PaperlayerView exact revision on arXiv

Source-linked AI summary

Information Directed Sampling and Bandits with Heteroscedastic Noise

Johannes Kirschner, Andreas Krause

arXiv:1801.09667v2stat.ML

TL;DR

Bandit methods often assume observation noise is uniform across evaluation points, although the noise can depend on the chosen point. The paper develops a frequentist information-directed framework for heteroscedastic bandits and reports advantages over UCB and Thompson Sampling in that setting. Its regret bounds recover known UCB bounds in the homoscedastic case and can be much better with heteroscedastic noise.

  • Problem

    Standard bandit analyses commonly assume a noise bound that is known and independent of the evaluation point, despite applications where noise varies across points.

    Source: §1 · pp. 1–2

  • Method

    The paper develops a frequentist regret framework and IDS approach that balances regret against the information gained from an action.

    Source: §1 · p. 2, §8 · p. 12

  • Results

    With heteroscedastic noise, IDS-UCB and IDS-TS show an advantage over UCB and Thompson Sampling.

    Source: §7 · p. 11

  • Takeaways & Limitations

    The regret-information framework is presented as a design principle that may extend to settings beyond the algorithms studied.

    Source: §8 · p. 12

    The analysis assumes the heteroscedastic noise bound is known.

    Source: §8 · p. 12

Abstract

from arXiv · show

In the stochastic bandit problem, the goal is to maximize an unknown function via a sequence of noisy evaluations. Typically, the observation noise is assumed to be independent of the evaluation point and to satisfy a tail bound uniformly on the domain; a restrictive assumption for many applications. In this work, we consider bandits with heteroscedastic noise, where we explicitly allow the noise distribution to depend on the evaluation point. We show that this leads to new trade-offs for information and regret, which are not taken into account by existing approaches like upper confidence bound algorithms (UCB) or Thompson Sampling. To address these shortcomings, we introduce a frequentist regret analysis framework, that is similar to the Bayesian framework of Russo and Van Roy (2014), and we prove a new high-probability regret bound for general, possibly randomized policies, which depends on a quantity we refer to as regret-information ratio. From this bound, we define a frequentist version of Information Directed Sampling (IDS) to minimize the regret-information ratio over all possible action sampling distributions. This further relies on concentration inequalities for online least squares regression in separable Hilbert spaces, which we generalize to the case of heteroscedastic noise. We then formulate several variants of IDS for linear and reproducing kernel Hilbert space response functions, yielding novel algorithms for Bayesian optimization. We also prove frequentist regret bounds, which in the homoscedastic case recover known bounds for UCB, but can be much better when the noise is heteroscedastic. Empirically, we demonstrate in a linear setting with heteroscedastic noise, that some of our methods can outperform UCB and Thompson Sampling, while staying competitive when the noise is homoscedastic.

1. Introduction

The paper studies bandits where observation noise varies with the evaluation point, a setting that challenges methods built around uniform noise bounds. It develops a frequentist information–regret framework and IDS variants, with theoretical and empirical contributions for heteroscedastic bandits.

1. Introduction

  • Because noise can depend on the evaluation point, the method must balance information gathering with reward and account for noise in both estimation and exploration.The introduction cites reinforcement-learning roll-outs and physical-system hyperparameter tuning as settings where noise can vary with the explored region or chosen parameters.Source: §1 · pp. 1–2

1.1. Related Work

  • The paper identifies a gap in prior approaches: UCB and Thompson Sampling may fail to resolve even simple heteroscedastic examples, while Bayesian IDS lacks known frequentist regret guarantees.Prior work on heteroscedastic bandits includes Cowan et al. (2015) for finite independent Gaussian arms with unknown variances.Source: §1.1 · p. 2, §1.2 · p. 3

1.2. Contributions

  • The paper introduces a frequentist regret bound for randomized policies based on information gain and a regret-information ratio.The framework is presented as analogous to Russo and Van Roy (2014) and as a generalization of standard UCB analyses.Source: §1.2 · p. 3
  • Frequentist IDS minimizes a surrogate regret-information ratio over action-sampling distributions, and a deterministic variant is proposed as a cheaper alternative.The randomized framework also establishes properties of the ratio beyond finite action sets.Source: §1.2 · p. 3
  • The work extends online least-squares concentration bounds to heteroscedastic noise, supporting IDS variants and regret guarantees for the setting.The bounds recover known UCB bounds in the homoscedastic case and can be much better when noise is heteroscedastic.Source: §1.2 · p. 3
  • In linear heteroscedastic bandits, some proposed methods can outperform UCB and Thompson Sampling.The paper also reports regret bounds that recover known UCB bounds in the homoscedastic case and can be much better with heteroscedastic noise.Source: §1.2 · p. 3
  • The IDS framework is formulated more generally than heteroscedastic bandits and could support algorithms for other settings.Source: §1.2 · p. 3

