Exploration via linearly perturbed loss minimisation
This provides a simple, efficient exploration method for bandit problems, with incremental improvements over prior perturbation-based approaches.
The paper tackles the problem of exploration in structured stochastic bandits by introducing EVILL, a method using linearly perturbed loss minimisation, which matches Thompson-sampling performance in theory and practice and avoids inconsistency issues in non-linear cases.
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.