톰슨 샘플링

1. 개요[편집]

톰슨 샘플링 Thompson Sampling
제안	William R. Thompson (1933), Biometrika 25
다른 이름	확률 일치 · 사후표본추출(posterior sampling)
한 줄 요약	사후분포에서 한 번 뽑고, 그 표본을 진실이라 믿고 탐욕적으로 행동
표준 켤레쌍	베타-베르누이 — $\theta_k\sim\mathrm{Beta}(1+S_k,\,1+F_k)$
후회	점근 최적 $O(\log T)$ — Agrawal-Goyal, Kaufmann 외 (2012)
튜닝 파라미터	없음 (대신 사전분포를 골라야 함)
재발견	Chapelle & Li (2011) 실증 평가 — 78년 만의 부활

톰슨 샘플링(Thompson sampling)은 미지의 파라미터에 대한 사후분포에서 표본을 한 번 뽑고, 그 표본이 참값인 것처럼 취급해 최적 행동을 고르는 순차적 의사결정 알고리즘이다. 탐색과 활용의 균형을 명시적인 손잡이로 조절하는 대신, 불확실성 그 자체를 난수로 바꿔 행동에 주입한다는 것이 핵심 발상이다.

의사결정 규칙 전체가 두 줄이다.

$$\tilde\theta \sim p(\theta \mid \mathcal{H}_t), \qquad a_t = \arg\max_{a} \; \mathbb{E}\bigl[r \mid a, \tilde\theta\bigr]$$

$\mathcal{H}_t$ 는 지금까지의 관측 이력이다. 여기서 팔 $a$ 가 선택될 확률은 그 팔이 실제로 최적일 사후확률과 정확히 같아지는데, 이 성질을 확률 일치(probability matching)라 부른다. 사후확률을 직접 계산하는 것은 대개 불가능하지만, 표본을 뽑아 argmax를 취하기만 하면 저절로 그렇게 된다는 것이 이 알고리즘의 우아한 지점이다.

윌리엄 톰슨이 1933년 Biometrika 에 두 치료법의 임상 배정 문제로 발표했는데, 이후 60여 년간 사실상 잊혔다. 1990년대 이후 다중 슬롯머신 문헌에서 간간이 언급되다가, 샤펠과 리(2011)가 광고 노출 문제에서 UCB를 실제로 이긴다는 것을 실증하고 2012년에 이론적 후회 한계가 잇달아 증명되면서 완전히 부활했다. 논문이 78년 묵혀 있다가 표준이 된 사례로 자주 인용된다.¹

2. 왜 이것이 탐색인가[편집]

$\varepsilon$-탐욕은 확률 $\varepsilon$ 로 아무 팔이나 고른다. 명백히 나쁜 팔에도 똑같은 몫의 탐색을 낭비하고, $\varepsilon$ 을 언제 얼마나 줄일지는 사람이 정해야 한다. 톰슨 샘플링은 이 두 결함을 동시에 없앤다.

• 탐색량이 불확실성에 비례한다. 어떤 팔의 사후분포가 선두 팔의 사후분포와 겹치는 만큼만 그 팔이 뽑힌다. 데이터가 확실히 나쁘다고 말하는 팔은 사후분포가 아래쪽에 몰려 있어 거의 안 뽑힌다.
• 탐색이 자동으로 식는다. 관측이 쌓이면 사후분포가 좁아지고, 표본의 산포가 줄어 선택이 결정적으로 수렴한다. 냉각 스케줄을 손으로 짤 필요가 없다.

즉 탐색-활용 균형이 알고리즘의 하이퍼파라미터가 아니라 베이즈 추론의 부산물로 나온다. 공짜는 아니다. 대신 사전분포와 관측 모형을 명시해야 하고, 그 모형이 틀리면 조용히 대가를 치른다.

3. 베타-베르누이 — 다섯 줄짜리 구현[편집]

