Research map / Bandits and online learning / Online convex optimization and games
Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
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 the interactive Fano method, a unifying algorithm-dependent lower bound framework recovering Le Cam, Assouad, Fano and DEC lower bounds, and introduces the fractional covering number to characterize learnability of structured bandits up to an exponential gap.
Problem
Classical lower bound techniques (Le Cam, Fano, Assouad) do not give tight minimax lower bounds for interactive decision making, and DEC-based lower bounds omit the estimation complexity, leaving a gap with upper bounds.
Approach
An algorithm-dependent interactive Fano method that replaces the hard separation condition with a soft quantile probability under a reference ("ghost data") distribution and f-divergences, which recovers Le Cam, Assouad, Fano and DEC bounds; a fractional covering number then captures estimation complexity for lower and upper bounds.
Key results
- Fractional covering number gives lower bound T >= (est(2Delta)-2)/(2C_KL) and upper bound regret T*Delta + O(log(T/delta)) sqrt(T*V(M)), characterizing structured bandit learnability up to an exponential gap.
- Recovers the linear bandit Omega(d/sqrt(T)) PAC lower bound via mutual information, showing an extra sqrt(d) factor beyond the DEC bound sqrt(d/T).
- Quantile DEC lower bound recovers the constrained PAC-DEC lower bound up to additive error 8*epsilon.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the interactive Fano method to interactive decision making | Interactive decision making lower bounds · Interactive decision making | lower-bound coverage | Helped |
| Use fractional covering number alongside DEC | Structured bandit learnability · Structured bandit problems | finite-time learnability characterization | Helped |
| Use the interactive mutual-information lower bound instead of relying on the standard DEC lower bound | d-dimensional linear bandits · d-dimensional linear bandit | minimax PAC risk lower bound: DEC lower bounds ... scale as \sqrt{d/T}; our bound is \Omega(\min\set{d/\sqrt{T},1}) | Helped |
| Combine fractional covering number with DEC | Interactive decision making with convex model classes · Convex model classes | upper/lower bound gap: up to a quadratic factor | Helped |
| Use the fractional covering number upper bound | Reward maximization in DMSO · Reward maximization, DMSO | sample complexity characterization: lower bound is logarithmic in \DV{\mathcal{M}}; the upper bound will be polynomial | Mixed |
Surprising findings
- The DEC lower bound for linear bandits scales only as sqrt(d/T), missing a factor sqrt(d) that comes from estimation complexity.
Limitations
- Upper and lower bounds on learnability for structured bandits differ by an exponential gap in quantitative rates.
- Closing the gap to upper bounds for general interactive decision making is only up to polynomial factors and requires convex model classes.
- Fractional covering number upper bound is polynomial while lower bound is logarithmic in the covering quantity.
Experimental setup
Metrics: minimax risk lower bound minimax regret sample complexity
Baselines: constrained DEC lower bound Le Cam convex hull method mutual information-based Fano bounds
Builds on: Decision-Estimation Coefficient Fano's method Le Cam's two-point method Assouad's lemma Yang-Barron method
Closest papers by meaning
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.88)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.88)
- On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice (NeurIPS 2024 · similarity 0.88)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.88)
- p-Mean Regret for Stochastic Bandits (AAAI 2025 · similarity 0.87)
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.