強化学習

機械学習の一種である強化学習について勉強したことをまとめたノート（忘備録）です。

尚、ここで取り上げている各種強化学習手法の一部の手法の実装コードは、以下のレポジトリに保管してあります。

github.com

目次 [Contents]

1. 強化学習のモデル化
   1. エージェントと環境の相互作用
   2. 環境のマルコフ性
   3. エピソード的タスクと連続タスク
   4. マルコフ決定過程（MDP）
   5. 価値関数
   6. 状態価値関数
   7. 行動価値関数
   8. 状態価値関数と行動価値関数の関係
   9. ベルマン方程式
      1. ベルマン最適方程式とグリーディーな選択
2. 代表的な古典的強化学習手法の比較
3. 強化学習における動的計画法（DP法）
   1. 反復法による近似解
   2. 方策評価
      1. 反復方策評価
   3. 方策改善
      1. 方策改善定理
      2. 方策改善定理とグリーディー方策
      3. 方策改善のアルゴリズム
   4. 方策反復法 [policy iteration]
   5. 価値反復法 [value iteration]
   6. 一般化方策反復（GPI）
4. モンテカルロ法（MC法）
   1. 初回訪問モンテカルロ法
   2. 逐一訪問モンテカルロ法
   3. モンテカルロ-ES法
   4. 方策オン型モンテカルロ法
   5. 方策オフ型モンテカルロ法
   6. モンテカルロ法の適用例
5. TD学習（時間的差分学習）
   1. TD(0)法
   2. Sarsa（方策オン型TD制御）
   3. Q学習 [Q-learning]（方策オフ型TD制御）
   4. nステップTD法
   5. TD(λ)法
      1. TD(λ)の前方観測的な見方
      2. TD(λ)の後方観測的な見方と適格度トレース
      3. 前方観測的見方と後方観測的見方の等価性
      4. Sarsa(λ)
      5. Q(λ)
   6. アクター・クリティック手法
      1. アクタークリティック手法への適格度トレースの適用
   7. TD法の適用例
6. 関数による価値関数の近似（関数近似手法）
   1. 損失関数としての最小２乗誤差（MSE）
   2. パラメータの更新式としての最急降下法
   3. 線形関数での価値関数の近似（線形手法）
   4. 最急降下型Sarsa（関数近似手法のSarsaへの適用）
   5. 最急降下型Q学習（関数近似手法のQ学習への適用）
7. 方策勾配に基づく強化学習手法
   1. REINFORCE
   2. 方策勾配法
   3. 方策勾配に基づく強化学習手法の適用例
8. モデルとプランニング（各種古典的強化学習の統一的見解）
   1. Dyna,Dyna-Q
9. 深層学習の構造を取り込んだ強化学習手法（深層強化学習手法）
   1. 多層パーセプトロン（MLP）による価値関数の近似
   2. Neural Fitted Q Iteration（MLPによる関数近似で学習を安定化させるための工夫）
   3. Deep Q Network（DQN）
      1. DQNの適用例
   4. Double-DQN（DDQN）
      1. DDQNの適用例
   5. Prioritized Experience Replay（優先順位付き経験再生）
      1. Prioritized Experience Replayの適用例
   6. Dueling Network
      1. Dueling Network の適用例
   7. GORILA [General Reinforcement Learning Architecture]
   8. A3C [Asynchronous Advantage Actor-Critic]
   9. A2C [Advantage Actor-Critic]
   10. UNREAL [UNsupervised REinforcement and Auxiliary Learning]
   11. TRPO [trust region policy optimization]
   12. PPO [proximal policy optimization]
   13. GAE [generalized advantage estimator]
10. 補足事項
    1. 【外部リンク】機械学習
    2. 【外部リンク】ニューラルネットワーク / ディープラーニング
       1. 【外部リンク】パーセプトロン
       2. 【外部リンク】畳み込みニューラルネットワーク(CNN)
    3. 【外部リンク】グラフ理論
       1. 【補足（外部リンク）】確率過程とマルコフ連鎖
11. 参考サイトと参考文献

---

■ 強化学習のモデル化

◎ エージェントと環境の相互作用

上図は、強化学習で取り扱うシステムを図示したものである。
このシステムは、以下のように、エージェントと環境との相互作用でモデル化される。

• エージェントとは、意思決定と学習（※将来に渡る収益の期待値を最大化するような学習）を行う行動主体である。
  
• 環境とは、エージェントが相互作用を行う対象であり、エージェントの行動 a を反映した上で、エージェントに対して、状態 s と、その状態での報酬 r を与える。
  

• エージェントの行動 a は、確率分布で表現される行動方策 [policy] に基づいて選択される。
  ここで、 は、 ならば となる確率を表す。
  

• エージェントと環境は、継続的に相互作用を行う。
  より詳細には、離散時間 t=0,1,2,... の各々の時間 t おいて、相互作用を行う。
  

• エージェントがその意思決定目的とする収益は、時間経過 t=0,1,2,.. での時間経過によって、その値が減衰するものとする。
  つまり、時間 t 時点から見て、将来 t+1,t+2,... にわたっての報酬 r の差し引きを考慮した割引収益
  
  で考える。
  ※ 割引収益で考えるのは、同じ収益値ならば、将来受け取るよりも現時点で受け取るほうがよい値であることの妥当性もあるが、別の理由として、終端状態の存在しない連続タスクにおいて、割引なしの場合の将来にわたっての収益の和が、t→∞ の時間経過により、無限大に発散してしまい、エージェントの目的である将来にわたっての収益の最大化が、数学的に取り扱いずらい問題になってしまうことを防ぐという理由もある。
  

• そして、エージェントは、時間経過 t=0,1,2,.. での相互作用によって、この将来にわたっての割引収益 の期待値 E[R] を最大化するように、自身の行動方策 を学習しながら、行動する。
  ※ 一般的に、強化学習の枠組みにおいて、時間に依存する行動方策 ではなく、時間 t によらない定常方策 が用いられる。
  （価値関数の満たすべき方程式を与えるベルマンの方程式は、定常方策 を前提とした方程式となっている。）
  

• ここで、エージェントと環境の相互作用の順序は、以下のようになる。
  ① エージェントは、環境から状態を受け取る。（＝エージェントの状態がになる。）
  ② エージェントは、現在の状態に基づき、行動方策 に従って、行動を選択する。
  ③ 時間が１ステップ t→t+1 経過後に、エージェントは、エージェントの行動の結果として、報酬 を受取る。
  ※ 時間 t で環境が受け取った行動による即時報酬という意味で、ではなく を用いる。
  ※ つまり、状態は行動を選択するための判断材料となり、報酬はその行動を評価するための判断材料となる。
  

• 尚、強化学習の文脈において、エージェントと環境との相互作用の一連の時系列単位を、エピソード [Episode] という。
  このエピソードは、エージェントの初期状態から始まって、環境との相互作用により終端状態まで移行するまでのの過程を、１回のエピソードとして扱う。
  例えば、迷路探索問題においては、エージェントが、迷路のスタート地点からゴールまで辿りつくまでの一連の過程が、１回のエピソードになる。
  強化学習による学習（＝行動方策の学習や価値関数の学習など）では、１回のエピソード内の各時間ステップ t→t+1 度に学習を行う手法（例えば、価値反復法などの動的計画法やTD法）もあれば、１回のエピソードが完了する毎に学習を行う手法（例えば、モンテカルロ法）も存在するので、エピソードと時間ステップを明確に区別しておく必要がある。
  

【Memo】　エージェントと環境の境界線はどのように設定すべきか？
このようにモデル化される強化学習のシステムにおいて、実際上のタスクでは、どのようにエージェントと環境との線引を行えばよいのか？という問題は残る。
これは例えば、ロボット制御タスクにおいては、ロボットを構成するモーターやセンサーなどの物理的デバイスは、その内部の電子回路など自体は、エージェントであるロボット自身からは直接制御できるないので、エージェントの一部というよりも、むしろ環境の一部とみなしたほうが適切であるのでは？と考えられる。
同様の例として、人体制御タスクにおいては、人体を構成する筋肉や骨格や感覚器などは、エージェントの一部というよりも、むしろ環境の一部とみなしたほうが適切であるのでは？と考えられる。
この問題の一般的な基準を与える回答としては、エージェントが任意に変更出来ないものは、エージェントの外部にあると考え、それらを環境とみなすという解決策が考えられる。

このエージェントと環境の相互作用を、時間や相互作用の順序を含まて考える場合においては、以下のようなバックアップ線図で表現したほうがわかりやすい。
例えば、以下の図は、マス目上に仕切られた迷路探索問題（移動方向が上下左右の４方向）における、バックアップ線図である。
但し、この問題では、状態遷移関数 が確率１で決定論的に定まるために、状態遷移関数による分岐が存在しないことに注意（青線部分）。

より一般的には、以下のバックアップ線図のように、状態遷移関数 による分岐が存在する。

尚、バックアップ線図を用いての詳細な議論は、後述の価値関数～ベルマンの方程式で議論する。
※ バックアップ線図という名前は、価値関数の満たすべき方程式を記述するベルマンの方程式が、前回と今回の価値関数の値の再帰的関係（＝バックアップ）で記述されるためである。

◎ 環境のマルコフ性

強化学習で生じるエージェントと環境との相互作用の過程（＝確率過程となる）において、時間 t で状態にあるエージェントによって選択された行動に対して、次の時間 t+1 において環境がどのように応答するのかという問題を考える。

この問題の最も一般的なモデル化では、以前に生じた全ての事象 に依存した条件付き同時確率分布でモデル化する。
即ち、

しかしながら、最も一般的なモデルでは、過去の全ての事象に依存するために、問題設定や計算が複雑になるという問題が存在する。従って、強化学習のモデル化においては、一般的に、環境に対してマルコフ性の性質を仮定する。

ここで、このマルコフ性とは、「ある状態から、別の状態 に移行する確率が、それ以前の経路 t によらず、現在の状態のみで決まる。」という性質である。
今の場合、環境に対してマルコフ性の性質を仮定するので、（環境がエージェントに与える）状態 s と報酬 r が対象となる。式で書くと、

である。

このように環境がマルコフ性の性質を満たすとき、現在の状態と行動さえ与えられてば、１ステップ t→t+1 間での環境による遷移確率 から、次のステップ t+1 での状態 と行動 を予測することが出来るので、これらの反復処理を逐次繰り返すことにより、過去の全ての履歴が与えられた場合と同様にして、将来における状態と行動を予測できる構造が織り込まれていることになる。（それ故に、マルコフ性の条件が重要である。）
式で書くと、

である。

◎ マルコフ決定過程（MDP）

先に見たように、強化学習は、エージェント環境が各時間ステップ t=0,1,2,... で継続的に相互作用するシステムにおいて、エージェントが目標を示す数値である割引収益を最大化するように行動方策を学習制御するような過程 であって、更に、環境に対してマルコフ性の性質を仮定してモデル化された。

このようなモデルは、マルコフ決定過程 [MDP:Markov decision process] の枠組みで厳密にモデル化出来る。 このマルコフ決定過程は、マルコフ性とエルゴード性を持つ確率過程であって、選択可能な行動、及び、報酬を追加したものである。
言い換えると、マルコフ決定過程は、マルコフ連鎖に対して、選択可能な行動、及び、報酬を追加したものである。

• エルゴード性（定常性）：
  任意の初期状態からスタートした確率過程が、無限時間経過後には、最初の状態とは無関係になる性質。
  マルコフ連鎖は、このエルゴード性の性質も合わせ持つ。
  

