Stochastic Bandits (2) - ε-greedy

이전 포스팅에서 Stochastic Bandits에 대한 개요를 다루었습니다. 짧게 Reward에 확률 분포를 가정하는 MAB라고 요약 할 수 있습니다. 이번 포스팅에서는 Reward의 확률 분포를 Frequentist의 관점에서 point estimation하는 방법을 다루려고 합니다. 대표적인 알고리즘은 ε-greedy이고, 부제로 선정했습니다. :)

On The View of Frequentist

Frequentist, Bayesian의 구분은 확률을 해석하는 철학적인 차이입니다. Frequentist는 확률을 상대빈도의 관점으로 바라보며, 이는 많은 시도를 했을때 사건(Event)이 발생한 상대빈도로 확률을 정의합니다. 반면 Bayesian은 확률을 어떤 사건(Event)에 대한 믿음의 정도를 정의합니다.

이번 포스팅은 Frequentist의 관점에서 Reward를 해석하려고합니다. Frequentist 관점의 핵심은 Reward의 확률분포를 추정하기 위하여, 여러번 시도(Trial)하는 것과 Event를 정의하고 count하는 것 입니다. 가령 특정 user에게 어떤 웹페이지의 상단에 3개의 뉴스중 하나를 임의로 노출했을 때, 그 user는 뉴스를 클릭할 수도 있고, 안 할 수도 있을 것 입니다. 이때 Event는 어떤 뉴스를 클릭하는 것이고, 3개의 뉴스를 임의로 반복적으로 노출하는 것을 Trial로 대응할 수 있습니다.

위 상황을 MAB로 확장하면 뉴스 3개가 bandit이 선택할 수 있는 arms가 됩니다. 어떤 뉴스를 노출하는 것은 arm을 선택하는 것과 같고 만약 노출된 뉴스를 클릭한다면 보상 1을 받는다면 Frequentist는 아래와 같이 추정합니다.

Fig 1. Reward Estimation (Frequentist)

위 표에서 t는 각 round를 의미하고, 파란색 음영이 칠해진 것이 각 라운드에서 선택한 arm입니다. 1 라운드에서는 News 1을 노출했고, 클릭을 했기 때문에 (클릭)/(누적 노출 건수)로 각 news의 평균 reward를 예측할 수 있습니다. 반복하여 6라운드에 도달했을 땐, News 1의 평균 반응은 1이되고, News 2, 3은 각각 0.5, 0이 됩니다.

위와 같이 Frequentist는 여러번 반복하며 Reward의 확률 분포를 추정합니다. 여기에서 자연스럽게 Exploration-Exploitation Trade-off(Exp.-Exp. Trade off)가 발생합니다. 내용을 종합하면 Frequentist의 MAB Algorithm은 여러번 반복하여 각 arm이 주는 보상을 추정(Exploration)하여, 가장 보상이 클 것으로 예상되는 arm을 선택(Exploitation)할 때, 충분히 Exploration하여, 좋은 Exploitation이 되도록 알고리즘을 구축합니다.

Notations

• Arms: $a_{t}\in\{1, \cdots, K\}$
• Rounds: $t\in\{1,\cdots,T\}$
• Expected Rewards: $\mu\in\{\mu_{1},\cdots,\mu_{K}\}$, $\forall j, \mu_{j}\in[0, 1]$
• Rewards: $r_{t}(a_{t})\overset{iid}{\sim} Ber(\mu_{a_{t}})$

Stochastic Bandits에서는 위 Notations을 사용하겠습니다. Stochastic Bandits에서는 Reward의 확률 분포를 가정하며 가장 흔히 사용되는 Bernoulli Distribution을 가정했습니다. 좀 더 풀어쓰면 $t=1$에 $a_{t=1}=2$, 2번 arm을 선택하면, $r_{t=1, a_{t=1}=2}\sim Ber(\mu_{2})$에서 랜덤 샘플링된다고 모델링한 것입니다. 

Regret Function

