バンディットアルゴリズムの続き

2020.02.07

機械学習

こんにちは。kzです。

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

Keywords

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

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

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

強化学習　Bandit Algorithm で入門する

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の場合の詳しい計算は

https://cafeunder.github.io/rosenblock-chainers-blog/2018/03/07/bayes-gaussian-mean-sigma.html

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

Thompson Sampling

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

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

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

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