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

Kintan Saha; Ahana Deb; Anders Jonsson; Debabrota Basu

cs.LGOct 14, 2026

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

Authors: Kintan Saha, Ahana Deb, Anders Jonsson, Debabrota Basu

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

Abstract

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.

Figures & tables

Stepsize	$\alpha_{k}=\frac{4}{(1-\gamma)(k+h)}$
Inter-option (Theorem 5.1 )	$\frac{1}{k}\left(\Delta_{0}^{2}+\frac{\mathrm{sp}(Q^{*})^{2}+\|\mathcal{S}\|\|\mathcal{O}\|J^{4}}{(1-\gamma)^{3}}\right)$
Intra-option (Theorem 5.2 )	$\frac{1}{k}\left(\Delta_{0}^{2}+\frac{\mathrm{sp}(Q^{*})^{2}+\|\mathcal{S}\|J^{4}}{(1-\gamma)^{3}}\right)$

Table 1: Finite-time bounds on

\Delta_{k}^{2}\mathrel{\triangleq}\mathbb{E}\!\left[\mathrm{sp}(Q_{k}-Q^{*})^{2}\right]

. We present the bounds in

\tilde{\mathcal{O}}(\cdot)

\mathrm{sp}(\mathbf{x})

denotes span:

(\max_{i}\mathbf{x}(i)-\min_{i^{\prime}}\mathbf{x}(i^{\prime}))/2

Figure 1: Contraction factors ( $\gamma$ ) for intra-option and inter-option in Four Rooms.

Figure 2: Guideline to select $J$ with $\frac{(\mathrm{sp}(Q^{*})+J)^{2}}{(1-\gamma)^{3}}$ .

Panel of Figure 3 — Figure 3: Evolution of $\mathrm{sp}(Q_{k}-Q^{*})$ (mean $\pm$ std. over $5$ runs) with $k$ iterations for Four Rooms.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$\mathcal{S},\mathcal{A},\mathcal{O}$	Finite state, primitive-action, and option spaces.
$s,a,o$	Generic state, primitive action, and option.
$S_{k},A_{k},O_{k}$	State, primitive action, and option at iteration $k$ .
$p(s^{\prime}\|s,a)$	Primitive MDP transition kernel.
$r(s,a)$	Primitive one-step reward.
$\pi(a\|s,o)$	Intra-option policy associated with option $o$ .

Appendix

Table 2: Notation for the average-reward option-learning setup and algorithms.

\displaystyle(\widehat{H}_{\rm k,inter}Q)(s,o)\leftarrow\widehat{\rho}_{k}(s,o)+(1-\widehat{\lambda}_{k}(s,o))Q(s,o)+\widehat{\lambda}_{k}(s,o)\sum_{s^{\prime}}\widehat{p}_{k}(s^{\prime}|s,o)\max_{o^{\prime}}Q(s^{\prime},o^{\prime})\quad\forall(s,o)\in\mathcal{S}\times\mathcal{O}.

Appendix

Algorithm 1 Synchronous inter-option

J

-step Q-learning

(\widehat{H}_{k,\mathrm{intra}}Q)(s,o)\leftarrow\widehat{r}_{k}(s,o)+\sum_{s^{\prime}}\widehat{p}_{k}(s^{\prime}|s,o)\bigl[(1-\beta(s^{\prime},o))Q(s^{\prime},o)+\beta(s^{\prime},o)\max_{o^{\prime}}Q(s^{\prime},o^{\prime})\bigr],\quad\forall(s,o)\in\mathcal{S}\times\mathcal{O}.

Appendix

Algorithm 2 Synchronous intra-option

J

-step Q-learning

Panel of Figure 4 — Figure 4: Evolution of $\mathrm{sp}(Q_{k}-Q^{*})$ with iterations $k$ for synchronous learning for intra-option setting (a), (b) and inter-option setting (c), (d) for Taxi and Office gridworld respectively.

Panel of Figure 5 — Figure 5: Four Rooms gridworld with $3\times 3$ rooms, four primitive actions, and a reward machine corresponding to a patrolling task.

Figure 6: Evolution of $\mathrm{sp}(Q_{k}-Q^{*})$ over iterations $k$ for synchronous intra-option setting for Four Rooms environment.

J	Four Rooms		Taxi		Office gridworld
	Intra-option	Inter-option	Intra-option	Inter-option	Intra-option	Inter-option
1	$0.81\pm 0.07$	$0.821\pm 0.05$	$0.79\pm 0.08$	$0.83\pm 0.05$	$0.75\pm 0.07$	$0.83\pm 0.07$
2	$0.68\pm 0.08$	$0.70\pm 0.06$	$0.68\pm 0.08$	$0.73\pm 0.05$	$0.63\pm 0.06$	$0.76\pm 0.07$
3	$0.56\pm 0.09$	$0.62\pm 0.06$	$0.58\pm 0.08$	$0.66\pm 0.05$	$0.54\pm 0.06$	$0.72\pm 0.06$
4	$0.48\pm 0.08$	$0.55\pm 0.07$	$0.48\pm 0.09$	$0.59\pm 0.04$	$0.48\pm 0.05$	$0.66\pm 0.06$

Appendix

Table 3: Contraction factor

\gamma

for the three environments for different values of

J

for the synchronous setting.

Panel of Figure 7 — Figure 7: $J$ -step contraction and $J$ -step selection guideline for intra-and inter-option operators for Four rooms environment.

Q-Learning

Q-learning estimates long-term action values from experience so agents can improve decisions without a learned transition model.

See all 98 papers

Heavy-Ball Q-Learning with Residual Weighting Correction
Jun 25, 2026Donghwan LeeMomentum Methods Q-Learning
Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea
Gaussian Approximation for Asynchronous Q-learning
Apr 8, 2026Artemy Rubtsov, Sergey Samsonov, Vladimir Ulyanov +1Polyak-Ruppert Averaging Q-Learning
HSE University, Moscow, Russia · HSE University & Lomonosov MSU, Moscow, Russia · HSE University & Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia
Mixing Regularization for Average-Reward $Q$ -Learning and $Q$ -Planning
Oct 10, 2026Julien Roger, Sam Bodmer, Jian Qian +1Reinforcement Learning Average-Reward RL
École polytechnique · New York University · The University of Hong Kong

Jun 25, 2026J/K move · Enter open · S save

Heavy-Ball Q-Learning with Residual Weighting Correction

Donghwan Lee

Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea

Momentum Methods Q-Learning

Open paper AskPDF arXiv

This paper proposes a corrected heavy-ball Q-learning method for reinforcement learning (RL) and establishes convergence of its deterministic mean dynamics. It also identifies conditions under which the method is theoretically guaranteed to converge faster than standard Q-learning. The same construction is then extended to Q-learning with linear function approximation, where analogous convergence and acceleration statements are derived for the corresponding corrected fixed point. The sampled stochastic versions are treated through conditional-mean recursions and, in the stated linear-function-approximation setting, finite-time bounds. The analysis is based on a switched linear system (SLS) representation of Q-learning algorithms and on the joint spectral radius (JSR) of the associated switching families. This SLS viewpoint is not commonly used in standard analyses of Q-learning, and it provides a complementary framework and new insight into how heavy-ball momentum can accelerate Q-learning.

Abstract

Q-Learning

Explore similar work

Heavy-Ball Q-Learning with Residual Weighting Correction

Gaussian Approximation for Asynchronous Q-learning

Mixing Regularization for Average-Reward QQQ-Learning and QQQ-Planning

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