Mixing Regularization for Average-Reward Q-Learning and Q-Planning
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.
Related
- Non-asymptotic Convergence of Average-reward Q-learning with Options
- Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning
- Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
- Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
BibTeX
@misc{roger2026mixing,
title = {{Mixing Regularization for Average-Reward $Q$-Learning and $Q$-Planning}},
author = {Julien Roger and Sam Bodmer and Jian Qian and Benjamin Riviere},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14988},
eprint = {2610.14988},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14988},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Mixing Regularization for Average-Reward Q-Learning and Q-Planning
AU - Julien Roger
AU - Sam Bodmer
AU - Jian Qian
AU - Benjamin Riviere
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14988
UR - https://arxiv.org/abs/2610.14988
AB - 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.
ER -