Research map / Bandits and online learning / Multi-armed bandits
Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits
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.
Characterizes optimal success probability and mutual information over time for a multi-armed bandit with a unique best arm (fixed margin), revealing linear-quadratic-linear-saturating information growth and showing that optimal learning and information can decouple.
Problem
How optimal success probability and mutual information about the best arm evolve over small time horizons (below the n/Δ² sample complexity) in interactive multi-armed bandit learning, and how they compare to non-interactive learning.
Approach
Uses a sequential probability ratio test (biased random walk elimination) to achieve optimal success probability and mutual information, and proves converses via a boosting-based reduction from large t to small t and a change-of-divergence argument for mutual information, showing Fano's inequality is loose in intermediate regimes.
Key results
- Optimal success probability is Θ((1+tΔ²)/n) for t ≤ n/Δ², and mutual information grows linearly, then quadratically (for 1<tΔ²≤log n), then linearly with a log n factor (log n<tΔ²≤n), saturating at log n.
- Non-interactive optimal success probability scales as tΔ²/(n log(1+tΔ²)), strictly smaller than the interactive one in the intermediate regime.
- An algorithm achieving optimal success probability can accumulate strictly less mutual information than the optimum when tΔ² ∈ ω(1)∩n^{o(1)}, so Fano's inequality is loose there.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use interactive rather than non-interactive sampling | MAB best-arm identification · MAB, 1 < tΔ² ≤ n | success probability: p_t^\star \asymp \frac{t \Delta^2}{n}; \optspnonint \asymp \frac{t\Delta^2}{n\log(1+t\Delta^2)} | Helped |
| Use interactive rather than non-interactive sampling | MAB information accumulation · MAB, log n < tΔ² ≤ n | mutual information: I_t^\star \asymp \frac{t \Delta^2 \log n} n; \optminonint \asymp \frac{t\Delta^2}{n} | Helped |
| Interactively adapt arm selection based on preliminary estimates | MAB information accumulation · MAB, 1 < tΔ² ≤ log n | mutual information: I_t^\star \asymp \frac{(t \Delta^2)^2}{n} | Helped |
| Use a non-interactive strategy in the early regime | MAB information accumulation · MAB, tΔ² ≤ 1 | mutual information: I_t^\star \asymp \frac{t \Delta^2} n; \optminonint \asymp \frac{t\Delta^2}{n} | No clear effect |
| Allow a random stopping time with expected duration at most t | MAB information accumulation · MAB, t ≤ n/Δ² | mutual information: \optmiexp \gtrsim \frac{t\Delta^2\log n}{n} | Helped |
| Add an upper threshold θ_r > 0 for the random walks to stop pulling the best arm early (ablation) | Sequential probability ratio test · MAB, tΔ² ∈ ω(1) ∩ n^{o(1)} | mutual information: O\pth{\frac{t\Delta^2\log(t\Delta^2)}{n}}=o(I_t^\star) | Hurt |
Surprising findings
- Optimal success probability and mutual information can decouple: an optimal-learning algorithm may accumulate strictly suboptimal information, so mutual information alone may not characterize learning limits.
- Standard two-point/TV-based bounds and the two-phase clean-answer reduction fail to give tight converses for intermediate t.
Limitations
- Analysis is restricted to a specific toy instance (uniform prior, fixed margin Bernoulli rewards), not general bandits.
- Algorithms are designed for theoretical analysis rather than practical use, as the paper states.
- Some results are stated up to constants and assume Δ = 1-Ω(1) in parts of the converse.
Experimental setup
Metrics: optimal success probability mutual information
Baselines: non-interactive algorithm median elimination two-phase clean-answer model
Builds on: Fano's inequality DEC (decision-estimation coefficient) median elimination information-directed sampling
Closest papers by meaning
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.88)
- The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability (ICML 2025 · similarity 0.87)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.87)
- Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting (NeurIPS 2024 · similarity 0.86)
- Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation (ICLR 2024 · similarity 0.86)
- Evolutionary Prediction Games (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.