Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
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 minimax regret for strong vs weak corruption in linear bandits, gives new corrupted adversarial linear bandit bounds, and reduces gap-dependent misspecification to corruption-robust learning with a specialized algorithm achieving optimal rho ~ 1/sqrt(d).
Problem
Corruption-robust learning in stochastic and adversarial linear bandits with tight dependence on corruption level, and learning under gap-dependent misspecification where misspecification of an action scales with its suboptimality gap.
Approach
Unified corruption framework (strong vs weak measures); an elimination algorithm that samples exactly from a G-optimal design to get sqrt(d)C_inf and dC bounds; a logdet-FTRL with a minimal-ellipsoid bonus (B_t) for adversarial corruption; and a black-box reduction from gap-dependent misspecification to corruption-robust algorithms.
Key results
- Stochastic linear bandit algorithm achieves Õ(d√T + √d C_∞) regret, matching lower bound for weak corruption.
- Adversarial linear bandit algorithms achieve Õ(d√T + √d C_∞) and Õ(√(d³T) + dC) regret under weak and strong corruption, respectively.
- For gap-dependent misspecification in linear bandits, an algorithm achieves Õ(d√T) regret with misspecification level rho up to O(1/√d), improving the prior O(1/d) requirement.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized phased elimination with the strong-corruption guarantee | Stochastic linear bandits · Stochastic linear bandits | regret upper bound (strong corruption C): \mathcal{O}(d \sqrt{T \log(T/\delta)} + dC\log T) | Helped |
| Use randomized phased elimination with the weak-corruption guarantee | Stochastic linear bandits · Stochastic linear bandits | regret upper bound (weak corruption C∞): \mathcal{O}(d \sqrt{T \log(T/\delta)} + \sqrt{d}C_\infty\log T) | Helped |
| Use a log-determinant FTRL bonus construction | Adversarial linear bandits · Adversarial linear bandits | regret upper bound (weak corruption C∞): \otil(d\sqrt{T} + \sqrt{d}C_\infty) | Helped |
| Use continuous exponential weights on the lifted action space with concentrated sampling | Adversarial linear bandits · Adversarial linear bandits | regret upper bound (strong corruption C): \otil\big(\sqrt{d^3T} + dC \big) | Helped |
| Use a specialized algorithm instead of the general corruption-robust reduction | Gap-dependent misspecified linear bandits · Gap-dependent misspecified linear bandits | permitted misspecification level ρ: \rho \le \mathcal{O} (\tfrac{1}{d \log T}) -> \rho \le \mathcal{O} (\tfrac{1}{\sqrt{d}}) | Helped |
| Use the general reduction with a corruption-robust algorithm | Gap-dependent misspecified linear MDPs · Gap-dependent misspecified linear MDPs | regret upper bound: \cOtil ( \sqrt{d^3 H^2 T} ) | Helped |
| Use deterministic rather than randomized action sampling (ablation) | Stochastic linear bandits · Stochastic linear bandits | regret lower bound (weak corruption C∞): \Omega(d\sqrt{T}+dC_\infty) | Hurt |
| Use the previous bonus design rather than the proposed cumulative matrix bonus (ablation) | Adversarial linear bandits · Adversarial linear bandits | corruption-dependent regret term: \sqrt{d}\Crmsinf >\sqrt{d}C_\infty | Hurt |
| Use the non-lifted polynomial-time CEW algorithm instead of lifted CEW (ablation) | Adversarial linear bandits · Adversarial linear bandits | regret upper bound (strong corruption C): \otil(d^3\sqrt{T} + d^{\nicefrac{5}{2}}C) | Hurt |
Surprising findings
- Deterministic algorithms must suffer Ω(d√T + dC_∞) regret under weak corruption, so many prior algorithms cannot achieve the √d C_∞ bound.
- The general reduction from gap-dependent misspecification to corruption is not able to reach the optimal rho, unlike the specialized algorithm.
Limitations
- The dC adversarial bound's algorithm is likely not computationally efficient (fixed-point formulation).
- Requires knowledge of corruption level C_∞ or C (unknown C is shown to be hard).
- Open problem: tight d√T + dC adversarial bound and tight C_∞ bound for linear contextual bandits remain open.
Experimental setup
Metrics: regret
Baselines: OFUL-style corruption-robust algorithms Bogunovic et al. corruption elimination Lee et al. corruption-robust algorithm gap-dependent misspecification algorithm of Liu et al.
Builds on: phased elimination FTRL with log-determinant regularizer continuous exponential weights SCRiBLe
Closest papers by meaning
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.89)
- Learning from Imperfect Human Feedback: A Tale from Corruption-Robust Dueling (ICLR 2025 · similarity 0.89)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.89)
- Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption (ICML 2024 · similarity 0.89)
- A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond (NeurIPS 2025 · similarity 0.89)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · 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.