On the Convergence of SARSA with Linear Function Approximation

2022-02-14 · Shangtong Zhang, Remi Tachet, Romain Laroche

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.

📄 PDF Abstract BibTeX arXiv:2202.06828

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Expected Sarsa Expected Sarsa is like Q-learning but instead of taking the maximum over next state-action pairs, we use the expected value,…

Sarsa Sarsa is an on-policy TD control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} + \gamma{Q}\left(S\_{t+1},…

Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents

2025-12-19 · Paul Mangold, Eloïse Berthier, Eric Moulines arxiv

We present a novel theoretical analysis of Federated SARSA (FedSARSA) with linear function approximation and local training. We establish convergence guarantees for FedSARSA in the presence of heterogeneity, both in loca…

Convergence of SARSA with linear function approximation: The random horizon case

2023-06-07 · Lina Palmborg

The reinforcement learning algorithm SARSA combined with linear function approximation has been shown to converge for infinite horizon discounted Markov decision problems (MDPs). In this paper, we investigate the converg…

reinforcement-learning

On Convergence of Gradient Expected Sarsa($λ$)

2020-12-14 · Long Yang, Gang Zheng, Yu Zhang, Qian Zheng 외

We study the convergence of $\mathtt{Expected~Sarsa}(\lambda)$ with linear function approximation. We show that applying the off-line estimate (multi-step bootstrapping) to $\mathtt{Expected~Sarsa}(\lambda)$ is unstable …

Finite-Sample Analysis for SARSA with Linear Function Approximation

2019-02-06 · NeurIPS 2019 12 · Shaofeng Zou, Tengyu Xu, Yingbin Liang

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…

Q-Learning Reinforcement Learning

Online Transfer Learning in Reinforcement Learning Domains

2015-07-02 · Yusen Zhan, Matthew E. Taylor

This paper proposes an online transfer framework to capture the interaction among agents and shows that current transfer learning in reinforcement learning is a special case of online transfer. Furthermore, this paper re…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1