MAB sutton book review

Multi-arm Bandits¹

(nonassociative, evaluative feedback) problem

1. nonassociative - 한번에 두 개 이상의 action(or arm)을 취하지 못한다.
2. evaluative - feedback 이 어떤action을 취하느냐에 의존적이다.

An n-Armed Bandit Problem

문제정의: $n$ 개의 action들 가운데 하나를 선택하는 상황이 반복된다. 한번 선택(action)을 취하면 그 선택한 action 의 stationary probability distribution에 따르는 보상(reward)를 받는다.

각 action 별로 reward 에 대한 확률 분포가 있다.

목표는 일정 time step 안의 action들에 대해 받는 보상의 총합을 최대화 하는 것이다.

Action Value의 개념: 어떤 action을 취했을때 (미래의) 보상값의 평균값

가능한 action에 대해 value값들를 모두 알고있는 경우, value값이 가장 높은 놈만 고르면 되니까 최적이다.

각 time step 별로 가능한 모든 action value를 예측하고, 그 중 action 을 선택하는 방식을 생각할 수 있다.

Action value를 예측한 상태로 Action 을 선택하는 데 두 가지 옵션이 있다.

1. exploiting - greedy action(action value 값이 가장 높게 예측된)를 선택
2. exploring - nongreedy action을 선택

exploring 을 하는 것은 nongreedy action들에 대한 value 예측 성능을 높힌다.

왜 모든 time step 에 대해 greedy choice를 하지 않을까? greedy action을 선택하는것이 어느 한 time step에서는 보상을 높히는데 좋을 지라도, 모든 time step에 대한 보상 값을 최대화 하지는 못한다. 기억해보면, 알고리즘에서 greedy choice 가 optimal 한 결과를 이끌어 낼때는 오직 optimal substructure property 와 greedy choice property 두 가지 특성들을 모두 만족하는 경우만 가능했다.

즉, exploration 와 exploitation 의 적절한 balance를 찾는 것이 중요하다. explore할지 exploit할지 결정하는 세련된 방법들이 있지만 strong assumption이나 prior knowledge가 요구되고 실제 application 에서는 그 가정에 위배되거나 prior knowledge를 얻을 수 없는 경우가 많다.

따라서 reinforcement learning 을 통해 해결하는 방법론들이 많이 등장 하고 있다.

exploration과 exploitation에 대한 balance 를 찾는 문제 중 쉬운 편에 속하는 n-arm bandit problem 에 대해 집중적으로 살펴보자.

Bandit 문제를 이해하기 위해 알아야하는 사전 지식들을 순서대로 공부할 것이다.

Action-Value Methods

time step $t$에서 action value의 실제 값 $q(a)$ 추정 값 $Q_t(a)$

$t$ 스텝 전까지 action $a$ 를 선택한 상황 수 $N_t(a)$, 그 action 에 대한 보상 $R_1, \cdots, R_{N_t(a)}$

추정값을 sample average 방식으로 정의하면 다음과 같다.

\[Q_t(a) = \begin{cases} 0 & N_t(a) = 0\\ 1 & N_t(a) \rightarrow \infty \\ \frac{R_1 + R_2 + \cdots + R_{N_t(a)}}{N_t(a)} & o.w \end{cases}\]

Epsilon Greedy

위의 정의로 얻은 추정 값으로 다음 action을 선택하는 방법 중 하나인 $\epsilon$-greedy 방법은 다음과 같다.

\[A_{t} \leftarrow \begin{cases}\underset{a}{\operatorname{argmax}}Q_{t}(a), & \text{ with probability }1-\epsilon \\ \text{a random action}, & \text{with probability }\epsilon\end{cases}\]

위의 계산 방식으로 문제를 푸는 경우, 한 time step별로 $R_1, \cdots, R_{N_t(a)}$ 을 담고 있을 메모리가 필요하다. 또한 이 값들이 평균을 계산하는 데 $O(N_t(a))$ 이므로, 시간이 경과됨에 따라 연산량이 증가하기 때문에 impractical 하다. 그래서 incremental하게 $Q_t(a)$ 를 찾을 수 있는 방법을 다음 섹션에서 다루겠다.

Incremental Implementation

$N_t(a) := k$ 라고 하면, 다음과 같이 정리할 수 있다.

\[\begin{align*} Q_{k + 1} &= \frac{1}{k}\sum_{i=1}^{k}R_i \\ &= \frac{1}{k}\left(R_k + \sum_{i=1}^{k-1}R_i\right) \\ &= \frac{1}{k}\left(R_k + (k-1)Q_k + Q_k - Q_k\right) \\ &= \frac{1}{k}\left(R_k + kQ_k - Q_k\right) \\ &= Q_k + \frac{1}{k}\left[R_k - Q_k\right] \end{align*}\]

$R_k$ 와 $Q_k$ 를 action 별로 keep 하고 있으므로서, $Q_{k + 1}$을 $O(1)$에 계산할 수 있다.

의미를 잘 되집어 보면, 어떤 action 에 관한 $Q_{t+1}(a)$, 즉 $Q_{k + 1}$ 는 시작 점부터 time step $t$ 까지의 reward 경험(experience)들을 토대로 다음 reward를 예측하는 관계라고 생각 하면 된다.

위의 업데이트 방식을 general 하게 표현하면 다음과 같다.

\(NewEstimate \leftarrow OldEstimate + StepSize[Target - OldEstimate].\) target은 $k$ th reward 이며, $[Target - OldEstimate]$ 는 error를 뜻한다. step 이 진행될 수록 error는 줄어든다.

여기서 주목해야할 점은 현재 스텝까지의 모든 reward를 동일한 weight로 하여 평균을 낸 값으로 action value $Q_k$ 를 예측 하도록 하는 sample average 방식을 사용할때 업데이트 식의 스텝 사이즈가 $1/k$ 이라는 것이다.

스텝사이즈가 스텝에 따라 변하는 $1/k$ 이므로 일반화 하면 $\alpha_k(a)$ 로 둘 수 있다.

Tracking a Nonstationary Problem

실생활에서는 가장 최근의 action에 대한 reward가 중요한 의미를 지닌다. (예를 들면 뉴스는 최신 뉴스가 제일 중요)

즉, 시간에 따라 현재 action에 대한 분포가 변하는 Nonstationary 분포에서 reward가 샘플링 되는 상황이면 sample average 방식은 합당하지 않다.

이런 상황을 이전 section에서 언급한 value 업데이트식에서 step size로 조절할 수 있다.

다음과 같이 식을 변형해보자.

\[\begin{align*} Q_{k + 1} &= Q_k + \alpha\left[R_k - Q_k\right] \\ &= \alpha R_k + (1 - \alpha)Q_k\\ &= \alpha R_k + (1 - \alpha)[\alpha R_{k-1} + (1 - \alpha)Q_{k-1}] \\ &= \alpha R_k + (1 - \alpha)\alpha R_{k-1} + (1 - \alpha)^2 Q_{k-1} \\ &= \alpha R_k + (1 - \alpha)\alpha R_{k-1} + (1 - \alpha)\alpha R_{k-2} + \dots + (1 - \alpha)^{k-1}\alpha R_1 + (1 - \alpha)^k Q_1\\ &= (1 - \alpha)^k Q_1 + \sum_{i=1}^{k}\alpha(1 - \alpha)^{k-i}R_i & \end{align*}\]

여기서 주목할 점은 $(1 - \alpha)^k + \sum_i^k \alpha (1 - \alpha)^{k - i} = 1$ 이므로, $Q_{k + 1}$ 은 $Q_1$ 과 ${R_i}_{\forall i}$ 의 weighted average 라는 것이다.

게다가 $1 - \alpha < 1$ 이므로 현재 time step 과 가까울 수록 보상 값의 가중치가 더 크다.

