Residual Bootstrap Exploration for Bandit Algorithms
This work addresses the challenge of efficient exploration in bandit algorithms, which is crucial for applications like online advertising and recommendation systems, and represents an incremental improvement over prior perturbation-based methods.
The paper tackles the problem of exploration in bandit algorithms by proposing a novel perturbation-based method called residual bootstrap exploration (ReBoot), which injects data-driven randomness to escape suboptimal solutions and achieves instance-dependent logarithmic regret in Gaussian multi-armed bandits, performing better for unbounded rewards and more robustly than existing methods like Giro and PHE.
In this paper, we propose a novel perturbation-based exploration method in bandit algorithms with bounded or unbounded rewards, called residual bootstrap exploration (\texttt{ReBoot}). The \texttt{ReBoot} 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 \textit{unconventional} way. In theory, with appropriate variance inflation level, \texttt{ReBoot} provably secures instance-dependent logarithmic regret in Gaussian multi-armed bandits. We evaluate the \texttt{ReBoot} in different synthetic multi-armed bandits problems and observe that the \texttt{ReBoot} performs better for unbounded rewards and more robustly than \texttt{Giro} \cite{kveton2018garbage} and \texttt{PHE} \cite{kveton2019perturbed}, with comparable computational efficiency to the Thompson sampling method.