Stochastic Bandits (3) - UCB (Upper Confidence Bound)

이번 포스팅은 Stochastic Bandits 그리고 Frequentists 관점의 연속입니다. 직전 포스팅에서는 reward의 확률 분포를 Point Estimation하는 관점에서 살펴보았고, 대응하는 알고리즘으로는 ε-greedy를 살펴보았습니다. 이번 포스팅에서는 Interval Estimation하는 관점의 algorithm인 Upper Confidence Bound Algorithm (UCB Algorithm)이 메인입니다.

Point Estimation vs. Interval Estimation

Frequentist의 확률 철학은 많은 시도를 반복했을때 사건이 발생한 상대빈도를 의미한다고 했습니다. 이러한 상대빈도를 추청하는 방식에는 크게 두가지 방식이 있는데, Point Estimation과 Interval Estimation이 되겠습니다. Point Estimation은 어떤 확률 분포를 결정짓는 parameter의 추정치, estimate를 줍니다. 반면 Interval Estimation은 확률 분포를 결정짓는 parameter가 속해 있을 구간의 추정치를 줍니다. 이때 구간을 신뢰 구간, Confidence Interval이라고 부릅니다. 예를 들어, $X_{i}\overset{i.i.d}{\operatorname{\sim}}N(\mu, \sigma^{2}), i\in\{1,\cdots,n\}$일 때, $$\begin{align*}&\mathbb{P}\left(|\bar{X}-\mu|<z_{0.025}\frac{\sigma}{\sqrt{n}}\right)&=0.95\\&\mathbb{P}\left(\bar{X}-z_{0.025}\frac{\sigma}{\sqrt{n}}<\mu<\bar{X}+z_{0.025}\frac{\sigma}{\sqrt{n}}\right)&=0.95\end{align*}$$로 나타낼 수 있는데, 이때 $\left[\bar{X}-z_{0.025}\frac{\sigma}{\sqrt{n}},\bar{X}+z_{0.025}\frac{\sigma}{\sqrt{n}}\right]$을 95% confidence interval이라고 부릅니다. Confidence Interval의 $\bar{X}$는 n개의 sample을 얻을 때 마다, 값이 달라지기 때문에 random variable입니다. Confidence Interval 앞의 95%의 의미는 위와 같은 방식으로 confidence interval을 100번 구축한다면 parameter의 참값인 $\mu$를 95번 정도 포함한다고 해석하면 됩니다.

Why Interval Estimation on Stochastic Bandits?

MAB에서 왜 Interval Estimation을 적용하려는 시도가 있었을까요? Point Estimation의 ε-greedy algorithm을 살펴보면, exploration schedule은 어떤 라운드 $t$까지 각 arm에 대한 추정의 질을 고려하지 않도록 설계 되어 있습니다. 다르게 말하면 과거에 관측된 reward를 전혀 고려하지 않고 random하게 exploration을 하기 때문에 비효율적입니다. Interval Esimation을 적용하면 관측된 reward에 기반한 exploration scheduling이 이루어집니다. (후에 다시 한 번 다루겠습니다.)

Hoeffiding's Inequality

MAB에서 신뢰구간을 정의하기 위해서 Hoeffiding's Inequality를 이용합니다. Hoeffiding's Inequality는 $X_{1}, \cdots, X_{n}$가 independent random variables이고, $\forall i, X_{i}\in[0,1]$일 때, $$\mathbb{P}\left(|\bar{X}-\mathbb{E}\bar{X}|\le t\right)\ge 1-2e^{-2nt^{2}}$$를 의미합니다.

Confidence Interval

이전 포스팅에서 은근슬쩍 넘어갔던 regret analysis 부분을 다시 살펴보면, $$\mathbb{P}\left(|\bar{\mu}(a)-\mu(a)|\le r(a)\right)\ge 1-\frac{2}{T^{4}},$$ 여기에서 $r(a)=\sqrt{\frac{2\log{T}}{N}}$입니다. 이때 $1-\frac{2}{T^{4}}$ confidence interval은 $\left[\bar{\mu}(a)-r(a),\bar{\mu}(a)+r(a)\right]$가 됩니다. Confidence Interval의 좌측 끝값과 우측 끝값을 각각 Lower Confidence Bound (LCB), Upper Confidence Bound (UCB)라고 부릅니다.