このマルコフ決定過程による過程は、以下の遷移グラフで図示するとわかりやすい。
但し、この遷移グラフでは、行動方策による行動の選択の分岐は表現できていないことと、時間ステップ t に対する のダイナミクス は表現していないこと注意。（添字の位置に注意）

時間ステップによるダイナミクス、行動方策による行動の選択の分岐と、遷移確率による状態の遷移の分岐を含めて表現するには、以下のバックアップ線図で図示するとわかりやすい。

• 【参考サイト】
  
  • マルコフ決定過程 - Wikipedia
    

◎ 価値関数

先に述べたように、強化学習をマルコフ決定過程でモデル化するにあたって、エージェントの目的は、自身の行動則 π により目的関数である将来に渡っての割引収益（収益の総和）

の期待値を最大化することであったが、一般的に、強化学習のモデル化においては、この行動方策として、特に定常方策の場合を考え、この定常方策に従った場合に得られる収益の期待値である価値関数の概念を導入する。

ここで、価値関数には、以下のように、状態 s における価値を表す状態価値関数と、状態 s で行動 a を選択した場合の価値を表す行動価値関数が存在する。

• 状態価値関数：
  状態 s で現在の行動方策 に従いつづけた（＝定常方策）ときに得られる価値。
  

• 行動価値関数：
  状態 s で行動 a を選択し、その後は既存の行動方策 に従いつづけた（＝定常方策）ときに得られる価値。
  

• 【参照サイト】
  
  • 今さら聞けない強化学習（1）：状態価値関数とBellman方程式 - Qiita
    
  • 今さら聞けない強化学習（3）：行動価値関数とBellman方程式 - Qiita
    
  • 人工知能概論 第6回 多段決定(2) 強化学習.
    

◎ 状態価値関数

以下の図は、バックアップ線図に状態価値関数 を記した図である。

このバックアップ図より、状態価値関数の定義にある将来に対する割引収益の期待値 は、青枠内での（将来における）報酬 r の平均をとったものになっていることが分かる。

更に、この将来の割引総和に関しての期待値は、上図から分かるように、行動方策での分岐（赤線）の和の部分 と遷移関数での分岐（青線）の和の部分 で各々平均値をとったものに対応しているので、以下の関係が成り立つことが分かる。

尚、この関係式を上図のバックアップ線図から直感的にではなく、式変形で示すと以下のようになる。

ここで、この関係式は、状態価値関数に関しての方程式になっており、（状態価値関数に対しての）ベルマンの方程式という。
そして、このベルマンの方程式は不動点方程式であるので、この方程式を解けば、原理的には不動点としての状態価値関数の最適解が一意に存在することになる（詳細は後述）

◎ 行動価値関数

以下の図は、バックアップ線図に状態価値関数 を記した図である。

このバックアップ線図より、状態行動関数の定義にある割引収益の期待値 は、青枠内での報酬 r の平均をとったものになっていることが分かる。

◎ 状態価値関数と行動価値関数の関係

価値関数には、状態価値関数と行動価値関数の２つが存在するが、これら２つの関数は、互いに結びつく。
このことをバックアップ線図を元に見ていく。

以下の図は、バックアップ線図に状態価値関数 と行動価値関数 とを記した図である。

このバックアップ線図から、以下のような関係が成り立つことが分かる。

→ 将来の期待利得である状態価値関数 は、（現在の期待利得である）行動価値関数 に対して、行動方策に関しての分岐（赤枠部分）で和をとった形で表現できる。

以上の関係式をまとめると、以下のようになる。

• （証明略）バックアップ線図より成り立つことが分かる。
  

◎ ベルマン方程式

次の問題は、これら最適価値関数 , を如何にして求めるかということである。
最適価値関数 , は、以下のベルマン方程式と呼ばれる、最適解に関しての不動点方程式から求めることが原理的には可能となる。
※ ”原理的には可能” と表現したのは、ベルマン方程式が最適価値関数に関しての不動点方程式となっており、収束先の不動点としての最適解を持つことが保証されるが、実際上この方程式を直接解くことは困難であり、代わりに動的計画法（価値反復、方策反復など）の手法で近似解を得るようにすることが多いため。

まずは、最適価値関数のうち、最適状態価値関数 に対してのベルマン方程式を考える。

• （証明略）先の「状態価値関数」の項目を参照
  

• （証明略）先の「状態価値関数」の項目を参照
  

同様にして、最適行動価値関数 に対してもベルマン方程式が成り立ち、この不動点方程式の収束解（＝不動点）としての最適行動価値関数の値の存在性が保証される。

• （証明略）先の「状態価値関数と行動価値関数の関係」の項目を参照
  

☆ ベルマン最適方程式とグリーディーな選択

一般的に、コンピューターサイエンスの分野におけるグリーディーの意味とは、「長期的・大域的には、より良い代替案・最適解を見つかる可能性を考慮せずに、短期的・局所的な情報の中でのみ、代替案・最適解を見つけるような検索方針・意思決定手続き」のこのとを指す。

今考えている、最適価値関数 は、ベルマン最適方程式

の解として与られるが、この２つの方程式は、いずれも、１ステップ間 での短期的なグリーディーな選択 を取りさえすれば、１エピーソード間の長期的な意味でも最適解に到達できることを意味している。
言い換れば、１ステップ間でのその時点での短期的で局所的なグリーディーな選択さえ続けていれば、エピーソード間での大域的最適解が得られることを意味している。

これは、価値関数は、”将来”に対して報酬の期待値として定義しているために、将来の全ての可能な挙動がもららす報酬が、既に考慮されていることに起因する。

■ 代表的な古典的強化学習手法の比較

ここでは、代表的な古典的強化学習アルゴリズムである、

• 動的計画法（価値反復法、方策反復法など）
• モンテカルロ法
• TD学習（Sarsa、Q学習など）
• 関数近似手法

などの各種古典的強化学習手法を、統一的観点から、互いの特徴を比較する。

以下の表は、各種古典的強化学習手法（横軸）を、いくつかの代表的な特徴軸（縦軸）で比較した表である。

■ 強化学習における動的計画法（DP法）

先のベルマンの方程式

が示す重要な性質は、「ある状態や行動の価値 , は、その後の状態や行動の価値 , を用いて表すことが出来る。」という、ブートストラップ性の性質である。
（※機械学習で用られるデータ分割手法の１つであるブートストラップ法と異なるものであることに注意）

このような価値関数のブートストラップ性を利用して、価値関数を反復的に枝分かれをたどりながら逐次計算していく手法を総称して、動的計画法という。

そして、このブーストラップ性の性質をバックアップ線図で書いたものが、以下のような動的計画法のバックアップ線図になる。

※ この動的計画法で計算可能になるためには、ベルマンの方程式に出てくる状態遷移関数 が既知であることが条件になる。言い換えると、動的計画法による強化学習手法は、環境のモデルを共にした手法で、モデルベースの強化学習手法である。

※ これに対して、環境のダイナミクスが既知でなくとも有効な価値関数の計算手法として、モンテカルロ法やTD法などの、モデルフリーの強化学習手法がある。（詳細は、後述）

ここで、このベルマンの方程式は、価値関数に対しての不動点方程式にもなっており、この不動点方程式が導く不動点としての最適価値関数の存在の一意性は、価値反復法 [value iteration] や方策反復法 [policy iteration] などの動的計画法のアルゴリズムで、最適解が得られることの根拠となる。

◎ 反復法による近似解

方策評価をする（＝ベルマン方程式を解く）にあたっては、厳密な解法では、ベルマン方程式を、状態集合 S 個の未知変数 s∈S を持つ、S 個の連立一次方程式とみなし、これを解くことになるが、この厳密な解法では、一般的に計算量が膨大となり、現実的でない。
そこで、反復法による近似解を用いる。

反復法は、ベルマンの方程式を満たす価値関数、及びそのときの最適行動方策を、ベルマンの方程式の式にそのままに従って再帰的に総当たり計算するのではなく、今の状態と次の状態の２層間のみの繰り返し計算により近似的に求める動的計画法の一種である。
より詳細には、
- 今の状態 s と次の状態 s' の２層間のみでの計算を、k=0,1,2,... で更新しながら反復する。
- 最適解に近づくまで、この更新処理 k=0,1,2,... を続ける。
- 得られた最適解の近似から、最適行動方針を算出する。
というのが基本的なアイデアである。

反復法には、それぞれ価値反復法と方策反復法が存在するが、両者の違いは、行動選択における以下のような方向性に違いとなる。

• Policyベース：
  行動方策 π により、行動選択が行われる。
  方策反復法は、このPolicy ベースな反復法になっている。
  

• Value ベース：
  価値関数を最大化するような行動選択を行う。
  （＝））
  価値反復法は、このValueベースな反復法となっている。
  

• 【参考サイト】
  
  • 今さら聞けない強化学習（5）：状態価値関数近似と方策評価
    

◎ 方策評価

状態価値関数 は、状態 s において、定常方策 に従いつづけた際の価値を表している。
従って、任意の定常方策 に対する、状態価値関数 を求めることは、ある定常方策の評価指数となりうる価値を求めて、方策を評価していることになるので、（動的計画法の文脈では）”方策評価” という。

状態価値関数についてのベルマン方程式

は、ある行動方策 π のもとでの、状態価値関数を解としているので、ベルマン方程式を解くことは、方策評価となる。

☆ 反復方策評価

上図のように、状態価値関数に対してのベルマン方程式を、更新規則とした更新式

から生成される近似列 を考える。
すると、この近似列 は、k → ∞の極限で、 に収束することが知られている（証明略）。
このアルゴリズムは、ベルマン方程式を繰り返し解くこと、即ち、方策評価を繰り返し行い、価値関数を近似しているので、反復方策評価という。

ここで、この反復方策評価のアルゴリズムには、以下のような特徴が存在する。

• スイープ操作と完全バックアップ
  一般的に、現在評価している行動方策 π の元で、実現可能な全ての１ステップ遷移（＝時間ステップ t→t+1 での遷移）に対して、バックアップ処理（＝時間ステップでの遷移後から遷移前の逆方向への更新処理）を行うことを完全バックアップという。
  今の反復方策評価では、全ての可能な状態 を sweep 操作しながら、１ステップ遷移 毎に、１度ずつバックアップ処理（ ）を行っているので、完全バックアップ処理を行っていることになる。（下図の迷路探索問題の例を参照）
  
  cf : サンプルバックアップ
  
  
• その場更新型のコード実装
  反復方策評価で取り扱うインデックス k に対する更新式（＝逐次近似式）
  
  をコード実装する際に、
  単純に考えると、新しい価値関数の配列 と元の配列 の２つの配列を確保し、それらを逐次更新していく実装が考えられるが、
  別の実装方法として、価値関数の配列を１つだけ確保し、その時点 k での新しい価値関数 を、古い価値関数 に直接上書きする実装方法も考えられる。
  後者の方法では、新しいデータをすぐに利用するので、２つの配列を用いる方法よりも、通常は速く収束するというメリットが存在する。
  

以上の事項をアルゴリズムとしてまとめると、以下のようになる。

◎ 方策改善

従来の行動方策から、別の新しい行動方策に変更することで、得られる価値がより良くなるのかを？という方策改善の問題を考える。
この方策改善は、
① 状態 s において、従来の行動方策 π に従いつづけた際の価値である状態価値関数 と、
② 状態 s から、新しい行動方策 π' に従って、一度だけ行動 a を選択して、その後は従来行動方策 π に従いつづけた際の価値である行動価値関数
という２つの値との大小比較

