Softmax Policy Gradient Methods Can Take Exponential Time to Converge

2021-02-22 · Gen Li, Yuting Wei, Yuejie Chi, Yuxin Chen

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 $\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}$ and the effective horizon $\frac{1}{1-\gamma}$, 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 \[ \frac{1}{\eta} |\mathcal{S}|^{2^{\Omega\big(\frac{1}{1-\gamma}\big)}} ~\text{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.

📄 PDF Abstract BibTeX arXiv:2102.11270

Code (0)

등록된 구현이 없습니다.

Tasks

Policy Gradient Methods

Methods 이 논문이 사용한 방법론

Softmax The Softmax output function transforms a previous layer's output into a vector of probabilities. It is commonly used for multiclass classification. Given an input vector $x$…

Beyond Softmax and Entropy: Convergence Rates of Policy Gradients with f-SoftArgmax Parameterization & Coupled Regularization

2026-01-18 · Safwan Labbi, Daniil Tiapkin, Paul Mangold, Eric Moulines arxiv

Policy gradient methods are known to be highly sensitive to the choice of policy parameterization. In particular, the widely used softmax parameterization can induce ill-conditioned optimization landscapes and lead to ex…

SoftTreeMax: Exponential Variance Reduction in Policy Gradient via Tree Search

2023-01-30 · Gal Dalal, Assaf Hallak, Gugan Thoppe, Shie Mannor 외

Despite the popularity of policy gradient methods, they are known to suffer from large variance and high sample complexity. To mitigate this, we introduce SoftTreeMax -- a generalization of softmax that takes planning in…

GPU Policy Gradient Methods

Structure Matters: Dynamic Policy Gradient

2024-11-07 · Sara Klein, Xiangyuan Zhang, Tamer Başar, Simon Weissmann 외

In this work, we study $\gamma$-discounted infinite-horizon tabular Markov decision processes (MDPs) and introduce a framework called dynamic policy gradient (DynPG). The framework directly integrates dynamic programming…

Multi-Armed Bandits

Neural Replicator Dynamics

2019-06-01 · Daniel Hennes, Dustin Morrill, Shayegan Omidshafiei, Remi Munos 외

Policy gradient and actor-critic algorithms form the basis of many commonly used training techniques in deep reinforcement learning. Using these algorithms in multiagent environments poses problems such as nonstationarit…

counterfactual Deep Reinforcement Learning Policy Gradient Methods Reinforcement Learning

Expected Policy Gradients for Reinforcement Learning

2018-01-10 · Kamil Ciosek, Shimon Whiteson

We propose expected policy gradients (EPG), which unify stochastic policy gradients (SPG) and deterministic policy gradients (DPG) for reinforcement learning. Inspired by expected sarsa, EPG integrates (or sums) across a…

Policy Gradient Methods reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)