Finite-Sample Analysis of LSTD - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

Finite-Sample Analysis of LSTD

(1) , (1) , (1)
Alessandro Lazaric
Mohammad Ghavamzadeh
  • Function : Author
  • PersonId : 868946
Remi Munos
  • Function : Author
  • PersonId : 836863


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 $\beta$-mixing.
Fichier principal
Vignette du fichier
lstd-tech.pdf (303.36 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00482189 , version 1 (09-05-2010)


  • HAL Id : inria-00482189 , version 1


Alessandro Lazaric, Mohammad Ghavamzadeh, Remi Munos. Finite-Sample Analysis of LSTD. ICML - 27th International Conference on Machine Learning, Jun 2010, Haifa, Israel. pp.615-622. ⟨inria-00482189⟩
459 View
441 Download


Gmail Facebook Twitter LinkedIn More