Sutton RL - Ch1. Multi-armed Bandits (4)

Gradient Bandit Algorithms

앞의 방법들처럼 action value estimates를 이용하여 이를 토대로 action selection을 진행하는 방법 대신, 별도의 또다른 metric을 이용하는 방법들도 있습니다.

action $a$를 선호하는 Preference $H_t(a)$를 정의합니다. $H_t(a)$는 value로 표현한 함수가 아닌, 임의로 정의한 action에 대한 선호도 입니다.

action을 선택할 때, action별 $H_t(a)$을 비교하여 선호도가 높은 action위주로 시행하며, action을 선택할 확률 $\pi_t(a)$를 Preference $H_t(a)$에 대한 softmax 함수의 형태로 정의합니다.

$Pr\{A_t=a\} \doteq {{e^{H_t(a)}}\over{\sum^k_{b=1} e^{H_t(b)}}} \doteq \pi_t(a)$

초기 선호도가 모두 동일한 상태(e.g., $H_1(a) = 0, \text{ for all a}$)에서 action selection을 진행해 가며 gradient ascent를 이용하여 전체 성능을 극대화하는 $H_t(a)$를 찾을 수 있습니다. 전체 성능에 대한 measure로는 expected reward $\mathbb{E}[R_t] = \underset{x}{\sum}\pi_t(x)q_*(x)$를 이용하고, 이를 토대로 action preferences updating 알고리즘을 만들 수 있습니다.

$H_{t+1}(a) \doteq H_t(a) + \alpha (R_t - \bar{R_t})(\mathbf{1}_{A_t=a} - \pi_t(a)), \quad \forall{a}$

$\alpha > 0$은 step-size parameter(learning rate)이며, $\bar{R_t} \in \mathbb{R}$은 time $t$까지의(t를 포함한) reward 평균으로, baseline으로서 기능합니다. (지금까지의 성능과 비교하여 action 평가의 기준이 됩니다.)

$\bar{R_t} \doteq {1\over{t}}\underset{i=1}{\overset{t}{\sum}}R_i$

앞의 방법들과 혼동하지 말아야 할 부분은, $Q_t(a)$값이 action마다 할당된 값이었던 것과 비교하여, $\bar{R_t}$는 global한 값이라는 부분입니다. reward의 평균이라는 부분에서 동일한 metric으로 오해할 수 있는데, $Q_t(a)$는 “action $a$의 reward 총합을 a가 선택한 횟수로 나눈 값”이고, $\bar{R_t}$는 “모든 action들에 대한 전체 reward 총합을 time step으로 나눈 값” 입니다. 때문에, 당연히 incremental update를 진행할 때에도 $Q_t(a)$와는 달리 action이 시행된 횟수가 아닌 time step을 기준으로 진행하여야 합니다.

10-armed testbed에서 학습한 결과는 아래 그래프와 같습니다.

이전과 같이 간략화한 문제에 대입하여 과정을 살펴보면 다음과 같습니다. $\alpha = 0.5$로 계산합니다.

step 1: $H_1(a_1) = 0$, $H_1(a_2) = 0$, $H_1(a_3) = 0$

• $\pi_1(a_1) = 1/3$, $\pi_1(a_2) = 1/3$, $\pi_1(a_3) = 1/3$
• $a_1$ 선택, $R_1(a_1) = 1$ 리턴
• $\bar{R_1} = 1$
• $H_2(a_1) = 0 + 0.5(1 - 1)(1 - 1/3) = 0$
• $H_2(a_2) = 0 + 0.5(1 - 1)(0 - 1/3) = 0$
• $H_2(a_3) = 0 + 0.5(1 - 1)(0 - 1/3) = 0$

step 2: $H_2(a_1) = 0$, $H_2(a_2) = 0$, $H_2(a_3) = 0$

• $\pi_2(a_1) = 1/3$, $\pi_2(a_2) = 1/3$, $\pi_2(a_3) = 1/3$
• $a_2$ 선택, $R_2(a_2) = 2$ 리턴
• $\bar{R_2} = 1 + (2 - 1) / 2 = 1.5$ (incremental implementation)
• $H_3(a_1) = 0 + 0.5(2 - 1.5)(0 - 1/3) = -0.083$
• $H_3(a_2) = 0 + 0.5(2 - 1.5)(1 - 1/3) = 0.167$
• $H_3(a_3) = 0 + 0.5(2 - 1.5)(0 - 1/3) = -0.083$

step 3: $H_3(a_1) = -0.083$, $H_3(a_2) = 0.167$, $H_3(a_3) = -0.083$

• $\pi_3(a_1) = 0.304$, $\pi_3(a_2) = 0.391$, $\pi_3(a_3) = 0.304$
• $a_2$ 선택, $R_3(a_2) = 2$ 리턴
• $\bar{R_3} = 1.5 + (2 - 1.5) / 3 = 1.67$ (incremental implementation)
• $H_4(a_1) = -0.083 + 0.5(2 - 1.67)(0 - 0.304) = -0.133$
• $H_4(a_2) = 0.167 + 0.5(2 - 1.67)(1 - 0.391) = 0.267$
• $H_4(a_3) = -0.083 + 0.5(2 - 1.67)(0 - 0.304) = -0.133$

step 4: $H_4(a_1) = -0.133$, $H_4(a_2) = 0.267$, $H_4(a_3) = -0.133$

• $\pi_4(a_1) = 0.286$, $\pi_4(a_2) = 0.427$, $\pi_4(a_3) = 0.286$
• $a_3$ 선택, $R_4(a_3) = 3$ 리턴
• $\bar{R_4} = 1.67 + (3 - 1.67) / 4 = 2.00$ (incremental implementation)
• $H_4(a_1) = -0.133 + 0.5(3 - 2)(0 - 0.286) = -0.276$
• $H_4(a_2) = 0.267 + 0.5(3 - 2)(0 - 0.427) = 0.054$
• $H_4(a_3) = -0.133 + 0.5(3 - 2)(1 - 0.286) = 0.224$

step 5: $H_5(a_1) = -0.276$, $H_5(a_2) = 0.054$, $H_5(a_3) = 0.224$

• $\pi_5(a_1) = 0.248$, $\pi_5(a_2) = 0.344$, $\pi_5(a_3) = 0.408$
• …

다음에 선택될 action이 deterministric하지 않고 stochastic하다는 부분에 있어 타 방법들과 큰 차이가 있습니다. 위의 방법들은 평가의 기준이 되는 메트릭이 가장 높은 action만 결정적으로 선택하여도 학습의 진행에 큰 문제가 없지만, 이 방법으로는 그런 식으로 진행할 경우 학습이 진행되지 않기에 불안정하다고 느껴질 수도 있습니다.

baseline $\bar{R_t}$에 대한 보다 깊은 이해를 위해서는 알고리즘의 유도과정을 살펴봐야 합니다. 어려운 내용은 아니나, 다소 길기에 차후 살펴보도록 하겠습니다.

Algorithms Comparison

각 학습방법들에 대한 비교 그래프를 그려보면 아래와 같습니다.