An Information-Theoretic Analysis of Thompson Sampling

By Daniel Russo, Benjamin Van Roy. 2014

466 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Science Applications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Management Science and Operations Research

Citations in the corpus

A Tutorial on Thompson Sampling (2017, background): “Subsequent papers have further developed this theory [43, 44, 45] and have studied extensions of Thompson sampling to reinforcement-learning [35, 46, 47, 48].”
Learning to Optimize via Information-Directed Sampling (2014, methodology): “Several such bounds were provided by Russo and Van Roy [25].”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “In particular, such a mutual information can be cast as the information gain (Schmidhuber, 1991; 2010; Sun et al., 2011; Still and Precup, 2012; Houthooft et al., 2016; Russo and Van Roy, 2016; 2018) for estimating w h , which is induced by observing � ( s h , a h ) in addition to D .”
Bao: Making Learned Query Optimization Practical (2020, background): “y plans produced by the optimizer (when given each hint set) represent the contextual information. To solve the bandit 1This process can be executed in parallel to maintain reaboth theoretical bounds [57] and real-world success [12]. The details of our approach are presented in Section 3. Mixing que”
Effective Diversity in Population-Based Reinforcement Learning (2020, methodology): “Specifically, we use Thompson Sampling [60, 55, 1, 46, 47].”
Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, background): “Some recent theoretical advances have characterised the performance of TS in sequential settings [3, 6, 31, 32].”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “Inspired by the insights from Condorcet dueling bandits, we also discuss how to refine the regret of D-TS in general Copeland dueling bandits.”
Time-Sensitive Bandit Learning and Satisficing Thompson Sampling (2017, methodology): “The regret analysis in [14] relates the regret an algorithm incurs to the information it acquires about the identity of optimal action They deﬁne the information ratio in a given period to be the ratio between the square of single-period expected regret and the information acquired about the…”
Parallelised Bayesian Optimisation via Thompson Sampling (2018, background): “TS has been explored for sequential BO [4, 39] and some recent theoretical advances have characterised the performance of TS in sequential settings [3, 7, 27, 35, 36].”
Bandit Algorithms (2020, background): “3 can be generalized to structured settings such as linear bandits [Russo and Roy, 2016].”
Stochastic matrix games with bandit feedback (2020, background): “In the single-player case it can be shown that Thompson sampling can only suffer high regret in any given round if it is also gaining information about the optimal action [35].”