Can I read Softmax Policy Gradient Methods Can Take Exponential Time to Converge on EtoBox?

Softmax Policy Gradient Methods Can Take Exponential Time to Converge by Li, Gen; Wei, Yuting; Chi, Yuejie; Chen, Yuxin is a scholarly article available to read on EtoBox.

What is Softmax Policy Gradient Methods Can Take Exponential Time to Converge about?

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 mismat

Author

Li, Gen; Wei, Yuting; Chi, Yuejie; Chen, Yuxin

Published

2021

Language

EN