New error bounds for approximations from projected linear equations

Huizhen Yu; Dimitri P. Bertsekas

doi:10.1007/978-3-540-89722-4_20

New error bounds for approximations from projected linear equations

Huizhen Yu, Dimitri P. Bertsekas

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markovian decision processes (MDP), one of our bounds is always sharper than the standard worst case bounds, and another one is often sharper. Our bounds also apply to the non-contraction case, including policy evaluation in MDP with nonstandard projections that enhance exploration. There are no error bounds currently available for this case to our knowledge.

Original language	English (US)
Title of host publication	Recent Advances in Reinforcement Learning - 8th European Workshop, EWRL 2008, Revised and Selected Papers
Pages	253-267
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-540-89722-4_20
State	Published - 2008
Externally published	Yes
Event	8th European Workshop on Reinforcement Learning, EWRL 2008 - Villeneuve d'Ascq, France Duration: Jun 30 2008 → Jul 3 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5323 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th European Workshop on Reinforcement Learning, EWRL 2008
Country/Territory	France
City	Villeneuve d'Ascq
Period	6/30/08 → 7/3/08

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-89722-4_20

Cite this

Yu, H., & Bertsekas, D. P. (2008). New error bounds for approximations from projected linear equations. In Recent Advances in Reinforcement Learning - 8th European Workshop, EWRL 2008, Revised and Selected Papers (pp. 253-267). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5323 LNAI). https://doi.org/10.1007/978-3-540-89722-4_20

New error bounds for approximations from projected linear equations. / Yu, Huizhen; Bertsekas, Dimitri P.
Recent Advances in Reinforcement Learning - 8th European Workshop, EWRL 2008, Revised and Selected Papers. 2008. p. 253-267 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5323 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Yu, H & Bertsekas, DP 2008, New error bounds for approximations from projected linear equations. in Recent Advances in Reinforcement Learning - 8th European Workshop, EWRL 2008, Revised and Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5323 LNAI, pp. 253-267, 8th European Workshop on Reinforcement Learning, EWRL 2008, Villeneuve d'Ascq, France, 6/30/08. https://doi.org/10.1007/978-3-540-89722-4_20

Yu H, Bertsekas DP. New error bounds for approximations from projected linear equations. In Recent Advances in Reinforcement Learning - 8th European Workshop, EWRL 2008, Revised and Selected Papers. 2008. p. 253-267. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-89722-4_20

@inproceedings{45d2bd6886ca4268ad966ca363fb1950,

title = "New error bounds for approximations from projected linear equations",

abstract = "We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markovian decision processes (MDP), one of our bounds is always sharper than the standard worst case bounds, and another one is often sharper. Our bounds also apply to the non-contraction case, including policy evaluation in MDP with nonstandard projections that enhance exploration. There are no error bounds currently available for this case to our knowledge.",

author = "Huizhen Yu and Bertsekas, {Dimitri P.}",

year = "2008",

doi = "10.1007/978-3-540-89722-4_20",

language = "English (US)",

isbn = "3540897216",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "253--267",

booktitle = "Recent Advances in Reinforcement Learning - 8th European Workshop, EWRL 2008, Revised and Selected Papers",

}

TY - GEN

T1 - New error bounds for approximations from projected linear equations

AU - Yu, Huizhen

AU - Bertsekas, Dimitri P.

PY - 2008

Y1 - 2008

N2 - We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markovian decision processes (MDP), one of our bounds is always sharper than the standard worst case bounds, and another one is often sharper. Our bounds also apply to the non-contraction case, including policy evaluation in MDP with nonstandard projections that enhance exploration. There are no error bounds currently available for this case to our knowledge.

AB - We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markovian decision processes (MDP), one of our bounds is always sharper than the standard worst case bounds, and another one is often sharper. Our bounds also apply to the non-contraction case, including policy evaluation in MDP with nonstandard projections that enhance exploration. There are no error bounds currently available for this case to our knowledge.

UR - http://www.scopus.com/inward/record.url?scp=58449106856&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449106856&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-89722-4_20

DO - 10.1007/978-3-540-89722-4_20

M3 - Conference contribution

AN - SCOPUS:58449106856

SN - 3540897216

SN - 9783540897217

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 253

EP - 267

BT - Recent Advances in Reinforcement Learning - 8th European Workshop, EWRL 2008, Revised and Selected Papers

T2 - 8th European Workshop on Reinforcement Learning, EWRL 2008

Y2 - 30 June 2008 through 3 July 2008

ER -

New error bounds for approximations from projected linear equations

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this