2. Problem Statement

The problem is to maximize cumulative reward by choosing actions and observing noisy evaluations of an unknown function. The setup allows noise and information gain to depend on the action, motivating comparisons of low- and high-noise actions with equal rewards.

2. Problem Statement

  • A policy chooses actions from history-dependent distributions on a compact action set and observes the function value plus noise.The objective is to maximize cumulative reward.Source: §2 · p. 3
  • The noise is conditionally ρ(x)-subgaussian, with a positive continuous bound that may vary by action; the policy's knowledge of ρ is left open.The condition implies zero-mean noise, with Gaussian, Rademacher, and uniform examples.Source: §2 · p. 4
  • The setup defines action-specific information gain; one example is log(1 + σt(x)^2/ρ(x)^2), which corresponds to mutual information in the stated Bayesian setting.The paper relates its maximum-information-gain quantity γT to the notion of Srinivas et al. (2010).Source: §2 · p. 4
  • With equal rewards for each action's low- and high-noise versions, a uniform-noise regret guarantee degenerates as ρ2 grows, although the low-noise version is more efficient.The example duplicates actions while assigning their copies noise bounds ρ1 < ρ2.Source: §2 · p. 4
  • UCB's acquisition function and Thompson Sampling show no preference between the low- and high-noise versions of an action.Thompson Sampling selects an action by maximizing a function sampled from the posterior over parameters.Source: §2 · p. 4
  • In a linear bandit, adding d basis-vector actions with negligible noise can yield vanishing regret after d plays, yet UCB and Thompson Sampling fail to choose them.The basis vectors can be scaled so none is optimal.Source: §2 · p. 4

3. A Frequentist Regret Framework

The framework gives high-probability regret bounds for general policies using the regret-information ratio and total information gain. It extends the usual UCB-style analysis while accommodating randomized policies.

3. A Frequentist Regret Framework

  • Theorem 1 bounds regret with high probability for any policy using its regret-information ratios and total information gain.The bound holds at every time horizon; a separate result treats deterministic policies.Source: §3 · p. 5
  • For deterministic policies, the framework also gives a simpler regret bound because the chosen action is predictable.The randomized-policy analysis must additionally control martingale differences.Source: §3 · p. 5
  • A concentration inequality for bounded supermartingales controls cumulative conditional information gains without a log(T) factor in the leading term.The proof uses a predictable, non-negative process and a method-of-mixtures argument.Source: §3 · p. 6
  • The general randomized-policy bound retains a log(1/δ) factor that cannot be completely avoided.The result assumes a bound on sub-optimality gaps; the additional condition I_t(x_t) ≤ 1 is presented as a continuity assumption and is eventually satisfied for the later information functions.Source: §3 · pp. 5–6

4. Frequentist Information Directed Sampling

Frequentist IDS minimizes a surrogate for the regret-information ratio, built from confidence bounds on sub-optimality gaps. Its minimizing distribution can be supported on at most two actions, including for compact continuous action sets.

4. Frequentist Information Directed Sampling

  • IDS minimizes a surrogate regret-information ratio formed using confidence-based upper bounds on sub-optimality gaps.The confidence band must contain the true function values for the surrogate bound to hold.Source: §4 · p. 7
  • For compact action sets, a minimizing distribution exists, and the regret-information ratio surrogate is convex in the sampling distribution.A minimizer can be supported on at most two actions, even with continuous action sets.Source: §4 · p. 7
  • DIDS chooses a single action by minimizing the regret-information ratio over single-action distributions.The unrestricted IDS sampling distribution may require support on two actions.Source: §4 · p. 7
  • Empirically, which IDS version has lower regret depends strongly on the information function; DIDS may be cheaper to compute with similar or sometimes better performance.The authors leave understanding the potential benefits of randomized IDS for future work.Source: §4 · p. 7

5. Online Least Squares Estimation with Heteroscedastic Noise

The paper extends online least-squares concentration results to heteroscedastic noise in linear and separable Hilbert spaces. The resulting estimators account for noise levels and support confidence bounds for linear and RKHS response functions.

5. Online Least Squares Estimation with Heteroscedastic Noise

  • The section generalizes online least-squares concentration inequalities to heteroscedastic noise in both Rd and separable Hilbert spaces.The stated setup uses a diagonal noise matrix of observation-specific variances and a subgaussian noise condition.Source: §5 · p. 8, §5.1 · p. 8, §5.2 · p. 9

