Non-asymptotic Convergence of Average-reward Q-learning with Options
Average-reward reinforcement learning with options models continuing hierarchical tasks, but before this paper there were no finite-time convergence guarantees for option-based Q-learning in that setting. The authors prove that multi-step (J-step) inter- and intra-option Bellman operators contract in the span seminorm, design corrected synchronous multi-step estimators, and derive the first $\widetilde{\mathcal{O}}(1/k)$ mean-square convergence rates for average-reward option Q-learning. The results extend to hierarchical reward machines and are supported by small-scale tabular experiments.
The paper delivers a rigorous theoretical advance: the first non-asymptotic $\widetilde{\mathcal{O}}(1/k)$ bounds for synchronous average-reward inter- and intra-option Q-learning under minimal assumptions. Its most distinctive contribution is a careful bias analysis showing that prior multi-step estimators in the literature are not conditionally unbiased. The authors write: "This estimator is claimed to be unbiased for the J-step Bellman operator. But in general, its conditional expectation is not $H^J Q_k$." (Section 5, Rectifying J-step estimators in prior work). They support this with an explicit counterexample in Appendix B, Remark 1. The convergence rates match the best-known primitive-action bounds up to problem-dependent constants involving $J^4/(1-\gamma)^3$, though the analysis is restricted to synchronous updates and unichain models.
The J-step span contraction results (Theorems 3.1 and 3.2) are the essential enabler; they extend standard Puterman-style arguments to option-induced SMDPs and are validated empirically in Figure 1. The explicit counterexample exposing the bias in prior multi-step estimators is both simple and damning: for a specific zero-reward MDP and $Q$-function, the naive greedy rollout yields 0 whereas the true $H^2 Q$ value is 10. The corrected construction is described cleanly: "Our construction rectifies this issue by replacing the unavailable greedy values with empirical Bellman iterates and explicitly controlling the resulting bias." (Section 5, Rectifying J-step estimators in prior work). The tabular experiments further demonstrate that choosing $J=6$ (inter-option) or $J=5$ (intra-option) accelerates convergence over the $J=1$ baseline.
The analysis is confined to synchronous tabular Q-learning, leaving asynchronous and function-approximation settings for future work. The unichain requirements in Assumptions 2 and 3 are standard but exclude multichain MDPs, and the paper notes that "whether the unichain assumptions can be relaxed to more general multichain settings for options ... remains an open direction" (Section 8). The inter-option bound suffers an additional $|\mathcal{S}||\mathcal{O}|c^2 J^4$ term from online estimation of $\rho$ and $\lambda$, which inflates sample complexity when option holding times have high variance. Finally, the empirical evaluation is limited to small gridworlds (Four Rooms, Taxi, Office); it does not establish whether the span-semimetric convergence guarantees translate into reliable policy improvement in larger or stochastic environments.
The authors fairly position their results against the literature. They contrast their finite-time guarantees with the asymptotic results of Wan et al. (2024), whose abstract describes proving "almost-sure convergence" and characterizing "sets to which RVI Q-learning algorithms converge" for options, but offers no iteration complexity. The fetched abstract confirms: "We extend the almost-sure convergence analysis ... proving their almost-sure convergence" (Wan et al., 2024, Abstract). Saha et al. also explicitly name the biased estimator used in prior finite-time work and refute it with a labeled counterexample: "$\mathbb{E}[\widehat{\mathcal{H}}_{\mathrm{roll}}^{2}Q(s_0,a_0)]=0\neq 10=(\mathcal{H}^2 Q)(s_0,a_0)$" (Appendix B, Remark 1). This direct comparison strengthens the paper's credibility.
The paper provides pseudocode and step-size formulas ($\alpha_k = \frac{4}{(1-\gamma)(k+h)}$) in Section 4 and Appendix D, and describes the benchmark environments in Appendix F. Nevertheless, no source code or data repository is linked in the main text, and the hyperparameter $J$ is chosen via an empirical proxy rather than the full bound: "there are optimal J's, namely 6 and 5 for inter- and intra-option settings, by tracking the quantity $(\mathrm{sp}(Q^*)+J)^2/(1-\gamma)^3$" (Section 5, Guideline to Select J). Reproducing the inter-option algorithm requires implementing the online rolling estimates of $\rho$ and $\lambda$, which are nontrivial but documented. The pathwise growth bound $\|Q_k\|_\infty = \mathcal{O}(\log k)$ used in the analysis may also be delicate to verify independently.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.