An information-theoretic analysis of Thompson sampling

Daniel Russo; Benjamin Van Roy

An information-theoretic analysis of Thompson sampling

Daniel Russo, Benjamin Van Roy

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

111 Scopus citations

Abstract

We provide an information-theoretic analysis of Thompson sampling that applies across a broad range of online optimization problems in which a decision-maker must learn from partial feedback. This analysis inherits the simplicity and elegance of information theory and leads to regret bounds that scale with the entropy of the optimal-action distribution. This strengthens preexisting results and yields new insight into how information improves performance.

Original language	English (US)
Journal	Journal of Machine Learning Research
Volume	17
State	Published - Apr 1 2016

Keywords

Information theory
Mutli-armed bandit
Online optimization
Regret bounds
Thompson sampling

ASJC Scopus subject areas

Software
Control and Systems Engineering
Statistics and Probability
Artificial Intelligence

Cite this

@article{b1d8a8e0f232483087cddb20105c7125,

title = "An information-theoretic analysis of Thompson sampling",

abstract = "We provide an information-theoretic analysis of Thompson sampling that applies across a broad range of online optimization problems in which a decision-maker must learn from partial feedback. This analysis inherits the simplicity and elegance of information theory and leads to regret bounds that scale with the entropy of the optimal-action distribution. This strengthens preexisting results and yields new insight into how information improves performance.",

keywords = "Information theory, Mutli-armed bandit, Online optimization, Regret bounds, Thompson sampling",

author = "Daniel Russo and {Van Roy}, Benjamin",

note = "Funding Information: Daniel Russo is supported by a Burt and Deedee McMurty Stanford Graduate Fellowship. This work was supported, in part, by the National Science Foundation under Grant CMMI-0968707. The authors would like to thank the anonymous reviewers for their helpful comments. Publisher Copyright: {\textcopyright}2016 Daniel Russo and Benjamin Van Roy.",

year = "2016",

month = apr,

day = "1",

language = "English (US)",

volume = "17",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

}

TY - JOUR

T1 - An information-theoretic analysis of Thompson sampling

AU - Russo, Daniel

AU - Van Roy, Benjamin

N1 - Funding Information: Daniel Russo is supported by a Burt and Deedee McMurty Stanford Graduate Fellowship. This work was supported, in part, by the National Science Foundation under Grant CMMI-0968707. The authors would like to thank the anonymous reviewers for their helpful comments. Publisher Copyright: ©2016 Daniel Russo and Benjamin Van Roy.

PY - 2016/4/1

Y1 - 2016/4/1

N2 - We provide an information-theoretic analysis of Thompson sampling that applies across a broad range of online optimization problems in which a decision-maker must learn from partial feedback. This analysis inherits the simplicity and elegance of information theory and leads to regret bounds that scale with the entropy of the optimal-action distribution. This strengthens preexisting results and yields new insight into how information improves performance.

AB - We provide an information-theoretic analysis of Thompson sampling that applies across a broad range of online optimization problems in which a decision-maker must learn from partial feedback. This analysis inherits the simplicity and elegance of information theory and leads to regret bounds that scale with the entropy of the optimal-action distribution. This strengthens preexisting results and yields new insight into how information improves performance.

KW - Information theory

KW - Mutli-armed bandit

KW - Online optimization

KW - Regret bounds

KW - Thompson sampling

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

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

M3 - Article

AN - SCOPUS:84979947876

SN - 1532-4435

VL - 17

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

ER -

An information-theoretic analysis of Thompson sampling

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this