Finite-Sample Analysis for SARSA with Linear Function Approximation

2019/02/06 by Shaofeng Zou, Zou, Shaofeng, Tengyu Xu +3 · 11 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1902.02234

openalex publication_date 2019/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents
• Auto-exploration for online reinforcement learning
• Towards Formalizing Reinforcement Learning Theory
• A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies
• Implicit Updates for Average-Reward Temporal Difference Learning
• Generalized Fitted Q-Iteration with Clustered Data
• Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
• Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Actor-Critic Reinforcement Learning for Control with Stability Guarantee
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes

Related

• Convergence of SARSA with linear function approximation: The random horizon case
• On the Convergence of SARSA with Linear Function Approximation
• Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation