Randomized Exploration for Linear Bandits via Absolute Perturbations

• URL: http://arxiv.org/abs/2606.28616v1
• Date: Fri, 26 Jun 2026 21:22:17 GMT
• Title: Randomized Exploration for Linear Bandits via Absolute Perturbations
• Abstract summary: Absolute Thompson Sampling (ATS) is a simple modification of Thompson Sampling (TS) that ensures optimism in expectation.<n>ATS achieves $tildeO(d3/2sqrtK)$ regret, matching existing bounds for TS in linear bandits.<n> Ensemble Absolute Thompson Sampling (EATS) takes the maximum over multiple absolute perturbations with normalization by the ensemble size.
• Score: 29.1817020301259
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature. We propose Absolute Thompson Sampling (ATS), a simple modification of TS that ensures optimism in expectation by replacing the signed exploration noise with its absolute value. This preserves the computational efficiency of TS while avoiding the technically involved anti-concentration arguments common in TS analyses, enabling a simple UCB-style regret analysis. We show that ATS achieves $\tilde{O}(d^{3/2}\sqrt{K})$ regret, matching existing bounds for TS in linear bandits. We further introduce Ensemble Absolute Thompson Sampling (EATS), which takes the maximum over multiple absolute perturbations with normalization by the ensemble size. As the ensemble size grows, EATS converges to the UCB objective, recovering UCB behavior in the limit. Experiments show that moderate ensemble sizes already yield strong performance. Our results point to a bridge between randomized exploration and deterministic optimism both in theory and practice.

Related papers

• Tight Generalization Bounds for Noiseless Inverse Optimization [20.72173263660803]
  Inverse optimization (IO) seeks to infer the parameters of a decision-maker's objective from observed context--action data.<n>We provide a high-probability $O(fracdT)$ bound for the induced action set, where $d$ is the number of unknown parameters and $T$ is the size of the training dataset.<n>We show that the $O(fracdT)$ rate is tight over all consistent estimators considered here, and extend the result to both instantaneous and cumulative regret.
  arXiv  Detail & Related papers  (2026-05-09T10:33:38Z)
• Thompson Sampling for Multi-Objective Linear Contextual Bandit [29.777578580338584]
  We study the multi-objective linear contextual bandit problem, where multiple possible conflicting objectives must be optimized simultaneously.<n>We propose textttMOL-TS, the textitfirst Thompson Sampling algorithm with Pareto regret guarantees for this problem.<n> Empirical results confirm the benefits of our proposed approach, demonstrating improved regret minimization and strong multi-objective performance.
  arXiv  Detail & Related papers  (2025-11-30T15:18:01Z)
• 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)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model.<n>Our results rely on a combination of FTRL over occupancy measures, self-bounding techniques, and new loss estimators inspired by recent advances in online shortest path problems.
  arXiv  Detail & Related papers  (2025-10-20T02:28:08Z)
• Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective [17.53150194998013]
  We introduce TS-SA, which incorporates approximation (SA) within the Thompson Sampling (TS) framework.<n>In each round, TS-SA constructs a posterior approximation only using the most recent reward(s) and applies an SA step to average noisy proposals over time.<n>This can be interpreted as approximating a stationary posterior target throughout the entire algorithm.
  arXiv  Detail & Related papers  (2025-10-06T17:01:29Z)
• Thompson Sampling-like Algorithms for Stochastic Rising Bandits [20.143361197609934]
  Rising rested bandit (SRRB) is a setting where the arms' expected rewards increase as they are pulled.<n>This work provides novel regret analyses for such algorithms in SRRBs, highlighting the challenges and providing new technical tools of independent interest.
  arXiv  Detail & Related papers  (2025-05-17T17:19:07Z)
• Scalable Exploration via Ensemble++ [29.871658730354437]
  We propose a scalable exploration framework using a novel shared-factor ensemble architecture with random linear combinations.<n>For linear bandits, we provide theoretical guarantees showing that Ensemble++ achieves regret comparable to exact Thompson Sampling.<n>We extend this theoretical foundation to nonlinear rewards by replacing fixed features with learnable neural representations.
  arXiv  Detail & Related papers  (2024-07-18T06:16:09Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family. We propose a Thompson sampling, termed Expulli, which uses a novel sampling distribution to avoid the under-estimation of the optimal arm.
  arXiv  Detail & Related papers  (2022-06-07T18:08:21Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  We investigate multi-armed bandit with semi-bandit feedback (CMAB) We analyze variants of the Combinatorial Thompson Sampling policy (CTS) This last result gives us an alternative to the Efficient Sampling for Combinatorial Bandit policy (ESCB)
  arXiv  Detail & Related papers  (2020-06-11T17:12:11Z)
• Thompson Sampling for Linearly Constrained Bandits [18.477962150017095]
  We describe LinConTS, an algorithm for bandits that place a linear constraint on the probability of earning a reward in every round. We show that for LinConTS, the regret as well as the cumulative constraint violations are upper bounded by O(log T) for the suboptimal arms.
  arXiv  Detail & Related papers  (2020-04-20T13:06:35Z)

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.