UCBアルゴリズムを実装して多腕バンディット問題(マルチアームバンディットプロブレム)で試してみました。
UCBアルゴリズム
UCBアルゴリズムは「知らない選択肢は楽観的に」をポリシーとした行動選択手法です。
UCBではUCB値という値を用いて、行動選択を行います。 選択肢\(i\)のUCB値は以下のように定義されます。
$$\begin{aligned}
UCB_i = Q_{i} + C \sqrt{\frac{2 \ln n}{n_i}}
\end{aligned}$$
UCB_i = Q_{i} + C \sqrt{\frac{2 \ln n}{n_i}}
\end{aligned}$$
\(Q_i\) は選択肢iを選択して得られた報酬の平均値。nは全試行回数、\(n_i\)は 選択肢iの試行回数。Cは定数。 このUCB値が最も高い選択肢をステップ毎に選択します。
アルゴリズム的には以下のようになります。
- UCB値を初期化
- 最も高いUCB値を持つ選択肢\(i\)を選択
- 選択によって報酬\(r\)を得る
- 選択肢\(i\) の期待値\(Q_i\)、総試行回数n、選択肢の試行回数\(n_i\) を１ずつ増やす
- 上述した式によって実行した選択肢\(i\)のUCB値を更新
- 2,3,4,5を繰り返す
実験
問題設定
多腕バンディット問題を用います。
今回は５つのアームがあり、３つ目のアームの期待報酬値が最も高い設定とします。
ソースコード
結果
上述したプログラムを実行すると、以下のようなステップ毎の獲得報酬の推移を出力します。
ステップ毎のUCBエージェントの利得の推移
UCBアルゴリズムによって、ある程度高い報酬を得ることができていると確認できます。
コメント