Kwangmin Kim - Thompson Sampling — Beta-Bernoulli

출처

이 글은 교재 직접 참조 없이 agent 사전학습 기반으로 작성되었다 (교재 미확인 — agent 사전학습 기반). 핵심 정리는 Thompson (1933), Russo, Van Roy, Kazerouni, Osband, Wen (2018) 등 검증 가능한 원논문에 한해 명시한다.

이 글은 Phase I 시리즈의 네 번째 글이다. UCB 의 결정론적 신뢰구간 과 다른 접근 — 베이지안 사후 분포에서 샘플링 — 인 Thompson Sampling 을 다룬다.

1 진입 직관 — “내 사후 분포에 따라 행동”

UCB 가 불확실성의 상한 을 보고 결정한다면, Thompson Sampling 은 불확실성 자체에서 한 표본을 뽑아 그것이 진실인 것처럼 행동한다.

Thompson Sampling 의 한 줄 원리: 각 팔의 진짜 평균에 대한 사후 분포에서 표본 1 개 추출, 표본이 가장 큰 팔 선택.

1.1 메커니즘

각 시점 \(t\) 마다:

각 팔 \(a\) 의 진짜 평균 \(\mu_a\) 에 대한 베이지안 사후 분포 유지
각 팔의 사후에서 1 개 표본 \(\tilde{\mu}_a \sim P(\mu_a | \text{data})\) 추출
표본이 가장 큰 팔 \(A_t = \arg\max_a \tilde{\mu}_a\) 선택
Reward 관찰, 사후 업데이트

자연스러운 탐색: 충분히 시도된 팔의 사후는 진짜 평균 근처에 좁게 — 표본이 진짜 평균에 가까움. 덜 시도된 팔의 사후는 넓게 퍼짐 — 표본이 높을 수도, 낮을 수도. 가끔 높이 나오면 그 팔이 선택됨 — 자동 탐색.

비유 — 결정 회의: 임원 5 명이 각자 다른 후보안 에 대한 직관적 평가 를 가짐. UCB 는 가장 낙관적 임원의 의견 으로 결정. Thompson 은 임원 1 명을 무작위 추첨하여 그 임원의 평가 로 결정. 평균적으로 같은 결정에 수렴하지만, 과정의 다양성 이 다름.

2 역사 — Thompson 1933

놀라운 사실: Thompson Sampling 은 1933 년 William R. Thompson 이 의학 시험 맥락에서 제안. MAB 라는 용어가 생기기 20 년 전.

2.1 Thompson (1933) 의 동기

의학 시험에서 두 처치 (A vs B) 의 효과 비교. 베이지안 관점 에서 사후 확률 P(A 가 더 좋음) 계산. 다음 환자에게 그 확률대로 A 또는 B 선택.

환자 보호 의 윤리적 동기 — 효과 좋은 약을 더 많이 받게.

2.2 잊혀진 90 년

1933 년 이후 Thompson Sampling 은 거의 사용 안 됨. 의학에서는 고정 할당 RCT 가 표준. 1980 년대 MAB 이론 발달도 frequentist (UCB 등) 중심.

2.3 2010 년대의 부활

Chapelle & Li (2011), Russo & Van Roy (2014, 2016) 등이 Thompson Sampling 의 우수성을 실증. 광고 추천, 추천 시스템 등 실무에서 놀라운 성능. UCB 와 비슷하거나 더 좋은 regret, 더 단순한 구현.

Russo et al. (2018) 의 입장: “Thompson Sampling 이 가장 추천되는 baseline. UCB 보다 자주 더 좋고, 단순함.”

3 Beta-Bernoulli — Conjugate Prior

3.1 Bernoulli reward

가장 흔한 MAB 환경: 각 팔의 reward 가 Bernoulli (0 또는 1). 클릭률, 전환율, 임상 반응 등.

3.2 Beta 분포

정의: \(\text{Beta}(\alpha, \beta)\) 는 0~1 범위의 확률 변수 의 분포. 매개변수:

\(\alpha\): 성공 횟수 + 1 비유

