# On the Convergence of SARSA with Linear Function Approximation

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 14 Feb 2022.

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

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [State of the Art Control of Atari Games Using Shallow Reinforcement Learning](https://mlsanity.com/paper/1512.01563/) (2015)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)

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

- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [C-MCTS: Safe Planning with Monte Carlo Tree Search](https://mlsanity.com/paper/2305.16209/) (2023)
- [Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation](https://mlsanity.com/paper/2408.08192/) (2024)
- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [Does DQN Learn?](https://mlsanity.com/paper/2205.13617/) (2022)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments](https://mlsanity.com/paper/2409.03897/) (2024)
- [Implicit Updates for Average-Reward Temporal Difference Learning](https://mlsanity.com/paper/2510.06149/) (2025)
- [Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents](https://mlsanity.com/paper/2512.17688/) (2025)
- [Temporal Difference Learning with Constrained Initial Representations](https://mlsanity.com/paper/2602.11800/) (2026)
- [Convergence of SARSA with linear function approximation: The random horizon case](https://mlsanity.com/paper/2306.04548/) (2023)
- [Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem](https://mlsanity.com/paper/2508.13963/) (2025)
- [Implicit Q-Learning and SARSA: Liberating Policy Control from Step-Size Calibration](https://mlsanity.com/paper/2601.18907/) (2026)

## Abstract (arXiv)

SARSA, a classical on-policy control algorithm for reinforcement learning, is known to chatter when combined with linear function approximation: SARSA does not diverge but oscillates in a bounded region. However, little is known about how fast SARSA converges to that region and how large the region is. In this paper, we make progress towards this open problem by showing the convergence rate of projected SARSA to a bounded region. Importantly, the region is much smaller than the region that we project into, provided that the magnitude of the reward is not too large. Existing works regarding the convergence of linear SARSA to a fixed point all require the Lipschitz constant of SARSA's policy improvement operator to be sufficiently small; our analysis instead applies to arbitrary Lipschitz constants and thus characterizes the behavior of linear SARSA for a new regime.