Softmax Policy Gradient Methods Can Take Exponential Time to Converge

• DOI: 10.48550/arxiv.2102.11270
• Publication Date: 2023-01-23
• Authors: Gen Li; Yuting Wei; Yuejie Chi; Yuxin Chen
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; 0209 industrial biotechnology; Computer Science - Information Theory; Information Theory (cs.IT); Machine Learning (stat.ML); Systems and Control (eess.SY); 02 engineering and technology; Electrical Engineering and Systems Science - Systems and Control; Machine Learning (cs.LG); Statistics - Machine Learning; Optimization and Control (math.OC); 0202 electrical engineering, electronic engineering, information engineering; FOS: Electrical engineering, electronic engineering, information engineering; FOS: Mathematics; Mathematics - Optimization and Control

AbstractThe softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For$$\gamma $$γ-discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space$${\mathcal {S}}$$Sand the effective horizon$$\frac{1}{1-\gamma }$$11-γ, both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize$$\eta $$ηcan take$$\begin{aligned} \frac{1}{\eta } |{\mathcal {S}}|^{2^{\Omega \big (\frac{1}{1-\gamma }\big )}} ~\text {iterations} \end{aligned}$$1η|S|2Ω(11-γ)iterationsto converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods.