Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
This work addresses the theoretical analysis of online reinforcement learning algorithms, providing new regret bounds and a concentration tool for stochastic approximation, which is incremental but offers specific improvements in understanding exploration schemes.
The paper tackles the problem of analyzing the regret and sample complexity of online Q-learning in infinite-horizon discounted Markov decision processes, showing that Boltzmann Q-learning has sublinear regret for large suboptimality gaps but linear growth for small gaps, and introducing a Smoothed εn-Greedy scheme with a near-Õ(N^{9/10}) gap-robust regret bound.
We present the first high-probability regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes, 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-$\tilde{O}(N^{9/10})$. 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 bound is governed by the mixing time and is allowed to converge to one asymptotically.