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

Upper-Confidence-Bound Action Selection

upper-confidence-bound action selection (이하 UCB)은 $Q_t(a)$값을 토대로 true action values의 upper bound를 어림하여, 이 값이 가장 큰 action을 선택하는 방식으로 진행합니다.

upper bound estimation은 Hoeffding’s Inequality와 Chernoff Bounds를 통하여 얻은 confidence interval로부터 유도되는 식을 통하여 구합니다.

$A_t \doteq \underset{a}{\operatorname{argmax}}\left[Q_t(a) + c\sqrt{{\ln t}\over{N_t(a)}}\right]$

여기서 $N_t(a)$는 action $a$가 선택된 횟수를 의미합니다.

위 식을 통하여 upper bound는 time step이 증가할 수록 천천히 증가하고, action이 선택될 때마다 급격하게 감소하는 경향을 볼 수 있습니다. 그러나 각각 로그함수, 분수함수이기에 이러한 경향은 $t$값과 $N$값이 커짐에 따라 둔화됩니다.

중요한 표현식은 $\sqrt{1\over{N_t(a)}}$부분 입니다. 자주 선택된 action은 이 부분 때문에 confidence bound가 작아지고, 대신 다른 action이 선택됩니다. 분수함수는 초반에 굉장히 빠르게 감소하기 때문에 이러한 작업이 반복됨에 따라 모든 action들에 대한 confidence bound는 급격하게, 고르게 작아지며 결국 $Q_t(a)$가 dominant해집니다. 그러나 $\sqrt{\log t}$부분이 있기에 time step이 증가함에 따라 천천히 confidence bound의 영향력이 커지게 되고 다시금 exploiting 대신에 exploring을 진행하게 됩니다.

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

UCB의 특이한 점은 $Q_t(a)$가 어느 정도 수렴한 뒤에도 exploring을 중단하지 않고 interval을 증가시켜가며 계속해서 exploring을 수행하여 update한다는 점입니다.

위에서 설명하였듯 $N_t(a)$값이 커져 confidence bound의 영향이 충분히 줄어들었다 해도, $\sqrt{\log t}$는 지속적으로 증가하여, 결국에는 다시 confidence bound의 영향이 커지게 됩니다. 로그함수의 형태기에 confidence bound의 영향력이 커지는 interval은 점점 길어집니다.

confidence bound term은 결국 exploiting 대신에 exploring을 진행하게끔 하는 term이라 할 수 있겠고, time step이 증가함에 따라 exploring을 실시하는 주기가 점점 길어지지만, 결코 중단하지는 않는다고 이해할 수 있습니다.

확률론적 접근으로 얻어진 UCB 방식은 수렴속도도 빠른 편이지만, 그 타당성에 있어서도 다른 방법들에 비하여 뛰어난 부분이 있습니다.

Mysterious Spikes

UCB의 경우에도 optimistic initial values방법과 동일한 spike가 나타납니다.

UCB의 초기단계 거동은 optimistic initial values와 같으며, 때문에 이 spike의 성인도 동일합니다. 때문에, 초기단계에 UCB가 어떤 논리적 과정을 거치는지만 파악한다면 이 spike가 왜 생기는지 정확하게 설명할 수 있습니다.

optimistic initial values에서 3개 actions, 고정값 반환으로 간소화하였던 문제를 UCB로 다시 진행하면 다음과 같은 과정을 거칩니다.

$c$값은 2로 하며(사실 이 값은 이 문제에 있어 optimal한 값은 아니나, UCB의 selection process를 더 잘 이해하기 위해 일부러 적절하지 못한 값으로 줍니다), 여기서는 optimistic initial values에서와는 다르게 $Q$의 밑을 time step $t$로 합니다.

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

• $\operatorname{UCB}_{a1} = \infty$, $\operatorname{UCB}_{a2} = \infty$, $\operatorname{UCB}_{a3} = \infty$
• 세 UCB가 모두 $\infty$이므로 랜덤하게 $a_1$ 선택, $R(a_1) = 1$ 리턴

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

• $\operatorname{UCB}_{a1} = 1 + 2\sqrt{{\ln 2}\over{1}}$, $\operatorname{UCB}_{a2} = \infty$, $\operatorname{UCB}_{a3} = \infty$
• $\operatorname{UCB}_{a1}$은 유한한 값을 가지나 $\operatorname{UCB}_{a2}$, $\operatorname{UCB}_{a3}$는 $\infty$이므로 둘 중 랜덤하게 $a_2$ 선택, $R(a_2) = 2$ 리턴

