inria-00116936, version 2

arXiv:cs.LG/0611145

See detailed view

BibTeX  EndNote  TEI  RefWorks %% inria-00116936, version 2 %% http://hal.inria.fr/inria-00116936/en/ @inproceedings{LOTH:2006:INRIA-00116936:2, title = { {A} {U}nified {V}iew of {TD} {A}lgorithms; {I}ntroducing {F}ull-{G}radient {TD} and {E}qui-{G}radient {D}escent {TD}}, author = {{L}oth, {M}anuel and {P}reux, {P}hilippe and {D}avy, {M}anuel}, abstract = {{T}his paper addresses the issue of policy evaluation in {M}arkov {D}ecision {P}rocesses, using linear function approximation. {I}t provides a unified view of algorithms such as {TD}(lambda), {LSTD}(lambda), i{LSTD}, residual-gradient {TD}. {I}t is asserted that they all consist in minimizing a gradient function and differ by the form of this function and their means of minimizing it. {T}wo new schemes are introduced in that framework: {F}ull-gradient {TD} which uses a generalization of the principle introduced in i{LSTD}, and {EGD} {TD}, which reduces the gradient by successive equi-gradient descents. {T}hese three algorithms form a new intermediate family with the interesting property of making much better use of the samples than {TD} while keeping a gradient descent scheme, which is useful for complexity issues and optimistic policy iteration.}, keywords = {temporal difference reinforcement learning markov decision process}, language = {{E}nglish}, affiliation = {{SEQUEL} - {INRIA} {F}uturs - {INRIA} - {CNRS} : {UMR}8022 - {CNRS} : {UMR}8146 - {U}niversit{\'e} des {S}ciences et {T}echnologies de {L}ille - {L}ille {I} - {U}niversit{\'e} {C}harles de {G}aulle - {L}ille {III} - {E}cole {C}entrale de {L}ille - {G}rappa - {LIFL} - {GRAPPA} - {CNRS} : {UMR}8022 - {U}niversit{\'e} {C}harles de {G}aulle - {L}ille {III} - {L}aboratoire d'{A}utomatique, {G}{\'e}nie {I}nformatique et {S}ignal - {LAGIS} - {CNRS} : {UMR}8146 - {U}niversit{\'e} des {S}ciences et {T}echnologies de {L}ille - {L}ille {I} - {E}cole {C}entrale de {L}ille }, booktitle = {{E}uropean {S}ymposium on {A}rtificial {N}eural {N}etworks }, address = {{B}ruges, {B}elgium }, note = {{I}.: {C}omputing {M}ethodologies/{I}.2: {ARTIFICIAL} {INTELLIGENCE}/{I}.2.8: {P}roblem {S}olving, {C}ontrol {M}ethods, and {S}earch/{I}.2.8.1: {C}ontrol theory }, audience = {not specified }, day = {25}, month = {04}, year = {2007}, URL = {http://hal.inria.fr/inria-00116936/en/}, URL = {http://hal.inria.fr/inria-00116936/PDF/unified.pdf}, } %F inria-00116936, version 2 %0 Conference Proceedings %U http://hal.inria.fr/inria-00116936/en/ %2 INFO:INFO_LG %T A Unified View of TD Algorithms; Introducing Full-Gradient TD and Equi-Gradient Descent TD %A Loth, Manuel %A Preux, Philippe %A Davy, Manuel %A Loth, M. %A Preux, P. %A Davy, M. %A Loth M. et al %+ SEQUEL - INRIA Futurs - INRIA - CNRS : UMR8022 - CNRS : UMR8146 - Université des Sciences et Technologies de Lille - Lille I - Université Charles de Gaulle - Lille III - Ecole Centrale de Lille - Grappa - LIFL - GRAPPA - CNRS : UMR8022 - Université Charles de Gaulle - Lille III - Laboratoire d'Automatique, Génie Informatique et Signal - LAGIS - CNRS : UMR8146 - Université des Sciences et Technologies de Lille - Lille I - Ecole Centrale de Lille %X This paper addresses the issue of policy evaluation in Markov Decision Processes, using linear function approximation. It provides a unified view of algorithms such as TD(lambda), LSTD(lambda), iLSTD, residual-gradient TD. It is asserted that they all consist in minimizing a gradient function and differ by the form of this function and their means of minimizing it. Two new schemes are introduced in that framework: Full-gradient TD which uses a generalization of the principle introduced in iLSTD, and EGD TD, which reduces the gradient by successive equi-gradient descents. These three algorithms form a new intermediate family with the interesting property of making much better use of the samples than TD while keeping a gradient descent scheme, which is useful for complexity issues and optimistic policy iteration. %2 I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.8: Problem Solving, Control Methods, and Search/I.2.8.1: Control theory %G English %8 2007-04-25 %2 not specified %B European Symposium on Artificial Neural Networks %2 Bruges, Belgium %8 2007-04-25 %K temporal difference reinforcement learning markov decision process %2 2006 <?xml version="1.0" encoding="UTF-8"?> <listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML"> <listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head> <biblStruct type="inproceedings" xml:id="inria-00116936"><analytic> <author><persName><forename>Manuel</forename><surname>Loth</surname></persName> <affiliation> <orgName type="laboratory">INRIA Futurs</orgName> <orgName type="team">SEQUEL</orgName> <country>FR</country> <orgName type="institution">INRIA</orgName> <orgName type="institution">CNRS : UMR8022</orgName> <orgName type="institution">CNRS : UMR8146</orgName> <orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName> <orgName type="institution">Université Charles de Gaulle - Lille III</orgName> <orgName type="institution">Ecole Centrale de Lille</orgName> </affiliation> <affiliation> <orgName type="laboratory">GRAPPA</orgName> <orgName type="team">Grappa - LIFL</orgName> <country>FR</country> <orgName type="institution">CNRS : UMR8022</orgName> <orgName type="institution">Université Charles de Gaulle - Lille III</orgName> </affiliation> </author> <author><persName><forename>Philippe</forename><surname>Preux</surname></persName> <affiliation> <orgName type="laboratory">INRIA Futurs</orgName> <orgName type="team">SEQUEL</orgName> <country>FR</country> <orgName type="institution">INRIA</orgName> <orgName type="institution">CNRS : UMR8022</orgName> <orgName type="institution">CNRS : UMR8146</orgName> <orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName> <orgName type="institution">Université Charles de Gaulle - Lille III</orgName> <orgName type="institution">Ecole Centrale de Lille</orgName> </affiliation> <affiliation> <orgName type="laboratory">GRAPPA</orgName> <orgName type="team">Grappa - LIFL</orgName> <country>FR</country> <orgName type="institution">CNRS : UMR8022</orgName> <orgName type="institution">Université Charles de Gaulle - Lille III</orgName> </affiliation> </author> <author><persName><forename>Manuel</forename><surname>Davy</surname></persName> <affiliation> <orgName type="laboratory">INRIA Futurs</orgName> <orgName type="team">SEQUEL</orgName> <country>FR</country> <orgName type="institution">INRIA</orgName> <orgName type="institution">CNRS : UMR8022</orgName> <orgName type="institution">CNRS : UMR8146</orgName> <orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName> <orgName type="institution">Université Charles de Gaulle - Lille III</orgName> <orgName type="institution">Ecole Centrale de Lille</orgName> </affiliation> <affiliation> <orgName type="laboratory">LAGIS</orgName> <orgName type="team">Laboratoire d'Automatique, Génie Informatique et Signal</orgName> <country>FR</country> <orgName type="institution">CNRS : UMR8146</orgName> <orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName> <orgName type="institution">Ecole Centrale de Lille</orgName> </affiliation> </author> <title type="main" level="a">A Unified View of TD Algorithms; Introducing Full-Gradient TD and Equi-Gradient Descent TD</title></analytic><monogr><meeting>European Symposium on Artificial Neural Networks</meeting><imprint><pubPlace><settlement>Bruges</settlement><country> Belgium</country></pubPlace><biblScope type="publicationDate">2007-04-25</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00116936/en/</idno><idno type="HALFile">http://hal.inria.fr/inria-00116936/PDF/unified.pdf</idno></biblStruct> </listBibl> </listBibl>

