Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Stochastic Bandits with ReLU Neural Networks
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.
Proves a Õ(√T) regret bound for stochastic bandits whose reward is a one-layer ReLU network, via random exploration to estimate neurons, then OFUL on a transformed linear feature space (OFU-ReLU), plus a batched variant (OFU-ReLU+) that removes knowledge of the gap.
Problem
Stochastic bandits where the reward is a ReLU neural network; prior ReLU/NTK bandit methods yield regret bounds that are superlinear or depend on an effective dimension, and no √T-type guarantee was known for neural bandits without such assumptions.
Approach
Randomly explore until the ReLU neuron parameters are estimated accurately, then freeze the indicator functions at the estimates so the reward becomes linear in a transformed (kd- or 2kd-dimensional) feature space; add k extra features to handle sign ambiguity, and use geometrically shrinking batches with cumulative data to remove the need to know the optimal-action gap.
Key results
- OFU-ReLU achieves regret Õ(kd√T) plus a T-independent exploration term, the first Õ(√T) bound for neural-network bandits without effective-dimension assumptions (one-layer ReLU).
- OFU-ReLU+ achieves Õ(k^14 d^7 + k^14 d^3 T^{8 log b/log a} + kd√T), recovering Õ(√T) when 8 log b / log a ≤ 1/2 (e.g., a=2, b=2^{1/32} gives T^{1/4} term).
- In synthetic experiments with T=1000 over 50 trials, OFU-ReLU significantly outperforms OFUL and NeuralUCB variants, with exploration length of only 20 steps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OFU-ReLU instead of the benchmark algorithms | Synthetic one-layer ReLU bandit · d=2, k=3 and d=2, k=10 | cumulative regret | Helped |
| Use OFU-ReLU instead of NeuralUCB-T | Synthetic one-layer ReLU bandit · d=2, k=3 and d=2, k=10 | cumulative regret | Helped |
| Use OFU-ReLU with a 20-step exploration phase | OFU-ReLU · Synthetic bandit, T=1,000 | convergence time | Helped |
Surprising findings
- The theoretical exploration phase is very long (t0 scales like k^13 d^3 / nu^8), yet a practical exploration length of only 20 steps performed best in experiments.
Limitations
- Restricted to one-layer ReLU networks with unit second-layer weights and unit-norm neurons plus separation assumptions.
- Theoretical exploration length and regret constants are very large polynomials in k, d and 1/nu_*.
- Experiments are small synthetic settings with d=2 only.
Experimental setup
Benchmarks: synthetic ReLU bandit settings (d=2, k=3 and k=10)
Metrics: cumulative regret
Baselines: OFUL NeuralUCB-F NeuralUCB-T NeuralUCB-TW
Builds on: OFUL NeuralUCB Neural tangent kernel bandits
Closest papers by meaning
- No-Regret Bandit Exploration based on Soft Tree Ensemble Model (NeurIPS 2024 · similarity 0.89)
- Neural Contextual Bandits with UCB-based Exploration (ICML 2020 · similarity 0.88)
- An Efficient Algorithm for Deep Stochastic Contextual Bandits (AAAI 2021 · similarity 0.88)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
- Exploration via Feature Perturbation in Contextual Bandits (NeurIPS 2025 · similarity 0.86)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.86)
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.