Policy gradient methods

In policy based algorithms:

• There is no value function during or after training
• We directly learn the policy, as opposed to value based algorithms where we implicitly learn the policy via a learnt value function

Advantages of policy based algorithms:

• Better for action spaces that are huge or continuous
  In Q-learning, at each step we took a max over the actions, this is expensive for action spaces that are huge or continuous

Disadvantage:

• Can get stuck in local optima

Policy based methods are optimization problems, where we aim to maximize the policy for a given objective function.

In policy gradient methods, the policy is parameterized, and apply gradient ascent to find local maxima based on the objective function.

Some examples of objecitve functions:

• If the problem is episodic, meaning that it always starts at state $s_1$ and terminates eventually and restarts at $s_1$, then the objective function of taking the state value of the starting state makes sense:

$$J_1(\theta )=V^{{\pi }_{\theta }}\left(s_1\right)={\mathbb{E}}_{{\pi }_{\theta }}\left[v_1\right]$$

• For continuing environments, that is an environment that does not terminate and restert, but keeps on rolling, the average value of the states weighted by their stationary distribution works:

$$J_{avV}(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)V^{{\pi }_{\theta }}(s)$$

• Still for continuing environments, we can also take the average reward after a single step and weigh it by the stationary distibution:

$$\begin{array}{c}{J}_{avR}(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)\sum _a{\pi }_{\theta }(s,a){\mathcal{R}}_s^a\end{array}$$

If we can analytically calculate the gradient of the policy, using autograd software (pytorch, tensorflow, tinygrad), we can easily apply gradient ascent.

Note, that in the following equations we will see ${\nabla }_{\theta }\log {\pi }_{\theta }(s,a)$, before we get confused we explain where this part comes from:

$$\begin{array}{c}\begin{array}{rl}{\nabla }_{\theta }{\pi }_{\theta }(s,a)& ={\pi }_{\theta }(s,a)\frac{{\nabla }_{\theta }{\pi }_{\theta }(s,a)}{{\pi }_{\theta }(s,a)}\\ & ={\pi }_{\theta }(s,a){\nabla }_{\theta }\log {\pi }_{\theta }(s,a)\end{array}\end{array}$$

As you can see, this is just an algebraic manipulation.

Policy gradient theorem
For any differentiable policy ${\pi }_{\theta }$, for any policy objective function $J$, the policy gradient is the following:

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