Thompson Sampling이란? 주어진 $k$개의 액션에 해당하는 reward의 추정치 $Q_t(a)$가 확률 분포를 따른다고 가정하는 것이다. 이때 많이 사용하는 확률 분포는 베타 분포이다. MAB와의 가장 큰 차이점은 각각의 액션의 reward 추정치를 확률이 아닌 확률 분포를 사용하는 것이다. 베타 분포(Beta Distribution) 두 개의 양의 변수 $\alpha$, $\beta$로 표현할 수 있는 확률 분포이며, 0과 1 사이의 값을 갖는다. $$ Beta(x, \alpha, \beta) = \frac{1}{B(\alpha, \beta)}x^{\alpha - 1}(1 - x)^{\beta - 1} $$ 여기서 $B(\alpha, \beta)$는 $\alpha$, $\beta$에 의해 ..

Multi-Armed Bandit이란? 카지노에 있는 슬롯머신은 한 번에 한 개의 arm을 당길 수 있다. (One-Armed Bandit) 만약에 카지노에 있는 K개의 슬롯머신을 N번 플레이할 수 있으면 어떻게 플레이 하는 것이 좋을지에 관한 아이디어에서 나온 것이다. K개의 슬롯머신에서 얻을 수 있는 reward의 확률이 모두 다르다고 가정한다. Reward를 최대화하기 위해서는 arm을 어떠한 순서로 또는 어떤 정책에 의해 당겨야 하는지를 구하는 것이 문제이다. Multi-Armed Bandit의 문제 그러나 슬롯머신의 reward 확률을 정확히 알 수 없다는 것이 단점이다. 모든 슬롯 머신을 동일한 횟수로 당기면 높은 reward를 얻을 수 없게 된다. (Exploration) 일정 횟수만큼 슬롯..