1
$\begingroup$

I'm reading this paper on Natural Policy Gradient https://papers.nips.cc/paper/2073-a-natural-policy-gradient.pdf and have some questions regarding how it works.

I'm coming at this from an ML background and do not have a very strong math background so please bear with me. The argument that is being made is that, the gradient that is calculated in standard gradient descent is noncovariant. The definition that I've found of noncovariant is that (from what I can tell) if you reparameterize the policy but the output probability distribution is the same, you can get different directions of steepest descent?

To deal with this, the author looks to find a direction which is covariant using a particular metric tensor.

When looking to choose a $d\theta$ such that the distance between $\eta(\theta)$ and $\eta(\theta + d\theta)$ is maximized, solving gives us $$d\theta = \frac{1}{2 \lambda} G^{-1} \nabla \eta({\theta}) $$ where $G$ is a metric tensor which, in euclidean space, corresponds to the identity matrix.

My understanding of what a metric tensor is is very sketchy but as far as I can tell it's like a mapping from some parameter space to a distance-value according to some metric (?). To improve the optimization procedure he uses the Fisher Information Matrix $F$ instead of $G$.

The author says that the average reward is technically a function on the set of distributions $\pi_\theta$ rather than on the parameters $\theta$ themselves and suggests transforming the gradient $\nabla \eta(\theta)$ by $F(\theta)^{-1}$ instead since, instead, what we should be looking for is to improve the probability distribution directly.

I'm not entirely sure what exactly this transformation does? If I think about the gradient as just a general greatest rate of change and then transforming it by the metric tensor then I guess intuitively $d\theta$ will be the update that maximizes the informational difference (which seems to try and push the policy to be almost deterministic?). While I can buy this to some degree I'm having quite a bit of trouble understanding how these are going to be different in terms of how $\eta(\theta)$ changes. Is it possible that optimizing using policy gradient and natural gradient will simply arrive at the same solution if given enough time?

Hopefully someone can spot some glaring flaws in my understanding that might help me understand!

Thanks

$\endgroup$
2
$\begingroup$

This question applies more broadly for any gradient (stochastic or not) descent method as applied to a cost function defined on a space of distributions.

The reason for at least some of the confusion is that the concept of a gradient is often not taught well. The gradient of a function $f$ is supposed to be a vector that points in the direction of steepest ascent of $f$. This direction is found by computing $(\partial f/\partial x_1,...,\partial f/\partial x_n)^T$ only if $x_i$ are Cartesian coordinates in a Euclidean space. I will explain below how this generalizes to other cases, but let me first address why the generalization may be needed.

The point of natural metrics on spaces of distributions is that the Euclidean structure is unnatural. There are several ways to convince oneself of this unnaturalness: one is that one may freely reparametrize a distribution without changing it, and if we have Euclidean structure in one parametrization, we lose it if we go to another one (see below); parameters may have different physical units, or other constraints that preclude a Euclidean structure; the Euclidean structure leads to inefficient optimization paths. The Fisher information metric is a more natural metric on spaces of distributions because it is compatible with transformations of the state space (not just the parameter space). But in the context of the discussion below, it is just a special case; once we understand how to define a gradient for an arbitrary non-Euclidean metric, we can apply this to the Fisher information metric.

Next, let's try to understand why the "vector" of partial derivative does not correspond to a direction in the space. Let's look at a simple example in $\mathbb{R}^2$. Suppose we want to minimize the function $f(x,y)=x^2+2y^2$. Let's do the usual thing and use the following system of ODE's to get to the minimum $$\dot x=-\frac{\partial f}{\partial x}=-2x,$$ $$\dot y=-\frac{\partial f}{\partial y}=-4y.$$ Then we switch to polar coordinates: $x=r\cos\varphi$ and $y=r\sin\varphi$. In those coordinates, the function reads $f(r,\varphi)=r^2(1+\sin^2\varphi)$. If we do the same as above, we would write $$\dot r=-\frac{\partial f}{\partial r}=-2r(1+\sin^2\varphi),$$ $$\dot \varphi=-\frac{\partial f}{\partial \varphi}=-2r^2\cos\varphi\sin\varphi.$$

Now, one may check that the two trajectories, although they both converge to $x=y=0$, look different. What happened?

