Research map / Bandits and online learning / Multi-armed bandits
On Interpolating Experts and 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.
Studies an interpolation between expert advice and multi-armed bandits (m-MAB, arms partitioned into groups that reveal losses jointly), proving tight minimax regret Θ(sqrt(T Σ log(m_k+1))) and tight PAC sample complexity for the pure-exploration analogue m-BAI, extended to graph feedback via clique covers.
Problem
Minimax regret and pure-exploration (best arm identification) sample complexity when arms are grouped into cliques of observation, interpolating between bandit and expert feedback, and more generally bandits with graph feedback.
Approach
A two-stage OSMD algorithm (group distribution plus within-group distribution) with a new analysis via piecewise continuous processes gives the optimal Σ log(m_k+1) dependence; BAI lower bounds use a direct-sum argument over groups and an all-Ber(1/2) hard instance, with Gaussian-to-Bernoulli reduction.
Key results
- Minimax regret of m-MAB is Θ(sqrt(T Σ_k log(m_k+1))), generalizing both bandit (Θ(sqrt(NT))) and expert (Θ(sqrt(T log N))) rates.
- An (eps,0.05)-PAC algorithm for m-BAI uses O(Σ_k log(m_k+1)/eps^2) pulls, matched by an Ω(Σ_k log(m_k+1)/eps^2) lower bound for eps<1/8.
- The lower bounds extend to graph feedback with strongly observable subgraphs and to weakly observable graphs, resolving a conjectured bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use clique-group sizes in the regret bound instead of the independence-number parameter | m-MAB · m-MAB | minimax regret: O\tuple{\sqrt{TK\log(N/K)}} -> \Theta\tp{\sqrt{T\sum_{k=1}^K\log (m_k+1)}} | Helped |
| Use clique-cover sizes to characterize regret on strongly observable graphs | Bandit with graph feedback · Strongly observable graphs with self-loops | minimax regret upper bound: O\tp{\sqrt{\alpha T}\log NT} -> O\tp{\sqrt{T\sum_{k=1}^K \log m_k}} | Helped |
| Apply the two-stage OSMD algorithm to m-MAB | m-MAB · m-MAB | minimax regret: O\tuple{\sqrt{T\sum_{k=1}^K\log (m_k+1)}} | Helped |
| Reduce m-BAI to m-MAB using the two-stage OSMD regret guarantee | m-BAI · m-BAI, (ε,0.05)-PAC | number of pulls: O\tuple{\sum_{k=1}^K\frac{\log (m_k+1)}{\eps^2}} | Helped |
Surprising findings
- Chen et al.'s independence-number bound O(sqrt(TK log(N/K))) is loose here; for m=(1,...,1,N-K+1) the true minimax regret is Θ(sqrt(T log N)) versus their O(sqrt(T) log N).
Limitations
- Results are for stochastic/theoretical settings with clique-cover structure; no empirical experiments.
- Only the (eps,0.05) PAC setting with delta fixed at 0.05 is fully treated in the main results.
Experimental setup
Metrics: minimax regret expected number of pulls for (eps,0.05)-PAC
Baselines: Exp3-style OSMD bounds for strongly observable graphs FTRL with Tsallis-negative entropy for clique cover graphs Chen et al. independence-number bound
Builds on: online stochastic mirror descent bandit with graph feedback two-stage OSMD for weakly observable graphs
Closest papers by meaning
- On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice (NeurIPS 2024 · similarity 0.91)
- Combinatorial Bandits for Maximum Value Reward Function under Value-Index Feedback (ICLR 2024 · similarity 0.91)
- On the Minimax Regret for Online Learning with Feedback Graphs (NeurIPS 2023 · similarity 0.90)
- Lenient Regret for Multi-Armed Bandits (AAAI 2021 · similarity 0.90)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.89)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.89)
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.