# Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

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

## Key facts

- Cited by 1 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.
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Placed in

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

## Builds on (most cited first, 22 of 22)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Boltzmann Exploration Done Right](https://mlsanity.com/paper/1705.10257/) (2017)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Regret Bounds for Discounted MDPs](https://mlsanity.com/paper/2002.05138/) (2020)
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [A Concentration Bound for TD(0) with Function Approximation](https://mlsanity.com/paper/2312.10424/) (2023)
- [Final Iteration Convergence Bound of Q-Learning: Switching System Approach](https://mlsanity.com/paper/2205.05455/) (2022)
- [Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise](https://mlsanity.com/paper/2503.18391/) (2025)
- [Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time](https://mlsanity.com/paper/2305.15546/) (2023)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)

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

- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)

## Abstract (arXiv)

We present the first regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes (MDPs), without relying on optimism or bonus terms. We first analyze Boltzmann Q-learning with decaying temperature and show that its regret depends critically on the suboptimality gap of the MDP: for sufficiently large gaps, the regret is sublinear, while for small gaps it deteriorates and can approach linear growth. To address this limitation, we study a Smoothed εn-Greedy exploration scheme that combines εn-greedy and Boltzmann exploration, for which we prove a gap-robust regret bound of near-tildeO(N9/10). We also obtain sample complexity guarantees, with both regret and sample complexity bounds holding with high probability. To analyze these algorithms, we develop a high-probability concentration bound for contractive Markovian stochastic approximation with iterate- and time-dependent transition dynamics. This bound may be of independent interest as the contraction factor in our framework is allowed to converge to one asymptotically.