# Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2020.

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

- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [TD Convergence: An Optimization Perspective](https://mlsanity.com/paper/2306.17750/) (2023)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [MDP Geometry, Normalization and Reward Balancing Solvers](https://mlsanity.com/paper/2407.06712/) (2024)
- [A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression](https://mlsanity.com/paper/2504.08178/) (2025)
- [Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks](https://mlsanity.com/paper/2401.09665/) (2024)
- [PID Accelerated Temporal Difference Algorithms](https://mlsanity.com/paper/2407.08803/) (2024)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Finite-Time Analysis of Temporal Difference Learning with Experience Replay](https://mlsanity.com/paper/2306.09746/) (2023)
- [Gaussian Approximation for Asynchronous Q-learning](https://mlsanity.com/paper/2604.07323/) (2026)

## Abstract (arXiv)

Stochastic Approximation (SA) is a popular approach for solving fixed-point equations where the information is corrupted by noise. In this paper, we consider an SA involving a contraction mapping with respect to an arbitrary norm, and show its finite-sample error bounds while using different stepsizes. The idea is to construct a smooth Lyapunov function using the generalized Moreau envelope, and show that the iterates of SA have negative drift with respect to that Lyapunov function. Our result is applicable in Reinforcement Learning (RL). In particular, we use it to establish the first-known convergence rate of the V-trace algorithm for off-policy TD-learning. Moreover, we also use it to study TD-learning in the on-policy setting, and recover the existing state-of-the-art results for Q-learning. Importantly, our construction results in only a logarithmic dependence of the convergence bound on the size of the state-space.