Finite-Sample Analysis for SARSA with Linear Function Approximation

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

NeurIPS 2019

Cited by in corpus (34)

• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Successive Convex Approximation Based Off-Policy Optimization for Constrained Reinforcement Learning
• Finite-Time Analysis for Double Q-learning
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
• Actor-Critic Reinforcement Learning for Control with Stability Guarantee
• Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Making
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Deeply-Debiased Off-Policy Interval Estimation
• Online Robust Reinforcement Learning with Model Uncertainty
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Breaking the Deadly Triad with a Target Network
• On the Analysis of Model-free Methods for the Linear Quadratic Regulator
• Reinforcement Learning Control of Constrained Dynamic Systems with Uniformly Ultimate Boundedness Stability Guarantee
• Truncated Emphatic Temporal Difference Methods for Prediction and Control
• Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Predictor-Corrector(PC) Temporal Difference(TD) Learning (PCTD)
• On Convergence of Gradient Expected Sarsa($\lambda$)
• Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs