Learning to Optimize via Information-Directed Sampling

By Daniel Russo, Benjamin Van Roy. 2014

336 citations recorded by the source corpus.

We propose information-directed sampling - a new algorithm for online optimization problems in which a decision-maker must balance between exploration and exploitation while learning from partial feedback. Each action is sampled in a manner that minimizes the ratio between the square of expected single-period regret and a measure of information gain: the mutual information between the optimal action and the next observation. We establish an expected regret bound for information-directed sampling that applies across a very general class of models and scales with the entropy of the optimal action distribution. For the widely studied Bernoulli and linear bandit models, we demonstrate simulation performance surpassing popular approaches, including upper confidence bound algorithms, Thompson sampling, and knowledge gradient. Further, we present simple analytic examples illustrating that information-directed sampling can dramatically outperform upper confidence bound algorithms and Thompson sampling due to the way it measures information gain.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

Citations in the corpus

Learning to reinforcement learn (2016, background): “Similar problems have been examined before as providing a challenge to standard bandit algorithms (see e.g. Russo and Van Roy, 2014).”
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, background): “Thompson Sampling (and UCB approaches) would never select such actions, even if they are worth their cost [32].”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “[56] Russo, D.”
Deep Exploration via Randomized Value Functions (2017, background): “On the other hand, for some problems with more complex information structures, it is possible to explore much more efficiently than does Thompson sampling [44].”
Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, methodology): “Our analysis is based on Russo and Van Roy [31] and Srinivas et al. [36], and also uses some techniques from Desautels et al. [8].”
Deep reinforcement learning: a survey (2020, background): “Information-directed sampling (Russo and Roy, 2014) measures the mutual information between the true optimal action and the next observation, and then selects an action to quantify the amount learned.”
Risk versus Uncertainty in Deep Learning: Bayes, Bootstrap and the Dangers of Dropout (2016, background): “For exploration, risk also makes any single observation less informative [27].”
Simple Bayesian Algorithms for Best Arm Identification (2016, background): “The decision-maker chooses a policy, or adaptive allocation rule, which is a (possibly randomized) rule for choosing a design In to measure as a function of past observations I1, Y1,I1 , ...”
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 .”