Tight iteration complexity of exact softmax policy gradient in tabular discounted MDPs
Difficulty 45: a precise theory question with strong partial results on both sides (an O(1/t) upper bound with problem-dependent constants, a doubly exponential lower bound); comparable to simplex-smoothed-complexity-dimension-dependence (38) but less studied. Application value 8: practice uses regularised or clipped variants. Leverage 18: policy-optimisation theory only.
The problem
How many small steps does the most basic way of improving a decision rule need, in the worst case?
- 1Step uphill on expected reward
- 2Tiny probabilities slow the gradient
- 3Delays pile up across states
- 4Slowdown grows with horizon
- 5Is the bound tight?
Why it matters. Policy-gradient methods, the family behind PPO and GRPO, are used everywhere, yet basic questions about how fast they converge are open even in the simplest setting. This problem asks for the exact worst-case speed there.
A Markov decision process (MDP) has a finite set of states and actions ; in each state the agent picks an action, receives a reward and moves to a next state with given probabilities. Future rewards are discounted by , and the effective horizon is roughly how many steps ahead the agent cares about ( gives 100). The policy is a softmax: each state-action pair has a parameter , and which turns arbitrary numbers into positive probabilities summing to 1. The algorithm is plain gradient ascent with the exact gradient (no sampling noise): with step size , where the gradient is the vector of partial derivatives of the value with respect to every parameter.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Policy gradient methods and PPOAlgorithm · host
- Then
- Tight iteration complexity of exact softmax policy gradient in tabular discounted MDPsThe problem
State of the art
Mei et al. (2020) prove an rate with constants depending on the problem and initialisation. Li et al. (COLT 2021; Mathematical Programming) show that the iteration count can be at least for some MDP with three actions, even with a benign initialisation and an initial distribution amenable to exploration, so the dependence on horizon can be doubly exponential in the exponent. Whether this is tight, and what is the worst case from uniform initialisation with explicit constants, is not settled. Regularised and natural policy gradient methods avoid the lower bound.
Realistic applications
Indirect: sharpens understanding of why practical policy optimisation needs regularisation, natural gradients or trust regions, which are used in PPO and GRPO.
What counts as solved
A proved matching upper and lower bound, with the hard MDP family given explicitly and its gradient dynamics recomputed numerically for small cases by an independent referee.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: worst-case iterations of exact-gradient softmax policy gradient from uniform initialisation. Current record: lower bound (Li et al., 2021, arXiv 2102.11270); upper bounds with problem-dependent constants (Mei et al., arXiv 2005.06392). Certificate for an improvement: a written proof of a matching upper bound or of a strictly stronger lower bound, plus the explicit MDP transition and reward tables for the hard family so that a referee can integrate the gradient flow or iterate the update in exact rational or high-precision arithmetic for small and compare iteration counts with the claimed bound.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
A proof problem; small numerical experiments on the hard MDP family only check lower-bound dynamics.
Bottlenecks
ranked by votes- #1TheoryCharacterising the dynamics of softmax PG
The softmax parametrisation creates plateaus where probabilities of optimal actions grow slowly; tight bounds need control of the dynamics over many phases.
Sign in to name a bottleneck or vote.
Community grades
Sign in to add your own grade.
Connected problems
No connections yet.