\(\beta\): 실패 횟수 + 1 비유

평균: \(\alpha / (\alpha + \beta)\)

분산: \(\alpha\beta / ((\alpha+\beta)^2 (\alpha+\beta+1))\)

\(\text{Beta}(1, 1)\) 은 균등 분포 (uniform) — prior 정보 없음.

3.3 Conjugate 업데이트

결정적 성질: Bernoulli likelihood + Beta prior → Beta posterior. 닫힌 형태.

\[ \text{prior} = \text{Beta}(\alpha_0, \beta_0) \]

\(n_s\) 회 성공, \(n_f\) 회 실패 관찰 후:

\[ \text{posterior} = \text{Beta}(\alpha_0 + n_s, \beta_0 + n_f) \]

수식 직관: prior 의 \(\alpha, \beta\) 에 관찰된 성공/실패 횟수 더함. 매우 단순.

3.4 Thompson Sampling for Bernoulli

알고리즘: Thompson Sampling (Beta-Bernoulli)

초기화:
  for each arm a:
    α_a = 1, β_a = 1   # uniform prior

For t = 1 to N:
  # 사후 표본 추출
  for each a:
    θ_a ~ Beta(α_a, β_a)

  # 표본 최대 팔 선택
  A_t = argmax_a θ_a

  # Reward 관찰
  X_t ~ Bernoulli(μ_{A_t})

  # 업데이트
  if X_t == 1:
    α_{A_t} += 1
  else:
    β_{A_t} += 1

매개변수: prior \(\alpha_0, \beta_0\) (보통 1, 1) — 거의 hyperparameter 없음.

단순성: 약 10 줄 코드. UCB 보다 오히려 단순.

4 Gaussian Variant — 연속 Reward

Bernoulli 가 아닌 연속 reward (예: 매출, 시간) 에 대해 Gaussian 가정.

4.1 Gaussian Reward

각 팔의 reward \(X_a \sim \mathcal{N}(\mu_a, \sigma^2)\). \(\sigma^2\) 는 알려졌다고 가정 (또는 표본 분산으로 추정).

4.2 Conjugate

Gaussian likelihood + Gaussian prior → Gaussian posterior. 평균 \(\mu_a\) 의 사후:

\[ \mu_a | \text{data} \sim \mathcal{N}\left(\hat{\mu}_a, \frac{\sigma^2}{n_a}\right) \]

이는 Hoeffding/CLT 에서의 신뢰구간과 같은 형태.

4.3 알고리즘

For t = 1 to N:
  for each a:
    θ_a ~ Normal(μ̂_a, σ²/n_a)
  A_t = argmax_a θ_a
  Observe X_t, update sums_{A_t}, n_{A_t}

표본 분산 사용: \(\sigma^2\) 미지 시 표본 분산 \(\hat{\sigma}^2_a\) 사용. 또는 Normal-Inverse-Gamma conjugate prior 로 분산도 베이지안 처리.

5 UCB 와의 비교 — 결정론적 vs 확률적

측면	UCB1	Thompson Sampling
탐색 방식	결정론적 (신뢰구간 상한)	확률적 (사후 표본)
매 시점 행동	유일 결정	무작위
Hyperparameter	거의 없음	Prior \(\alpha_0, \beta_0\) (보통 1, 1)
Regret (이론)	\(O(\log N)\)	\(O(\log N)\)
실무 성능	안정	UCB 보다 약간 좋음 (실증)
코드 길이	~15 줄	~10 줄
Bayesian 해석	약함	자연스러움

5.1 Russo et al. (2018) 의 결과

“Thompson Sampling 이 광범위한 실증 환경에서 UCB 보다 같거나 더 좋은 regret. 광고 추천 사례에서 특히 우수.”

5.2 실무 매력

Bayesian 직관: 의사결정자에게 “이 팔이 최선일 사후 확률은 70%” 같은 해석 가능한 출력 제공. UCB 의 상한 점수 보다 직관적.

6 Probability of Being Best — 부수적 출력

Thompson Sampling 의 자연스러운 부산물:

각 팔이 최선일 사후 확률 \(P(\mu_a = \max_a' \mu_{a'} | \text{data})\) 를 몬테카를로 로 추정 가능.

6.1 알고리즘

m_iter = 10000
counts = [0] * K
for _ in range(m_iter):
  samples = [Beta(α_a, β_a).sample() for each a]
  best = argmax(samples)
  counts[best] += 1
prob_best = counts / m_iter

6.2 응용

A/B test 의 p-value 대신 비즈니스 친화 출력:

“처치 A 가 최선일 확률 87%”

“처치 B 가 최선일 확률 11%”

의사결정자가 직접 해석 가능. Bayesian A/B testing 의 핵심 도구.

Phase F 와의 연결: Bayesian A/B testing (Phase F-7) 에서 동일 도구 사용. Thompson Sampling 의 posterior 직관 은 더 광범위.

7 시뮬레이션 — Thompson vs UCB vs ε-Greedy

import numpy as np

np.random.seed(42)

K = 5
true_means = np.array([0.30, 0.50, 0.70, 0.40, 0.60])
mu_star = true_means.max()
N = 5000

def thompson_bernoulli(true_means, N):
    K = len(true_means)
    alpha = np.ones(K)   # uniform prior
    beta = np.ones(K)
    rewards = np.zeros(N)

    for t in range(N):
        # Sample from posterior
        theta = np.random.beta(alpha, beta)
        a = theta.argmax()
        r = np.random.binomial(1, true_means[a])
        rewards[t] = r
        if r == 1:
            alpha[a] += 1
        else:
            beta[a] += 1
    return rewards

def ucb1(true_means, N):
    K = len(true_means)
    pulls = np.zeros(K)
    sums = np.zeros(K)
    rewards = np.zeros(N)
    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        pulls[a] = 1
        sums[a] = r
        rewards[a] = r
    for t in range(K, N):
        means = sums / pulls
        ucb = means + np.sqrt(2 * np.log(t + 1) / pulls)
        a = ucb.argmax()
        r = np.random.binomial(1, true_means[a])
        pulls[a] += 1
        sums[a] += r
        rewards[t] = r
    return rewards

def epsilon_greedy(true_means, N, epsilon=0.1):
    K = len(true_means)
    pulls = np.zeros(K)
    sums = np.zeros(K)
    rewards = np.zeros(N)
    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        pulls[a] = 1
        sums[a] = r
        rewards[a] = r
    for t in range(K, N):
        if np.random.random() < epsilon:
            a = np.random.randint(K)
        else:
            means = sums / pulls
            a = means.argmax()
        r = np.random.binomial(1, true_means[a])
        pulls[a] += 1
        sums[a] += r
        rewards[t] = r
    return rewards

def cumulative_regret(rewards, mu_star):
    return np.arange(1, len(rewards) + 1) * mu_star - np.cumsum(rewards)

n_sim = 500
ts_regrets = np.zeros((n_sim, N))
ucb_regrets = np.zeros((n_sim, N))
eg_regrets = np.zeros((n_sim, N))

for s in range(n_sim):
    ts_regrets[s] = cumulative_regret(thompson_bernoulli(true_means, N), mu_star)
    ucb_regrets[s] = cumulative_regret(ucb1(true_means, N), mu_star)
    eg_regrets[s] = cumulative_regret(epsilon_greedy(true_means, N), mu_star)

print(f"[Thompson vs UCB1 vs ε-Greedy(0.1) — N={N}, 500 sims]\n")
for t_check in [100, 500, 1000, 2000, 5000]:
    if t_check <= N:
        print(f"  t={t_check:>4}: TS={ts_regrets[:, t_check-1].mean():>6.1f}, "
              f"UCB={ucb_regrets[:, t_check-1].mean():>6.1f}, "
              f"εG={eg_regrets[:, t_check-1].mean():>6.1f}")

