PAC bounds for discounted MDPs

Tor Lattimore; Marcus Hutter

doi:10.1007/978-3-642-34106-9_26

PAC bounds for discounted MDPs

Tor Lattimore^*, Marcus Hutter

^*Corresponding author for this work

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

78 Citations (Scopus)

Abstract

We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (mdps). We prove a new bound for a modified version of Upper Confidence Reinforcement Learning (ucrl) with only cubic dependence on the horizon. The bound is unimprovable in all parameters except the size of the state/action space, where it depends linearly on the number of non-zero transition probabilities. The lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors provided the transition matrix is not too dense.

Original language	English
Title of host publication	Algorithmic Learning Theory - 23rd International Conference, ALT 2012, Proceedings
Pages	320-334
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-34106-9_26
Publication status	Published - 2012
Event	23rd International Conference on Algorithmic Learning Theory, ALT 2012 - Lyon, France Duration: 29 Oct 2012 → 31 Oct 2012

Publication series

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

Conference

Conference	23rd International Conference on Algorithmic Learning Theory, ALT 2012
Country/Territory	France
City	Lyon
Period	29/10/12 → 31/10/12

Access to Document

10.1007/978-3-642-34106-9_26

Cite this

@inproceedings{249bd1b4f2814b628891d1b1daaa1620,

title = "PAC bounds for discounted MDPs",

abstract = "We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (mdps). We prove a new bound for a modified version of Upper Confidence Reinforcement Learning (ucrl) with only cubic dependence on the horizon. The bound is unimprovable in all parameters except the size of the state/action space, where it depends linearly on the number of non-zero transition probabilities. The lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors provided the transition matrix is not too dense.",

keywords = "Markov decision processes, PAC-MDP, Reinforcement learning, exploration exploitation, sample-complexity",

author = "Tor Lattimore and Marcus Hutter",

year = "2012",

doi = "10.1007/978-3-642-34106-9_26",

language = "English",

isbn = "9783642341052",

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

pages = "320--334",

booktitle = "Algorithmic Learning Theory - 23rd International Conference, ALT 2012, Proceedings",

note = "23rd International Conference on Algorithmic Learning Theory, ALT 2012 ; Conference date: 29-10-2012 Through 31-10-2012",

}

Lattimore, T & Hutter, M 2012, PAC bounds for discounted MDPs. in Algorithmic Learning Theory - 23rd International Conference, ALT 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7568 LNAI, pp. 320-334, 23rd International Conference on Algorithmic Learning Theory, ALT 2012, Lyon, France, 29/10/12. https://doi.org/10.1007/978-3-642-34106-9_26

PAC bounds for discounted MDPs. / Lattimore, Tor; Hutter, Marcus.
Algorithmic Learning Theory - 23rd International Conference, ALT 2012, Proceedings. 2012. p. 320-334 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7568 LNAI).

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

TY - GEN

T1 - PAC bounds for discounted MDPs

AU - Lattimore, Tor

AU - Hutter, Marcus

PY - 2012

Y1 - 2012

N2 - We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (mdps). We prove a new bound for a modified version of Upper Confidence Reinforcement Learning (ucrl) with only cubic dependence on the horizon. The bound is unimprovable in all parameters except the size of the state/action space, where it depends linearly on the number of non-zero transition probabilities. The lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors provided the transition matrix is not too dense.

AB - We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (mdps). We prove a new bound for a modified version of Upper Confidence Reinforcement Learning (ucrl) with only cubic dependence on the horizon. The bound is unimprovable in all parameters except the size of the state/action space, where it depends linearly on the number of non-zero transition probabilities. The lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors provided the transition matrix is not too dense.

KW - Markov decision processes

KW - PAC-MDP

KW - Reinforcement learning

KW - exploration exploitation

KW - sample-complexity

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

U2 - 10.1007/978-3-642-34106-9_26

DO - 10.1007/978-3-642-34106-9_26

M3 - Conference contribution

SN - 9783642341052

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

SP - 320

EP - 334

BT - Algorithmic Learning Theory - 23rd International Conference, ALT 2012, Proceedings

T2 - 23rd International Conference on Algorithmic Learning Theory, ALT 2012

Y2 - 29 October 2012 through 31 October 2012

ER -

PAC bounds for discounted MDPs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this