적대적 커널화된 밴딧을 위한 거의 최적 알고리즘

요약

본 논문은 적대적 환경에서 커널화된 밴딧(kernelized bandits) 문제를 다루며, 특히 알려진 재생 커널 힐베르트 공간(RKHS) 내의 보상 함수가 매 라운드마다 적대적으로 선택될 수 있는 상황을 가정합니다. 연구진은 지수 가중치 알고리즘을 제안하여 $ ilde{O}(\sqrt{T \gamma_T})$의 적대적 후회(adversarial regret)를 달성함을 증명했습니다. 또한, 이 알고리즘이 다항로그 계수까지 최적임을 보장하는 하한 경계를 제시하고, 계산 효율성을 높인 변형도 제안합니다.

핵심 포인트

• 적대적 환경에서의 커널화된 밴딧(Kernelized Bandits) 문제를 연구함.
• 지수 가중치 알고리즘을 통해 $ ilde{O}(\sqrt{T \gamma_T})$의 적대적 후회(Adversarial Regret)를 달성함을 증명함.
• 제안된 알고리즘이 다항로그 계수까지 최적임을 보장하는 하한 경계를 제시함.
• Nyström 근사 기법을 활용하여 계산 효율성을 유지하면서도 거의 최적의 후회 보장을 제공함.