Upper Confidence Bound (UCB) 정리, 보충 설명

Upper Confidence Bound (UCB)에 대한 상세한 내용을 이해하기 위해서는 실버 교수님의 강화학습 강의 1장 ~ 9장 까지 한번은 공부하시길 추천드립니다. UCB는 9장 Exploration and Exploitation에서 다루고 있는 내용입니다.

 

그림1. 불확실한 상황일때 우리는 무슨 arm (밴딧 머신)을 선택할 것인가?

그림 1.은 3개의 밴딧 머신 (Bandit Machine=슬롯 머신)이 있을때, 각 밴딧 머신의 손잡이 (arm)를 눌러 얻을 수 있는 reward (Q)의 분포를 나타냅니다 (a_1: 파란색 , a_2: 빨간색, a_3:초록색).

그림에 대해 간단하게 예를 들면 a_3는 매번 누를 때마다 30만원에서 50만원사이의 돈을 받을 수 있다고 보고, a_1의 경우 어떨때는 돈을 잃거나 또는 200만원을 받아 일확천금할 수 있다고 받을 수 있다고 생각하시면 됩니다.

직관적으로 a_3 의 신뢰구간 (Confidence Interval)이 매우 짧은 것을 볼 수 있으며, 불확실환 상황 속에서도 a_3를 선택하면 높은 reward (Q) 를 어느정도 보장 받을 수 있음을 볼 수 있습니다. 

 

그림 2. 파란색은 더 높은 reward (Q)를 받을 확률이 존재 합니다.

그러나 그림 2와 같이 a_1과 a_2을 선택하면 a_3의 우측에 더 높은 reward을 받을 수 있는 확률이 있다는 것을 할 수 있습니다.

만약 이와 같은 상황에서 Exploitation, 즉 현재 time step에서 좋아 보이는 (cumulative sum of future reward 가 높은) 머신을 선택하게 되고, 이와 같은 과정을 반복하면, 더 높은 포텐셜을 갖고 있는 a_1을 탐험해 보지 못하고, 결국 sub optimal에 도달 할 수 밖에 없습니다. 이와 같은 문제를 해결하기 위해 UCB를 사용해 exploration을 장려합니다.

 

 

그림 3. a_2의 확률 분포

그림 3.과 같이 이와 같은 확률 분포는 정 가운데를 평균 (mean)으로 볼 수 있으며, 신뢰 구간을 어떻게 설정 하느냐에 따라 Upper confidence bound (UCB) U(a) 를 설정할 수 있습니다.

 

신뢰구간이 X% 라고 가정 하면, 보너스 구간 포함에서 리워드 Q(a) + U(a) 를 예측 할 수 있습니다.

(예, 정확히 계산된 값이 아님) reward 평균 100만원, 신뢰구간 X%의 보너스 구간 (+50만원) = 150만원

 

즉, 그림2와 같이 a_1 (파란색)은 평균이 a_3 (초록색) 비해 작지만, 같으면서 넓은 신뢰구간 (예: 95%)를 사용했을 때의 UCB가 더 크므로, 불확실성에 기대 더 높은 리워드를 받을 수 있다고 생각해 a_1을 선택합니다.

 

위와 같은 방법론을 기반으로 여러 가능한 action (어떤 bandit machine을 선택) 중 하나를 선택 하고자 할 때에는 그 action이 UCB를 최대화 하는 것을 선택하도록 합니다.

 

이와 관련한 수식은 그림 4와 같습니다.

 

그림 4. UCB

그림 4에서 기술한 것 같이 Q값을 예측한 횟수 N(a) 가 증가할 수록 Q 값을 더 정확히 예측 할 수 있는데, 이와 같은 특성으로 예측 횟수가 증가할수록 신뢰 구간을 작아지게 하여 즉, U(a)가 작아지도록 해 exploration은 줄이고 더 안정적인 결과를 보여주는 action을 선택하도록 장려하여 (exploitation) 효과적으로 action을 선택하게 끔 하는 효과가 생깁니다.

 

* UCB를 구하는 방법 중 하나인 UCB1 포함 이후의 내용은 다시 강의 내용을 참고하시기 바랍니다.