mlsanityData to 7 Oct 2026

Information Directed Sampling and Bandits with Heteroscedastic Noise

arXiv 1801.09667 ↗First posted 29 Jan 2018stat.MLcited by 75

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 75 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Jan 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 17; 2023: 13; 2024: 16; 2025: 11; 2026: 8.

75 papers.

Sort:

By area:

  1. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 57
  2. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  3. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  4. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  5. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  6. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  7. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  8. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
  9. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  10. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  11. 2023Efficient Exploration in Continuous-time Model-based Reinforcement Learningcited by 21
  12. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
38 more
  1. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  2. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  3. 2021Risk-averse Heteroscedastic Bayesian Optimizationcited by 17
  4. 2021Bayesian Optimization for Cascade-type Multi-stage Processescited by 17
  5. 2022Contextual Information-Directed Samplingcited by 16
  6. 2021Metalearning Linear Bandits by Prior Updatecited by 15
  7. 2022Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computationcited by 14
  8. 2022Bregman Deviations of Generic Exponential Familiescited by 13
  9. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  10. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
  11. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  12. 2022Variance-Aware Sparse Linear Banditscited by 11
  13. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
  14. 2024When to Sense and Control? A Time-adaptive Approach for Continuous-Time RLcited by 9
  15. 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
  16. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  17. 2024Linear bandits with polylogarithmic minimax regretcited by 8
  18. 2022Movement Penalized Bayesian Optimization with Application to Wind Energy Systemscited by 7
  19. 2023Batch Bayesian Optimization for Replicable Experimental Designcited by 7
  20. 2023OVD-Explorer: Optimism Should Not Be the Sole Pursuit of Exploration in Noisy Environmentscited by 7
  21. 2024Transition Constrained Bayesian Optimization via Markov Decision Processescited by 7
  22. 2024Optimistic Information Directed Samplingcited by 7
  23. 2024Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimizationcited by 6
  24. 2021A Bit Better? Quantifying Information for Bandit Learningcited by 5
  25. 2022Bayesian Optimization for Distributionally Robust Chance-constrained Problemcited by 5
  26. 2022Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Banditscited by 5
  27. 2022Multi-Armed Bandits with Self-Information Rewardscited by 5
  28. 2023Bounding Box-based Multi-objective Bayesian Optimization of Risk Measures under Input Uncertaintycited by 5
  29. 2024Model-Free Active Exploration in Reinforcement Learningcited by 5
  30. 2023Provably Efficient Reinforcement Learning via Surprise Boundcited by 4
  31. 2024TS-RSR: A provably efficient approach for batch Bayesian Optimizationcited by 4
  32. 2025Variance-Dependent Regret Lower Bounds for Contextual Banditscited by 4
  33. 2025Vector-valued self-normalized concentration inequalities beyond sub-Gaussianitycited by 4
  34. 2023SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Banditscited by 3
  35. 2023Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Banditscited by 3
  36. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  37. 2025Wasserstein Distributionally Robust Bayesian Optimization with Continuous Contextcited by 3
  38. 2021Generalised correlated batched bandits via the ARC algorithm with application to dynamic pricingcited by 2

50 most cited of 75 All 75 (JSON)