方策勾配法

強化学習の目的は「長期的な報酬を最大化する方策を求めること」でした．

方策勾配法は，方策をパラメータを持った関数として定義し，方策の価値が最大となるパラメータを勾配法で求める方法です．

パラメータ $\theta$ を持つ方策 $\pi_{\theta}$ の価値を $J(\theta)$ とします．方策の価値の勾配を $\nabla_{\theta} J(\theta)$ ，学習率を $\alpha$ とすると，パラメータの更新式は次式のようになります．

$\theta'=\theta+\alpha \nabla_{\theta} J(\theta)$

次に $\nabla_{\theta} J(\theta)$ の求め方について説明します．結果から示すと， $\nabla_{\theta} J(\theta)$ はこうなります．

$\nabla_{\theta} J(\theta) = \mathbb{E} _{d,\pi} [ \nabla_{\theta} \ln \pi_{\theta}(a|s) Q^{\pi_{\theta}}(s,a)$ ]

これを方策勾配定理と呼びます．([Sutton+, 1999] Policy Gradient Methods for Reinforcement Learning with Function Approximation)

方策勾配定理の導出

方策の価値を状態価値関数とします．

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

状態価値関数を $\theta$ で偏微分すると，

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

ここで，

$Q^{\pi_{\theta}}(s,a)=\sum_{s'} P(s'|s,a) \left( R(s,a,s') + \gamma V^{\pi_{\theta}}(s') \right)$

より

$\nabla_{\theta} Q^{\pi_{\theta}}(s,a) = \gamma \sum_{s'} P(s'|s,a) \nabla_{\theta} V^{\pi_{\theta}}(s')$

を代入して

$\nabla_{\theta} V^{\pi_{\theta}}(s) = \sum_{a} \nabla_{\theta} \pi_{\theta}(a|s) Q^{\pi_{\theta}}(s,a) + \gamma \sum_{a} \pi_{\theta}(a|s) \sum_{s'} P(s'|s,a) \nabla_{\theta} V^{\pi_{\theta}}(s')$

$f(s) = \sum_{a} \nabla_{\theta} \pi_{\theta}(a|s) Q^{\pi_{\theta}}(s,a)$ とすると，

$\nabla_{\theta} V^{\pi_{\theta}}(s) = f(s) + \gamma \sum_{a} \pi_{\theta}(a|s) \sum_{s'} P(s'|s,a) \nabla_{\theta} V^{\pi_{\theta}}(s')$

となり， $\nabla_{\theta} V^{\pi_{\theta}}(s)$ が再帰的な形になります．もう1ステップ進めると，

$\nabla_{\theta} V^{\pi_{\theta}}(s) = f(s) + \gamma \sum_{a} \pi_{\theta}(a|s) \sum_{s'} P(s'|s,a) \left(f(s') + \gamma \sum_{a'} \pi_{\theta}(a'|s') \sum_{s''} P(s''|s',a') \nabla_{\theta} V^{\pi_{\theta}}(s'') \right)$

ここで， $P(s \rightarrow s', t)$ を $t$ ステップで $s$ から $s'$ に遷移する確率とすると，

$\nabla_{\theta} V^{\pi_{\theta}}(s) = f(s)+\gamma P(s \rightarrow s', 1) f(s') + \gamma^2 P(s \rightarrow s'', 2)f(s'')+\cdots$

$= \sum_{s} \sum_{t=0}^{\infty} \gamma^t P(s \rightarrow s', t) f(s')$

$= \sum_{s'} \sum_{t=0}^{\infty} \gamma^t P(s \rightarrow s', t) \sum_{a} \nabla_{\theta} \pi_{\theta}(a|s') Q^{\pi_{\theta}}(s',a)$

これで，価値の勾配を示せることができました．もう少し正確には，方策の価値は「初期状態 $s_0$ で方策 $\pi_{\theta}$ に従って行動したときの価値」なので $J(\theta)=V^{\pi_{\theta}}(s_0)$ となります．

また， $\sum_{s'} \sum_{t=0}^{\infty} \gamma^t P(s \rightarrow s', t)$ を初期状態 $s_0$ から状態 $s$ へと遷移する確率に書き換えると， $\sum_{s} \sum_{t=0}^{\infty} \gamma^t P(s_0 \rightarrow s, t)$ となり，これを $\sum_s d^{\pi_{\theta}}(s)$ とします．