그런 이유로 이 방식은 적당한 상수인 $\alpha$를 선택하는 exponential, receny-weighted average 방식이라고 불리운다.

일반화된 $\alpha_k(a)$ 가 항상 업데이트식을 수렴하게 할까? 아니다. 제약조건이 따른다

statistical approximation theroy에 의하면 스텝 사이즈가 다음과 같은 제약조건을 따를 때만 수렴한다.

\[\begin{align} \sum_{k=1}^{\infty} \alpha_k(a) &= \infty & \text{and}&& \sum_{k=1}^{\infty} \alpha_k(a) < \infty \end{align}\]

대략적으로만 말하면 첫번째 조건은 충분히 커서 스텝사이즈가 초기 조건이나 진동하는 상황을 극복하도록 하고, 두번째 조건은 수렴할 수 있도록 충분히 작아야 한다는 조건이다. 즉, 너무 작아도 너무 커서도 안되는 적당한 값을 찾도록 하면 된다.

번외로 앞전에 말한 sample average 방법에 대한 수렴성을 증명하기가 쉽다.

$\sum_{k=1}^{\infty}1/k = \infty$ 증명 과 $\sum_{k=1}^{\infty}1/k^2 < \infty$ 증명 참조

실제 많은 경우에 $\alpha_k(a)$ 값은 수렴 조건이 만족해도 수렴속도가 너무 느리거나 튜닝하기 어려운 경우가 많으므로 어플리케이션에서 잘 쓰이지 않는다.

Optimistic Initial Values

이 방법은 주로 Nonstationary 문제에서 사용된다. (이유는 나중에)

핵심 사항은 초기 step에 exploration을 많이 하도록하여 다른 action들이 선택될 확률을 두루 높힌다.

모든 action에 대해 초기 $Q_1(a)$ 값을 높게 설정한다.

그렇게 하면 초반에는 exploration을 많이 하기 때문에 성능이 떨어질 지라도 long term 에서 보면 모든 action들이 거의 한번씩은 선택되므로 하나의 action으로 치중되는게 아닌 여러 경우의 수를 고려할 수 있게 된다.

nonstationary 방법에서는 잘 동작하지 않는데 그 이유는 스텝 초만에만 exploration이 많이 이뤄지는 것이기 때문이다. 좀 더 설명하면 상수 스텝을 쓰는 nonstationary 방법에서는 최근 reward가 중요한 역할을 하며 과거의 값들은 비중이 높지 않기 때문이다.

Upper-Confidence-Bound Action Selection

$\epsilon$-greedy 방법은 uncertainty 가 따르는 방법이다. 이러한 단점이 있는 방법을 사용하기보다는 action-value를 추정하는 것에 대한 신뢰도를 주기위해 이 방법(UCB)을 사용한다.

이 방법에서 추정한 action-value 를 기반으로 action을 다음과 같이 선택한다.

\[A_t = \underset{a}{argmax}\Big[ Q_t(a) + c \sqrt{\frac{ln{t}}{N_t(a)}} \Big]\]

여기서 $c\sqrt{\frac{lnt}{N_t(a)}}$ 가 클수록 action $a$ 가 선택되는 것을 돕는다.

그 의미를 보면, 선택이 적게된 action에 대한 exploration을 돕는 term임을 알 수 있다.

step 수 $t$ 가 증가함에 따라 $N_t(a)$ 가 상대적으로 낮은 action은 action-value에 좀 더 큰 값을 더해 주기 때문이다.

$c$ 는 이 term의 비중을 control 하는 파라미터이다.

이 term은 upper confidence bound라고 불리우는데 그 이유는 다음과 같이 action value예측에 대한 신뢰도의 upper bound역할을 하기 때문이다.

여기서 $U_t(a)$ 는 upper bound term이다.

\(Q^*(a) \le Q_t(a) + U_t(a)\) 어떻게 저런 upper bound term 이 유도가 되는 것일까?

prior knowledge로 Hoeffding’s inequality개념을 알아야한다. 이 블로그에도 설명 되어있다.

