「これからの強化学習（2016　編　牧野貴樹）」p10〜

不確かな時は楽観的にという発想で楽観的初期値法が提案されたが、これには反例がある。そこで、

すべての選択肢に対して必要な探索が行われることを保証しつつ、探索のコストも最適解を間違えるリスクも少なくできる

ことが理論的に保証されているUpper Confidence Bound（UCB）アルゴリズムがある。これは、多腕バンディット問題の解法としてよく用いられるらしい。

UCB1アルゴリズム

$R$ ：払戻額の最大値と最小値の差
$N_{i}$ ：これまで腕iを選んだ回数
$r_{n_{i}}$ ：腕iをn回目に選んだ時の報酬

1. まだ選んだことのない腕があれば、そのうちの１つを選ぶ

2. 各々の腕iから得られる報酬の期待値を計算

$\mu_{i}=\frac{ \sum_{ n_{i} }r_{ n_{i} } }{ N_{i} }$

3. 各々の腕iから得られる報酬の信頼区間の半幅を計算

$U_{i} = R \sqrt{ \frac{ 2ln(\sum_{i}N_{i}) }{ N_{i} } }$

4. 以下の値が最大の腕を選ぶ

$x_{i} = \mu_{i} + U_{i}$

以上。次回、greedyとε-greedyとUCB1で多腕バンディット問題を解いて、性能を比較する。

メモ帳