5.1. Linear Least Squares with Heteroscedastic Noise

  • Weighted linear least squares gives less weight to noisier observations, and the paper extends its confidence inequality to heteroscedastic noise.The linear estimator has confidence intervals that contain the true function value with probability at least 1 − δ.Source: §5.1 · p. 8

5.2. Least Squares Estimation in Separable Hilbert Spaces

  • In separable Hilbert spaces, the paper extends concentration bounds for regularized least squares; the RKHS case yields a tractable kernel estimator.The RKHS estimate and uncertainty can be updated iteratively using Schur’s complement, avoiding a T × T matrix inverse at each step.Source: §5.2 · p. 9

6. Regret Bounds for Information Directed Sampling on Heteroscedastic Bandits

The paper defines information gains for heteroscedastic bandits and uses them to construct IDS variants and regret bounds. The bounds recover known UCB bounds in the homoscedastic case and can be much better under heteroscedastic noise.

6. Regret Bounds for Information Directed Sampling on Heteroscedastic Bandits

  • The proposed information gain decreases as function uncertainty falls and also decreases when observation noise is larger.The passage states that compactness of the action set ensures I_t(x) ≤ 1.Source: §6 · p. 10
  • IDS-UCB collects information about the UCB action but may choose a more informative alternative, without costing more to compute than standard UCB.The policy is not restricted to playing the UCB action itself.Source: §6 · p. 10
  • The regret bounds recover known UCB bounds in the homoscedastic setting and can be much better with heteroscedastic noise.The paper summarizes worst-case bounds for IDS-F and IDS-UCB in Table 1.Source: §6 · p. 11, Table 1 · p. 11
  • The guarantees are worst-case; instance-dependent regret may differ, and adaptive bounds for more general heteroscedastic settings remain an undertaking.The discussion says such bounds would require relating the sum of information gains directly to the noise and policy.Source: §6 · p. 11

7. Experiments

In a synthetic linear-bandit experiment, the methods are competitive with UCB and Thompson Sampling under homoscedastic noise, while IDS-UCB and IDS-TS improve on their counterparts under heteroscedastic noise. The experiments also compare randomized and deterministic IDS variants across the two noise settings.

7. Experiments

  • The synthetic experiment fixes a linear function in R^3 and randomly generates 30 actions in the Euclidean unit ball for each trial.The homoscedastic setting uses Gaussian noise with constant bound ρ = 0.5; the heteroscedastic setting assigns action-specific bounds uniformly in [0.1, 1].Source: §7 · p. 11
  • Under heteroscedastic noise, IDS-UCB outperforms UCB/W-UCB and IDS-TS improves on TS/W-TS; under homoscedastic noise, IDS-UCB and UCB, and IDS-TS and TS, achieve almost the same regret.The authors attribute the heteroscedastic comparison to using the noise bound for both estimation and exploration.Source: §7 · p. 11, Figure 1 · p. 12
  • In the homoscedastic setting, DIDS-F performs similarly to IDS-UCB but explores more, and IDS- F's regret curve is close to O(√T log T).The experiment reports 2 standard errors over 500 trials; IDS-TS is defined using Thompson Sampling, but the authors do not yet have regret bounds for it.Source: §7 · p. 11, Figure 1 · p. 12

8. Conclusion and Future Work

The paper presents frequentist IDS for heteroscedastic bandits and identifies open questions about information-function choices, noise-bound knowledge, and the broader usefulness of regret-information ratio. It notes that IDS performance depends strongly on the chosen information function.

Conclusion and Future Work

  • The authors frame Information Directed Sampling as a design principle whose behavior depends on user-defined information and regret quantities.They report that IDS performance strongly depends on the information function; an optimum-based information function can be more expensive to compute and may require approximation.Source: §8 · p. 12
  • The heteroscedastic-noise analysis assumes that the noise bound ρ is known, while estimating noise variance directly from data is left as a possible alternative.The authors cite Cowan et al. (2015) for variance estimation in Gaussian multi-armed bandits.Source: §8 · p. 12
  • The authors leave open whether regret-information ratio is useful beyond the algorithms studied, including whether it can bound Thompson Sampling's frequentist regret.They note that frequentist regret bounds for Thompson Sampling remain harder to achieve than Bayesian bounds.Source: §8 · p. 12

Appendix A. Concentration Inequalities for Martingales

The appendix develops martingale and supermartingale concentration results, including an anytime supermartingale inequality. It also outlines a mixture-based proof and reports removal of two assumptions from an earlier lemma.

