Fast LSTD Using Stochastic Approximation: Finite Time Analysis and Application to Traffic Control
Abstract
We propose a stochastic approximation based method with randomisation of samples for policy evaluation using the least squares temporal difference (LSTD) algorithm. Our method results in an O ( d ) improvement in complexity in comparison to regular LSTD, where d is the dimension of the data. We provide convergence rate results for our proposed method, both in high probability and in expectation. Moreover, we also establish that using our scheme in place of LSTD does not impact the rate of convergence of the approximate value function to the true value function. This result coupled with the low complexity of our method makes it attractive for implementation in big data settings, where d is large. Further, we also analyse a similar low-complexity alternative for least squares regression and provide finite-time bounds there. We demonstrate the practicality of our method for LSTD empirically by combining it with the LSPI algorithm in a traffic signal control application.
Cite
Text
Prashanth et al. "Fast LSTD Using Stochastic Approximation: Finite Time Analysis and Application to Traffic Control." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2014. doi:10.1007/978-3-662-44851-9_5Markdown
[Prashanth et al. "Fast LSTD Using Stochastic Approximation: Finite Time Analysis and Application to Traffic Control." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2014.](https://mlanthology.org/ecmlpkdd/2014/a2014ecmlpkdd-fast/) doi:10.1007/978-3-662-44851-9_5BibTeX
@inproceedings{a2014ecmlpkdd-fast,
title = {{Fast LSTD Using Stochastic Approximation: Finite Time Analysis and Application to Traffic Control}},
author = {Prashanth, L. A. and Korda, Nathaniel and Munos, Rémi},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2014},
pages = {66-81},
doi = {10.1007/978-3-662-44851-9_5},
url = {https://mlanthology.org/ecmlpkdd/2014/a2014ecmlpkdd-fast/}
}