Multi-armed bandit(멀티 암드 밴딧)은 탐색과 이용(Exploitaion & Exploitation)에 관한 강화 학습 분야의 유명한 문제이다. 평균 수익이 얼마인지 모르는 여러 개의 슬롯 머신이 있을 때, 어떤 슬롯머신의 레버를 얼마나 당겨야 가장 높은 수익을 낼 수 있는가에 관한 문제로, 이름은 슬롯 머신을 일컫는 은어인 외팔 강도(One-armed bandit)에서 따왔다.
전략
Epsilon-greedy 전략
Epsilon-greedy ([math]\displaystyle{ \epsilon }[/math]-greedy) 전략은 지금까지 관찰한 결과 가장 기댓값이 높은 arm을 [math]\displaystyle{ 1 - \epsilon }[/math]의 확률로, 그렇지 않은 arm을 [math]\displaystyle{ \epsilon }[/math]의 확률로 시도해보는 전략이다. 무한히 많은 시행을 거치면 가장 기댓값이 큰 arm을 발견할 수 있지만, 그렇게 발견한 뒤에도 일정 확률로 계속 테스트해보기 때문에 Regret이 시행 횟수에 정비례([math]\displaystyle{ O(n) }[/math])한다. [math]\displaystyle{ \epsilon }[/math]을 고정해놓지 않고 시행 횟수에 반비례([math]\displaystyle{ \epsilon \propto 1/t }[/math])하게 만들면 Regret이 [math]\displaystyle{ O(\log n) }[/math]으로 좋아진다. 그러나 이 전략은 현저하게 나쁜 것으로 밝혀진 arm과, 최적일 가능성이 남아있는 arm을 구분하지 않고 [math]\displaystyle{ \epsilon }[/math]을 일정하게 나눠가지기 때문에 비효율적이다.