Understand DDPG algorithm step by step (1)

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

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

強化学習において、方策を最適化するアルゴリズムを大きく2つに分類すると、「価値反復に基づくアルゴリズム」と「方策勾配に基づくアルゴリズム」に分けられます.

前者は、状態価値関数V(s)や行動価値関数Q(s, a)にもとづいて方策を記述し、V(s)やQ(s, a)の推定をしていくアルゴリズムであり、

後者は、方策をパラメータθでモデル化し、直接最適化するアルゴリズムです.

このシリーズでは、方策勾配に基づくアルゴリズムの系譜を順にたどっていき、最終的にDDPG(Deep Deterinistic Policy Gradient)を理解し実装することを目的とします.

具体的に、理解していくアルゴリズムは

Stochastic Policy Gradient method
Deterministic Policy Gradient method
Deep Deterministic Policy Gradient method

となります. 下のアルゴリズムを理解するのに、上のアルゴリズムを理解する必要があるという関係になっています.

この記事ではまずStochastic Policy Gradient methodについて理解していきます.

1) SPGアルゴリズム

1) SPGアルゴリズム

方策勾配に基づくアルゴリズムでは、「現在のtarget-policy(= 最適化の対象となる方策)にしたがってagentが行動しつづけたときの期待報酬 $J(\theta)$ 」を目的関数とします. つまり、target-policyのパラメータ $\theta$ を更新しつづけた結果、期待報酬 $J(\theta)$ が最大になることを目指します.

今回はtarget-policyに、stochastic-policy(= 状態sに対して確率的にaが決まる方策)を想定した場合を考えます. つまり、 $\pi(s | a ;\theta)$ というように記述されます.

期待報酬 $J(\theta)$ の勾配 $\nabla_{\theta}J(\theta)$ をアルゴリズムの毎イテレーションで求め、 $J(\theta)$ をその方向に更新していくことで、 $J(\theta)$ を最大化することを目指すのが、このアルゴリズムの大枠となります.

$J(\theta) \leftarrow J(\theta) + 学習率 × \nabla_{\theta}J(\theta)$

Jが最大化したときの $\theta^{\ast}$ が、最適化されたtarget-policyのパラメータとなります.

つまり、 $\pi(s | a ;\theta^{\ast})$ にしたがって行動するのが、optimalな方策であるという結論になり、この強化学習タスクが完了します.

さて、あとは $\nabla_{\theta}J(\theta)$ の求め方を理解すれば、SPGを実装することができます.

SPGにおいては、 $\nabla_{\theta}J(\theta)$ を「勾配方策定理」に基づいて求めます.

以下、2通りの期待報酬Jの表し方を定義し、どちらの表し方においても成り立つ勾配方策定理を提示して、その導出をしていきます.

1.1) 2通りの期待報酬Jの表し方

期待報酬(= 方策の良さ)Jは、平均報酬と割引報酬和との2通りで定義することができます.

平均報酬と割引報酬和でJを定義した場合とでは、それぞれ行動価値関数Q(s, a)と状態sに関する関数d(s)の定義の仕方が異なります.

1.1.1) 平均報酬でJを定義した場合

$J(\theta) = \lim_{n \to \infty} \frac{1}{n} \mathbf{E} (r_0 + r_1 + … + r_n | \theta)$

行動価値関数は

$Q(s, a) = \sum_{t=0}^{\infty} \mathbf{E}(r_t - J(\theta) | s_0 = s, a_0 = a ; \theta)$

状態sに関する関数は、

$d(s) = \lim_{t \to \infty} \Pr(s_t = s | s_0, \theta)$

(平均報酬でJを定義した場合のd(s)は、sの定常分布を表しています. つまり、確率分布を表す量となっています)

1.1.2) 割引報酬和でJを定義した場合

$J(\theta) = \mathbf{E}( \sum_{t=0}^{\infty}\gamma^t r_{t+1} | s_0 ; \theta)$

行動価値関数は

$Q(s, a) = \mathbf{E}( \sum_{t=0}^{\infty}\gamma^{t} r_{t+1} | s_0 = s, a_0 = a ; \theta)$

状態sに関する関数は

$d(s) = \sum_{t=0}^{\infty} \gamma^t \Pr(s_t = s | s_0, \theta)$

(割引報酬和でJを定義した場合のd(s)は、平均報酬でJを定義した場合のd(s)とはちがって、確率分布を表す量ではないことに注意. [Sutton et al. 2000]では、この場合のd(s)をdiscounted weighting of states encountered starting at s0 and then following pi と説明されています)

