From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
This work presents the first finite-time analysis for the last-iterate convergence of average-reward Q-learning with an asynchronous implementation. A key feature of the algorithm we study is the use of adaptive stepsizes, which serve as local clocks for each state-action pair. We show that, under appropriate assumptions, the iterates generated by this Q-learning algorithm converge at a rate of tildeO(1/k) (in the mean-square sense) to the optimal Q-function in the span seminorm. Moreover, by adding a centering step to the algorithm, we further establish pointwise mean-square convergence to the centered optimal Q-function, also at a rate of tildeO(1/k). To prove these results, we show that adaptive stepsizes are necessary, as without them, the algorithm fails to converge to the correct target. In addition, adaptive stepsizes can be interpreted as a form of implicit importance sampling that counteracts the effects of asynchronous updates. Technically, the use of adaptive stepsizes makes each Q-learning update depend on the entire sample history, introducing strong correlations and making the algorithm a non-Markovian stochastic approximation (SA) scheme. Our approach to overcoming this challenge involves (1) a time-inhomogeneous Markovian reformulation of non-Markovian SA, and (2) a combination of almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities to break the strong correlations between the adaptive stepsizes and the iterates. The tools developed in this work are likely to be broadly applicable to the analysis of general SA algorithms with adaptive stepsizes.
Key facts. Cited by 4 papers in the map (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 25 Apr 2025.
Builds on
0 of 0 references.
No references here yet.
Built on by
Citing papers per year: 2025: 1; 2026: 3.
4 papers.
- 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 4
- 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 3
- 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
- 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
- 2026Policy Gradient Algorithms in Average-Reward Multichain MDPs20 Feb 2026
- 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes18 Feb 2026
- 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning20 Jan 2026
- 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning8 Jun 2025
Similar, not cited
Close in wording, no citation either way
- 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
- 2026Non-asymptotic Convergence of Average-reward Q-learning with Options
- 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
- 2026Hitting-Time Bounds for Asynchronous Q-Learning
- 2026Mixing Regularization for Average-Reward Q-Learning and Q-Planning
- 2025Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration
- 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
- 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes