2017年に UC Berkeleyで開催されたDeep RL Bootcampの動画を見たのでそれをまとめていこうと思う．

強化学習とは

MDPと呼ばれる問題設定において，方策と呼ばれる行動指針を学習するアルゴリズム．

ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習の一種． Wikipediaより

教師あり学習などとの違いは，教師あり学習は学習データと教師ラベルのデータセットから相互の関係性（回帰・分類）を学習するのに対して，強化学習はエージェントと環境との相互作用によって，その時々に対する出力を学習する．

強化学習では環境からのフィードバックを前提とする．

強化学習のすみわけ

強化学習の住み分けは以下の感じ．

f:id:hayamizuy:20200131150713p:plain — 強化学習のすみわけ

Policy Optimizationから派生するPolicy GradientsとDynamic Programmingから派生するQ-Learningなどがある． Policy Optimizationの中のPolicy Gradients（方策勾配法）はDeep Learningとの組み合わせで用いられることが多い．こちらについては別の記事で触れようと思う．

今回はDynamic ProgrammingのValue IterationとPolicy Iterationについて触れる．

Markov Decision Process (MDP)

Markov Decision Process (MDP)は状態遷移が確率的に行われるようなシステムをモデル化したもの．

強化学習の枠組みはMDPをベースとして考えられることが多いのでここで理解しておく．

定義

f:id:hayamizuy:20200131155620p:plain

Sは状態の集合（ロボットのジョイント角度など）．

Aは行動の集合（各ジョイントに送るトルク）．

Tは状態遷移関数．決定的・確率的を問わない．現在の状態と行動が与えられた時に求められる次状態，またはその分布を返す関数．

Rは報酬関数．ある状態sにおいて行動aを選択し，次状態s'へと遷移した時に得られる報酬を決定する関数．

$s_0$ は初期状態．もしくは初期状態の分布

$\gamma$ はdiscount factor(割引率)．現在と比較しいてどれくらい将来の報酬を見積もるかを決定するスカラー値．利子のようなものと理解しておけば良い．

HはHorizon．どのくらい長く行動を行うかの指標．有限でも無限でも良い．

問題設定

MDPが与えられたときの最適化問題．

今回の目的は以下の通り．

MDPが与えられたとき，報酬和を最大化するような最適方策 $\pi^*$ を求める．

この問題設定を解くために，Value IterationとPolicy Iterationを考える．

Value Iteration

はじめに最適価値関数を用意する．

f:id:hayamizuy:20200201112713p:plain

これは状態 $s$ から，最適方策 $\pi$ に従って行動したときの期待割引報酬和．

これは最適な方策を取ったときの各状態の価値，すなわちその状態にいると将来的にどれくらいの価値が得られるかということを示す値ということになる．

では $s_0$ からスタートして $s_g$ に行くときの $V^*(s_0)$ はどのように表されるか？

f:id:hayamizuy:20200201112820p:plain

このように $V^*$ の再起的な式として表される．

再起的な価値関数 $V$ を求めるためにValue Iterationを用いる．これにより， $H=0$ から初めて再起的に $V*$ を求める．

$V_0^*=0, \forall s$

とすると，

f:id:hayamizuy:20200201143901p:plain

のようになる．このとき $V^*_k$ は $H=k$ のときの価値関数ということになる．

Value Iterationのアルゴリズムは以下の通り．

f:id:hayamizuy:20200201144011p:plain

毎回の $V$ の更新をValue updateやBellman update/back-upと呼んだりする．

無限回の更新によって最適な価値関数を得ることができることが証明されている．

最適価値関数を得ることができたら，MDPを解くための方策 $\pi$ を獲得したことになる.

次に，価値関数と同様に行動価値関数というものを考える．

f:id:hayamizuy:20200201145245p:plain

$V^*(s)$ では行動は最適方策に従う行動 $a$ であったが，今回は $a$ はどんな行動でも良い．

行動価値関数は状態 $s$ において行動 $a$ を選択た後に最適方策に従う行動を取った場合に，状態 $s$ において将来的にどれくらいの価値を得られるかを示す関数ということができる（ややこしい）．

価値関数と同様に行動価値関数 $Q^*(s, a)$ においてもupdateの式を考えると，

f:id:hayamizuy:20200201145301p:plain

となる．

行動価値関数[tex: Q^(s, a)]を考える理由はいくつかあるが，一つとして，価値関数のみでは最適行動を選択できないということが挙げられる．価値関数 $V$ は行動を選択した際の遷移確率を考慮していないが，行動価値関数はある状態からある行動を選択した際の価値を考えているため，この問題が発生しない．また[tex:max_a Q^(s,a)]が状態 $s$ における方策となるので，方策 $\pi$ を更新する必要がなく，行動価値関数のみを保持しておくだけで良くなる．

Value Iterationでは収束までにどれくらいのHを設定しておけば良いかが分からないため，実際に使用する場合はとりあえず大きな値（無限回）を設定しておく必要がある．

