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)})$$

In the above function, there is no gradient is taken for the reward function, which means the reward function can be discontinuous or unknown.

Next we will further expand the probability, $P$, into a temporal based function of state and action. We write out the expression for $P$, which is probability of future state given the present state and action, times policy, ${\pi }_{\theta }$, which is the probability of action given state:

$${\nabla }_{\theta }\log P({\tau }^{(i)};\theta )={\nabla }_{\theta }\log [\prod _{t=0}^{H}P(s_{t+1}^{(i)}|s_t^{(i)},u_t^{(i)})\cdot {\pi }_{\theta }(u_t^{(i)}|u_s^{(i)})]$$

We use use some log rules to separate the product:

$$log\prod PQ=\sum \log (PQ)=\sum \log P+\sum \log Q$$

and we get:

$$\begin{array}{rl}{\nabla }_{\theta }\log P({\tau }^{(i)};\theta )& ={\nabla }_{\theta }[\sum _{t=0}^H\log P(s_{t+1}^{(i)}|s_t^{(i)},u_t^{(i)})+\sum _{t=0}^H\log {\pi }_{\theta }(u_t^{(i)}|u_s^{(i)})]\\ & =[\sum _{t=0}^H{\nabla }_{\theta }\log P(s_{t+1}^{(i)}|s_t^{(i)},u_t^{(i)})+\sum _{t=0}^H{\nabla }_{\theta }\log {\pi }_{\theta }(u_t^{(i)}|u_s^{(i)})]\end{array}$$

since probability $P$ isn’t a function of $\theta$, it’s gradient is 0. Thus we get:

$${\nabla }_{\theta }\log P({\tau }^{(i)};\theta )=\sum _{t=0}^H{\nabla }_{\theta }\log {\pi }_{\theta }(u_t^{(i)}|s_t^{(i)})$$

The distribution function, $P$, disappears. This gives us the final form of the policy gradient theorem:

$${\nabla }_{\theta }U(\theta )\approx \hat{g}=\frac{1}{m}\sum _{i=1}^m{\nabla }_{\theta }\log {\pi }_{\theta }(u_t^{(i)}|s_t^{(i)})R({\tau }^{(i)})$$

This tells us to improve the overall utility, move the policy in the direction tht make the high reward more likely.

Note

Policy gradient theorem says that to improve the overall utility, move the policy in the direction tht make the high reward more likely.