step 3: $Q_3(a_1) = 1$, $Q_3(a_2) = 2$, $Q_3(a_3) = 0$

• $\operatorname{UCB}_{a1} = 1 + 2\sqrt{{\ln 3}\over{1}}$, $\operatorname{UCB}_{a2} = 2 + 2\sqrt{{\ln 3}\over{1}}$, $\operatorname{UCB}_{a3} = \infty$
• $\operatorname{UCB}_{a1}$, $\operatorname{UCB}_{a2}$는 유한한 값을 가지나 $\operatorname{UCB}_{a3}$는 $\infty$이므로 $a_3$ 선택, $R(a_3) = 3$ 리턴

step 4: $Q_4(a_1) = 1$, $Q_4(a_2) = 2$, $Q_4(a_3) = 3$

• $\operatorname{UCB}_{a1} = 1 + 2\sqrt{{\ln 4}\over{1}}$, $\operatorname{UCB}_{a2} = 2 + 2\sqrt{{\ln 4}\over{1}}$, $\operatorname{UCB}_{a3} = 3 + 2\sqrt{{\ln 4}\over{1}}$
• $\operatorname{UCB}_{a3}$의 값이 가장 크므로 $a_3$ 선택, $R(a_3) = 3$ 리턴

step 5: $Q_5(a_1) = 1$, $Q_5(a_2) = 2$, $Q_5(a_3) = 3$

• $\operatorname{UCB}_{a1} = 1 + 2\sqrt{{\ln 5}\over{1}} = 3.54$, $\operatorname{UCB}_{a2} = 2 + 2\sqrt{{\ln 5}\over{1}} = 4.54$, $\operatorname{UCB}_{a3} = 3 + 2\sqrt{{\ln 5}\over{2}} = 4.79$
• $\operatorname{UCB}_{a3}$의 값이 가장 크므로 $a_3$ 선택, $R(a_3) = 3$ 리턴

step 6: $Q_6(a_1) = 1$, $Q_6(a_2) = 2$, $Q_6(a_3) = 3$

• $\operatorname{UCB}_{a1} = 1 + 2\sqrt{{\ln 6}\over{1}} = 3.68$, $\operatorname{UCB}_{a2} = 2 + 2\sqrt{{\ln 6}\over{1}} = 4.68$, $\operatorname{UCB}_{a3} = 3 + 2\sqrt{{\ln 6}\over{3}} = 4.55$
• $\operatorname{UCB}_{a2}$의 값이 가장 크므로 $a_2$ 선택, $R(a_2) = 2$ 리턴

step 7: $Q_7(a_1) = 1$, $Q_7(a_2) = 2$, $Q_7(a_3) = 3$

• $\operatorname{UCB}_{a1} = 1 + 2\sqrt{{\ln 7}\over{1}} = 3.79$, $\operatorname{UCB}_{a2} = 2 + 2\sqrt{{\ln 7}\over{2}} = 3.97$, $\operatorname{UCB}_{a3} = 3 + 2\sqrt{{\ln 7}\over{3}} = 4.61$
• $\operatorname{UCB}_{a3}$의 값이 가장 크므로 $a_3$ 선택, $R(a_3) = 3$ 리턴

step 8: $Q_7(a_1) = 1$, $Q_7(a_2) = 2$, $Q_7(a_3) = 3$

• …

위에서 나열한 과정은 $c$값을 optimal값보다 작게 잘못 설정한 케이스 입니다. $c = 3$으로 학습을 진행할 경우, step 5에서 $\operatorname{UCB}_{a2}$가 $\operatorname{UCB}_{a3}$보다 커지기 때문에 $a_2$를 선택하게 되며, 이런 방식으로 초기에 전체에 걸쳐 exploring을 진행하는 편이 성능이 더 좋습니다. 학습 후반부에서 optimal action이 아닌 값들에 대하여 어떤 방식으로 exploring interval을 길게 가져가는가의 살펴보기 위하여 일부러 작은 값으로 설정하여, confidence bound term의 영향력이 이미 작아진 상태로 학습을 시작하였습니다.

이 과정을 통하여 모든 actions에 대하여 exploring을 진행한 직후 이를 토대로 exploiting을 진행하기에 발생하는 spike를 설명할 수 있고, 동시에 confidence bound의 영향력이 작을 때 exploring 대신에 exploiting이 진행되는 과정과 더불어, exploiting을 많이 진행함에 따라 해당 action의 confidence bound가 작아져 exploring을 진행하는 과정까지 확인할 수 있습니다.