강화학습 - (UCB)

---

Upper Confidence Bound

UCB는 random하게 선정하는 것의 불확실성을 해소하기 위해 이용되는 방법이다.

우연히 나쁜 표본이 선택되어 potential이 있는 slot machine을 배제하고 다른 slot machine을 선택하게 되는 일을 방지하기 위한 알고리즘이다. 자세히 알아보자면 아래와 같다.
UCB 알고리즘은 보상 값의 잠재적 가능성을 상한 신뢰 경계 U_t(a)로 측정하여, 실제 값 q_*(a)가 (Q_t(a) + U_t(a)) 이하일 확률이 높게 된다. 여기서 상한 경계 U_t(a)는 (N_t(a)), 즉 시간 t 이전에 액션 a가 선택된 횟수에 대한 함수이다. 액션 a가 더 자주 선택될수록 U_t(a) 는 더 작아진다.
UCB 알고리즘에서는 항상 상한 신뢰 경계를 최대화하는 가장 greedy한 액션을 선택한다.

상한 신뢰 경계는 Hoeffding’s Inequality(호프딩 부등식)을 이용하여 측정된다. iid(독립 동일 분포)를 따르는 랜덤 변수 ( X1, X2, ..., Xn이 모두 [0,1] 구간에 속한다고 가정하자. 이들의 표본 평균이 아래와 같을때

u>0에 대해 다음이 성립한다.

  이는 실제 평균이 표본 평균보다 u만큼 크게 될 확률이 e^(-2Nu^2)이하임을 의미한다.

이 부등식은 UCB에서 상한 신뢰 경계를 정하는 데 사용된다. 표본 평균 근처에서 실제 평균이 위치할 확률을 수학적으로 제한하고, 이를 통해 알고리즘이 얼마나 greedy한 선택을해야 하는지를 결정할 수 있다. N이 증가함에 따라 상한 신뢰 경계는 줄어들고, 이는 알고리즘이 더 확신 있는 액션을 선택하도록 유도한다.

위 그래프는 표본의 크기 n이 증가함에 따라 상한 신뢰 경계가 어떻게 감소하는지 보여주고 있다. n = 10, 30, 50일 때의 분포를 나타낸 그래프는, n이 커질수록 신뢰 구간이 좁아지는 것을 보여준다. 이것은 알고리즘이 더 많은 정보를 가질수록 보상에 대한 추정이 더 정확해진다는 것을 의미한다. 따라서 UCB 알고리즘은 시간이 지남에 따라 점점 더 정확한 추정을 기반으로 결정을 내릴 수 있게 된다. 

호프딩 부등식으로 부터 아래와 같은 식을 이끌어낼 수 있고, 작은 threshold가 되는 p와 U(t)는 아래와 같이 구해진다.

U는 다시 아래와 같이 표현되고 이를 통해 UCB 알고리즘의 핵심 수식을 이끌어 낼 수 있다. 그리고 이 알고리즘은 알파고가 사용한 컨셉과 굉장히 유사하다.

UCB 알고리즘 수식

 

그림을 통해 UCB의 전체적인 컨셉과 장점을 다시 살펴보자.

upper bound를 직접 살펴보며 말하자면 위와 같은 3가지 선택지가 있으면 당연히 upper bound도 높고 안정성도 높은 Q(2)를 선택하면된다.

그러나 이런식으로 Q(2)가 안정적인 좋은 결과를 낸다고 판단되는 경우 기존의 Multi-armed Bandit은 Q(2)를 지속적으로 선택할 확률이 높거나 무의미한 Q(3)까지 exploration할 가능성이 높다. 하지만 Q(1)의 upper bound가 제일 높아서 그 potential을 판단할 수 있는 UCB알고리즘을 통해 강화학습이 진행된다면 Q(1)에 대한 exploration만을 수행하여 적은 자원으로 최선의 결과를 이끌어낼 것이다.

---