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

Non-asymptotic Convergence of Average-reward Q-learning with Options
Oct 14, 2026Kintan Saha, Ahana Deb, Anders Jonsson +1Q-Learning Average-Reward RL
Indian Institute of Science · Universitat Pompeu Fabra · Univ. Lille, Inria, CNRS- CRIStAL, Centrale Lille
Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
Feb 18, 2026Rahul Singh, Siddharth Chandak, Eric Moulines +2Regret Minimization in RL Q-Learning
MBZUAI, UAE · Stanford University, USA · EPITA, France +1
Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning
Jun 8, 2025Yang Xu, Swetha Ganesh, Vaneet AggarwalRobust Markov Decision Processes Reinforcement Learning
Purdue University, West Lafayette, Indiana, USA 47907

Oct 14, 2026J/K move · Enter open · S save

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

Kintan Saha, Ahana Deb, Anders Jonsson, Debabrota Basu

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

Q-Learning Average-Reward RL Hierarchical RL

Open paper AskPDF arXiv

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.

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