トンプソンサンプリング
治療効果評価をシミュレートするために適用されたトンプソンサンプリングの具体的な例

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

説明

コンテキストの集合、アクションの集合、および における報酬 を考えます。プレイヤーの目的は、様々なコンテキストの下でアクションを実行し、例えば累積報酬を最大化することです。具体的には、各ラウンドにおいて、プレイヤーはコンテキスト を取得し、アクションを実行し、コンテキストと実行されたアクションに依存する分配に従って 報酬を受け取ります。X{\displaystyle {\mathcal {X}}}あ{\displaystyle {\mathcal {A}}}R{\displaystyle \mathbb {R} }×∈X{\displaystyle x\in {\mathcal {X}}}1つの∈あ{\displaystyle a\in {\mathcal {A}}}r∈R{\displaystyle r\in \mathbb {R} }

トンプソンサンプリングの要素は以下のとおりである: [ 3 ] : sec. 4

  1. 尤度関数 ;P（r|θ、1つの、×）{\displaystyle P(r|\theta,a,x)}
  2. の分布のパラメータのセット。Θ{\displaystyle \Theta}θ{\displaystyle \theta}r{\displaystyle r}
  3. これらのパラメータに関する事前分布 。P（θ）{\displaystyle P(\theta )}
  4. 過去の観測トリプレット;D＝{（×;1つの;r）}{\displaystyle {\mathcal {D}}=\{(x;a;r)\}}
  5. 事後分布 、ここでは尤度関数です。P（θ|D）∝P（D|θ）P（θ）{\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}P（D|θ）{\displaystyle P({\mathcal {D}}|\theta )}

トンプソンサンプリングは、期待報酬を最大化する確率に従って行動を行うことから成り、行動は確率[ 3 ]で選択される。アルゴリズム4 1つの∗∈あ{\displaystyle a^{\ast }\in {\mathcal {A}}}1つの∗{\displaystyle a^{\ast}}

∫私[E（r|1つの∗、×、θ）＝最大1つの′E（r|1つの′、×、θ）]P（θ|D）dθ、{\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} }

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

歴史

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

他のアプローチとの関係

確率マッチング

確率マッチングとは、クラス所属の予測がクラスベースレートに比例する決定戦略です。例えば、トレーニングセットにおいて、正例が60%の確率で観測され、負例が40%の確率で観測される場合、確率マッチング戦略を用いる観察者は（ラベル付けされていない例の場合）、インスタンスの60%で「正」のクラスラベルを予測し、インスタンスの40%で「負」のクラスラベルを予測します。

ベイズ制御則

トンプソンサンプリングを任意の動的環境と因果構造に一般化したベイズ制御則は、行動と観測を含む適応符号化問題に対する最適解であることが示されている。[ 5 ]この定式化では、エージェントは一連の行動の混合として概念化される。エージェントは環境と相互作用するにつれて因果特性を学習し、環境の行動を最もよく予測する行動に対する相対エントロピーを最小化する行動を採用する。これらの行動が最大期待効用原理に従って選択された場合、ベイズ制御則の漸近的挙動は、完全に合理的なエージェントの漸近的挙動と一致する。

設定は以下の通りである。エージェントが時刻までに発行した行動を とし、エージェントが時刻までに収集した観測値を とする。すると、エージェントは確率[ 5 ]で行動を発行する。1つの1、1つの2、…、1つのT{\displaystyle a_{1},a_{2},\ldots ,a_{T}}T{\displaystyle T}o1、o2、…、oT{\displaystyle o_{1},o_{2},\ldots ,o_{T}}T{\displaystyle T}1つのT+1{\displaystyle a_{T+1}}

P（1つのT+1|1つの^1:T、o1:T）、{\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T}),}

ここで「ハット」記法は、通常の観察ではなく因果的介入（因果関係を参照）であるという事実を表す。エージェントが自身の行動に関して信念を抱いている場合、ベイズ制御則は次のようになる。 1つの^t{\displaystyle {\hat {a}}_{t}}1つのt{\displaystyle a_{t}}θ∈Θ{\displaystyle \theta \in \Theta }

P（1つのT+1|1つの^1:T、o1:T）＝∫ΘP（1つのT+1|θ、1つの^1:T、o1:T）P（θ|1つの^1:T、o1:T）dθ{\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T})=\int _{\Theta }P(a_{T+1}|\theta ,{\hat {a}}_{1:T},o_{1:T})P(\theta |{\hat {a}}_{1:T},o_{1:T})\,d\theta }、

ここで、 はアクションと観測が与えられたパラメータ上の事後分布です。 P（θ|1つの^1:T、o1:T）{\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}θ{\displaystyle \theta}1つの1:T{\displaystyle a_{1:T}}o1:T{\displaystyle o_{1:T}}