How to adaptively explore?

위에 잠시 언급했듯이 Interval estimate로 과거에 추정된 값을 고려하여 exploration을 한다면 ε-greedy alogrithm 중 exploration의 비효율성을 줄일 수 있습니다. Upper Bound를 보면 $r(a)$의 분모가 $N$이기 때문에 신뢰구간이 짧아지는 효과를 가져옵니다. 즉 자주 선택한 arm의 신뢰구간이 짧아집니다. 신뢰구간이 짧아진다는 의미는 짧은 구간을 여러번 만들면 상당수의 참값을 포함하는 신뢰구간 많이 있다는 의미로 추정의 질이 좋아짐을 의미합니다.

Figure 1. Confidence Interval

Figure 1은 a, b 2개 arms을 고려했을때, 어떤 arm의 UCB보다 큰 다른 arm의 LCB가 존재할때 해당 arm을 제거하고, 아닌 경우에는 계속해서 교차선택하는 알고리즘을 생각할 수 있습니다. 이렇게 하면 점점 confidence interval의 길이가 짧아지면서 최종적으로 좋은 arm이 남게됩니다. 즉 이전의 결과가 반영된 adaptive exploration이 됩니다.

Successive Elimination Algorithm

Interval Estimation을 적용한 가장 simple한 algorithm은 Successive Elimination Algorithm입니다. Successive Elimination Algorithm은 모든 arm이 active된 상태로 시작하여, active된 모든 arm을 당기고 UCB가 다른 arm의 LCB보다 작은 경우가 적어도 하나 존재하면 해당 arm을 elimination하는 algorithm입니다.

Figure 2. Successive Elimination Algorithm

Successive Elimination Algorithm의 Regret Upper Bound는 $\mathbb{E}R(t)=O\left(\sqrt{Kt\log{T}}\right)$로 알려져있습니다.

UCB Algorithm

Successive Elimination Alogrithm의 단점은 비등비등한 arms을 매번 선택하여 불필요한 exploration이 반복된다는 점입니다. Interval estimate을 이용하는 또 다른 방법은 당장 실수를 하더라도 반복한다면 좋아지겠지라는 낙관적인 생각 (optimism under the face of uncertainty)으로 UCB가 가장 큰 arm을 찾고, tie가 있다면 random하게 선택하는 방법을 취한다면 불필요한 exploration을 줄일 수 있을 것 입니다. 이를 Upper Confidence Bound Algorithm (UCB Algorithm)이라고 부릅니다.

Figure 3. UCB Algorithm

Figure 3에서 $UCB_{j}=\bar{\mu}_{n_{j}}(j)+r_{n_{j}}(j)$, $r_{n_{j}}(j)=\sqrt{\frac{2\log{T}}{n_{j}}}$를 일컫습니다.

Summary

Stochastic Bandit(1), (2), (3)을 거쳐 Frequentist 관점 + context-free한 상황의 Stochastic Bandits을 살펴보았습니다. 핵심이 되는 algorithm은 ε-greedy, UCB algorithm입니다. 다음 포스팅에서는 Bayesian 관점 + context-free의 Stochastic Banditd을 살펴보겠습니다.

감사합니다:)

어떠한 형태의 co-work도 환영합니다.

yjjo.tistory@gmail.com

References

Slivkins, Aleksandrs. "Introduction to multi-armed bandits."arXiv preprint arXiv:1904.07272(2019).

Wikipedia contributors. "Multi-armed bandit." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 22 Oct. 2020. Web. 30 Nov. 2020.

Li, Lihong, et al. "A contextual-bandit approach to personalized news article recommendation." Proceedings of the 19th international conference on World wide web. 2010.

Agrawal, Shipra, and Navin Goyal. "Thompson sampling for contextual bandits with linear payoffs." International Conference on Machine Learning. 2013.