deterministic_policy_gradient_proof

Proof of Deterministic Policy Gradient

Notations

Since the policy is deterministic,

$$a=\mu (s,\theta )\doteq \mu (s)$$

• $\mu (s)$ is the deterministic policy function.
• $\theta$ is the parameter of the policy function.
• $\mu$ is a mapping from $\mathcal{S}$ to $\mathcal{A}$.

$\mu$ v.s. $\pi$

So far, we use the notation $\pi (a|s)$ to represent the stochastic policy,

• $\pi (a|s)$ is the probability of taking action $a$ in state $s$.
• input: one state $s$, output: a probability distribution over actions.

and now we use $\mu (s)$ to represent the deterministic policy.

• $\mu (s)$ is just the action taken in state $s$.
• input: one state $s$, output: one action.

we have

$$v_{\mu }(s)=q_{\mu }(s,a)=q_{\mu }(s,\mu (s))$$

Action value

Remember the stochastic case: $v_{\pi }(s)={\mathbb{E}}_{A\sim \pi }[q_{\pi }(s,A)]$, refer to action value, because the action is sampled from the stochastic policy, and now the policy is deterministic (or one-hot), so the action is fixed. (the ${\sum }_a$ operation can be removed)

Theorem of DPG

As we mentioned before, in the discounted case where $\gamma \in (0,1)$, the gradient of $J(\theta )$ is

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& =\sum _{s\in \mathcal{S}}{\rho }_{\mu }(s){\nabla }_{\theta }\mu (s)({\nabla }_a{q}_{\mu }(s,a)){|}_{a=\mu (s)}\\ & ={\mathbb{E}}_{S\sim {\rho }_{\mu }}\left[{\nabla }_{\theta }\mu (S)({\nabla }_a{q}_{\mu }(S,a)){|}_{a=\mu (S)}\right]\end{array}$$

Here ${\rho }_{\mu }$ is the state distribution under policy $\mu$.

Derivation of DPG

$$\begin{array}{rl}{\nabla }_{\theta }{v}_{\mu }(s)& ={\nabla }_{\theta }{q}_{\mu }(s,a)=\frac{\mathrm{d}{q}_{\mu }(s,a)}{\mathrm{d}\theta }\\ & =\frac{\mathrm{d}{q}_{\mu }(s,a)}{\mathrm{d}s}\frac{\mathrm{d}s}{\mathrm{d}\theta }+\frac{\mathrm{d}{q}_{\mu }(s,a)}{\mathrm{d}a}\frac{\mathrm{d}a}{\mathrm{d}\theta }\\ & =({\nabla }_{\theta }{q}_{\mu }(s,a)){|}_{a=\mu (s)}+({\nabla }_a{q}_{\mu }(s,a)){|}_{a=\mu (s)}{\nabla }_{\theta }\mu (s)\\ & =({\nabla }_{\theta }\left(r(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)v_{\mu }(s^{\prime })\right)){|}_{a=\mu (s)}+({\nabla }_a{q}_{\mu }(s,a)){|}_{a=\mu (s)}{\nabla }_{\theta }\mu (s)\\ & =\left(0+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a){\nabla }_{\theta }{v}_{\mu }(s^{\prime })\right){|}_{a=\mu (s)}+({\nabla }_a{q}_{\mu }(s,a)){|}_{a=\mu (s)}{\nabla }_{\theta }\mu (s)\\ & =\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,\mu (s)){\nabla }_{\theta }{v}_{\mu }(s^{\prime })+\underset{u(s)}{\underbrace{({\nabla }_a{q}_{\mu }(s,a)){|}_{a=\mu (s)}{\nabla }_{\theta }\mu (s)}}\end{array}$$

Turn in to matrix form:

• $n=|\mathcal{S}|$, the size of state space
• $\theta \in {\mathbb{R}}^k$, $k$ is the dimension of parameter $\theta$
• ${\nabla }_{\theta }{v}_{\mu }(s)$ is a (k,1) vector when $s$ is fixed, then ${\nabla }_{\theta }{v}_{\mu }$ is a (n,k) matrix
• $p(s^{\prime }|s,\mu (s))$ is a (n,1) vector when $s$ is fixed, then $P_{\mu }$ is a (n,n) matrix
• $u(s)$ is a (k,1) vector when $s$ is fixed, then $u$ is a (n,k) matrix

Then we have:

$$\begin{array}{rl}{\nabla }_{\theta }{v}_{\mu }& =\gamma P_{\mu }{\nabla }_{\theta }{v}_{\mu }+u\\ \Rightarrow {\nabla }_{\theta }{v}_{\mu }& =(I_n-\gamma P_{\mu }{)}^{-1}u=\left(\sum _{k=0}^{\infty }(\gamma P_{\mu }{)}^k\right)u\end{array}$$

TL;DR

• just denote $\mu$ as a one-hot (n,m) vector, same as the shape of $\pi$ before
• $P_{\mu }=\mu @P_s\in {\mathbb{R}}^{n\times n}$, same as the shape of $P_{\pi }$ before

Then we can directly use the result in the policy gradient proof:

$$\begin{array}{rl}\mathrm{d}{v}_{\pi }& =(I-\gamma P_{\pi }{)}^{-1}\mathrm{d}\pi @q_{\pi }\\ & =\left(\sum _{k=0}^{\infty }(\gamma P_{\pi }{)}^k\right)\mathrm{d}\pi @q_{\pi }\end{array}$$

Just replace $\pi$ by $\mu$, and divide by the factor $\mathrm{d}\theta$

$$\begin{array}{rl}{\nabla }_{\theta }{v}_{\mu }& =\frac{\mathrm{d}{v}_{\mu }}{\mathrm{d}\theta }=\left(\sum _{k=0}^{\infty }(\gamma P_{\mu }{)}^k\right)\frac{\mathrm{d}\mu @q_{\mu }}{\mathrm{d}\theta }\end{array}$$

And we know that actually, when $\mu (s)$ is deterministic and just return one value, our $\mathrm{d}\mu @q_{\mu }/\mathrm{d}\theta$ element-wise form is

$$\begin{array}{rl}\frac{\mathrm{d}q(s,\mu (s))}{\mathrm{d}\theta }& =\frac{\mathrm{d}q(s,a)}{\mathrm{d}a}{|}_{a=\mu (s)}\frac{\mathrm{d}a}{\mathrm{d}\theta }\\ & =({\nabla }_{a}q(s,a)){|}_{a=\mu (s)}{\nabla }_{\theta }\mu (s)\end{array}$$

Then we have the deterministic policy gradient, unified form:

$$\boxed{\nabla J(\theta )=C\rho \nabla \mu @q_{\mu }}$$

Element-wise form:

$${\nabla }_{\theta }J(\theta )=C\sum _{s\in \mathcal{S}}{\rho }_{\mu }(s){\nabla }_{\theta }\mu (s)({\nabla }_a{q}_{\mu }(s,a)){|}_{a=\mu (s)}$$

• ${\rho }_{\mu }$ is the state distribution under policy $\mu$
• $C=1/(1-\gamma )$