Multi-Armed Bandit

Multi-Armed Bandit (MAB, 멀티 암드 밴딧)

여러 개의 슬롯머신(arm) 중 보상 분포를 모르는 채로 매번 하나를 당기며, 누적 보상을 최대화하는 의사결정 문제.
**탐색(exploration, 더 좋은 arm을 찾기) ↔ 활용(exploitation, 지금까지 최고인 arm을 당기기)**의 딜레마를 가장 순수한 형태로 담은 문제로, MCTS의 UCT, A/B 테스트, 추천/광고 시스템의 이론적 토대다.

multi-armed-bandit exploration-exploitation UCB reinforcement-learning

문제 설정

• “one-armed bandit”은 슬롯머신의 별명. **여러 팔(arm)**을 가진 슬롯머신을 상상한 데서 유래.
• $K$개의 arm이 있고, 각 arm $a$를 당기면 알 수 없는 분포에서 보상 $r$이 나온다. 평균 보상 ${\mu }_a=\mathbb{E}[r|a]$.
• 매 라운드 $t$에 arm $a_t$를 하나 골라 보상 $r_t$를 받는다. 목표: 총 $T$ 라운드의 누적 보상 최대화.
• 어려움: arm의 ${\mu }_a$를 모름 → 좋은 arm을 찾으려면 당겨 봐야(탐색) 하지만, 탐색에 쓴 라운드는 최선의 arm을 당기지 못한 손해다.

(Full) RL과의 차이

Bandit은 상태(state)가 없는 RL의 특수 케이스다. 행동이 다음 상태에 영향을 주지 않고(즉시 보상만 받음), 따라서 장기적 신용 할당(credit assignment) 문제가 없다. Basic RL에서 상태 전이를 제거하면 bandit이 된다.

Regret: 무엇을 최소화하나

성능은 보통 **regret(후회)**으로 잰다 — “전지적으로 최선의 arm만 골랐을 때 대비 얼마나 손해 봤나”:

$$R(T)=T{\mu }^{\ast }-\mathbb{E}\left[\sum _{t=1}^T{\mu }_{a_t}\right],{\mu }^{\ast }=\underset{a}{\max }{\mu }_a$$

• 좋은 알고리즘은 regret이 시간에 대해 sublinear($R(T)/T\to 0$) → 결국 거의 항상 최적 arm을 당기게 됨.
• 이론적 하한(Lai-Robbins): regret은 $\Omega (\log T)$ 이상으로 줄일 수 없다. 즉 $O(\log T)$ regret이 사실상 최적.

핵심 전략들

1. $\epsilon$-greedy

• 확률 $1-\epsilon$로 지금까지 평균 보상이 최고인 arm을 당기고(활용), 확률 $\epsilon$로 무작위 arm을 당긴다(탐색).
• 장점: 단순. 단점: 탐색이 무작위라 비효율적이고, 고정 $\epsilon$이면 regret이 선형($O(\epsilon T)$)으로 샌다 → ${\epsilon }_t$를 시간에 따라 줄여야 함.

2. UCB (Upper Confidence Bound)

“불확실하면 낙관적으로(optimism in the face of uncertainty)” — 추정 평균에 불확실성 보너스를 더해, 그 합이 최대인 arm을 당긴다.

$$a_t=\arg \underset{a}{\max }\left[{\hat{\mu }}_a+\sqrt{\frac{2\ln t}{N_a}}\right]$$

• ${\hat{\mu }}_a$: arm $a$의 표본 평균 보상(활용 항).
• $\sqrt{\frac{2\ln t}{N_a}}$: 덜 당겨 본($N_a$ 작은) arm일수록 커지는 탐색 보너스. 신뢰구간의 위쪽 끝.
• 자연스럽게 탐색→활용으로 수렴하며 $O(\log T)$ regret 달성. 이 UCB1이 MCTS의 UCT로 그대로 이어진다.

3. Thompson Sampling (베이지안) ❓

• 각 arm의 보상 확률에 대한 **사후분포(posterior)**를 유지하고, 매 라운드 각 분포에서 표본을 하나씩 뽑아 가장 큰 표본을 낸 arm을 당긴다.
• 베르누이 보상이면 Beta 사후분포로 깔끔하게 갱신(Beta-Bernoulli). 실무에서 UCB보다 자주 성능이 좋고 구현도 간단해 인기.
• “확률적으로 최적일 가능성에 비례해 arm을 고른다”는 직관 → probability matching.

변형(variants)

변형	설명
Stochastic MAB	각 arm 보상이 고정 분포에서 i.i.d. (기본형)
Adversarial MAB	보상을 적이 정함 → EXP3 알고리즘
Contextual Bandit	매 라운드 **문맥(feature) $x_t$**가 주어지고 보상이 $x_t$에 의존 → 추천/광고의 실전 형태(LinUCB 등)
Non-stationary	보상 분포가 시간에 따라 변함(할인·슬라이딩 윈도우)

어디에 쓰이나

• 추천 / 광고 / 뉴스 배열: 어떤 아이템을 노출할지를 contextual bandit으로. 클릭=보상.
• A/B 테스트의 대안: 고정 비율 분할 대신, 좋은 변형에 트래픽을 적응적으로 몰아 손실(regret)을 줄임.
• 하이퍼파라미터 / 임상시험: 유망한 설정·치료에 자원을 적응 배분.
• MCTS: 트리의 각 노드에서 “어느 자식으로 갈까”를 작은 bandit 문제로 보고 UCB를 재귀 적용한 것이 UCT.

Related

• Monte Carlo Tree Search(MCTS) — UCT는 MAB의 UCB1을 트리에 적용한 것.
• Basic RL — bandit은 상태 없는 RL의 특수 케이스.
• Importance Sampling — off-policy bandit 평가(로그 데이터로 새 정책 평가)에서 가중치 보정에 등장.