policy gradient

The goal of reinforcement learning is to find an optimal behavior strategy for the agent to obtain optimal rewards. Policy gradient methods target at modeling and optimizing the policy directly (as opposed to value-based methods that model a value function and derive the policy from it). The policy is usually modeled with a parameterized function respect to $\theta$, ${\pi }_{\theta }(s|a)$ The value of the reward (objective) function depends on this policy and then various algorithms can be applied to optimize for the best reward.
The reward function is defined as:

$$J(\theta )=\sum _{s\in \mathcal{S}}{d}^{\pi }(s)V^{\pi }(s)=\sum _{s\in \mathcal{S}}{d}^{\pi }(s)\sum _{a\in \mathcal{A}}{\pi }_{\theta }(a|s)Q^{\pi }(s,a)$$

where $d^{\pi }(s)={\lim }_{t\to \infty }P(s_t=s\mid s_0,{\pi }_0)$ is the stationary distribution of the markov chain for ${\pi }_{\theta }$ (on-policy state distribution under $\pi$).
Using gradient ascent, we can move $\theta$ toward the direction suggested by the gradient ${\nabla }_{\theta }J(\theta )$ to find the $\theta$ that maximizes the return.

Via the policy gradient theorem, we can drop $d^{\pi }$ from the gradient (i.e. don’t need to know / differentiate the environment).
We end up with the vanilla policy gradient:

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{\pi }[Q^{\pi }(s,a){\nabla }_{\theta }\ln {\pi }_{\theta }(a\mid s)]$$

See vanilla policy gradient for a more detailed explanation of the most basic policy gradient algorithm / how we derive the gradient of this objective. Below is a more general formulation of different policy gradients, based on the High-Dimensional Continuous Control Using Generalized Advantage Estimation paper.

Policy gradient methods

Let $s_0$ be sampled from initial distribution ${\rho }_0$. A trajectory $(s_0,a_0,s_1,a_1,\dots )$ is generated by:

• Sampling actions: $a_t\sim \pi (a_t\mid s_t)$
• Sampling states: $s_{t+1}\sim P(s_{t+1}\mid s_t,a_t)$

until reaching a terminal state. At each timestep, a reward $r_t=r(s_t,a_t,s_{t+1})$ is received. The goal is to maximize the expected total reward ${\sum }_{t=0}^{\infty }{r}_t$ (assumed to be finite).

Policy gradient methods maximize the expected total reward by estimating the gradient $g$:

$$g:={\nabla }_{\theta }\mathbb{E}\left[\sum _{t=0}^{\infty }{r}_t\right]\approx \mathbb{E}\left[\sum _{t=0}^{\infty }{\Psi }_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)\right]$$

where ${\Psi }_t$ can take various forms, to estimate the contribution of each action to the total reward:

${\sum }_{t=0}^{\infty }{r}_t$ … Total trajectory reward
${\sum }_{t^{\prime }=t}^{\infty }{r}_{t^{\prime }}$ … Future reward after action $a_t$
${\sum }_{t^{\prime }=t}^{\infty }{r}_{t^{\prime }}-b(s_t)$ … Baselined future reward after action $a_t$
$Q^{\pi }(s_t,a_t)$ … state-action value
$A^{\pi }(s_t,a_t)$ … advantage function
$r_t+V^{\pi }(s_{t+1})-V^{\pi }(s_t)$ … TD residual

where
$V^{\pi }(s_t):={\mathbb{E}}_{s_{t+1:\infty },a_{t:\infty }}\left[{\sum }_{l=0}^{\infty }{r}_{t+l}\right]$ … state-value; expected total reward from state $s_t$
$Q^{\pi }(s_t,a_t):={\mathbb{E}}_{s_{t+1:\infty },a_{t+1:\infty }}\left[{\sum }_{l=0}^{\infty }{r}_{t+l}\right]$ … state-action value; expected total reward from state $s_t$ and action $a_t$
$A^{\pi }(s_t,a_t):=Q^{\pi }(s_t,a_t)-V^{\pi }(s_t)$

Choosing the advantage function for ${\Psi }_t$ yields almost the lowest possible variance, though in practice, the advantage function is not known and must be estimated. This statement can be intuitively justified by the following interpretation of the policy gradient: that a step in the policy gradient direction should increase the probability of better-than-average actions and decrease the probability of worse-than-average actions. The advantage function, by it’s definition measures whether or not the action is better or worse than the policy’s default behavior. Hence, we should choose ${\Psi }_t$ to be the advantage function, so that the gradient term${\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$ points in the direction of increased ${\pi }_{\theta }(a_t\mid s_t)$ if and only if $A^{\pi }(s_t,a_t)>0$.

References

$\theta$, but also inputs like $(s,a)$ are often ommitted in notation.

PPO

https://lilianweng.github.io/posts/2018-04-08-policy-gradient/