1.2) 勾配方策定理の導出

以上のようにJ(θ), Q(s, a), d(s)を定義したとき、平均報酬と割引報酬和とのどちらでJを定義しても以下の式が成り立ち、これを「勾配方策定理」とよびます.

$\frac{\partial J}{\partial \theta} = \sum_{s} d(s) \sum_{a} \frac{\partial \pi_{\theta} (a | s)}{\partial \theta} Q(s, a)$

以下これを導出します.

1.2.1平均報酬でJを定義した場合

状態価値関数V(s)は、行動価値関数Q(s, a)のaに関する期待値であるので

$V(s) = \sum_{a} \pi(a | s) Q(s, a)$

このV(s)をθで偏微分してみると以下のようになります

$\frac{\partial V(s)}{\partial \theta} = \sum_{a} ( \frac{\partial \pi_{\theta} (a | s)}{\partial \theta} Q(s, a) + \pi_{\theta} (a | s) \frac{\partial Q(s, a)}{\partial \theta} )$

ここで $\frac{\partial Q(s, a)}{\partial \theta}$ を求めたいので、 $Q(s, a)$ を展開し、 $\theta$ で偏微分してみます

$Q(s, a)$

$=\sum_{t=0}^{\infty}\mathbf{E}(r_{t+1} - J(\theta) | s_0 = s, a_0 = 0 ; \theta)$

$= \mathbf{E} (r_1 - J(\theta) | s_0 = s, a_0 = a ; \theta) + \sum_{t=1}^{\infty} \mathbf{E} (r_{t+1} - J(\theta) | s_0 = s, a_0 = a ; \theta)$

