[論文解説] Deterministic Policy Gradient Algorithms

この記事は，以下の論文の解説です．

Deterministic Policy Gradient Algorithms (ICML 2014)

ただし，この記事は「DDPGが(Importance Samplingなしで)なぜoff-policyで学習できるのか」の回答を示すことを主な目的とし，論文内で提案している手法や検証実験に関しては触れていません(めんどくさかったため)．

記事内容では，強化学習の基礎的な知識を前提としています．
また，記事中の図は全て論文からの引用です．
不備がございましたら，ご指摘頂けると幸いです．

概要

この論文は，「決定的方策に関する勾配定理を示し，連続行動タスクにおいてoff-policyで学習可能なアルゴリズムを提案した」論文になります．

方策勾配法は，連続行動空間での強化学習によく用いられる手法の一つで，確率的方策 $\pi_\theta(a|s) = \mathbb P [a|s;\theta]$ をモデル化し，確率的方策のパラメータ $\theta$ を割引累積報酬(=収益)の期待値を最大化させるように変化させていきます．つまり，期待収益の $\theta$ に関する微分(=方策勾配)を計算し，$\theta$ を方策勾配の方向に変化させます．

一方，この論文では，決定的方策 $a = \mu_\theta(s)$ をモデル化します．確率的方策の時と同様に，方策勾配の方向に $\theta$ を変化させていけば，期待収益が最大化されると期待できます．しかし先行研究では，決定的な方策の方策勾配(=決定的方策勾配)は存在しないと考えられてきました．

この論文では，まず決定的方策勾配が実際に存在することを示し，(確率的)方策勾配よりも効率的に計算できることを示します．さらに，決定的方策勾配法を用いることで，Importance Samplingなしでoff-policyで学習可能であることを示します．

この記事では触れませんが，論文では，決定的方策勾配法を用いることで，(確率的)方策勾配法よりも効率的に学習できることを検証実験により示しています．

確率的方策の場合

通常の確率的なMDP $<\mathcal S, \mathcal A, r, p, \gamma>$ を考えます．ただし，初期状態分布を $p_1(s_1)$，確率的方策を $\pi_\theta(a|s)$，ステップ $t$ 以降の収益を $r_t^\gamma = \sum_{k=t}^\infty \gamma^{k-t} r(s_k, a_k)$ と表し，$\theta \in \mathcal R^n$ とします．

また，確率的方策 $\pi$ に従ったときに時刻 $t$ で状態 $s$ から状態 $s'$ に遷移する確率密度を $p(s\to s', t, \pi)$ と表し，確率的方策 $\pi$ に従ったときに訪問する状態の期待値の分布(=状態分布)を $\rho^\pi(s') = \int_{\mathcal S} \sum_{t=1}^\infty \gamma^{t-1}p_1(s) p(s\to s', t, \pi)ds$ と表します．

これらを用いると，確率的方策 $\pi$ を用いたとき，目的関数(期待収益)は確率的方策 $\pi$ に関する状態分布 $\rho^\pi$ と確率的方策 $\pi_\theta$ の期待値の形で表すことができます．

\begin{align}
J(\pi_\theta) &= \int_{\mathcal S}\rho^\pi(s)\int_{\mathcal A} \pi_\theta(s,a)r(s,a)dads \\
&= \mathbb E_{s\sim \rho^\pi, a \sim \pi_\theta} [r(s,a)]
\end{align}

方策勾配定理

(確率的)方策勾配法では，確率的方策のパラメータ $\theta$ を方策勾配 $\nabla_\theta J(\pi_\theta)$ の方向に動かすことで，期待収益の最大化を行います．この手法は，以下の方策勾配定理に基づいて計算されます．

\begin{align}
\nabla_\theta J(\pi_\theta)& = \int_{\mathcal S}\rho^\pi (s)\int_{\mathcal A} \nabla_\theta \pi_\theta(a|s)Q^\pi(s,a) dads \\
&= \mathbb E_{s \sim \rho^\pi, a\sim \pi_\theta}[\nabla_\theta \log \pi_\theta(a|s) Q^\pi(s,a)]
\end{align}

導出は，OpenAI Spinning Upにわかりやすく説明されているので，気になる方は参照してみてください(細かな記法は異なりますが，数式は等価です)．

この方策勾配定理では，状態分布 $\rho^\pi$ は方策のパラメータ $\theta$ に依存しているものの，方策勾配は状態分布の勾配に依存しないという大きな特徴を持ちます．真の価値関数 $Q^\pi(s,a)$ は未知なので適切に推定する必要があり，単に収益 $r_t^\gamma$ を $Q^\pi(s,a)$ の推定値に用いた手法が，有名なREINFORCEアルゴリズムです．

