Softmax Policy Gradient Methods Can Take Exponential Time to Converge

2021/02/22 by Gen Li, Yuting Wei, Li, Gen +5 · 4 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Systems and Control (eess.SY) #cs.IT #cs.LG #cs.SY #eess.SY #electronic engineering #information engineering #math.IT #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.2102.11270

accepted to Mathematical Programming (Series A); also presented in part in Conference on Learning Theory (COLT) 2021

arxiv created 2022/12/15 · arxiv updated 2022/12/19

Abstract

The 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 γ-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 S and the effective horizon (1)/(1-γ), 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 η can take \frac1η |S|^2^{Ω((1)/(1-γ))} ~iterations to 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.

Cited by

• Breaking the Safety-Capability Tradeoff: Reinforcement Learning with Verifiable Rewards Maintains Safety Guardrails in LLMs
• On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation
• Statistical and Algorithmic Foundations of Reinforcement Learning
• Reshaping Reasoning in LLMs: A Theoretical Analysis of RL Training Dynamics through Pattern Selection

Related

• Elementary Analysis of Policy Gradient Methods
• Structure Matters: Dynamic Policy Gradient
• Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs
• Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods
• On the Global Convergence Rates of Softmax Policy Gradient Methods