# Policy Mirror Descent Inherently Explores Action Space

arXiv: https://arxiv.org/abs/2303.04386 · HTML: https://mlsanity.com/paper/2303.04386/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 48 references that are in the map.
- First posted on arXiv 8 Mar 2023.

## Builds on (most cited first, 25 of 25)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [Policy Optimization over General State and Action Spaces](https://mlsanity.com/paper/2211.16715/) (2022)
- [Tsallis Reinforcement Learning: A Unified Framework for Maximum Entropy Reinforcement Learning](https://mlsanity.com/paper/1902.00137/) (2019)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022)
- [Provably Correct Optimization and Exploration with Non-linear Policies](https://mlsanity.com/paper/2103.11559/) (2021)
- [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021)
- [Block Policy Mirror Descent](https://mlsanity.com/paper/2201.05756/) (2022)

## Built on by (most cited first, 13 of 13)

- [First-order Policy Optimization for Robust Policy Evaluation](https://mlsanity.com/paper/2307.15890/) (2023)
- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [Strongly-polynomial time and validation analysis of policy gradient methods](https://mlsanity.com/paper/2409.19437/) (2024)
- [Auto-exploration for online reinforcement learning](https://mlsanity.com/paper/2512.06244/) (2025)
- [Dual Approximation Policy Optimization](https://mlsanity.com/paper/2410.01249/) (2024)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Delightful Gradients Accelerate Corner Escape](https://mlsanity.com/paper/2605.11908/) (2026)
- [Learning mirror maps in policy mirror descent](https://mlsanity.com/paper/2402.05187/) (2024)
- [Actor-Accelerated Policy Dual Averaging for Reinforcement Learning in Continuous Action Spaces](https://mlsanity.com/paper/2603.10199/) (2026)
- [Value Mirror Descent for Reinforcement Learning](https://mlsanity.com/paper/2604.06039/) (2026)
- [(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator](https://mlsanity.com/paper/2609.19712/) (2026)
- [Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces](https://mlsanity.com/paper/2609.21433/) (2026)
- [Fast Regularized Policy Mirror Descent with One-Step TD Updates](https://mlsanity.com/paper/2609.39837/) (2026)

## Abstract (arXiv)

Explicit exploration in the action space was assumed to be indispensable for online policy gradient methods to avoid a drastic degradation in sample complexity, for solving general reinforcement learning problems over finite state and action spaces. In this paper, we establish for the first time an tildeO(1/ε2) sample complexity for online policy gradient methods without incorporating any exploration strategies. The essential development consists of two new on-policy evaluation operators and a novel analysis of the stochastic policy mirror descent method (SPMD). SPMD with the first evaluation operator, called value-based estimation, tailors to the Kullback-Leibler divergence. Provided the Markov chains on the state space of generated policies are uniformly mixing with non-diminishing minimal visitation measure, an tildeO(1/ε2) sample complexity is obtained with a linear dependence on the size of the action space. SPMD with the second evaluation operator, namely truncated on-policy Monte Carlo (TOMC), attains an tildeO(HD/ε2) sample complexity, where HD mildly depends on the effective horizon and the size of the action space with properly chosen Bregman divergence (e.g., Tsallis divergence). SPMD with TOMC also exhibits stronger convergence properties in that it controls the optimality gap with high probability rather than in expectation. In contrast to explicit exploration, these new policy gradient methods can prevent repeatedly committing to potentially high-risk actions when searching for optimal policies.