톰프슨 샘플링 (Thompson sampling)

한 줄 정의: 각 선택지의 사후분포에서 값을 뽑아 가장 높은 쪽을 고르는 베이즈식 탐색 전략입니다.

쉽게 풀면

선택지마다 “이 정도 성능일 것 같다”는 믿음을 확률분포로 들고 있습니다. 매 시행마다 각 분포에서 주사위를 굴리듯 값을 하나씩 뽑고, 그중 가장 큰 값이 나온 선택지를 고릅니다. 아직 잘 모르는 선택지는 분포가 넓어서 가끔 큰 값이 나오므로 자연스럽게 시험 기회를 얻고, 데이터가 쌓여 분포가 좁아지면 점차 진짜 좋은 쪽으로 수렴합니다.

왜 중요한가

탐색과 활용의 균형을 별도의 규칙 없이 확률적으로 자동 조절한다는 점에서 우아하고, 실제 성능도 매우 좋아 온라인 실험과 광고 노출 최적화의 사실상 표준이 되었습니다. 베이즈 추론과 의사결정을 자연스럽게 잇는 사례로 이론적 관심도 큽니다. 지연된 보상이나 배치 단위 갱신 같은 현실적 제약에도 비교적 잘 견딥니다.

논문에서는 이렇게 쓰입니다

"베타-이항 모형을 사용한 톰프슨 샘플링이 ε-탐욕 대비 동일 시행 수에서 누적 후회를 절반 수준으로 낮추었다."

확률분포에서 뽑아 고르는 방식이 무작위로 섞는 방식보다 손해가 훨씬 적었다는 비교 결과입니다.

조금 더 깊게 보면

1933년 톰프슨이 임상시험 맥락에서 제안했으나 오랫동안 잊혔다가 2010년대에 성능과 이론적 보장이 재조명되었습니다. 클릭 여부처럼 이항 보상에서는 베타 분포를 켤레 사전분포로 써서 성공·실패 횟수만 세면 사후분포가 갱신되므로 구현이 매우 간단합니다. 누적 후회가 로그 차수로 증가한다는 점이 증명되어 이론적으로도 상한 신뢰구간 알고리즘에 뒤지지 않습니다.

주의할 점

상한 신뢰구간 알고리즘이 불확실성을 결정론적 보너스 항으로 더하는 반면, 톰프슨 샘플링은 표본추출이라는 무작위성 자체로 탐색을 만들어 낸다는 점이 다릅니다. 사전분포를 잘못 설정하면 초기 수렴이 크게 왜곡될 수 있습니다.