[Data] MAB(Multi-Armed Bandits) 찍먹하기

들어가며

MAB가 무엇이기 알아보기 전에 A/B Test로 돌아가고자 한다.

전통적인 A/B Test에는 여러 단점들이 존재한다. 대표적인 몇 가지 단

- 충분한 표본이 있지 않을 때, 테스트의 결과를 확신할 수 있을까?
- 취향의 변화를 반영하기가 어렵다.
- Test 기간이 길어질수록, (진행 비용등에 의해), 단기적ㅇ로 손해가 발생할 수 있다.

MAB(Multi-Armed Bandit)

MAB는, 슬롯 머신의 손잡이를(One-Armed Bandit)이라고 부르는 데에서 이름이 유래했다.

슬롯 머신이 여러대가 있다면, "어느 슬롯머신의 보상 확률이 가장 높고, 어느 슬롯 머신의 보상이 가장 큰지?'를 찾는 것이 중요할 것이다. 이러한 정보가 없다면 "어떤 순서로, 어떻게 슬롯머신을 당겨야 빠르게 가장 큰 보상을 얻을까?'를 고민해야 한다.

이를 위해서는 탐색과 보상을 얻는 과정을 반복해야 할 것이다.

최초에 정보가 없을 경우, 탐색은 불가피하다. 이 과정을 토대로 가장 승률이 높은 슬롯머신을 찾는다면, 해당 기계에 집중적으로 돈을 투자하면 된다.  하지만 다른 슬롯머신의 승률이 실제로는 더 높을수도 있기에, 포기를 할 수도 없다. 그래서 약간의 분량을 다른 슬롯머신에 투자를 하다, 해당 슬롯머신의 승률이 더 좋아질수도 있다. 이럴 때의 대응에 대해 고민해봐야 할 것이다.

Epsilon - Greedy Algorithm

위의 문제를 해결할 수 있는 가장 간단한 알고리즘이다.

ε라는 parameter를 도입하게 되는데, 여기서 이 ε는 가장 이득이 높다고 발견된 슬롯머신을 제외하고 나머지 하나를 택하는 과정을 고르게 된다. 

- 기본적으로는 이득이 가장 높은 슬롯머신을 굴린다.
- 그러다가, ε이 확률에 걸릴 경우, 나머지 슬롯머신을 굴린다.  (*)

이, (*) 과정이 must이기 때문에, 가장 최적의 슬롯 머신을 찾았음에도 불구하고, 계속 해당 확률 만큼의 새로운 탐사가 주어져 최적값과 무조건 멀어지게 된다는 큰 단점을 가지게 된다.  그리고 더 많은 선택지가 주어질 경우 낮은 확률로 새로운 슬롯머신의 탐사 기회가 주어지더라도, 그 중 하나를 또 골라야 하기에 정보가 부족한 선택지가 발생하게 된다.

개선 : UCB - The Upper Confidence Bound Algorithm

위의 단점을 해결하기 위해, 과거의 결과를 확인하려고 한다.
즉, 시간 t마다 과거의 관측 결과와 확률을 고려, 최적이 될만한 가능성을 수치로 표현하게 된다.

- t : 모든 슬롯머신을 선택한 횟수의 합
- Qt(a) : t 시점까지의, 슬롯머신 a 누적 보상
- c : 탐색의 정도를 결정. (탐색할지, 보상을 얻을지)
- Nt(a) : t 시점까지, 해당 슬롯머신을 선택한 횟수