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