다중 팔 밴딧 문제(multi-armed bandit problem)는 때때로 K- 또는 N-팔 밴딧 문제라고도 불리며, 확률론과 머신러닝의 기초 개념이다. 이 이름은 "한 팔 밴딧(one-armed bandits)"이라고 불리는 슬롯 머신 줄을 마주한 도박꾼이 어떤 기계를 플레이할지, 각 기계를 몇 번 플레이할지, 어떤 순서로 플레이할지 결정하면서 현재 기계를 고수할지 다른 기계를 시도할지도 결정해야 하는 상황에서 유래했다. 더 일반적으로, 이는 각 선택지의 속성이 할당 시점에 부분적으로만 알려져 있고 시간이 지남에 따라 더 잘 이해될 수 있을 때, 여러 고정 선택지(팔 또는 행동이라고 함) 중 하나를 반복적으로 선택하는 의사 결정자를 설명한다. 핵심적인 측면은 팔을 선택하는 것이 해당 팔이나 다른 팔의 속성에 영향을 미치지 않는다는 점이며, 이는 행동이 미래 상태와 보상 분포를 변경할 수 있는 더 광범위한 강화학습 문제와 구별된다.
이 문제는 머신러닝의 핵심 딜레마인 탐험-활용 트레이드오프(exploration-exploitation tradeoff)를 예시한다. 도박꾼은 알려진 기대 보상이 가장 높은 기계를 "활용(exploitation)"하는 것과 다른 기계에 대한 정보를 더 수집하는 "탐험(exploration)" 사이에서 균형을 맞춰야 한다. 목표는 일련의 레버 당김을 통해 얻는 총 보상을 최대화하는 것이다. 이 트레이드오프는 임상 시험, 적응형 네트워크 라우팅, 금융 포트폴리오 설계, 연구 조직의 자원 할당 등 많은 실제 응용 분야에 나타난다.
다중 팔 밴딧 문제는 원래 제2차 세계 대전 중 연합군 과학자들에 의해 고려되었지만, 너무 다루기 어려워서 Peter Whittle에 따르면 독일 과학자들도 시간을 낭비하게 하기 위해 독일 상공에 투하하자는 제안이 있었다고 한다. 현재 일반적으로 분석되는 버전은 1952년 Herbert Robbins가 그의 논문 "Some Aspects of the Sequential Design of Experiments"에서 수렴하는 모집단 선택 전략을 구성하면서 공식화했다. 주목할 만한 이론적 결과로는 John C. Gittins가 처음 발표한 Gittins 지수가 있으며, 이는 기대 할인 보상을 최대화하기 위한 최적 정책을 제공한다.
공식 모델
다중 팔 밴딧은 실수 분포의 집합 \(B = \{R_1, \dots, R_K\}\)로 모델링할 수 있으며, 각 분포는 \(K\)개의 레버 중 하나가 제공하는 보상과 연관된다. 여기서 \(K \in \mathbb{N}^+\)이다. \(\mu_1, \dots, \mu_K\)를 이러한 보상 분포의 평균값이라고 하자. 도박꾼은 라운드마다 레버 하나를 반복적으로 플레이하고 관련 보상을 관찰하며, 남은 라운드 수인 지평선 \(H\)에 걸쳐 수집된 보상의 합을 최대화하는 것을 목표로 한다. 밴딧 문제는 공식적으로 단일 상태 마르코프 결정 과정과 동등하다.
회귀(regret)는 \(\rho\)로 표기하며, 최적 전략의 보상 합과 \(T\)라운드 후 수집된 보상 사이의 기대 차이를 측정한다. 이는 \(\rho = T\mu^ - \sum_{t=1}^T \hat{r}_t\)로 정의되며, 여기서 \(\mu^\)는 최대 보상 평균이고 \(\hat{r}_t\)는 \(t\)라운드에서 얻은 보상이다. 회귀를 최소화하는 것은 밴딧 알고리즘의 주요 목표이다.
탐험 vs. 활용
탐험-활용 트레이드오프는 다중 팔 밴딧 문제의 핵심 과제이다. 활용은 현재 지식에 기반하여 추정 보상이 가장 높은 팔을 선택하는 것이고, 탐험은 잠재적 보상에 대한 불확실성을 줄이기 위해 다른 팔을 시도하는 것이다. 효과적인 전략은 장기 누적 보상을 최대화하기 위해 이러한 상충되는 목표 사이에서 균형을 맞춰야 한다. 이 트레이드오프는 밴딧에만 고유한 것이 아니라 Machine learning 전반에 나타나며, 알려진 전략을 사용할지 새로운 전략을 발견할지 결정해야 하는 Reinforcement learning 및 Artificial intelligence 시스템에도 포함된다.
실제로 다중 팔 밴딧은 과학 재단이나 제약 회사와 같은 대규모 조직에서 연구 프로젝트를 관리하는 문제를 모델링하는 데 사용되어 왔다. 예를 들어, 연구 관리자는 알려진 잠재력을 가진 프로젝트를 활용하는 것과 새롭고 불확실한 아이디어를 탐험하는 것 사이에서 균형을 맞추며 어떤 프로젝트에 자금을 지원할지 결정해야 한다. 이 모델은 네트워크 지연을 최소화하기 위한 적응형 라우팅과 유사한 트레이드오프가 포함된 자산 선택이 이루어지는 금융 포트폴리오 설계에도 적용되었다.
알고리즘 및 전략
다중 팔 밴딧 문제를 해결하기 위해 여러 알고리즘이 개발되었다. 가장 초기의 것 중 하나는 엡실론-그리디(epsilon-greedy) 전략으로, 에이전트가 확률 \(\epsilon\)로 무작위 팔을 선택하고(탐험), 그 외에는 추정 보상이 가장 높은 팔을 선택한다(활용). 또 다른 인기 있는 접근 방식은 상한 신뢰 구간(UCB) 알고리즘으로, 평균 보상과 해당 추정치의 불확실성 모두에 기반하여 팔을 선택하여 원리적으로 탐험과 활용을 균형 있게 조정한다. 베이지안 방법인 톰슨 샘플링(Thompson sampling)은 각 팔의 보상에 대한 사후 분포를 유지하고 이러한 분포에서 샘플링하여 어떤 팔을 플레이할지 결정한다.
John C. Gittins가 도입한 Gittins 지수는 특정 밴딧 설정에서 기대 할인 보상을 최대화하기 위한 최적 정책을 제공한다. 이는 각 팔의 상태에 따라 지수를 할당하며, 최적 전략은 가장 높은 지수를 가진 팔을 플레이하는 것이다. 이 결과는 운영 연구와 경제학에 영향을 미쳐 왔다.
응용 및 경험적 증거
다중 팔 밴딧 프레임워크는 수많은 실제 응용 분야를 가지고 있다. 임상 시험에서는 환자를 다른 치료법에 할당하여 치료 효능에 대한 정보를 수집하면서 환자 손실을 최소화하는 데 사용할 수 있다. 적응형 라우팅에서는 네트워크 경로를 동적으로 선택하여 지연을 최소화하는 데 도움을 준다. 금융 포트폴리오 설계에서는 경쟁 투자 옵션 간 자원 할당을 안내한다.
2024년 카지노 도박 기록을 사용한 연구는 알 수 없는 확률을 가진 슬롯 머신 간의 플레이어 반복 선택을 대규모 다중 팔 밴딧 문제로 취급했다. 이 연구는 더 경험이 많은 플레이어가 더 나은 확률을 가진 기계를 선택하는 경향이 있고 시간이 지남에 따라 기계 선택에서 더 큰 일관성을 보였으며, 이는 학습과 더 잘 알려진 옵션의 더 큰 활용과 일치하는 패턴임을 발견했다. 이 경험적 증거는 밴딧 모델이 실제 의사 결정과 관련이 있음을 뒷받침한다.
이 모델은 또한 난이도와 보상에 대한 불확실성이 있을 때 어떤 프로젝트에 작업할지에 대한 질문에 답하면서 여러 프로젝트에 자원을 동적으로 할당하는 것을 제어하는 데 사용되어 왔다. 이 응용은 조직이 제한된 자원을 경쟁 이니셔티브에 어떻게 할당할지 결정해야 하는 연구 개발에서 특히 관련이 있다.
강화학습과의 관계
다중 팔 밴딧 문제는 탐험-활용 트레이드오프를 예시하는 고전적인 Reinforcement learning 문제이다. 그러나 선택된 행동이 팔의 보상 분포에 영향을 미치지 않기 때문에 일반 강화학습보다 더 단순하다. 대조적으로, 일반 강화학습에서는 행동이 환경의 상태를 변경하여 미래 보상에 영향을 줄 수 있다. 이러한 구별은 밴딧을 탐험-활용 딜레마를 연구하기 위한 다루기 쉬운 출발점으로 만들며, 밴딧을 위해 개발된 많은 알고리즘이 더 복잡한 강화학습 설정으로 확장되었다.
이 문제는 또한 다른 행동의 결과에 대한 불확실성 하에서 결정을 내려야 하는 확률적 스케줄링의 광범위한 범주에 속한다. 이러한 연결은 운영 연구에서 Artificial intelligence에 이르기까지 다양한 영역에 걸친 밴딧 모델의 광범위한 적용 가능성을 강조한다.
요약하면, 다중 팔 밴딧 문제는 불확실성 하에서 의사 결정을 위한 기본 모델로, 깊은 이론적 뿌리와 광범위한 실용적 관련성을 가지고 있다. 그 연구는 Machine learning 및 그 너머의 연구에 계속 정보를 제공하는 우아한 알고리즘과 통찰력을 생산해 왔다.