On Bits and Bandits: Quantifying the Regret-Information Trade-off
Not on the map. Why?
Abstract (arXiv)
In many sequential decision problems, an agent performs a repeated task. He then suffers regret and obtains information that he may use in the following rounds. However, sometimes the agent may also obtain information and avoid suffering regret by querying external sources. We study the trade-off between the information an agent accumulates and the regret it suffers. We invoke information-theoretic methods for obtaining regret lower bounds, that also allow us to easily re-derive several known lower bounds. We introduce the first Bayesian regret lower bounds that depend on the information an agent accumulates. We also prove regret upper bounds using the amount of information the agent accumulates. These bounds show that information measured in bits, can be traded off for regret, measured in reward. Finally, we demonstrate the utility of these bounds in improving the performance of a question-answering task with large language models, allowing us to obtain valuable insights.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 34 of its 56 references that are in the map. First posted on arXiv 26 May 2024.
Builds on
34 of 56 references.
References · 34
- 2020Measuring Massive Multitask Language Understandingcited by 7,768
- 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
- 2020Aligning AI With Shared Human Valuescited by 706
- 2022The case for 4-bit precision: k-bit Inference Scaling Lawscited by 247
- 2021The Statistical Complexity of Interactive Decision Makingcited by 208
- 2023Guiding Pretraining in Reinforcement Learning with Large Language Modelscited by 185
- 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
- 2014Learning to Optimize via Information-Directed Samplingcited by 168
- 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
- 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
- 2018A Contextual Bandit Bake-offcited by 64
- 2013Bandits and Experts in Metric Spacescited by 63
22 more
- 2023Language Instructed Reinforcement Learning for Human-AI Coordinationcited by 61
- 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
- 2019Adaptive Exploration in Linear Contextual Banditcited by 43
- 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 42
- 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
- 2020Mirror Descent and the Information Ratiocited by 39
- 2018Satisficing in Time-Sensitive Bandit Learningcited by 38
- 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
- 2019An Introductory Guide to Fano's Inequality with Applications in Statistical Estimationcited by 30
- 2019Self-Paced Contextual Reinforcement Learningcited by 26
- 2013Prior-free and prior-dependent regret bounds for Thompson Samplingcited by 25
- 2017Information Directed Sampling for Stochastic Bandits with Graph Feedbackcited by 24
- 2020Reinforcement learning with human advice: a surveycited by 23
- 2021Deciding What to Learn: A Rate-Distortion Approachcited by 23
- 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
- 2021Information Directed Sampling for Sparse Linear Banditscited by 20
- 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
- 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
- 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
- 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
- 2021Combinatorial Multi-armed Bandits for Resource Allocationcited by 10
- 2024Optimal cross-learning for contextual bandits with unknown context distributionscited by 7
Built on by
Citing papers per year: 2026: 3.
3 papers.