보상이 0/1인 표준 설정에서는 켤레사전분포가 모든 것을 해결한다. 팔 $k$ 의 성공확률 $\theta_k$ 에 $\mathrm{Beta}(\alpha_k,\beta_k)$ 사전분포를 두면, 성공 시 $\alpha_k \mathrel{+}= 1$, 실패 시 $\beta_k \mathrel{+}= 1$ 이 갱신의 전부다. 사후분포는 성공 $S_k$ 회·실패 $F_k$ 회 뒤

$$\theta_k \mid \mathcal{H} \;\sim\; \mathrm{Beta}(\alpha_k + S_k,\; \beta_k + F_k)$$

이고, 매 라운드 각 팔에서 $\tilde\theta_k$ 를 하나씩 뽑아 가장 큰 팔을 당기면 끝이다. 상태는 팔마다 정수 두 개, 연산은 베타 난수 $K$ 개. 분포를 명시적으로 들고 있는데도 메모리가 $O(K)$ 인 이 간결함이 온라인 시스템에서 채택된 실질적 이유다.

사전분포는 $\mathrm{Beta}(1,1)$(균등)이 기본값이고, 유효 사전표본크기가 0에 가까운 제프리스 사전분포 $\mathrm{Beta}(1/2,1/2)$ 도 흔히 쓴다. 팔이 많고 데이터가 적으면 사전분포의 무게가 초반 행동을 좌우하므로, 사전분포를 “무정보”라고 부르며 아무거나 꽂는 습관은 여기서 비용을 청구받는다.²

가우스 보상이면 정규-정규(또는 정규-역감마) 켤레쌍으로 같은 구조가 반복되고, 켤레가 없으면 라플라스 근사·변분 추론·마르코프 연쇄 몬테카를로·부트스트랩 앙상블 중 하나로 사후표본을 흉내 낸다. 이때 근사 사후분포가 실제보다 좁으면 탐색이 조기에 죽는다 — 딥 밴딧 실험에서 반복 보고되는 실패 양상이고, 그래서 근사의 과확신 여부를 점검하는 것이 구현의 핵심 작업이 된다.

4. UCB와의 대조[편집]

같은 문제의 다른 표준 해법이 신뢰상계(UCB)다. 둘의 차이는 불확실성을 결정론적 보너스로 바꾸느냐, 난수로 바꾸느냐로 요약된다.

항목	UCB	톰슨 샘플링
관점	빈도주의 신뢰구간	베이즈 사후분포
지수	평균 추정 + 신뢰폭 보너스	사후분포에서 뽑은 표본
행동	결정적 (같은 이력이면 같은 선택)	확률적
튜닝	신뢰폭 상수	사전분포
복잡 모형 확장	신뢰집합 유도가 필요	사후표본만 뽑히면 됨
배치·지연	같은 팔을 반복 선택	자동으로 분산됨

이론적 후회 차수는 둘 다 $O(\log T)$ 로 같고, 상수까지 점근 최적이라는 결과도 양쪽에 있다. 그럼에도 실측에서 톰슨 샘플링이 자주 앞서는데, 가장 자주 지목되는 이유는 UCB의 신뢰폭이 최악의 경우를 대비해 넉넉하게 잡히기 때문이다. 상한을 증명하려면 보너스를 크게 잡아야 하고, 크게 잡으면 실제 문제에서 과잉 탐색이 된다. 사후분포는 그런 여유분 없이 데이터가 말하는 만큼만 퍼져 있다.

반대로 UCB가 유리한 지점도 분명하다. 재현성이 필요한 규제 환경(결정적이라 감사 로그가 깔끔하다), 사전분포를 정당화하기 곤란한 상황, 그리고 보상이 적대적으로 정해지는 설정 — 후자에서는 베이즈 가정 자체가 성립하지 않으므로 헤지 알고리즘 계열의 EXP3로 가야 한다.

5. 후회 한계[편집]

후회는 $R_T = \sum_{t} (\mu^* - \mu_{a_t})$, 즉 매번 최적 팔을 당겼을 때와의 누적 격차다(정의와 온라인 학습 전반의 틀은 온라인 볼록 최적화 참고). 라이와 로빈스(1985)의 고전적 하한은 어떤 알고리즘도

$$\liminf_{T\to\infty}\frac{\mathbb{E}[R_T]}{\ln T}\;\ge\;\sum_{k:\Delta_k>0}\frac{\Delta_k}{\mathrm{KL}(\theta_k,\theta^*)}$$

를 밑돌 수 없다고 말한다($\Delta_k = \mu^*-\mu_k$). 톰슨 샘플링에 관한 결과는 이렇게 쌓였다.

• 아그라왈과 고얄(2012). 톰슨 샘플링의 빈도주의 후회에 대한 최초의 로그 한계 $O\bigl(\sum_k \ln T/\Delta_k\bigr)$. “베이즈 알고리즘인데 사전분포가 틀려도 잘 돈다”는 것을 처음 보인 결과라 의미가 크다.
• 카우프만·코르다·뮈노스(2012). 베르누이 밴딧에서 균등 사전분포를 쓴 톰슨 샘플링이 라이-로빈스 하한을 상수까지 달성함을 증명. 점근 최적성이 여기서 확정됐다.
• 아그라왈과 고얄(2013 이후). 문제 독립 한계 $O(\sqrt{KT\ln T})$. 하한 $\Omega(\sqrt{KT})$ 와 로그 인자만 차이 난다.
• 루소와 반 로이(2014, 2016). 사전분포를 진짜로 믿는 베이즈 후회 관점에서 $O(\sqrt{KT\log T})$ 를 정보이론적으로 유도했다. 핵심 도구인 정보비(information ratio) — 한 스텝의 기대 후회 제곱을 그 스텝이 얻는 정보량으로 나눈 값 — 는 이후 밴딧 분석의 표준 언어가 됐다.

즉 문제 종속·문제 독립·베이즈 세 종류의 후회에서 모두 (거의) 최적이라는, 알고리즘의 단순함을 생각하면 과분한 성적표를 갖고 있다.

6. 배치와 지연 피드백에서 강한 이유[편집]

실제 시스템에서 보상은 즉시 오지 않는다. 광고 클릭은 몇 초에서 몇 분, 구매 전환은 며칠, 임상 결과는 몇 달이 걸린다. 그 사이에도 결정은 계속 내려야 하므로, 낡은 사후분포로 여러 결정을 연속으로 내리는 상황이 기본값이다.

여기서 결정적 알고리즘과 확률적 알고리즘의 차이가 극명해진다. UCB는 이력이 그대로면 지수도 그대로라 같은 팔을 $B$ 번 반복 선택한다. 배치 크기만큼 탐색이 통째로 정지하는 셈이다. 반면 톰슨 샘플링은 매 결정마다 사후분포에서 새로 뽑으므로, 같은 사후분포에서도 자연스럽게 여러 팔로 분산된 배분이 나온다. 그 배분의 비율이 바로 “각 팔이 최적일 확률”이라, 배치 내부의 할당이 자동으로 합리적이다.

샤펠과 리(2011)가 지연을 인위적으로 늘려 가며 측정했을 때 톰슨 샘플링의 성능 저하가 UCB보다 훨씬 완만했던 것이 이 성질 때문이며, 실무 채택을 이끈 결정적 근거이기도 하다. 부수적 이득이 하나 더 있다 — 선택 확률(propensity)이 정의된다. 로그에 각 라운드의 선택 확률을 같이 남겨 두면, 나중에 다른 정책을 중요도 표본추출로 오프폴리시 평가할 수 있다. 결정적 정책에서는 이 확률이 0 아니면 1이라 반사실적 평가가 불가능하다. 고정 배분 A/B 테스트를 적응적 배분으로 바꾸면서도 사후 분석 가능성을 잃지 않는 방법이 사실상 이것뿐이다.

