mlsanityData to 14 Oct 2026

On the Convergence of SARSA with Linear Function Approximation

arXiv 2202.06828 ↗First posted 14 Feb 2022cs.LGcited by 15

Not on the map. Why?

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.

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

9 of 42 references.

References · 9

  1. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  4. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  5. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  6. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  7. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  8. 2015State of the Art Control of Atari Games Using Shallow Reinforcement Learningcited by 23
  9. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 3; 2025: 7; 2026: 2.

15 papers.

Sort:

By area:

  1. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 12
  2. 2023C-MCTS: Safe Planning with Monte Carlo Tree Searchcited by 6
  3. 2024Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximationcited by 5
  4. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  5. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  6. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  7. 2022Does DQN Learn?cited by 4
  8. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 4
  9. 2024On the Convergence Rates of Federated Q-Learning across Heterogeneous Environmentscited by 2
  10. 2025Implicit Updates for Average-Reward Temporal Difference Learningcited by 2
  11. 2025Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agentscited by 2
  12. 2026Temporal Difference Learning with Constrained Initial Representationscited by 2
3 more
  1. 2023Convergence of SARSA with linear function approximation: The random horizon casecited by 0
  2. 2025Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problemcited by 0
  3. 2026Implicit Q-Learning and SARSA: Liberating Policy Control from Step-Size Calibrationcited by 0