【強化学習】UCBアルゴリズム〜多腕バンディット問題を解く〜

UCBアルゴリズムを実装して多腕バンディット問題(マルチアームバンディットプロブレム)で試してみました。

UCBアルゴリズム

UCBアルゴリズムは「知らない選択肢は楽観的に」をポリシーとした行動選択手法です。

UCBではUCB値という値を用いて、行動選択を行います。 選択肢\(i\)のUCB値は以下のように定義されます。

$$\begin{aligned}
UCB_i = Q_{i} + C \sqrt{\frac{2 \ln n}{n_i}}
\end{aligned}$$

\(Q_i\) は選択肢iを選択して得られた報酬の平均値。nは全試行回数、\(n_i\)は 選択肢iの試行回数。Cは定数。 このUCB値が最も高い選択肢をステップ毎に選択します。

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

  1. UCB値を初期化
  2. 最も高いUCB値を持つ選択肢\(i\)を選択
  3. 選択によって報酬\(r\)を得る
  4. 選択肢\(i\) の期待値\(Q_i\)、総試行回数n、選択肢の試行回数\(n_i\) を1ずつ増やす
  5. 上述した式によって実行した選択肢\(i\)のUCB値を更新
  6. 2,3,4,5を繰り返す

実験

問題設定

多腕バンディット問題を用います。

今回は5つのアームがあり、3つ目のアームの期待報酬値が最も高い設定とします。

ソースコード

結果

上述したプログラムを実行すると、以下のようなステップ毎の獲得報酬の推移を出力します。

f:id:ttt242242:20190813160145p:plainステップ毎のUCBエージェントの利得の推移

UCBアルゴリズムによって、ある程度高い報酬を得ることができていると確認できます。

参考文献

コメント

タイトルとURLをコピーしました