Lattimore, TorHutter, MarcusSunehag, Peter2015-08-142015-08-141532-4435http://hdl.handle.net/1885/14719We present a new algorithm for general reinforcement learning where the true environment is known to belong to a finite class of N arbitrary models. The algorithm is shown to be near-optimal for all but O(N log2 N) timesteps with high probability. Infinite classes are also considered where we show that compactness is a key criterion for determining the existence of uniform sample-complexity bounds. A matching lower bound is given for the finite case.© 2013 by the author(s).. Author can archive publisher’s version/PDF. http://www.sherpa.ac.uk/romeo/issn/1532-4435/ as at 14/8/15http://creativecommons.org/licenses/by/4.0/reinforcement learningsample complexityPAC bounds2013-06Creative Commons Attribution licence