[CS246] Bandits (4) - Thompson Sampling

Thompson Sampling: Probability-Based Bandit Algorithm

 

Thompson sampling은 각 행동이 최적인 확률에 비례하여 세션을 arm에 할당한다.

결과분포는 집합 \( \{ 0, 1 \} \) 으로 가정한다.

이는 각 행동은 성공($1$) 또는 실패($0$)를 의미한다.

그리고 확률 \( \theta \) 로 동전을 던지면 이 동전은(동전의 결과는) 베르누이 분포를 따른다.

그리고 \( \theta \)를 추정하기 위해 \( 0 \)과 \( 1 \)의 개수를 세어간다.

 

\( k \)개의 arm이 있고, 각 arm의 파라미터를 \( \theta_i \)라 하자.

즉 \( \boldsymbol{\theta} = ( \theta_1, \theta_2, \dots, \theta_k ) , \quad \theta_i = \cfrac{\text{# successes}}  {\text{(# successes + # failures) }} \)

 

성공-실패에 대한 확률분포는 보통 베타분포를 사용한다.

※ 이항분포(Binomial distribution)는 확률($p$)과 시행횟수($n$)가 고정되어있고 성공횟수($x$)를 모델링하는 확률분포이다. 

※ 베타분포(Beta distribution)는 성공과 실패횟수($\alpha,\ \beta$)를 통해 확률($p$)을 모델링하는 확률분포이다.

※ 베타분포와 베르누이분포 모두 지주속이고, 베타는 베르누이의 conjugate prior이다. 

https://trivia-starage.tistory.com/183

[Bayesian] Exponential Family & Conjugate Priors (지수족, 켤레사전분포)

 

https://en.wikipedia.org/wiki/Conjugate_prior

Conjugate prior - Wikipedia

 

Thompson sampling for the Bernoulli bandit

\( S_i = 0,\ F_i = 0,\ \forall i \)
for $t=1, \dots, T$ do
    for $i=1, \dots, K$ do
        Draw \( \theta_i \sim \text{Beta}(S_i + \alpha,\ F_i + \beta) \)
    end for
    Draw arm \( \hat{i} = \displaystyle\arg\max_{i} \theta_i \)
    Observe reward \( r \) ( \( r \in \{ 0, 1 \} \) )
    if \( r = 1 \) then
        \( S_i = S_i + 1 \)
    else
        \( F_i = F_i + 1 \)
    end if
end for

 

Thompson Sampling to Traffic

이제 Thompson sampling을 엄청난 양의 트래픽에 적용해보자.

(1) \( \text{Beta}(\alpha + S_a, \beta + F_b) \) 로부터 수많은 샘플을 뽑아낸다.

(2) arm $a$의 최적 확률은 $a$가 가장 큰 시뮬레이션 값을 가진 행의 비율이다.

(3) arm $a$의 트래픽을 $a$의 성공 비율(%)에 맞게 설정(세팅)한다.

 

Use Case: Two versions of the website

두개 버전의 인터넷 웹사이트를 A/B test를 한다고 해보자.

버전A의 참여율과 버전B의 참여율은 각각 5%, 4%라고 하자.

95%의 신뢰도로 버전A가 더 좋다고 주장하고 싶다고 하자.

그러면 각 arm마다 11,165개의 관찰값이 필요하다. 즉 22,330개의 관찰이 필요하다.

하루에 100개의 관측값을 수집한다고 가정하자.

(단순 t-test를 이용할 것이라면 총 223일이 필요하다)

첫날에 각 버전에 50개의 세션이 할당된다.

첫날에 운이 좋아서 A가 B보다 좋을 확률이 70%라고 하자.

그러면 둘째 날에는 전체 트래픽 중 A에 70%를, B에 30%를 할당한다.

둘째날이 끝날 때, 누적된 트래픽을 모으고 다시 각 웹사이트 버전이 최적일 확률을 업데이트한다.

Simulation of A/B Test

66일치에 실험은 끝난다. 단순 A/B test를 시행했으면 223일이 걸렸을 텐데 157일을 아낄수있다!!

 

Generalizatioin to Multiple Arms

 

Thompson sampling을 이용한 multi-armed bandit으로도 확장 가능하다.