#概要
強化学習理論の基礎3の続きです。
4の範囲は、学習とプランニングの統合(Model-FreeとModel-Basedの統合)についてです。
5はこちら。

1ではDPを例にModel-Basedなアルゴリズムについて学び、2~3ではModel-Freeのアルゴリズムについて学習しました。
今回は、取得したサンプルからモデル※1を学習(Learning)し、学習したモデルを使ってプランニング(Planning※2)するアルゴリズムを見ていきます。

※1：大まかにいうと、各状態のから状態への遷移についての情報と、どの状態が最終的にどのくらいの報酬に繋がるかという情報のことです。ここでモデルはMDPを想定しています。

※2：Planningの訳し方がわからなかったのですが、こんな感じのイメージだと思っています。
「予測したモデルから各状態やアクションによって何が起きるかを推測し、最適な価値関数や方策を予想すること」

#Model-Based Reinforcement Learning
Model-Free RLでは、Modelを与えられたり学習するということはせず、経験(サンプル)から最適な価値関数や方策を学習した。
Model-Based RLでは、Modelを経験から学習し、最適な価値関数や方策をプランニングする。
Model-Based RLは、アクションを実行して環境(本当のモデル)から経験を取得する→取得した経験を使ってモデルを学習する→学習したモデルを利用して価値関数や方策をプランニングする→プランニングした価値関数や方策によって次のアクションを決定する→...を繰り返すことで行われる。

ここでわざわざModel-Based RLを使う必要性があるかどうかという疑問が生じる。
Model-Freeのようにモデルを構築せずに、経験から直接価値関数や方策を学習した方が効率的ではないか、と感じる。
もちろんModel-BasedにもModel-Freeに比べて有用な点があるために利用されている。

まず、複雑な環境にModel-Free RLを適用するのは難しいという点である。
例としてチェスを使う。
チェスには状態が膨大に存在するが、報酬は最後に勝ったか負けたかということのみで判断されるため、ある状態ではどのくらいの勝率があって...ということの判断は難しい(=経験から直接的に価値関数を見つけることは難しい)。
チェスなどの戦略的なゲームでは、モデルはゲームのルールそのものになる。また、将来何が起こるかということが予知しにくく、将来の結果から現在の状態を逆算することが極めて困難なため、モデルを使ったプランニングによって現在の状態を知る必要がある。
これがModel-Basedの最も大きな利点である。

また、教師あり学習への手法を使ってモデルを効率的に学習できることがあげられる。教師データは、現在の状態をインプットにして遷移先の状態をアウトプットとして示すことになり、教師あり学習が簡単に適用できる。
次に、構築したモデルがどこまで実際の環境について学習できているかを示すことができる点である。新しい状態の探索において、環境のどこらへんがまだ十分に学習できていないかということを構築したモデルから知ることができるため、その部分を重点的に学習させることができる。

Model-Basedの欠点としては、誤差を生み出す要素が2つになることである。
Model-Freeでは、推測と現実の差は価値関数や方策のみであった。
しかし、Model-Basedはモデルを推測し、推測したモデルを元にして価値関数や方策を推測する。そのため、推測を使って推測することになり、誤差が大きくなる。

##モデルの学習
モデルの学習について学ぶが、その前にモデルをもう少し具体的に定義する。
まず、学習するモデル$M$をパラメータ$\eta $によって表現されたMDP($〈S,A,P,R〉$)と定義する。
ここでは、全状態$S$と全アクション$A$はすでに知っていることとする。

$M$は$〈P_\eta ,R_\eta 〉$と表すことができ、状態遷移と報酬は共に実際の環境と近似させるので、$P_\eta \approx P, R_\eta \approx R$と表せる。
これを使ってタイムステップごとの遷移先状態と即時報酬を表すと以下のようになる。

S_{t+1} \sim P_\eta(S_{t+1}|S_t, A_t) \\
R_{t+1} = R_\eta(R_{t+1}|S_t, A_t)

上の式のように、状態遷移と報酬については独立して学習する。

学習するモデル$M$が定義できたので、これをサンプル($S_1, A_1, R_2, \cdots ,S_T$)から推測する。
ここでの学習はただの教師あり学習といえる。
例えば、$S_1$と$A_1$というインプットから、$R_2$と$S_2$が導かれるように学習を進めれば良いのである。

