ノート

強化学習関連のこと

MENU

【強化学習】UCBアルゴリズム

UCBアルゴリズム

UCBアルゴリズム知らないものに楽観的にを ポリシーにした行動選択戦略です。

UCBではUCB値という値を用いて、 行動選択を行います。

UCB値は選択肢毎に設定され、

以下の式を用いて、更新していきます。

\begin{align} UCB_i = Q_{t} + C \sqrt{\frac{\ln n}{2 n_i}} \end{align}

$Q_i$ は選択肢iの平均報酬。nは全試行回数、$n_i$は アームiの全試行回数。Cは定数。

上記の式は、右の項によって、あまり選択していなければ、 その価値が高くなるように調整されます。

逆に、多く選択されれば、分母が大きくなるので0に近づきます。

つまり、純粋な期待値でだけで評価するようになります。

アルゴリズム的には以下のようになります。

  1. UCB値を初期化
  2. 最も高いUCB値を持つ選択肢$i$を選択
  3. 選択によって報酬$r$を得る
  4. 選択肢$i$ の期待値$Q_i$、総プレス数n、選択肢$n_i$ を1ずつ増やす
  5. UCB値を更新
  6. 2,3,4,5を繰り返す

参考文献

https://www.jstage.jst.go.jp/article/fss/30/0/30_174/_pdf