Algorithm 구축시 알고리즘을 평가하기 위한 지표가 필요할 것입니다. MAB에서는 Regret Function을 이용하여 Algorithm을 평가합니다. Regret Function은 최적 선택 arm의 reward와, Algorithm 선택 arm의 reward의 차로, 그 값이 0에 가까울 수록 더 좋은 Algorithm임을 의미합니다. Stochastic Bandits에서 Regret Function은 아래와 같이 정의합니다. $$\bar{R}(T)=\underset{j\in{1,\cdots,K}}{\operatorname{max}}\sum_{t=1}^{T}r_{t}(j)-\sum_{t=1}^{T}r_{t}(a_{t})$$ 그런데 $r_{t}$는 확률변수이기 때문에 해석을 위해서 Expecction을 취해줍니다. 이를 Expected Regret이라고 합니다. $$\mathbb{E}\bar{R}(T)=\mathbb{E}\left[\underset{j\in\{1,\cdots,K\}}{\operatorname{max}}\sum_{t=1}^{T}r_{t}(j)-\sum_{t=1}^{T}r_{t}(a_{t})\right]$$ 이렇게 해두고나니 계산하기가 어렵습니다. Jensen's Inequality를 이용하여 max operator를 바깥으로 빼줍니다. $$\begin{align*}\mathbb{E}\bar{R}(T)\geq&\underset{j\in\{1,\cdots,K\}}{\operatorname{max}}\mathbb{E}\left[\sum_{t=1}^{T}r_{t}(j)-\sum_{t=1}^{T}r_{t}(a_{t})\right]\\&=\underset{j\in\{1,\cdots,K\}}{\operatorname{max}}\left[\sum_{t=1}^{T}\mu_{j}-\sum_{t=1}^{T}\mu_{a_{t}}\right]\\&=T\mu^{*}-\sum_{t=1}^{T}\mu_{a_{t}}\end{align*}$$ 여기에서 $\mu^{*}=\underset{j\in\{1,\cdots, K\}}{\operatorname{\max}}\mu_{j}$를 의미합니다. 위 수식의 마지막 줄을 Pseudo Regret으로 정의하고 이어질 regret analysis에 이용합니다. $$R(T)=T\mu^{*}-\sum_{t=1}^{T}\mu_{a_{t}}$$ 다시말하면 $T$ 라운드의 Regret은 최적 arm의 평균 보상과 알고리즘이 선택한 arm의 평균 보상의 차이를 의미합니다.

Explore-First Algorithm

가장 naive한 접근 방법은 Explore-First Algorithm입니다. 이름 그대로 먼저 explore를 한 다음에 이후엔 exploit만 하는 알고리즘입니다. 

Fig 2. Explore-First Algorithm for Stochastic Bandits

Regret Analysis

Explore-First Algorithm의 Regret을 살펴보겠습니다. $\bar{\mu}(a)$를 exploration phase가 종료된 후 arm $a$의 average reward라고 하고, $\mu(a)$를 arm $a$의 true average라고 하겠습니다. 만약 충분히 추정이 잘 되었다면 $|\bar{\mu}(a)-\mu(a)|$ 값이 작을 것 입니다. 즉 $\mu(a)$라는 중심으로부터 얼마나 떨어져있는가를 의미합니다.

중심으로부터 얼마나 떨어져있는지를 척도화한 부등식을 concentration inequality라고하는데, 그 중 Hoeffiding's Inequality는 다음과 같이 정의합니다. $X_{i}\in[0, 1]$이고 independent한 random variable이라면, $$\mathbb{P}\left(|\bar{X}-\mathbb{E}\bar{X}|\le t\right)\ge 1-2e^{-2nt^{2}}$$ Hoeffiding's Inequality를 적용하면 $$\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}}$이고 confidence radius라고 정의합니다. 모든 arm $a$에 대하여 위 부등식을 만족하는 event를 clean event $\mathcal{C}$로 정의하고, 그렇지 않은 event을 bad event $\mathcal{C}^{c}$로 정의하겠습니다.

