# Exploration via linearly perturbed loss minimisation

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 41 references that are in the map.
- First posted on arXiv 13 Nov 2023.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [Self-Concordant Analysis of Generalized Linear Bandits with Forgetting](https://mlsanity.com/paper/2011.00819/) (2020)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [Sampling-based inference for large linear models, with application to linearised Laplace](https://mlsanity.com/paper/2210.04994/) (2022)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)

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

- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning](https://mlsanity.com/paper/2403.05385/) (2024)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits](https://mlsanity.com/paper/2410.01112/) (2024)
- [When and why randomised exploration works (in linear bandits)](https://mlsanity.com/paper/2502.08870/) (2025)
- [Posterior Behavioral Cloning: Pretraining BC Policies for Efficient RL Finetuning](https://mlsanity.com/paper/2512.16911/) (2025)
- [Ensemble sampling for linear bandits: small ensembles suffice](https://mlsanity.com/paper/2311.08376/) (2023)
- [Eluder dimension: localise it!](https://mlsanity.com/paper/2601.09825/) (2026)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [ε-Policy Gradient for Online Pricing](https://mlsanity.com/paper/2405.03624/) (2024)
- [On the Sublinear Regret of Continuous K-Max Bandits](https://mlsanity.com/paper/2502.13467/) (2025)
- [Exploration via Feature Perturbation in Contextual Bandits](https://mlsanity.com/paper/2510.17390/) (2025)
- [Variance-sensitive Thompson sampling for generalised linear bandits, revisited](https://mlsanity.com/paper/2606.00431/) (2026)

## Abstract (arXiv)

We introduce exploration via linear loss perturbations (EVILL), a randomised exploration method for structured stochastic bandit problems that works by solving for the minimiser of a linearly perturbed regularised negative log-likelihood function. We show that, for the case of generalised linear bandits, EVILL reduces to perturbed history exploration (PHE), a method where exploration is done by training on randomly perturbed rewards. In doing so, we provide a simple and clean explanation of when and why random reward perturbations give rise to good bandit algorithms. We propose data-dependent perturbations not present in previous PHE-type methods that allow EVILL to match the performance of Thompson-sampling-style parameter-perturbation methods, both in theory and in practice. Moreover, we show an example outside generalised linear bandits where PHE leads to inconsistent estimates, and thus linear regret, while EVILL remains performant. Like PHE, EVILL can be implemented in just a few lines of code.