Bayesian Bandits - Thompson Sampling

이번 포스팅은 Bayesian Bandits을 살펴보려고 합니다. 특히 Bayesian Bandits 중 대표적인 알고리즘인 Thompson Sampling을 부제로 선정했습니다. :)

On The View of Bayesian

Frequentist는 확률을 상대빈도의 관점으로 바라보지만, Bayesian은 확률을 어떤 사건에 대한 믿음의 정도로 해석합니다. 동전을 던져서 앞면이 나올 확률에 대해서 Frequentist는 "10000번 던지면 앞면이 5000번 나온다."고 해석하는 것이고, Bayesian은 "경험에 의하면 앞면이 나온다고 50% 믿는다."라고 해석합니다.

Prior vs. Posterior Probability?

위 예시에서 Bayesian의 멘트 중 "경험에 의하면"이라는 문구가 있습니다. 어떤 사건에 대한 사전 믿음의 정도를 수치화한 것을 사전 확률, prior probability라고 부르고, 샘플을 관측한 이후에 믿음의 정도를 다시 수치화한 것을 사후 확률, posterior probability라고 부릅니다. Posterior 계산하는 방법에 대한 이론을 Bayes` Theorem이라고 부릅니다. Bayes` Theorem은 $$\mathbb{P}\left(\theta|x\right)=\frac{\mathbb{P}\left(x|\theta\right)\mathbb{P}(\theta)}{\int\mathbb{P}\left(x|\theta\right)\mathbb{P}(\theta)d\theta}\propto\mathbb{P}\left(x|\theta\right)\mathbb{P}(\theta)$$입니다. 여기에서 $x$는 샘플을, $\mathbb{P}\left(\theta|x\right)$은 posterior를, $\mathbb{P}(\theta)$는 prior를, $\mathbb{P}\left(x|\theta\right)$는 likelihood를 의미합니다.

Beta-Bernoulli Model

Bayesian에서 중요한 것은 결국 Posterior를 어떻게 계산하는가 입니다. 여러 분포에 대해서 prior와 posterior를 정리할 수 있고, Prior와 Posterior의 분포가 같은 경우의 Prior를 conjugate prior라고 부릅니다. 예를 들어, Bernoulli Distribution의 parameter인 $\theta$의 Conjugate Prior는 Beta Distribution이 됩니다. 이러한 관계를 Beta-Bernoulli Model, Distribution 등 다양하게 부릅니다. 즉, $\theta\sim Beta(\alpha, \beta)$, $x\sim Ber(\theta)$일 때, $$\begin{align*}Posterior=\mathbb{P}(\theta|x)&\propto\mathbb{P}(x|\theta)\mathbb{P}(\theta)\\&\propto\theta^{x}(1-\theta)^{1-x}\theta^{\alpha-1}(1-\theta)^{\beta-1}\\&=\theta^{x+\alpha-1}(1-\theta)^{\beta-x}\\&=\theta^{x+\alpha-1}(1-\theta)^{\beta-x+1-1}\sim Beta(x+\alpha, \beta-x+1)\end{align*}$$가 됩니다.

이를 MAB 상황으로 확장해보겠습니다. 여러 arm을 선택했을 때 얻을 수 있는 reward가 binary형태일 경우 Beta-Bernoulli Model에 적용할 수 있습니다. 상호 독립적인 arm이 $K$개 있다고 가정하고, 각 arm의 reward의 대한 믿음의 정도(prior)를 $\theta_{k}\sim Beta(\alpha_{k},\beta_{k})$, $k\in\{1,\cdots,K\}$로 나타내고, arm, $k$을 선택하면, $x\sim Ber(\theta_{k})$로 얻어진다고 생각할 수 있습니다. 이와 비슷하게 Gaussian-Gaussian등 다양한 상황에 알맞도록 모델링을 할 수 있습니다.

Bayesian Bandit?

Bayesian Bandit은 reward가 얻어지는 확률에 대한 가정과 해석을 Bayesian의 관점으로 표현한 Bandit을 말합니다. Frequentist는 어떤 고정된 확률분포를 가정하는 반면, Bayesian은 Prior 기반으로 reward를 얻는 것으로 해석하여, 확률분포가 바뀌는 것이 차이점입니다.

Bayesian Regret

$\mathbb{P}$를 어떤 prior distribution이라고 하고, $\mathcal{I}$를 prior로 얻어진 bandit의 trial and error에 대한 instance라고 하면, Bayesian regret은 아래와 같이 정의됩니다. $$BR(T)=\mathbb{E}_{\mathcal{I}\sim\mathbb{P}}\left[\mathbb{E}[R(T)|\mathcal{I}]\right]=\mathbb{P}_{\mathcal{I}\sim\mathbb{P}}\left[\mu^{*}T-\sum_{t=1}^{T}\mu(a_{t})\right]$$ Beyesian Bandit은 Bayesian Regret을 최소화하는 것이 목표입니다. 일환으로 Thompson Sampling Algorithm이 널리 알려져 있습니다.

Thompson Sampling

Thompson Sampling은 Prior, Posterior의 관계를 이용하여 각 라운드별 최적의 arm을 선택하는 algorithm입니다.

Figure 1. Overview of Thompson Samping

Thompson Sampling은 다음의 과정을 거칩니다.

1. 주어진 Prior Distribution에 대하여 Sampling을 합니다.
   • 이때 sample의 수는 1개부터 n개까지 상관없고, 그 수 만큼 평균내어 이용합니다.
2. Prior Distribution의 Sample 중 결과가 가장 우수한 arm을 선택합니다.
3. 선택한 arm에 대하여, reward를 관측합니다.
4. 관측된 reward를 이용하여 Posterior를 계산합니다.
5. 계산된 Posterior를 다음 라운드의 Prior로 이용합니다.

위 process 중 1, 2, 5가 핵심입니다. 1은 각 arm의 prior로부터 sampling을 함으로써 exploration을 할 수 있습니다. 이어서 2를 진행하는 것은 exploitation이 됩니다. 위에 sample의 수는 상관이 없다고 했는데, 아무래도 sample의 수가 크면 평균에 아주 가까운 값이 나와서 exploration이 제대로 안될 수 있습니다. 그래서 Thompson Sampling은 1개의 sample을 이용하는 것이 통상적입니다. 마지막으로 5는 posterior를 계산한 뒤, 다음 라운드로 넘겨줍니다. 알고리즘을 반복하면, prior의 추정치가 점점 정확해지며, optimal한 arm을 선택할 확률을 높이게 됩니다. Reward가 binary형태의 경우 Thompson Sampling Algorithm은 다음과 같습니다.

Figure 2. Thompson Sampling

Summary

이번 포스팅에서는 Bayesian Bandits의 Thompson Sampling을 살펴봤습니다. Thompson Sampling은 각 arm의 prior probability를 가정하고, 매라운드 arm을 선택하기 위해 sampling을 하고,  samling결과가 가장 우수한 arm을 선택하여, Posterior를 계산하여 다음 라운드의 Prior로 이용하는 프레임 워크를 가지고 있습니다. 이 과정 속에서 Exploration, Exploitation이 자연스럽게 이루어지는 algorithm입니다. 

긴 글 읽어주셔서 감사합니다. :)

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.