今回は前回のバンディットアルゴリズムの続きです。UCBと簡単なトンプソンサンプリングの実装を行います。前回実装した

Keywords
この記事のキーワードを先にリストアップします。-Greedy
- Boltzmann Softmax
- Hoeffding’s inequality
- UCB
- Bayesian UCB
- Thompson Sampling
- scaled inverse chi-squared Distribution
Hoeffding’s inequality

確率変数




UCB
UCBはアームの期待値に加えてその上限(Upper Confidence Bound)、いわばアームの可能性(分散)、を考慮したアルゴリズムです。どうやって上限を加味するかといいますと、対象のアームを選択した回数の逆数で重み付けします。こうすることで多数引いたアームにはより小さい上限を、少数引いたアームにはより大きい上限を付与することができます。これは直感的にもいいですよね。何度も引いたことのあるガチャガチャよりも数回しか引いたことのないガチャガチャの方が可能性を感じますよね。そういうことです。





Hoeffdingの不等式において
![Rendered by QuickLaTeX.com X_i \in [a,b]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-e466ddd4e42358957f329ef15587b4d0_l3.png)
![Rendered by QuickLaTeX.com [0,1]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-25b6d943ab489c05a3dbd5ea29087a48_l3.png)



報酬(確率変数)
を真の行動価値
を経験上の行動価値
をupper confidence bound,





UCBはこのconfidence levelをパラメータとして持ちます。もっとも一般的な値は次のようになります。


Bayesian UCB
UCBにベイズを応用したアルゴリズムのことです。今までは報酬の分布にベルヌーイを仮定しましたが、他にもガウス分布の仮定があります。それぞれ次のように呼びます- Bernoulli – Thompson Sampling
- Gaussian – Thompson Sampling
本当にハードなんですが、Gaussianの場合の詳しい計算は この方がやってくれています。
Thompson Sampling
定義は少し複雑ですが、実装の際はサンプリングを行うので思ったよりはシンプルです。





事後確率は積分を用いて次のように計算されます。





- 各アーム
の報酬の期待値に関する事後分布
から乱数
を生成

Best Arm RateをUCBと比較してみます。

scaled inverse chi-squared Distribution
もしGaussianでThompson Samplingを実装するならばこちらを


Code
次回はContextual BanditとIPSについてまとめたいと思います。でわ
References
- https://youtu.be/xN11-epRuSU
- https://youtu.be/TIlDzLZPyhY
- http://snap.stanford.edu/class/cs246-2013/slides/18-bandits.pdf
- https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html
- https://courses.cs.washington.edu/courses/cse599i/18wi/resources/lecture10/lecture10.pdf
- https://hagino3000.blogspot.com/2016/12/linear-bandit.html
- https://www.slideshare.net/tsubosaka/introduction-contexual-bandit
- http://ibisml.org/archive/ibis2014/ibis2014_bandit.pdf
- http://seetheworld1992.hatenablog.com/entry/2017/06/04/150253
- https://to-kei.net/bayes/bayes-normal-distribution/