Fast Regularized Policy Mirror Descent with One-Step TD Updates

Qipei Chen; Wenye Li; Yule Sun; Ke Wei

cs.LGSep 30, 2026

Fast Regularized Policy Mirror Descent with One-Step TD Updates

Authors: Qipei Chen, Wenye Li, Yule Sun, Ke Wei

Organizations: School of Mathematical Sciences, Fudan University · School of Data Science, Fudan University

Abstract

Policy mirror descent (PMD) enjoys fast convergence in regularized Markov decision processes (MDPs), but existing guarantees often rely on exact or increasingly accurate policy evaluation. We analyze PMD coupled with a persistent critic advanced by one temporal-difference (TD) update. For finite discounted MDPs, we establish global linear convergence in value for exact coordinate-wise Bellman updates, with any positive constant actor stepsize and arbitrary finite critic initialization. The proof combines a resolvent-based auxiliary distribution with a decaying Bellman-violation correction and a potential weighted by inverse coordinate weights. We then study stochastic TD-PMD with general strongly convex mirror maps under a single off-policy Markov trajectory. With suitably chosen constant stepsizes and a finite-batch TD update, the method achieves an expected value gap of $ε$ after $\widetilde{O}(1/((1-γ)^5 \widetildeσ_b ε))$ transitions. The stochastic analysis relies on the trajectory-wise Lipschitz continuity of the regularizer, derived from uniform bounds on vertex Bregman divergences, together with a visitation-weighted resolvent estimate for signed critic-error propagation that yields an inverse-linear dependence on behavior coverage $\widetildeσ_b$ . In contrast to many prior guarantees for regularized policy optimization, our sample-complexity guarantee holds without trajectory resets, generative-model access, or nested policy-evaluation loops. Numerical results are consistent with the theoretical convergence analysis.

Figures & tables

	Algorithm	Iteration complexity	Stochastic access	Sample complexity
Cen et al. [2022]	NPG	$\mathcal{O}\!\left(\log_{(1-\eta\tau)^{-1}}(\epsilon^{-1})\right)$	—	—
Cen et al. [2023]	TD–NPG	$\mathcal{O}\!\left(\log_{[1-\frac{(1-\gamma)\eta\tau}{4}]^{-1}}(\epsilon^{-1})\right)$	—	—
Zhan et al. [2023]	PMD	$\mathcal{O}\!\left(\log_{[1-\frac{\eta\tau}{1+\eta\tau}(1-\gamma)]^{-1}}(\epsilon^{-1})\right)$	—	—
Lan [2023]	PMD	$\mathcal{O}\!\left(\log_{\gamma^{-1}}(\epsilon^{-1})\right)$	Generative model	$\widetilde{\mathcal{O}}\!\left(\frac{\|\mathcal{S}\|\|\mathcal{A}\|}{(1-\gamma)^{5}\epsilon}\right)$
Jia and Lan [2026]	VMD	$\mathcal{O}\!\left((1-\gamma)^{-1}\log_{2}([(1-\gamma)\epsilon]^{-1})\right)$	Generative model	$\widetilde{\mathcal{O}}\!\left(\frac{\|\mathcal{S}\|\|\mathcal{A}\|}{(1-\gamma)^{5}\epsilon}\right)$
This work	TD–PMD	$\mathcal{O}\!\left(\log_{[1-\underline{w}\min\{1-\gamma,\frac{\eta\tau}{1+\eta\tau}\}]^{-1}}(\epsilon^{-1})\right)$	Off-policy Markov data	$\widetilde{\mathcal{O}}\!\left(\frac{1}{(1-\gamma)^{5}\widetilde{\sigma}_{b}\epsilon}\right)$

Table 1: Comparison of regularized PMD results. Here,

\widetilde{\sigma}_{b}

is the smallest stationary visitation probability over state–action pairs; under near-uniform coverage,

\widetilde{\sigma}_{b}=\Theta((|\mathcal{S}||\mathcal{A}|)^{-1})

