📚 멀티암드 밴딧 알고리즘

N개의 슬롯머신이 있고, 각각의 슬롯머신은 수익률이 다르다고 하자.
그렇다면 어느 머신에 돈을 걸고 암(슬롯머신의 손잡이)를 내려야 할까?
슬롯머신을 밴딧(강도), 손잡이를 암이라고 하고,
성공하기 위해서는 어느 슬롯머신을 노려야 하는지 구하는 알고리즘이다.

💡 예시

• A, B, C 세 슬롯머신이 있다고 하자.

• 각각 50번씩 돌렸다고 할 때, 다음과 같은 결과를 얻었다:
  A) 50번 중 10번 승리
  B) 50번 중 2번 승리
  C) 50번 중 4번 승리

• 1) 단순히 봤을 때는, A가 최고! 라는 결론을 내릴 수 있다. 따라서 A만 당기자는 판단을 내렸다고 하자.

• 다만 이 경우, 이익을 초기에 얻게 되지만 장기적으로 B와 C가 더 우월하다면 이 사실을 발견할 기회를 놓치게 된다.

• 2) 그렇다면 이번에는 '모두 무작위니 그냥 다 똑같이 당기자!' 전략을 써볼 수 있다.

• 이 경우, A 외에도 다른 슬롯머신의 확률을 알 기회가 생기지만, 수익률이 낮을 것으로 예상되는 행위를 반복해야 한다. 언제까지 꼬라박게?

💡 MAB는 이 경우 하이브리드 접근 방식을 취한다.

🎲 A가 우월하다면 B와 C의 기회를 A로 좀 몰아준다. 그러나 B, C를 놓지는 않는다.
🎲 A가 나빠지기 시작하고 B나 C가 좋아지기 시작하면 뺏긴 기회를 돌려준다.
🎲 그 중 하나가 A보다 우월하고 이게 우연에 의해 발견되지 않은 것이라면 이제는 많은 테스트를 통해 이를 밝힐 수 있다!

실제로도 비즈니스 어플리케이션에서 상당한 성과를 보이고 있다고 한다.

이 때 엡실론-그리디(epsilon-greedy), 톰슨 샘플링 등의 알고리즘이 쓰인다.

🛩 엡실론-그리디 알고리즘

• 간단한 A/B 검정을 위한 알고리즘.

1) 0~1 사이 균등분포의 난수를 생성한다.
2) 이 숫자가 0~$\epsilon$ 사이에 존재하면 , 5:5 확률로 동전 던지기를 시행한다.

• 2-1) 결과가 앞면이면 A를 표시
• 2-2) 결과가 뒷면이면 B를 표시

3) 숫자가 $\epsilon$보다 크면 지금까지 가장 좋은 결과를 보인 제안을 표시한다.

엡실론은 이 알고리즘을 제어하는 단일 파라미터로, 0인 경우 완전한 그리디 알고리즘(현재 최상인 제안 선택)이 되고, 1인 경우 완전한 A/B검정(랜덤)이 된다.

😾 톰슨 샘플링

• 베타 분포를 사용하여 성공률을 계산하는 방법.
• 매 판단 단계에서 x값을 임의추출하여 비교하기 때문에 다음번에 최고 손잡이를 선택할 확률을 최적화할 수 있다.
• 자세한 내용은 톰슨 샘플링에 잘 설명되어 있다.

  👨‍🏫 참고
  https://brunch.co.kr/@chris-song/62
  https://brunch.co.kr/@chris-song/66
  책 [데이터 과학을 위한 통계]