off-policyでの方策勾配

off-policyで強化学習を行う際には，学習する方策とは別の方策(=行動方策) $\beta(a|s) \neq \pi(a|s)$ を用いてトラジェクトリーを収集します．以下では，収集したトラジェクトリーを単にデータと呼びます．よって，データの状態分布は獲得方策 $\beta(s|a)$ に基づいているものの，最大化したい期待収益(または価値関数)は学習方策 $\pi(a|s)$ に基づくため，方策勾配の計算に修正を加える必要が生じます．

修正後の目的関数(期待収益) $J_\beta(\pi_\theta)$ は，以下の式で表されます．

\begin{align}
J_\beta(\pi_\theta) &= \int_{\mathcal S}\rho^\beta(s) V^\pi(s)ds \\
&= \int_{\mathcal S}\int_{\mathcal A} \rho^\beta (s)\pi_\theta(a|s)Q^\pi(s,a) dads
\end{align}

上式では，価値関数は学習方策 $\pi$ に基づいているものの，行動方策 $\beta$ の状態分布に関して期待値が取られていることがわかります．この目的関数の勾配は，以下のように近似することができます．

\begin{align}
\nabla_\theta J_\beta(\pi_\theta) &\simeq \int_{\mathcal S} \int_{\mathcal A}\rho^\beta(s)\nabla_\theta\pi_\theta(a|s)Q^\pi(s,a)dsda \\
&= \mathbb E_{s\sim \rho^\beta,a\sim\beta}[\frac{\pi_\theta(a|s)}{\beta_\theta(a|s)}\nabla_\theta\log \pi_\theta(a|s)Q^\pi(s,a)]
\end{align}

この近似では，価値関数に関する勾配 $\nabla_\theta Q^\pi(s,a)$ に関する項を無視していますが，比較的良い近似であることが知られています．この式に現れる $\frac{\pi_\theta(a|s)}{\beta_\theta(a|s)}$ は，Importance Sampling Ratioと呼ばれ，学習方策 $\pi$ ではなく獲得方策 $\beta$ によってデータが収集されたことを補正しています．また，この補正をImportance Samplingと呼びます．

関数近似誤差

Actor-Criticは方策勾配定理に基づいたアルゴリズムで，2つの要素で構成されます．Actorは確率的方策 $\pi_\theta(a|s)$ を表し，方策勾配法に従ってパラメータ $\theta$ を更新します．Criticは，未知の真の価値関数 $Q^\pi(s,a)$ の推定値として $Q^\omega(s,a)$ を表し，TD学習などを用いてパラメータ $\omega$ を更新します．

一般に，価値関数 $Q^\pi(s,a)$ を $Q^\omega(s,a)$ のように関数近似することによって，方策勾配にバイアスが生じてしまいます．しかし，以下の2点を満たす $Q^\omega(s,a)$ を用いると，方策勾配にバイアスが生じなくなることが示されています．

1. $Q^\omega(s,a)$ は，確率的方策の特徴 $\nabla_\theta \pi_\theta(a|s)$ に線形である．
   $$
   Q^\omega(s,a) = \nabla_\theta \log \pi_\theta(a|s)^T \omega
   $$

2. パラメータ $\omega$ は，以下の二乗誤差 $\epsilon^2(\omega)$ を最小化する．
   $$
   \epsilon^2(\omega) = \mathbb E_{s\sim \rho^\pi, a\sim\pi_\theta}[(Q^\omega(s,a)-Q^\pi(s,a))^2]
   $$

この2つを満たすCriticを用いることで，通常の方策勾配法(Criticを用いていない場合)と等価な学習を行うことができます．

決定的方策の場合

前述の議論を決定的方策に拡張していきます．

以下では，まず決定的方策勾配に関する直感的な解釈を追っていきます．その後，数学的な定式化を行います．

価値関数の勾配

多くのモデルフリーの強化学習アルゴリズムでは，方策評価と方策改善を交互に行います．方策評価では，価値関数の推定 $Q^\omega(s,a)$ が真の価値関数 $Q^\pi(s,a)$ に近づくように，パラメータ $\omega$ を更新します．方策改善では，現在の価値関数の推定に基づいて，方策を更新します．よく利用されているアプローチは，価値を最大化する行動選択を行う貪欲方策 $\mu^{k+1}(s) = arg\max_a Q^{\mu^k}(s,a)$ を用いることです．

しかし，連続行動空間では，行動空間全体で$\max$操作を行うことはコストが高いという問題が生じます．よって，$\max$操作の代わりに，価値関数 $Q$ の勾配を取ってその方向に方策を変化させることで，期待収益を最大化するように方策を改善できると考えられます．すなわち，ある状態 $s$ に関して，価値関数の勾配 $\nabla_\theta Q^{\mu^k}(s, \mu_\theta(s))$ に比例して方策のパラメータ $\theta^{k+1}$ を変化させます．各状態 $s$ は異なる方向の勾配を持ちますが，状態分布 $\rho^\mu(s)$ に関して期待値を取ることで方策 $\mu^k$ に従った時の期待収益を最大化する勾配を得ることができると考えられます．
$$
\theta^{k+1} = \theta^k + \alpha \mathbb E_{s\sim \rho^{\mu^k}}[\nabla_\theta Q^{\mu^k}(s, \mu_\theta(s))]
$$
チェーンルールにより，価値関数の方策パラメータ $\theta$ に関する微分は，以下のように分解できます．
$$
\theta^{k+1} = \theta^k + \alpha \mathbb E_{s\sim \rho^{\mu^k}}[\nabla_\theta \mu_\theta(s) \nabla_a Q^{\mu^k}(s, a)\mid_{a = \mu_\theta(s)}]
$$
しかし，方策が更新されると状態分布 $\rho^\mu$ も変化してしまうため，学習方策と行動方策が異なることになります．上式の更新は方策が改善されることを保証するのか，それともImportance Samplingなどの補正を行う必要があるのか??

以下では，上式の直感的な更新が，実際に目的関数(期待収益)に関する勾配(方策勾配)に等しいことを示していきます．

決定的方策勾配定理

決定的方策を $\mu_\theta(s)$ とし，目的関数(期待収益)を $J(\mu_\theta) = \mathbb E[r_1^\gamma|\mu]$ と表し，$\theta \in \mathbb R^N$ とします．また，確率的方策の時と同様に状態分布 $\rho^\mu(s)$ を定義します．目的関数(期待収益)は，以下の式で表されます．

\begin{align}
J(\pi_\theta) &= \int_{\mathcal S} \rho^\mu(s)r(s,\mu_\theta(s)) ds \\
&= \mathbb E_{s\sim\rho^\mu}[r(s,\mu(s))]
\end{align}

確率的方策の時との一番の違いは，方策が決定的なので方策に関する期待値計算がないことです．確率的な場合と同様に，決定的方策勾配定理を以下に示します(証明は論文付録参照)．

定理1: (決定的方策勾配定理)

$p(s'|s,a), \nabla_a p(s'|s,a), \mu_\theta(s), r(s,a), \nabla_a r(s,a), p_1(s)$ が全て連続の時，$\nabla_\theta \mu_\theta(s)$ と $\nabla_a Q^\mu(s,a)$ は存在する．また決定的方策勾配は存在し，以下の式で表される．

\begin{align}
\nabla_\theta J(\mu_\theta) &= \int_{\mathcal S}\rho^\mu(s)\nabla_\theta\mu_\theta(s)\nabla_aQ^\mu(s,a)\mid_{a=\mu_\theta(s)}ds \
&= \mathbb E_{s\sim \rho^\mu}[\nabla_\theta\mu_\theta(s)\nabla_aQ^\mu(s,a)\mid_{a=\mu_\theta(s)}]
\end{align}

よって，前述の直感的な決定的方策のパラメータの更新が，実際に目的関数(期待収益)の勾配方向の更新となっていたことがわかります．つまり，**決定的方策勾配では，Importance Samplingなしでoff-policyでの学習が可能である**ことがわかります．

また，決定的方策勾配では方策に関して期待値計算が必要ないため，(確率的)方策勾配よりも効率的に計算が可能であるというメリットもあります．



### 確率的方策勾配との関係

決定的方策 $\mu_\theta$ と分散パラメータ $\sigma$ を用いて，確率的方策を $\pi_{\mu_\theta, \sigma}$ と表します．ただし，$\sigma=0$ のとき $\pi_{\mu_\theta,0} = \mu_\theta$ となります．このとき，決定的方策勾配が，確率的方策勾配の極限($\sigma \to 0$)として導けることが証明されています(論文付録参照)．すなわち，決定的方策勾配は確率的方策勾配の特殊な場合であると言えます．



## Deterministic Actor-Critic

以下では，決定的方策に基づくActir-Critic，**Deterministic Actor-Critic**のアルゴリズムを示していきます．

### on-policyの場合

強化学習では探索が非常に重要であると考えられており，決定的方策による収集では十分な探索ができないと考えられます．しかし，on-policyでのDeterministic Actor-Criticを理解することはoff-policyの場合の理解の手助けになるので，示していきます．

