Multi-Armed Bandits

정의

$K$개 arm, 매 라운드 $t$에 $A_t$를 당겨 보상 관측. cumulative regret 최소화: $R_T=T\mu^\*-\mathbb{E}\Big[\sum_{t=1}^T \mu_{A_t}\Big],\quad \mu^\*=\max_k\mu_k.$ explore–exploit 균형. 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)$ regret, Lai–Robbins 하한 달성. Thompson Sampling: 사후분포 표집. 확장: contextual/linear bandits.

직관적 이해

“불확실한 arm을 더 시도(explore) vs 지금까지 최선을 당기기(exploit)“의 최적 균형. concentration·minimax 논증이 regret 이론의 핵심 도구.

관련 개념

• 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