Appendix A. Concentration Inequalities for Martingales

  • A bounded-increment martingale lemma is included, and its related proof removes the earlier assumptions δ < 1/e and T ≥ 3.The lemma concerns a martingale difference sequence whose increments are bounded above by b.Source: Appendix A · p. 15
  • An anytime supermartingale concentration inequality is presented as a variant of Corollary 2.7 by Fan et al. (2015).The authors note that this inequality may be of independent interest.Source: Appendix A · p. 16
  • The proof combines Corollary 2.7 of Fan et al. (2015) with the method of mixtures used by Abbasi-Yadkori et al. (2011).Because the supermartingale is defined only for nonnegative λ, the mixing density is supported on [0, ∞).Source: Appendix A · pp. 16–17

Appendix B. Proof of Theorem 1

The proof develops the regret bound by controlling realized regret, relating expected regret to the regret-information ratio, and bounding cumulative information gain. Appendix C establishes properties of that ratio, including a two-action minimizer for compact action sets.

Appendix B. Proof of Theorem 1

  • The proof bounds regret through concentration, a Cauchy–Schwarz step using the regret-information ratio, and a bound on cumulative information gain.The argument handles general policies and uses a union bound to make the relevant events hold simultaneously.Source: Appendix B · pp. 19–20, Lemma 14 · p. 21

Appendix C. Properties of the Information Regret Ratio

  • The regret-information ratio is convex in the sampling distribution, and under the stated compactness and continuity conditions its minimum is attained by a distribution supported on at most two actions.The proof preserves the distribution’s expected regret and expected information quantity when replacing it with a two-action mixture.Source: Appendix C · pp. 22–24

D.1. Least Squares Estimator for RKHS

  • The RKHS least-squares derivation uses the reproducing property to express its kernel terms through the kernel matrix and regularized covariance matrix.The displayed expression includes k(x,y) − kT(x)⊤(KT + λΣT)−1kT(y).Source: §D.1 · pp. 24–25

Appendix E. Summary of Information Gain Functions

The appendix describes information-gain variants that use Thompson Sampling proposals and compares IDS variants in a heteroscedastic simulation. In that experiment, IDS-UCB and IDS-TS select the less noisy action in each pair, and IDS-TS has the lowest regret after 5000 steps.

Appendix E. Summary of Information Gain Functions

  • IDS-TS uses a Thompson Sampling proposal to identify an action for information gathering, but is not restricted to playing that proposed action.The proposal maximizes a sample from the posterior distribution of the reward function.Source: Appendix E · p. 25
  • IDS-E uses averaged information gain calculated from multiple Thompson Sampling proposals.The appendix specifies averaging over 10 proposals in the described experiment.Source: Appendix E · p. 25
  • After 5000 steps, IDS-TS achieves the lowest regret among the policies, while IDS-UCB clearly outperforms W-UCB.W-TS outperforms TS and is competitive with IDS-TS; the plotted curves overlap.Source: Appendix E · p. 26
  • In paired actions with different noise levels, IDS-UCB and IDS-TS are guaranteed to choose the less noisy action, while UCB and TS deteriorate when committed to the noisier action.Without the second, noisier action, UCB and IDS-UCB perform similarly, as do TS and IDS-TS.Source: Appendix E · p. 26

Appendix F. Further Numerical Experiments

The further experiments compare IDS variants and weighted estimators in a linear bandit setting. The reported results favor several variants empirically, while the appendix notes that some lack known frequentist regret bounds and that performance depends on the noise assignment.

Appendix F. Further Numerical Experiments

  • The experiments use randomly generated actions and, in the heteroscedastic case, noise bounds drawn uniformly from [0.4, 0.6].IDS-E averages over 10 Thompson Sampling proposals; the experiments also include FW-TS.Source: Appendix F · p. 26
  • TS, WTS, D/IDS-TS, and D/IDS-E perform well empirically, although no frequentist regret bounds are currently known for them.The IDS and DIDS versions differ little except for IDS-F and DIDS-F, where randomized IDS-F appears to over-explore.Source: Appendix F · p. 26
  • IDS-F achieves higher information gain than DIDS-F while maintaining the worst-case regret guarantee.The authors conjecture that randomized IDS may have lower regret than its deterministic version in some settings.Source: Appendix F · p. 27
  • The authors caution that noise assignments can change the apparent advantage of information-directed strategies and identify broader experiments, including real-world applications, as future work.Very low noise on a suboptimal action can degrade these strategies; very low noise on the optimal action can give them an additional advantage.Source: Appendix F · p. 27

Appendix G. Useful Inequalities

  • The appendix’s Bhatia–Davis variance bound is tight when all probability mass lies at the interval’s endpoints.Source: Appendix G · p. 27

Related papers

Loading 1801.09667v2…