確率的方策の時と同様，価値関数 $Q^\pi(s,a)$ の推定を $Q^\omega(s,a)$ とし，決定的方策を $\mu_\theta(s)$ とします．決定的方策勾配定理の $Q^\pi(s,a)$ の代わりに推定値 $Q^\omega(s,a)$ を用いることで，方策のパラメータ $\theta$ を更新します．価値関数の推定の更新にSarsaを用いると，以下のようにパラメータを更新していくことになります．

```math
\begin{align}
\delta_t &= r_t + \gamma Q^\omega(s_{t+1},a_{t+1})-Q^\omega(s_t,a_t) \\
\omega_{t+1} &= \omega_t + \alpha_\omega \delta_t \nabla_\omega Q^\omega(s_t,a_t) \\
\theta_{t+1} &= \theta_t+\alpha_\theta\nabla_\theta\mu_\theta(s_t) \nabla_aQ^\omega(s_t,a_t) \mid_{a=\mu_\theta(s)}
\end{align}

off-policyの場合

確率的方策の時と同様，目的関数(期待収益)を以下のように修正します．

\begin{align}
J_\beta(\mu_\theta) &= \int_{\mathcal S}\rho^\beta(s)V^\mu(s)ds \\
&= \int_{\mathcal S}\rho^\beta(s)Q^\mu(s,\mu_\theta(s))ds
\end{align}

よって，方策勾配は以下のように近似することができます．

\begin{align}
\nabla_\theta J_\beta(\mu_\theta) &\simeq \int_{\mathcal S} \rho^\beta(s)\nabla_\theta \mu_\theta(a|s) Q^\mu(s,a)ds \\
&= \mathbb E_{s\sim\rho^\beta} [\nabla_\theta \mu_\theta(s)\nabla_a Q^\mu(s,a)\mid_{a=\mu_\theta(s)}]
\end{align}

この近似でも，$\nabla_\theta Q^{\mu_\theta}$ に関する項を無視しています．大事なのでもう一度言いますが，確率的方策勾配と違い方策に関する期待値計算を必要としないため，決定的方策勾配では，Importance Samplingなしでoff-policyでの学習が可能です．

価値関数の推定にQ学習を用いると，価値関数の更新でもデータを収集した時の方策 $\beta$ に依存しなくなり，Importance Samplingを避けることができます．まとめると，以下のようにパラメータを更新することができます．

\begin{align}
\delta_t &= r_t + \gamma Q^\omega(s_{t+1},\mu_\theta(s_{t+1}))-Q^\omega(s_t,a_t) \\
\omega_{t+1} &= \omega_t + \alpha_\omega \delta_t \nabla_\omega Q^\omega(s_t,a_t) \\
\theta_{t+1} &= \theta_t+\alpha_\theta\nabla_\theta\mu_\theta(s_t) \nabla_aQ^\omega(s_t,a_t) \mid_{a=\mu_\theta(s)}
\end{align}

連続行動空間では，行動方策として確率的方策を用いることで効率的な探索を行いつつも，決定的方策定理を用いることで，より効率的な学習が可能になると考えられます．

###関数近似誤差

決定的方策勾配においても，真の価値関数 $Q^\mu(s,a)$ の代わりに関数近似した推定値 $Q^\omega(s,a)$ を用いることでバイアスが生じます．しかし，確率的方策の時と同様，以下の2点を満たすことで，バイアスなしで決定的方策勾配を計算することができることが証明されています(証明は論文参照)．

1. $\nabla_a Q^\omega(s,a) \mid_{a=\mu_\theta(s)}$ は，決定的方策の特徴 $\nabla_\theta \mu_\theta (s)$ に線形である．
   $$
   \nabla_a Q^\omega(s,a) \mid_{a=\mu_\theta(s)} = \nabla_\theta \mu_\theta(s)^T \omega
   $$

2. パラメータ $\omega$ は，以下の二乗誤差 $\epsilon^2(s;\theta,\omega)$ を最小化する．
   $$
   \epsilon^2(s;\theta,\omega) = \mathbb E[(\nabla_a Q^\omega (s,a)\mid_{a=\mu_\theta(s)}-\nabla_a Q^\mu(s,a) \mid_{a=\mu_\theta(s)})^2]
   $$

まとめ

この論文では，決定的方策勾配定理を示し，決定的方策勾配法に従うことで，連続行動タスクにおいて，Importance Samplingなしでoff-policyで強化学習を行うことができることを示しました．

この決定的方策勾配定理は，DDPGやTD3のベースとなっており，off-policyでサンプル効率のいいアルゴリズムを実現するキモとなっています．