sykwer’s blog

進捗どうですか

深層強化学習アルゴリズムDDPGをしっかり理解する(2)

{ \DeclareMathOperator*{\argmin}{arg\,min} }
{ \DeclareMathOperator*{\argmax}{arg\,max} }
 

この記事は、

sykwer.hatenablog.jp

これ↑の続きにあたるものです.

Deterministic policy gradient theoremの導出だけ知りたい! という人以外は、最初の記事から読むことをおすすめします.

 

 

2) DPGアルゴリズム

前回の記事では、確率的な方策(= とある状態sに対して行動aが確率的に決まる方策)をparameterizeし、平均報酬 or 割引報酬和が最大になるようにパラメータを更新していくアルゴリズムを導出し実装しました.

このようなアルゴリズムをSPG(stochastic policy gradient) algorithmと呼ぶことも紹介しました.

 

今回は、決定論的な方策(= とある状態sに対して一意に行動aが決まる方策)をparameterizeし、割引報酬和が最大になるようにパラメータを更新していくアルゴリズムを導出し、実装していきます.

このようなアルゴリズムをDPG(deterministic policy gradient) algorithmと呼びます.

 

かつては、決定論的な方策勾配は存在しないか、model-freeでない強化学習モデルでのみ存在すると考えられていました.
しかし、2014年のdeepmind社の論文により、決定論的な方策勾配が存在し、確率論的な方策勾配のアプローチよりも性能面で上回ることが示されました.

 

2.1) DPGアルゴリズムを使っていくモチベーション

この章では、SPGアルゴリズムに代わってDPGアルゴリズムを使っていくメリットについて書いていきます.

 

そのためにまずは、方策パラメータの更新則を示す、決定論的な勾配方策定理がどのような形をしているのかを見てみます.

以下の式が決定論的な勾配方策定理です. ただし、

  • 今回、状態sと状態aには連続値を想定.
  • {\displaystyle \mu }: 決定論的な方策. 状態sに対して行動aを一意に出力.
  • {\displaystyle \rho^{\mu}(s) }: 方策{\displaystyle \mu }のもとでの、状態sの割引分布(前回の記事を参照)
  • {\displaystyle Q^{\mu}(s, a) }: 方策{\displaystyle \mu }のもとで、状態sで行動aをとったときの行動価値関数.

{\displaystyle \nabla_{\theta} J(\mu^{\theta}) }

{\displaystyle = \int_S \rho^{\mu}(s) \nabla_{\theta} \mu_{\theta}(s) \nabla_a Q^{\mu}(s, a) |_{a = \mu_{\theta}(s)} ds }

{\displaystyle = \mathbf{E}_{s \sim \rho^{\mu}} [ \nabla_{\theta} \mu_{\theta}(s) \nabla_a Q^{\mu}(s, a) |_{a = \mu_{\theta}(s)} ] }

{\displaystyle = \mathbf{E}_{s \sim \rho^{\mu}} [ \nabla_{\theta} Q^{\mu}(s, \mu_{\theta}(s)) ] }

 

割引報酬和の勾配は、行動価値関数の勾配∇θQ(s, μ(s))に対して、状態sで期待値をとった形をしています.


さて、この形だと確率論的な方策勾配定理に対して何がうれしいのでしょうか.

 

前回の記事で考えた、確率論的な方策勾配定理(ただし、s, aが連続値バージョン)は以下のような形をしていました.

 

{\displaystyle \nabla_{\theta} J(\pi_{\theta}) }

{\displaystyle = \int_S \rho^{\pi}(s) \int_A \nabla_{\theta}\pi_{\theta}(a | s)Q^{\pi}(s, a) da ds } 

{\displaystyle = \mathbf{E}_{s \sim \rho^{\pi}, a \sim \pi_{\theta}} [ \nabla_{\theta} \log \pi_{\theta}(a|s) Q^{\pi}(s, a) ] }

 

注目すべきは、何に対する期待値をとっているかです.
SPGは、状態空間と行動空間の2つに対して期待値をとっているのに対して、
DPGは、状態空間のみに対して期待値をとっています.

 

よってPGを推定するために必要なサンプル数が、SPGよりもDPGの方が少なくなり、計算量が小さくなるのです.
(特に、行動空間の次元数が大きいときにうれしい)

 

2.2) DPG theoremの導出

それでは、上述の確率論的な方策勾配定理を導出していきましょう.

 

{\displaystyle \nabla_{\theta}V^{\mu^{\theta}}(s) }
 
今回は決定論的な方策を考えていて、状態に対して行動が一意に決まるので
{\displaystyle = \nabla_{\theta} Q^{\mu^{\theta}}(s, \mu_{\theta}(s)) }
 
ベルマン方程式を適用して
{\displaystyle = \nabla_{\theta} [ r(s, \mu_{\theta}(s)) + \int_S \Pr(s’ | s, \mu_{\theta}(s)) V^{\mu^{\theta}}(s’) ds' ] }
 
微分のchain ruleより
{\displaystyle = \nabla_{\theta}\mu_{\theta}(s)\nabla_a r(s, a)|_{a = \mu_{\theta}(s)} + \int_S \gamma [ \nabla_{\theta}\mu_{\theta}(s)\nabla_a\Pr(s’ | s, a)|_{a = \mu_{\theta}(s)} V^{\mu^{\theta}}(s’) + \Pr(s’ | s, \mu_{\theta}(s)) \nabla_{\theta}V^{\mu_{\theta}}(s') ] ds' }
 
 共通項をくくって
{\displaystyle = \nabla_{\theta}\mu_{\theta}(s)\nabla_a[ r(s, a) + \int_S \gamma\Pr(s’ | s, a) V^{\mu_{\theta}(s’)}ds' ] |_{a = \mu_{\theta}(s)} + \int_S \gamma \Pr(s’ | s, \mu_{\theta}(s)) \nabla_{\theta}V^{\mu_{\theta}}ds' }
 
ベルマン方程式より
{\displaystyle = \nabla_{\theta}\mu_{\theta}(s) \nabla_aQ^{\mu^{\theta}}(s, a)|_{a = \mu_{\theta}(s)} + \int_S \gamma \Pr(s \rightarrow s’ | 1, \mu_{\theta}) \nabla_{\theta}V^{\mu_{\theta}}(s’)ds' }
 
さて、以上の式変形により {\displaystyle \nabla_{\theta}V^{\mu^{\theta}}(s) } に関する漸化式を導くことができました. 以下漸化式をくりかえし適用してみます.
 
{\displaystyle \nabla_{\theta}V^{\mu^{\theta}}(s) }
{\displaystyle = \nabla_{\theta}\mu_{\theta}(s)\nabla_a Q^{\mu_{\theta}}(s, a)|_{a = \mu^{\theta}(s)} }
{\displaystyle \ \ \ + \int_S \gamma \Pr(s \rightarrow s’, 1, \mu_{\theta}(s)) \nabla_{\theta}(s’) \nabla_a Q^{\mu^{\theta}}(s’, a’)|_{a’ = \mu_{\theta}(s')}ds' }
{\displaystyle \ \ \ + \int_S \gamma \Pr(s \rightarrow s’, 1, \mu_{\theta}) \int_S \gamma \Pr(s' \rightarrow s’', 1, \mu_{\theta}) \nabla_{\theta}\mu_{\theta}(s'’) \nabla_{a''} Q^{\mu_{\theta}}(s'’, a'’)|_{a'’ = \mu_{\theta}(s'')} ds’ ds'' }
{\displaystyle \ \ \ \ +... }
{\displaystyle = \nabla_{\theta}\mu_{\theta}(s)\nabla_a Q^{\mu_{\theta}}(s, a)|_{a = \mu^{\theta}(s)} }
{\displaystyle \ \ \ + \int_S \gamma \Pr(s \rightarrow s’, 1, \mu_{\theta}(s)) \nabla_{\theta}(s’) \nabla_a Q^{\mu^{\theta}}(s’, a’)|_{a’ = \mu_{\theta}(s')}ds' }
{\displaystyle \ \ \ + \int_S \gamma^2 \Pr(s \rightarrow s’, 2, \mu_{\theta}(s)) \nabla_{\theta}(s’) \nabla_a Q^{\mu^{\theta}}(s’, a’)|_{a’ = \mu_{\theta}(s')}ds' }
{\displaystyle \ \ \ \ +... }
{\displaystyle = \int_S \sum_{t=0}^{\infty} \gamma^t \Pr(s \rightarrow s’, t, \mu_{\theta}) \nabla_{\theta}\mu_{\theta}(s’) \nabla_{a'} Q^{\mu_{\theta}}(s’, a’)|_{a’ = \mu_{\theta}(s')} ds' }
 
以上、{\displaystyle \nabla_{\theta}V^{\mu^{\theta}}(s) }を計算することができました.
さて、以下で方策勾配を計算してみます. すると{\displaystyle \nabla_{\theta}V^{\mu^{\theta}}(s) }の項が出現するので、以上の計算結果を利用することができます. そして整理すると決定論的な方策勾配定理を導くことができます.
 
{\displaystyle \nabla_{\theta}J(\mu_{\theta}) }
{\displaystyle = \nabla_{\theta} \int_S p_0(s) V^{\mu_{\theta}}(s) ds }
{\displaystyle = \int_S p_0(s)\nabla_{\theta} V^{\mu_{\theta}}(s) ds }
{\displaystyle = \int_S p_0(s) \int_S \sum_{t=0}^{\infty} \gamma^t \Pr(s \rightarrow s’, t, \mu_{\theta}) \nabla_{\theta}\mu_{\theta}(s’) \nabla_{a'} Q^{\mu_{\theta}}(s’, a’)|_{a’ = \mu_{\theta}(s')} ds' ds }
{\displaystyle = \int_S  \int_S \{ \sum_{t=0}^{\infty} \gamma^t p_0(s) \Pr(s \rightarrow s’, t, \mu_{\theta}) \} \nabla_{\theta}\mu_{\theta}(s’) \nabla_{a'} Q^{\mu_{\theta}}(s’, a’)|_{a’ = \mu_{\theta}(s')} ds' ds }
{\displaystyle = \int_S  \rho^{\mu_{\theta}}(s) \nabla_{\theta}\mu_{\theta}(s) \nabla_{a} Q^{\mu_{\theta}}(s, a)|_{a = \mu_{\theta}(s)}  ds }
 

2.3) DPGの直感的な理解

DPGは以下のような形をしていることが導かれました. 方策勾配は、行動価値関数の勾配の期待値というシンプルな形をしています.
 

{\displaystyle J(\mu^{\theta})= \mathbf{E}_{s \sim \rho^{\mu}} [ \nabla_{\theta} Q^{\mu}(s, \mu_{\theta}(s)) ] }

 

これは以下のように直感的に理解することができます.
 
 
多くのmodel-freeを想定した強化学習アルゴリズムをざっくりまとめると、policy-evaluation -> policy-improvement -> policy-evaluation -> ... というようなpolicy-iterationのサイクルにしたがってアルゴリズムが進行していくと捉えることができます.
 
policy-evaluationのフェーズでは、行動価値関数{\displaystyle Q^{\mu}(s, a) }の評価を行います. 具体的には、モンテカルロ近似やTD学習によって評価されます.
 
policy-improvementのフェーズでは、policy-evaluationのフェーズで更新された行動価値関数にしたがって、方策を更新します. もっとも単純な具体例は、greedyアルゴリズムにしたがって方策を決定していくアプローチでしょう. さて、このアプローチを数式で表すと以下のように書けます.
 
{\displaystyle \mu^{k+1}(s) = \argmax_a Q^{\mu^k}(s, a) }
(k+1ステップにおける方策は、前のステップでevaluateされた行動価値関数に対するgreedyな選択によって決定する、という意味)
 
このgreedyな選択は、行動空間が離散でかつ次元数が小さいときは、大きすぎないルックアップテーブルから最大値を探す作業となり、コンピュータ上で計算可能です.
 
しかし、行動空間が連続である場合は {\displaystyle \argmax_a Q^{\mu^k}(s, a) }を毎ステップ、解析的に求めなくてはなりません. これは不可能です.
 
そこで思いつく有効な代替案は、方策のパラメータを行動価値関数Qの勾配の方向に更新するというものです.
 
つまり、方策のパラメータ{\displaystyle \theta^{k+1} }{\displaystyle \nabla_{\theta}Q^{\mu^k}(s, \mu_{\theta}(s)) }の方向に更新する、というアルゴリズムが導かれます.
 
これは、決定論的な方策勾配定理そのものです.
 

2.4) DPGによる強化学習の特徴

DPGにおけるtarget-policyは、決定論的な方策なので、この方策をそのまま探索における方策に用いてしまうと、十分な探索を行うことができません.

 

そこで十分な探索を保証するために、学習対象となるtarget-policyとは別に、学習中の探索にもちいるbehavior-policyを用いなくてはなりません.
いわゆるoff-policyな強化学習です.

 

また、決定論的方策と行動価値関数との2つを関数近似し最適化していくので、いわゆるActor-Criticアルゴリズムに分類されます.

 

2.5) 実装

前回のSPGと同様に実装例を載せようと思いましたが、次回の記事で解説するDDPGは、DPGアルゴリズムに深いニューラルネットワークを導入したものであり、どちらもDPG theoremに基づくアルゴリズムなので、実装例は次回の記事に委ねることにしました.
 

2.6) 参考文献