mlsanityData to 14 Oct 2026

Optimistic Information Directed Sampling

arXiv 2402.15411 ↗First posted 23 Feb 2024cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

We study the problem of online learning in contextual bandit problems where the loss function is assumed to belong to a known parametric function class. We propose a new analytic framework for this setting that bridges the Bayesian theory of information-directed sampling due to Russo and Van Roy (2018) and the worst-case theory of Foster, Kakade, Qian, and Rakhlin (2021) based on the decision-estimation coefficient. Drawing from both lines of work, we propose a algorithmic template called Optimistic Information-Directed Sampling and show that it can achieve instance-dependent regret guarantees similar to the ones achievable by the classic Bayesian IDS method, but with the major advantage of not requiring any Bayesian assumptions. The key technical innovation of our analysis is introducing an optimistic surrogate model for the regret and using it to define a frequentist version of the Information Ratio of Russo and Van Roy (2018), and a less conservative version of the Decision Estimation Coefficient of Foster et al. (2021). Keywords: Contextual bandits, information-directed sampling, decision estimation coefficient, first-order regret bounds.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 27 of its 43 references that are in the map. First posted on arXiv 23 Feb 2024.

Builds on

27 of 43 references.

References · 27

  1. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  2. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  3. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  4. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  5. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  6. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  7. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  8. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  9. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  10. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  11. 2020Information Directed Sampling for Linear Partial Monitoringcited by 40
  12. 2020Mirror Descent and the Information Ratiocited by 40
15 more
  1. 2020Asymptotically Optimal Information-Directed Samplingcited by 33
  2. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  3. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
  4. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  5. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  6. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  7. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 18
  8. 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
  9. 2019First-Order Bayesian Regret Analysis of Thompson Samplingcited by 17
  10. 2022Contextual Information-Directed Samplingcited by 16
  11. 2019Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Casecited by 11
  12. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  13. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  14. 2019Safe-Bayesian Generalized Linear Regressioncited by 9
  15. 2017Efficient Online Bandit Multiclass Learning with tildeO(√T) Regretcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 3.

7 papers.

  1. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2
  2. 2024An Information-Theoretic Analysis of Thompson Sampling for Logistic Banditscited by 1
  3. 2025Sparse Optimistic Information Directed Samplingcited by 1
  4. 2026Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximationcited by 1
  5. 2025Sparse Nonparametric Contextual Banditscited by 0
  6. 2025Information-directed sampling for bandits: a primercited by 0
  7. 2026C-IDS: Solving Contextual POMDP via Information-Directed Objectivecited by 0