これからの強化学習：ノート4

読んでいる本（出典）：これからの強化学習 | 牧野貴樹, 澁谷長史, 白川真一 |本 | 通販 | Amazon

この本読みですが、スライドにまとめようとしたら2回で挫折したのでとりあえず感想ノートの方を続けることにします。
というかどこまで読んだかもよくわからなくなりましたが、とりあえず落ち着いて現在の進捗を整理すると以下です。

テキスト範囲	読書メモ	スライド
1.1～1.3節（1～41ページ）	ノート1	勉強会#1
1.4～1.5節（42～70ページ）	まだ	勉強会#2
2.1節（71～111ページ）	ノート3	まだ
2.2～2.4節（112～147ページ）	この記事	まだ

以下、読書メモ。2章以降は1節1節が真面目に読むと重いのでふわっと雰囲気だけ。スライド作成時に補完したい。

2.2節

まず、強化学習にはさまざまな解法アルゴリズムがあるけど、アルゴリズムの性能を評価できないの？というお話。

1つの考え方としては、最善の選択をできた場合の収益に届かなかった分（リグレット）でもって評価する。
多腕バンディットタスクの場合、
- UCB1は、リグレットを $\varepsilon$ 減衰版 $\varepsilon$ -greedy を長期的に適用した場合よりも抑えられる。このアルゴリズムはゲーム木の探索やその他の探索問題にも応用できる。
- Thompson サンプリング（下図；各腕を引いたときにコインが出てくる確率 $\mu$ の事後分布を更新していき、常にこの事後分布からのランダムサンプリング結果が最大の腕を選択する）でも「不確かなときは楽観的に」が実現でき、リグレットをUCB1と同等に抑えられる。
  
  ※ 確率分布の形は適当です。
別の考え方としては、間違った行動（最善の選択をした場合より期待収益が劣る行動）を取ってしまった回数で評価する（サンプル複雑性）。

あと、ちょうどUCB1や Thompson サンプリングで評価値の確率分布を更新していくように、探索と利用のトレードオフはベイズ的に取り扱えるよね、というお話。

ベイズ適応的マルコフ決定過程（BAMDP）という。

2.3節

報酬ってどう定義すればいいんだろう？というお話。

例えばボードゲームの学習で勝ったときにのみ +1 という報酬の定義はあり得るが、ゲームの性質が以下のような場合、このように終端状態のみで報酬を定義するのは得策ではない。
- 初期方策＝ランダムな手で勝てる見込みが薄い（そもそも学習が進まない）。
- 手数が多く、終端状態が初手の行動価値を修正する幅が小さい（学習が遅い）。
- 自分が勝ったとき、自分の行動と相手の行動のどちらが寄与したのか明らかにはわからない。
学習の結果を最善手に導いてくれるような報酬を定義したいんだけど、それなら最善手がわかっているときに、最善手が学習されるように（？）各状態に報酬を割り当てればいい（逆強化学習）。状態集合が有限集合なら、報酬関数の推定は線形計画問題になる。

2.4節

学習を速くしたいというお話。

経験強化型学習では、報酬を得たときに、前回報酬を得て以降に現れた状態行動対の評価値を更新する。このとき、エピソード内の各ステップの状態行動対に報酬からどれだけ過去かに応じてポイントを割り当て、そのエピソードにおけるある状態行動対の評価は、その状態行動対に割り当てられたポイントの和とする（その状態行動対を4回通れば4回分のポイントの和を取る：138ページの図2.4.1）。過去にさかのぼるほど等比減少関数でポイントを割り当てれば、迂回路となる状態行動対を優先してしまうことがない（ということか？）。
- Sutton本での単純なモンテカルロ法との違いは、単純なモンテカルロ法においては、ある状態行動対の評価はエピソード内の初回発生後の収益となるので、迂回路も平等に評価されてしまう。だからモンテカルロ法だと学習が遅い。ということだと思う。

「リグレットは『探索コスト』を表す指標に見えるが（113ページ）」：現実に「最善の選択をできた場合の収益」が出せないのは、現実には探索にコストをかける必要があるので、そのコストの分が差し引かれているように見える、という見方と考えられる。ただ、本当は、この箇所の直後に書かれているように、「探索と利用」から「探索」だけ切り離したようなものではない。
「探索と利用を同時に実現する（113ページ）」： UCB1は、どれだけ探索できているか（＝どれだけの精度で評価できているか）を加味して行動を選択するアルゴリズムだった（「これからの強化学習」勉強会#1 - クッキーの日記 7ページ）。その行動が未探索なほど（＝評価の精度が粗いほど）より高く評価するようにしておくことで、利用のために取った行動で探索（精度向上）も実現している。
Thompson サンプリング（114ページ）：フリーの原論文見つからず。以下のPDFが参考になる？
https://bandits.wikischolars.columbia.edu/file/view/Lecture+4.pdf
「（略）強化学習が優位な点としては、（略）たとえば、動的計画法のように環境のダイナミクスを表す状態遷移行列は不要であるし（127ページ）」：動的計画法が強化学習の範疇ではないような書き方なんだけど、動的計画法は強化学習の一解法だと思っていたんだけど、モンテカルロ法やTD学習による解き方のみを強化学習とみなすような線引きもあるということ？