Multi-Armed Bandits

정의

multi-armed bandit은 $K$개의 arm 중 매 라운드 $t$에 하나의 arm $A_t$를 당겨 보상(reward)을 관측하는 순차적 의사결정 문제다. 목표는 누적 후회(cumulative regret)를 최소화하는 것이다. $R_T=T\mu^\*-\mathbb{E}\Big[\sum_{t=1}^T \mu_{A_t}\Big],\quad \mu^\*=\max_k\mu_k.$ 핵심은 탐색(exploration)과 활용(exploitation) 사이의 균형이다. UCB는 낙관적 추정값을 쓰는 대표 알고리즘으로 $A_t=\arg\max_k\big(\hat\mu_k+\sqrt{2\log t/N_k}\big)$를 당겨 $O\!\big(\sum_{k:\Delta_k>0}\log T/\Delta_k\big)$의 후회를 달성하며, 이는 Lai–Robbins 하한에 도달한다. **Thompson Sampling**은 사후분포에서 표집해 arm을 고른다. contextual bandit이나 linear bandit으로 확장할 수 있다(contextual/linear bandits).

직관적 이해

불확실한 arm을 더 시도하는 탐색과 지금까지 가장 좋았던 arm을 당기는 활용 사이에서 최적의 균형을 찾는 문제다. concentration 부등식과 minimax 논증이 후회 이론을 떠받치는 핵심 도구다.

관련 개념

• Contextual Bandits · Thompson Sampling · MDP(→RL 가교) · Off-Policy Evaluation

참고 논문

• Lattimore & Szepesvári, Bandit Algorithms, Cambridge UP 2020 (무료 PDF) — bandit 커리큘럼 전체
• Russo, Van Roy, Kazerouni, Osband & Wen, “A Tutorial on Thompson Sampling”, FnT in ML 11(1), 2018