Research map / Bandits and online learning / Multi-armed bandits
On Bits and Bandits: Quantifying the Regret-Information Trade-off
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an information-theoretic (Fano-based) method for Bayesian regret lower bounds in contextual interactive decision-making, derives bounds linking accumulated mutual information (bits) to regret, and applies a bits-based LLM routing policy to MMLU question answering.
Problem
Quantifying the exact trade-off between information an agent accumulates (in bits, from interaction or external sources) and the regret it suffers in sequential decision-making.
Approach
Uses Fano's inequality with local packing constructions to lower bound worst-case Bayesian regret, and bounds mutual information between the best decision/ history to yield regret lower bounds as a function of information bits R (and entropy of the prior), plus Thompson sampling upper bounds in terms of bits; applies a bits-based policy to choose between small and large LLMs.
Key results
- Bits-based LLM selection yields lower mean regret than random selection at every deployment level, e.g., 36 ± 1 vs 38.7 ± 0.3 at 50% large-LLM deployment with Mistral-7B as small LLM over 200 steps.
- With Gemma-2B as the small LLM, bits-based policy achieves 26 ± 1 vs 27 ± 1 random at 90% deployment.
- Theory: Bayesian regret lower bound Omega(sqrt(KT log K / R)) for R bits of accumulated information, recovering known Omega(sqrt(KT)) MAB bound when R is of order log K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the small LLM's information score to select when to query the large LLM instead of selecting randomly | Mistral-7B / Mixtral-8x7B · MMLU, 50% large-LLM deployment | mean regret: 38.7 ± 0.3 -> 36 ± 1 | Helped |
| Use the small LLM's information score to select when to query the large LLM instead of selecting randomly | Mistral-7B / Mixtral-8x7B · MMLU, 70% large-LLM deployment | mean regret: 30.5 ± 0.4 -> 26.6 ± 0.8 | Helped |
| Use the small LLM's information score to select when to query the large LLM instead of selecting randomly | Mistral-7B / Mixtral-8x7B · MMLU, 90% large-LLM deployment | mean regret: 22.4 ± 0.5 -> 21.8 ± 0.4 | Helped |
| Use the small LLM's information score to select when to query the large LLM instead of selecting randomly | Gemma-2B / Mixtral-8x7B · MMLU, 50% large-LLM deployment | mean regret: 44.5 ± 0.7 -> 38 ± 2 | Helped |
| Use the small LLM's information score to select when to query the large LLM instead of selecting randomly | Gemma-2B / Mixtral-8x7B · MMLU, 70% large-LLM deployment | mean regret: 35.6 ± 0.8 -> 32 ± 1 | Helped |
| Use the small LLM's information score to select when to query the large LLM instead of selecting randomly | Gemma-2B / Mixtral-8x7B · MMLU, 90% large-LLM deployment | mean regret: 27 ± 1 -> 26 ± 1 | Helped |
Surprising findings
- The bits-based policy's advantage over random selection grows as the allowed number of large-LLM deployments increases, and the gap is small at 90% deployment (e.g., 21.8 vs 22.4).
Limitations
- Bounds for regret lower and upper bounds differ by a factor of sqrt(log K).
- Analysis is limited to the Bayesian setting; the information measure relies on it.
- Assumes exogenous information can be gathered regardless of process history.
Experimental setup
Datasets: MMLU
Benchmarks: MMLU
Metrics: mean accumulated regret
Baselines: Random LLM selection Small LLM only Large LLM only EXP3 APS Thompson sampling
Builds on: Fano's inequality Thompson sampling information-directed sampling interactive decision-making framework (Foster et al.)
Closest papers by meaning
- Bits Beat Tokens: A Regret Rate Distortion Theory for Large Language Model Agents (NeurIPS 2026 · similarity 0.89)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring (NeurIPS 2025 · similarity 0.87)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.87)
- Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds (ICML 2025 · similarity 0.86)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.