Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes

Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini

Abstract

Policy Mirror Descent (PMD) is a versatile framework that encompasses many popular reinforcement learning algorithms, including Natural Policy Gradient. While classical methods like Policy Iteration (PI) are known to converge at a linear rate determined by the discount factor $\gamma$, the theoretical guarantees for unregularized PMD have historically lagged behind, often exhibiting dependence on state-action space dimensions or distribution mismatch coefficients. This paper establishes that unregularized PMD, equipped with a novel adaptive step-size, achieves the optimal $\gamma$-rate convergence. Crucially, this rate is independent of the state and action space sizes, matching the performance of classical PI without requiring objective regularization.

1. Introduction

In the study of discounted Markov Decision Processes (MDPs), Policy Iteration (PI) and Value Iteration (VI) serve as the gold standard for convergence, achieving a linear rate of $O(\gamma^k)$. However, modern reinforcement learning (RL) practitioners favor Policy Gradient (PG) and its generalization, Policy Mirror Descent (PMD), due to their flexibility and compatibility with function approximation.

Despite their empirical success, the theoretical analysis of PMD has faced several hurdles. Previous bounds often required entropy regularization—which shifts the optimal policy—or suffered from "dimension dependence," where convergence speed scales with the number of states $|S|$ and actions $|A|$. Furthermore, many analyses relied on the "distribution mismatch coefficient," a term that quantifies the discrepancy between the state distribution of the current policy and the optimal policy. This research, presented at NeurIPS 2023, provides a definitive analysis that removes these dependencies, proving that PMD can be as efficient as PI.

2. The Challenge of Dimension-Free Convergence

The authors identify three primary limitations in existing PMD theory:

  1. Regularization Bias: Many proofs necessitate adding a penalty term (e.g., KL divergence or entropy) to ensure stability, which alters the original optimization objective.
  2. Dimension Scaling: Real-world environments possess massive state spaces. A convergence rate that depends on $|S|$ or $|A|$ is impractical for large-scale applications.
  3. Distribution Mismatch: The reliance on the Performance Difference Lemma typically introduces a coefficient that measures how poorly the current policy explores the state space relative to the optimal policy.

The central question addressed is whether unregularized PMD can achieve a dimension-free $\gamma$-rate, effectively matching the "universal speed limit" of MDP solvers.

3. Algorithmic Framework: Adaptive PMD

The paper focuses on unregularized PMD, where the policy is updated by maximizing the expected value while constrained by a Bregman divergence to the previous iteration. The core innovation is the introduction of an adaptive step-size.

Unlike fixed step-sizes or simple geometric schedules, the proposed step-size adapts based on the Bregman divergence between the current policy and the "greedy" policy at each step. This adaptivity allows the algorithm to navigate the optimization landscape more effectively, accelerating convergence when far from the optimum and maintaining stability as it approaches.

3.1 Bypassing the Performance Difference Lemma

To achieve dimension-independent results, the authors developed a new proof technique. By avoiding the standard Performance Difference Lemma, they eliminate the distribution mismatch coefficient from the analysis. This direct analysis of value sub-optimality allows for the derivation of bounds in the $\ell_\infty$-norm, which are inherently stronger than average-case bounds.

4. Key Theoretical Results

The research yields several landmark findings for the tabular MDP setting:

  • Optimal Linear Convergence: With the adaptive step-size, PMD achieves a convergence rate of $\|V^* - V^k\|_\infty \leq \frac{2}{1-\gamma} \gamma^k$. This bound is entirely independent of $|S|$ and $|A|$.
  • Fundamental Lower Bounds: The authors prove that the $\gamma$-rate is not just achievable but optimal. The study establishes that for any iteration budget $k < n$, there exists an MDP where the error is at least $\frac{1}{2}\gamma^k$, establishing the $\gamma$-rate as a fundamental limit for this class of algorithms.
  • Necessity of Adaptivity: The paper demonstrates that a constant step-size is insufficient to reach the optimal rate. Adaptivity is a requirement for PMD to match the efficiency of Policy Iteration.

5. Inexact PMD and Sample Complexity

In practical scenarios, the environment's transition dynamics are unknown, and Q-values must be estimated via sampling (the "generative model" setting). The authors extend their analysis to this inexact setting, establishing a sample complexity of $\tilde{O}(|S||A|(1-\gamma)^{-8}\epsilon^{-2})$. This represents the first dimension-optimal result for unregularized PMD, meaning the scaling with respect to the number of states and actions is linear and theoretically optimal.

6. Discussion and Future Directions

While this work closes the gap between PMD and PI regarding dimension dependence and convergence rates, some open questions remain:

  • Discount Factor Dependence: The current sample complexity scales with $(1-\gamma)^{-8}$. While the state-action scaling is optimal, the dependence on the discount factor is higher than the theoretical lower bound of $(1-\gamma)^{-3}$. Future work may bridge this gap using more sophisticated variance-reduction techniques.
  • Function Approximation: These results are derived for the tabular setting. Extending dimension-free $\gamma$-rates to deep RL settings involving neural network function approximators remains a significant challenge for the field.

In conclusion, this research provides the first proof that unregularized Policy Mirror Descent can achieve the optimal, dimension-free convergence rate of classical methods, solidifying the theoretical foundation for one of the most widely used frameworks in modern reinforcement learning.

Summary updated

BibTeX
@inproceedings{johnson2023optimal,
  author = {Emmeran Johnson and Ciara Pike-Burke and Patrick Rebeschini},
  title = {{Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=DKHEkP7Idx},
}
Figure