policy gradient theorem

Policy gradient theorem or, likelihood ratio policy gradient, is a theorem that transforms policy gradient into a sample based estimation problem. The derivation is the following.

We want to optimize the overall utility $U$ of using a policy $\pi$ over a state-action sequence, a trajectory, $\tau$, where $\tau =s_0,u_0,...,s_H,u_H$. We can express the utility as:

$$U(\theta )=E[\sum _{t=0}^{H}R(s_t,u_t);{\pi }_{\theta }]$$

Given an expectation under a distribution, we can turn it into a sum over all possible events weighted by their probabilities (the definition of expectation). In our case, we can rewrite this expectation in terms of a probability function, $P$, of a trajectory, $\tau$, under policy ${\pi }_{\theta }$ and the corresponding reward, $R$:

$$U(\theta )=E[\sum _{t=0}^{H}R(s_t,u_t);{\pi }_{\theta }]=\sum _{\tau }P(\tau ;\theta )R(\tau )$$

The goal is to find the parameter $\theta$ that gives the maximum utility:

$$\underset{\theta }{\max }U(\theta )=\underset{\theta }{\max }\sum _{\tau }P(\tau ;\theta )R(\tau )$$

Next, we will use gradient optimization to solve this problem. We take the gradient of $U$ with respect to $\theta$:

$${\nabla }_{\theta }U(\theta )={\nabla }_{\theta }\sum _{\tau }P(\tau ;\theta )R(\tau )$$

Based on the linearity of gradient, the gradient of sum is the sum of gradient. Therefore, we have:

$${\nabla }_{\theta }\sum _{\tau }P(\tau ;\theta )R(\tau )=\sum _{\tau }{\nabla }_{\theta }P(\tau ;\theta )R(\tau )$$

Here, we want to have a weighted sum so that we can sample the trajectories instead of enumerate all trajectories. To get there, we multiply and divide by $P(\tau ;\theta )$:

$$\sum _{\tau }\frac{P(\tau ;\theta )}{P(\tau ;\theta )}{\nabla }_{\theta }P(\tau ;\theta )R(\tau )$$

Notice now we have a derivative of a $log$ function:

$${\nabla }_{\theta }\log f(x)=\frac{1}{f(x)}{\nabla }_{\theta }f(x)$$

Our gradient becomes:

$$\sum _{\tau }\frac{P(\tau ;\theta )}{P(\tau ;\theta )}{\nabla }_{\theta }P(\tau ;\theta )R(\tau )=\sum _{\tau }P(\tau ;\theta ){\nabla }_{\theta }\text{log}P(\tau ;\theta )R(\tau )$$

Here, we can apply the definition of expectation again, now in reverse:

$$\sum _{\tau }P(\tau ;\theta ){\nabla }_{\theta }\text{log}P(\tau ;\theta )R(\tau )=E_{\tau \sim P(\tau ;\theta )}[{\nabla }_{\theta }\text{log}P(\tau ;\theta )R(\tau )]$$

which gives us the expected value of a function, ${\nabla }_{\theta }\text{log}P(\tau ;\theta )R(\tau )$, under distribution $P(\tau ;\theta )$. This allows us to use a sample-based estimate of $P(\tau ;\theta )$ instead of enumerating all possible trajectories. Using an empirical estimate of the expectation with $m$ samples, we get:

$${\nabla }_{\theta }U(\theta )\approx \hat{g}=\frac{1}{m}\sum _{i=1}^m{\nabla }_{\theta }\log P({\tau }^{(i)};\theta )R({\tau }^{(i)})$$