から、計量的に取り扱うことが出来る。

• 【参考サイト】
  
  • 今さら聞けない強化学習（6）：反復法による最適方策
    

☆ 方策改善定理

このことを一般的に述べたものが、以下の方策改善定理と呼ばれるものになる。

• （証明）
  状態価値関数と行動価値関数の関係より、
  
  の関係が成り立つので、以下のような時間ステップ t に関しての漸化式が成り立つ。
  
  従って、 の関係が成り立つので、定理が成り立つことが分かる。
  

☆ 方策改善定理とグリーディー方策

ここで、以下のように定義される新しい行動方策としてのグリーディー方策

は、方策改善定理にある新たな方策 π′ の条件 を満たし、方策改善になっている。（証明略）
つまり、１ステップ間 t→t+1 で、グリーディー方策で行動を選択することで、方策が改善されていくことが保証される。

☆ 方策改善のアルゴリズム

このグリーディー方策による方策改善をアルゴリズムとしてまとめると、以下のようになる。

◎ 方策反復法 [policy iteration]

先にみた方策評価と方策改善のプロセスを繰り返すことで、方策と価値価値関数を次々と更新し、最終的には、最適行動方策と最適価値関数に収束させるようなアルゴリズムであって、行動選択を行動方策に基づきて行う Policyベースののアルゴリズムを、方策反復法という。

• 【参考サイト】
  
  • 強化学習について学んでみた。（その12）
    

◎ 価値反復法 [value iteration]

先に見てきた方策反復法では、そのアルゴリズム中に含まれる方策評価のプロセスにおいて、全ての状態に対してのスイープ操作による完全バックアップ処理を行うために、方策改善のプロセスの段階に移行するまで時間がかかるという欠点が存在する。

そこで、価値反復法と呼ばれるアルゴリズムでは、最適解への収束性を失うことなく、１回のスイープ操作度に、方策改善を行うようにして、方策反復法よりも速く方策改善が行えるようにしている。

更に、価値反復法では、状態価値関数の推定値 V(s) の更新式として

というベルマン最適方程式に準じた形の更新式を利用することで、 価値関数を最大化するように行動選択を行うという、Valueベースの手法となっている。

この更新式は、先のPolicyベースな方策反復法での、状態価値関数の更新式

と比較すると、
価値反復法では、行動方策に関しての全ての分岐 の情報に従って更新を行うのではなくて、グリーディーな行動選択 に従って、更新を行っていることになるので、
分岐の総和をとる方策反復法に比べて、グリーディーで max のみを選択するために、１ステップあたりの計算量は、価値反復法に比べて減少するというメリットが存在する。

以上のことをアルゴリズムとしてまとめると、以下のようになる。

• 【参考サイト】
  
  • 強化学習について学んでみた。（その13）
    

◎ 一般化方策反復（GPI）

一般化方策反復（GPI）とは、これまで見てきた様々な強化学習手法でなぜ最適解が得られるのかを、共通の枠組みで解釈するための考え方・概念のことである。（※アルゴリズムではないことに注意）

これまで見てきた強化学習手法では、
例えば、方策反復法では、方策評価のループが完了→方策改善に移行。
価値反復法では、１回の方策評価→１回の方策改善に移行。
といったように、方策評価のプロセスと方策改善のプロセスにおいて、その粒度の違いは存在するものの、方策評価と方策改善の２つのプロセスの相互作用で、最適解に収束させていくアルゴリズムであった。

一般化方策反復（GPI）では、このような強化学習手法に共通する、方策評価と方策改善の２つのプロセスの相互作用による最適解への収束過程を、一般的概念（共通概念）として扱う。
これにより、ほとんど全ての強化学習手法は、（明確な方策と価値関数、及びそれによる方策評価、方策改善プロセスを持つために、）この一般化方策反復の枠組みで、定性的に解釈することが出来る。

• 安定性：
  一般化方策反復の枠組みでの安定性とは、方策評価と方策改善のプロセスにおいて、これ以上変化が生じず、価値関数と方策が共に最適になっていることを意味している。
  ここで、価値関数が安定になるのは、現在の方策との ”整合性” が取れている場合である。
  又、方策が安定になるのは、行動方策が、現在の価値関数に対してのグリーディ方策になっている場合のみである。
  

■ モンテカルロ法による価値推定、方策評価と方策改善

モンテカルロ法とは、数値計算やシミュレーションなどにおいて、ランダムな乱数をサンプリングすることで数値計算（例えば、積分計算など）を行う手法の総称であるが、今考えているマルコフ決定過程における価値関数の推定問題、方策評価と方策改善問題にも応用出来る。

先に見たように、動的計画法と呼ばれる、マルコフ決定過程でモデル化された環境における価値関数のブートストラップ性を利用して、反復的に枝分かを辿りながら価値関数を計算していく手法は、モデルベースの強化学習手法であり、ベルマンの方程式に出てくる状態遷移関数 が既知でなくてはならないという問題があった。

これに対して、モンテカルロ法による価値関数の推定法では、ブートストラップ性を利用せず、（マルコフ決定過程でモデル化された環境ではなく）実際の環境が繰り返し生成するエピソードの系列（＝サンプル）を利用して、経験的に価値関数を推定するため、この状態遷移関数が既知でなくてもよいというメリットが存在する。（＝モデルフリーの強化学習手法）
※ 但し、状態遷移関数が既知でなくてもよいのは、状態価値関数ではなく行動価値関数を推定するアルゴリズムに限定される。（詳細は後述）
※ モンテカルロ法では、エピソードの系列全体を利用するので、エピソードの完了を待ってから方策評価・方策改善を行う必要がある。
※ 又、収益の分散が大きい場合、モンテカルロ法による価値関数の推定は、信頼度が低くなってしまうという問題がある。

下図は、動的計画法とモンテカルロ法による手法の違いを示したバックアップ線図である。

動的計画法の各種手法は、マルコフ決定過程でモデル化した環境が、ベルマン方程式を満たすこと、更に、ベルマン方程式のブーストラップ性により、動的計画法の各種手法のバックアップ線図は、現在の状態行動対 (s,a)∈S×A →次回の状態行動対 (s′,a′)∈S×A で可能な遷移経路全てで分岐していた。

一方、モンテカルロ法では、（モデル化された環境ではなくて）実際の環境上で、１つのエピソードが繰り返し試行され、経験的に１つの経路が繰り返し試行されるだけなので、モンテカルロ法のバックアップ線図は、上図の太線部分で示された１つのエピソードの開始から終端までの１つのサンプリングされた経路となる。

ここで、状態価値関数は、

のように期待利得に関する期待値で定義されるものであったことを考えると、モンテカルロ法で価値推定を行う場合には、実際の環境が生成するエピソードの系列に従って状態を訪問した後に観測した収益を平均化すれば良いことが分かる。
そうすることで、より多くの訪問回数を重ねるにつれて、平均値が期待値に収束するようになる。

• 【参考サイト】
  
  • 今さら聞けない強化学習（7）：モンテカルロ法で価値推定
    
  • 強化学習について学んでみた。（その14）
    
  • 強化学習について学んでみた。（その16）
    

◎ 初回訪問モンテカルロ法による価値推定

初回訪問モンテカルロ法は、あるエピソードにおいて、状態 s への初回訪問の結果で発生した収益のみを平均値するアルゴリズムで、以下のようになる。
※ このアルゴリズムは、状態価値関数の推定を行っているだけで、方策評価と方策改善は行っていないことに注意。

◎ 逐一訪問モンテカルロ法による価値推定

逐一訪問モンテカルロ法は、エピソード群全体での、状態 s への全ての訪問後に発生した収益に対して、平均化処理を行い、その平均値で状態価値関数の推定を行う。
※ このアルゴリズムは、状態価値関数の推定を行っているだけで、方策評価と方策改善は行っていないことに注意。

◎ モンテカルロ-ES法

モンテカルロ法による価値推定、方策評価が有効であるためには、以下のような事項を考慮する必要がある。
そして、これらの事項を考慮したモンテカルロ法を、モンテカルロ-ES法 [ES:Exploring Starts] という。

• 状態価値関数ではなく行動価値関数で方策評価：
  状態遷移関数 が与えられていて、モデルのダイナミクスが明確なときは、
  
  の関係式に従って、算出した状態価値関数の推定値 V(s) から、行動方策 π を算出することが出来る。
  逆に、状態遷移関数 が不明で、モデルのダイナミクスが不明なときは、この関係式に従って、状態価値関数の推定値 V(s) から、行動方策 π を算出することが出来ないので、状態価値関数ではなくて行動価値関数を推定値 Q(s,a) を算出し、そこから
  
  の関係式に従って、行動方策を算出する必要がある。
  モンテカルロ法のメリットの１つは、先に述べたようにモデルのダイナミクスが不明であっても、価値推定が行えることにあるので、このメリットを享受するためには、状態価値関数ではなく、行動価値関数で方策評価する必要がある。
  

• 到達されない状態行動対と開始点検索の仮定：
  モンテカルロ法では、シミュレーションに従って経験的にエピソードの試行を行うが、行動方策が確率１の決定論的な行動方策であった場合、或いは、ほとんど決定論的な行動方策であった場合、エピソードの試行回数を多くしても、モンテカルロ法のシミュレーション上で到達されない状態や行動が出てきてしない、結果として、平均化すべき収益がなくなるので、収益の平均値として算出される行動価値関数の推定値も正しく算出出来なくなるという問題が存在する。
  この問題を解決するための１つの方法として、全ての状態とそれに続く行動セット（＝状態行動対）を、エピソードの開始点に取ることが出来るという、開始点検索の仮定をおく方法が考えられる。
  これにより、無限回のエピソードの試行において、全ての状態行動対が訪問され、正しく行動価値関数の推定値が算出可能となることが保証される。
  

• 無限個のエピソードを試行する必要があることへの対応：
  モンテカルロ法による価値推定が、正しい値に収束するためには、原理的には、無限回のエピソードを試行する必要がある。
  但し、（これまで見てきた動的計画法の手法と同じように）推定値の近似値を得るという目的であれば、無限回のエピソードを試行せずとも、十分回数の多いエピソードの試行回数で近似推定値を得ることが出来る。
  或いは無限回のエピソードを試行することを避ける別の方法としては、方策評価が完了して方策改善を行う手順ではなくて、方策評価と方策改善を交互に逐次行っておく方法が考えられる。
  （例えば、動的計画法の手法の１つである価値反復法では、１回の方策評価→１回の方策改善を繰り返すアルゴリズムになっている。）
  モンテカルロ-ES法では、この方法を採用しており、１エピーソード単位で方策評価と方策改善の交互に行う。つまりは、各エピーソード完了後に、観測された収益から算出された行動価値関数の推定値で、方策評価を行い、エピーソード中に訪問された全ての状態において、方策改善が行われるという具合である。
  

これらの事項を考慮したモンテカルロ法を、モンテカルロ-ES法といい、以下のようなアルゴリズムとなる。

◎ 方策オン型モンテカルロ法

先のモンテカルロ-ES法では、決定論的な行動方策において、モンテカルロシミュレーション上で、実際には到達しない状態行動対が存在するために、利得の平均値の計算が出来ず、結果として、収益の平均値として算出される行動価値関数の推定値も正しく算出出来なくなるという問題を回避するために、開始点検索（＝全ての状態行動対を、エピソードの開始点に設定出来る）の仮定を行っていた。

