PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Optimize via Information-Directed Sampling

Daniel Russo, Benjamin Van Roy

arXiv:1403.5556v7cs.LG

TL;DR

Online optimization with complex information structures requires methods that use information from one action to learn about others. The paper proposes information-directed sampling, establishes general regret guarantees, and reports strong empirical performance across several bandit settings.

  • Problem

    Existing approaches extend UCB and Thompson sampling to complex information structures, creating a need for algorithms that take those structures into account more effectively.

  • Method

    The paper proposes information-directed sampling and develops a general regret analysis for it across online optimization models.

  • Results

    IDS can dramatically outperform UCB, Thompson sampling, and knowledge-gradient algorithms in analytic examples, while achieving order-optimal bounds up to a poly-logarithmic factor in several problem classes.

  • Takeaways & Limitations

    IDS sometimes greatly outperforms popular approaches that do not carefully measure the information provided by sampled actions, with simulations surpassing those approaches in several widely studied bandit classes.

  • Takeaways & Limitations

    The paper does not pursue extending IDS to discounted problems where time preference is important.

Abstract

from arXiv · show

We propose information-directed sampling -- a new approach to 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 squared 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. We illustrate through simple analytic examples how information-directed sampling accounts for kinds of information that alternative approaches do not adequately address and that this can lead to dramatic performance gains. For the widely studied Bernoulli, Gaussian, and linear bandit problems, we demonstrate state-of-the-art simulation performance.

1 Introduction

The paper introduces information-directed sampling (IDS) for online optimization with partial feedback, balancing regret against information gained about the optimal action. It provides general regret guarantees, broad applicability, and strong empirical performance.

  • Approach: IDS selects actions by minimizing squared expected single-period regret relative to mutual information about the optimal action.The information measure is the mutual information between the true optimal action and the next observation.
  • Theory: The expected regret bound applies across a very general model class and scales with the entropy of the optimal action distribution.Specialized bounds are order optimal up to a poly-logarithmic factor for several problem classes.
  • Analytic examples: IDS can dramatically outperform UCB, Thompson sampling, and knowledge-gradient algorithms in simple analytic examples.The examples illustrate information types that alternative approaches do not adequately address.
  • Simulations: In Bernoulli, Gaussian, and linear bandit simulations, IDS outperforms UCB algorithms and Thompson sampling.The comparison is notable because these baselines are known to be effective in those settings.
  • Computation: Computing IDS can be demanding when the action set is enormous or mutual information is difficult to evaluate.The paper develops numerical methods and efficient approximations for particular problem classes.
  • Scope: IDS applies to a broad class of information structures, including observations that inform rewards of arbitrary action subsets or reward-relevant factors.The formulation encompasses bandit feedback and more general settings.

2 Literature review

The literature includes UCB, Thompson sampling, knowledge gradient, Bayesian experimental design, and partial-monitoring approaches for learning under structured or limited feedback. The paper distinguishes IDS by combining information about the optimal action with cumulative-reward optimization across more general settings.

  • Dependent-arm bandits: UCB and Thompson sampling extend classical bandit methods to dependent-arm models with linear, generalized linear, sparse, Gaussian-process, and related reward structures.Strong guarantees or empirical results exist for several of these problem classes.
  • Mutual-information methods: Prior mutual-information methods between the optimal action and next observation focused on expensive black-box optimization.Those methods addressed pure exploration rather than cumulative reward optimization and used Gaussian-process priors with continuous action spaces.
  • Novelty: IDS is formulated for a broader range of information structures than earlier optimal-action mutual-information methods.The paper’s formulation covers settings beyond Gaussian-process priors and continuous action spaces.
  • Knowledge gradient: Knowledge gradient chooses actions using the expected impact of an observation on the quality of a greedy posterior decision.Unlike IDS, its information measure is based on improving the greedy decision.
  • Time preference: The literature primarily targets convergence to an optimal action while limiting exploration costs, rather than settings where time preference is important.The paper notes that IDS could be extended to discounted problems but does not pursue that extension.
  • Theoretical connection: Regret bounds for IDS build on an information-theoretic analysis of Thompson sampling because IDS has a smaller information ratio than Thompson sampling.The paper uses this relationship to transfer information-ratio bounds into regret bounds.

