Non-asymptotic Convergence of Average-reward Q-learning with Options
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (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 tildeO(1/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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. First posted on arXiv 14 Oct 2026.
Builds on
0 of 0 references.
No references here yet.
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Optimistic Q-learning for average reward and episodic reinforcement learning
- 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
- 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
- 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
- 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
- 2025Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration
- 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning
- 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning