Cultural advice

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.

Aboriginal and Torres Strait Islander peoples are advised that ANU Library collections may include images, names, voices, and other representations of deceased persons.

Material in the collection may contain terms, language or views that reflect the period in which the item was created and may be considered inappropriate today.

The sample-complexity of general reinforcement learning

Thumbnail Image

Date

2013-06

Authors

Lattimore, Tor
Hutter, Marcus
Sunehag, Peter

Journal Title

Journal ISSN

Volume Title

Publisher

Journal of Machine Learning Research

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

Description

Keywords

reinforcement learning, sample complexity, PAC bounds

Citation

URI

http://hdl.handle.net/1885/14719

Collections

ANU Research Publications

Source

Type

Conference paper

Book Title

Proceedings of The 30th International Conference on Machine Learning

Entity type

Access Statement

Open Access

License Rights

Creative Commons Attribution licence

DOI

Restricted until

Downloads

File
Description
Lattimore et al The Sample Complexity 2013.pdf (393.56 KB)

DSpace software copyright © 2002-2026 LYRASIS