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)
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.
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).