Multi-armed bandit

Multi-armed bandit(멀티 암드 밴딧, MAB)은 탐색과 이용(Exploitaion & Exploitation)에 관한 강화 학습 분야의 유명한 문제이다. 평균 수익이 얼마인지 모르는 여러 개의 슬롯 머신이 있을 때, 어떤 슬롯 머신의 레버를 얼마나 당겨야 가장 높은 수익을 낼 수 있는가에 관한 문제로, 이름은 슬롯 머신을 일컫는 은어인 외팔 강도(One-armed bandit)에서 따왔다. 이 문제는 상태가 하나뿐인 마르코프 결정 과정(Markov Decision Process)으로 볼 수 있다.

용어

arm (암)

각각의 슬롯머신을 의미한다. action이라고도 한다.

reward (보상)

슬롯머신의 arm을 당길 때 얻는 수익을 말한다.

regret (리그렛)

후회라는 뜻인데, 최선이 아닌 arm을 선택해서 입은 손해를 뜻한다. arm A를 선택했다면 100의 reward를 얻을 수 있었는데, arm B를 선택해 60의 reward만 얻었다면 regret은 40이다. 실제로는 최선의 arm에서 얼마를 얻을지 모르기 때문에, 최선이 아닌 각 arm에 대해서, 최선의 arm의 기댓값과 해당 arm의 기댓값의 차이를 그 arm의 시행횟수만큼 곱한 것을 모두 더해 계산한다. 이 regret을 최소화하는 것을 목표로 한다.

exploration (탐색)

어떤 arm이 최선인지 찾기 위해 (지금까지의 평균이 가장 높지 않은) arm들을 시행해보는 것을 말한다. 큰 수의 법칙에 의해 어떤 arm을 많이 시행해볼 수록 더 정확한 기댓값을 얻을 수 있게 된다.

exploitation (이용)

시행을 통해 추정한 최선의 arm을 시행해서 이득을 얻는 것을 말한다. 탐색에만 너무 치중할 경우 최선이 아닌 arm이 너무 많이 선택되어 손해를 보고, 이용에만 너무 치중할 경우 최선이 아닌 arm을 최선이라고 착각하는 경우가 발생할 수 있다. 따라서 탐색과 이용의 비율을 적절히 선택하는 것이 핵심이다.

전략

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 알고리즘

UCB (Upper Confidence Bound) 알고리즘은 현재까지 테스트해본 arm의 평균값과 시행 횟수를 이용해 모평균이 어느 범위에 있을지 추정하고, 그 범위의 상한이 가장 높은 arm을 선택하는 알고리즘이다. 시행횟수가 적은 arm은 이 범위가 넓어지고, 시행횟수가 많은 arm은 범위가 좁아지도록 하여 탐색과 이용을 적절하게 분배할 수 있다.

UCB1

UCB 알고리즘의 일종인 UCB1은 다음과 같다.

1. 우선 모든 arm을 한 번씩 시도해본다.
2. UCB [math]\displaystyle{ \bar {x}_i+\sqrt{2\log n \over n_i} }[/math]를 최대로 만드는 arm [math]\displaystyle{ i }[/math]를 선택한다.
3. 2를 반복한다.

여기서 [math]\displaystyle{ \bar {x}_i }[/math]는 arm [math]\displaystyle{ i }[/math]에서 지금까지 얻은 reward의 평균(empirical mean), [math]\displaystyle{ n }[/math]은 여태까지 어떤 arm이든 시도한 총 횟수이고, [math]\displaystyle{ n_i }[/math]는 그 중 arm [math]\displaystyle{ i }[/math]를 시도한 횟수이다.

[math]\displaystyle{ K }[/math]개의 arm이 있는 밴딧 문제에서 이 알고리즘을 따랐을 경우, 최대 regret은 다음과 같다.

[math]\displaystyle{ \displaystyle \left[8\sum_{i:\mu_i\lt \mu^*} \left({\log n \over \Delta_i}\right)\right] + \left(1+{\pi^2 \over 3}\right)\left(\sum_{i\in[K]} \Delta_i\right) }[/math]

여기서 [math]\displaystyle{ \mu_i }[/math]는 [math]\displaystyle{ i }[/math]번째 arm의 평균 reward, [math]\displaystyle{ \mu^* }[/math]는 최적의 arm의 평균 reward를 말하며, [math]\displaystyle{ \Delta_i :=\mu^*-\mu_i }[/math]는 최적의 arm과 [math]\displaystyle{ i }[/math]번째 arm간의 평균 reward 차이를 말한다. [math]\displaystyle{ [K] }[/math]는 1부터 [math]\displaystyle{ K }[/math]까지의 자연수 집합이다.

KL-UCB

KL-Divergence를 이용하는 알고리즘으로, reward들의 확률분포에 관한 정보가 있을 경우에 사용할 수 있는 알고리즘이다.

활용

웹사이트나 모바일 애플리케이션 등의 업데이트가 긍정적인 고객 반응(웹사이트 방문, 광고 클릭, 상품 결제 등)을 유도하는지 아닌지를 확인하고 싶을 때, 일부의 사용자에게는 기존 버전을, 다른 일부의 사용자에게는 새 버전을 보여줘서 테스트하는 것을 A/B테스트라고 부른다. 만약 새 업데이트가 사용자에게 부정적인 영향을 미친다면, 새 버전을 계속 노출하는 것이 큰 손해가 될 수도 있으며, 충분한 테스트를 거치지 않고 조급하게 결정을 내려버리는 경우도 발생할 수 있다. 이러한 테스트 과정에 밴딧 문제를 응용하면 테스트 기간 동안 일어날 수 있는 잠재적인 손해를 줄일 수 있고, 신뢰할 수 있을 만큼 테스트가 되었는지 역시 이론적으로 확인할 수 있다는 장점이 있다.