専ら上手くいくという Thompson Sampling のシュミレーションをする

Thompson Sampling

• ベイズ戦略で MAB の腕を決める方法
  • 事後確率から sampling して最大となる腕を選ぶ

参考

• 確率的バンディット問題
• 多腕バンディット問題の 理論とアルゴリズム

シュミレーション

• johnmyleswhite/BanditsBook · GitHub の python のシュミレーションに合うような Thompson Sampling(ベルヌーイ施行) クラスを作って実行
  • ``An Empirical Evaluation of Thompson Sampling'' に書いてあるアルゴリズムを実装している(はず)

参考

• An Empirical Evaluation of Thompson Sampling

code 類

結果

• 報酬を得る確率

• 得る報酬の累積

• 選ばれる腕の分散

まとめ

• epsilon-greedy，UCB1 および Softmax と比べて，Thompson Sampling（紫） は
  • 報酬を得る確率が高く
  • 報酬の合計は一番大きく
  • 報酬を最大化する腕を見つけるのが速い ということが分かりました(小並感)