Residual Bootstrap Exploration for Bandit Algorithms

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.