  Projected policy gradient under the simplex parameterization, policy gradient
and natural policy gradient under the softmax parameterization, are fundamental
algorithms in reinforcement learning. There have been a flurry of recent
activities in studying these algorithms from the theoretical aspect. Despite
this, their convergence behavior is still not fully understood, even given the
access to exact policy evaluations. In this paper, we focus on the discounted
MDP setting and conduct a systematic study of the aforementioned policy
optimization methods. Several novel results are presented, including 1) global
linear convergence of projected policy gradient for any constant step size, 2)
sublinear convergence of softmax policy gradient for any constant step size, 3)
global linear convergence of softmax natural policy gradient for any constant
step size, 4) global linear convergence of entropy regularized softmax policy
gradient for a wider range of constant step sizes than existing result, 5)
tight local linear convergence rate of entropy regularized natural policy
gradient, and 6) a new and concise local quadratic convergence rate of soft
policy iteration without the assumption on the stationary distribution under
the optimal policy. New and elementary analysis techniques have been developed
to establish these results.
