[Data] Multi-Armed Bandit - 개념편

다음 글을 기반으로 정리하였습니다.

- https://playinpap.github.io/mab/#mab%EA%B0%80-%EC%99%9C-%EB%98%91%EB%98%91%ED%95%9C%EA%B0%80
- https://hardenkim.tistory.com/181
- https://yjjo.tistory.com/38
- https://soobarkbar.tistory.com/135

 

들어가기

현업에서 데이터 분석을 하다보면, A/B 테스트는 피할 수 없습니다. 하지만 테스트는 공짜가 아니죠. 그리고 여러 딜레마적인 상황도 발생합니다. 이를 정리하면 다음과 같습니다.

- A/B 테스트를 진행할수록, 기회 비용이 발생한다. 
- 하지만 그렇다고 A/B 테스트를 짧게 하면 신뢰성에 문제가 생긴다.
- 결정적으로 비즈니스 의사결정이 2지선다라는 보장은 없는데, A/B 테스트는 기본적으로 2지선다이다.

이러한 문제를 해결하기 위해 Multi-Armed Bandit(MAB)를 고려해볼 수 있습니다.

Multi-Armed Bandit의 목표 및 용어

앞에서 언급한 A/B 테스트의 두 가지 딜레마인 기회 비용 발생과, 신뢰성의 문제  이 두 가지를 해결하기 위해서는 적절한 시점까지 테스트를 하고 대안을 찾아야 합니다. 이를 체계적으로 논하는 것이 MAB 입니다. 즉, MAB에서는 적절한 탐색 과정을 통해서 최적의 수익을 내는 것이 목표입니다. 즉, 어느 순간까지 탐색하고, 어떤 결정을 내려서 탐색을 종료할 것인지 이를 풀어보는 알고리즘을 제시하게 될 것입니다.

다음은 MAB에서 사용하게 될 용어입니다.
- 행동 : MAB에서 선택하게 되는 대안입니다.
- 보상 : 한 번의 행동에 따른 수치화된 결과입니다.
- 가치 : 행동에 의한 기대 보상입니다.

MAB와 A/B 테스트와 근본적으로 다른 점은, A/B테스트는 테스트가 끝나고 하나의 대안을 선택하는 것이라면 MAB는 점진적으로 행동의 보상, 가치를 통해 좋은 행동을 점진적으로 찾아나간다는 것입니다.

https://www.codemotion.com/magazine/frontend/design-ux/multi-armed-bandits-a-better-way-to-a-b-test/

 

MAB의 다양한 알고리즘

MAB 문제를 해결할 수 있는 대표적인 알고리즘들을 살펴보겠습니다.

Algorithm 1 : Greedy

가장 쉽게 생각할 수 있는 알고리즘입니다. 대안을 하나씩 선택 후, 가장 수익이 높은 대안으로 선택합니다.
탐색을 충분하게 하지 못한다는 단점이 존재합니다. 특히, 그리디의 가장 큰 문제점은 한 번의 우연을 통해 높게 나온 값을 따라갈 경우, 그 리스크가 크다는 점입니다.

Algorithm 2 : Epsilon - Greedy Algorithm

앞의 그리디 알고리즘은 무지성(?)으로 하나의 선택지만 따라간다면, 이 알고리즘은 그리디 알고리즘에서 탐색을 조금 더 촉진하기 위한 방법입니다. 기본적으로는 그리디를 따라가나, ε라는 낮은 확률에 당첨될 경우, 무작위 선택을 합니다.

하지만 이 방법은 최적의 선택지를 찾았더라도, 해당 선택지를 항상 고를 수 있는 것이 아니기에 최적의 수익을 얻는 방법으로 적합하진 않습니다. 

Algorithm 3 : Softmax Algorithm

알고리즘 2의 상황을 조금 더 생각해봅시다. 낮은 확률에 당첨되어 무작위 선택을 할 때, 이 확률은 동일하게 적용됩니다. 하지만 이게 최선일까요? 우리는 실험 데이터가 쌓일수록 대안들의 순위를 어렴풋이 알게 됩니다. 이미 안 될 선택지를 무리해서 많이 탐색할 이유는 없습니다.  즉, 등수에 대한 보정이 필요한데, 이를 softmax 함수로 해결해줍니다.

즉, 그리디가 아닌 선택을 할 때에는 기존의 수익률에 보정이 반영된 softmax 함수를 기반으로 다음 선택지를 고릅니다.
위에서 말한 점진적 선택이 조금 더 이뤄지는 구조겠네요.

Algorithm 4 : UCB Algorithm (Upper Confidence Bound Algorithm)

하지만, 위의 알고리즘들은 적된 수익의 값만을 보여줍니다. 즉, 수익들의 분포에 대해서는 고려하지 않습니다.
정확하게는, 이 결과가 얼마나 많은 탐색을 통해 이뤄줬는가, 그 횟수에 대한 보정이 없습니다. 이 횟수에 대한 보정이 일어나는 것이 바로 UCB Algorithm 입니다.

더 이상, 랜덤 탐색을 사용하지 않습니다. 

- t : 탐색횟수 총 합
- Nt(a) : a를 선택한 횟수
- Qt(a) : a 선택의 총 누적 보상
- c : 탐색의 정도를 결정하는 hyperparameter

즉, 여기서는 선택지들 중 선택율이 낮았던 것에 자동으로 보정이 들어갑니다. 물론 되도않는 선택지는 알아서 버려지는 효과도 있습니다.  c의 값을 크게 할 경우 선택지의 탐색이 빈번하겠고, c의 값이 작아질수록 greedy에 가까워 집니다.

실전편에서는 위의 알고리즘들을 구현해보고, 실제 데이터에 적용하는 시간을 가져보겠습니다.