Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach

• URL: http://arxiv.org/abs/2606.20022v1
• Date: Thu, 18 Jun 2026 09:54:23 GMT
• Title: Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach
• Abstract summary: Bounded reward noise is more informative than the sub-Gaussian condition but has not been leveraged explicitly in the SLCB literature.<n>We propose a novel algorithm SME-OFU by utilizing an uncertainty quantification method called set-membership estimation (SME) and applying the principle of optimism in the face of uncertainty (OFU)<n>Our algorithm enjoys an improved regret bound $tildeO(sqrtT)$ for sub-Gaussian noise because bounded noise is a stronger condition.
• Score: 13.426300917962712
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers stochastic linear contextual bandits (SLCB) with bounded reward noise. Existing works typically assume sub-Gaussian reward noise and bounded expected rewards, under which the optimal regret bound scales as $\tilde{O}(\sqrt{T})$ in terms of horizon $T$. However, in many applications, realized/observed rewards are also naturally bounded, implying bounded reward noise. Bounded noise is more informative than the sub-Gaussian condition but has not been leveraged explicitly in the SLCB literature. In this paper, we propose a novel algorithm SME-OFU by utilizing an uncertainty quantification method called set-membership estimation (SME) and applying the principle of optimism in the face of uncertainty (OFU). Our algorithm enjoys an improved regret bound $O(\log T)$. Notice that this does not contradict the existing optimal bound $\tilde{O}(\sqrt{T})$ for sub-Gaussian noise because bounded noise is a stronger condition. Finally, simulations show empirical improvements of SME-OFU over a benchmark algorithm designed for sub-Gaussian noise when the reward noise is bounded.

Related papers

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
  In this paper, we revisit the linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process.<n>We propose a novel variance-adaptive algorithm textttVAEE for large action set, which actively explores actions that maximize the information gain.<n>We establish a nearly matching lower bound for the fixed action set setting indicating that emphharmonic-mean dependent rate is unavoidable.
  arXiv  Detail & Related papers  (2026-07-26T14:24:34Z)
• Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization [12.903796669387809]
  We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses.<n>We establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction.
  arXiv  Detail & Related papers  (2026-06-06T07:40:55Z)
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits [54.220839560203096]
  We present FGTSVA, a variance-aware Thompson Sampling algorithm for contextual bandits with general reward function with optimal regret bound.<n>With the new decoupling coefficient denoted by $mathrmdc$, FGTS-VA achieves the regret of $tildeO(sqrtmathrmdccdotlog|mathcalF|$, where $|mathcalF|$ is the size of the model space.<n>In the setting of contextual linear bandits, the regret bound of FGTSVA matches that of UCB-based
  arXiv  Detail & Related papers  (2025-11-03T23:25:41Z)
• Optimal High-probability Convergence of Nonlinear SGD under Heavy-tailed Noise via Symmetrization [50.49466204159458]
  We propose two novel estimators based on the idea of noise symmetrization.<n>We provide a sharper analysis and improved rates.<n>Compared to works assuming symmetric noise with moments, we provide a sharper analysis and improved rates.
  arXiv  Detail & Related papers  (2025-07-12T00:31:13Z)
• Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits [3.6985338895569204]
  We show the nearly optimal regret upper bound of noise-free GP-UCB.<n>Specifically, our analysis shows the first constant cumulative regret in the noise-free settings for the squared exponential kernel and Mat'ern kernel.
  arXiv  Detail & Related papers  (2025-02-26T10:10:51Z)
• Lasso Bandit with Compatibility Condition on Optimal Arm [10.216425987201333]
  We consider a sparse linear bandit problem where only a sparse subset of context features affects the expected reward function.<n>We propose an algorithm that adapts the forced-sampling technique and prove that the proposed algorithm achieves $O(textpolylog dT)$ regret.
  arXiv  Detail & Related papers  (2024-06-02T18:11:47Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  We study a distributed multi-armed bandit where a client supplies the learner with communication-constrained feedback. We propose a multi-phase bandit algorithm, $mathttUEtext-UCB++$, which matches this lower bound to a minor additive factor.
  arXiv  Detail & Related papers  (2023-04-25T09:31:20Z)
• Higher degree sum-of-squares relaxations robust against oblivious outliers [14.58610686291355]
  We consider estimation models of the form $Y=X*+N$, where $X*$ is some $m$-dimensional signal we wish to recover. We introduce a family of algorithms that under mild assumptions recover the signal $X*$ in all estimation problems for which there exists a sum-of-squares algorithm.
  arXiv  Detail & Related papers  (2022-11-14T13:09:12Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  We show how to characterize the trade-off between regret bounds of GP bandit algorithms and complexity of the posterior distributions. We observe state of the art accuracy and complexity trade-offs for GP bandit algorithms applied to global optimization.
  arXiv  Detail & Related papers  (2020-03-23T21:05:15Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  We develop Thompson Sampling-style algorithms for mean-variance MAB. We also provide comprehensive regret analyses for Gaussian and Bernoulli bandits. Our algorithms significantly outperform existing LCB-based algorithms for all risk tolerances.
  arXiv  Detail & Related papers  (2020-02-01T15:33:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.