# Finite-Sample Analysis for SARSA with Linear Function Approximation

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

## Key facts

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

## Built on by (most cited first, 30 of 85)

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [q-Learning in Continuous Time](https://mlsanity.com/paper/2207.00713/) (2022)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2210.01808/) (2022)
- [Deeply-Debiased Off-Policy Interval Estimation](https://mlsanity.com/paper/2105.04646/) (2021)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process](https://mlsanity.com/paper/2110.10351/) (2021)
- [Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic](https://mlsanity.com/paper/2301.12083/) (2023)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [TD Convergence: An Optimization Perspective](https://mlsanity.com/paper/2306.17750/) (2023)
- [On the Convergence of SARSA with Linear Function Approximation](https://mlsanity.com/paper/2202.06828/) (2022)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation](https://mlsanity.com/paper/2106.07472/) (2021)
- [Offline Reinforcement Learning with Closed-Form Policy Improvement Operators](https://mlsanity.com/paper/2211.15956/) (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)
- [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021)
- [Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees](https://mlsanity.com/paper/2210.01282/) (2022)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Truncated Emphatic Temporal Difference Methods for Prediction and Control](https://mlsanity.com/paper/2108.05338/) (2021)
- [Statistically Efficient Advantage Learning for Offline Reinforcement Learning in Infinite Horizons](https://mlsanity.com/paper/2202.13163/) (2022)
- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)

## 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.