멀티 암드 밴딧(Multi-Armed Bandits)

MAB (Multi-Armed Bandits)

• 카지노에서 슬롯머신 투자를 최적화하기 위해 만들어진 알고리즘
• 슬롯머신이 밴딧(Bandit)
• 슬롯머신의 손잡이가 암(Arm)
• 다양한 슬롯머신이 있는데 내 돈을 어디에 걸고 손잡이를 내려야 하나?

탐색과 활용 (Exploration and Exploitation)

1. greedy 전략

• 한 번씩 플레이한 후, 점수 좋은 슬롯 머신에 몰빵

2. 입실론 그리디 (e-greedy)

• 동전을 던져서 윗면이 나오면 점수 좋았던 슬롯머신, 뒤면이 나오면 랜덤으로 선택
• 동전의 앞면이 나올 50%의 확률이 입실론(epsilon)이라는 하이퍼파라미터

3. UCB (Upper-Confidence-Bound)

• 좋은 수익률을 보이며 최적의 선택이 될 가능성이 있는 슬로머신을 선택

중간 요약

• MAB는 A/B 테스트 전략의 진화된 버전이라 볼 수 있음
• A/B 테스트의 몇 가지 문제점:
  • 테스트를 하는 데 오래걸리고 비용이 많이 듬
  • A/B 테스트를 할 때 A안이 훨씬 좋았다면 테스트 기간 동안엔 B안으로 인해 결국 손해를 봄
  • A/B 테스트를 할 때는 A안이 좋았는데 일주일이 지나니 B안 반응률이 더 좋아짐
• A/B 테스트의 몇 가지 문제들이 멀티암드밴딧을 사용하면 문제가 말끔히 해결된다고 함

---

A/B 테스트의 몇 가지 문제들이 멀티암드밴딧을 사용하면 문제가 말끔히 해결되는 이유들

A/B 테스트의 문제점을 멀티암드밴딧(Multi-Armed Bandit, MAB)을 사용하면 해결할 수 있는 이유는 멀티암드밴딧이 동적이고 효율적인 탐색 및 활용 전략을 기반으로 작동하기 때문

1. A/B 테스트의 주요 문제점

(1) 테스트에 시간이 오래 걸리고 비용이 많이 듦

• A/B 테스트는 고정된 비율로 트래픽을 나누어 데이터를 수집해야 하므로, 충분한 통계적 유의미성을 확보하려면 많은 시간이 필요합니다.
• 특히, 트래픽이 적은 경우 더 오랜 시간이 소요됩니다.

(2) 손해를 감수해야 함

• A/B 테스트는 초기에 A안과 B안을 동일한 비율로 노출하기 때문에, 더 나쁜 옵션(B안)이 많은 트래픽을 차지해도 일정 기간 동안 유지됩니다.
• 이는 비효율적인 선택으로 인한 기회비용을 발생시킴

(3) 시간에 따른 사용자 반응 변화

• A/B 테스트는 고정된 기간 동안 데이터를 수집하므로, 시간에 따라 사용자 선호가 변하는 경우 이를 반영하지 못합니다.
• 예: 특정 이벤트나 주기적 변화로 인해 테스트가 끝난 후 다른 결과가 나타날 수 있음.

---

2. 멀티암드밴딧(MAB)이 문제를 해결하는 이유

멀티암드밴딧은 탐색(Exploration)과 활용(Exploitation)의 균형을 자동으로 조정하여, 실시간으로 데이터를 분석하고 최적의 옵션을 동적으로 선택함

(1) 효율적인 자원 분배

• MAB는 실험 기간 동안 성능이 좋은 옵션에 더 많은 트래픽을 할당합니다.
  • 예: A안이 B안보다 좋다는 초기 신호를 감지하면, A안에 더 많은 트래픽을 할당.
• 반대로, A/B 테스트는 모든 옵션에 동일한 트래픽을 분배하므로 비효율적입니다.

(2) 손해를 최소화

• 더 나쁜 옵션에 트래픽을 적게 할당하기 때문에, 비효율적인 선택으로 인한 손해를 줄일 수 있습니다.
  • 예: B안이 더 나쁜 성과를 보이면, B안에 배정된 트래픽을 점차 줄이고 A안에 집중.

(3) 실시간 반응

• MAB는 시간에 따른 사용자 반응 변화를 실시간으로 반영합니다.
  • 예: 초기에는 A안이 좋았지만, 시간이 지나면서 B안의 반응률이 좋아진다면 B안에 더 많은 트래픽을 할당.

(4) 테스트 시간을 단축

• A/B 테스트는 통계적 유의미성을 얻기 위해 고정된 기간 동안 데이터를 수집해야 하지만, MAB는 실시간으로 데이터를 분석하고 결정을 내리기 때문에 테스트 기간을 단축할 수 있습니다.

---

3. 작동 원리

멀티암드밴딧 알고리즘은 다양한 변형이 있지만, 기본적으로 다음과 같은 방식을 사용합니다:

1. 탐색(Exploration): 각 옵션의 성과를 탐색하기 위해 일부 트래픽을 분배.
2. 활용(Exploitation): 현재까지의 데이터를 기반으로 가장 좋은 옵션에 더 많은 트래픽을 할당.
3. 동적 업데이트: 실시간으로 데이터를 분석하고, 결과에 따라 탐색과 활용의 비율을 조정.

주요 알고리즘:

• Epsilon-Greedy: 일정 비율(ε)로 탐색하고, 나머지 비율(1-ε)로 최적의 옵션을 선택.
• Upper Confidence Bound (UCB): 옵션의 평균 성과와 불확실성을 고려해 선택.
• Thompson Sampling: 확률적 접근 방식을 사용해 각 옵션의 성과를 모델링하고 선택.

---

4. 예시

A/B 테스트

• 트래픽의 50%를 A안에, 나머지 50%를 B안에 고정 배분.
• 결과가 유의미할 때까지 기다려야 함.

멀티암드밴딧

• 초기에는 A안과 B안을 탐색하면서 데이터를 수집.
• A안이 더 좋은 성과를 보이면, 점차 A안에 트래픽을 집중.
• 시간이 지나면서 B안이 더 좋아지는 경우, B안에 트래픽을 다시 분배.

5. 결론

멀티암드밴딧은 다음과 같은 이유로 A/B 테스트의 주요 문제를 해결합니다:
1. 효율적 자원 활용: 더 나은 옵션에 트래픽을 집중시켜 손해를 최소화.
2. 실시간 학습: 시간에 따른 사용자 반응 변화를 반영.
3. 빠른 테스트 종료: 고정된 테스트 기간 없이도 최적의 결과를 얻을 수 있음.

A/B 테스트와 비교해 멀티암드밴딧은 효율성, 동적 적응성, 손해 최소화에서 뛰어난 장점을 제공함

Reference

• https://brunch.co.kr/@chris-song/62
• https://github.com/bgalbraith/bandits
• https://github.com/johnmyleswhite/BanditsBook
• Chapter2. Multi-Armed Bandits, Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto
• https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf