本日は強化学習について。
強化学習とは
教師あり、なし学習と違い、最終的な目標だけ設定されたものを指します。
強化学習には
・environment(環境)
・Agent(行動をおこすもの)
・reward(報酬)
の3つの要素があり、environmentの中でAgentが行動を起こし、行動によって得られるrewardを最大にするのが強化学習の行うものです。オセロなどのゲームに用いられます。
強化学習の行動の流れ
入力(過去の状態）
↓
方策(policy:π)
↓
出力（行動）
の流れを繰り返します。何回か繰り返すと報酬が得られ、とるべき行動を学習します。
多椀バンディット問題
ではどう方策をとればよいのでしょうか、多椀バンディット問題があります。
あるギャンブラーと複数のスロットマシーンがあります。ギャンブラーはスロットマシーンを有限回回して報酬を得ます。またスロットマシーンの報酬は確率的で、それぞれに偏りがあります。累積報酬の最大化するにはどう行動すればよいでしょうか。
行動には2つ考えられます。
1.利用
1つのスロットマシーンを回し続ける
2.探索
別のスロットマシーンに変えて回す
利用を続けていれば、もっといい報酬を得られるスロットマシーンに気づきません。そして探索を続けていた場合いいスロットを見つけてもその価値を最大にできません。
greedyとε-greedy
そこでgreedyとε-greedyという手法があります。
greedyは今までの経験から最大報酬を見込める行動をとりますが、いい報酬を得られる手法に気づきません。
ε-greedyはεで探索し、1-εで利用をします。イプシロンは最初大きく、後半小さく設計するとうまくいきます。
多椀バンディット問題ならば前半は様々なスロットマシーンを実行し、後半はその中から報酬が多く見込まれるスロットマシーンを利用するという流れがよいです。
マルコフ決定過程
バンディット問題は報酬が即座にもらえますが、実際の問題では報酬は遅れてもらえます。
また環境も同様で行動によってバンディット問題では報酬は変化しませんが、実際の問題では変化します。
これらの問題もモデルにしたのはマルコフ決定過程(MDP:Markov Decision Process)です。
マルコフ決定過程では以下の点を考えます。
・行動によって状態が遷移し、状態ごとでとるべき行動が変化
・もし報酬がもらえた場合、後半に取った行動が良いと仮定（割引率、報酬割引和）
強化学習の学習方法
価値反復法
行動価値と状態価値の2つを考える学習方法です。
行動価値は行動価値関数Q(s,a)（状態sの時、行動aをとるとどれくらいの報酬の期待値が見込めるか）で、
状態価値は状態価値関数V(s)（今の状態sは、将来にわたってどれくらいの報酬期待値が見込めそうか）で表します。
QとVは実質同じです、なので多くの手法はQ(s,a)の考えに着目しています。
価値関数が定まれば方策も定まります。（計画的にどう動けばいいかわかる）
モンテカルロ法
ランダムに動いて得られた報酬の平均をとる手法。これによりV(s)、Q(s,a)を求めます。
ですが効率が悪いです。
ベルマン方程式
効率の良い求め方を考えます。
そこで提案されているのがベルリマン方程式、これを解くと報酬の期待値を最大化されると考えます。
Q^\pi(s,a)=r(s,a)+\gamma \sum_{s'}p(s'|s,a)V^\pi(s')
$Q^\pi(s,a):$状態sの時、行動aをとるとどれくらい良いか
$r(s,a):$状態sの時、行動aをとったときの報酬
$\gamma:$減衰率
$\sum_{s'}p(s'|s,a)V^\pi(s'):$将来得られる報酬の総量の推定値（難しいし、わからない）
難しいのでこのままでは解けません、なので近似的に解きます。
いかに近似的に解く手法を紹介します。
SARSA(State Action Reward State Action)
方策を考慮した方法。
どの行動をとるかはε-greedy法で決めます。
Q(s,a)←Q(s,a)+\alpha(R(s,a)+ \gamma Q(s',a')-Q(s,a))
左辺の$Q(s,a):$状態sの時、行動aをとるとどれくらい良いか
右辺の$Q(s,a):$今見込まれるQ値
$\alpha:$減衰率
$R(s,a)+ \gamma Q(s',a'):$実際に行動したときの報酬
Q(s',a')は方策に影響されます。
予想を上回る報酬が手に入ったらQ(s,a)を増やし、下回る報酬が手に入ったらQ(s,a)を減らします、学習を繰り返すと報酬の予測値が実際の値に近くなります。
Q学習
方策を考慮しない（方策off）手法です。
Q(s,a)←Q(s,a)+\alpha(R(s,a)+ \gamma max_{a'}E[Q(s',a')]-Q(s,a))
Q値を最大にするよう式を更新します。
Q学習の方がプログラムの並列化ができるのでこちらのほうが多く用いられています。
ですが、s,a,Q(s,a)の情報が多く、情報が保持できません。
そこでNNを用いてs,aからQ(s,a)を出力する仕組みを作り、強化学習が発展しました。
方策勾配法
方策を直接求める手法。
行動aを直接状態sから求めればいいじゃんってお話。
この手法によるメリットは
・V,Qが不要なので膨大なメモリが不要
・行動が連続空間でも問題なし
・状態にマルコフ仮定を使わなくてよい
デメリットは
・のちに紹介するExperienceReplayが使えないので学習が難しい
・収束の保証なし
Actor Critic
方策勾配法が一番最初に使われた手法。
A3C
報酬は独立ではないうえ、何度も試行しないといけないので学習は難しいです。
そこでA3CはActor Criticを膨大にして並列処理できるようにしたもの。
メインサーバーがモデルを持っていて、子のサーバー(worker)にネットワークを配り計算します。
workerは勾配を計算し、勾配を中央のネットワークに渡して、中央のネットワークが学習する仕組みです。
方策がオンでもオフでもどちらでも使え、workerが独立なので多様性が期待できます。
APE-X
A3Cと違い、workerにExperience Replayで使うサンプルを送ります。
データ量が少なくなるため転送コストの問題を緩和できました。
AlphaGo
学習が難しい問題を以下の手法で解決しました。
・バッチ正則化を使う
・ResNetを使う
・L2正則化を使う
・πとVを1つのネットワークで表現
・πは交差エントロピー、Vは平均二乗誤差(MSE)とし、和を損失関数とする。
モンテカルロ木探索(MCTS)がベースにした手法で、MCTSの効率を上げるため2つのネットワーク
・現在の盤面から勝率を推定(Value Network)
・現在の盤面から一番良い手を推定(Policy Network)
を使っています。
モンテカルロ木探索
ランダムにゲームが終了するまで（プレイアウト）手を打って勝率を計算し、良さそうな手を考える手法。
Experience Replay
状態行動報酬をすべて保存し、そこからランダムサンプリングして利用する手法です。
強化学習のデータは時系列データが多く、データに強い相関があり、過学習の要因になります。
なのでデータを独立させる必要があります。
ゲームでいうとステージを最初からプレイするのではなく、ランダムにプレイするイメージです。
ただ
方策オフの手法（方策オンだと自身の方策によって行動が変わるので計算の順番が変えられないため）
RNNには使えない（計算の順番が変えられないため）
メモリを食う
といった問題点があります。
報酬クリッピング
昔は報酬の設計に重点が置かれていましたが、学習の阻害になるらしく、シンプルに設計した方がいいじゃんという話。
強化学習のテクニック集
Fixed Target
重みの更新をミニバッチの学習が終わったときに行う手法。
Q値は教師データの役割を持っているので重みを更新すると教師データが変化してしまいます。
なので教師データが変化しないよう手を施した手法です。
Double DQN
状態価値ネットワークと行動選択ネットワークを分ける手法。
Q値の計算時にmax関数が含まれているので値が上振れします、その対策です。
Distibutional RL
報酬を分布として扱う手法。
Noisy Net
ネットワークにノイズを載せる手法
Montezuma's Revenge
強化学習で学習できなくてエンジニアが頭を抱えたゲーム。
主人公が弱すぎて報酬が得られなくてエージェントが動かなくなってしまいました。
内発的報酬
好奇心を取り込んだ学習方法。
今まで経験したことがない経験をすると報酬を得られるようにするとエージェントが動くようになりました。
Go-Explore
現時点で最強の学習方法。人間越えしました。