A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies

2025/10/17 by Nanda, Phalguni, Chen, Zaiwei · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2510.16132

Abstract

In this work, we present the first finite-time analysis of the Q-learning algorithm under time-varying learning policies (i.e., on-policy sampling) with minimal assumptions -- specifically, assuming only the existence of a policy that induces an irreducible Markov chain over the state space. We establish a last-iterate convergence rate for 𝔼[‖Q_k - Q^*‖_∞²], implying a sample complexity of order O(1/ε²) for achieving 𝔼[‖Q_k - Q^*‖_∞] ≤ ε, matching that of off-policy Q-learning but with a worse dependence on exploration-related parameters. We also derive an explicit rate for 𝔼[‖Q^π_k - Q^*‖_∞²], where π_k is the learning policy at iteration k. These results reveal that on-policy Q-learning exhibits weaker exploration than its off-policy counterpart but enjoys an exploitation advantage, as its policy converges to an optimal one rather than remaining fixed. Numerical simulations corroborate our theory. Technically, the combination of time-varying learning policies (which induce rapidly time-inhomogeneous Markovian noise) and the minimal assumption on exploration presents significant analytical challenges. To address these challenges, we employ a refined approach that leverages the Poisson equation to decompose the Markovian noise corresponding to the lazy transition matrix into a martingale-difference term and residual terms. To control the residual terms under time inhomogeneity, we perform a sensitivity analysis of the Poisson equation solution with respect to both the Q-function estimate and the learning policy. These tools may further facilitate the analysis of general reinforcement learning algorithms with rapidly time-varying learning policies -- such as single-timescale actor--critic methods and learning-in-games algorithms -- and are of independent interest.

Citations

• Linear Q-Learning Does Not Diverge in L²: Convergence Rates to a Bounded Set
• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem
• Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
• Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games
• A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation
• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
• The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond
• Smoothed Q-learning
• A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP
• Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning
• Final Iteration Convergence Bound of Q-Learning: Switching System Approach
• Target Network and Truncation Overcome The Deadly Triad in Q-Learning
• Training language models to follow instructions with human feedback
• On the Convergence of SARSA with Linear Function Approximation
• A Statistical Analysis of Polyak-Ruppert Averaged Q-learning
• Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
• Instance-optimality in optimal value estimation: Adaptivity via\n variance-reduced Q-learning
• Concentration of Contractive Stochastic Approximation and Reinforcement Learning
• Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm
• Reinforcement learning based recommender systems: A survey
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Bandit Algorithms
• Q-learning with Logarithmic Regret
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning
• Variance-reduced Q-learning is minimax optimal
• Stochastic approximation with cone-contractive operators: Sharp\n \ℓ_\∞-bounds for Q-learning
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD\n Learning
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Is Q-learning Provably Efficient?
• A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
• Reinforcement Learning with Deep Energy-Based Policies
• Deep Reinforcement Learning with Double Q-learning
• End-to-End Training of Deep Visuomotor Policies
• Dynamic Policy Programming
• A Stochastic Approximation Method
• Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning
• Reinforcement Learning: An Introduction
• Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales

Cited by

• Auto-exploration for online reinforcement learning

Related

• q-Learning in Continuous Time
• Q-learning with Nearest Neighbors
• Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistence
• An Elementary Proof that Q-learning Converges Almost Surely
• Stochastic Primal-Dual Q-Learning