$= \mathbf{E} (r_1 | s_0 = s, a_0 = a ; \theta) - J(\theta) + \sum_{s’} \Pr(s’ | s, a) V(s')$

$\frac{\partial Q(s, a)}{\partial \theta}$

$= - \frac{\partial J(\theta)}{\partial \theta} + \sum_{s’} \Pr(s’ | s, a) \frac{\partial V(s')}{\partial \theta}$ ( $a_0$ がgivenなので $r_1$ は $\theta$ に依存しなく $\mathbf{E} (r_1)$ は消える)

この求めた $\frac{\partial Q(s, a)}{\partial \theta}$ を $Q(s, a)$ の式に代入すると以下のようになります

$\frac{\partial V(s)}{\partial \theta} = - \frac{\partial J(\theta)}{\partial \theta} + \sum_{a} ( \frac{\partial \pi_{\theta} (a | s)}{\partial \theta} Q(s, a) + \pi_{\theta} (a | s) \sum_{s’} \Pr(s’ | s, a) V(s') )$

最終的に求めたい量は $\frac{\partial J(\theta)}{\partial \theta}$ であるので、 $\frac{\partial J(\theta)}{\partial \theta}$ を左辺に、それ以外を右辺にまとめて、さらに式を展開すると以下のようになります

$\frac{\partial J(\theta)}{\partial \theta} = \sum_{a} \frac{\partial \pi_{\theta}(a | s)}{\partial \theta} Q(s, a) + \sum_{a} \pi_{\theta}(a | s) \sum_{s’} \Pr(s’ | s, a)\frac{\partial V(s')}{\partial \theta} - \frac{\partial V(s)}{\partial \theta}$

ここで両辺にd(s)をかけて、全てのsについて和をとります (平均報酬の場合のd(s)は定常分布を表すので、定常状態での期待値をとっていると解釈できます)

$\sum_{s} d(s) \frac{\partial J(\theta)}{\partial \theta} = \sum_{s} d(s) \sum_{a} \frac{\partial \pi_{\theta}(a | s)}{\partial \theta} Q(s, a) + \sum_{s} d(s) \sum_{a} \pi_{\theta}(a | s) \sum_{s’} \Pr(s’ | s, a)\frac{\partial V(s')}{\partial \theta} - \sum_{s} d(s) \frac{\partial V(s)}{\partial \theta}$

ここでd(s)が定常分布であるので、第二項について

$\sum_{s'}\sum_{a}\sum_{s} \Pr(s’ | s, a) Pr(\pi_{\theta}(a|s)) d(s) \frac{\partial V(s')}{\partial \theta} = \sum_{s’}d(s')\frac{\partial V(s')}{\partial \theta}$

と計算することができ、第二項と第三項が相殺し、以下のようになります

$\sum_{s} d(s) \frac{\partial J(\theta)}{\partial \theta} = \sum_{s} d(s) \sum_{a} \frac{\partial \pi_{\theta}(a | s)}{\partial \theta} Q(s, a)$

Jはsに依存しないので、 $\sum_{s}d(s) \frac{\partial J(\theta)}{\partial \theta} = \frac{\partial J(\theta)}{\partial \theta}$ と計算することができ、方策勾配定理が導かれます

$\frac{\partial J}{\partial \theta} = \sum_{s} d(s) \sum_{a} \frac{\partial \pi_{\theta} (a | s)}{\partial \theta} Q(s, a)$

1.2.2) 割引報酬和でJを定義した場合

状態価値関数V(s)は、行動価値関数Q(s, a)のaに関する期待値であるので

$V(s) = \sum_{a} \pi(a | s) Q(s, a)$

このV(s)をθで偏微分してみると以下のようになります

$\frac{\partial V(s)}{\partial \theta} = \sum_{a} ( \frac{\partial \pi_{\theta} (a | s)}{\partial \theta} Q(s, a) + \pi_{\theta} (a | s) \frac{\partial Q(s, a)}{\partial \theta} )$

ここで $\frac{\partial Q(s, a)}{\partial \theta}$ を求めたいので、 $Q(s, a)$ を展開し、 $\theta$ で偏微分してみます

$Q(s, a) = \mathbf{E}(r_1) + \sum_{s’}\gamma \Pr(s’ | s, a)V(s’)$

$\frac{\partial Q(s, a)}{\partial \theta} = \sum_{s’}\gamma\Pr(s’ | s, a)\frac{\partial V(s')}{\partial \theta}$ ( $a_0$ がgivenなので $r_1$ は $\theta$ に依存せず $\mathbf{E}(r_1)$ は消えます)

この求めた $\frac{\partial Q(s, a)}{\partial \theta}$ を代入し、再帰的に $\frac{\partial V(○)}{\partial \theta}$ に代入をしていくと以下のようになります. ただし $f(s) = \sum_{a}\frac{\partial \pi(a | s)}{\partial \theta}Q(s, a)$ とおきました.

$\frac{\partial V(s)}{\partial \theta}$

$= \sum_{a}\frac{\partial \pi(a | s)}{\partial \theta}Q(s, a) + \sum_{a}\pi(a | s)\sum_{s’}\gamma\Pr(s’ | s, a)\frac{\partial V(s')}{\partial \theta}$

$= f(s) + \sum_{a}\pi(a | s)\sum_{s’}\gamma\Pr(s’ | s, a)\frac{\partial V(s')}{\partial \theta}$

$= f(s) + \sum_{a}\pi(a | s)\sum_{s’}\gamma\Pr(s’ | s, a)( f(s’) + \sum_{a’}\pi(a’ | s')\sum_{s’’}\gamma\Pr(s’’ | s’, a')\frac{\partial V(s'')}{\partial \theta} )$

$= f(s) + \sum_{a}\sum_{s’}\gamma\pi(a | s)\Pr(s’ | s, a)f(s') + \sum_{a}\sum_{s’}\sum_{a'}\sum_{s’'}\gamma\pi(a | s)\Pr(s’ | s, a)\pi(a' | s')\Pr(s’' | s', a’)f(s’') + ...$

この再帰的な計算を無限に繰り返すと以下のようになります. ただし、式中のs, s', s'', ...を全部xで総称し、sからkステップでxに遷移する確率を $\Pr(s \rightarrow x, k)$ としました.

$\frac{\partial V(s)}{\partial \theta} = \sum_{x}\sum_{k=0}^{\infty}\gamma^k\Pr(s \rightarrow, k)f(s)$

ここで、 $J(\theta)$ は定義より $\frac{\partial V(s_0)}{\partial \theta}$ であるので

$\frac{\partial J(\theta)}{\partial \theta} = \frac{\partial V(s_0)}{\partial \theta}$

$= \sum_{s}\sum_{k=0}^{\infty}\gamma^k\Pr(s_0 \rightarrow s, k)f(s)$

$= \sum_{s}\sum_{k=0}^{\infty}\gamma^k\Pr(s_0 \rightarrow s, k)\sum_{a}\frac{\partial \pi_{\theta}(a|s)}{\partial \theta}Q(s, a)$

$s_0$ からkステップでsになる確率 $\Pr(s_0 = \rightarrow s, k)$ と $s_t$ がsである確率 $\Pr(s_t = s | s_0, \theta)$ は同じなので以下のように変形でき、方策勾配定理が導かれます.

$\frac{\partial J(\theta)}{\partial \theta}$

$= \sum_{s}\sum_{k=0}^{\infty}\gamma^k\Pr(s_t = s | s_0 ; \theta)\sum_{a}\frac{\partial \pi_{\theta}(a | s)}{\partial \theta}Q(s, a)$

$= \sum_{s}d(s)\sum_{a}\frac{\partial \pi_{\theta}(a | s)}{\partial \theta}Q(s, a)$

1.3) 勾配の近似

平均報酬でJを定義した場合では、 $d(s)$ は定常分布を表すので、 $\frac{\partial J(\theta)}{\partial \theta}$ を以下のように変形できます.

$\frac{\partial J(\theta)}{\partial \theta}$

$= \sum_{s}d(s)\sum_{a}\frac{\partial \pi_{\theta}(a | s)}{\partial \theta}Q(s, a)$

$= \sum_{s}\sum_{a}\pi_{\theta}(a|s)d(s)\frac{1}{\pi_{\theta}(a|s)}\frac{\partial \pi_{\theta}(a | s)}{\partial \theta}Q(s, a)$

$= \mathbf{E}(\frac{1}{\pi_{\theta}(a|s)}\frac{\partial \pi_{\theta}(a | s)}{\partial \theta}Q(s, a))$

$= \mathbf{E}(\frac{\partial \log\pi_{\theta}(a | s)}{\partial \theta}Q(s, a))$

この形が「方策勾配定理」と紹介されることが多く、実践上でもこの形の方策勾配定理を用います. なお、割引報酬和でJを定義した場合でも、この形の方策勾配定理を導けることがわかっています.

さて、この勾配を解析的に求めることはできないので、stochasticな方策 $\pi_{\theta}$ に基づき行動して得られたサンプルデータを利用してこれを近似しなくてはなりません.

agentがstochasticな方策 $\pi_{\theta}$ にしたがって、Tステップの行動をMエピソードだけ行ったとき、モンテカルロ近似により以下のように勾配を求めることができます.

$\frac{\partial J(\theta)}{\partial \theta} \simeq \frac{1}{M} \sum_{m=0}^{M-1} \frac{1}{T} \sum_{t=0}^{T-1} \frac{\partial \log\pi_{\theta}(a_t^m | s_t^m)}{\partial \theta} Q(s_t^m, a_t^m)$

1.4) 実装

ここまでの導出で得られた、近似版の方策勾配定理を用いて、強化学習タスクを実装してみます. 今回はAtari2600のゲームの内の一つ、Pongをうまくプレイするagentをつくるタスクを書きました.

特徴をかいつまむと

10エピソードに渡って ${\displaystyle\frac{\partial J(\theta)}{\partial \theta} }$ の和をとったのち、その勾配方向に $\theta$ を更新している.
パラメータ $\theta$ の更新にはRMSProp(直近で大きく更新した方向には、更新量が小さくなるようにする手法)を用いている.

といったアルゴリズムになっています.

入力データには前処理をした画像のraw-pixelを用いていますが、畳み込みニューラルネットワークではなく、通常のニューラルネットワークを用いています. 畳み込みニューラルネットワークを用いるとさらに性能が良くなるはずです.

ソースコードは以下のリポジトリにおいてあります.

github.com

1.5) 行動価値の推定

方策勾配の式をみてみると、勾配を求めるためには未知の行動価値関数を評価しなくてはならないことがわかります.

$\frac{\partial J(\theta)}{\partial \theta} \simeq \frac{1}{M} \sum_{m=0}^{M-1} \frac{1}{T} \sum_{t=0}^{T-1} \frac{\partial \log\pi_{\theta}(a_t^m | s_t^m)}{\partial \theta} Q(s_t^m, a_t^m)$

もっとも簡単な近似として知られているのが、 $Q^{\pi}(s_t^m, a_t^m)$ を即時報酬 $r(s_t^m, a_t^m, s_{t+1}^m)$ に置き換えてしまうアプローチです. この近似によるアルゴリズムをREINFORCEアルゴリズム[Williams, 1992]とよびます. これはちょっと荒すぎる近似であり、あまりいい性能もでないことから、大きな注目は浴びませんでした.