Ch2. Multi-armed Bandit (2) Action-value Methods

이 글은 Richard S. Sutton과 Andrew G. Barto의 Reinforcement Learning: An Introduction second edition을 기반으로 하고 있습니다. 개인적인 주관과 지식으로 인해 틀린 내용이 있을 수 있으므로 피드백이나 질문은 언제나 환영입니다.

Action-Value Methods

이전에 행동에 대한 가치(action-value)를 추정(estimate)하고, 가치가 높은 행동(greedy action)을 선택한다고 했다. 이렇게 행동을 결정하는 방법에 대해 action-value method라 부르겠다. 다시 이전 절에서 떠올려보면, 행동에 대한 '진짜' 가치는 행동을 할 때 얻을 것이라 기대되는, 평균 보상이였다. 그렇다면 이 가치를 구할 쉬운 방법 중 하나는 진짜 평균을 구해보는 것이다.

$$Q_t(a) \doteq \frac{t 이전까지 행동 a를 했을 때 얻은 보상}{t 이전에 행동 a를 한 횟수} = \frac{\sum^{t-1}{i=1}R_i \cdot \mathbb{1}{A_i=a}}{\sum^{t-1}{i=1} \mathbb{1}{A_i=a}}$$

$\mathbb{1}_{(조건)}$은 조건이 성립하면 1 아니면 0의 값을 갖는다. 즉, $A_i=a$이면 1 아니면 0인 것이다.

행동 $a$에 대한 진짜 가치를 $q(a)$, 그리고 우리가 추측한 가치를 $Q_t(a)$라 정의한다. 행동 가치를 추측하는 방법 중에 하나는 이 때까지 행동하면서 얻은 가치의 평균을 내는 것이다. 이를 sample-averge라 한다.

• 시간(time-step) $t$
• 행동(action) $a$
• 행동에 대한 가치(value of the action) $Q$
• 행동한 시점, 즉 처음부터 현재 $t$까지 이른 time step 수 $N_t$

처음엔 아무것도 안했을 테니 $N_t(a) = 0$일 것이다. 그런 경우는 기본 값(default)으로 $Q_1(a)=0$이라 한다. 반대로 $N_t(a) = \inf$일 경우. 무한히 해보았으니 거의 진짜 값($q_t$)에 수렴할 것이다.

Greedy action

이제 가치를 추측했으니 가치를 가지고 행동을 할 차례이다. 가장 간단한 방법은 그냥 가치가 가장 큰 값을 선택하는 것이다. 이를 저번에 greedy action이라 했다. t 시점에서 행동 $A^\ast_t$의 가치가 최고값이라면($Q_t(A^\ast_t)=max_a Q_t(a)$)

argmax는 가장 큰 값의 index를 말한다.
배열 [1, 10, 3, 2]이 있다 할 때 각 인덱스는 0, 1, 2, 3 이다.
결국 10이 가장 크므로 argmax의 값은 1이다.

$\epsilon$-greedy action

처음 추측해보고 그 다음부턴 무조건 큰 값을 고를 것이다. 그럼 다른 행동은 전혀 안하게 될 것이고 더 좋을 수도 있는 행동을 안한다는 말이다.(즉 exploration은 안하고 exploitation만 한다) 이 문제를 해결하기 위한 방법 중에 하나는 어떤 작은 일정한 확률($\epsilon$)로 아무런 행동(random action)을 하고 나머지 확률($1-\epsilon$)은 greedy action을 하는 것이다. 이를 \epsilon greedy 방법이라 한다. 그럼 적절히 exploration과 exploitation을 하게 된다. 따라서 무한히 할 수록 진짜 가치에 수렴할 수 있다. 진짜 가치에 수렴했음에도 임의의 확률로 다른 행동을 하겠지만 greedy보다는 효과적이다.

10-armed testbed

정말 그런가를 보기 위해 10-armed testbed 예를 든다.

• 슬롯 머신 2000번 돌려야 한다.
• n는 10개, 즉 10개의 슬롯 머신, 다시 말해 행동(action)이 10가지이다.
• 각 행동들은 평균 0, 분산 1을 가진 normal(Gaussian) 분포(distribution)로 reward를 받을 것이다. 다만 분포 위치만 다르다.

여기서 $q_\ast$는 책 예전 표기법으로 현재는 $q$라 표현한다.

greedy action, $\epsilon=0.01$ greedy action, $\epsilon=0.1$ greedy action일 때, 3가지를 1000 step에 걸쳐서 구한 결과는 다음과 같다. 하면서 action-value는 sample-average 방법을 사용했다.

결과

greedy

시작할 때 greedy가 가장 빠르게 향상되었지만, 가장 낮은 average reward = 1으로 끝난다.(3번 슬롯만 할 경우 최고 1.5를 얻을 수 있다. 즉, 이 말은 잘못 추측하면서 다른 슬롯을 골랐다는 얘기다.) 짧게 보면 괜찮은 결과가 나올지는 몰라도 장기적으로 봤을 때는 최고에 가깝지만 최고는 아닌 행동(suboptimal action)을 하고 그것을 벗어나지 못한다.(optimal action의 30%)

$\epsilon$-greedy

greedy보다 좋다. 왜냐하면 무조건 가치 높은 것만이 아닌 exploration을 조금 해줬기 때문. $\epsilon=0.01$보다는 $\epsilon=0.1$이 더 exploration을 더 많이 한다. 그래서 더 빨리 찾는다. 하지만 optimal action의 91% 이상을 이루지 못한다. $\epsilon=0.01$은 더 느리지만 덜 exploration하기 때문에 장기적으로 봤을 때 더 좋은 행동을 많이하여 최고의 결과를 얻을 가능성이 더 높다.

분석

무조건 $\epsilon$-greedy가 좋은 것인가? 꼭 그렇지는 않을 것이다. 상황과 무슨 일을 해야하는 지에 따라 다를 것이다.

• reward distribution 분산이 0이여서 무조건 그 값만 나온다면?(noise가 없다) => greedy가 좋음. 한 번씩 해보고 제일 높은 값만 하면 되니까
• reward distribution 분산이 10이라 더 높아서 예상했던 노이즈와는 다르게 다양하게 나온다면?(noise가 심하다) => $\epsilon$-greedy가 좋음. 다양한 시도로 exploration을 많이 해봐야 한다.

대부분의 상황에서는 $\epsilon$-greedy가 좋을 것이다. 예를 들면 2000step마다 새로운 slot machine으로 바뀐다면?? 분산도 다양하게 바뀔 것이다. greedy 방법은 영원히 안 바뀌겠지만, $\epsilon$-greedy는 exploration을 통해 새롭게 optimal action을 찾을 것이다.

reward 분포의 분산이 0일 때처럼, 확률없이 원하는 보상이 나오는 상황을 결정론적(Deterministic)이라 한다. 반대로 분산이 존재해서, 확률에 따라 다르게 나오는 상황을 확률적(Stochastic)이라 한다.

다음 시간에는

sample-average 방법을 통해 가치를 추측했다. 매번 가치를 추측할 때마다 이전에 받은 모든 보상을 가져오는 것은 좋은 판단은 아니다. 그렇기에 약간 변형된 방법을 다룰 예정이다.