Search Machine Learning Repository: The Sample-Complexity of General Reinforcement Learning
Authors: Tor Lattimore, Marcus Hutter and Peter Sunehag
Conference: Proceedings of the 30th International Conference on Machine Learning (ICML-13)
Year: 2013
Pages: 28-36
Abstract: We study the sample-complexity of reinforcement learning in a general setting without assuming ergodicity or finiteness of the environment. Instead, we define a topology on the space of environments and show that if an environment class is compact with respect to this topology then finite sample-complexity bounds are possible and give an algorithm achieving these bounds. We also show the existence of environment classes that are non-compact where finite sample-complexity bounds are not achievable. A lower bound is presented that matches the upper bound except for logarithmic factors.
[pdf] [BibTeX]

authors venues years
Suggest Changes to this paper.
Brought to you by the WUSTL Machine Learning Group. We have open faculty positions (tenured and tenure-track).