# Probability of being best
print("\n[최종 시점에 각 팔이 최선일 사후 확률 — Thompson 의 부산물]")
np.random.seed(42)
alpha = np.ones(K)
beta = np.ones(K)
# 한 번의 Thompson sampling 시뮬레이션
for t in range(N):
    theta = np.random.beta(alpha, beta)
    a = theta.argmax()
    r = np.random.binomial(1, true_means[a])
    if r == 1:
        alpha[a] += 1
    else:
        beta[a] += 1

# 사후 확률 추정
m = 10000
counts = np.zeros(K)
for _ in range(m):
    s = np.random.beta(alpha, beta)
    counts[s.argmax()] += 1
prob_best = counts / m
print(f"각 팔의 사후 P(best): {dict(enumerate(prob_best))}")
print(f"진짜 최선의 팔: {true_means.argmax()} (mean = {mu_star})")

결과 해석:

Thompson 이 보통 UCB 보다 약간 작은 regret.

ε-greedy (fixed 0.1) 은 N 증가 시 선형 누적 — 다른 둘과 격차 커짐.

최종 사후 확률 이 진짜 최선의 팔에 거의 1. 의사결정자에게 직접 의미 있는 출력.

8 Bayesian 해석 — Phase F 와의 연결

8.1 Frequentist vs Bayesian

관점	Frequentist	Bayesian
모수 \(\mu_a\)	고정된 미지	분포를 가진 random variable
추론 도구	표본 평균, 신뢰구간	사후 분포, credible interval
MAB 알고리즘	UCB	Thompson Sampling

8.2 A/B Testing 에서

Phase F-7 (Bayesian A/B Testing) 에서 Thompson 과 같은 도구 사용:

사전 분포 → 데이터 → 사후 분포 → “B 가 A 보다 클 확률” 계산

Bayesian 추론의 광범위한 활용 의 일부.

반사실: Frequentist 에서 p-value 0.04 는 “귀무가설 하 데이터 확률 4%” — 직관적이지 않음. Bayesian 의 “B가 더 클 확률 96%” 는 직접 해석 가능. 의사결정자에게 매력.

9 실무 권고

9.1 Thompson 을 권장하는 경우

Bayesian 직관 이 익숙한 팀
probability of being best 같은 출력 가치
단순 코드 + 안정 성능
Russo et al. 2018 의 실증 — 광고 추천, 콘텐츠 personalization

9.2 UCB 를 권장하는 경우

결정론적 행동 필요 (재현성 등)
이론 분석이 우선 (KL-UCB, MAB 변형 깊이)
Hyperparameter (prior) 결정 부담 회피

9.3 실무 절충

기본: Thompson Sampling (Beta(1,1) prior). 변경 이유 가 명확하면 UCB 또는 변형.

10 결론

Thompson Sampling 은 1933 년 발명되어 90 년간 잊혀졌다가, 2010 년대에 MAB 의 표준 baseline 으로 부활. UCB 만큼 좋고 더 단순하며, Bayesian 해석을 자연스럽게 제공.

핵심 메시지:

사후 분포 샘플링: 단순한 베이지안 원리
Beta-Bernoulli conjugate: 닫힌 형태 업데이트
Gaussian variant: 연속 reward 처리
Probability of being best: 부수적 출력의 가치
UCB 와 비슷하거나 더 좋음: 실증 (Russo 2018)
Phase F-7 과 연결: Bayesian A/B testing 의 형제

다음 글: MAB vs A/B Test 의 종합 비교.

11 관련 주제

선행 지식

Phase I 후속 글

다른 카테고리 연결

(Phase F-7) Bayesian A/B Testing — 동일 사후 분포 도구
Statistics — Beta 분포, Conjugate priors

12 참고문헌

Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25, 285-294.
Chapelle, O. & Li, L. (2011). An empirical evaluation of Thompson sampling. NIPS.
Russo, D. & Van Roy, B. (2014). Learning to optimize via posterior sampling. Math. Oper. Res. 39, 1221-1243.
Russo, D., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z. (2018). A tutorial on Thompson sampling. Foundations and Trends in Machine Learning 11, 1-96.
Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (교재 미확인 — agent 사전학습 기반)