[CS246] Bandits (3) - UCB1 Algorithm

UCB: Upper confidence sampling algorithm

 

Confidence Intervals

confidence interval(신뢰구간)은 특정 확률로 평균이 있다는 확신할 수 있는 값의 범위이다.

단순 확률로 해석하기 어렵다. 필요하면 아래 신뢰구간(confidence interval)과 신용구간(credible interval)을 참고.

https://trivia-starage.tistory.com/175

[Bayesian Learning] Frequentism vs Bayesianism

덜 시도했다면 reward의 추정값의 정확도가 떨어지므로 confidence interval이 길어진다.

action을 더 시도할 수록 정보를 더 얻고, interval은 짦아진다.

 

우리가 (모종의 계산을 통해) confidence interval을 알고 있다고 가정하자.

그러면 우리는 confidence interval의 상한(upper bound)가 가장 높은 action을 고를 수 있다.

(단순히 평균이 높은것을 선택하지 않는다.)

 

이제 confidence bound를 계산하는 법을 알아보자.

arm $a$에 대하여 $m$개의 trial에 대해 얻은 payoff를 $X_{a, 1}, \dots, X_{a,m}$이라 하자.

이때 $X_{a, 1}, \dots, X_{a,m}$은 $\{0, 1\}$에서 iid하게 추출한 확률변수로 해석할 수 있다.

실제 mean 값은 $\mu_a = E[X_{a, \cdot}]$이지만 우리의 추정량은 $\widehat{\mu_{a,m}} = \frac{1}{m}\sum_{l=1}^{m}X_{a,l}$이다.

따라서 우리는 다음 확률 $\Pr(|\mu_a - \widehat{\mu_{a,m}}| \le b)$이 가장 큰 upper bound $b$를 찾아야 한다.

 

Hoeffding's Inequality

Hoeffding's inequality(호에프딩 부등식)는 기댓값이 일정량 이상 벗어날 확률에 대한 상한선을 제공한다.

자세한 내용은 wiki를 참고하면 되고, 여기서는 베르누이 시행에 대한 부등식만 다룬다.

$\widehat{\mu_m} = \frac{1}{m}\sum_{l=1}^{m}X_l$이라 할 때, 다음 부등식이 성립한다.

\[ \Pr(|\mu - \widehat{\mu_m}| \ge b) \le 2\exp (-2b^2m) = \delta \]

이때 $\delta$는 confidence level이다.

 

$b$를 찾기 위해 부등식을 풀면 해는 다음과 같다.

\[ b \ge \sqrt{\cfrac{\ln\left( \cfrac{2}{\delta} \right)}{2m}} \]

 

$b$는 upper bound이고, $m$은 action하기 까지의 횟수이다.

$b=b(a,T) = \sqrt(s\log(T) / m_a)$라 하자. 그러면 $\Pr(|\mu - \widehat{\mu_m}| \ge b) \le 2T^{-4}$이다.

따라서 매우 빠르게 $0$으로 수렴한다.

※ action을 수행하지 않는다면, upper bound $b$는 계속 상승한다.

 

UCB1 Algorithm

setup: $\widehat{\mu_1} = \cdots \widehat{\mu_k}=0$, $m_1 = \cdots = m_k=0$으로 초기화한다.

$\widehat{\mu_a}$는 arm $a$의 payoff의 추정량이고, $m_a$는 현재까지 arm $a$를 당긴 횟수이다.

 

for $t=1:T$ 동안 다음을 시행한다

• 각 arm $a$마다 $UCB(a) = \widehat{\mu_a} + \alpha \sqrt{\cfrac{2 \ln t}{m_a}}$를 계산한다.
• UCB가 가장 큰 arm을 선택한다. 이 arm을 $j$라 한다. 즉, $j = \underset{a}{\text{argmax}}UCB(a)$
• $j$를 당겨서 실제 값 $y_t$를 얻는다. ($y_j$가 아니다. $t$에서 얻은 $y$이다)
• $m_j$와 $\widehat{\mu_j}$를 업데이트한다.
  • $m_j \leftarrow m_j +1$
  • $\widehat{\mu_j} \leftarrow \cfrac{1}{m_j}\left( y_t + (m_j - 1)\widehat{\mu_j} \right)$