Softmax policy gradient methods can take exponential time to converge
From MaRDI portal
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 and the effective horizon , 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 [ frac{1}{eta} |mathcal{S}|^{2^{Omega�ig(frac{1}{1-gamma}�ig)}} ~ ext{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.
Recommendations
- Fast global convergence of natural policy gradient methods with entropy regularization
- Global convergence of policy gradient methods to (almost) locally optimal policies
- On linear and super-linear convergence of natural policy gradient algorithm
- Block Policy Mirror Descent
- Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes
Cites work
- Fast global convergence of natural policy gradient methods with entropy regularization
- Finite-Sample Analysis of Two-Time-Scale Natural Actor–Critic Algorithm
- First-order methods in optimization
- Global convergence of policy gradient methods to (almost) locally optimal policies
- Instance-Dependent ℓ∞-Bounds for Policy Evaluation in Tabular Reinforcement Learning
- Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
- Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model
- On the theory of policy gradient methods: optimality, approximation, and distribution shift
- OnActor-Critic Algorithms
- Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
- Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes
- Simple statistical gradient-following algorithms for connectionist reinforcement learning
Cited in
(4)- Fast global convergence of natural policy gradient methods with entropy regularization
- Global convergence of policy gradient methods to (almost) locally optimal policies
- Approximate Newton Policy Gradient Algorithms
- Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
This page was built for publication: Softmax policy gradient methods can take exponential time to converge
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6110457)
