こんにちは。

今回は前回のバンディットアルゴリズムの続きです。UCBと簡単なトンプソンサンプリングの実装を行います。前回実装した\epsilon-GreedyとBoltzmann Softmaxとの最終的な比較も行います。

Keywords

この記事のキーワードを先にリストアップします。

  • \epsilon-Greedy
  • Boltzmann Softmax
  • Hoeffding’s inequality
  • UCB
  • Bayesian UCB
  • Thompson Sampling
  • scaled inverse chi-squared Distribution

先頭2つは前回やったので3つ目から話します。

Hoeffding’s inequality

Hoeffdingの不等式です。これはUCBの導出に使います。証明にはマルコフの不等式とチェビシェフの不等式を使います。まあそれは置いておいて、この不等式の意味を考えます。

確率変数Zの平均とその期待値の誤差t\in\mathbb{R}_+の確率をtで測っています。これがまさに後述するUCBの核の考え方です。こちら側でtそ操作することで、期待値のブレの許容範囲をある確率の範囲で操作することができます。

UCB

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

これは直感的にもいいですよね。何度も引いたことのあるガチャガチャよりも数回しか引いたことのないガチャガチャの方が可能性を感じますよね。そういうことです。


ただし、

見ての通り、分母N_t(a)が小さいほど大きい値が加算されます。イメージは次の感じです。

お気づきかもしれませんが逆数と言いつつ、ルートを付けてます。気になりますよね。ということで証明します。先程のHoeffdingの不等式を用います。

Hoeffdingの不等式においてX_i \in [a,b][0,1]として次が得られます。(u\geq 0)。報酬はベルヌーイを仮定しました。

a \in \mathcal{A}を一つとり固定します。私たちの問題に書き換えるためNotationを定義します。

  • r_t(a) 報酬(確率変数)
  • \mathcal{Q}(a)  を真の行動価値
  • \mathcal{\hat{Q}}(a)  を経験上の行動価値
  • u をupper confidence bound, u=U_t(a)

代入しますと

ここで上限に対する閾値をこちらで設定します。

これをU_t(a)に関して解けば終了です

おや?よくみると2の位置が異なります。それは\epsilonをこちらで設定する必要があるからです。confidence levelと言われます。

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

そしてこの時のアルゴリズムをUCB1いいます。代入して計算すると

先程の結果になりました。では実装してみます。

実はよくない結果です。前回のEGとBSと比べるとわかります。この記事の最後に全アルゴリズムの比較を行いますのでとりあえずは進めていきます。

Bayesian UCB

UCBにベイズを応用したアルゴリズムのことです。今までは報酬の分布にベルヌーイを仮定しましたが、他にもガウス分布の仮定があります。それぞれ次のように呼びます

  • Bernoulli – Thompson Sampling
  • Gaussian – Thompson Sampling

察しの通り事後分布からパラメータをサンプリングしてアームを選択します。

本当にハードなんですが、Gaussianの場合の詳しい計算は

この方がやってくれています。

Thompson Sampling

定義は少し複雑ですが、実装の際はサンプリングを行うので思ったよりはシンプルです。

とあるaが他のどのa'よりも価値が高い、という事後確率(\pi)を計算してaを選ぶアルゴリズムです。R_tは時刻tまでのアームのhistoryです。

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

ここでR_iarm_iの報酬履歴です。左の積分が\mathcal{Q}(a) = \theta_iになる確率で右の積分がその他のアームで\mathcal{Q}(a') \leq \theta_iとなる確率です。積分が解析的ではないので、サンプリングします。困ったときはサンプリングです。結果アルゴリズムは次のように単純化できます。

  1. 各アームaの報酬の期待値に関する事後分布\pi( \theta  |R_a)から乱数\theta_aを生成
  2.  TS(a) = \arg \max_{a\in\mathcal{A}}  \theta_a \sim \pi( \theta |R_a)

何度も言いますが報酬の分布はベルヌーイを仮定するので事後分布であるベータ分布は非常にシンプルになります。

実装では一様分布を仮定するのでパラメータは共に1とします。

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

全アルゴリズムでBARとCumulative Rewardsも比較してみます。

Thompson Samplingが圧勝でした。

scaled inverse chi-squared Distribution

もしGaussianでThompson Samplingを実装するならばこちらを\sigma^2の事前分布として導入します。(事前分布p(\mu, \sigma^2)を条件付き確率で分解する)scaled inverse chi-squared分布といいます。

    \[  p (\sigma^2) \sim  \mathcal{X}^2 (v_{0}, \hat{\sigma}_{0}^{2})  \]


Code

Gaussian Thompson Samplingすごく難しいですね、パラメータが多すぎてなにがなんだが、、、

次回はContextual BanditとIPSについてまとめたいと思います。でわ

References