あけましておめでとうございます、今年もよろしくお願いします（おじぎ）
そろそろE資格試験が来るのでじわじわ勉強していこうと思います。今回は強化学習について。
お品書き
強化学習とは
教師あり学習、教師なし学習と機械学習の学習手法がありますが、もう一つ強化学習という学習手法がありますほかの手法と比較しますと
教師あり学習：入力と出力のペアが与えられる
教師なし学習：入力だけ与えられる
強化学習：最終目標が与えられている
というかんじになっております。
強化学習はどこに用いられるのかと言いますと将棋などのゲームで用いられます。例えば囲碁で世界チャンピオンを負けさせたAlpha Goなんていうのにも強化学習が用いられます。囲碁なら「相手に勝つ」という最終目標のために学習を進めます。
強化学習に登場する3つの要素
では次に強化学習で用いられる要素を紹介します。主に3つ
エージェント
環境
報酬
があります。
エージェント
エージェントとは行動をするものを指します。囲碁ならエージェントはプレイヤー、行動は石を打つ行為を指します。
環境
環境とはエージェントが行動を起こす対象を指します。囲碁なら盤面（どこに石が打たれているか）、ルールなどが環境に含まれます。
報酬
エージェントは環境の中で報酬をもらいながら行動をします、この報酬によって次の行動が決まります。囲碁なら陣地の大きさが報酬として挙げられます。
方策
んでエージェントが行動を起こすために必要なのが方策というもの、ようするに報酬をたくさんもらうための作戦です。
探索と利用のトレードオフ
どうエージェントが行動すればよい方策が見つかり、報酬がたくさんもらえるかという話ですが探索と利用の2つがあります。
利用：これまでの知識を使って最善の手を使う。
探索：未知の行動をとったらもっといい報酬がもらえるかもしれない。
ですがこの2つはトレードオフなので利用ばっかりするといい報酬が得られない可能性がありますし、かといって探索しすぎると時間の無駄になってしまう可能性もありますし、非常に難しいところです。
ε-greedy法
そこで考えられたのがε-greedy法です。具体的には確率εで探索し、1-εで利用するというシンプルなもの。最初のうちはεの値は大きく（＝探索メイン）し、後半に進むにつれて値を小さくする（＝利用メイン）とうまくいくそうです。
強化学習の学習方法
では強化学習を進め方を見ていきます。
価値反復法
行動価値と状態価値の2つを考える学習方法です。
行動価値は行動価値関数Q(s,a)（状態sの時、行動aをとるとどれくらいの報酬の期待値が見込めるか）、
状態価値は状態価値関数V(s)（今の状態sは、将来にわたってどれくらいの報酬期待値が見込めそうか）で表します。
QとVは実質同じです、なので多くの手法はQ(s,a)に着目します。
価値関数が定まれば計画的にどう動けばいいかわかるので方策も定まります。
モンテカルロ法
ランダムに動いて得られた報酬の平均をとる手法。これによりV(s)、Q(s,a)を求めます。
ですがランダムに動くため効率が悪いです。
ベルマン方程式
モンテカルロ法でのデメリットであった効率の悪さを解決するために提案されたのがベルリマン方程式、これを解くと報酬の期待値を最大化されます。
Qπ(s,a)=r(s,a)+γ∑s′p(s′|s,a)Vπ(s′)
Qπ(s,a):状態sの時、行動aをとるとどれくらい良いか
r(s,a):状態sの時、行動aをとったときの報酬
γ:減衰率
∑s′p(s′|s,a)Vπ(s′):将来得られる報酬の総量の推定値（難しいし、わからない）
難しいのでこのままでは解けません、なので近似的に解きます。
SARSA(State Action Reward State Action)
方策を考慮した方法。
どの行動をとるかはε-greedy法で決めます。
Q(s,a)←Q(s,a)+α(R(s,a)+γQ(s′,a′)−Q(s,a))
左辺のQ(s,a):状態sの時、行動aをとるとどれくらい良いか
右辺のQ(s,a):今見込まれるQ値
α:減衰率
R(s,a)+γQ(s′,a′):実際に行動したときの報酬
Q(s',a')は方策に影響されます。
予想を上回る報酬が手に入ったらQ(s,a)を増やし、下回る報酬が手に入ったらQ(s,a)を減らしますので、学習を繰り返すと報酬の予測値が実際の値に近くなります。
Q学習
方策を考慮しない（方策off）手法です。つまりその時で最大となるように行動する学習をします。
Q(s,a)←Q(s,a)+α(R(s,a)+γ 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
これまで強化学習は学習が難しかったですが、AlphaGoでは以下の手法で解決しました。
・バッチ正則化を使う
・ResNetを使う
・L2正則化を使う
・πとVを1つのネットワークで表現
・πは交差エントロピー、Vは平均二乗誤差(MSE)とし、和を損失関数とする。
Alpha Goではモンテカルロ木探索(MCTS)がベースにした手法で、MCTSの効率を上げるため2つのネットワーク
・現在の盤面から勝率を推定(Value Network)
・現在の盤面から一番良い手を推定(Policy Network)
を使っています。
モンテカルロ木探索
ランダムにゲームが終了するまで（プレイアウト）手を打って勝率を計算し、良さそうな手を考える手法。
強化学習のテクニック集
次にE資格で出てきそうな強化学習のテクニックです。
報酬クリッピング
昔は報酬の設計に重点が置かれていましたが、学習の阻害になるらしく、シンプルに設計した方がいいらしいという話。
Fixed Target
重みの更新をミニバッチの学習が終わったときに行う手法。
Q値は教師データの役割を持っているので重みを更新すると教師データが変化してしまいますので教師データが変化しないよう手を施した手法です。
Double DQN
状態価値ネットワークと行動選択ネットワークを分ける手法。
Q値の計算時にmax関数が含まれているので値が上振れしますので対策となります。
Experience Replay
状態行動報酬をすべて保存し、そこからランダムサンプリングして利用する手法です。
強化学習のデータは時系列データが多く、データに強い相関があり、過学習の要因になります。
なのでデータを独立させる必要があります。
ゲームでいうとステージを最初からプレイするのではなく、ランダムにプレイするイメージです。
ただ
・方策オフの手法（方策オンだと自身の方策によって行動が変わるので計算の順番が変えられないため）
・RNNには使えない（計算の順番が変えられないため）
・メモリを食う
といった問題点があります。
Distibutional RL
報酬を分布として扱う手法。
Noisy Net
ネットワークにノイズを載せる手法
Montezuma's Revenge
強化学習で学習できなくてエンジニアが頭を抱えたゲーム。
主人公が弱すぎて報酬が得られなくてエージェントが動かなくなってしまいました。
内発的報酬
↑の対策で好奇心を取り込んだ学習方法。
今まで経験したことがない経験をすると報酬を得られるようにするとエージェントが動くようになりました。
Go-Explore
現時点で最強の学習方法。人間越えしました。
以上となります。長々と話しましたが参考になれば幸いです。