Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Bandits with Online Neural Regression
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.
Shows O(log T) regret for online regression with QG/almost-convex losses and a small random output perturbation of wide networks, then converts it to O(sqrt(KT)) (NeuSquareCB) and O(sqrt(KL*)+K) (NeuFastCB) regret for neural contextual bandits.
Problem
Neural contextual bandits with adversarial contexts have weak regret guarantees: NeuralUCB/NeuralTS bounds can be Omega(T), and the naive online-regression reduction for wide networks yields O(sqrt(K) T^{3/4}) or O(sqrt(KL*)T^{1/4}+K sqrt(T)).
Approach
Show that projected OGD on losses that are almost convex, satisfy QG, and have a unique minimizer gives O(log T) regret; then make wide-network losses satisfy these via a small Rademacher random output perturbation averaged over S draws, and plug the resulting online regression bounds into SquareCB and FastCB reductions.
Key results
- NeuFastCB (KL loss) persistently outperforms NeuralUCB, NeuralTS, EE-Net and NeuralEpsilon in cumulative regret across all six OpenML multiclass-as-bandit datasets under adversarial context sampling.
- Theory: O(log T) regret for online regression with perturbed wide networks under squared and KL loss, giving O(sqrt(KT)) for NeuSquareCB and O(sqrt(KL*)+K) for NeuFastCB regret.
- Shows NeuralUCB and NeuralTS regret lower bounds of Omega(T) under the original assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add a small random perturbation to network predictions | Wide neural online regression with squared loss · Online regression | regret: O(\sqrt{T}) -> O(\log T) | Helped |
| Add a small random perturbation to network predictions | Wide neural online regression with KL loss · Online regression | regret: O(\log T) | Helped |
| Use square-loss regression with the SquareCB reduction | NeuSquareCB · Contextual bandits with adversarial contexts | regret: \tilde{{\cal O}}(\sqrt{K}T^{3/4}) -> \tilde{{\cal O}}(\sqrt{KT}) | Helped |
| Use KL-loss regression with the FastCB reduction | NeuFastCB · Contextual bandits with adversarial contexts | regret: \tilde{{\cal O}}(\sqrt{L^*K}+K) | Helped |
| Use NeuFastCB instead of baseline neural bandit algorithms | Neural contextual bandits · OpenML datasets: covertype, fashion, MagicTelescope, mushroom, Plants, shuttle | cumulative regret | Helped |
| Use NeuSquareCB or NeuFastCB instead of baseline neural bandit algorithms | Neural contextual bandits · OpenML datasets | consistency across datasets | Helped |
| Use NeuralUCB under the stated assumptions | NeuralUCB · Worst-case contextual bandits | regret bound: \Omega(T) | Hurt |
| Use NeuralTS under the stated assumptions | NeuralTS · Worst-case contextual bandits | regret bound: \Omega(T) | Hurt |
Surprising findings
- Adding a small random Rademacher output perturbation to a wide network makes the square loss satisfy QG with a unique minimizer, giving O(log T) regret despite wide networks having no unique minima.
- Existing regret bounds for NeuralUCB and NeuralTS can be Omega(T) in the worst case under their own assumptions.
Limitations
- Requires an NTK positive-definiteness assumption and wide networks (m polynomial in T) for the theory.
- The O(log T) bound for square loss holds only with the perturbation and averaging over S = Theta(log m) draws; the perturbation is not used in experiments.
Experimental setup
Datasets: covertype fashion MagicTelescope mushroom Plants shuttle
Benchmarks: covertype fashion MagicTelescope mushroom Plants shuttle
Metrics: cumulative regret
Baselines: NeuralUCB NeuralTS EE-Net NeuralEpsilon
Builds on: SquareCB FastCB NeuralUCB NeuralTS EE-Net
Closest papers by meaning
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Efficient Contextual Bandits with Uninformed Feedback Graphs (ICML 2024 · similarity 0.90)
- Contextual Online Decision Making with Infinite-Dimensional Functional Regression (ICML 2025 · similarity 0.88)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.88)
- High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions (ICML 2025 · similarity 0.88)
- Conservative Contextual Bandits: Beyond Linear Representations (ICLR 2025 · similarity 0.88)
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.