状態$s$とアクション$a$から即時報酬$r$を得ること(決定論的)を学習するのは回帰問題、状態$s$とアクション$a$から遷移先状態$s'$を得ること(確率的)を学習するのは密度推定問題と言える。
そして、二乗誤差やKL情報量(2つの確率分布がどのくらい近いか)など誤差関数を選び、誤差が最小になるようなパラメータ$\eta $を学習する。

モデルには様々な種類があり、それぞれの問題にあったモデルを使う。
状態がそれほど多くない場合はテーブル探索モデル、線形であればfeature vectorを利用したLinear Expectation Model、Linear Gaussian Modelなどが利用できる。(他にもたくさん...)

今回は一番シンプルなテーブル探索モデルを使って学習する方法を確認する。
ここで推測モデル$M$は、状態遷移を表す$\hat{P}$、報酬を表す$\hat{R}$からなる。
状態遷移の学習では、状態$s$においてアクション$a$を取った回数をカウントし($N(s,a)$)、遷移先状態$s'$ごとに遷移回数を$N(s,a)$で割ることで、$s$で$a$を実行した場合に$s'$に遷移する確率$\hat{P}^a _{s,s'}$を求める。
報酬の学習では、状態$s$においてアクション$a$を取った回数をカウントし($N(s,a)$)、得られた報酬を合計したものを$N(s,a)$で割って平均を得ることで、$s$で$a$を実行した場合の即時報酬期待値である$\hat{R}^a _s$を求める。

\hat{P}^a _{s,s'} = \frac{1}{N(s,a)} \sum ^T _{t=1} 1(S_t,A_t,S_{t+1} = s,a,s') \\
\hat{R}^a _s = \frac{1}{N(s,a)} \sum ^T _{t=1} 1(S_t,A_t = s,a)R_t

また、タイムステップ$t$ごとに$〈S_t,A_t,R_{t+1},S_{t+1}〉$を取得し、$〈s,a,,〉$と一致するサンプルをランダムに選んで標本化する手法もある。

##プランニング
モデルの学習ができたら、次にモデルを使ってプランニングを行う。
プランニングでは、学習したモデル($M_\eta = 〈P_\eta , R_\eta 〉$)を利用して最適な価値関数や最適な方策を見つける = MDP($〈S,A,P_\eta ,R_\eta 〉$)を解く。
学習したモデルを実際の環境だと想定すると、DPと同じことをすれば良いことがわかる。
そのため、Value IterationやPolicy Iteration、探索木などのアルゴリズムを利用してプランニングを行うことができる。

ここで最もシンプルな例について考える。(Sample-Based Planning)
学習したモデル$M_\eta$からのみサンプルを取得し、それを元にプランニングを進める。
DPでは全てのケースを学習していったが、今回は実際に$M_\eta$からサンプルを取得して利用する。
例えば、次の日が晴れの確率と雨の確率が50%づつであった場合、DPではそれぞれの場合について価値関数や方策の最適化を行うが、このシンプルな例では実際の天候(晴れなら晴れの状態、雨なら雨の状態)の価値関数の最適化を行うことになる。
モデルから得られるサンプルは以下のようになる。

S_{t+1} \sim P_\eta(S_{t+1}|S_t, A_t) \\
R_{t+1} = R_\eta(R_{t+1}|S_t, A_t)

取得したサンプルをModel-Free RLのアルゴリズム(Sarsa, MC, Q学習)に適用し、学習する。

これは単なるModel-Free RLよりもずっと効率的に学習が進められる。
その理由は、すでにモデルを知っている(推定したものだが)ので、何も知らない状態で大量のサンプルから学習するよりも、より高い遷移確率や発生確率を持つ状態やアクションについて学習することができるためである。

重要なのは、実際の環境から得たサンプルはそこまで多くなくても、モデルを構築することで、プランニングの際のサンプリングの量を大きくできることである。(講義資料にABを使った例があるので参照)
これは現実の問題を考える際にとても重要となる。
コストの高い現実世界でのサンプリングを減らし、コストの低いシミュレーション上のサンプリングを増やせるということになるからである。

では、もし構築したモデルが正しくなかったらどうだろう。
もちろん、正しくないモデルから学習した価値関数や方策は正しくないものになる。
しかし、それは他のアルゴリズムも同様であり、完璧なモデルや価値関数の推測は不可能である。(強化学習全体の課題)
それでもモデルが使いものにならなかった場合、解決策は2つある。
1つ目は、構築したモデルを破棄してModel-Free RLを行う。
2つ目は、モデルの不確実性について明示的に推測する。(ベイズ理論的なアプローチ)

#Integrated Architecture
次に、Model-FreeとModel-Basedの考えを統合させてみる。
まず考慮すべきことは、環境(Real MDP)とモデル(Approximate MDP)があり、各々から経験を取得できるということである。
環境から取得した(本当の)サンプルはこのように表せる。

S' \sim P^a _{s,s'} \\
R = R^a _s

