Multi-armed Bandit 문제

Introduction

Multi-armed Bandit(MAB) 문제는 여러 개의 슬롯머신 중에서 보상을 최대화하는 문제입니다. 각 슬롯머신은 서로 다른 보상 분포를 가지고 있습니다.

밴딧(Bandit) 문제는 강화학습과 비교했을 때, 주요 차별점이 단일 행동에서 누릴 수 있는 최대 보상의 추구에 있다고 할 수 있습니다. 반면에 강화학습은 시간이 흐름에 따라 얻을 수 있는 총 보상의 최대화를 목표로 합니다. 이를 달성하기 위해, 각 시점에서 최적의 결정을 내리는 전략, 즉 정책을 학습하는 것입니다. 추가적으로, 밴딧 문제에서는 강화학습에서 중요한 상태(state)라는 개념이 생략되며, 한번 취해진 행동이 그다음 행동에 영향을 미치지 않는 독립적인 구조를 갖고 있습니다.

Exploration-Exploitation Strategies

제한된 기회 내에서 최대한의 보상을 얻는 것을 목표로 한다. 이를 달성하기 위해 탐색(exploration)과 활용(exploitation)을 적절히 사용한다. 직관적으로 아래와 같은 의미를 가진다. 탐색(Exploration)은 행동의 보상을 탐색하여 새로운 정보를 얻는 과정이며, 활용(Exploitation)은 탐색 과정에서 얻은 보상을 활용하여 현재의 상황을 개선하는 과정입니다.

Greedy

높은 보상을 주는 슬롯머신을 선택한다고 가정할 때, 가장 높은 보상을 주는 슬롯머신을 선택한다. 여기서 문제는 한번만 테스트하여 탐색이 충분히 이루어지지 않은 것이다.

epsilon-Greedy

ε-greedy 알고리즘은 각 스텝에서 ε 확률로 무작위 액션을 선택하고, 1-ε 확률로 현재까지의 경험으로 부터 가장 높은 보상을 제공하는 액션을 선택한다. ε-greedy 알고리즘의 선택 메커니즘은 아래 수식으로 나타낸다.

\[a_t = \begin{cases} \text{argmax}_a Q(a), & \text{with probability } 1 - \epsilon \\ \text{random action}, & \text{with probability } \epsilon \end{cases}\]

UCB (Upper Confidence Bound)

UCB 알고리즘은 불확실성과 최적화 사이의 균형을 찾는 데 중점을 둡니다. 이 선택 메커니즘을 나타내는 수식은 다음과 같습니다.

\[a_t = \text{argmax}_a \left[ Q(a) + c \sqrt{\frac{\log t}{n_a}} \right]\]

Thompson Sampling

Thompson Sampling은 베이지안 접근법을 사용하여 각 액션의 성공 확률에 대한 사후 분포를 갱신한다. Thompson Sampling의 선택 메커니즘은 아래 수식으로 나타낸다.

\[a_t = \text{argmax}_a \left[ \text{sample from } \beta(\alpha_a, \beta_a) \right]\]