しかしながら、この開始点検索の仮定は、実際上のタスクにおいて、非現実的なものであので、次に、開始点検索の仮定を除外することを考える。
この方法には、大きく分けて２つの方法（方策オン型モンテカルロ法と方策オフ型モンテカルロ法）があるが、いづれもエージェントに、到達しない状態行動対を選び続けさせるというのが基本的なコンセプトになっている。
※ ここでのオン・オフの意味は、モンテカルロシミュレーションでエピソードの系列（＝状態行動対）を観測する際に、方策評価、方策改善で対象となる行動方策を「使う」/「使わない」ということを意味している。

まずは、方策オン型モンテカルロ法について見ていく。

方策オン型モンテカルロ法では、決定論的な行動方策を全てにおいて完全に排除して、常に全ての状態 ∀s∈S と行動 ∀a∈A において というソフトなもの置き換える。
これにより、常に なので、到達されない状態行動対は存在しなくなり、開始点検索の仮定は必要なくなる。
そして、上記のように方策をソフトなものに置き換えた上で、行動方策を、決定論的になる最適方策に向けて、徐々に移行させていくようにする。

方策をソフトなものに置き換えるやり方は、いくつか変種があるが、ここでは、ε-greedy 手法を用いる方法を見ていく。

ε-グリーディ方策では、以下の式で与えられる行動方策 である。

先に見た一般化方策（GPI）による共通の知見では、方策改善が行えるためには、行動方策がグリーディ方策に移行しなくてはならないが、これは、移行の過程で、該当方策がずっとグリーディ方策であることは要求しておらず、グリーディ方策に移行することだけが要求されている。

今考えている方策オン型モンテカルロ法の場合では、単純にεーグリーディ方策へと移行するだけである？
行動価値関数 に関するどのような ε-グリーディ方策も、従来のソフト方策に関して、改善された方策になっている。このことは方策改善定理によって保証されている。
即ち、任意の状態 ∀s∈S 、新しい ε-グリーディー方策 π′、従来のソフト方策 π に対して、

となり、方策改善定理の条件が成り立つので、新しい εーグリーディー方策 π′ と従来のソフト方策 π に対して、 となり、 となる。
つまり、行動価値関数 に関するどのような ε-グリーディ方策も、従来のソフト方策に関して、改善された方策になっている。

以上のことを踏まえて、先のモンテカルロ-ES法から、開始点検索の仮定を取り除き、決定論的な行動方策をソフト方策に置き換ると、以下のような方策オン型モンテカルロ法のアルゴリズムが得られる。

◎ 方策オフ型モンテカルロ法

開始点検索の仮定を外しても、価値推定を正しく行うことが出来る別の方法として、方策オフ型モンテカルロ法が存在する。

この方策オフ型モンテカルロ法では、行動方策を、次の２つの方策 π′,π に分ける。

• 挙動方策 π′ [behavior policy]：エピーソードを生成するための方策
  

• 推定方策 Ï€ [estimation policy]：方策評価・方策改善に使用する方策
  

このように方策を２つの方策に分けた場合は、挙動方策と推定方策とで得られる収益が異なるので、如何にしてエピソードを生成する挙動方策から、推定方策を使って方策評価や方策改善を行えばよいのか？というのが課題となる。

この課題を解決するために、挙動方策と推定方策それぞれで、実際に生成されるエピソードの系列が実現される確率を比較し、それらを収益で評価（＝価値関数で評価）するときの重みとして利用することを考える。

そのためにまず、上図のように、挙動方策と推定方策２つの方策 π,π′ に対して、エピソード全体に渡っての、以下のような確率を導入する。

今のモンテカルロ法の場合、この２つの確率 は、状態遷移関数 が不明なので、未知の変数であるが、その確率の比 をとると、

となるので、状態遷移確率によらないので、モデルのダイナミクスが不明であっても、２つの行動方策（推定方策、挙動方策）から計算可能な値となる。

次に、挙動方策 π′ で収益 R が観測されたときに、推定方策 π でも収益 R が観測される確率を考えると、この確率は、確率の比 で表現されるので、推定方策 π のもとでの収益の合計 と行動価値関数の推定値 Q(s,a) は、以下のようなアルゴリズムで求まることが分かる。

ここまでの事項をアルゴリズムとしてまとめると、以下のような方策オフ型モンテカルロ法のアルゴリズムが得られる。

◎ モンテカルロ法の適用例

• （例）逐一訪問モンテカルロ法を利用した単純な迷路探索問題
  

github.com

■ TD学習（時間的差分学習）

先のモンテカルロ法は、モデルフリーの強化学習でモデルを必要としないが、実際の環境が生成したエピソードの開始から終端までで繰り返しサンプリングを行うために、エピソードの完了までに待たなくては計算可能とならない問題が存在する。

一方、動的計画法は、ブーストラップ性によりエピソードの完了を待たずとも計算可能となるが、モデルベースの強化学習手法であり、状態遷移確率の形が具体的に与えられていないと、計算が出来ないという問題が存在する。

この両者（MC法、DP法）の利点を織り込んだ最適価値関数の推定手法として、TD学習と呼ばれるモデルフリーの強化学習手法が存在する。
具体的には、このTD学習では、状態遷移確率の具体的な形を必要せず、なおかつ、ブートストラップ性を用いて、エピソードの終端まで待たずに、価値関数の更新をオンライン型で逐次行うことが出来る。
※ 但し、エピソードの完了を待たずに、逐次現時点での見積もりを行っていることになるため、１エピソード全体に渡っての見積もりを行うMC法と比べて、特に初期段階においては正確性に欠けることになる。

ここで、オンライン型の推定値の計算の一般的な議論の例として、平均値の計算の取扱いについて見てみる。 報酬 の平均値計算は、以下のようにして計算できる。

この平均値計算式の形式では、新しいデータが追加されるたびに、和の操作を再度実行する必要があるために、計算負荷が大きくなりやすいという問題が存在する。即ち、

従って、この式を、前回の平均値と最新のデータから、新しい平均値を算出するという漸近式の表現に書き直すと、

即ち、平均値の計算を、漸近式の形で表現すると、以下のような形式となる。

• 新しい推定値 ← 古い推定値＋ステップサイズ ✕ [最新の更新データ ー 古い推定値]
  

この漸近式の表現では、新しいデータに対して、都度平均値計算をし直す必要はなく、オンライン型の手続きが可能となり、計算負荷が軽減されるといったメリットが存在する。

次に、この漸近式の表現での価値関数の推定方法を、先の逐次訪問モンテカルロ法による価値推定の方法に適用してみることを考える。
先のモンテカルロ法による価値推定の方法では、各状態 s に対する得られた収益のリスト Returns(s) を平均化したもので価値関数の推定を行っていたが、これを漸近式の形で表現すると、

この収益 を目標値とする漸近式の形で表現した、逐次訪問モンテカルロ法による価値推定手法を、アルファ不変MC法という。
尚、このアルファ不変MC法は、漸近式の形で表現されているが、報酬の平均値である収益 がエピソードの完了までまたないと計算できないため、漸近式のメリットであるオンライン型の手続きのメリットは享受できない。

◎ TD(0)法

TD学習では、このα不変MC法のように、エピソードの完了までまたないと計算できない収益 ではなく、次のステップでの価値関数と報酬の推定値 を使用する。
即ち、 の１ステップでの関係式を、先の不変MC法の式 の収益 の項に入力した式

により、価値関数の推定値の更新を行う。
このような１ステップ間での直近の価値関数の推定値を用いる最も単純なTD法を、TD(0)法と呼ぶ。

以下の図は、モンテカルロ法とTD(0)のバックアップ線図を比較した図である。

この図から分かるように、このTD(0)法では、α不変MC法と比較すると、 を目標値として更新を行うが、この際に、α不変MC法とは異なり、エピソードの完了まで待たなくとも、次のステップ t+1 まで待つだけでよい。
※ この TD(0)法では、上図のバックアップ線図で示したように、１ステップでのバックアップ処理の式になっているので、１ステップTD法であるとも言える（詳細は後述）

• 【参考サイト】
  
  • 今さら聞けない強化学習（9）: TD法の導出
    
  • 強化学習について学んでみた。（その18）

◎ Sarsa（方策オン型TD制御）

ここでは、TD法を制御問題に適用する方法について見ていく。
TD法を制御問題に適用した手法には、大きく分けて、方策オン型TD制御手法と方策オフ型TD制御手法の２つが存在する。
Sarsa は、このうち方策オン型TD制御手法に分類される手法の１つであり、先のTD法と ε-greedy 手法を組み合わせた手法である。より具体的には、行動価値関数の推定をTD法によって行い、エピソードの更新（＝行動選択）を ε-greedy な行動方策によって行う手法である。

まず、行動選択に関する ε-greedy 手法について見ていく。
行動価値関数 Q(s,a) に関してグリーディな行動方策とは、 となるような行動 a のことであったが、このグリーディーな行動方策では、常にその時点での最適解を模索するため、局所的最適解に陥る恐れが存在する。
そこで、局所的最適解を脱出して大域的最適解に移動できるように、リスクをとって、一定の確率 ε でランダムな行動をとるよな行動方策を考える。この行動方策を ε-greedy 手法という。

Sarsa では、行動価値関数の推定をTD法によって行うが、TD法による行動価値関数の更新と推定は、以下のような漸近式で表現されるのであった。

記号の簡単化のため、t の添字なしで書き換えると、以下のようになる。

Sarsa では、この更新式により、推定する行動価値関数の更新を行う。
※ Sarsa というアルゴリズムの名前は、上式の推定式の右辺の変数 s,a,r′,s′,a′ の頭文字を繋げたものに由来する。
そして、エピソードの更新（＝行動選択）は、ε-greedy 手法に従った行動方策によって行う。

以下の図は、Sarsa のバックアップ線図である。

上図から分かるように、この Sarsa は、ε-greedy な行動方策によってエピソードの更新（＝行動選択）が行われ、それに伴って次の状態 s',a' が定まり、価値関数の更新が行われることになる。
即ち、Sarsa では、実際に進む行動（＝エピソードを更新する行動）と価値関数の推定値の更新に用いる行動が同様となる。
そして、このような制御手法を、方策オン型TD制御という。

この Sarsa をアルゴリズムとしてまとめると、以下のようになる。

◎ Q学習 [Q-learning]（方策オフ型TD制御）

先に見た Sarsa は、エピソードの更新（＝行動選択）と価値関数の更新の双方が、共に同じ ε-greedy な行動方策に従って行われる方策オン型TD制御アルゴリズムであった。

一方、Q学習は、エピソードの更新（＝行動選択）と価値関数の更新の双方が、必ずしも同じ行動方策になるとは限らない方策オン型TD制御アルゴリズムになっている。

まず、Q学習における、価値関数の推定値の更新式は、以下のようになる。

この式から分かるように、Sarsa とは異なり、Q学習では、価値関数の値が max となるようなグリーディーな行動選択を一律に行う。
（※ Sarsa では、ε-greedy な行動方策に従って、一定のランダム性を織り込んだ行動選択であった。）
一方、エピソードの更新（＝行動選択）は、Sarsa と同様にして、ε-greedy 手法に従った行動方策によって行う。

以下の図は、Q学習のバックアップ線図である。

上図から分かるように、（推定値の更新式に含まれる項である） によるグリーディーな行動選択と、ε-greedy な行動方策によるエピソードの更新（＝行動選択）とは、必ずしも一致するとは限らない。
即ち、Q学習では、実際に進む行動（＝エピソードを更新する行動）と価値関数の推定値の更新に用いる行動が異なる。
そして、このような制御手法を、方策オフ型TD制御という。

