Mixing Regularization for Average-Reward $Q$-Learning and $Q$-Planning

Julien Roger; Sam Bodmer; Jian Qian; Benjamin Riviere

cs.LGOct 10, 2026

Mixing Regularization for Average-Reward $Q$ -Learning and $Q$ -Planning

Authors: Julien Roger, Sam Bodmer, Jian Qian, Benjamin Riviere

Organizations: École polytechnique · New York University · The University of Hong Kong

Abstract

The average-reward setting for reinforcement learning is challenging because its Bellman operator is known to contract in span only when the underlying Markov chain is mixing. Whereas existing work typically assumes a contraction property, e.g., through environment mixing, we consider the setting where we are given a reward-agnostic $m$ -step mixing policy, and we control the contraction and exploration properties of the learned policy by regularizing toward the mixing policy. We provide finite-time analysis of $Q$ -learning algorithms that can be instantiated with multiple choices of regularization, with guarantees measured with respect to the regularized fixed point. Our framework exposes novel regularizer-dependent objects that control contraction, exploration, and operator bias. In the one-step setting, our rates match the best known rates for $Q$ -iteration and synchronous $Q$ -learning, and for $m$ -step mixing we derive new rates. We also study $Q$ -planning variants, and show that planning acts as time-localized learning, where the planning horizon $H$ trades off the bias from the boundary value against the sample complexity. Finally, we present numerical studies validating the analysis: (i) knowledge of a strong mixing policy improves convergence and exploration, and its advantage increases with bottleneck severity and, (ii) our theory predicts the convergence and bias rankings of regularizers from the $α$ -divergence family.

Figures & tables

	general $\alpha$	reverse KL	forward KL	Hellinger	$\chi^{2}$
		$\alpha=1$	$\alpha=0$	$\alpha=\frac{1}{2}$	$\alpha=2$
$\Omega_{\alpha,s}(\pi)$	$D_{\alpha}(\pi\\|\mu_{s})$	$\text{KL}(\pi\\|\mu_{s})$	$\text{KL}(\mu_{s}\\|\pi)$	$2\\|\sqrt{\pi}-\sqrt{\mu_{s}}\\|_{2}^{2}$	$\frac{1}{2}\chi^{2}(\pi\\|\mu_{s})$
strong convexity	$\mu_{\min}^{(1-\alpha)_{+}}$ if $\alpha\leq 2$	$1$	$\mu_{\min}$	$\sqrt{\mu_{\min}}$	$1$
$\pi_{\Omega,Q}(a\|s)/\mu_{a}$	$\big[1+\frac{(\alpha-1)(Q_{a}-\zeta_{s})}{\tau}\big]_{+}^{\frac{1}{\alpha-1}}$	$\frac{e^{Q_{a}/\tau}}{\sum_{b}\mu_{b}e^{Q_{b}/\tau}}$	$\big(1+\frac{\zeta_{s}-Q_{a}}{\tau}\big)^{-1}$	$\big(1+\frac{\zeta_{s}-Q_{a}}{2\tau}\big)^{-2}$	$\big[1+\frac{Q_{a}-\zeta_{s}}{\tau}\big]_{+}$
$\gamma_{\Omega}(R)\geq$	$\exp_{2-\alpha}(-R/\tau)$	$e^{-R/\tau}$	$\frac{\tau}{\tau+R}$	$\big(1+\frac{R}{2\tau}\big)^{-2}$	$\big[1-\frac{R}{\tau}\big]_{+}$
$\Lambda_{\Omega}(R)\leq$	$\tau\frac{\mu_{\min}^{1-\alpha}-1}{\alpha(\alpha-1)}$ if $\alpha>0$	$\tau\log\frac{1}{\mu_{\min}}$	$\tau\big(1+\log_{+}\frac{R}{\tau}\big)$	$4\tau(1-\sqrt{\mu_{\min}})$	$\frac{\tau}{2}\big(\frac{1}{\mu_{\min}}-1\big)$

