Finite-Sample Analysis of LSTD

Published 21 June 2010Open access

Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos

Citations49

TL;DR

The problem of policy evaluation in reinforcement learning, i.e., learning the value function of a fixed policy, using the least-squares temporal-difference (LSTD) learning algorithm, is considered and a finite-sample analysis of LSTD is reported.

Abstract

In this paper we consider the problem of policy evaluation in reinforcement learning, i.e., learning the value function of a fixed policy, using the least-squares temporal-difference (LSTD) learning algorithm. We report a finite-sample analysis of LSTD. We first derive a bound on the performance of the LSTD solution evaluated at the states generated by the Markov chain and used by the algorithm to learn an estimate of the value function. This result is general in the sense that no assumption is made on the existence of a stationary distribution for the Markov chain. We then derive generalization bounds in the case when the Markov chain possesses a stationary distribution and is β-mixing. 1.

Keywords

Computer ScienceDecision SciencesBiochemistry, Genetics and Molecular Biology

IEEE Transactions on Neural NetworksReinforcement Learning: An Introduction

25,692 Citations2005

MIT Press eBooksIntroduction to Reinforcement Learning

6,868 Citations1998Richard S. Sutton, Andrew G. Barto

In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning.

Markov Chains and Stochastic Stability

5,130 Citations1993Sean Meyn, Richard L. Tweedie

This second edition reflects the same discipline and style that marked out the original and helped it to become a classic: proofs are rigorous and concise, the range of applications is broad and knowledgeable, and key ideas are accessible to practitioners with limited mathematical background.

Springer series in statisticsA Distribution-Free Theory of Nonparametric Regression

1,738 Citations2002László Györfi, Michael Köhler +2 more

How to Construct Nonparametric Regression Estimates * Lower Bounds * Partitioning Estimates * Kernel Estimates * k-NN Estimates * Splitting the Sample * Cross Validation * Uniform Laws of Large Numbers

View PDF

IEEE Transactions on Automatic ControlAn analysis of temporal-difference learning with function approximation

1,202 Citations1997John N. Tsitsiklis, Benjamin Van Roy

It is proved that divergence may occur when updates are not based on trajectories of the Markov chain, which reconciles positive and negative results that have been discussed in the literature, regarding the soundness of temporal-difference learning.

View PDF

Machine LearningLinear Least-Squares algorithms for temporal difference learning

639 Citations1996Steven J. Bradtke, Andrew G. Barto

Two new temporal diffence algorithms based on the theory of linear least-squares function approximation, LS TD and RLS TD, are introduced and prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters.

View PDF

Applied Physics Letters10.1162/1532443041827907

446 Citations2000

The new algorithm, least-squares policy iteration (LSPI), learns the state-action value function which allows for action selection without a model and for incremental policy improvement within a policy-iteration framework.

View PDF

The Annals of ProbabilityRates of Convergence for Empirical Processes of Stationary Mixing Sequences

299 Citations1994Bin Yu

View PDF

Least-Squares Temporal Difference Learning

260 Citations1999Justin A. Boyan

This paper presents a simpler derivation of the LSTD algorithm, which generalizes from = 0 to arbitrary values of ; at the extreme of = 1, the resulting algorithm is shown to be a practical formulation of supervised linear regression.

Machine LearningLearning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path

250 Citations2007András Antos, Csaba Szepesvári +1 more

A finite-sample, high-probability bound on the performance of the computed policy that depends on the mixing rate of the trajectory, the capacity of the function set as measured by a novel capacity concept, the approximation power of thefunction set and the controllability properties of the MDP is found.

View PDF