Perturbed-History Exploration in Stochastic Linear Bandits
This work addresses regret minimization in bandit problems, which is incremental as it builds on existing linear bandit methods with a novel exploration technique.
The authors tackled the problem of cumulative regret minimization in stochastic linear bandits by proposing a new algorithm called LinPHE, which uses perturbed history exploration and achieved a gap-free regret bound of $ ilde{O}(d \sqrt{n})$.
We propose a new online algorithm for cumulative regret minimization in a stochastic linear bandit. The algorithm pulls the arm with the highest estimated reward in a linear model trained on its perturbed history. Therefore, we call it perturbed-history exploration in a linear bandit (LinPHE). The perturbed history is a mixture of observed rewards and randomly generated i.i.d. pseudo-rewards. We derive a $\tilde{O}(d \sqrt{n})$ gap-free bound on the $n$-round regret of LinPHE, where $d$ is the number of features. The key steps in our analysis are new concentration and anti-concentration bounds on the weighted sum of Bernoulli random variables. To show the generality of our design, we generalize LinPHE to a logistic model. We evaluate our algorithms empirically and show that they are practical.