Research map / Bandits and online learning / Contextual bandits and Thompson sampling
An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
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.
Reduces adversarial linear contextual bandits with stochastic action sets to misspecification-robust adversarial linear bandits over an empirical Minkowski-sum feasible set, giving poly(d,T) time and ~min{d^2 sqrt T, sqrt(d^3 T log K)} regret without a simulator.
Problem
Adversarial linear contextual bandits with i.i.d. stochastic action sets and unknown context distribution, where prior efficient algorithms scale polynomially with the number of actions K and achieve suboptimal regret without a simulator.
Approach
Approximates the policy-induced feasible set by an empirical Minkowski sum of convex hulls of N sampled action sets, decomposes points into mixtures of linear classifier policies via a Frank-Wolfe procedure that calls a linear optimization oracle, and runs a misspecification-robust continuous exponential weights bandit algorithm with a bonus term.
Key results
- Achieves regret Õ(min{d^2 sqrt(T), sqrt(d^3 T log K)}) for adversarial linear contextual bandits with stochastic action sets without a simulator, running in poly(d,T) time plus poly(d,T) linear optimization oracle calls.
- With a simulator, achieves Õ(d sqrt(L*)) small-loss regret, recovering the minimax d sqrt(T) rate.
- First algorithm to achieve poly(d) sqrt(T) regret in polynomial time for combinatorial bandits with stochastic action sets and adversarial losses (per the authors).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed reduction with simulator access rather than without simulator access | Ours · Adversarial linear contextual bandits | regret: \min\{d^2\sqrt{T}, \sqrt{d^3T\log K}\} -> d\sqrt{L^\star} | Helped |
| Use the proposed algorithm instead of the prior combinatorial-bandit algorithm | Adversarial linear contextual bandits with stochastic action sets · Combinatorial bandits with stochastic action sets and adversarial losses | regret: (dT)^{2/3} -> \sqrt{T} | Helped |
Limitations
- Without a simulator the bound has d^2 sqrt(T) rather than the optimal d sqrt(T) dependence.
- Small-loss bound with poly(d) sqrt(L*) without a simulator remains open.
- Requires access to a linear optimization oracle for action sets and knowledge of misspecification level epsilon.
Experimental setup
Metrics: regret
Baselines: Dani et al. 2008-style LinUCB-type methods Neu and Olkhovskaya 2020 Liu et al. 2023 Majumdar et al. 2017 style sleeping bandits
Builds on: continuous exponential weights Frank-Wolfe misspecified linear bandits
Closest papers by meaning
- Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits (NeurIPS 2023 · similarity 0.95)
- First- and Second-Order Bounds for Adversarial Linear Contextual Bandits (NeurIPS 2023 · similarity 0.94)
- Efficient Algorithms for Adversarial Contextual Learning (ICML 2016 · similarity 0.93)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.92)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.90)
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.