Skip navigation
Skip navigation

The sample-complexity of general reinforcement learning

Lattimore, Tor; Hutter, Marcus; Sunehag, Peter


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

CollectionsANU Research Publications
Date published: 2013-06
Type: Conference paper


File Description SizeFormat Image
Lattimore et al The Sample Complexity 2013.pdf393.56 kBAdobe PDFThumbnail

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator