Research map / Bandits and online learning / Multi-armed bandits
On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice
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.
Gives a matching Ω(√(KT log+(N/K))) lower bound for multi-armed bandits with expert advice (closing the minimax gap), and an FTRL-Tsallis contextual linear bandit algorithm with context-dependent learning rates achieving O(√(dT log+(K min{1,S/d}))) with a matching lower bound.
Problem
Determining the minimax regret for multi-armed bandits with expert advice (for arbitrary K and N) and for stochastic-context adversarial-loss contextual linear bandits, where prior upper and lower bounds did not match.
Approach
Lower bound for BwE is obtained by reducing from best-expert identification with a PAC argument and constructing instances with N' = Θ(N/K) experts per arm pair, replicated Θ(K) times. For CLB, FTRL with a context-adaptive Tsallis entropy regularizer (tuned α, context-dependent learning rate η(x)) yields improved upper bounds, with a matching lower bound built from S copies of the Dani et al. inst
Key results
- Lower bound Ω(√(KT log+(N/K))) for multi-armed bandits with expert advice when the expert is chosen before advice is observed, matching Kale's 2014 upper bound and resolving the open question of Seldin and Lugosi.
- Contextual linear bandit algorithm achieves O(√(dT log+(K min{1,S/d}))) regret, improving on O(d√(T log T)) of Liu et al. 2024 in the stochastic-context setting.
- Matching lower bound Ω(√(dT log+(K min{1,S/d}))) for contextual linear bandits holds for K ≤ 2d ≤ KS; for linear bandits the upper bound O(√(dT log+(K/d))) improves on O(√(dT log K)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Establish a lower bound matching Kale's upper-bound rate | Multi-armed bandit with expert advice (BwE), when the player chooses an expert before observing advice · BwE | regret: Ω(√KT log+ N/K) | Helped |
| Use FTRL with Tsallis entropy regularization and tune α rather than fixing it to 1 | Proposed linear bandit algorithm · Linear bandit | regret upper bound: O(√dT log K) -> O(√dT log+ K/d) | Helped |
| Use FTRL with Tsallis entropy and context-dependent learning rates | Proposed contextual linear bandit algorithm · Contextual linear bandit | regret upper bound: O(d√T log T) -> O(√dT log+ (K min{1, S/d})) | Helped |
| Tune context-dependent learning rates η(x) | Proposed contextual linear bandit algorithm · Contextual linear bandit | regret upper bound: O(√dT log+ (KS/d) + λ0√T1−β) | Helped |
Limitations
- Lower bound for BwE only covers the setting where the expert is chosen before observing advice.
- Contextual linear bandit analysis assumes a finite context space with known context distribution bounded below by 1/L (Assumption 1).
- Computing V(p_t) may be computationally expensive in the infinite-context case.
Experimental setup
Metrics: regret
Baselines: EXP4 Kale 2014 Liu et al. 2024 Bubeck et al. 2012 Dani et al. 2008
Builds on: EXP4 EXP2 Kale 2014 bandits with expert advice Seldin and Lugosi 2016 Neu and Olkhovskaya 2020
Closest papers by meaning
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.91)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.90)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.90)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.89)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.89)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 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.