mlsanityData to 14 Oct 2026

Perturbed-History Exploration in Stochastic Linear Bandits

arXiv 1903.09132 ↗First posted 21 Mar 2019cs.LG stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

We propose a new online algorithm for cumulative regret minimization in a stochastic linear bandit. The algorithm pulls the arm with the highest estimated reward in a linear model trained on its perturbed history. Therefore, we call it perturbed-history exploration in a linear bandit (LinPHE). The perturbed history is a mixture of observed rewards and randomly generated i.i.d. pseudo-rewards. We derive a tildeO(d √n) gap-free bound on the n-round regret of LinPHE, where d is the number of features. The key steps in our analysis are new concentration and anti-concentration bounds on the weighted sum of Bernoulli random variables. To show the generality of our design, we generalize LinPHE to a logistic model. We evaluate our algorithms empirically and show that they are practical.

Key facts. Cited by 29 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Mar 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 5; 2024: 4; 2025: 4; 2026: 3.

29 papers.

Sort:

By area:

  1. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  2. 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 24
  3. 2022An Analysis of Ensemble Samplingcited by 24
  4. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  5. 2022Learning Neural Contextual Bandits Through Perturbed Rewardscited by 17
  6. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  7. 2023Exploration via linearly perturbed loss minimisationcited by 13
  8. 2021Diffusion Approximations for Thompson Sampling in the Small Gap Regimecited by 12
  9. 2022Residual Bootstrap Exploration for Stochastic Linear Banditcited by 8
  10. 2021Anti-Concentrated Confidence Bonuses for Scalable Explorationcited by 7
  11. 2023Ensemble sampling for linear bandits: small ensembles sufficecited by 7
  12. 2022Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Banditscited by 6
17 more
  1. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6
  2. 2024Improved Regret of Linear Ensemble Samplingcited by 6
  3. 2023Multiplier Bootstrap-based Explorationcited by 3
  4. 2024Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Banditscited by 3
  5. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  6. 2021CORe: Capitalizing On Rewards in Bandit Explorationcited by 1
  7. 2021An Efficient Algorithm for Deep Stochastic Contextual Banditscited by 1
  8. 2022Some performance considerations when using multi-armed bandit algorithms in the presence of missing datacited by 1
  9. 2024Graph Neural Thompson Samplingcited by 1
  10. 2025Exploration by Random Reward Perturbationcited by 1
  11. 2026Laplacian Kernelized Banditcited by 1
  12. 2023Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Banditscited by 0
  13. 2023Zero-Inflated Banditscited by 0
  14. 2025Adaptive Data Augmentation for Thompson Samplingcited by 0
  15. 2025Exploration via Feature Perturbation in Contextual Banditscited by 0
  16. 2026Linear Ensemble Sampling with Smaller Ensemblescited by 0
  17. 2026Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Setscited by 0