The sample-complexity of general reinforcement learning

Tor Lattimore; Marcus Hutter; Peter Sunehag

The sample-complexity of general reinforcement learning

Tor Lattimore, Marcus Hutter, Peter Sunehag

Research output: Contribution to conference › Paper › peer-review

22 Citations (Scopus)

Abstract

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 log² N) time-steps 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.

Original language	English
Pages	1065-1073
Number of pages	9
Publication status	Published - 2013
Event	30th International Conference on Machine Learning, ICML 2013 - Atlanta, GA, United States Duration: 16 Jun 2013 → 21 Jun 2013

Conference

Conference	30th International Conference on Machine Learning, ICML 2013
Country/Territory	United States
City	Atlanta, GA
Period	16/06/13 → 21/06/13

Cite this

@conference{754353c7575e4c0386fc6c62293ca0c0,

title = "The sample-complexity of general reinforcement learning",

abstract = "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) time-steps 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.",

author = "Tor Lattimore and Marcus Hutter and Peter Sunehag",

year = "2013",

language = "English",

pages = "1065--1073",

note = "30th International Conference on Machine Learning, ICML 2013 ; Conference date: 16-06-2013 Through 21-06-2013",

}

TY - CONF

T1 - The sample-complexity of general reinforcement learning

AU - Lattimore, Tor

AU - Hutter, Marcus

AU - Sunehag, Peter

PY - 2013

Y1 - 2013

N2 - 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) time-steps 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.

AB - 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) time-steps 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.

UR - http://www.scopus.com/inward/record.url?scp=84897514541&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84897514541

SP - 1065

EP - 1073

T2 - 30th International Conference on Machine Learning, ICML 2013

Y2 - 16 June 2013 through 21 June 2013

ER -

The sample-complexity of general reinforcement learning

Abstract

Conference

Other files and links

Fingerprint

Cite this