Research map / Optimization / Nonconvex and smooth optimization
Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes best-in-class convergence of policy mirror descent for general (non-complete) parametric policy classes under a variational gradient dominance condition, replacing closure assumptions, with rates independent of the state-space size.
Problem
Convergence guarantees for policy mirror descent (PMD) over general, non-complete parametric policy classes, where existing analyses require strong closure conditions that rarely hold for neural policies.
Approach
Replaces closure conditions with a weaker variational gradient dominance (VGD) assumption and analyzes PMD as a Bregman proximal point method under smoothness of the value function w.r.t. a local norm induced by the current occupancy measure, yielding rates independent of the state-space cardinality.
Key results
- Euclidean-regularized PMD achieves O(C*^2 A^{3/2} H^3 / K^{2/3}) suboptimality plus statistical and VGD error floors, with rates independent of state-space size.
- Negative-entropy PMD achieves a weaker O(1/K^{2/7}) rate under the same VGD assumption.
- Shows closure implies VGD but not conversely, with a log-linear example where closure-based bounds have error floor at least 10H while PMD converges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace Euclidean regularization with negative entropy regularization (ablation) | PMD · General policy classes satisfying (C⋆, εvgd)-VGD | convergence rate: 1/K^{2/3} -> 1/K^{2/7} | Hurt |
| add ε-greedy exploration | PMD with Euclidean regularization · General policy classes satisfying VGD | convergence rate: O(1/K) -> O(1/K^{2/3}) | Hurt |
Surprising findings
- Closure-based bounds become vacuous on a simple MDP where VGD holds, while PMD still converges to best-in-class policy.
Limitations
- Requires convexity of the policy class when no closure holds.
- Euclidean rate of K^{-2/3} is slower than the O(1/K) standard smoothness rate; entropy regularization degrades further to K^{-2/7}.
- Geometric rates not expected under VGD alone; analysis assumes finite state space.
Experimental setup
Metrics: suboptimality gap V(pi^K) - best in-class value convergence rate in K
Baselines: Agarwal et al. closure-based PMD analysis Lan PMD tabular analysis Liu et al. NPG analysis Xiao log-linear analysis
Builds on: policy mirror descent compatible function approximation Bregman proximal point method
Closest papers by meaning
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.90)
- Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes (NeurIPS 2023 · similarity 0.90)
- Policy Mirror Descent with Lookahead (NeurIPS 2024 · similarity 0.89)
- Mirror descent actor-critic methods for entropy regularised MDPs in general spaces: stability and convergence (NeurIPS 2026 · similarity 0.89)
- Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity (NeurIPS 2026 · similarity 0.88)
- Learning mirror maps in policy mirror descent (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.