Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning

Abstract

Motivated by the study of $Q$-learning algorithms in reinforcement learning, we study a class of stochastic approximation procedures based on operators that satisfy monotonicity and quasi-contractivity conditions with respect to an underlying cone. We prove a general sandwich relation on the iterate error at each time, and use it to derive non-asymptotic bounds on the error in terms of a cone-induced gauge norm. These results are derived within a deterministic framework, requiring no assumptions on the noise. We illustrate these general bounds in application to synchronous $Q$-learning for discounted Markov decision processes with discrete state-action spaces, in particular by deriving non-asymptotic bounds on the ${\ell }_{\infty }$-norm for a range of stepsizes. These results are the sharpest known to date, and we show via simulation that the dependence of our bounds cannot be improved in a worst-case sense. These results show that relative to a model-based $Q$-iteration, the ${\ell }_{\infty }$-based sample complexity of $Q$-learning is suboptimal in terms of the discount factor $\gamma$.

Changes from v1: -- Part of Lemma 1 was incorrect; corrected -- proof of Lemma 2: fixed minor typo in equation (36)

References in corpus (1)

• From Gauss to Kolmogorov: Localized Measures of Complexity for Ellipses

Cited by in corpus (18)

• Variance-reduced $Q$-learning is minimax optimal
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Finite-Time Analysis for Double Q-learning
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Optimal oracle inequalities for solving projected fixed-point equations
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs