Learning to Optimize via Information-Directed Sampling
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 informationdirected sampling can dramatically outperform upper confidence bound algorithms and Thompson sampling due to the way it measures information gain.
This paper presents a new general algorithm for Bayesian bandit problems, based on a tradeoff between the "information gain" of an action and its contribution to the regret. The idea is new and interesting, and the algorithm appears to display good performance on numerical simulations. However the general results stated for the method are comparable to that of other approaches and the claim that it can "dramatically outperform upper confidence bound algorithms and Thompson sampling" (in the introduction) appear to be excessive in light of the elements provided in Section 5 and 6. In addition, details of the algorithms given in the supplementary material suggest that the implementation is much more involved than that of UCB or Thompson Sampling. Regarding the latter aspect it is difficult to understand by reading the paper to which extend the algorithm can really be implemented and will be efficient. In particular, for which bandit problems are the quantities \alpha_t, g_t, \Delta_t easy to compute? The implementation for Beta-Bernoulli models can only be found in the supplementary material, and the authors almost never mention this classical example of bandit model in the main text. Explanations on how to compute g_t and \Delta_t should be given as early in the text as possible (and certainly not in the supplementary material only).The intuition on why the information gain is defined this way is not obvious: there are plenty of ways of realizing a tradoff between the two quantities \Delta_t and g_t: why not minimizing \Delta_t + 1/g_t for example? The proof of Proposition 2 should be provided in the main text, as (1) it is the theoretical cornerstone of the analysis (the bounds on \Phi_t(\pi^TS) following from previous work if I get it right); (2) it helps understanding why \Pi_t is chosen this way (or at least why this choice make the proof work!); (3) it is short.  The value of the counter-examples in Section 5 is somewhat uncertain as they appear to rely on very specific assumptions. In particular, the first counter-example relates to the very artificial setting of sparse linear bandits without observation noise and known 1-sparsity. In light of the authors' answer in the rebuttal regarding this comment, it is clear that the argument also relies on the fact that the arms are L1-normalized vectors of {0,1}^d, as omitting the normalization would make Thompson sampling select arms with more than one non-zero coordinate (just as the proposed method does). Note that in this (artificial) setting, L1-normalizing the arms is a curious choice as it makes all the arms that have more than one non-zero component inadmissible in the linear bandit model as they are convex combinations of others (ie. they could be removed from start, leaving only the d arms that have a single non-zero component). This being said, the main question here is what can be learned more generally from these very specific situations?In the numerical experiments, please specify that Figure (a) displays the Bayesian regret (drawing problems from the priors). You should also comment more on the difficulty of implementing IDS in the Bernoulli case compared to the other approaches. There is also big typo in the Lai and Robbins lower bound: the sum is before the fraction! (line 394). I didn't check the complexity of implementation for linear bandits: could you comment on how much complex it is compared to Thompson Sampling? Could you also give precisions on the modified version on GP-UCB that is mentioned in the text? In Section 1, it may be worth mentioning that the use of the mutual information to select the most informative actions is also a largely used principle in sensor networks (googling "information-based sensor" of "information-theoretic sensor" will bring up plenty of related references), although the combination with a regret measure is quite probably novel.Minor typos: 124: It's -> It is; 150: $R_t$ should be $R$ I guess; 177: "_the_ design"; 273: it should be \cP_t (the subscript t is missing); 562: 988888 ???.