Table 1: The

\alpha

-divergence regularizers

Panel of Figure 1 — Figure 1: Empirical results on the Two-Rooms MDP. Biasing the reference policy $\mu$ towards the bottleneck improves both convergence (b) and exploration (c).

Panel of Figure 2 — Figure 2: Comparison of regularizers from the $\alpha$ -divergence family on the RiverSwim MDP. As predicted by the theory, convergence slows as $\alpha$ increases at equal bias level.

Paper	Assumptions	Sample complexity
$Q$ -iteration (known transitions)
Puterman (1994)	one-step minorization $p(\cdot\|s,a)\geq\beta\nu$	$\|\mathcal{S}\|^{2}\|\mathcal{A}\|\,\beta^{-1}\log(1/\varepsilon)$
Ours, Corollary 1	$m$ -step Doeblin policy $\mu$ ; regularizer satisfying ( P1 )	$\|\mathcal{S}\|^{2}\|\mathcal{A}\|\,m\,\tilde{\beta}^{-1}\log(1/\varepsilon)$
Generative model, model-based
Wang et al. (2024)	all stationary policies uniformly mixing	$\|\mathcal{S}\|\|\mathcal{A}\|\,t_{\mathrm{mix}}\,\varepsilon^{-2}$
Zurek and Chen (2024)	weakly communicating	$\|\mathcal{S}\|\|\mathcal{A}\|\,\\|\max_{a}Q^{*}\\|_{\mathrm{sp}}\,\varepsilon^{-2}$

Table 2: Sample complexity of average-reward methods, in sampled transitions and up to logarithmic factors; for

Q

-iteration we count evaluations of

p(s^{\prime}|s,a)

. Let

t_{\mathrm{mix}}

be the mixing time,

K

the worst expected hitting time of a reference state, and

\theta<1

a span-contraction factor. Whereas other methods target

Q^{*}

, we target the regularized fixed point

Q^{*}_{\Omega}

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

MDP and kernels
$\mathcal{S}$ , $\mathcal{A}$ , $p$ , $r$	finite state and action sets, transition kernel, deterministic reward
$\mathbb{P}_{\pi}(\cdot\mid s_{0}=s)$ , $\mathbb{E}_{\pi}[\cdot\mid s_{0}=s]$	law and expectation of the chain started at $s$ , with $a_{t}\sim\pi(\cdot\|s_{t})$ and $s_{t+1}\sim p(\cdot\|s_{t},a_{t})$
$P$	rectangular kernel $(s,a)\mapsto p(\cdot\|s,a)$ , from $\mathcal{S}\times\mathcal{A}$ to $\mathcal{S}$
$P_{\pi}$	state kernel $P_{\pi}(s^{\prime}\|s)=\sum_{a}\pi(a\|s)p(s^{\prime}\|s,a)$ , acting on $\mathbb{R}^{\mathcal{S}}$
$K_{\pi}$	state-action kernel $K_{\pi}(s^{\prime},a^{\prime}\|s,a)=p(s^{\prime}\|s,a)\pi(a^{\prime}\|s^{\prime})$ , acting on $\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$
$K_{\pi_{1}:\pi_{m}}$ , $K^{m}_{\mu}$	$m$ -step state-action kernels, ( G.2 ); $K^{m}_{\mu}(s^{\prime}\|s,a)$ is the state marginal

Appendix

Table 3: Notation used across sections.

Figure 3: Bias $\|Q^{*}_{\Omega}-Q^{*}\|_{\mathrm{sp}}$ on Two Rooms against $\mu(\text{DOOR})$ , exact. Dotted line: uniform $\mu$ .

Figure 4: The objects of Definition 2 for the

\alpha

-divergences to a uniform

\mu

over two actions, and the resulting bias. (a) Domination profile

\gamma_{\Omega}

and (b) regularization modulus

\Lambda_{\Omega}/\tau

, both functions of

R/\tau

only. (c) The pair

