# Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization

arXiv: https://arxiv.org/abs/2402.07341 · HTML: https://mlsanity.com/paper/2402.07341/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 45 references that are in the map.
- First posted on arXiv 12 Feb 2024.

## Builds on (most cited first, 21 of 21)

- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [NATS-Bench: Benchmarking NAS Algorithms for Architecture Topology and Size](https://mlsanity.com/paper/2009.00437/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures](https://mlsanity.com/paper/2309.14298/) (2023)
- [Likelihood Ratio Confidence Sets for Sequential Decision Making](https://mlsanity.com/paper/2311.04402/) (2023)

## Built on by (most cited first, 6 of 6)

- [Linear Bandits on Ellipsoids: Minimax Optimal Algorithms](https://mlsanity.com/paper/2502.17175/) (2025)
- [Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity](https://mlsanity.com/paper/2511.03606/) (2025)
- [Second-Order Bounds for [0,1]-Valued Regression via Betting Loss](https://mlsanity.com/paper/2507.12584/) (2025)
- [Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts](https://mlsanity.com/paper/2606.09802/) (2026)
- [The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems](https://mlsanity.com/paper/2608.08826/) (2026)
- [Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2608.26755/) (2026)

## Abstract (arXiv)

Adapting to a priori unknown noise level is a very important but challenging problem in sequential decision-making as efficient exploration typically requires knowledge of the noise level, which is often loosely specified. We report significant progress in addressing this issue for linear bandits in two respects. First, we propose a novel confidence set that is `semi-adaptive' to the unknown sub-Gaussian parameter σ_*2 in the sense that the (normalized) confidence width scales with √dσ_*2 + σ02 where d is the dimension and σ02 is the specified sub-Gaussian parameter (known) that can be much larger than σ_*2. This is a significant improvement over √dσ02 of the standard confidence set of Abbasi-Yadkori et al. (2011), especially when d is large or σ_*2=0. We show that this leads to an improved regret bound in linear bandits. Second, for bounded rewards, we propose a novel variance-adaptive confidence set that has much improved numerical performance upon prior art. We then apply this confidence set to develop, as we claim, the first practical variance-adaptive linear bandit algorithm via an optimistic approach, which is enabled by our novel regret analysis technique. Both of our confidence sets rely critically on `regret equality' from online learning. Our empirical evaluation in diverse Bayesian optimization tasks shows that our proposed algorithms demonstrate better or comparable performance compared to existing methods.