# Residual Bootstrap Exploration for Bandit Algorithms

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2020.

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

- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization](https://mlsanity.com/paper/2106.09215/) (2021)
- [Did we personalize? Assessing personalization by an online reinforcement learning algorithm using resampling](https://mlsanity.com/paper/2304.05365/) (2023)
- [From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits](https://mlsanity.com/paper/2111.09724/) (2021)
- [Federated Online Sparse Decision Making](https://mlsanity.com/paper/2202.13448/) (2022)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Batch Ensemble for Variance Dependent Regret in Stochastic Bandits](https://mlsanity.com/paper/2409.08570/) (2024)
- [Forced Exploration in Bandit Problems](https://mlsanity.com/paper/2312.07285/) (2023)
- [Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System](https://mlsanity.com/paper/2406.04374/) (2024)
- [GuideBoot: Guided Bootstrap for Deep Contextual Bandits](https://mlsanity.com/paper/2107.08383/) (2021)
- [FLASH: Federated Learning Across Simultaneous Heterogeneities](https://mlsanity.com/paper/2402.08769/) (2024)

## Abstract (arXiv)

In this paper, we propose a novel perturbation-based exploration method in bandit algorithms with bounded or unbounded rewards, called residual bootstrap exploration (textttReBoot). The textttReBoot enforces exploration by injecting data-driven randomness through a residual-based perturbation mechanism. This novel mechanism captures the underlying distributional properties of fitting errors, and more importantly boosts exploration to escape from suboptimal solutions (for small sample sizes) by inflating variance level in an textitunconventional way. In theory, with appropriate variance inflation level, textttReBoot provably secures instance-dependent logarithmic regret in Gaussian multi-armed bandits. We evaluate the textttReBoot in different synthetic multi-armed bandits problems and observe that the textttReBoot performs better for unbounded rewards and more robustly than textttGiro citekveton2018garbage and textttPHE citekveton2019perturbed, with comparable computational efficiency to the Thompson sampling method.