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.
Cite
Text
Lattimore and Hutter. "PAC Bounds for Discounted MDPs." International Conference on Algorithmic Learning Theory, 2012. doi:10.1007/978-3-642-34106-9_26Markdown
[Lattimore and Hutter. "PAC Bounds for Discounted MDPs." International Conference on Algorithmic Learning Theory, 2012.](https://mlanthology.org/alt/2012/lattimore2012alt-pac/) doi:10.1007/978-3-642-34106-9_26BibTeX
@inproceedings{lattimore2012alt-pac,
title = {{PAC Bounds for Discounted MDPs}},
author = {Lattimore, Tor and Hutter, Marcus},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2012},
pages = {320-334},
doi = {10.1007/978-3-642-34106-9_26},
url = {https://mlanthology.org/alt/2012/lattimore2012alt-pac/}
}