このQ学習をアルゴリズムとしてまとめると、以下のようになる。

【Memo】
- SarsaとQ学習のの収束性の比較
行動選択に関しては、SarsaとQ学習は共に ε-greedy によるランダム性をもった行動選択となるが、価値関数の推定値の更新に関しては、Sarsa が ε-greedy ランダム性が更新式に入る一方で、Q学習では、 のようにランダム性を持たない一律のグリーディーな行動選択となる。
従って、ランダム性がない分、Q学習のほうが Sarsa より収束が早い傾向がある。

• 【参考サイト】
  
  • 今さら聞けない強化学習（10）: SarsaとQ学習の違い
    
  • 強化学習について学んでみた。（その19）

◎ nステップTD法

先のTD(0)では、価値関数の更新式（＝漸化式） の式での収益 R おいて、１ステップでの関係式 を代入した式

つまりは、１ステップバックアップで価値関数の推定を行っていた。
一方、モンテカルロ法では、エピソードの開始から終端までの全ての系列に基づいてバックアップを行っていた。

nステップTD法は、この１ステップバックアップであるTD(0)法と、全ステップバックアップであるモンテカルロ法の中間のバックアップであり、n ステップバックアップで価値関数の推定を行う（下図参照）
※ 尚、先の TD(0) 学習は、このnステップTD法の範疇にあり、n=1 のときの手法となる。

式で書くと、TD学習における、価値関数の更新式（＝漸化式）

の収益 R おいて、TD(0) 法では、１ステップでの関係式 を代入していたのに対して、 nステップTD法では、nステップ先での関係式

に拡張して代入する。即ち、価値関数の推定値の更新式は、

となる。

◎ TD(λ)法

☆ TD(λ)の前方観測的な見方

一般的に、TD法におけるバックアップ

の収益項（＝目標値）は、nステップ収益に対してのみだけではなく、nステップ収益の平均値に対しても適用でき、この平均化された収益で、上式に従って価値推定を行うことが出来る。

TD(λ) アルゴリズムは、このような、nステップバックアップを平均化した収益で価値推定を行うアルゴリズムである。
詳細には、各 n ステップ収益 を で重み付け平均化した収益

を収益として利用して、価値推定を行う。
※ この式において、λ=0 とすると、 となるので１ステップ収益となり、TD(0) に帰着する。
※ 又、λ=1 とすると、 となり、アルファ不変MCに帰着する。

この重み付けの様子を、バックアップ線図とともに図示したものが以下の図である。

ここで、この重み付け平均化した利得 の計算は、現在の時間 t から将来の時間 t+1,t+2,... に渡っての重み付け平均化処理であり、時間の経過方向 t→t+1→t+2→... に沿って観測しているので、前方観測的見方となっていることが分かる。

☆ TD(λ)の後方観測的な見方と適格度トレース

先に見たTD(λ)の前方観測的見方では、

の式に従って、重み付け平均化された収益 を算出したが、これは、現在の時間 t から将来の時間 t+1,t+2,... に渡っての重み付け平均化処理であり、時間の経過方向 t→t+1→t+2→... に沿って観測しているので、前方観測的見方となっている。

しかしながら、前方観測的見方の方法では、時間が n ステップ経過後でないと、実際に利益 R_t⁽ⁿ⁾ が計算できないので、価値推定を行えないという問題が存在する。

この問題を解決するために、前方観測的見方を反転し、時間の経過方向とは逆の方向からみた後方観測的見方からTD(λ)を考え直す。
より詳細には、今考えているTD(λ)において、後方の時間ステップ t+n から見た、TD誤差（＝現在の推定価値との差分） が、時間ステップ t での価値推定 にどの程度の重みで影響を与えているのか？ということを考えると、TD(λ)においては、各時間ステップ t+1,t+2,... でのTD誤差は、nステップ前の価値の推定に、 の重みで影響を与えているということが分かる。

従って、 に比例した重みで影響を与えるような以下のような適格度トーレスなるものを考える。

• この適格度トーレスは、
  「時間ステップ t において、次の状態 を観測した際に、ある状態 s∈S の価値 V(s) に反映させるための、現在状態との価値の差分 に対しての重み」
  を表しており、全ての状態 ∀s∈S に対して定義される。
  
• より端的・包括的に言い換えると、
  「強化事象が発生したときに、各状態が学習上の変化を受けることが、”適格” であることの度合い」
  を表しており、その意味で、適格度トレースという。
  

この適格度トレースは、価値関数に反映させるための、TD誤差 に対しての重みになっているので、この２つ（＝TD誤差と適格度トレース）を乗算した式から、TD(λ)の価値推定（＝価値関数の更新）を行う。
即ち、

• 【参考サイト】
  
  • 強化学習について学んでみた。（その25）
    

☆ Sarsa(λ)

Sarsa に対して、TD(λ) と同様にして、適格度トレースを導入したものを Sarsa(λ) という。
これは、単純に、Sarsaにおける価値推定の更新式

を、適格度トレースを使用した以下のような価値推定の更新式に置き換えるものである。

この Sarsa(λ) をアルゴリズムとしてまとめると、以下のようになる。

◎ アクター・クリティック手法

アクター・クリティック手法は、TD法の１種であるが、これまでの強化学習手法とは異なる考え方に基づくアプローチであり、行動方策に基づく行動と方策評価のプロセスを、それぞれアクターとクリティックという２つの機構に分離して強化学習をモデル化している。

• アクター（行動器）[actor]：
  行動方策 に基づき、行動を選択する機構。
  行動方策は、以下のような softmax 関数で選択される。
  
  

• クリティック（評価器）[critic]：
  現在アクターが利用している行動方策 に対する評価を行う機構。
  

クリティックによる方策評価は、TD誤差 を、状態で行われた行動が選択される確率である への評価として利用することで行われる。
即ち、TD誤差の値に応じて、 を以下のようにを増減させる。

☆ アクタークリティック手法への適格度トレースの適用

アクター・クリティック手法に対しても、TD(λ) の後方観測的見方と同様にして、前方観測的見方→後方観測的見方に置き換えて、適格度トレースを導入することが出来る。

まず、アクター・クリティック手法（＝厳密には、１ステップ・アクター・クリティック手法）では、状態 s で行動 a を選択する確率 を、以下のように増減させていた。

この更新式は、TD(λ) での推定価値関数の更新式 に対応したものになっているので、TD(λ) の後方観測的見方での推定価値関数の更新式

と同様にして、以下のように、適格度トレースを用いて書き換えられる。
即ち、

◎ TD法の適用例

• （例）Sarsa を利用した単純な迷路探索問題
  

github.com

• （例）Q学習を利用した単純な迷路探索問題
  

github.com

• （例）Q学習を利用した倒立振子課題（CartPole）
  

github.com

• （例）Q学習を利用した FrozenLake
  

github.com

■ 関数による価値関数の近似（関数近似手法）

これまで見てきた各種強化学習アルゴリズムでは、いずれも、離散的な状態空間 、及び、離散的な行動空間 に対して、
状態価値関数 V(s) の各要素

或いは、行動価値関数 Q(s,a) の各要素

の推定を行っていた。

※ 下図は、状態価値関数 V(s) の離散的な各状態 s∈S に対しての、各要素の推定値の模式図。行動価値関数 Q(s,a) では、離散的な各状態行動対 (s,a)∈S×A に対しての３次元プロットになる。

そして、このような処理を実現するために、これらの離散的な状態空間、離散的な行動空間に対しての、価値関数の各要素の推定値

をそのままメモリ上に保管し、価値関数の推定値の更新処理を行っていた。
このような方式を、テーブル法という。

しかしながら、このテーブル法では、多くの実際上の強化学習のタスクにあるように、状態数や行動数が膨大な数存在する場合、或いは、状態や行動が離散的ではなく連続である場合において、膨大なメモリを消費しい、又計算コストも膨大になるという問題が存在する。

この問題を解決するための別の方法として、下図のように、真の価値関数を、離散的な状態行動対に対しての価値関数で推定するのではなくて、連続な関数で近似することを考える。このような手法を、関数近似手法という。

まず、真の価値関数の関数近似を行う関数を、時間ステップ t に依存したパラメータ で表現される関数とする。
即ち、時間ステップ t での価値関数を、以下のように近似することを考える。

※ この近似関数は、例えば、パーセプトロンの場合は、パラメータ 、各層のノード間の重みとなる。
※ 別の例として、決定木で計算される関数を、この近似関数とすることも出来る。（この場合のパラメータ は、木の全ての分岐数と葉の数を決めるようなパラメータに相当する。）

ここで、このパラメータ の要素数は、状態数 |S| に比べて、圧倒的に少なく、パラメータ１つを変更すれば、多くの価値関数の推定値が変更されることを想定している。
これにより、テーブル方式でメモリ管理する手法に比べて、大幅にメモリを消費量を削減できるようになる。

• 【参考サイト】
  
  • 今さら聞けない強化学習(11) 線形関数による価値関数近似
    
  • 強化学習について学んでみた。（その28）
    
  • 強化学習について学んでみた。（その29）
    

◎ 損失関数としての最小２乗誤差（MSE）

強化学習における関数近似では、一般的に、損失関数 L として、最小２乗誤差（MSE）を考え、これが最小（※出来れば大域的最適解の意味での最小だが、一般的には、局所的最適解の意味での最小になることが多い）になるように、パラメータ の学習を行う。
即ち、

ここで、P(s) は、異なる状態 の誤差 に対して、重み付けを行う分布関数である。
一般的に、全ての状態 s に対して、良い価値関数の近似を得ることは難しく、そのため、ある幾つかのの状態 s に対しては、良い近似とする代わりに、別の幾つかの状態の近似を犠牲にすることが多い。この状態に対しての重みの分布関数 P(s) を導入することにより、このようなトレードオフを表現することが出来る。

◎ パラメータの更新式としての最急降下法

先に見たように、関数近似器による真の価値関数への関数近似を行うためには、損失関数としての最小２乗誤差（MSE）を採用し、これを最小化するようにパラメータを学習すれば良い。
ここでは、このパラメータの学習規則であるパラメータの更新式を、最急降下法によって導く。

最急降下法では、損失関数 L が最も変化する方向（＝勾配方向）に、パラメータを更新する。
即ち、

ここで、この損失関数の勾配は

と書けるので、先の最急降下法によるパラメーターの更新式は、以下のように書き換えられる。

ここで重要なのは、このパラメータの更新式

に含まれる真の価値関数 は、不明であるということである。
これが、教師あり学習と強化学習の大きな違いの１つであり、強化学習では正解となる真の価値関数という教師データが与えられておらず、教師なし学習となっている。

しかしながら、このパラメータの更新式に従って、パラメータの学習を進めていくには、何かしらの目標となる値が必要であることには変わりない。
つまり、真の価値関数 ではなく、何かしらの目標値 に従って、パラメータの学習を進めていく必要がある。
即ち、

この何かしらの目標値 として良い目標値を与えるのが、先に見てきたモンテカルロ法やTD法などの各種強化学習手法である。

例えば、モンテカルロ法での、 の更新式で用いた を目標値として利用できる。（）
このとき、パラメータの学習の更新式は、以下のようになる。

※ この最急降下法を用いたモンテカルロ状態価値推定は、偏りのない真の価値関数の推定値となるので、局所的最適解の発見が保証される。

同様にして、TD(λ)での、各 n ステップ収益 を重み付け平均化した収益

も目標値として利用できる。（）
このとき、パラメータの学習の更新式は、以下のようになる。