Policy Iteration

Policy Iterationは大枠はValue Iterationとほぼ同じだが，とても重要なのでちゃんと理解したい．

Value Iterationの更新方法は以下の通りだった．

f:id:hayamizuy:20200201151620p:plain

状態 $s$ において最適方策 $\pi$ に従って行動する．

Value Iterationにおいては毎回のValue updateの際に，その時々の最適方策が獲得されている必要がある．

では，方策 $\pi$ が最適でなかった場合はどうか？

例えば方策が適当に与えられており，ある状態 $s$ における方策 $\pi(s)$ がどれくらい良い方策なのかを評価したい場合，その方策に従ったときの価値関数は，

f:id:hayamizuy:20200202084901p:plain

となる．

これでその方策がどれくらい良いのかということを評価できることができるようになったので，これを更新していきたい．

Policy Iterationは方策評価と更新を行う．

１）現在の方策を $\pi_k$ としてそのときの価値関数を評価し，２）その価値関数の値をもとに次状態の価値関数が最大となるような現在の行動を方策 $\pi_{k+1}$ として更新する．

f:id:hayamizuy:20200202094207p:plain

これを $\pi_k$ と $\pi_{k+1}$ のさが限りなく小さくなるまで繰り返す．

１）の方策評価においてはValue IterationのようにValue updateを行う方法と，Policy Iterationにおける価値関数の式を線形システムとして計算する方法の２種類がある． Policy Iterationではmaxの式が外れるので線形システムとして計算できるというのが良い点．

まとめ

MDPで方策を求める方法としてValue IterationとPlicy Iterationを勉強した．

Value IterationやPolicy IterationではTやRがあらかじめ与えられている前提でMDPが解けるというものだった．

次の勉強では遷移関数や報酬関数が与えられていないときはどのように方策を求めれば良いのか，ということをまとめていく．

個人的に定義が曖昧な気がして，嫌だったので自分なりの解釈をまとめておく．

Off-policy

一般的にOff-policyは学習の過程で方策πの評価と更新を行わない． Off-policyの手法としてはQ-Learningなどが挙げられる．

Q-Learning:

状態行動列を用いて価値関数Qを更新し，任意の方策πに基づいて行動を選択する．価値関数Qの更新の際には，価値関数Qが最大となるような行動選択（グリーディ法）に基づいてQを更新する．

On-policy

On-policyはOff-policyの逆で，学習の過程で方策πの評価と更新を同時に行う．
On-policyの手法としては動的計画法やSarsa，方策勾配法が挙げられる．

動的計画法 (DP: Dynamic programming):: 状態行動列を用いて価値関数Qを更新した後，更新された価値関数Qを用いて方策πを更新する．更新された方策πに基づいて行動を選択する．
Sarsa:: 状態行動列を用いて価値関数Qを更新し，任意の方策πに基づいて行動を選択する．価値関数Qの更新の際には任意の方策πが用いられる．

方策勾配法:

状態行動列とその時に得られる報酬を用いてその行動の評価関数が最大となるように方策を直接更新する．

動的計画法と方策勾配法はわかりやすい．動的計画法は更新されたQをもとに各状態が観測された時に取るべき行動がそれぞれ選択されるし，方策勾配法も価値関数Qが最大となるように方策πを更新する．でもここで疑問．Sarsaって方策の評価と更新行ってるの？

実際にSarsaを実装してみたり，他の人のソースコードを見てみると，行動選択の関数はグリーディ法やソフトマックス法，ボルツマン選択などであることが多い．
方策更新してないじゃん（そもそも自分の方策の更新の定義が間違っているのか？）．

解釈

On-policyとOff-policyの違いは価値関数Qと"実際の"方策πが独立しているかどうかの違い．

Sarsaは方策を直接更新しない．だからQ-LearningなどのOff-policyの手法との違いはなんだ？と感じてしまっていた．ここで，QlearningとSarsaの違いについてみてみる．
QLearningもSarsaも方策にはグリーディ法やソフトマックス法，ボルツマン選択などが使用される．この点については同じ．

一方で価値関数Qの更新の時はどうだろう．
QLearningでは，グリーディ選択により決まった行動により得られた価値を利用するのに対して，Sarsaでは，実際に次の状態で選択した行動により得られた価値を利用する．

Sarsaは価値関数Qを更新する時に実際に選択された方策πにより得られる値を使用している．つまり使用する方策（グリーディ法やソフトマックス法，ボルツマン選択など）を決定するが，実際の行動選択した時の結果に依存して価値関数Qが決まる．だから間接的に価値関数Qが方策πの影響を受けることになるので，Off-policyではなくOn-policyと言える．

このことからOn-Policyの場合はタスクに応じて価値関数Qの値が大きく異なることになり，方策の再利用が難しい．

Log(haya)

備忘録ー知識の昇華

Deep RL Bootcampで強化学習の勉強 Vol. 1