# Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 65 references that are in the map.
- First posted on arXiv 24 Jun 2021.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Safe and Efficient Off-Policy Reinforcement Learning](https://mlsanity.com/paper/1606.02647/) (2016)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning](https://mlsanity.com/paper/1503.04269/) (2015)
- [Reinforcement Learning to Optimize Long-term User Engagement in Recommender Systems](https://mlsanity.com/paper/1902.05570/) (2019)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Q(λ) with Off-Policy Corrections](https://mlsanity.com/paper/1602.04951/) (2016)
- [Interpretable Off-Policy Evaluation in Reinforcement Learning by Highlighting Influential Transitions](https://mlsanity.com/paper/2002.03478/) (2020)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2102.09318/) (2021)
- [A Concentration Bound for Stochastic Approximation via Alekseev's Formula](https://mlsanity.com/paper/1506.08657/) (2015)
- [True Online Temporal-Difference Learning](https://mlsanity.com/paper/1512.04087/) (2015)
- [Learning Nash Equilibria in Zero-Sum Stochastic Games via Entropy-Regularized Policy Approximation](https://mlsanity.com/paper/2009.00162/) (2020)

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

- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00661/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithms](https://mlsanity.com/paper/2208.03247/) (2022)
- [A Tutorial Introduction to Reinforcement Learning](https://mlsanity.com/paper/2304.00803/) (2023)
- [Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learning](https://mlsanity.com/paper/2508.05984/) (2025)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2402.15781/) (2024)
- [Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments](https://mlsanity.com/paper/2510.07436/) (2025)
- [Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.16196/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Set-based value operators for non-stationary Markovian environments](https://mlsanity.com/paper/2207.07271/) (2022)
- [Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.08941/) (2025)
- [Reinforcement Learning for Control with Probabilistic Stability Guarantee: A Finite-Sample Approach](https://mlsanity.com/paper/2603.00043/) (2026)

## Abstract (arXiv)

In temporal difference (TD) learning, off-policy sampling is known to be more practical than on-policy sampling, and by decoupling learning from data collection, it enables data reuse. It is known that policy evaluation (including multi-step off-policy importance sampling) has the interpretation of solving a generalized Bellman equation. In this paper, we derive finite-sample bounds for any general off-policy TD-like stochastic approximation algorithm that solves for the fixed-point of this generalized Bellman operator. Our key step is to show that the generalized Bellman operator is simultaneously a contraction mapping with respect to a weighted ℓp-norm for each p in [1,∞), with a common contraction factor. Off-policy TD-learning is known to suffer from high variance due to the product of importance sampling ratios. A number of algorithms (e.g. Qπ(λ), Tree-Backup(λ), Retrace(λ), and Q-trace) have been proposed in the literature to address this issue. Our results immediately imply finite-sample bounds of these algorithms. In particular, we provide first-known finite-sample guarantees for Qπ(λ), Tree-Backup(λ), and Retrace(λ), and improve the best known bounds of Q-trace in [19]. Moreover, we show the bias-variance trade-offs in each of these algorithms.