Understand DDPG algorithm step by step (2)

${ \DeclareMathOperator*{\argmin}{arg\,min} }$

${ \DeclareMathOperator*{\argmax}{arg\,max} }$

この記事は、

sykwer.hatenablog.jp

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

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

2) DPGアルゴリズム

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

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

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

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

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

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

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

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

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

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

$= \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の導出

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

$\nabla_{\theta}V^{\mu^{\theta}}(s)$

今回は決定論的な方策を考えていて、状態に対して行動が一意に決まるので

$= \nabla_{\theta} Q^{\mu^{\theta}}(s, \mu_{\theta}(s))$

ベルマン方程式を適用して

$= \nabla_{\theta} [ r(s, \mu_{\theta}(s)) + \int_S \Pr(s’ | s, \mu_{\theta}(s)) V^{\mu^{\theta}}(s’) ds' ]$

微分のchain ruleより

$= \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'$

共通項をくくって

$= \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'$

ベルマン方程式より

$= \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'$

さて、以上の式変形により $\nabla_{\theta}V^{\mu^{\theta}}(s)$ に関する漸化式を導くことができました. 以下漸化式をくりかえし適用してみます.

$\nabla_{\theta}V^{\mu^{\theta}}(s)$

$= \nabla_{\theta}\mu_{\theta}(s)\nabla_a Q^{\mu_{\theta}}(s, a)|_{a = \mu^{\theta}(s)}$

$\ \ \ + \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'$

$\ \ \ + \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''$

$\ \ \ \ +...$

$= \nabla_{\theta}\mu_{\theta}(s)\nabla_a Q^{\mu_{\theta}}(s, a)|_{a = \mu^{\theta}(s)}$

$\ \ \ + \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'$

$\ \ \ + \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'$

$\ \ \ \ +...$

$= \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'$

以上、 $\nabla_{\theta}V^{\mu^{\theta}}(s)$ を計算することができました.

さて、以下で方策勾配を計算してみます. すると $\nabla_{\theta}V^{\mu^{\theta}}(s)$ の項が出現するので、以上の計算結果を利用することができます. そして整理すると決定論的な方策勾配定理を導くことができます.

$\nabla_{\theta}J(\mu_{\theta})$

$= \nabla_{\theta} \int_S p_0(s) V^{\mu_{\theta}}(s) ds$

$= \int_S p_0(s)\nabla_{\theta} V^{\mu_{\theta}}(s) ds$

$= \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$

$= \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$

$= \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は以下のような形をしていることが導かれました. 方策勾配は、行動価値関数の勾配の期待値というシンプルな形をしています.

$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のフェーズでは、行動価値関数 $Q^{\mu}(s, a)$ の評価を行います. 具体的には、モンテカルロ近似やTD学習によって評価されます.

policy-improvementのフェーズでは、policy-evaluationのフェーズで更新された行動価値関数にしたがって、方策を更新します. もっとも単純な具体例は、greedyアルゴリズムにしたがって方策を決定していくアプローチでしょう. さて、このアプローチを数式で表すと以下のように書けます.

$\mu^{k+1}(s) = \argmax_a Q^{\mu^k}(s, a)$