(\Lambda_{\Omega}/\tau,\gamma_{\Omega})

R/\tau

grows.

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,661 papers

Oct 14, 2026

Non-asymptotic Convergence of Average-reward Q-learning with Options

We study the finite-sample convergence of Q-learning algorithms for the average-reward formulation of Reinforcement Learning (RL) with options. While options allow temporarily extended and hierarchical actions, the average-reward formulation incorporates continual tasks beyond discounted and episodic RL. We establish the first

\tilde{O}(1/\text{iterations})

convergence guarantees, in the mean-square sense, for average-reward option Q-learning algorithms in both the inter- and intra-option settings. First, we prove that both inter- and intra-option Bellman operators satisfy multi-step span contractions under unichain assumptions. Then, we propose synchronous estimators of these multi-step option Bellman operators leading to two variants of option Q-learning. Finally, we extend the stochastic approximation framework to prove convergence rates of these two algorithms under the minimal assumptions used in the literature.

Kintan Saha, Ahana Deb, Anders Jonsson +1

Indian Institute of Science · Universitat Pompeu Fabra · Univ. Lille, Inria, CNRS- CRIStAL, Centrale Lille

Q-Learning Average-Reward RL Hierarchical RL

Ask PDF

Feb 18, 2026

Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

We present the first regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes (MDPs), without relying on optimism or bonus terms. We first analyze Boltzmann Q-learning with decaying temperature and show that its regret depends critically on the suboptimality gap of the MDP: for sufficiently large gaps, the regret is sublinear, while for small gaps it deteriorates and can approach linear growth. To address this limitation, we study a Smoothed

ε_n

-Greedy exploration scheme that combines

ε_n

-greedy and Boltzmann exploration, for which we prove a gap-robust regret bound of near-

\tilde{O}(N^{9/10})

. We also obtain sample complexity guarantees, with both regret and sample complexity bounds holding with high probability. To analyze these algorithms, we develop a high-probability concentration bound for contractive Markovian stochastic approximation with iterate- and time-dependent transition dynamics. This bound may be of independent interest as the contraction factor in our framework is allowed to converge to one asymptotically.

Rahul Singh, Siddharth Chandak, Eric Moulines +2

MBZUAI, UAE · Stanford University, USA · EPITA, France +1

Regret Minimization in RL Q-Learning Sample-Efficient RL RL Exploration Stochastic Approximation

Ask PDF

Jun 8, 2025

Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning

We study model-free methods for distributionally robust infinite-horizon average-reward Markov decision processes (MDPs). We present non-asymptotic convergence analyses of Q-learning and actor-critic algorithms for robust average-reward MDPs under contamination, total-variation distance, and Wasserstein uncertainty sets. A key ingredient of our analysis is showing that the optimal robust Bellman operator is a strict contraction with respect to a carefully designed semi-norm. This property enables a stochastic approximation update that learns the optimal robust

Q

-function with

\tilde{\mathcal{O}}(ε^{-2})

dependence on the target accuracy. We also establish robust TD convergence bounds whose constants are uniform over all stationary policies, yielding an efficient data-driven routine for robust critic estimation. Building on this, we introduce an actor-critic algorithm that learns an

ε

-optimal robust policy with

\tilde{\mathcal{O}}(ε^{-2})

dependence on the target accuracy. We provide numerical simulations to illustrate the qualitative behavior of the proposed algorithms. Our results contribute to the theoretical foundations of robust planning under model misspecification and to model-free approaches for building robust long-run policies directly from simulation data.

Yang Xu, Swetha Ganesh, Vaneet Aggarwal

Purdue University, West Lafayette, Indiana, USA 47907

Robust Markov Decision Processes Reinforcement Learning Average-Reward RL Q-Learning Distributionally Robust RL Model-Free RL+3

Ask PDF

Abstract

Reinforcement Learning

Explore similar work

Non-asymptotic Convergence of Average-reward Q-learning with Options

Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning