policy-gradient convergence

Policy-gradient methods nudge a parameterized policy uphill along the gradient of expected return. Because that return surface is generally non-concave in the parameters, the worry is the classic one from optimization: gradient ascent could get stuck at a saddle point or a poor local optimum. Convergence theory asks where these methods actually land, and how quickly they get there.

The picture is more hopeful than non-concavity suggests. With exact gradients, vanilla policy gradient converges to a stationary point, and for the softmax tabular parameterization it provably reaches the global optimum, albeit at a slow sublinear rate. Natural policy gradient — which preconditions the update by the Fisher information matrix — converges much faster, achieving dimension-free linear or near-1/T rates; this is the theoretical backbone of TRPO and PPO. Stochastic gradients add variance that the step sizes must tame in the Robbins-Monro sense.

The strong global guarantees lean on exact or low-variance gradients and benign parameterizations. With deep networks, large variance, and limited exploration, only stationary-point guarantees survive, and the practical gap between "a stationary point" and "the optimum" is where much of the engineering effort goes.