Multi-armed Bandit 문제

Introduction

Multi-armed Bandit(MAB) 문제는 각기 다른 보상을 가진 여러 개의 슬롯머신에서 보상을 maximize하는 문제이다.

Bandit 문제가 기존 강화학습(reinforcement learning)과 차이점이 있다면, 단일 행동에 대한 최대의 보상을 얻는 것이라 말할 수 있다. 강화학습은 시간에 따라 최대의 누적 보상을 얻는 것을 목표로 한다. 이 과정에서 누적 보상을 maximize하기 위한 정책(policy)을 학습하는 것이라 볼 수 있다. 또한, Bandit 문제는 강화학습과 달리 상태 개념이 없으며, 앞에서 발생한 action은 이후 일어날 action에 영향을 주지 않는다.

Exploration-Exploitation Strategies

제한된 기회 내에서 최대한의 보상을 얻는 것을 목표로 한다. 이를 달성하기 위해 탐색(exploration)과 활용(exploitation)을 적절히 사용한다. 직관적으로 아래와 같은 의미를 가진다.

• 탐색(Exploration): 어떤 선택(action)이 가지는 보상을 확인하기
• 활용(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 알고리즘은 불확실성과 최적화의 균형을 찾는다. 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]\]