メモ帳

これは私のメモ帳です。

UCB1アルゴリズム（多腕バンディットの例）

「これからの強化学習（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で多腕バンディット問題を解いて、性能を比較する。

不確かな時は楽観的に

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

報酬の期待値の2種類の誤りの非対称性から考える。ある選択肢の期待値が小さく見積もられる場合は、それを修正するのは困難である。一方ある選択肢の期待値が大きく見積もられる場合は、その後その選択肢を選び続けるうちに間違いが修正される。したがって、

期待値に不確実性がある時は、その不確実性の範囲内で大きい期待値を仮定すべき

ということ。

楽観的初期値法（多腕バンディットの例）

学習前にあらかじめ、各腕から報酬の最大値をK回得ていたことを仮定しておく

  • 腕iのプレイ回数： N_{i}
  • 腕iから実際に得た報酬和： R_{N_{i}}
  • 腕iの報酬の最大値： r_{max}

\mu'_{i} = \frac{R_{N_{i}} + Kr_{max}}{N_{i} + K}

こうしておくと、どの腕も初めは真の報酬期待値よりも大きい値だと見積もっていることになる。そこからいつも最大期待値の腕を選び続けていれば、その腕の期待値が真の値に近づいた時に他の（楽観的期待値の）腕より期待値が小さければ選択が変わっていくので、最終的に真の期待値が最大の腕を選び続けるだろう、という考えに基づく。

しかし、反例がある。（その反例が知りたい）

より洗練された方法として、Upper Confidence Bound（UCB）アルゴリズムがあり、これは多腕バンディット問題の解法としてよく知られているらしい。

報酬の期待値を誤って見積もる2種類の例

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

  • 多腕バンディット問題（腕はAとB）を解く例
  • 初期の一定試行だけランダムに探索し、その結果から各腕の報酬期待値を計算し、それ以降は最適と推定した選択だけを続ける（greedy）。
  • 腕Aの真の報酬確率は0.6
  • 腕Bの真の報酬確率は0.4
  • 期待値の見積もりを誤る原因は、探索数が少ないこと

1. 腕Bの期待値を高く見積もる誤り

探索中にたまたまBで報酬がたくさん出て、期待値を0.8と見積もった。

その後ずっと、最適であると思われるBを選び続けたが、やがて真の期待値である0.4に近づいていきAよりも期待値が小さいことがわかった。

この場合は、常に期待値を比較して行動を選択していればやがてAを選ぶように修正できる。

2. 腕Aの期待値を低く見積もる誤り

探索中にたまたまAで報酬があまり出ず、期待値を0.2と見積もった。

その後ずっと、最適であると思われるBを選び続けた。

この場合は、常に期待値を比較して行動選択してもAを選ぶことがないのでAの期待値は0.2から更新されず、最適でないBを選び続けることになる。

まとめ

ある時点で探索を打ち切ると、2の例のように本来最適でない行動を選択し続ける可能性がある。

したがって、一定の割合で探索を続けた方が良いのではないか。

→ ε-greedyアルゴリズム

補足

  • この問題は教師なし学習では起こりうるが、教師あり学習では起こり得ない。なぜなら、教師あり学習では、あらかじめ訓練データがすべて与えられているから。
    • したがって、訓練データが偏る可能性があるタスクに教師あり学習を適用すると同じ問題が発生しうる。
  • 理論的には、探索のコストと最適解を取り違えるリスクを統一して扱うためにリグレットに基づく分析が用いられる。

truffleでtest用RPCを使う

truffleでtest用RPCを使う

testRPCを使うメリット

  • デプロイが一瞬（これでかい）

起動方法

# globalでインストールしてあるなら、どこでも実行できる
$ testrpc
# 起動すると、この仮想etherネット内で使用可能なアカウントのアドレスとプラベートキー一覧、あと、host:portが出力される
# デフォルトは、localhost:8545

テストスイート実行（事前にコンパイルやデプロイをする必要はない）

# デプロイ先を設定（デフォルトのままで良いはずだけど一応確認）
$ vim truffle.js
# 以下のように、developmentのhostがlocalhost(127.0.0.1)で、portが8545になっていれば良い
# というか、testrpcのホストとポートね
> module.exports = {
>   networks: {
>     development: {
>       host: '127.0.0.1',
>       port: 8545,
>       network_id: '*' // Match any network id
>     }
>   }
> }

# テストスイート実行
$ truffle test