次にモデルから取得した(シミュレーション上の)サンプルはこのように表せる。

S' \sim P_\eta (S'|S,A) \\
R = R_\eta (R|S,A)

Model-Free RLでは、モデルは考慮せず、実際の環境で取得したサンプルを使って価値関数や方策を学習する。
Model-Based RL(Sample-Based Planningを使った場合)では、実際の環境で取得したサンプルを使ってモデルを学習し、モデルで取得したサンプルを使って価値関数や方策をプランニングする。
この2つを組み合わせた考えがDynaである。

##Dyna
Dynaでは、実際の環境で取得したサンプルを使ってモデルを学習し、実際の環境で取得したサンプルとモデルで取得したサンプルを使って価値関数や方策をプランニングする。
最もシンプルな例は、Dyna-Q Algorithmである。
これは単純にQ学習にDynaの要素を組み合わせただけである。
Q学習は、Model-Freeのため、実際のサンプルから直接Qテーブルの値を更新していた。
Dyna-Qでは、Q学習の1タイムステップの更新が終わった後、Qテーブルの更新に利用したサンプルを使ってModelの更新を行う。
そして、Modelの更新後に決められた数のタイムステップ内(決めておくものであり、planning stepと呼ぶ)にModelに対してサンプリングし、Qテーブルの更新を行う。
上記を繰り返すことで、モデルを学習しながら、本当のサンプルとシミュレーション上のサンプルを使ったQテーブルの更新が可能となる。
また、planning stepの数を0にすると、普通のQ学習になる。

講義資料で紹介されているが、planning stepを0に設定した場合と5に設定した場合では、圧倒的に5に設定した場合の効率が良い。50に設定した場合は5に設定した場合よりもさらに効率が良くなる。
また、途中で環境を難しくなるように変えた場合、しばらくは学習結果が上昇しないが、その後また学習が進むようになる。
途中で学習結果が上昇しないのは、構築したモデルと変更後の環境の差異が大きいため、正しく学習ができないからである。
学習効率の面で見てると、より効率的に探索と搾取を行うアルゴリズム(Dyna-Q+)が最も良い学習効率となり、Dyna-Q+はDyna-Qよりも環境が困難な方向に変化した後に再度学習が進むまでのタイムステップが短くて済む。
Dyna-Q+では、新しい状態を見つける度に報酬を上乗せするように設定することで、より探索を奨励している。
また、環境を簡単に変えた場合、Dyna-Qは学習速度が変わらないが、Dyna-Q+はすぐに簡単な方法を見つけ出しより良い効率で学習を行う。

#Simulation-Based Search
最後に、プランニングのアルゴリズムについての話に戻る。

プランニングのアルゴリズムはいくつか存在する。
1つ目は、Forward Searchである。
Forward Searchは、ランダムに全ての状態をランダムにサンプリングするのではなく、現在の状態においてその先を見据えた結果として最も良いと考えられるアクションを選択する。
まず、現在の状態から取りうるアクションと遷移先状態さらにその先のアクション...といった探索木を描く。
Forward searchでは、全てのMDPについて解く必要はなく、現在の状態から先の部分的なMDP(sub-MDP)のみ解けばよいため、効率的である。

Simulation-Based Searchは、Forward searchの考え方を、Sample-Based Planningで行う。
Forward searchのように現在の状態から先を見据え、モデルからシミュレーションによってサンプルを取得する。
ここではモデルが現実の環境か、サンプルして学習したものかは関係ない。(どちらにしろプランニングの段階では既に与えられているはず)
取得したサンプルに対してModel-Free RLのアルゴリズムを適用する。
サンプルを取得する全エピソード数を$K$、現在のエピソードの回数を$k$、現タイムステップを$t$、現在の状態を$s_t$とすると、取得できるサンプルは以下のようになる。

[s^k _t, A^k _t, R^k _{t+1}, \cdots , S^k _T]^K _{k=1} \sim M_v

これをModel-Free RLに適用する。
MCに適用した場合はMonte-Carlo search、Sarsaに適用した場合はTD searchと呼ぶ。
これ以外のModel-Free RLにももちろん適用可能である。

##Monte-Carlo Search
今回は、Monte-Carlo Searchについてより深く考察する。
まずは最もシンプルなケースを考える。
モデル$M_v$、シミュレーション方策(simulation policy)$\pi $が与えられているとする。
シミュレーション方策は、シミュレーションによるサンプリングの際にアクション選択をするための方策である。

ルート状態$s_t$において選択可能な全てのアクション$a \in A$ごとに以下を実行する。
まず、$\pi $に従って$M_v$からエピソード$K$回分のシミュレーション上でサンプルを取得する。

[s_t, a, R^k _{t+1}, S_{t+1}, A^k _{t+1}, \cdots , S^k _T]^K _{k=1} \sim M_v, \pi

次にアクション$a$ごとに、エピソードごとの合計報酬の平均を計算し、$s_t$における$a$の行動価値関数とする。(Monte-Carlo Evaluation)

Q(s_t,a) = \frac{1}{K} \sum ^K _{k=1} G_t \rightarrow ^P q_\pi (s_t,a)

全ての$a$についてのシミュレーションが終了したら、最も高い行動価値関数となった$a$を実際のアクション($a_t$)とする。

次にもっと洗練された、Monte-Carlo Tree Search(MCTS)について確認してみる。(Evaluation)
ルート状態$s_t$からシミュレーション上でサンプルを取得するのは上記のシンプルなケースと同様だが、全てのアクションをシミュレーションするのではなく、最初のアクションもシミュレーション方策$\pi $によって選択する。
そのため、得られるサンプルは以下のようになる。

[s_t, A^k _t, R^k _{t+1}, S_{t+1}, A^k _{t+1}, \cdots , S^k _T]^K _{k=1} \sim M_v, \pi

そして、サンプルを取得するにあたって訪れた状態と実施したアクションのペア(s,a)を持つ、ルート$s_t$の探索木を構築する。
そして、ペアごとに行動価値関数を更新する。

Q(s_t,a) = \frac{1}{N(s,a)} \sum ^K _{k=1} \sum ^T _{u=t} 1 (S_u, A_u = s, a)G_u \rightarrow ^P q_\pi (s,a)

更新後に、最も価値の高いアクションを選択するのは同様である。

ここで大事なのは、ルート状態でだけでなく、サンプリングした状態とアクションのペアごとの価値関数を得たため、シミュレーション方策$\pi $の更新が可能になったことである。
そこで、次に$\pi $を更新するMCTS(Simulation)について学習してみる。

探索木において行動価値関数が最大になるアクションを選択する方策をTree Policy、ランダムにアクションを選択する方策をDefault Policyと呼び、1つのシミュレーションの中でそれぞれ利用する。MCTSで更新する方策はTree Policyである。
なぜ2つ必要なのかというと、探索木は環境を完全に表しているのではなくその一部でしかないため、探索が必要になるためである。Default Policyを使って環境からサンプルを取得し(out-of-tree)、サンプルから探索木を構築し行動価値関数を更新する際にTree Policyを使う(in-tree)。

行動価値関数の更新は、evaluationと同様にMCTSなのでMonte-Carlo evaluationを利用する。
Tree Policyの更新は、行動価値関数に対してε-greedyに更新する。
上記2つの更新をシミュレーションごとに実施する。

シミュレーションによって得たサンプルにMonte-Carlo controlを適用することは変わらない。
また、最終的に最適な探索木に収束する = 現在の状態から選択すべき最適なアクションを知ることができる。($Q(s,a) \rightarrow q_* (s,a)$)
囲碁を例にした、MCTSの視覚的な動きは、講義資料または講義動画を参照。

