Thompson Sampling: 탐색과 활용의 균형을 잡는 알고리즘

A/B 테스트, 추천 시스템, 광고 최적화처럼 실시간으로 결과를 보면서 “무엇이 더 좋을까?”를 판단해야 할 때 사용하는 방법이다.

그냥 무작위로 고르기엔 아깝고, 한 가지만 고집하기엔 불확실하다.

이럴 때 유용하게 쓰이는 방법이 바로 Thompson Sampling이다.

핵심 개념 한 줄 요약

확률적으로 잘 될 것 같은 선택지를 고른다.

Thompson Sampling은 베이지안 확률 모델을 이용해서, 여러 선택지 중에서 성공 확률이 높아 보이는 것을 무작위로 뽑아 실험하고, 결과를 반영해 점점 더 좋은 선택을 할 수 있도록 돕는 방식이다.

예시: 슬롯머신 게임 (Multi-Armed Bandit 문제)

당신 앞에 슬롯머신(뽑기 기계)이 3대 있다.

• A 슬롯머신: 성공률 10%
• B 슬롯머신: 성공률 30%
• C 슬롯머신: 성공률 50%

하지만 당신은 이 확률들을 모른다.
당첨/실패 결과를 보면서, 점점 더 나은 선택을 해야 한다.

Thompson Sampling 동작 방식

1. 각 선택지(arm)에 대해 성공률을 추정하는 분포를 초기화한다.

   • 초기에는 모두 Beta(1, 1)로 시작한다. (완전 랜덤한 상태)

2. 각 선택지에서 하나씩 확률 값을 샘플링한다.

   • 예: A=0.12, B=0.37, C=0.42

3. 가장 높은 값을 가진 선택지를 선택한다.

4. 결과에 따라 분포를 업데이트한다.

   • 성공 시: α (성공 횟수) += 1
   • 실패 시: β (실패 횟수) += 1

5. 이 과정을 반복하면서, 잘 되는 선택지는 더 자주 뽑히고, 확신 없는 선택지는 가끔씩 탐색한다.

Beta 분포란?

Beta(α, β)는 “이 선택지는 성공률이 이 정도일 것이다”라는 믿음을 나타낸다.

• α: 성공한 횟수 + 1
• β: 실패한 횟수 + 1

예를 들어, 어떤 버튼이 3번 성공하고 2번 실패했다면 → Beta(4, 3)
샘플링을 통해 “이 버튼의 실제 클릭률이 얼마일까?”를 계속 추정하는 거다.

탐색과 활용의 균형

Thompson Sampling의 가장 큰 특징은, 탐색(explore)과 활용(exploit) 사이의 균형을 자동으로 맞춰준다는 점이다.

• 아직 정보가 부족한 선택지는 분포의 분산이 커서 샘플링 값이 요동치기 때문에 탐색 대상이 된다.
• 정보가 충분히 쌓인 선택지는 분포가 날카로워져서 거의 확정적으로 선택된다.

따라서 별도의 파라미터 없이도 자연스럽게 효율적인 선택을 하게 됩니다.

Python 의사 코드 예시

alpha = [1, 1, 1]  # 각 선택지의 성공 횟수
beta = [1, 1, 1]   # 각 선택지의 실패 횟수

for t in range(1000):
    sampled_probs = [np.random.beta(a, b) for a, b in zip(alpha, beta)]
    chosen = np.argmax(sampled_probs)

    reward = pull(chosen)  # 실제 클릭 여부 (1 또는 0)

    if reward == 1:
        alpha[chosen] += 1
    else:
        beta[chosen] += 1

어디에 사용할 수 있을까?

장점 요약

• 탐색과 활용의 균형을 자동으로 조절
• 수학적으로 안정성과 성능이 검증됨
• 코드 구현이 간단함
• 실제 서비스에서 성능이 우수함

마무리

Thompson Sampling은 “성공 확률이 높아 보이는 선택을 확률적으로 뽑아 실험하고, 그 결과를 반영하여 더 나은 선택으로 진화해가는” 방법이다. A/B 테스트나 추천 시스템처럼 사용자 행동을 기반으로 최적의 선택을 찾아야 할 때 매우 유용한 전략이며, 구현도 간단하기 때문에 실무에 쉽게 적용할 수 있다.