3 Problem formulation

The paper models online optimization in a Bayesian setting where actions generate partial observations and uncertainty determines the optimal action. It defines regret and information gain using posterior quantities conditioned on observed history.

  • Bayesian model: The decision-maker sequentially selects actions from a finite set and observes the outcome associated with the selected action.Uncertainty is represented through random quantities in a general probabilistic formulation.
  • Optimal action: The optimal action A∗ maximizes expected reward under the uncertain system parameter.The reward function is fixed and known, while uncertainty about the parameter induces uncertainty about A∗.
  • Regret: Expected regret measures the cumulative reward difference between always selecting the optimal action and following the algorithm’s action sequence.The expectation includes randomness in actions, outcomes, and the prior over the unknown parameter.
  • Policy: Actions are sampled from a history-dependent distribution determined by the observations collected before the current period.The history includes previously selected actions and their observed outcomes.
  • Information gain: The information gain from action a is the mutual information between the optimal action and that action’s next observation.This equals the expected reduction in posterior entropy of the optimal action.
  • Action distributions: For an action distribution, expected information gain and expected instantaneous regret are posterior-weighted averages over actions.The paper denotes these quantities by g_t(π) and Δ_t(π).

4 Algorithm design principles

IDS is a general design principle that selects actions by valuing decision-relevant information, including indirect and cumulative feedback. Analytic examples show that this focus can outperform UCB, Thompson sampling, knowledge gradient, and parameter-directed information strategies.

  • IDS selects actions to obtain indirect feedback about other actions, even when the selected action itself provides no useful feedback.This capability distinguishes IDS from approaches that value only immediate improvement or information about the selected action.
  • IDS values information that may not immediately improve expected reward but can become useful when combined with later observations.This enables information to accumulate across decisions rather than requiring each observation to improve the next-period objective.
  • IDS avoids acquiring information irrelevant to identifying the optimal action, unlike approaches that seek broad knowledge of the underlying parameter.In the assortment example, parameter-directed IDS experiments unnecessarily, whereas IDS recognizes that the optimal assortment does not depend on full parameter knowledge.
  • IDS is a design principle rather than an algorithm, and implementing it can be computationally demanding when action spaces are enormous or mutual information is difficult to evaluate.Numerical methods may therefore produce efficient approximations rather than exact or near-exact solutions.
  • IDS can identify an optimal action after only log2(d) steps, whereas knowledge gradient may require samples and regret that scale linearly with dimension d.The binary-search example explains this gap: each step rules out half the parameter vectors while minimizing period regret.
  • IDS can learn a customer’s type m times faster than single-type assortments by offering diverse assortments.The diverse assortment reveals information about multiple product types simultaneously, while UCB and Thompson sampling require order n samples.

5 Regret bounds

The paper bounds IDS regret through an information ratio linked to the entropy of the optimal action distribution, with tighter guarantees under informative action structures. These bounds specialize to full-information, linear-bandit, and semi-bandit settings.

  • General information-ratio bounds: The information ratio Ψt(π) is squared expected regret per bit of information acquired about the optimal action.The general regret analysis combines information-ratio bounds with the entropy H(α1) of the optimal action distribution.
  • General information-ratio bounds: IDS balances exploration and exploitation by ensuring that large expected regret is associated with acquiring substantial information about the optimal action.Its information-ratio bounds reflect how sampling actions enables inference about other actions.
  • Specialized settings: |A|/2 bounds the information ratio in the general finite-action case, while d/2 bounds it for linear bandits.These bounds yield regret guarantees through the general corollary and reflect the role of action count or feature dimension.
  • Specialized settings: The regret bounds improve on worst-case log(|A|)-dependent bounds when the prior distribution over the optimal action is informative and H(α1) is smaller.The paper states analogous improvements for linear bandits relative to worst-case log(|A|)d-dependent bounds.
  • Specialized settings: Semi-bandit feedback yields an information-ratio bound of d/(2m^2) because selecting an action reveals the parameter components for its chosen projects.This improves on the naive d/2 bound obtained by applying the linear-bandit result directly.

