Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization
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.
Proposes two noise-adaptive confidence sets for linear bandits (semi-adaptive to sub-Gaussian parameter via weighted ridge regression and regret equality; fully variance-adaptive for bounded noise via intersection of L sets), yielding optimistic algorithms LOSAN and LOFAV evaluated on synthetic and Bayesian optimization tasks.
Problem
Linear bandits require knowing the noise level (sub-Gaussian parameter or bounded range) for efficient exploration, but this is often loosely specified; existing confidence sets scale with the specified rather than actual noise, and variance-adaptive methods (SAVE) are sample-inefficient and assume
Approach
Use the FTRL regret equality to keep the online loss term A_t (instead of bounding it by its worst case) in the confidence set, combined with a weighted ridge regression that keeps leverage terms ≤1/2; for bounded noise, intersect L base confidence sets indexed by scale levels with an exponential cover and secondary centers, enabling optimistic (OFUL-style) variance-adaptive algorithms.
Key results
- Semi-adaptive LOSAN confidence width scales as sqrt(d sigma_*^2 + sigma_0^2), giving regret O~(sigma_0 sqrt(dn) + sigma_* d sqrt(n)) versus O~(sigma_0 d sqrt(n)) for prior art, a sqrt(d) improvement when sigma_*^2 << sigma_0^2.
- LOFAV achieves the optimal variance-adaptive regret d sqrt(R^2 + sum sigma_t^2) up to log factors, matching SAVE while using all samples and O(d^2 n |X_t|) complexity like OFUL.
- In a worked example (n=500,000, d=2), the upper confidence bound on an arm's mean is 1.01 with the proposed full-adaptive set versus 7.66 with the prior variance-adaptive set and 1.05 with SNCS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LOSAN's semi-adaptive confidence set instead of the standard OFUL confidence set | Linear bandits with sub-Gaussian noise · Linear bandits (sub-Gaussian noise) | cumulative regret: \sig_0 d\sqrt{n\ln(1/\dt)} + dB -> \sig_* d \sqrt{n} + \sig_0 \sqrt{dn\ln(1/\dt)}+ dB | Helped |
| Use LOFAV's optimistic algorithm and confidence set instead of SAVE | Linear bandits with bounded noise · Linear bandits (bounded noise) | numerical tightness of confidence set: 7.66 -> 1.01 | Helped |
| Use LOFAV's confidence set instead of SNCS | Linear bandits with bounded noise; 500,000 samples, d=2 · Linear bandits (bounded noise) | upper confidence bound on mean reward for arm x=(1,0): 1.05 -> 1.01 | Helped |
| Use LOSAN and LOFAV instead of OFUL | Synthetic linear bandit experiments · Synthetic experiments | cumulative regret | Helped |
| Use LOSAN or LOFAV instead of OFUL or Bayesian optimization baselines | Bayesian optimization with benchmark functions · Beale, Branin, Three-Hump Camel, and Zakharov 4D | simple regret | Helped |
| Use LOSAN instead of the other evaluated methods | Bayesian optimization on NATS-Bench · NATS-Bench CIFAR-100 and ImageNet-16-120 | simple regret | Mixed |
Surprising findings
- The prior variance-adaptive confidence set (SAVE's) needs many samples before it becomes tighter than the standard self-normalized set.
Limitations
- Semi-adaptive regret bound and confidence set analysis rely on the assumption that ||x||_{V^-1} constraints via weighted ridge; the sub-Gaussian confidence set cannot be strictly tighter than SNCS without the weighting.
- LOFAV requires L = O(log(n/d)) confidence sets and extra log factors and constants, making it loose in the small-sample regime (mitigated by a practical version).
- Bayesian optimization experiments use a finite sampled arm set with random Fourier features and a fixed 128-dimensional feature map, which is a simplification.
Experimental setup
Datasets: NATS-Bench Beale Branin Three-Hump Camel Zakharov 4D synthetic linear bandit data
Benchmarks: NATS-Bench (CIFAR-100, ImageNet-16-120) Beale Branin Three-Hump Camel Zakharov 4D synthetic linear bandits
Metrics: cumulative regret simple regret
Baselines: OFUL SAVE Gaussian process UCB Gaussian process expected improvement NATS-Bench baselines
Builds on: OFUL SAVE self-normalized confidence set (Abbasi-Yadkori et al. 2011) online-to-confidence-set conversion random Fourier features
Closest papers by meaning
- Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling (ICLR 2024 · similarity 0.91)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.91)
- Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.90)
- Constrained Linear Thompson Sampling (NeurIPS 2025 · similarity 0.89)
- Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update (ICML 2025 · similarity 0.89)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (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.