MCTSの特徴および利点は次の通りである。
1つ目は、選択的な最良優先探索であるという点である。
これは、あるイテレーションのパスが良くないと判明した時点で、ルート状態に戻ってアクションを選択し直すということを繰り返すアルゴリズムの結果である。
2つ目に、動的に個々の状態を評価できるということが挙げられる。
DPとは違い、現在の状態を認識しているので、全ての状態とアクションについて計算する必要がなく、リソースを現在の状態以降のシミュレーションに絞ることができる。
3つ目に、サンプルを取得し学習に利用することで、次元数について配慮しなくて良くなる点がある。
2つ目に挙げたように、全ての可能性を考慮するのではなく、現在の状態から先の状態とアクションの中でより良い結果を得られるかどうかだけを考慮すればよいからである。
4つ目が、サンプルさえあれば学習ができるため、ブラックボックスなモデルに対しても適用可能であるということである。
以上より、MCTSが効率的で適用範囲の広いアルゴリズムであることがわかる。

##Temporal Difference Search
これまでMCTSについて学習したが、MCTSはあくまで広いSimulation-based searchというアルゴリズムの括りの中の1つに過ぎない。(MCをSimulation-based searchに適用し、さらに探索木を学習とプランニングのために採用した)
そのため、他のModel-Free RLのアルゴリズムをSimulation-based searchに適用することも可能である。

次は、SarsaとSimulation-based searchを組み合わせた、TD searchを学ぶ。
TDはMCと違い、bootstrappingを行うアルゴリズムであった。
MCTSでは現在の状態から先のsub-MDPに対してMC controlを適用したが、TD searchではSarsaをsub-MDPに適用する。

Model-Free RLのアルゴリズムでも確認したように、TDのほとんどの場合MCよりも学習効率が良い。
そして、TD(λ)はさらに効率が良かった。
これは、Simulation-based searchにも当てはめることができ、TD searchはMC searchよりも基本的に効率が良く、TD(λ)はさらに良くなることが多い。

TD searchの基本的なアルゴリズムはMCTSと変わらない。
現在の状態(実際の状態)$s_t$からシミュレーションを始める。
TD(TD(0))では、1つ先のタイムステップの視点から、即時報酬と次の行動価値関数を取得し、現在の状態と実施したアクションの行動価値関数$Q(s,a)$を更新する。

\Delta Q(S,A) = \alpha (R + \gamma Q(S',A') - Q(S,A))

アクション選択は、行動価値関数に対してε-greedy等を適用して決定される。
また、ここで行動価値関数$Q$に、テーブル探索ではなく、Function Approximationを導入することもできる。

TD searchは、MC searchより複雑な環境でより成果を発揮する。
例えば、ある状態が他の2つの親状態から遷移する場合、一度その状態を訪れていれば、違う親状態からその状態に遷移することを想定した場合、既に行動価値関数が更新されているため、より正確な情報を得ることができる。

##Dyna-2
最後に、Dynaの考えとSimulation-based searchを統合したアルゴリズムである、Dyna-2について学習する。
Dyna-2では、Dynaが本当の経験とシミュレーション上の経験を両方使って学習したように、2つの重みパラメータと2つのアルゴリズムによって、学習を行う。

2つのパラメータとは、Long-term memory(長期記憶)とShort-term(working) memory(短期記憶)のことである。
長期記憶は、どのエピソードにも適用可能な、一般的な知識を表す。
短期記憶は、特定のシチュエーションにのみ適用可能な知識を表す。
例えば、前に進めば進むだけ得点が増えるゲームがあったとして、基本的には前に移動すれば良いが(長期記憶)、目の前に落とし穴がある場合には、避けるために横に移動しなければならない(短期記憶)。

長期記憶は、本当の経験(実際の環境でアクションを実行していった結果)を使って、TD Learningによって更新される。
短期記憶は、シミュレーション上の経験(モデルでシミュレーションを行った結果)を使って、TD searchによって更新される。
最終的な価値関数は、長期記憶のものと短期記憶のものの合計になる。

囲碁に適用した場合、Dyna-2はTD searchやMCTSよりもずっと効率的に学習が進む。
その一方、シンプルなTD Learningは、全く学習が進まない。(グラフは講義資料参照)

#最後に
社会人になって再学習したとはいえ、数学を高校2年でやめた、強化学習独学の文系人が書いているので、間違っているところも多いと思います。
間違いを見つけた際には、私自身の学びのためにも、ご指摘いただけると大変ありがたいです。

#参考資料
An Introduction to Reinforcement Learning(訳本は出版されてますが、有料です)
http://incompleteideas.net/book/bookdraft2017nov5.pdf

Algorithms for Reinforcement Learning
https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf