Research map / Bandits and online learning / Online convex optimization and games
Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a randomized strategy from the instance-optimality optimization problem and robust loss estimates | REOLB · Stochastic linear bandits | regret: \mathcal{O}(c(\mathcal{X}, \theta)\log T\log\frac{T|\mathcal{X}|}{\delta}) | Helped |
| Use randomized sampling and robust loss estimation to handle corruption | REOLB · Corrupted linear bandits | regret: +C | Helped |
| Add an adversarial bandit component and statistical tests that switch between adversarial learning and REOLB-style allocation | BOTW · Adversarial linear bandits | regret: \mathcal{O}\left(\sqrt{C_1 T\log T}+\sqrt{C_1L_0}\right) | Helped |
| Combine the adversarial component and stochasticity tests with instance-optimal action allocation | BOTW · Stochastic linear bandits | regret: \mathcal{O}(c(\mathcal{X}, \theta)\log^2 T) | Helped |
| Use BOTW rather than REOLB for corrupted-setting guarantees | Linear bandit algorithms · Corrupted linear bandits | regret: \mathcal{O}(\frac{d\log^2 T}{\Delta_{\min}}+C) versus \mathcal{O}(c(\mathcal{X}, \theta)\log^2 T+C) | Mixed |
Closest papers by meaning
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.91)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.91)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.90)
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.90)
- An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction (NeurIPS 2025 · similarity 0.90)
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 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.