Natural Policy Gradient

Source is the same as Policy Gradient

If you think about how we optimize gradient normally it actually doesn’t make much sense: some parameters change probabilities a lot more than others, but we scale them the same (vanilla SGD)

The optimization can be seen as a constraint optimization problem: $\begin{array}{r}{\theta }^{\prime }\leftarrow \arg \underset{{\theta }^{\prime }}{\max }({\theta }^{\prime }-\theta {)}^T{\nabla }_{\theta }J(\theta )\text{ s.t. }\underset{\text{controls how far we go}}{\underbrace{\Vert {\theta }^{\prime }-\theta {\Vert }^2\le ϵ}}\end{array}$ In the 2D case, that’s basically saying how far we should go on the x-axis so that the first-order gradient times $\delta x$ (which gives us y) descends the most. We do not want to go too far because the first-order approximation is only valid within a small range.

Really we should be constrained by “output does not change too much”, not “all params in all dims does not change too much”. $\begin{array}{rl}& {\theta }^{\prime }\leftarrow \arg \underset{{\theta }^{\prime }}{\max }({\theta }^{\prime }-\theta {)}^T{\nabla }_{\theta }J(\theta )\text{ s.t. }D({\pi }_{{\theta }^{\prime }},{\pi }_{\theta })\le ϵ\\ & \text{parameterization-independent divergence measure}\\ & \text{usually KL-divergence: }{D}_{\text{KL}}({\pi }_{{\theta }^{\prime }}\Vert {\pi }_{\theta })=E_{{\pi }_{{\theta }^{\prime }}}[\log {\pi }_{\theta }-\log {\pi }_{{\theta }^{\prime }}]\\ & D_{\text{KL}}({\pi }_{{\theta }^{\prime }}\Vert {\pi }_{\theta })\approx ({\theta }^{\prime }-\theta {)}^T\mathbf{F}({\theta }^{\prime }-\theta )\mathbf{F}=E_{{\pi }_{\theta }}[{\nabla }_{\theta }\log {\pi }_{\theta }(\mathbf{a}|\mathbf{s}){\nabla }_{\theta }\log {\pi }_{\theta }(\mathbf{a}|\mathbf{s}{)}^T]\\ & \text{Fisher-information matrix}\end{array}$ So here comes KL Divergence, if we Taylor expand that, we’ll see the first two terms are all 0, and it can be approxiamated just by the second term, the Fisher-information matrix, and it’s the Reimannian metric on the manifold of probability distributions. $\begin{array}{rl}{\theta }^{\prime }& \leftarrow \arg \underset{{\theta }^{\prime }}{\max }({\theta }^{\prime }-\theta {)}^T{\nabla }_{\theta }J(\theta )\text{ s.t. }\Vert {\theta }^{\prime }-\theta {\Vert }_{\mathbf{F}}^2\le ϵ\\ \theta & \leftarrow \theta +\alpha {\mathbf{F}}^{-1}{\nabla }_{\theta }J(\theta )\end{array}$ We’ll see later how TRPO is based on this idea.