%0 Conference Paper %1 sutton2008 %A Sutton, R.S. %A Szepesvári, Cs. %A Maei, H.R. %B NIPS %D 2008 %K GTD algorithm, approximation, function gradient learning, online prediction, reinforcement stochastic theory, %P 1609--1616 %T A Convergent O(n) Algorithm for Off-policy Temporal-difference Learning with Linear Function Approximation %X We introduce the first temporal-difference learning algorithm that is stable with linear function approximation and off-policy training, for any finite Markov decision process, behavior policy, and target policy, and whose complexity scales linearly in the number of parameters. We consider an i.i.d. policy-evaluation setting in which the data need not come from on-policy experience. The gradient temporal-difference (GTD) algorithm estimates the expected update vector of the TD(0) algorithm and performs stochastic gradient descent on its L2 norm. We prove that this algorithm is stable and convergent under the usual stochastic approximation conditions to the same least-squares solution as found by the LSTD, but without LSTD's quadratic computational complexity. GTD is online and incremental, and does not involve multiplying by products of likelihood ratios as in importance-sampling methods.

@inproceedings{sutton2008, abstract = {We introduce the first temporal-difference learning algorithm that is stable with linear function approximation and off-policy training, for any finite Markov decision process, behavior policy, and target policy, and whose complexity scales linearly in the number of parameters. We consider an i.i.d. policy-evaluation setting in which the data need not come from on-policy experience. The gradient temporal-difference (GTD) algorithm estimates the expected update vector of the TD(0) algorithm and performs stochastic gradient descent on its L2 norm. We prove that this algorithm is stable and convergent under the usual stochastic approximation conditions to the same least-squares solution as found by the LSTD, but without LSTD's quadratic computational complexity. GTD is online and incremental, and does not involve multiplying by products of likelihood ratios as in importance-sampling methods.}, added-at = {2020-03-17T03:03:01.000+0100}, author = {Sutton, R.S. and Szepesv{\'a}ri, {Cs}. and Maei, H.R.}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/2ae2eb05437d68f9027da6658faaba91e/csaba}, booktitle = {NIPS}, crossref = {NIPS21}, date-added = {2010-08-28 17:38:14 -0600}, date-modified = {2010-11-25 00:50:58 -0700}, ee = {http://books.nips.cc/papers/files/nips21/NIPS2008_0421.pdf}, interhash = {2cd17553b0213961edd86f4ea585fb67}, intrahash = {ae2eb05437d68f9027da6658faaba91e}, keywords = {GTD algorithm, approximation, function gradient learning, online prediction, reinforcement stochastic theory,}, pages = {1609--1616}, pdf = {papers/gtdnips08.pdf}, timestamp = {2020-03-17T03:03:01.000+0100}, title = {A Convergent {O}(n) Algorithm for Off-policy Temporal-difference Learning with Linear Function Approximation}, year = 2008 }