conftrace_

2016 JMLR JMLR 2016

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. [abs] [ pdf ][ bib ] © JMLR 2016. (edit, beta)

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization

🐣 Hot Topic Early Bird - thompson sampling

Authors

Daniel Russo, Benjamin Van Roy

Topics

Artificial Intelligence > Bayesian & Probabilistic > Bayesian Learning Machine Learning > Optimization & Theory > Bayesian Inference Mathematics & Optimization > Mathematics > Information Theory Mathematics & Optimization > Optimization > Online Algorithms Machine Learning > Optimization & Theory > Information Theory Machine Learning > Learning Types > Multi-Armed Bandits

Keywords

information theory online optimization thompson sampling partial feedback multi-armed bandit regret bound

More from JMLR 2016

All JMLR 2016 papers →

Stereo Matching by Training a Convolutional Neural Network to Compare Image Patches

Bayesian Policy Gradient and Actor-Critic Algorithms

Practical Kernel-Based Reinforcement Learning

Compressed Gaussian Process for Manifold Regression

On the Characterization of a Class of Fisher-Consistent Loss Functions and its Application to Boosting

Exact Inference on Gaussian Graphical Models of Arbitrary Topology using Path-Sums