요약하면, 저 inequality에 의해 다음과 같은 관계를 갖고 그 관계에서부터 upper bound term을 유도할 수 있다.

\[\begin{align} P[Q^*(a) > Q(a) + U_t(a)] &\le exp(-2t(U_t(a))^2) & \text{since } Q(a) \in [0, 1] \end{align}\]

여기서 upper bound를 $p$ 라 하고, 전개하면 다음과 같이 되는데 휴리스틱으로 $p=t^{-2c^2}$로 두면 위의 식을 유도할 수 있다.

\[\begin{align} exp(-2t(U_t(a))^2) &\triangleq p \\ &\triangleq t^{-2c^2} \\ U_t(a) = c\sqrt{\frac{lnt}{N_t(a)}} \end{align}\]

---

Appendix

Thompson Sampling

MAB 문제를 푸는데 이용되는 대표적인 컴포넌트 중 하나인 Thompson sampling²에 대해 알아보자.

톰슨 샘플링을 다음과 같이 Bernoulli 분포를 따르는 bandit reward 문제에 적용할 것이다.

\[r \sim Bernoulli(\theta)\]

여기서 $i$ 번째 action 이 뽑힐 확률인 $\theta_i$ 를 Beta 확률 분포에서 샘플링하고 그 값에 의한 선택을 한다.

\(\theta_i \sim Beta(\alpha_i, \beta_i)\) pseudo code는 다음과 같다.

정리하면, 각 action 별로 beta 분포를 환경과의 상호작용을 통해 배워나간다고 생각하면 된다. 각 스텝마다 $K$ 개의 arm 의 파라미터 ${ \alpha_i, \beta_i }_{i=1, 2, \cdots, K}$를 (현재 beta분포를 통해 선택된 action, 보상 reward) 정보로 업데이트한다.

reward 가 1이면 $\alpha$ 업데이트 아니면 $\beta$ 업데이트.

왜 $ \alpha, \beta $ 의 업데이트는 위와 같이 이루어지는 것일까? 그 이유는 다음과 같다. Aerin Kim의 article 참조

\[\begin{align} r &\sim Bernoulli(\theta) \\ \theta &\sim Beta(\alpha, \beta) \end{align}\]

위의 가정 상황에서 posterior 인 $P(\theta \vert r)$ 에 대해 Bayesian rul을 적용하면 **prior 인 $P(\theta)$ 는 conjugate prior **임을 알 수 있다.

\[P(\theta \vert r) \propto P(r \vert \theta)P(\theta)\]

Conjugate prior in essence

For some likelihood functions, if you choose a certain prior, the posterior ends up being in the same distribution as the prior.
Such a prior then is called a Conjugate Prior.

따라서, (liklihood인 $P(r \vert \theta)$ 가 높아지는 $\theta$ 를 뽑도록) alpha, beta를 업데이트하므로서 posterior 를 높힐 수 있다.

wikipedia 에서 많은 conjugate 분포들의 테이블 정보를 확인 할 수 있다.

참고로 $i$ 번째 action에 대한 추정된 확률의 평균은 다음과 같이 데이터를 통해 배운 beta 분포의 평균지점이다.

\[\frac{\alpha_i}{\alpha_i + \beta_i}\]

한계를 말하기에 앞서, 우선 beta 분포의 분산은 다음과 같다.

\(\alpha \beta \over {(\alpha+\beta)^2(\alpha+\beta+1)}\) 평균이 같을 때 $\alpha + \beta$가 증가하면 분산이 작아지는 경향이 있다.

시간마다 action에 대한 분포가 변하는 Non-stationary 문제에서 예측 분포가 좁아지는 것에 대비하여 실제 분포의 변화로 평균지점이 달라져서 예측이 점점 어려워 지는 한계가 있다.

Reference

1. https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf “sutton 강화학습 책” ↩

2. An Empirical Evaluation of Thompson Sampling, NIPS 2011 ↩