6 Computational methods

The computational methods generate IDS actions from posterior information, using exact or approximate calculations of expected regret and information gain. Because these calculations can require difficult integrations, the paper develops pairwise, discretized, and sample-based approximations.

  • Posterior-based action generation: IDS computes an action distribution from posterior information, focusing on action generation while assuming the posterior can be computed and stored efficiently.The paper notes that approximate Bayesian inference and posterior sampling can extend this setup.
  • Computational limitations: No general efficient procedure computes expected regret and information gain for arbitrary posteriors because the required integrals may be high-dimensional.Problem-specific numerical integration and approximation methods are therefore necessary for practical implementations.
  • Finite-model evaluation: For finite models, Algorithm 1 computes each action’s expected regret and information gain from optimal-action probabilities and joint observation distributions.It uses posterior model probabilities, predictive observation distributions, and their joint distribution with the optimal action.
  • Beta-Bernoulli evaluation: In beta-Bernoulli bandits, conjugacy keeps each posterior beta-distributed, while information gain is evaluated through an expected Kullback-Leibler divergence.The divergence compares posterior predictive distributions conditioned on the optimal action with the posterior predictive distribution.
  • Beta-Bernoulli evaluation: Discretizing [0,1] at n grid points produces near-exact beta-Bernoulli approximations with computation scaling as K^2n.Memoization reduces repeated computation, but the paper identifies one algorithmic line as the bottleneck.
  • Choosing the sampling distribution: The IDS single-period optimization is convex and has an optimal solution supported on at most two actions.The implementation searches action pairs and solves a one-dimensional convex optimization over their mixing probability.
  • Approximate computation: Sample-based algorithms estimate IDS quantities from representative posterior samples without relying on special posterior structure, including when posterior sampling is available through MCMC.The paper presents this as a route toward complex models whose posteriors cannot be efficiently computed or stored.

7 Computational results

Computational experiments compare IDS with UCB, Thompson sampling, KG, and related methods across Bernoulli, Gaussian, and linear settings. IDS performs strongly across these settings, while results also expose trade-offs involving horizon knowledge, exploration, and computation.

  • Bernoulli bandit: In the Bernoulli experiment, IDS achieved the lowest average regret, 18.0, across 1000 trials with 10 arms and horizon 1000.UCB1 had average regret 130.7 and was omitted from Figure 1a because it was dramatically worse than IDS.
  • Bernoulli bandit: KG failed to explore sufficiently in the Bernoulli setting, causing regret that grows linearly with time despite highly variable realized outcomes.KG’s low regret in some trials reflected frequent selection of the best arm, while poor exploration produced much worse outcomes in others.
  • Independent Gaussian bandit: In the Gaussian setting, KG performed competitively with IDS, while KG* explored more aggressively and performed very well.KG’s median regret was lowest, but its regret exceeded 283 in 100 of 2000 trials, suggesting insufficient exploration in those trials.
  • Independent Gaussian bandit: IDS remained competitive with KG over short horizons even though IDS does not take the time horizon as input.KG explicitly uses the horizon and explores less aggressively as fewer periods remain.
  • Linear bandit: In the linear experiments, IDS significantly outperformed GP-UCB and Thompson sampling, while tuned GP-UCB and Bayes UCB were competitive with IDS.The comparison included algorithms with strong regret guarantees and heuristic variants tuned for empirical performance.
  • Runtime comparison: IDS required substantially more computation than Thompson sampling and UCB, although decisions often took only a small fraction of a second.The paper notes that parallel processing or optimized implementations could accelerate IDS, while KG’s computational cost varied substantially by model.

8 Conclusion

