mlsanityData to 14 Oct 2026

Finite-Sample Analysis for SARSA with Linear Function Approximation

arXiv 1902.02234 ↗First posted 6 Feb 2019cs.LG stat.MLcited by 85

Not on the map. Why?

Cited by 27 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

SARSA is an on-policy algorithm to learn a Markov decision process policy in reinforcement learning. We investigate the SARSA algorithm with linear function approximation under the non-i.i.d. data, where a single sample trajectory is available. With a Lipschitz continuous policy improvement operator that is smooth enough, SARSA has been shown to converge asymptotically citeperkins2003convergent,melo2008analysis. However, its non-asymptotic analysis is challenging and remains unsolved due to the non-i.i.d. samples and the fact that the behavior policy changes dynamically with time. In this paper, we develop a novel technique to explicitly characterize the stochastic bias of a type of stochastic approximation procedures with time-varying Markov transition kernels. Our approach enables non-asymptotic convergence analyses of this type of stochastic approximation algorithms, which may be of independent interest. Using our bias characterization technique and a gradient descent type of analysis, we provide the finite-sample analysis on the mean square error of the SARSA algorithm. We then further study a fitted SARSA algorithm, which includes the original SARSA algorithm and its variant in citeperkins2003convergent as special cases. This fitted SARSA algorithm provides a more general framework for textititerative on-policy fitted policy iteration, which is more memory and computationally efficient. For this fitted SARSA algorithm, we also provide its finite-sample analysis.

Key facts. Cited by 85 papers in the map (data through 14 Oct 2026). First posted on arXiv 6 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 21; 2022: 18; 2023: 13; 2024: 11; 2025: 15; 2026: 7.

85 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  2. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  3. 2022q-Learning in Continuous Timecited by 91
  4. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  5. 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guaranteescited by 42
  6. 2021Deeply-Debiased Off-Policy Interval Estimationcited by 36
  7. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  8. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  9. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 31
  10. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
  11. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  12. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 19
38 more
  1. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  2. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 17
  3. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  4. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 17
  5. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  6. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  7. 2023TD Convergence: An Optimization Perspectivecited by 16
  8. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  9. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  10. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 14
  11. 2022Offline Reinforcement Learning with Closed-Form Policy Improvement Operatorscited by 14
  12. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  13. 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13
  14. 2022Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guaranteescited by 12
  15. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 12
  16. 2021Truncated Emphatic Temporal Difference Methods for Prediction and Controlcited by 10
  17. 2022Statistically Efficient Advantage Learning for Offline Reinforcement Learning in Infinite Horizonscited by 10
  18. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 10
  19. 2022Analysis of Stochastic Processes through Replay Bufferscited by 9
  20. 2022Robust Knowledge Adaptation for Dynamic Graph Neural Networkscited by 9
  21. 2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8
  22. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  23. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
  24. 2021Sim and Real: Better Togethercited by 7
  25. 2023Revisiting a Design Choice in Gradient Temporal Difference Learningcited by 7
  26. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 7
  27. 2021Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexitycited by 5
  28. 2021Successive Convex Approximation Based Off-Policy Optimization for Constrained Reinforcement Learningcited by 5
  29. 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settingscited by 5
  30. 2022Data Sampling Affects the Complexity of Online SGD over Dependent Datacited by 5
  31. 2024Graphon Mean Field Games with a Representative Player: Analysis and Learning Algorithmcited by 5
  32. 2024SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learningcited by 5
  33. 2024Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximationcited by 5
  34. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  35. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 5
  36. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  37. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  38. 2022A Multi-Agent Reinforcement Learning Framework for Off-Policy Evaluation in Two-sided Marketscited by 4

50 most cited of 85 All 85 (JSON)