다중 슬롯머신 문제 (multi-armed bandit)
한 줄 정의: 보상 확률을 모르는 여러 선택지 중에서 총보상을 최대화하도록 반복 선택하는 문제입니다.
쉽게 풀면
당첨 확률이 제각각인 슬롯머신이 여러 대 있는데, 어느 것이 좋은지 미리 알 수 없는 상황입니다. 이미 괜찮아 보이는 기계만 계속 당기면 더 좋은 기계를 놓칠 수 있고, 여기저기 시험만 하면 좋은 기계로 벌 기회를 잃습니다. 정해진 횟수 안에서 이 둘의 균형을 어떻게 잡을지가 문제의 핵심입니다.
왜 중요한가
상태 전이가 없는 가장 단순한 순차적 의사결정 문제여서 탐색-활용 절충을 이론적으로 가장 깨끗하게 분석할 수 있습니다. 온라인 광고 노출, 웹 페이지 A/B 실험, 임상시험의 적응적 배정, 추천 시스템의 신규 항목 노출 등 현실 응용이 매우 넓습니다. 강화학습 이론의 후회 분석 기법 대부분이 여기서 출발했습니다.
논문에서는 이렇게 쓰입니다
"본 실험은 다중 슬롯머신 설정에서 누적 후회의 상한이 로그 차수로 증가함을 실증적으로 확인하였다."
최적 선택 대비 손해가 시행 횟수에 비해 매우 느리게만 늘어난다는 이론을 실험으로 확인했다는 뜻입니다.
조금 더 깊게 보면
성능은 대개 항상 최적 팔만 당겼을 때와의 보상 차이를 누적한 후회로 측정하며, 좋은 알고리즘은 후회가 시행 횟수의 로그에 비례해 증가합니다. 대표적 방법으로는 일정 확률로 무작위 선택을 섞는 ε-탐욕, 불확실성이 큰 팔에 낙관적 점수를 주는 상한 신뢰구간 알고리즘, 사후분포에서 표본을 뽑아 선택하는 톰프슨 샘플링이 있습니다. 각 선택지에 특징 벡터가 딸린 문맥적 밴딧으로 확장하면 개인화 추천에 바로 적용됩니다.
주의할 점
마르코프 결정 과정과 달리 선택이 다음 상태를 바꾸지 않는다는 가정이 있어, 행동의 장기적 파급을 다루지 못합니다. ‘밴딧’은 슬롯머신의 속칭에서 온 말이지 악의적 공격자를 뜻하지 않는다는 점도 유의하세요.