7. 문맥 밴딧, 베이지안 최적화, 강화학습으로[편집]

• 문맥 밴딧. 각 라운드에 특징 $x_t$ 가 주어지고 보상이 $\mathbb{E}[r\mid a,x] = x^\top\theta_a$ 인 선형 모형이면, $\theta_a$ 의 사후분포(가우스)에서 뽑아 argmax를 취하는 선형 톰슨 샘플링이 된다. 아그라왈과 고얄(2013)이 $\tilde{O}(d^{3/2}\sqrt{T})$ 후회를 보였다 — LinUCB의 $\tilde{O}(d\sqrt{T})$ 보다 차원 의존성이 나쁘지만 실측 성능은 대체로 앞선다는, 이 분야에서 반복되는 패턴.
• 베이지안 최적화. 가우스 과정 사후분포에서 함수 표본 경로를 하나 뽑아 그것을 최대화하면 그대로 획득함수가 된다. 기대개선(EI)·신뢰상한(UCB)과 나란히 놓이는 선택지이며, 배치 최적화에서 특히 빛난다 — 표본 경로를 $B$ 개 뽑으면 서로 다른 $B$ 개의 후보점이 공짜로 나오므로, 다른 획득함수들이 겪는 “배치 다양성 확보” 문제가 아예 발생하지 않는다. 무한차원 표본 경로는 랜덤 푸리에 특징 등으로 유한 근사한다.
• 강화 학습. 마르코프 결정 과정의 전이·보상 모형에 사후분포를 두고, 에피소드마다 MDP를 하나 통째로 뽑아 그것을 최적으로 푼 정책을 따르는 것이 사후표본추출 강화학습(PSRL, 오스밴드 외 2013)이다. 스텝마다 독립적으로 흔드는 $\varepsilon$-탐욕과 달리 에피소드 내내 일관된 가설을 밀어붙이므로 심층 탐색(deep exploration)이 가능해진다 — 보상이 여러 스텝 뒤에나 나오는 문제에서 이 차이가 결정적이다.

8. 언제 쓰면 안 되는가[편집]

• 순수 탐색(최적 팔 식별). 톰슨 샘플링의 목표는 누적 보상 최대화이므로, 열등한 팔이 확실해지면 즉시 버린다. 그런데 “예산을 다 쓰고 나서 최적 팔을 자신 있게 지목하라”는 문제에서는 2등 팔에도 자원을 계속 써야 신뢰도가 올라간다. 이 경우 톰슨 샘플링은 최적이 아니고, 상위 두 팔에 배분을 강제하는 top-two 변형이나 성공확률 기반 배분을 쓴다.
• 정보와 보상이 어긋난 문제. 루소-반 로이는 “지금 당장은 손해지만 가설 공간을 통째로 반쪽 낼 수 있는 행동”이 존재하는 문제에서 톰슨 샘플링이 임의로 나빠질 수 있음을 보였고, 정보비를 명시적으로 최적화하는 정보 지향 표본추출(IDS)을 대안으로 제시했다. 이진 탐색적 구조를 가진 문제가 대표적.
• 비정상 환경. 사후분포가 좁아지면 변화에 반응을 못 한다. 감쇠 계수로 옛 관측의 무게를 줄이거나($\alpha,\beta$ 에 $\gamma<1$ 을 곱해 가는 방식), 슬라이딩 윈도, 혹은 주기적 리셋이 필요하다. “자동으로 식는다”는 장점이 여기서는 그대로 단점이 된다.
• 모형 오설정. 보상 분포 가정이 틀리면 사후분포가 엉뚱한 곳에 확신을 갖는다. 관측 모형을 넉넉하게 잡거나, 사후분포를 일부러 부풀리는(온도를 올리는) 보정이 실무에서 쓰인다.
• 안전·공정성 제약이 있는 배정. 임상시험에서 적응적 배분은 통계적 효율은 좋지만, 분석의 복잡성과 환자 배정의 윤리 문제로 논쟁이 길다.³ 최소 배분 하한(팔마다 최소 $p$ 이상)을 두는 것이 흔한 타협이다.