$a^{*}$를 Exploitation phase에서 최적의 arm이라고 하면 Clean Event $\mathcal{C}$에 대하여 $-r(a)\le \bar{\mu}(a)-\mu \le r(a)$와 $-r(a^{*})\le\bar{\mu}(a^{*})-\mu(a^{*})\le r(a^{*})$가 성립합니다. 만약에 Exploitation Phase에서 Algorithm이 최적의 arm으로 $a$를 고른다고해보면, $\bar{\mu}(a)>\bar{\mu}(a^{*})$였다는 것을 의미합니다. 그러면 다음이 성립합니다. $$\mu(a^{*})-r(a^{*})\le\bar{\mu}(a^{*})\le\bar{\mu}(a)\le\mu(a)+r(a)\\\mu(a^{*})-\mu(a)\le r(a^{*})+r(a)=2r=2\sqrt{\frac{2\log{T}}{N}}$$ 첫 $NK$ round, 즉 exploration phase에서 발생할 수 있는 최대 regret은 1이기 때문에 $T$라운드 까지의 Regret은 $$\begin{align*}\mathbb{E}\left[R(T)|\mathcal{C}\right]&\le NK+(T-NK)2r\\&\le NK+T2r = NK+2T\sqrt{\frac{2\log{T}}{N}}\end{align*}$$ $N=(T/K)^{2/3}(2\log{T})^{1/3}$일때, $NK+2T\sqrt{\frac{2\log{T}}{N}}$가 최소가됨으로 $$\mathbb{E}\left[R(T)|\mathcal{C}\right]\le 3T^{2/3}(2K\log{T})^{1/3}=O\left(T^{2/3}(K\log{T})^{1/3}\right)$$을 얻을 수 있습니다. 다음으로 bad event $\mathcal{C}^{c}$의 경우 매라운드에서 얻을 수 있는 최대 regret은 1이기 때문에 $\mathbb{E}\left[R(T)|\mathcal{C}^{c}\right]\le T$가 됩니다. 또한 bad event가 발생할 확률은 $$\begin{align*}\mathbb{P}(\mathcal{C}^{c})&=\mathbb{P}\left(\exists a, s.t |\bar{\mu}(a)-\mu(a)|>r\right)\\&\le\sum_{a}\mathbb{P}\left(|\bar{\mu}(a)-\mu(a)|>r\right)\\&\le\frac{2K}{T}\le\frac{2}{T^{3}}\end{align*}$$와 같습니다. 정리하면 $$\begin{align*}\mathbb{E}R(T)&=\mathbb{E}R(T)|\mathcal{C}+\mathbb{E}R(T)|\mathcal{C}^{c}\\&\le O\left(T^{2/3}(K\log{T})^{1/3}\right)+T\frac{2}{T^{3}}=O\left(T^{2/3}(K\log{T})^{1/3}\right)\end{align*}$$으로 얻어집니다. Exploitation을 계속할 수록 Regret이 커지는 구조로 Regret이 엄청 나쁘다는 사실을 알 수 있습니다.

ε-Greedy Algorithm

눈치채셧겠지만 Explore-First Algorithm은 누가 보더라도 초반에 모든 arm에 대하여 $N$번씩 exploration을 하는 것은 광장히 비효율적이란것을 알 수 있습니다. 이를 보완한 방법이 ε-Greedy Algorithm입니다. ε-Greedy는 MAB뿐아니라 Reinforcement Learning에서도 굉장히 중요한 컨샙으로 사용됩니다. ε-Greedy의 ε은 exploration을 의미하며, ε의 비율만큼 exploration을 하고, 나머지는 exploitation하는 알고리즘입니다. Explore-First Algorithm과 비교하여 ε-Greedy는 Exploration을 random한 round에 진행한다는 차이가 있습니다.

Fig 3. ε-Greedy Algorithm for Stochastic Bandits

위 알고리즘을 살펴보면 $\epsilon_{t}$라고 되어있습니다. 즉 매라운드별로 값이 다르게하는 것도 가능하다는 것 입니다. 가장 기본적인 ε-greedy에서는 $\epsilon_{t}$를 상수로 고정하지만, 초반에는 값을 크게하고, 후반부로 갈수록 값을 점점 감소시키는 design도 가능합니다.

Regret Analysis

$\epsilon_{t}=t^{-1/3}(K\log{t})^{1/3}$으로 ε-greedy algorithm을 진행하면 regret upper bound는 $$\mathbb{E}R(t)\le O\left(t^{2/3}(K\log{t})^{1/3}\right)$$이 됩니다. (증명은 생략하겠습니다.)

Summary

이번 포스팅에서는 Stochastic Bandits의 가장 기본적인 Algorithm을 다루었습니다. 가장 기본적이란 의미는 앞으로 진행할 MAB Algorithm도 대부분은 결을 같이한다는 의미입니다. 또한 Explore-First Algorithm과 ε-greedy Algorithm모두 Frequentist 관점의 Point Estimation, 점추정입니다. 자연스럽게 다음 포스팅에서는 Frequentist 관점의 Interval Estimation, 구간추정을 살펴보겠습니다.

감사합니다:)

어떠한 형태의 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.