はじめに
- トンプソンサンプリングってあるよね
- トンプソンサンプリングは事後分布からサンプリングしてargmaxをとるよね
- なんでこれがいいんだろうか？？ 案外解説どこにも書いて無い？？
トンプソンサンプリングのおさらい
問題設定：バンディット問題
- $K$個のバンディット（スロットマシン）が存在する。
- バンディットにはそれぞれアームがついており、アーム引くことでスロットマシンの抽選をすることができる。
- 抽選で「はずれ」が出ると0点、「当たり」が出ると1点がもらえる（報酬がベルヌーイ分布）
- それぞれ「当たり」が出る確率が$\theta_i^*$で設定されている。ただし、ユーザはその設定値は見ることができない。
- 各時刻でアームを一つ引くことができるとき、累積報酬を最大化する（実際にはリグレットを最小化する）ようにするにはどのようにアームを引いていけばいいだろうか？ 各バンディットの素性もわからないので、探索的なトライも必要である。
トンプソンサンプリングの説明
トンプソンサンプリングは「現在のデータに基づき、"そのアームが期待値最大である確率" に従ってアームをランダムに選択する手法」と説明される。
ここは「ほう、直感的にも良さそうなアルゴリズムだなあ」と思う。
アルゴリズム
事後分布からサンプリングしてargmaxをとる操作で構成される：
- データセットを$D = \lbrace \rbrace$として初期化する
- 各アーム$i$の$\theta_i$の事後分布$p_i(\theta_i|D)$を計算する
- 以下繰り返し
3-1. 各アーム$i$に対して事後分布からサンプリングを行う：$\theta_i$ ~ $p_i(\theta_i|D)$
3-2. $\hat{i} = \operatorname*{argmax}_i\ \theta_i$を計算
3-3. アーム$\hat{i}$を引き、アーム$i$に対する報酬値$r^i$を取得
3-4. データセットを$D ← D + \lbrace r^i\rbrace$で更新
本題
なんで事後分布からのサンプリング結果に対するargmaxを行うことで、現在のデータに基づき、"そのアームが期待値最大である確率"に従ってアームをランダムに選択するという方法が達成されるのか？
ここが一番よくわからない。
\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\newcommand{\argmin}{\mathop{\rm arg~min}\limits}
これを数式的に解説してみよう。実は全然難しくないが、表記だけやや複雑になる。
A. トンプソンサンプリングで$i$番目のアームが選択される確率を考えてみると
\begin{align}
& \Pr(事後分布からのサンプリング結果に対する\argmaxでiが出る)\\
&= \Pr\left(i\in \argmax_j\; \theta_j ;\ \theta_jはp_j(\cdot|D)からサンプリング\right)\\
&= \Pr\left(\theta_i \geq \max_j \theta_j;\ \theta_jはp_j(\cdot|D)からサンプリング\right)\\
&= \Pr\left(\theta_i \geq \max_j \theta_j;\ \theta_j \sim p_j(\cdot|D)\right)
\end{align}
B. データ$D$に基づき、$i$番目のアームが期待値最大である確率を計算してみる。報酬$r$はベルヌーイ分布に従うことに注意すると$E[r^j]=\theta_j$である。$\theta_j$はデータ$D$が与えられているとき、$p_j(\theta_j|D)$に従うと推測される。これを使えば
\begin{align}
& \Pr(i番目のアームが期待値最大 | D)\\
&= \Pr\left(E[r^i] \geq \max_j E[r^j] \middle| D\right)\\
&= \Pr\left(\theta_i \geq \max_j \theta_j;\ \theta_jは p_j(\theta_j|D)に従う\right)\\
&= \Pr\left(\theta_i \geq \max_j \theta_j;\ \theta_j\sim p_j(\theta_j|D)\right)
\end{align}
よってA, Bの結果から、両者の確率が一致することが示された。
おわりに
- 簡単すぎて逆に誰も説明してくれないこと、あるよねー。
- トンプソンサンプリング解説してる本や記事自体が少ない気もする。