\pi_{k+1}(\cdot\mid s)\in\underset{p\in\Delta(\mathcal{A})}{\arg\max}\left\{\langle p,Q_{\tau}^{k}(s,\cdot)\rangle-\tau h(p)-\eta^{-1}D_{h}\!\left(p\,\middle\|\,\pi_{k}(\cdot\mid s)\right)\right\}.

Algorithm 1 Exact Regularized TD–PMD with Coordinate-Wise Bellman Updates

\displaystyle\forall\,s\in\mathcal{S}:\hskip 9.24994pt\pi_{k+1}(\cdot|s)=\underset{p\in\Delta(\mathcal{A})}{\arg\max}\;\left\{\left\langle p,\,Q_{\tau}^{k}(s,\cdot)\right\rangle-\tau h(p)-\frac{1}{\eta}D^{p}_{\pi_{k}}(s)\right\}.

Algorithm 2 Finite-Batch Off-Policy Expected TD–PMD

Figure 1: Exact coordinate-wise TD–PMD with different critic initializations. Solid curves correspond to initialization that satisfies the one-sided Bellman condition $\mathcal{F}_{\tau}^{\pi_{0}}Q_{\tau}^{0}-Q_{\tau}^{0}\geq 0$ while dashed curves correspond to general initialization.

Figure 2: Finite-batch stochastic TD–PMD over five independent Markov trajectories.

Explore similar work

Value Mirror Descent for Reinforcement Learning
Apr 7, 2026Zhichao Jia, Guanghui LanMirror Descent Value Functions
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332.
Behavior-Induced Mirror-Prox Temporal-Difference Learning for Faster Off-Policy Prediction
May 16, 2026Xingguo Chen, Yuchen Shen, Shangdong Yang +3Temporal Difference Mirror Descent
Nanjing University of Posts and Telecommunications, Nanjing, China · Department of Computer Science and Technology, Nanjing University, Nanjing, China · College of Electronic Countermeasure, National University of Defense Technology, Hefei, China
Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity
Jun 9, 2026Shira Vansover-Hager, Matan Schliserman, Ofir Schlisselberg +1Mirror Descent
Blavatnik School of Computer Science and AI, Tel Aviv University · Google Research

Apr 7, 2026, math.OCJ/K move · Enter open · S save

Value Mirror Descent for Reinforcement Learning

Zhichao Jia, Guanghui Lan

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332.

Mirror Descent Value Functions Stochastic Value

Open paper AskPDF arXiv

Value iteration-type methods have been extensively studied for computing a nearly optimal value function in reinforcement learning (RL). Under a generative sampling model, these methods can achieve sharper sample complexity than policy optimization approaches, particularly in their dependence on the discount factor. In practice, they are often employed for offline training. In this paper, we consider discounted Markov decision processes with state space S, action space A, discount factor

γ\in(0,1)

and costs in

[0,1]

. We introduce a novel value optimization method, termed value mirror descent (VMD), which integrates mirror descent from convex optimization into the classical value iteration framework. In the deterministic setting with known transition kernels, we show that VMD converges linearly. For the stochastic setting with a generative model, we develop a stochastic variant, SVMD, which incorporates variance reduction commonly used in stochastic value iteration-type methods. For RL problems with general convex regularizers, SVMD attains a near-optimal sample complexity of

\tilde{O}(|S||A|(1-γ)^{-3}ε^{-2})

. Moreover, we establish that the Bregman divergence between the generated and optimal policies remains bounded throughout the iterations, even under the presence of model misspecification. This property is absent in existing stochastic value iteration-type methods but is important for enabling effective online (continual) learning following offline training. Under a strongly convex regularizer, SVMD achieves sample complexity of

\tilde{O}(|S||A|(1-γ)^{-5}ε^{-1})

, improving performance in the high-accuracy regime. Furthermore, we prove convergence of the generated policy to the optimal policy. Overall, the proposed method, its analysis, and the resulting guarantees, constitute new contributions to the RL and optimization literature.

Abstract

Explore similar work

Value Mirror Descent for Reinforcement Learning

Behavior-Induced Mirror-Prox Temporal-Difference Learning for Faster Off-Policy Prediction

Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity