トンプソンサンプリング

トンプソンサンプリング^{[ 1 ] [ 2 ] [ 3 ]}は、ウィリアム・レイ・トンプソンにちなんで名付けられた、マルチアームバンディット問題における探索と活用のジレンマに対処する行動を選択するためのヒューリスティックである。これは、ランダムに抽出された信念に関して期待報酬を最大化する行動を選択することから成ります。

一連の状況を考慮する$\displaystyle {\mathcal {X}}}$一連の行動${\displaystyle {\mathcal {A}}}$、そして報酬は${\displaystyle \mathbb {R} }$プレイヤーの目的は、累積報酬を最大化するなど、さまざまな状況下で行動を起こすことです。具体的には、各ラウンドでプレイヤーは状況を取得します。${\displaystyle x\in {\mathcal {X}}}$アクションを実行する${\displaystyle a\in {\mathcal {A}}}$そして報酬を受け取る${\displaystyle r\in \mathbb {R} }$状況や発動されたアクションに応じて分布が変化する。

トンプソンサンプリングの要素は以下のとおりです。^{[ 3 ]：第4節}

1. 尤度関数${\displaystyle P(r|\theta ,a,x)}$;
2. セット${\displaystyle \Theta }$パラメータの${\displaystyle \theta }$分布の${\displaystyle r}$;
3. 事前分布${\displaystyle P(\theta )}$これらのパラメータに基づいて；
4. 過去の観察結果 三つ子${\displaystyle {\mathcal {D}}=\{(x;a;r)\}}$;
5. 事後分布${\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}$、 どこ${\displaystyle P({\mathcal {D}}|\theta )}$は尤度関数です。

トンプソンサンプリングは、アクションを再生することから成ります。${\displaystyle a^{\ast }\in {\mathcal {A}}}$期待報酬を最大化する確率に応じて行動する。$\displaystyle a^{\ast }}$確率^{[ 3 ]で選択される：アルゴリズム4}

${\displaystyle \int \mathbb {I} \left[\mathbb {E} (r|a^{\ast },x,\theta )=\max _{a'}\mathbb {E} (r|a',x,\theta )\right]P(\theta |{\mathcal {D}})d\theta ,}$

どこ${\displaystyle \mathbb {I} }$は指示関数です。

実際には、このルールはサンプリングによって実装されます。各ラウンドで、パラメータ${\displaystyle \theta ^{\ast }}$事後分布からサンプリングされる${\displaystyle P(\theta |{\mathcal {D}})}$[ ^{3 ]：7と}アクション${\displaystyle a^{\ast }}$最大化するように選択された${\displaystyle \mathbb {E} [r|\theta ^{\ast },a^{\ast },x]}$すなわち、サンプリングされたパラメータ、行動、および現在のコンテキストが与えられた場合の期待報酬です。概念的には、これはプレイヤーが各ラウンドで事後分布に従ってランダムに信念をインスタンス化し、それに従って最適に行動することを意味します。ほとんどの実用的なアプリケーションでは、モデル全体に​​わたる事後分布を維持してサンプリングすることは計算上負担が大きくなります。そのため、トンプソンサンプリングは近似サンプリング手法と組み合わせて使用​​されることがよくあります。^{[ 3 ]：第5節}

トンプソンサンプリングは、もともと1933年にトンプソンによって記述されました。^{[ 1 ]}その後、多腕バンディット問題の文脈で何度も独立して再発見されました。^{[ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]}バンディットの場合の収束の最初の証明は1997年に示されました。^{[ 4 ]}マルコフ決定過程への最初の適用は2000年でした。^{[ 6 ]}関連するアプローチ（ベイズ制御ルールを参照）は2010年に発表されました。^{[ 5 ]} 2010年には、トンプソンサンプリングが瞬時に自己修正することも示されました。^{[ 9 ]}コンテキストバンディットの漸近収束結果は 2011 年に発表されました。^{[ 7 ]}トンプソン サンプリングは、Web サイト設計やオンライン広告におけるA/B テスト、 ^{[ 10 ]}および分散型意思決定における加速学習など、多くのオンライン学習問題で広く使用されています。^{[ 11 ]}従来の MAB の変種であるデュエリング バンディットに対して、ペアワイズ比較の形式でフィードバックが得られるダブル トンプソン サンプリング (D-TS) ^{[ 12 ]}アルゴリズムが提案されています。