# From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes

arXiv: https://arxiv.org/abs/2504.18743 · HTML: https://mlsanity.com/paper/2504.18743/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Built on by (most cited first, 4 of 4)

- [Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.07040/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2602.16629/) (2026)

## 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.