Multi-armed bandit(멀티 암드 밴딧)은 탐색과 이용(Exploitaion & Exploitation)에 관한 강화 학습 분야의 유명한 문제이다. 평균 수익이 얼마인지 모르는 여러 개의 슬롯 머신이 있을 때, 어떤 슬롯 머신의 레버를 얼마나 당겨야 가장 높은 수익을 낼 수 있는가에 관한 문제로, 이름은 슬롯 머신을 일컫는 은어인 외팔 강도(One-armed bandit)에서 따왔다. 이 문제는 상태가 하나뿐인 마르코프 결정 과정(Markov Decision Process)으로 볼 수 있다.
용어
- arm (암)
- 각각의 슬롯머신을 의미한다. action이라고도 한다.
- regret (리그렛)
- 후회라는 뜻인데, 최선이 아닌 arm을 선택해서 입은 손해를 뜻한다. arm A를 선택했다면 100원을 벌 수 있었는데, arm B를 선택해 60원만 벌었다면 regret은 40이다. 실제로는 최선의 arm에서 얼마를 얻을지 모르기 때문에, 최선이 아닌 각 arm에 대해서, 최선의 arm의 기댓값과 해당 arm의 기댓값의 차이를 그 arm의 시행횟수만큼 곱한 것을 모두 더해 계산한다. 이 regret을 최소화하는 것이 이 문제의 목표이다.
전략
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]을 일정하게 나눠가지기 때문에 비효율적이다.
UCB 알고리즘
활용
웹사이트나 모바일 애플리케이션 등의 업데이트가 긍정적인 고객 반응(웹사이트 방문, 광고 클릭, 상품 결제 등)을 유도하는지 아닌지를 확인하고 싶을 때, 일부의 사용자에게는 기존 버전을, 다른 일부의 사용자에게는 새 버전을 보여줘서 테스트하는 것을 A/B테스트라고 부른다. 만약 새 업데이트가 사용자에게 부정적인 영향을 미친다면, 새 버전을 계속 노출하는 것이 큰 손해가 될 수도 있으며, 충분한 테스트를 거치지 않고 조급하게 결정을 내려버리는 경우도 발생할 수 있다. 이러한 테스트 과정에 밴딧 문제를 응용하면 테스트 기간 동안 일어날 수 있는 잠재적인 손해를 줄일 수 있고, 신뢰할 수 있을 만큼 테스트가 되었는지 역시 이론적으로 확인할 수 있다는 장점이 있다.