※ この最急降下法に基づく TD(λ)での状態価値推定は、（モンテカルロ法とは異なり）偏りのない真の価値関数の推定値とならないので、局所的最適解の発見が保証されない。
※ 但し、特別なケースにおいて、この局所的最適解とは異なる面での性能保証が得られる。その意味でも、このTD(λ)のようなブーストラップ手法は、重要なものとなる。（詳細は後述）

ここで、この最急降下法に基づく TD(λ)での状態価値推定は、時間ステップ t→t+1→t+2 方向で更新される式であり、前方観測的な見方の式になっているが、先に見たように、これを後方観測的見方で書き換えることも出来る。即ち、最急降下法に基づく TD(λ) の後方観測的見方は、以下の更新式で与えられる。

◎ 線形関数での価値関数の近似（線形手法）

線形手法は、関数近似器 を、特徴空間 内でのパラメータ に関しての線形関数で表現する手法である。
※ 特徴空間 内でパラメータ に対して線形なのであって、単に状態価値空間 S✕A での線形関数ではないことに注意。

より詳細には、関数近似器を、特徴写像後のベクトル とパラメータ との線形結合で表現する。

※ この特徴写像後のベクトル（＝特徴ベクトル） は、特徴空間 を張る基底ベクトルになる。

次に、このようなパラメータに関しての線形関数で表現された関数近似器に、最急降下法を適用することを考える。即ち、

従って、最急降下法によるパラメータの更新式

は、特徴ベクトルを用いた、以下のような簡単な形へと帰着される。

更に、この特徴空間内でのパラメータ に関しての線形関数 は、線形なので、局所的最適解 は一意に定まり、それ故に大域的最適解となる。
従って、最急降下法のように局所的最適解の存在やその近傍への収束を保証する手法ならば、この局所的最適解の収束性が、自動的に大域的最適解への収束を保証することになる。

ここで、この特徴写像 の具体的な形としては、例えば、以下のようなRBFカーネルが用いられる。

◎ 最急降下型Sarsa（関数近似手法のSarsaへの適用）

行動価値関数 Q(s,a) に対しての、最急降下法によるパラメーターの更新式は、状態価値関数のときと同様にして、以下のようになる。

この更新式は、前方観測的見方の式になっているが、後方観測的見方の式に書き換えると、状態価値関数のときと同様にして、

この後方観測的見方のパラメーターの更新式は、Sarsa(λ) に対して、関数近似と最急降下法手法を適用したものになっているので、最急降下型 Sarsa(λ) という。（線形手法も適用したものは、線形最急降下型Sarsa）
※ 厳密には、最急降下型 Sarsa(λ) の価値推定プロセス部分に相当。

制御手法としての完全な最急降下型 Sarsa(λ) アルゴリズムを得るためには、この価値推定のプロセスだけでなく、方策評価・方策改善のプロセスも織り込む必要がある。
しかしながら、このような作業は、行動集合 A が連続空間、或いは、離散的であっても要素数（＝行動数）が膨大な離散集合である場合は、困難となる。（現時点では、はっくりとした解法は提案されていない？）
一方で、行動集合 A が離散的で、要素数（＝行動数）がそれほど大きくない場合においては、従来のテーブル方式でのSarsa(λ)と同じ方策評価・方策改善のプロセスが利用できる。

これらの事項をまとめると、まず、最急降下型 Sarsa(λ) 価値推定アルゴリズムは、以下のようなアルゴリズムとなる。

■ 方策勾配に基づく強化学習手法

これまでみてきた各種強化学習手法は、行動価値関数や状態価値関数の学習を通じて、エージェントの最適な行動方策 π(s,a) を求めていた。

一方、この項目で扱う方策勾配法などの方策勾配に基づくアルゴリズムは、価値関数を経由することなしに、直接エージェントの行動方策 π(s,a) を求める手法である。
この際、行動方策は、あるパラメーターベクトル θ で定まる確率モデル で表現し、これをパラメーター θ に関して最適化することで、最適な行動方策を求める。

強化学習においてエージェントの目的は、その期待収益を最大化することであるが、このことは、方策勾配に基づく強化学習のアルゴリズムにおいては、上図のように、期待収益（＝割引利得の期待値）を目的関数 として、この目的関数 を最大化するように行動方策 のパラメーター θ を求めることになる。

ここで一般的に、この方策モデル でのパラメーター θ の学習は、勾配法などの勾配ベースの手法で行う。
即ち、

で繰り返し更新していくことで、最適解を求めていく。（多くの場合、局所的最適解）

この方策勾配による強化学習アルゴリズムは、大きく分けて以下のような３つの手順にまとめられる。
① 行動方策 による行動
② 行動方策 の評価
③ 行動方策 の更新

1. 行動方策 による行動
   方策勾配による強化学習手法では、エージェントの行動方策 を確率関数で定める。
   また、 はパラメーター θ に関して微分可能な関数とする。（勾配計算可能とするため）
   このような関数は、具体的には、以下のような関数となる。
   

   • 状態空間 S と行動空間 A が共に離散的である場合
     
     

   • 状態空間 S が連続で、行動空間 A が離散的である場合
     この場合、状態空間の状態数を数えれないため、単純にソフトマックス関数で確率を表現できない。
     従って、特徴写像を介してからソフトマックス関数で確率を表現する。即ち、
     
     

2. 行動方策 の評価
   勾配方策による強化学習手法では、パラメーター θ を更新することで、よりよい行動方策 を得ていくが、その際に、パラメーター θ によって定まる行動方策 の良さを評価する指標が必要となる。
   この指標となるのが、（エージェントの目的である）将来に渡っての期待収益（＝割引利得の期待値）である。（※ ここで、期待値をとるのは、行動方策は確率関数で表現されるために、得られる収益もゆらぎをもつためである。）
   式で書くと、
   
   

3. 行動方策 の更新
   行動方策 の評価を目的関数 として定義したので、その目的関数 を最大化するように行動方策のパラメーター θ を求めれば良いことになる。
   一般的には、このような目的関数 を最大化するパラメーター θ を解析的に解くことは困難であるため、勾配法による数値解析的手法が使用される。
   ある時点 t での勾配法による更新式は、以下のようになる。
   
   ここで、方策勾配定理より、目的関数の勾配 は、行動価値関数 Q(s,a) を用いて、以下のように表現できる。（詳細計算略）
   
   更に、対数の微分の性質を利用して変形すると、
   
   

• 参考サイト
  • memo: 強化学習 〜方策勾配定理の導出〜
  • ゼロから始める深層強化学習（NLP2018講演資料）/ Introduction of Deep Reinforcement Learning

â—Ž REINFORCE

先の勾配の式

は、実際には、解析的に解くことは出来ないため、行動方策 に従って、実際に得られたサンプリを用いて、これをモンテカルロ近似することを考える。

今、エージェントが行動方策に従って、ステップ数が t=0~T の行動を、M回のエピソード数行ったとすると、この勾配の式は、以下のようにモンテカルロ近似出来る。

ここで、この近似式における行動価値関数 は、未知であるため、これを更に近似することを考える。

REINFORCE は、この式における行動価値関数の最も簡単な近似として、行動価値関数 を即時報酬で近似するアルゴリズムである。
即ち、

REINFORCEアルゴリズムでは、この勾配推定の近似方法に加えて、更に、ベースラインという手法も導入している。これは、ベースラインというバイアス定数 b を勾配の推定式に追加して、

としても、期待値自体に変化は生じないため、この関係式は成り立つが、分散値には影響を及ぼすということを利用した手法である。
この性質を利用して、勾配の推定分散が小さくなるようにバイアス項 b を設定することで、勾配の推定精度を高めることが出来る。

一般的に、このような分散値を小さくするバイアス項 b としては、その計算の容易さから、平均報酬がよく利用される。
即ち、

従って、REINFORCE における勾配の推定式は、以下のようになる。

そして、この勾配の推定式で、勾配法に従って、パラメーター θ を逐次更新していくことになる。
即ち、

◎ 方策勾配法

先に見たように、勾配の推定にベースライン b を導入してもその期待値の式

は成り立つが、このようなベースライン b のうち、行動 a に依存せず、状態 s のみに依存するベースライン に対しても、

の関係式は成り立つ。

ここで、この状態 s のみに依存する関数であるベースライン として、状態価値関数 を採用すると、上式は、

となり、アドバンテージ関数 での推定式に置き換えられる。
このようにして、アドバンテージ関数の推定値から求めた勾配から、勾配法に従って、パラメータを更新していく手法を、方策勾配法という。
式で書くと、

■ 深層学習の構造を取り込んだ強化学習手法（深層強化学習手法）

◎ 多層パーセプトロン（MLP）による価値関数の近似

先の関数近似の手法では、真の価値関数の関数近似を行う関数を、以下のような時間ステップ t に依存したパラメータ で表現される関数とした。

自然な流れとし、このパラメーター を、ニューラルネットワークにおける各層間の重みとして採用することで、ニューラルネットワークで表現した関数近似器を採用することが考えられる。

下図は、最も基本的なニューラルネットワークとしての多層パーセプトロンを、価値関数の関数近似器として採用したときの図である。

ここで、上図のように、MLPに強化学習における関数近似手法を適用する際には、多層パーセプトロンへの入力信号・教師信号、及び、多層パーセプトロンからの出力信号は、以下のような設定となる。

多層パーセプトロン（MLP）では、この教師信号と出力信号との誤差から生じる損失関数の勾配を、逆伝搬させて、各層間の重みを逐次更新させる（＝誤差逆伝搬法）ことになるが、そのことを強化学習における関数近似に適用する場合にどうなるのかを、以下で順を追って見ていく。

まず、MLPを強化学習における関数近似に適用する場合においては、教師信号と出力信号との誤差は、以下のようなQ学習でのTD誤差で表現される。

強化学習における関数近似では、一般的に、損失関数として、最小２乗誤差（MSE）を考え、これが最小（※出来れば大域的最適解の意味での最小だが、一般的には、局所的最適解の意味での最小になることが多い）になるように、パラメータ の学習を行った。
ニューラルネットワークによる関数近似でも同様にして、先のTD誤差から作られる最小２乗誤差を損失関数として採用する。
即ち、

先に見た関数近似の手法では、このパラメータの学習規則であるパラメータの更新式を、最急降下法によって導いた。
ニューラルネットワークによる関数近似でも同様にして、最急降下法によって出力層への重み（＝パラメーター）を更新する。

ここで、この損失関数の勾配は、

と書けるので、最急降下法による出力層での重みの更新式は、以下のように書き換えられる。

そして、この最急降下法による出力層での重みの更新は、誤差逆伝搬で、出力層側から入力層側に向かって順次反映されていく。これにより、出力信号に教師信号（＝TD誤差）を与えるだけで、前段の層を含めたすべての層の重みを更新することが出来る。
※ 誤差逆伝搬では、勾配（＝最急降下法）による重みベクトルの更新を逆方向に伝搬させるために、損失関数の勾配をいわゆる連鎖率の計算で求めていく。
※ この連鎖率での微分計算を効率よく計算していくための、数値解析的な手法として、自動微分が使われる。

◎ Neural Fitted Q Iteration（MLPによる関数近似で学習を安定化させるための工夫）

先のMLPによる関数近似では、各層間の重み θ がそれぞれ別の値のパラメーターであるが故に、パラメーター数が多くて、なかなか学習が収束しないという問題が存在する。

ここで紹介する Neural Fitted Q Iteration は、先のMLPによる関数近似において、学習を安定化させるために以下のような工夫・テクニックを導入した手法である。

• Experience Replay（経験再生）：
  MLP に入力する状態信号は、何も考慮しない場合、あるエピソードにおける開始状態から終了状態に向かっての時系列データ（＝状態の履歴）となるが、このような時系列データは、一般的に、時系列由来の相関の影響を受けてしまっており、互いに独立なデータ [i.i.d] でないことになる。
  この問題を回避するために、このような時系列データではなくて、複数のエピソードにおける様々な時間ステップ t でのデータを、一連の学習用データとして使用する。
  これにより、学習データの偏りを防ぎ、学習を安定化させることが出来る。
  このような学習安定化のためのテクニックを、Experience Replay といい、Neural Fitted Q Iteration では、この Experience Replay のテクニックを利用して、学習を安定化させるための工夫を行っている。
  ※ 後述の Deep Q-Network（DQN）でも、この Experience Relay のテクニックは使用されている。
  

• オンライン学習ではなくバッチ学習で学習（＝パラメーターの更新）を行う：
  先のMLPによる関数近似では、以下の更新式に従って、（出力層の）重みを更新（＝学習）していた。
  この更新式は、新しい学習用データ (s′,a′,r) が届いた際に、その場で重みを更新するオンライン学習となっている。
  一般的な議論として、オンライン学習は、その場で素早く変化に対応して学習できる代わりに、学習が安定化しずらいというデメリットが存在する。
  Neural Fitted Q Iteration では、先の Experience Replay で生成した一連のデータセットに対して、このデータセット全体で一括に学習を行うというバッチ学習で学習を行うようにする。
  これにより、オンライン学習で学習を進めるよりかは、学習が安定することになる。
  

以上のような学習安定化のためのテクニックを考慮した Neural Fitted Q Iteration を、アルゴリズムとしてまとめると、以下のようになる。

◎ Deep Q Network（DQN）

DQNは、先の MLPによる関数近似や Neural Fitted Q-Iteration に対して、学習の安定化のための工夫として、主に以下のような手法やテクニックを導入した手法である。
※ DQN は、単に、DNNで関数近似しただけの手法ではなく、このような学習の成功・安定化テクニックを含めたものであることに注意

• Experience Replay（経験再生）：
  先の Neural Fitted Q-Iteration と同様にして、あるエピソードの状態履歴（＝時系列データ）を、複数エピソードの様々な時間ステップでのデータにシャッフルしたものを、学習用データとして利用する。
  

• ミニバッチ学習：
  先の Neural Fitted Q-Iteration では、オンライン学習ではなくバッチ学習での重み更新とすることで、学習の安定化を図ったが、DQN では、オンライン学習とバッチ学習の折込案であるミニバッチ学習により、学習を安定化させ、なおかつ、その場での逐次学習を可能にしている。
  

• 報酬の clipping：
  エージェントの報酬 r の値を、正規化処理として、クリッピングした値にする。
  即ち、+10,-5 のような価値に応じて重み付した値ではなく、正の価値なら＋１、負の価値なら－１、ゼロ価値ならば０に設定する。
  

• Target network の導入：
  
  先のMLPによる関数近似や Neural Fitted Q Iteration では、行動価値関数の関数近似器の目標値の更新式は、
  
  となっていたが、行動価値関数の関数近似値 と とは、エピソードの１ステップ間 t→t+1 での行動価値関数であり、互いに時系列に相関のあるものとなっているので、この更新式における、教師信号と出力信号とに、時系列な相関が出来てしまう（上図参考）。
  従って、この更新式で行動価値関数を更新すると、教師信号そのものの値が変化してしまい、本来の教師信号としての役割を果たしていないという問題が存在する。
  
  この問題を解決するための対策として、DQNでは、先の更新式において、前回時間ステップ t での重み θ での行動価値関数 の代わりに、古い時間ステップでの重み で固定されたDNN（＝Fixed Target Network という）による関数近似器 を使用する。
  そして、一定の周期で古い重み と最新の重みを同期 θ するようにする。
  即ち、以下のような更新式で、関数近似器を更新する。
  
  これにより、重みが更新されても、教師信号の値は更新させず、教師信号としての本来の役割を果たすことになる。
  

• 損失関数として、Huber 関数を利用：
  
  先のMLPによる関数近似や Neural Fitted Q Iteration では、損失関数として、（教師信号と出力信号との）最小２乗誤差を採用していたが、この最小２乗誤差では、上図のように、誤差値（＝教師信号ー出力信号）が大きい領域では、損失関数値の勾配値が大きくなりすぎて、学習の不安定化してしまうので、DQNでは、このような勾配爆発の対策として、Huber 関数を損失関数として採用する。
  この Huber 関数は、損失関数の値がある値を超えると、勾配が一定値でクリッピングさせるために、勾配爆発を防ぐことが出来る。（上図参照）
  

• CNNの導入：
  
  

  DQNでは、行動価値関数の関数近似器として、MLP ではなく、上図のようなCNNの構造を使用する。
  ※DQN で採用されている CNN のネットワーク構成では、一般的な CNN のネットワーク構成で見られるように、畳み込み層の後のプーリング層は構成されていないことに注意。
  ※このCNNでは、畳み込み層での１より大きいストライドで、ダウンサンプリングしており、これでプーリング処理の代用をしていると考えられる。
  この CNN の導入により、これまでの強化学習手法のように、入力データとして、マス０、マス１、・・・といった各強化学習タスク（迷路探索問題など）固有のエージェントの状態ではなく、強化学習環境の画面の画像データそのものを入力データとすることが出来る。
  

  更には、CNNの重み共有の構造により、MLPで関数近似するよりパラメーター数を減らすことに繫がって、結果として学習を容易にすることも出来る。
  

  ここで、この CNN に入力する入力画像は、うまく特徴量を捉えるために、まず以下のような前処理を行う。
  （前処理１）学習環境の画像データを、81✕81 pixel の画像データにリサイズ
  （前処理２）RGB情報を持つ画像データは、グレースケースに変換
  （前処理３）画面上のチラツキを抑えるため、前後のフレームの最大値を取る。（詳細は、後述の Max and Skip）
  

  そして、この前処理を行った強化学習環境の直近の連続４フレーム画像データを、CNNの入力層に入力する。
  ※ 連続した４フレーム分の画像を入力する理由の１つは、エージェントの移動を特徴量として捉えるためである。（１フレームの画像だけではエージェントの位置しか分からないが、過去２フレームあればエージェントの移動速度が分かり、過去３フレームあれば加速度が分かるため）
  

• その他の学習の安定化のための工夫
  

  • No-Operation
    強化学習環境のリセット直後の特定の開始状態で大きく依存して学習が進み、結果として過学習を起こしてしまうことを防ぐために、強化学習環境のリセット直後、数ステップ間は何も学習しないプロセスを実施する。
    
  • Episodic Life
    例えば、atari の Breakout（ブロック崩しゲーム）では５機のライフがあるので、５回失敗でゲーム終了となるが、この残機では学習が面倒となるので、１回失敗でゲーム終了に設定する。但し、１回失敗毎に完全にリセットすると、初期状態ばかり学習してしまい、過学習してしまいやすいので、１回失敗でのリセットでは、崩したブロックの状態はそのままにしておいて、５回失敗でのリセットでは、崩したブロックの状態もリセットする完全なリセットとする。
    
  • Max and Skip
    atari の Breakout は 60FPS で動作するが、この速さで動かすと早すぎるので、４フレーム単位で行動を判断させ、４フレーム連続で同じ行動を行うようにする。これにより、60FPS → 15 FPS となる。但し、atari のゲームには、奇数フレームと偶数フレームで現れる画像が異なるゲームがあるために、画面上のチラツキを抑える意味で、最後の3、4フレームの最大値をとった画像を入力画像（＝状態）として採用する。
    

☆ DQNの適用例

• （例）DQN（2013年バージョン）を用いた倒立振子課題（CartPole）

github.com

• （例）DQN（2015å¹´Natureバージョン）を用いた倒立振子課題（CartPole）

github.com

◎ Double-DQN（DDQN）

Q学習での関数近似やその延長線上であるDQNでは、下式のように、教師データを、推定価値関数の更新式でのmaxオペレーターによるグリーディな行動選択により生成している。

しかしながら、このグリーディな行動選択では、本当は価値が高くないような行動 a を過大評価し、結果として、過大な行動価値評価を行ってしまうことがあるために、正解データであるべき教師データとして、不適切なデータになってしまうことが多々生じ、これが学習の不安定化要因の１つとなる。

一方で、DQNでは、学習安定化のための工夫として、Fixed Target Network の仕組みを導入した。
これは、古い時間ステップでの重み で固定されたネットワーク（＝Fixed Target Network という）による関数近似器 を使用し、一定の周期で古い重み と最新の重み θ を同期するようにするものであった。

DDQNでは、このTarget Network による学習安定化のための工夫を更に発展させる。
具体的には、次の状態 でQ値を最大化する行動 は、Main Network から求め、その状態行動対 でのQ値は、Target Network から求めるようにする。
式で書くと、

☆ DDQNの適用例

• （例）DDQNを用いた倒立振子課題（CartPole）

github.com

◎ Prioritized Experience Replay（優先順位付き経験再生）

DQN では、学習の安定化のための工夫として、あるエピソードの状態履歴（＝時系列データ）を、複数エピソードの様々な時間ステップでのデータにシャッフルしたものを、学習用データとして利用するという Experience Relay（経験再生）を行っていた。
しかしながら、この Experience Relay では、これらの学習用データを保管するためのバッファサイズ（＝replay memory）のサイズが大きくなるという問題が存在する。

Prioritized Experience Replay（優先順位付き経験再生）の基本的なコンセプトは、Q学習が十分に進んでいない遷移サンプルを優先的にサンプリングすることで学習の効率を改善することである。
これにより、より少ないバッファサイズで効率的に学習することが出来るようになる。
※ この際の、Q学習が十分に進んでいないかの判断は、（Q学習での）TD誤差で行う。

先の Experience Relay では、N個のサンプルデータからなる学習用データバッファ（＝replay memory）中の i 番目のサンプルがサンプリングされる確率分布である に従ってサンプリングされていることになる。
これに対して、Prioritized Experience Replay では、TD誤差が大きい遷移サンプルほどサンプリングされやすくなるような、別の確率分布 に従ってサンプリングする。これにより、学習が十分進んでいないサンプルについて優先的に学習出来るようにする。

ここで、この確率分布 の具体的な式としては、以下のような種類が存在する。

• greedy TD-error priorization
  最も単純な TD誤差に基づくサンプリング方法で、TD誤差の絶対値が最大のもののみを greedy にサンプリングする。
  但し、この手法では以下のような問題点が存在する。
  

  1. サンプリングされた遷移サンプルのTD誤差のみが更新される。
     これにより、初期状態において、TD誤差が小さかった遷移サンプルは、長期間サンプリングされない状態が続き、学習がうまく進まない。
     

  2. 最大値のみを取るので、局所的にTD誤差が大きくなるようなスパイクノイズに過剰に反応してしまう。
     

  3. TD誤差の大きい遷移サンプルのみサンプリングするので、学習が多様ではなく局所的になり、過学習を起こしやすい。
     

• Stochastic sampling method
  先の greedy TD-error priorization での問題点を解決するために、Experience Relay と greedy なサンプリング手法の中間的なサンプリングを行う。
  即ち、遷移サンプル i を以下のような確率分布でサンプリングする。
  
  

  ここで、この遷移サンプル優先度 の具体的な形には、以下のような種類が存在する。
  
  

  1. Proportional Prioritization ( direct )
     
     

  2. Rank-based Prioritization ( indirect )
     
     

     このときのサンプリングの確率分布は、
     
     

     と変形できるので、確率分布 は、パラメーター α に対するべき乗分布となる。サンプリングの確率分布が、べき乗分布となるとなることにより、外れ値に対して過剰に反応しなくなり、（Proportional Prioritization の方法よりも）外れ値に対してのロバスト性が向上する。
     

• Annealing bias（重点サンプリングによるバイアス軽減）
  一様分布でない確率分布は、サンプリングの分布にバイアスを生じさせるので、この確率分布の期待値の収束値にもバイアスが生じてしまう問題がある。このバイアスを軽減させるために、重点サンプリングによる手法が使用される。
  具体的には、以下の式で与えられる重みをTD誤差に掛ける（）ことで、バイアスを軽減する。
  
  

• 参考サイト
  • Prioritized Experience Replay | DeepLearningを勉強する人
  • Prioritized Experience Replayを読んだ | Qiita

☆ Prioritized Experience Replay の適用例

• （例）DDQN & Prioritized Experience Replay を用いた倒立振子課題（CartPole）

github.com

â—Ž Dueling Network

先の DQNやDDQNでは、各状態 s ごとに複数の行動 に対する行動価値関数 を一度に出力するネットワークアーキテクチャになっていた。
この手法では、複数の行動に対する行動価値関数 を全て学習する必要があるが、このことは、例えば、行動価値関数 Q(s,a) が、状態 s のみに大きく依存して、行動 a の選択による影響が小さい場合においては、その計算効率はよいとは言えない。

Dueling Network は、下図のように、このような DQN のネットワークアーキテクチャを拡張し、ネットワークから状態価値関数 を直接求めるのではなく、行動価値関数 を評価するネットワーク部分とアドバンテージ関数と呼ばれる関数 を評価するネットワーク部分を分離して追加することで、状態価値関数 とアドバンテージ関数 を別々に学習し、そこから行動価値関数 を算出できるようにした手法である。
これにより、各状態ごとに複数の行動に対する行動価値関数を一度に出力するDQNに比べて、少ないステップ数で、学習を進めることができるようになるメリットが存在する。

※ ここで、アドバンテージ関数 は、その定義式 より、状態価値 に対する特定の行動 a を選択した場合の相対的な価値を表している。
※ もっと簡単に言えば、アドバンテージ関数は、行動価値関数から状態価値関数を引くことで、行動のみの価値を得ているとも言える。

• アドバンテージ関数とネットワークの分離
  アドバンテージ関数 の定義式を変形すると、
  
  となり、２つの分離されたネットワークからの出力であるアドバンテージ関数と状態価値関数を加算分離したものとなることがわかる。
  
  ここで、実際のネットワークからの各種出力は、（CNNでの）重みパラメーター θ,α,β に関しての推定関数であるので、この加算分離式は、
  
  で表現されるように思えるが、この推定関数での式は、あくまで（CNNからの）推定値であり、真の値と異なるので、この推定関数での分離式は厳密には成り立たない。
  
  例えば、グリッド上の迷路探索問題において、行動↑でのアドバンテージ推定関数の誤差が b0 であった場合、先の加算式が成り立つためには、推定価値関数にこれを打ち消す誤差 -b0 が乗る必要がある。
  式で書くと、
  
  一方で、行動↓でのアドバンテージ推定関数の誤差が b1 であった場合、先の加算式が成り立つためには、推定価値関数に、先の b0 とは異なるような、打ち消す誤差 -b1 が乗る必要がある。
  式で書くと、
  
  つまり、先の加算式が成り立つためには、行動の種類によって、異なる値の誤差が推定価値関数に乗る必要があり、これは、学習の不安定化要因になってしまう。
  
  従って、この分離式のよりよい近似式として、以下の２つの近似式を考える。
  
  
  これら２つの式の赤字の部分では、いずれも全ての行動 に対してのアドバンテージ関数 を計算することになるので、ある行動を行ったときにも、別の行動でのアドバンテージ関数に繋がるパラメーター（重み）を更新でき、各々の行動でのアドバンテージ関数が独立に計算されるのを防ぐことができる。
  その結果として、学習の不安定化要因である、行動の種類によって、異なる値の誤差が推定価値関数に乗ることを軽減することができる。
  

• 参考サイト

  • 論文紹介：Dueling network architectures for deep reinforcement learning

☆ Dueling Network の適用例

• （例）Dueling Network を用いた倒立振子課題（CartPole）

github.com

â—Ž A2C [Advantage Actor-Critic]

A2C [Advantage Actor Critic] は、Advantage学習、アクタークリティックモデルでのニューラルネットワーク、及び、方策勾配法に基づく損失関数をベースにした深層強化学習手法である。

※ A2C の名前にある Advantage Actor Critic の言葉自体には分散並列の意味は含まれないが、公式の A2C は分散環境で並列に経験を収集する手法も含むことに注意。これは A2C [Advantage Actor Critic] が A3C [Asynchronous Advantage Actor Critic] の後発であることに由来する。
※ ここで解説する A2C は、この分散環境で並列に経験を収集する手法を含まないものとしている。

• Advantage 学習：
  これまでみてきたQ学習などのTD学習やDQNでは、１時間ステップ間 t→t+1 での価値関数の更新を繰り返すことで学習を行ってきた。
  しかしながら、この 1ステップ間遷移で推定値の更新を繰り返す方法では、正しい値に収束するのに時間がかかってしまうという問題点が存在する。
  

  Advantage 学習では、この問題を解決するために、１ステップ先ではなく複数の k ステップ先まで一気に動かして推定値の更新を行うことで、学習の収束スピードを高める。
  ここで、この際の更新対象となる推定量は、価値関数ではなくアドバンテージ関数となる。
  式で書くと、
  
  ※ アドバンテージ関数の計算で、行動価値関数 Q と状態価値関数 V の双方を計算することを避けるため、行動価値関数 Q は、割引利得と割引された状態価値関数の和（赤字部分）を使用していることに注意。
  ※ ステップ幅 k の値を大きくとりすぎると、誤った学習をしてしまう可能性も増大するため、最適な k の値は、タスクに応じたハイパーパラメータとなる。
  

  ここで、後述で示すように、A2Cでは、このアドバンテージ学習をアクタークリティックモデルに適用するので、推定状態価値関数 V(s) は、行動方策 π での推定状態価値関数 になり、アドバンテージ関数の計算式は、
  
  となる。
  

• Actor Critic モデルでのニューラルネットワーク：
  DQNでは、ある状態 s に対して、複数の行動に対する行動価値関数 を全て学習する必要があるが、このことは、例えば、行動価値関数 Q(s,a) が、状態 s のみに大きく依存して、行動 a の選択による影響が小さい場合においては、その計算効率はよいとは言えない。
  （※ Dueling Network では、この問題を解決するために、後ろに、アドバンテージ関数と状態価値関数の２つのネットワークで分離させていた）
  

  A2C では、アクタークリティック手法のモデルを採用し、アクターの行動方策 π(s,a) と、クリティックの推定状態価値関数 V(s) をそれぞれ独立に学習させていくことで、計算効率を改善する。
  

  この際に、アクタークリティックモデルをニューラルネットワークに組み込むことになるが、モデリングするにあたって着目するのは、アクタークリティックモデルにおける入出力関係である。
  即ち、
  ① アクターは、状態 s を入力し、行動方策 π(s) を出力する。
  → 実際には、アドバンテージ関数 A(s) を出力させ、それを softmax することで、行動方策 π(s) を出力する。
  ② クリティックは、状態 s を入力し、行動方策 π での推定状態価値関数 を出力する。
  

  下図は、このアクタークリティックモデルにおける入出力関係をもとに、ニューラルネットワークを構築したアーキテクチャ図である。
  ※ 入出力関係の説明のしやすさから、ニューラルネットワークのネットワーク構成として、CNNではなくMLP上で説明しているが、一般的にはCNNが使用されることに注意。
  

  
  

• 損失関数
  ニューラルネットワークの重みパラメータは、誤差逆伝搬により行われるが、その際に損失関数が定義されている必要がある。
  A2C における、ニューラルネットワークでのアクタークリティックモデルでは、アクターとクリティックの２つのネットワークが存在するので、損失関数には、アクター側の損失関数と、クリティック側の損失関数の２つをそれぞれ定義する必要がある。
  

  1. アクター側の損失関数（方策勾配法に基づく損失関数）
     まず、アクター側の損失関数について考える。
     アクターが最大化したいのは割引利得であるので、割引利得であって、かつアドバンテージ関数で表現される関数が適切であると考えられるが、これには方策勾配法における割引利得の期待値が使用される。
     即ち、
     
     

     ここで、アドバンテージ関数 における行動価値関数 は、先のアドバンテージ学習でみたように、
     
     のように、行動 a に対する定数で表現されるもので近似する。
     

     更に、以下の式で与えられるエントロピー項のマイナス値を加える。
     
     ⇒ 一様分布となる行動方策で最大値をとり、どれか１つの行動を選択する決定論的な行動方策で最小値となる。
     ※ このエントロピー項を損失関数に加えることで、学習初期におけるパラメータ θ の更新が、局所的最適解に陥って抜け出せなくなってしまうことを防ぐ効果がある。
     

     以上をまとめると、アクター側の損失関数は、以下のようになる。
     
     

  2. クリティック側の損失関数
     クリティック側は、状態価値関数の推定値 V^π (s_t ) を正しく出力出来るように学習させたいので、状態 s から実際に行動 a を選択して得られる行動価値関数 との差の２乗で、損失関数を定義する。
     即ち、
     
     

• 参考
  • 星の本棚 | 強化学習 | アクター・クリティック手法

---

■ 参考サイトと参考文献

◎ 参考サイト

強調文字付きは、特に参考にさせたもらったサイトです。

• 【全般】

  • これから強化学習を勉強する人のための「強化学習アルゴリズム・マップ」と、実装例まとめ
  • ゼロからDeepまで学ぶ強化学習

• 【古典的強化学習手法】

  • 強化学習について学んでみた。（まとめ） - いものやま。
  • 今さら聞けない強化学習（1）：状態価値関数とBellman方程式
  • Reinforcement Learning: An Introduction(Richard S. Sutton and Andrew G. Barto)
  • 第３章： 強化学習の基礎理論
    
  • dissecting reinforcement learning
  • Reinforcement Learning(方策改善定理)
  • 強化学習理論の基礎3

• 【深層強化学習】
  

  • DQNからRainbowまで 〜深層強化学習の最新動向〜
    
  • ゼロから始める深層強化学習（NLP2018講演資料）/ Introduction of Deep Reinforcement Learning
  • 深層強化学習アルゴリズムまとめ
  • DQNの生い立ち　＋　Deep Q-Networkã‚’Chainerで書いた
    
  • 最近のDQN
    
  • DQNの理論説明
  • Prioritized Experience Replay - DeepLearningを勉強する人
  • Prioritized Experience Replayを読んだ
  • 論文紹介：Dueling network architectures for deep reinforcement learning
  • DQNを卒業してA3Cで途中挫折しないための7Tips
  • GAN（と強化学習との関係）

◎ 参考文献

強化学習

速習 強化学習 ―基礎理論とアルゴリズム―

これからの強化学習

つくりながら学ぶ! 深層強化学習 ~PyTorchによる実践プログラミング~

機械学習スタートアップシリーズ Pythonで学ぶ強化学習 入門から実践まで (KS情報科学専門書)