MAB Problem

1. Multi-Armed Bandit Probelm

---

MAB는 아래와 같습니다.

Consider the following learning problem. You are faced repeatedly with a choice among k different options, or actions, After each choice you receive a numerical reward chosen from a stationary probability distribution that depends on the action you selected. Your objective is to maximize the expected total reward over some time period.

Expected total reward를 최대화하는 것이 bandit problem의 목표입니다. 어떤 Action에는 해당하는 Expected or Mean reward가 있습니다.(Expected value는 구하기 어렵기 때문에 Mean value로 흔히 근사한다). Expected or Mean reward를 우리는 Value of the action이라 부릅니다.

We denote the action selected on time step t as $A_{t}$, and the corresponding reward as $R_{t}$. The value then of an arbitrary actiona, denoted $q_{∗}(a)$, is the expected reward given that a is selected: $q_{*}(a)\doteq E[R_{t} \mid A_{t} = a]$

하지만 대부분의 풀어야하는 문제에서는 우리는 value of the action을 알지 못합니다. 따라서 우리는 estimation을 통해서 value of the action을 유추하고자 합니다. 그리고 그 추정 값(estimated value)를 $Q_{t}(a)$로 donate합니다. 결국 $Q_{t}(a)$가 최대한 $q_{*}(a)$와 같도록 하면 됩니다.

만약 $Q_{t}(a)$가 $q_{*}(a)$와 정확하게 같다면 우리는 Multi-armed Bandit 문제를 쉽게 풀 수 있습니다. $Q_{t}(a)$가 최대가 되는 action을 취하면 우리가 목표로하는 Expected total reward를 최대화 할 수있습니다.

2. Exploration and Exploitation

---

위에서 말한 $Q_{t}(a)$의 최대 값인 action을 greedy actions라 부릅니다. 그렇다면 greedy action만 선택하면 최선일까요? 그렇지 않은 경우가 대부분입니다. 왜냐하면 앞서 말한 것 처럼 우리는 value of the action인 $q_{*}(a)$를 모르기 때문에 estimated value of the action인 $Q_{t}(a)$를 통해 그저 유추할 뿐입니다.

$Q_{t}(a)$의 greedy action을 취하는 것을 exploitation이라고 하고, 이는 그 상태에서는 expected reward를 최대화하는 방법입니다. greedy action을 취하지 않고 randomly nongreedy action을 취하는 것을 exploration이라고 하고, 이는 장기적으로 봤을 때 더 큰 total reward를 획득 할 수 도 있게끔 합니다.

When you select one of these actions, we say that you are exploiting your current knowledge of the value of the actions. If instead you select one of the nongreedy actions, then we say you are exploring, because this enables you to improve your estimate of the nongreedy action’s value. Exploitation is the right thing to do to maximize the expected reward on the one step, but exploration may produce the greater total reward in the long run.

이렇게 생각해보면 매 순간 exploiting과 exploring을 함께 할 수 있는 action을 취하면 가장 좋겠지만, exploitation과 exploration은 conflict 관계이기 때문에 그렇게 할 수 없습니다.

Reinforcement learning에서 exploration과 exploitation의 balancing 문제는 중요한 연구분야입니다.