A Unified View of TD Algorithms; Introducing Full-Gradient TD and Equi-Gradient Descent TD Manuel Loth () a, 1, 2, Philippe Preux () b, 1, 2, Manuel Davy c, 1, 3 (2006)

Access to full text PS PDF

European Symposium on Artificial Neural Networks (2007)

Abstract: This paper addresses the issue of policy evaluation in Markov Decision Processes, using linear function approximation. It provides a unified view of algorithms such as TD(lambda), LSTD(lambda), iLSTD, residual-gradient TD. It is asserted that they all consist in minimizing a gradient function and differ by the form of this function and their means of minimizing it. Two new schemes are introduced in that framework: Full-gradient TD which uses a generalization of the principle introduced in iLSTD, and EGD TD, which reduces the gradient by successive equi-gradient descents. These three algorithms form a new intermediate family with the interesting property of making much better use of the samples than TD while keeping a gradient descent scheme, which is useful for complexity issues and optimistic policy iteration.

a –	Université des Sciences et Technologie de Lille - Lille I
b –	Université Charles de Gaulle - Lille III
c –	Ecole Centrale de Lille
1:	SEQUEL (INRIA Futurs)
	INRIA – CNRS : UMR8022 – CNRS : UMR8146 – Université des Sciences et Technologies de Lille - Lille I – Université Charles de Gaulle - Lille III – Ecole Centrale de Lille
2:	Grappa - LIFL (GRAPPA)
	CNRS : UMR8022 – Université Charles de Gaulle - Lille III
3:	Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS)
	CNRS : UMR8146 – Université des Sciences et Technologies de Lille - Lille I – Ecole Centrale de Lille

Domain

:

Computer Science/Learning

Keywords : temporal difference reinforcement learning markov decision process

Available versions:

v1 (2006-11-29)

v2 (2006-11-29)

inria-00116936, version 2

http://hal.inria.fr/inria-00116936/en/

oai:hal.inria.fr:inria-00116936_v2

From: Manuel Loth <>

Submitted on: Wednesday, 29 November 2006 10:12:47

Updated on: Monday, 28 May 2007 19:56:53