Thompson Sampling, Multi-armed bandit, Contextual bandit

# Multi-armed bandit(=K-armed bandit)
여기서 armed는 action이고, K는 action의 개수를 의미함.

- Multi-armed bandit = One-state MDP
one-state MDP란 것은 state가 1가지로, 항상 고정된 상태를 의미함. 즉 state가 변하지 않기 때문에 이는 곧 state를 무시한다는 말과 동일함. 한마디로 state가 없는 MDP임

# Contextual bandit(=Associative Search)
Multi-armed bandit에서 한발 나아가, context를 given condition으로 받아서 문제를 확장한것임. 이때 context는 state와 다른데, 원래의 MDP에서는 Transition probability에 의해 (s, a -> s', r')가 되는 반면, contextual bandit에서는 (context, a -> r')으로 a가 다음 context에 영향을 주지 않음.

# Thompson Sampling
톰슨 샘플링은 기본적인 Exploration-Exploitation 문제를 다루는 Contextual bandit 알고리즘 중 하나로, contextual bandit이기 때문에 추천시스템에서 매우 잘 사용되는 알고리즘이다. (보통 추천 시스템은 사용자의 profile등을 context로 놓고 톰슨 샘플링을 사용함)

대략적인 그 개념을 이해하자면, Bayesian Approach를 Multi-armed bandit에 적용하여,여 Reward 분포를 MAP estimation으로 찾아서 action을 수행하는 알고리즘이다.

- Likelihood = P(r | a, context, Θ)
ex) Bernoulli distribution

- Prior = P(Θ)
ex) Beta distribution

- Posterior ∝ P(r | a, context, Θ)*P(Θ)

말로 설명하자면, 현재 내가 가지고 있는 P(r | a, context, Θ) 분포(처음엔 유니폼 랜덤)로 부터, reward의 기대값이 가장 큰 action a를 선택을 한다음, 그 action을 실행하여 새로운 데이터 D={r, a, context}를 구한다.
그다음 이 데이터 D를 이용해 likelihood를 최대화 하도록 학습하여 Θ를 찾고, 기존에 가지고 있던 P(r | a, context, Θ)를 prior로 놓고 sequential Bayesian learning을 하여 새로운 Posterior를 알아낸다.(이 부분은 추측임. 틀릴수도 있음. sequential bayesian을 안스고 그냥 매번 새로운 MAP을 할 수도 있음.)
위 과정을 계속 반복하여, 점점 더 정확한 Θ를 업데이트하고, 이로부터 더 정확해진 P(r | a, s, Θ)를 이용해 보다 좋은 action을 고르도록 위 과정을 반복한다.

기본 개념: https://en.wikipedia.org/wiki/Thompson_sampling

자세한 설명: http://sanghyukchun.github.io/96/
실제 구현 코드: https://github.com/wealthfront/thompson-sampling/blob/master/src/main/java/com/wealthfront/thompsonsampling/BatchedThompsonSampling.java

동영상 강의: https://www.youtube.com/watch?v=G7heaR0_9I0