mlsanityData to 7 Oct 2026

Asymptotically Optimal Information-Directed Sampling

arXiv 2011.05944 ↗First posted 11 Nov 2020stat.ML cs.LGcited by 33

Not on the map. Why?

Abstract (arXiv)

We introduce a simple and efficient algorithm for stochastic linear bandits with finitely many actions that is asymptotically optimal and (nearly) worst-case optimal in finite time. The approach is based on the frequentist information-directed sampling (IDS) framework, with a surrogate for the information gain that is informed by the optimization problem that defines the asymptotic lower bound. Our analysis sheds light on how IDS balances the trade-off between regret and information and uncovers a surprising connection between the recently proposed primal-dual methods and the IDS algorithm. We demonstrate empirically that IDS is competitive with UCB in finite-time, and can be significantly better in the asymptotic regime.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 11; 2023: 3; 2024: 5; 2025: 6; 2026: 1.

33 papers.

Sort:

By area:

  1. 2021Reinforcement Learning, Bit by Bitcited by 59
  2. 2022On the Complexity of Adversarial Decision Makingcited by 32
  3. 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
  4. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  5. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  6. 2022Contextual Information-Directed Samplingcited by 16
  7. 2021The Value of Information When Deciding What to Learncited by 15
  8. 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 13
  9. 2021Bias-Robust Bayesian Optimization via Dueling Banditscited by 11
  10. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 11
  11. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
  12. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
21 more
  1. 2024Optimistic Information Directed Samplingcited by 7
  2. 2024Optimal Batched Linear Banditscited by 7
  3. 2022Multi-Armed Bandits with Self-Information Rewardscited by 5
  4. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  5. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
  6. 2022The price of unfairness in linear bandits with biased feedbackcited by 3
  7. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  8. 2021Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classificationcited by 2
  9. 2022On the Complexity of Representation Learning in Contextual Linear Banditscited by 2
  10. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  11. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  12. 2024Indexed Minimum Empirical Divergence-Based Algorithms for Linear Banditscited by 2
  13. 2025Optimal and Practical Batched Linear Bandit Algorithmcited by 2
  14. 2022Non-Stationary Dynamic Pricing Via Actor-Critic Information-Directed Pricingcited by 1
  15. 2022Risk-aware linear bandits with convex losscited by 1
  16. 2025Sparse Optimistic Information Directed Samplingcited by 1
  17. 2026Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updatescited by 1
  18. 2022Occupancy Information Ratio: Infinite-Horizon, Information-Directed, Parameterized Policy Searchcited by 0
  19. 2022Truncated LinUCB for Stochastic Linear Banditscited by 0
  20. 2025Empirical Bound Information-Directed Sampling for Norm-Agnostic Banditscited by 0
  21. 2025Information-directed sampling for bandits: a primercited by 0