実際には、ベイズ制御は、各時間ステップで事後分布からパラメータをサンプリングすることに相当します。事後分布は、ベイズの規則を使用して、観測の（因果）尤度のみを考慮し、アクションの（因果）尤度を無視し、次にアクション分布からアクションをサンプリングすることによって計算されます。 θ∗{\displaystyle \theta ^{\ast}}P（θ|1つの^1:T、o1:T）{\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}o1、o2、…、oT{\displaystyle o_{1},o_{2},\ldots ,o_{T}}1つの1、1つの2、…、1つのT{\displaystyle a_{1},a_{2},\ldots ,a_{T}}1つのT+1∗{\displaystyle a_{T+1}^{\ast}}P（1つのT+1|θ∗、1つの^1:T、o1:T）{\displaystyle P(a_{T+1}|\theta ^{\ast },{\hat {a}}_{1:T},o_{1:T})}

上信頼限界（UCB）アルゴリズム

トンプソンサンプリングと上側信頼限界アルゴリズムは、多くの理論的保証の根底にある基本的な性質を共有しています。大まかに言えば、どちらのアルゴリズムも、探索的努力を最適である可能性のある行動に割り当てており、この意味で「楽観的」です。この性質を利用することで、UCBアルゴリズムで確立された後悔限界をトンプソンサンプリングのベイズ的後悔限界に変換したり[ 13 ]、これらのアルゴリズムと多くの問題クラスにわたって後悔分析を統合したりすることができます[ 14 ] 。

参考文献

  1. ^ a b トンプソン、ウィリアム・R. 「2つのサンプルの証拠を考慮すると、1つの未知の確率がもう1つの未知の確率を上回る尤度について」バイオメトリカ、 25(3–4):285–294、1933年。
  2. ^ トンプソン, WR (1935). 配分理論について.アメリカ数学ジャーナル, 57(2), 450-456.
  3. ^ a b c d e Daniel J. Russo、Benjamin Van Roy、Abbas Kazerouni、Ian Osband、Zheng Wen (2018)、「トンプソンサンプリングに関するチュートリアル」、機械学習の基礎とトレンド：第11巻、第1号、pp 1-96。https ://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
  4. ^ a b J. Wyatt.強化学習における探索と推論. エディンバラ大学人工知能学科博士論文. 1997年3月.
  5. ^ a b c d PAオルテガとDAブラウン「学習と行動のための最小相対エントロピー原理」、人工知能研究ジャーナル、38、475-511ページ、2010年、http://arxiv.org/abs/0810.3605
  6. ^ a b MJA Strens. 「強化学習のためのベイズ的枠組み」,第17回国際機械学習会議議事録, スタンフォード大学, カリフォルニア州, 2000年6月29日～7月2日, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
  7. ^ a b BC May, BC, N. Korda, A. Lee, DS Leslie. 「文脈バンディット問題における楽観的ベイズサンプリング」. ブリストル大学数学部統計グループ技術報告書, 2011年.
  8. ^ シャペル、オリヴィエ、リーホン・リー「トンプソンサンプリングの実証的評価」神経情報処理システムの進歩、2011年。http ://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
  9. ^ a b O.-C. Granmo. 「ベイズ学習オートマトンを用いた2本腕ベルヌーイバンディット問題の解決」、International Journal of Intelligent Computing and Cyber​​netics、3 (2)、2010、207-234。
  10. ^イアン・クラーク「比例A/Bテスト」、2011年9月22日、 http://blog.locut.us/2011/09/22/proportionate-ab-testing/
  11. ^ Granmo, OC; Glimsdal, S. (2012). 「分散型二腕バンディットに基づく意思決定のための加速ベイズ学習とGooreゲームへの応用」. Applied Intelligence . 38 (4): 479– 488. doi : 10.1007/s10489-012-0346-z . hdl : 11250/137969 . S2CID  8746483 .
  12. ^ Wu, Huasen; Liu, Xin; Srikant, R (2016), Dueling Banditsのためのダブルトンプソンサンプリング, arXiv : 1604.07101 , Bibcode : 2016arXiv160407101W
  13. ^ Russo, Daniel J.; Van Roy, ​​Benjamin (2014). 「事後サンプリングによる最適化学習」.オペレーションズ・リサーチ数学. 39 (4): 1221– 1243. arXiv : 1301.2609 . doi : 10.1287/moor.2014.0650 .
  14. ^ Daniel J. RussoとBenjamin Van Roy (2013)、「Eluder次元と楽観的探索のサンプル複雑性」、Advances in Neural Information Processing Systems 26、pp. 2256-2264。https ://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf
「 https://en.wikipedia.org/w/index.php?title=Thompson_sampling&oldid=1317790086」より取得