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 trajectory is available. With a Lipschitz continuous policy improvement operator that is smooth enough, SARSA has been shown to converge asymptotically \cite{perkins2003convergent,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 \cite{perkins2003convergent} as special cases. This fitted SARSA algorithm provides a more general framework for \textit{iterative} on-policy fitted policy iteration, which is more memory and computationally efficient. For this fitted SARSA algorithm, we also provide its finite-sample analysis.

📄 PDF Abstract BibTeX arXiv:1902.02234

Code (0)

등록된 구현이 없습니다.

Tasks

Q-LearningReinforcement Learning

Methods 이 논문이 사용한 방법론

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},…

Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning

2024-01-27 · Chenyu Zhang, Han Wang, Aritra Mitra, James Anderson

Federated reinforcement learning (FRL) has emerged as a promising paradigm for reducing the sample complexity of reinforcement learning tasks by exploiting information from different agents. However, when each agent inte…

reinforcement-learning Reinforcement Learning

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…

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 …

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 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 …