# Residual Bootstrap Exploration for Stochastic Linear Bandit

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 45 references that are in the map.
- First posted on arXiv 23 Feb 2022.

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

- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Bootstrapped Thompson Sampling and Deep Exploration](https://mlsanity.com/paper/1507.00300/) (2015)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [Online Forgetting Process for Linear Regression Models](https://mlsanity.com/paper/2012.01668/) (2020)
- [Thompson sampling with the online bootstrap](https://mlsanity.com/paper/1410.4009/) (2014)
- [On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variables](https://mlsanity.com/paper/1810.09006/) (2018)
- [Residual Bootstrap Exploration for Bandit Algorithms](https://mlsanity.com/paper/2002.08436/) (2020)
- [Online Batch Decision-Making with High-Dimensional Covariates](https://mlsanity.com/paper/2002.09438/) (2020)
- [New Insights into Bootstrapping for Bandits](https://mlsanity.com/paper/1805.09793/) (2018)
- [Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization](https://mlsanity.com/paper/2106.09215/) (2021)

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

- [Federated Online Sparse Decision Making](https://mlsanity.com/paper/2202.13448/) (2022)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm](https://mlsanity.com/paper/2303.07287/) (2023)
- [Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System](https://mlsanity.com/paper/2406.04374/) (2024)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Laplacian Kernelized Bandit](https://mlsanity.com/paper/2601.00461/) (2026)
- [Zero-Inflated Bandits](https://mlsanity.com/paper/2312.15595/) (2023)
- [Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback](https://mlsanity.com/paper/2610.17760/) (2026)

## Abstract (arXiv)

We propose a new bootstrap-based online algorithm for stochastic linear bandit problems. The key idea is to adopt residual bootstrap exploration, in which the agent estimates the next step reward by re-sampling the residuals of mean reward estimate. Our algorithm, residual bootstrap exploration for stochastic linear bandit (textttLinReBoot), estimates the linear reward from its re-sampling distribution and pulls the arm with the highest reward estimate. In particular, we contribute a theoretical framework to demystify residual bootstrap-based exploration mechanisms in stochastic linear bandit problems. The key insight is that the strength of bootstrap exploration is based on collaborated optimism between the online-learned model and the re-sampling distribution of residuals. Such observation enables us to show that the proposed textttLinReBoot secure a high-probability tildeO(d √n) sub-linear regret under mild conditions. Our experiments support the easy generalizability of the textttReBoot principle in the various formulations of linear bandit problems and show the significant computational efficiency of textttLinReBoot.