A k-armed Bandit Problem
k-armed bandit problem은 아래와 같다.
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\mathbb{E}[R_t|A_t=a]\)
하지만 대부분의 풀어야하는 문제에서는 우리는 value of the action을 알지 못 한다. 따라서 우리는 estimation을 통해서 value of the action을 유추하고자 한다. 그리고 그 추정 값(estimated value)를 \(Q_t(a)\)로 denote한다. 결국 \(Q_t(a)\)가 최대한 \(q_*(a)\)와 같도록 하면 된다.
만약, \(Q_t(a)\)가 \(q_*(a)\)와 정확하게 같다면 우리는 Multi-armed Bandit 문제를 쉽게 풀 수 있다. \(Q_t(a)\)가 최대가 되는 action을 취하면 우리가 목표로하는 Expected total reward를 최대화 할 수 있다.
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 문제는 중요한 연구분야이다.