Thompson Sampling is Asymptotically Optimal in General Environments

Jan Leike; Tor Lattimore; Laurent Orseau; Marcus Hutter

Thompson Sampling is Asymptotically Optimal in General Environments

Jan Leike, Tor Lattimore, Laurent Orseau, Marcus Hutter

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that (1) asymptotically its value converges to the optimal value in mean and (2) given a recoverability assumption regret is sublinear.

Original language	English
Title of host publication	Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence
Editors	Alexander Ihler and Dominik Janzing
Place of Publication	Canada
Publisher	AUAI Press
Pages	417-426pp
Edition	Peer reviewed
ISBN (Print)	9781510827806
Publication status	Published - 2016
Event	32nd Conference on Uncertainty in Artificial Intelligence 2016 - Jersey City, New Jersey, USA Duration: 1 Jan 2016 → …

Conference

Conference	32nd Conference on Uncertainty in Artificial Intelligence 2016
Period	1/01/16 → …
Other	June 25-29 2016

Cite this

@inproceedings{38cfe076f9354c84af5747f87d1ba40e,

title = "Thompson Sampling is Asymptotically Optimal in General Environments",

abstract = "We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that (1) asymptotically its value converges to the optimal value in mean and (2) given a recoverability assumption regret is sublinear.",

author = "Jan Leike and Tor Lattimore and Laurent Orseau and Marcus Hutter",

year = "2016",

language = "English",

isbn = "9781510827806",

pages = "417--426pp",

editor = "{Alexander Ihler and Dominik Janzing}",

booktitle = "Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence",

publisher = "AUAI Press",

edition = "Peer reviewed",

note = "32nd Conference on Uncertainty in Artificial Intelligence 2016 ; Conference date: 01-01-2016",

}

Thompson Sampling is Asymptotically Optimal in General Environments. / Leike, Jan; Lattimore, Tor; Orseau, Laurent et al.
Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence. ed. / Alexander Ihler and Dominik Janzing. Peer reviewed. ed. Canada: AUAI Press, 2016. p. 417-426pp.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Thompson Sampling is Asymptotically Optimal in General Environments

AU - Leike, Jan

AU - Lattimore, Tor

AU - Orseau, Laurent

AU - Hutter, Marcus

PY - 2016

Y1 - 2016

N2 - We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that (1) asymptotically its value converges to the optimal value in mean and (2) given a recoverability assumption regret is sublinear.

AB - We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that (1) asymptotically its value converges to the optimal value in mean and (2) given a recoverability assumption regret is sublinear.

M3 - Conference contribution

SN - 9781510827806

SP - 417

EP - 426

BT - Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence

A2 - null, Alexander Ihler and Dominik Janzing

PB - AUAI Press

CY - Canada

T2 - 32nd Conference on Uncertainty in Artificial Intelligence 2016

Y2 - 1 January 2016

ER -

Thompson Sampling is Asymptotically Optimal in General Environments

Abstract

Conference

Fingerprint

Cite this