멀티 암드 밴딧(Multi‑Armed Bandit, 약칭 MAB)은 확률적 보상을 제공하는 여러 선택지(‘암(arm)’이라고도 함) 중에서 순차적으로 하나를 선택하면서 누적 보상을 최대화하고자 하는 최적화 문제를 가리킨다. 이 용어는 실제 카지노의 슬롯머신(‘one‑armed bandit’)이 여러 대 배열된 모습을 비유적으로 차용한 것이다.
개념 및 정의
- 문제 형식: 시간 $t = 1, 2, \dots, T$에 걸쳐 에이전트는 $K$개의 암 중 하나 $a_t \in {1,\dots,K}$를 선택한다. 선택된 암에서 얻는 보상 $r_t$는 해당 암에 대한 확률 분포 $P_a$에 의해 무작위로 생성된다.
- 목표: 전체 시점 $T$ 동안의 기대 누적 보상 $\mathbb{E}\left[\sum_{t=1}^{T} r_t\right]$을 최대로 하는 정책을 설계한다. 동등하게, 레지 regret(후회) $\displaystyle R_T = T\mu^* - \mathbb{E}\left[\sum_{t=1}^{T} r_t\right]$를 최소화하는 것이 일반적인 평가 기준이다. 여기서 $\mu^* = \max_{a}\mathbb{E}[r|a]$는 최적 암의 평균 보상이다.
주요 가정
- 정적 분포: 각 암의 보상 분포는 시간에 따라 변하지 않는다고 가정한다(정적 MAB).
- 독립성: 암 간 보상은 서로 독립적이며, 동일 시점에 여러 암을 동시에 선택하지 않는다.
- 보상의 제한: 보통 0‒1 구간 또는 유한 구간으로 제한되어 분석이 용이하다.
대표적인 알고리즘
| 알고리즘 | 핵심 아이디어 | 특징 |
|---|---|---|
| ε‑greedy | 탐색(exploration) 확률 ε을 고정하거나 감소시키면서, 나머지 시간에 현재까지 평균 보상이 가장 높은 암을 선택 | 구현이 간단하나, 탐색률 조절에 민감 |
| Upper Confidence Bound (UCB) | 각 암에 대한 평균 보상에 신뢰 구간 상한을 더해, 상한이 가장 큰 암을 선택 | 이론적 regret 상한이 $\mathcal{O}(\log T)$로 보장됨 |
| Thompson Sampling | 베이지안 사후 분포에서 샘플을 추출해 가장 높은 샘플 값을 가진 암을 선택 | 실험적 성능이 우수하고, 다양한 보상 모델에 적용 가능 |
| KL‑UCB, Exp3 등 | Kullback‑Leibler divergence 기반 상한, adversarial 환경 전용 등 특수 상황에 대응 | 각각의 환경 가정에 최적화된 변형 |
응용 분야
- 온라인 광고: 광고 소재(암)를 순차적으로 보여주어 클릭률(CTR)을 최대화.
- 추천 시스템: 사용자에게 제시할 아이템을 선택해 만족도(보상)를 증가.
- 임상 시험: 치료법(암)의 효능을 실시간으로 평가하면서 환자에게 최적 치료 제공.
- 자원 할당: 네트워크 트래픽, 클라우드 컴퓨팅 자원 등에서 동적 정책 수립.
확장 형태
- 컨텍스트드 밴딧(Contextual Bandit): 각 선택 시점에 관측되는 특징(context)을 이용해 조건부 정책을 학습한다.
- 다중 플레이어/협동 밴딧: 여러 에이전트가 동시에 행동하고 보상이 상호 영향을 받는 경우.
- 비정적/Adversarial 밴딧: 보상 분포가 시간에 따라 변하거나 적대적(악의적) 환경이 존재하는 경우.
학술적 의의
멀티 암드 밴딧은 강화학습(Reinforcement Learning) 분야에서 탐색‑활용(trade‑off) 문제의 가장 단순화된 형태로 간주되며, 복잡한 마르코프 의사결정 과정(MDP)보다 분석 및 알고리즘 설계가 상대적으로 용이하다. 따라서 새로운 탐색 전략의 이론 검증이나 실험적 비교에 널리 활용된다.
참고 문헌(대표)
- Lai, T. L., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics.
- Auer, P., Cesa‑Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multi‑armed bandit problem. Machine Learning.
- Agrawal, S., & Goyal, N. (2012). Thompson Sampling for Contextual Bandits with Linear Payoffs. ICML.
본 항목은 멀티 암드 밴딧이 널리 알려진 학술·산업 용어임을 근거로 하며, 현재까지 검증된 정보를 바탕으로 기술하였다.
