Thomson sampling이란?

 최적화 문제가 어려운 이유는 탐색(Exploration)과 활용(Exploitation)간의 균형을 맞추는 것이다. 이를 위해 다양한 방법들이 있지만 Thomson Sampling이라는 방법이 있다.

One armed bandit라는 문제를 살펴보자.

 

외팔이 강도가 (one-armed bandit이) 우연한 기회로 눈 앞에 여러 개의 슬롯머신을 공짜로 H시간 동안 플레이 할 수 있는 기회를 얻었다고 생각해보자. 이때 강도는 한 번에 한 개의 슬롯머신의 arm만 당길 수 있으며 (즉 총 H번 시도할 수 있다) 각각의 슬롯머신에서 얻을 수 있는 reward는 다르다고 가정한다.

또한 reward는 어떤 probabilistic distribution에 의해 draw되는 random variable이라고 했을 때, 이때 강도가 가장 수익을 최대화하기 위해서는 arm을 어떤 순서대로, 어떤 policy대로 당겨야할까?

이 문제에서 가장 큰 난점은, 슬롯머신마다 보상이 다르고, 한 번에 한 슬롯머신의 reward만 관측할 수 있다는 점이다.

예를 들어 한 슬롯머신을 골라서 계속 그 슬롯머신만 당길 수도 있겠지만, 이 경우 다른 슬롯머신에서 더 좋은 reward를 얻었을 수도 있기 때문에 가장 최적의 전략은 아닐 것이다.

혹은 모든 슬롯머신을 동일한 횟수만큼 반복할 수도 있을 것이다. 그러나 슬롯머신 중에서 가장 좋은 reward를 보이는 머신은 오직 하나 뿐 일 것이므로, 이런 전략은 마찬가지로 최종 reward를 최적화하는 방법은 아닐 것이다.

혹은 일부 시간만 슬롯머신을 랜덤하게 당겨보고, 그 시간 동안 제일 좋았던 슬롯머신만 계속 당겨보는 수도 있을 것이다.

이와 같은 사례에서 Exploitation과 Exploration을 정의해보도록 하자.

이때 기존 경험 혹은 관측값을 토대로 가장 좋은 arm을 선택하는 것을 exploitation이라 하며 더 많은 정보를 위하여 새로운 arm을 선택하는 것을 exploration이라고 한다.

결국 시간이 제한되어있기 때문에 이 둘 사이에는 trade-off관계가 성립하게 된다. 만약 exploration를 너무 하지 않게 될 경우, 잘못된 정보를 토대로 exploitation을 하게 되기 때문에 최종 결과가 좋을 거라는 보장을 하기가 힘들 것이다. 그렇다고 해서 너무 exploration을 많이 하게 되면, 충분히 정보를 가지고 있음에도 불구하고 더 정보를 얻기 위해 쓸데 없는 비용이 발생할 것이다. 따라서 이런 측면에서 exploration과 exploitation은 서로 trade-off 관계가 있다고 할 수 있고, 이런 상황에서 우리가 이 둘을 어떻게 조절하느냐가 Multi-armed Bandit problem의 핵심이 되는 것이다.

Thompson sampling이란 그럼 무엇인가?
Thompson sampling이란?
one of oldest heuristic to address the exploration / exploitation trade-off.

Thompson sampling의 기본 생각은 부분적인 정보를 가지는 입력/행위들에 대해서 실제 모수에 근사한 값을 계산해서 최적해를 찾는 것이다.
이를 위해서 우도 함수(likelihood function, 알고리즘에서 P(θ|D))이 사용된다. 알고리즘은 다음과 같다.

T는 전체 round 횟수.
a는 전체 행위 집합에 속하는 한 액션. a ∈ А.
r은 보상(reward), 즉 결과 값.
D는 과거 관찰 결과, (x, a, r).
x는 행위 당시의 상황(context).
P(r|a, x, θ)는 θ에 기반한 우도 함수.
이전의 분포 P(θ)는 사전에 주어진다. (초기값)

는 보상(reward)을 최대화하는 행위 a를 찾는 것이다.

알고리즘을 설명하면 다음과 같다.

1. T번 동안 단계(round)를 돌면서,
2. 주어진 환경(x_t)과 기존 관측 결과(확률)에 기반해서 모든 행위(A)에 대해서 우도함수를 계산하고,
3. 우도함수 결과들 중에서 최대의 기대값을 갖는 행위(a)를 선택하고,
4. 선택된 행위를 수행한다.
5. 행위 선택의 결과를 관측하고
6. 관측된 결과를 기존 관측 결과들과 함께 보존한다.

이때 exploration과 exploitation은 확률에 기반한 우도 함수에 의해서 결정되는 것이다. 만약, 해결해야될 문제가 처음에 이야기한 것처럼 2가지의 경우(성공/실패)를 가지는 multi-armed bandit 문제라면 우도함수로 베타 분포를 사용할 수 있다.
베타 분포를 사용하면, 매우 빠르게 기대치를 계산할 수 있다.

K는 총 슬롯머신(행위)의 숫자.
S는 성공 횟수.
F는 실패 횟수.

알고리즘 2에서 베타 분포를 계산할 때, α와 β 형태로 context(환경 값)이 반영되고, Si와 Fi 형태로 기존 확률값이 반영된다. 그리고 베타 분포의 결과 중에서 최대값을 갖는 것을 선택해서 수행하고 결과를 관측한다.
여기서 결과의 보존은 성공 회수와 실패 회수의 합 형태로 보존된다.
모든 행위에 대해서 실제 기대치를 계산할 수 없다고 하더라도 자원소모가 크기 때문에 실제적으로 불가능한 문제의 경우 유사 예측치를 사용해야 한다.
Thompson sampling은 이 유사 예측치로 우도 함수(likelihood)를 사용함으로써 적은 자원으로 빠르게 계산을 할 수 있는 알고리즘이다.
또한 계속적으로(round가 지날 때마다) 예전 확률이 갱신되고 이것을 새로운 단계에서 사용하기 때문에 온라인상의 반응을 적용하기에 좋다.
Thompson sampling은 성능과 정확도 면에서 우수한 편이기에 활용도가 매우 높다.
하지만 우도 함수(likelihood)를 만들고 수학적으로 증명하는 것이 어려운 것이 단점이다.
이항 변수를 가지는 문제(multi-armed bandit)에서는 베타 분포를 사용할 수 있기에, 이항 변수 문제를 가지는 도메인에서는 사용해봄직한 알고리즘이다.