The important point to realize is that the "vector" of partial derivatives $(\partial f/\partial x,\partial f/\partial y)^T$ or $(\partial f/\partial r,\partial f/\partial \varphi)^T$ does not give directions, but rather acts on directions (tangent vectors) to see how $f$ locally changes in that direction. This can be made precise by considering a curve given by $x(t)$ and $y(t)$ (not necessarily a solution to the ODEs above) such that $x(0)=x_0$ and $y(t)=y_0$. The vector tangent $v$ to the curve at the point $p$ given by $x=x_0$ and $y=y_0$ (corresponding to $t=0$) is given by $v^x=\dot x(0)$ and $v^y=\dot y(0)$. Now if we compute the time derivative of $f$ evaluated along the curve at $t=0$, we get $$\frac{d}{dt}f(x(t),y(t))\Big\vert_{t=0}=\frac{\partial f}{\partial x}(x_0,y_0)\dot x(0)+\frac{\partial f}{\partial y}(x_0,y_0)\dot y(0)=(\partial f/\partial x,\partial f/\partial y)\begin{pmatrix}v_x\\v_y\end{pmatrix},$$ so we see that the partial derivatives form a dual vector that acts on the tangent vector to produce the directional derivative in the direction of the tangent vector. The result of the calculation also does not depend on higher-order behavior of the curve near $t=0$.

We can do the same calculation as above in polar coordinates. Let's pick a curve $r(t)$ and $\varphi(t)$ such that $r(0)=r_0$ and $\varphi(0)=\varphi_0$, as well as $\dot r(0)=v^r$ and $\dot\varphi(0)=v^{\varphi}$. In order for it to be the same curve (at least to first order at $t=0$), we have to have the relations $$x_0=r_0\cos\varphi_0, \quad y_0=r_0\sin\varphi_0,$$ $$v^x=\frac{\partial x}{\partial r}v^r+\frac{\partial x}{\partial \varphi}v^{\varphi}=\cos\varphi_0v^r-r_0\sin\varphi_0v^{\varphi},$$ $$ v^y=\frac{\partial y}{\partial r}v^r+\frac{\partial y}{\partial \varphi}v^{\varphi}=\sin\varphi_0v^r+r_0\cos\varphi_0v^{\varphi}.$$

Then we can write $$\frac{d}{dt}f(r(t),\varphi(t))\Big\vert_{t=0}=\frac{\partial f}{\partial r}(r_0,\varphi_0)\dot r(0)+\frac{\partial f}{\partial \varphi}(r_0,\varphi_0)\dot \varphi(0)=(\partial f/\partial r,\partial f/\partial \varphi)\begin{pmatrix}v_r\\v_{\varphi}\end{pmatrix},$$ and one may check that it gives the same result as in cartesian coordiantes because the components of $(\partial f/\partial r,\partial f/\partial \varphi)$ actually transform as $$ \frac{\partial f}{\partial r} = \frac{\partial x}{\partial r}\frac{\partial f}{\partial x}+\frac{\partial y}{\partial r}\frac{\partial f}{\partial y},\quad \frac{\partial f}{\partial \varphi} = \frac{\partial x}{\partial \varphi}\frac{\partial f}{\partial x}+\frac{\partial y}{\partial \varphi}\frac{\partial f}{\partial y}.$$

To go one step further, we can actually regard the vector $v$ as an abstract object attached to the point $p$. Likewise, the dual vector $df_p$ (differential of $f$ at $p$) is an object in its own right. We may express $v$ and $df_p$ in different coordinates as $$ v=v^x\partial_x|_p+v^y\partial_y|_p=v^r\partial_r|_p+v^{\varphi}\partial_{\varphi}|_p,$$ $$ df_p=\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy=\frac{\partial f}{\partial r}dr+\frac{\partial f}{\partial \varphi}d\varphi.$$ The computation above may be written in a coordinate-invariant way as $$\frac{d}{dt}f(p(t))\Big\vert_{t=0}=vf=df_p(v),$$ reflecting once again the duality of $v$ and $df_p$.

Ok, now that we understand the distinction between directions (tangent vectors) and their duals, of which $(\partial f/\partial x,\partial f/\partial y)$ or $(\partial f/\partial r,\partial f/\partial \varphi)$ are particular examples (a general dual vector does not need to come from a function, at least not globally), we may consider the problem of defining a gradient operator.

The gradient applied to a function $f$ at $p$ should produce a tangent vector that in some sense maximizes the local change in $f$ when walking in the direction of the tangent vector. In order for this to make sense, we have to constrain the length of the vector (otherwise the target of this maximization is unbounded). Thus, in order to define a gradient, we have to have a way of measuring the length of vectors. This is called a Riemannian metric, which is a way of specifying at each point a scalar product such that we can compute $\langle v,w\rangle_p$ for any two vectors $v,w$ at $p$, in a way that depends smoothly on the point. We may then define a steepest direction of $f$ at $p$ as the unit vector that maximizes the directional derivative of $f$ at $p$

$$sf_p = \arg \max_{\langle v,v\rangle_p=1} vf= \arg \max_{\langle v,v\rangle_p=1} df_p(v), \tag1$$ and then we define the gradient as a scaled version that also takes into account how fast $f$ actually changes in that direction. We therefore multiply $sf_p$ by the directional derivative of $f$ in the direction of $sf_p$: $$\text{grad} f_p=df_p(sf_p)\;sf_p.$$

It may then be shown that $\text{grad} f_p$ satisfies $$\langle \text{grad} f_p, v \rangle_p = df_p(v) \tag2$$ for every tangent vector $v$. By the non-degeneracy of the scalar product, this then uniquely defines $\text{grad} f_p$ in terms of the inverse metric tensor written in the OP. In order to show (2), we may write down a Lagrangian for the constrained optimization problem (1): $$\mathcal{L}(v)=df_p(v)+\lambda(\langle v,v\rangle_p-1),$$ where $\lambda$ is some Lagrange multiplier. The first variation of this reads $$\mathcal{L}(v+\delta v)-\mathcal{L}(v)=df_p(\delta v)+2\lambda \langle v,\delta v\rangle_p = 0, \quad \forall\delta v,$$ from which we obtain (by setting $v=\delta v=sf_p$) that $-2\lambda=df_p(sf_p)$ and then by plugging this back into the first variation for $v=sf_p$, $$\langle \text{grad} f_p, \delta v \rangle_p=df_p(sf_p)\langle sf_p, \delta v \rangle_p = df_p(\delta v), \quad \forall\delta v.$$

We may now come back to the example using cartesian and polar coordinates. The first observation is that if we use a Euclidean scalar product to measure the length of a vector in cartesian coordinates, it becomes non-Euclidean in polar coordinates in view of the transformation of the vector components from cartesian to polar:

$$\langle v,v \rangle_p=(v^x)^2+(v^y)^2=(v^r)^2+r^2 (v^{\varphi})^2.$$

This means that while in cartesian coordinates $(\partial f/\partial x,\partial f/\partial y)^T$ is the gradient, this property does not hold in polar coordinates! Instead, we have from (2) that $\text{grad} f_p=(\text{grad} f_p)^r\partial_r|_p+(\text{grad} f_p)^{\varphi}\partial_{\varphi}|_p$ such that

$$(\text{grad} f_p)^r v^r+ r^2 (\text{grad} f_p)^{\varphi} v^{\varphi}=\frac{\partial f}{\partial r}(p)v^r+\frac{\partial f}{\partial \varphi}(p)v^{\varphi}$$ holds for all $v^r,v^{\varphi}$. We immediately obtain $$(\text{grad} f_p)^r =\frac{\partial f}{\partial r}(p)=2r(1+\sin^2\varphi),$$ $$(\text{grad} f_p)^{\varphi} = \frac{1}{r^2}\frac{\partial f}{\partial \varphi}(p)=2\cos\varphi\sin\varphi.$$ If we now write a dynamical system as $\dot r=-(\text{grad} f)^r$ and $\dot\varphi=-(\text{grad} f)^{\varphi}$, we obtain the same solution curve as in cartesian coordinates.

$\endgroup$
  • $\begingroup$ Thank you so much for sharing all of this. It's quite overwhelming but I will struggle through it. For further background reading do you have any recommendations that might help? $\endgroup$ – tryingtolearn Sep 21 '18 at 20:50
  • $\begingroup$ Just to clarify, earlier you used x˙(0)= -∂f/∂x, however later on you've written that d/dt f(x(t),y(t))∣∣∣t=0 = ∂f/∂x(x0,y0) x˙(0), which looks confusing to me? is x˙(0) not supposed to be equal to ∂x/∂t in this equation? $\endgroup$ – tryingtolearn Sep 22 '18 at 10:58
  • $\begingroup$ The first was a dynamical system that I defined explicitely (gradient descent on the example $f$). Later on, I‘m doing completely general calculations (after the remark that I‘m considering a curve that is not necessarily a solution to the dynamical system above). The dot notation is just a shorthand for the time derivative. $\endgroup$ – S.Surace Sep 22 '18 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.