9. 실무에서[편집]

• 구현이 정말 다섯 줄이라 오히려 의심을 받는다. “탐색 파라미터가 어디 있냐”는 질문을 반드시 받게 되고, “사전분포가 그 자리입니다”라고 답해야 한다.
• 로그에 선택 확률을 남겨라. 사후에 정책을 재평가할 수 있느냐가 여기서 갈린다. 톰슨 샘플링은 확률이 해석적으로 안 나오지만, 사후표본을 여러 개 뽑아 몬테카를로로 추정해 기록하면 된다.
• 배분 비율이 매일 흔들린다는 사실을 미리 공지하라. 톰슨 샘플링은 정의상 배분이 계속 움직인다.⁴
• 팔 추가·제거를 어떻게 할지 미리 정하라. 새 팔이 들어오면 사후분포가 넓어 한동안 과대 노출되는데, 이게 의도한 탐색인지 사고인지는 상황에 따라 다르다.
• 보상 스케일을 0~1 구간으로 정규화하라. 베타-베르누이가 아닌 보상을 억지로 이 틀에 넣을 때 흔히 쓰는 처방이며, 클리핑 지점을 기록해 두지 않으면 나중에 결과 해석이 불가능해진다.
• 정책 자체가 실험이라는 점을 잊지 마라. 톰슨 샘플링을 켜는 순간 트래픽 배분이 시간에 따라 변하므로, 단순 평균으로 그룹을 비교하면 편향이 생긴다. 적응적 배분 데이터의 추정은 별도의 통계 처리가 필요하다.

10. 관련 문서[편집]

• 다중 슬롯머신 · 문맥 밴딧 · 헤지 알고리즘 · 온라인 볼록 최적화
• 켤레사전분포 · 제프리스 사전분포 · 변분 추론 · 마르코프 연쇄 몬테카를로
• 베이지안 최적화 · 실험계획법 · 순차 검정
• 강화 학습 · 마르코프 결정 과정 · 몬테카를로 트리 탐색
• 중요도 표본추출 · 입자 필터 · 칼만 필터

11. Footnotes[편집]

1. 톰슨의 원 논문 제목이 “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples”다. 밴딧이라는 단어도, 후회라는 개념도 없고, 그냥 두 치료법 중 어느 쪽이 나은지를 환자를 배정해 가며 알아내는 문제다. 이 분야의 표준 알고리즘이 될 것을 저자는 당연히 몰랐고, 알았다면 제목을 좀 짧게 지었을 것이다. ↩

2. “왜 하필 표본을 한 개만 뽑는가”는 좋은 질문이다. 여러 개 뽑아 평균 내면 그건 그냥 사후평균 탐욕(greedy)이 되어 탐색이 사라진다. 확률 일치를 정확히 실현하는 표본 수가 1이라는 것이 요점이며, 이 알고리즘에서 난수는 편의가 아니라 본질이다. ↩

3. 임상시험 쪽에서 적응적 배분은 늘 뜨거운 감자다. “더 나은 치료를 더 많은 환자에게”라는 명분과 “고정 배분이라야 검정이 깨끗하다”는 통계적 요구가 정면충돌한다. 1933년 톰슨이 던진 문제가 90년 넘게 해결되지 않았다는 뜻이기도 하다. ↩

4. 실무에서 톰슨 샘플링을 켜고 나면 “왜 어제는 B안이 70%였는데 오늘은 40%냐”는 질문을 받는다. 답은 “데이터가 그렇게 말해서”인데, 이 답이 통하는 조직과 안 통하는 조직이 있다. 안 통하는 곳에서는 최소 배분 하한과 일일 변동 상한을 걸어 두는 것이 정치적으로 안전하다. ↩