The paper introduces information-directed sampling for online optimization with partial feedback, establishes general regret guarantees, and reports superior simulation performance in several bandit settings. It also identifies computational and statistical questions that remain open.

  • Information-directed sampling is proposed for online optimization problems in which decisions must be learned from partial feedback.
  • The paper establishes a general regret bound and specializes it to several widely studied problem classes.
  • IDS sometimes greatly outperforms popular approaches that do not carefully measure the information provided by sampling actions.
  • Simulation performance surpasses popular approaches for some simple and widely studied multi-armed bandit problems.
  • IDS can be computationally demanding when the action set is enormous or mutual information is difficult to evaluate.
  • Open statistical questions include whether IDS attains the Lai–Robbins lower bound and when information ratio is the right measure of information complexity.

9 Extensions

The extensions develop variants of information-directed sampling for pure exploration and for information about the unknown parameter rather than the optimal action. They also introduce a tuning parameter that changes the exploration–exploitation balance and discuss corresponding guarantees and trade-offs.

  • 9 Extensions: Pure-exploration extensions seek information about the optimal action while minimizing terminal rather than cumulative regret.
  • 9 Extensions: A pure-exploration policy that acquires as much information about A∗ as possible is given a theoretical guarantee.
  • 9.2 Using information gain about θ: The parameter-focused variant replaces information gain about A∗ with mutual information between the next observation and the unknown parameter θ.
  • 9.2 Using information gain about θ: Parameter-focused information can be irrelevant to the decision problem, although the resulting algorithm may be computationally simple and statistically efficient in some cases.
  • 9 Extensions: The information ratio is bounded by λ when the policy satisfies the stated feasibility and almost-sure conditions.
  • 9 Extensions: A tuning parameter λ produces a version of IDS that strikes different exploration–exploitation balances and has regret bounds when λ is sufficiently large.

A Proof of Proposition 6

The proof shows that an optimal sampling distribution can be replaced by one supported on at most two actions without changing instantaneous expected regret or expected information gain. The argument uses convexity and a minimizer of an auxiliary objective.

  • A Proof of Proposition 6: The objective Ψ is convex because x^2/y is convex for y > 0 and the mapping from sampling distributions to regret and information gain is affine.
  • A Proof of Proposition 6: The proof considers a minimizer of an auxiliary function and examines its partial derivatives.
  • A Proof of Proposition 6: Ordering actions by information gain allows a mixture of two actions to match the minimizer’s expected regret and expected information gain.
  • A Proof of Proposition 6: Therefore, some optimal sampling distribution has support over at most two actions.

B Proof of Proposition 1

The proof bounds cumulative information gain using the entropy of the optimal action and then relates regret to the information ratio. This yields the proposition’s average expected information-ratio guarantee.

  • B Proof of Proposition 1: Mutual information between A∗ and the next observation equals the expected reduction in A∗’s entropy.
  • B Proof of Proposition 1: Proposition 1 provides a bound involving the average expected information ratio under any policy.
  • B Proof of Proposition 1: The proof first bounds expected cumulative information gain by entropy using the tower property and non-negativity of entropy.
  • B Proof of Proposition 1: The remaining inequality follows from Hölder’s inequality.

C Proof of Proposition 7

The proof establishes bounds on the variance-based IDS information ratio, obtaining a general |A|/2 bound and a tighter d/2 bound under linear reward structure. The linear case uses a matrix rank argument together with conditional mean-reward identities.

  • Linear bound: Ψt(πt) ≤ d/2 when actions and parameters lie in Rd and expected rewards satisfy E[Rt,a|θ] = aT θ.This is the proposition’s tighter bound under the stated linearity assumption.
  • Proof technique: The analysis adapts techniques from Russo and Van Roy to variance-based IDS and supplies a full proof for their applicability here.The proof also uses a matrix analogue of Cauchy-Schwarz involving nuclear, Frobenius, and trace norms.
  • General bound: Ψt(πt) ≤ |A|/2 holds generally for the variance-based IDS distribution.The proof invokes a Cauchy-Schwarz argument to derive this bound.
  • Linear bound: The linear-case proof represents the relevant matrix as a product of K by d and d by K matrices, so its rank is at most d.Conditional expected rewards are expressed through differences between conditional and unconditional parameter means.
Loading 1403.5556v7…