# Perturbed-History Exploration in Stochastic Linear Bandits

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

## Key facts

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

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

- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Learning Neural Contextual Bandits Through Perturbed Rewards](https://mlsanity.com/paper/2201.09910/) (2022)
- [Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2212.13540/) (2022)
- [Exploration via linearly perturbed loss minimisation](https://mlsanity.com/paper/2311.07565/) (2023)
- [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021)
- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Anti-Concentrated Confidence Bonuses for Scalable Exploration](https://mlsanity.com/paper/2110.11202/) (2021)
- [Ensemble sampling for linear bandits: small ensembles suffice](https://mlsanity.com/paper/2311.08376/) (2023)
- [Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits](https://mlsanity.com/paper/2206.05404/) (2022)
- [Random Latent Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.13755/) (2024)
- [Improved Regret of Linear Ensemble Sampling](https://mlsanity.com/paper/2411.03932/) (2024)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits](https://mlsanity.com/paper/2406.05710/) (2024)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [CORe: Capitalizing On Rewards in Bandit Exploration](https://mlsanity.com/paper/2103.04387/) (2021)
- [An Efficient Algorithm for Deep Stochastic Contextual Bandits](https://mlsanity.com/paper/2104.05613/) (2021)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Exploration by Random Reward Perturbation](https://mlsanity.com/paper/2506.08737/) (2025)
- [Laplacian Kernelized Bandit](https://mlsanity.com/paper/2601.00461/) (2026)
- [Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits](https://mlsanity.com/paper/2307.03587/) (2023)
- [Zero-Inflated Bandits](https://mlsanity.com/paper/2312.15595/) (2023)
- [Adaptive Data Augmentation for Thompson Sampling](https://mlsanity.com/paper/2506.14479/) (2025)
- [Exploration via Feature Perturbation in Contextual Bandits](https://mlsanity.com/paper/2510.17390/) (2025)
- [Linear Ensemble Sampling with Smaller Ensembles](https://mlsanity.com/paper/2609.13954/) (2026)
- [Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets](https://mlsanity.com/paper/2610.17818/) (2026)

## 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.