Thompson Sampling 이란?

톰슨 샘플링이란, 도출된 베타 분포에서 RV(e-commerce에서는 일반적으로 전환율)를 샘플링하는 기법을 말합니다. 구조를 보면 이해가 더 잘 될수있다.

1.베타 분포 공간에 각 배너의 확률밀도함수(PMF)를 Draw
2.각 배너의 갯수만큼 random variate를 샘플링 -> 이값을 argMax()값을 비교하여 최대 값의 배너를 취함)
3.argMax로 선정된 배너 노출
4.이후 클릭O/클릭X가 바뀐 값으로 다시 1번부터 실행

Code

밀도함수를 3회 실행을 했을때 구해진 샘플값을 보자.

• 배너 1 샘플값이 제일 높음
• 배너2 샘플값이 제일 높음
  
• 배너3 샘플값이 제일 높음

즉 아직 PMF가 수렴하기 전에는 샘플링에 의해 다른 배너가 선택될 여지가 있는 것이다.
반면 여러 차례 수행에 의해 아래와 같이 PMF값이 어느정도 수렴에 가까워 질때는 샘플링 값을 여러 차례 구해 보아도 배너 그래프의 확률 분포가 우세한 배너 쪽으로만 계속 선택이 되는것을 발견했다.
자세히 보면 아래의 샘플링 값은 미세하게 다르지만 선택되는 배너는 같다.

위 알고리즘 수도코드를 보면 결국 베타분포 공간에서 각 배너의 S(클릭한 횟수)와 B(클릭안한 횟수)를 이용하여 학률밀도함수(PMF)를 Draw하고 여기서 값을 샘플링하여 이 값중 가장 큰 값의 배너를 선택한다.(argmax) 또한 이후 클릭율이 어떻게 바뀌었는지 다시 관측하고 클릭 성공(S)과 클릭 실패(F)를 기록하여 다시 톰슨샘플링을 반복한다.