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을 선택할 확률 $π_{t} (a)$ 를 Preference $H_{t} (a)$ 에 대한 softmax 함수의 형태로 정의합니다.

$P r {A_{t} = a} ≐ \frac{e^{H_{t} (a)}}{\sum_{b = 1}^{k} e^{H_{t} (b)}} ≐ π_{t} (a)$

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

$H_{t + 1} (a) ≐ H_{t} (a) + α (R_{t} - \overset{ˉ}{R_{t}}) (1_{A_{t} = a} - π_{t} (a)), \forall a$

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

$\overset{ˉ}{R_{t}} ≐ \frac{1}{t} \underset{i = 1}{\sum^{t}} R_{i}$

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

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

gradient_suttonlec

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

step 1: $H_{1} (a_{1}) = 0$ , $H_{1} (a_{2}) = 0$ , $H_{1} (a_{3}) = 0$

$π_{1} (a_{1}) = 1 / 3$ , $π_{1} (a_{2}) = 1 / 3$ , $π_{1} (a_{3}) = 1 / 3$

$a_{1}$ 선택, $R_{1} (a_{1}) = 1$ 리턴

$\overset{ˉ}{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$

$π_{2} (a_{1}) = 1 / 3$ , $π_{2} (a_{2}) = 1 / 3$ , $π_{2} (a_{3}) = 1 / 3$

$a_{2}$ 선택, $R_{2} (a_{2}) = 2$ 리턴

$\overset{ˉ}{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$

$π_{3} (a_{1}) = 0.304$ , $π_{3} (a_{2}) = 0.391$ , $π_{3} (a_{3}) = 0.304$

$a_{2}$ 선택, $R_{3} (a_{2}) = 2$ 리턴

$\overset{ˉ}{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$

$π_{4} (a_{1}) = 0.286$ , $π_{4} (a_{2}) = 0.427$ , $π_{4} (a_{3}) = 0.286$

$a_{3}$ 선택, $R_{4} (a_{3}) = 3$ 리턴

$\overset{ˉ}{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$

$π_{5} (a_{1}) = 0.248$ , $π_{5} (a_{2}) = 0.344$ , $π_{5} (a_{3}) = 0.408$

...

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

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

Algorithms Comparison

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

comparison-suttonlec