잘 설명해놓은 링크가 있어서 같이 정리한다! https://gdmarmerola.github.io/ts-for-bayesian-optim/ Thompson Sampling이 무엇인지 궁금해서 계속 살펴보았는데, Multi arm bandit 부터 공부해야해서 자세하게 정리해본다.
Multi-Arm Bandit 문제
이미지는 위 블로그 글에서 가져왔다! Multi-arm bandit 문제란 슬롯머신의 팔이 여러 개 있고, 각 팔에 대한 리워드가 모두 다를 때, 총 reward를 최대화 하기 위해서 각 팔을 얼마나 당겨야 하는지 결정하는 문제이다.
따라서 처음에는 각 팔의 리워드가 얼마인지 모르기 때문에, 팔을 각각 당겨보면서 리워드가 얼마인지 파악하고 (exploration) 좋은 팔을 최대한 계속 당기는 (exploitation) 두 과정의 발란싱이 중요한 문제가 된다.
Binary Bernoulli Bandit
보통 여기서 베르누이 Bandit을 가정하는데, 각 라운드에서 어떤 arm k를 당기면 우리는 binary reward를 받을 수 있게 된다. 이때, 이 reward가 베르누이 분포의 파라미터 $\theta_k$에 따라 $R_k \sim Bernoulli(\theta_k)$ 이런 형태로 나타나게 된다.
이제부터는 이 Multi-Arm Bandit 문제를 풀기 위해 보통 사용하는 알고리즘인 $\epsilon$-Greedy, Upper Confidence Bound (UCB) 이 두 알고리즘을 Thompson Sampling 이전에 먼저 살펴보도록 하겠다.
$\epsilon$-Greedy
$\epsilon$-Greedy 알고리즘은 간단하게, 현재 라운드에서 가장 reward가 큰 arm을 고르되, $\epsilon$의 확률로 랜덤한 다른 arm을 고르는 알고리즘이다. 그래서 현재 라운드에서 $\epsilon$의 확률로 가장 reward가 큰 arm을 고르는 과정을 수식으로 표현하면 다음과 같다.
\[R_t = \begin{cases} \arg\max_k \mathbb{E}(\theta_k), & \text{with probability } 1-\epsilon \\ \text{random } k, & \text{with probability } \epsilon \end{cases}\]이러한 $epsilon$-Greedy 알고리즘은 $\epsilon$의 확률로 랜덤 arm을 고르기 때문에, 단순 exploitation만 진행되지는 않고 exploration을 함께 진행한다.
Upper Confidence Bound
UCB는 $\theta_k$ arm에 있는 uncertainty를 이용한다. 많이 탐색된 arm은 uncertainty가 적고, 덜 탐색된 arm은 uncertainty가 크기 때문에 덜 탐색된 arm을 더 많이 선택할 수 있도록 항을 구성하여 exploration을 진행한다. 이때 $n$은 총 라운드의 수, $n_t$는 $t$까지 $k$번 선택된 횟수를 의미한다.
\[R_t = \bar{x_k} + \sqrt{\frac{2 \ln n}{n_t}}\]이거는 Regret Bounded라고 하는데, Regret 관련 정리는 이후에 한번 다시 진행해보도록 하겠다.
Thompson Sampling
이제 Thompson Sampling이다. Thompson Sampling은 간단하게 다음 세 가지 과정으로 이루어진다.
- 각 Bandit에서 prior k와 현재까지 observe된 data인 likelihood를 기반으로 posterior distribution을 계산한다.
- 각 bandit k의 posterior distribution에서 샘플을 하나씩 샘플링한다.
- 가장 좋은 샘플이 나온 k에 대해서 observation을 진행한다.
이후 prior k를 현재 bandit k posterior distribution으로 업데이트하고 이 과정을 반복한다. 이때 posterior distribution에서 샘플을 추출하기 때문에, 자연스럽게 exploration과 exploitation이 동시에 진행된다. 간단하면서도 강력한 알고리즘이다!
Thompson Sampling for Contextual Bandits
Contextual Bandit은 Bandit이 단순히 prior $k$만 있는 것이 아니고, context $x$를 같이 고려해야하는 문제이다. 즉, x에 따라서 각 bandit의 reward값이 변한다.
예시로, k번째 bandit의 reward가 다음과 같이 정의되어 있다고 생각해보자.
\(\theta_k(x)= \frac{1}{1+\exp(-(\beta_0+\beta_1 \cdot x + \epsilon)}\) 따라서 reward는 이제 parameter $\beta$와 함께 x를 함께 고려해야 한다.
이제 먼저 가장 간단한 경우인 선형함수를 가정하고 OLR을 이용해서 문제를 풀어보자. function이 arm이고 x가 context라고 보면되나?
그러면 Thompson Sampling은?
그러면 thompson sampling은 다음과 같이 진행할 수 있게 된다.
- OLR을 각 bandit에 대해서 진행
- 각 bandit k의 posterior distribution에서 하나의 $\beta$를 샘플링 한다.
- 샘플링된 $\beta$를 이용해서 주어진 x들에 대한 reward를 예측하고, 예측된 reward 중 가장 큰 값을 가지는 x를 선택하여 observe한다.
TODO: OLR 정리 (베이지안 로지스틱 회귀)
베이지안 최적화에서 Acquistion function으로
BO에서 next-point를 구하는 과정에서도 Thompson Sampling을 활용할 수 있다. GP posterior에서 샘플링하여 가장 best인 값을 사용하는 것과 동일하다. GP posterior에서 실제 특정 X값에서의 확률 (PI, EI)을 구하는 것과, 실제 샘플링을 진행하는 것의 차이라고 생각해보면 좋을 것 같다.
- GP에 현재 가지고 있는 observation을 피팅한다. ($p(D\vert f)$)
- GP posterior ($p(f\vert D)\propto p(D\vert f)p(f)$)에서 함수 하나를 샘플링한다. (이 과정이 결국 여러 x들에 대한 샘플링을 하는 과정이 되는 것 같다.)
- 가장 큰 값을 가지는 x를 선택하여 observe한다.
