Perturbed-History Exploration in Stochastic Linear Bandits

Abstract

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.

Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence

References in corpus (5)

• Further Optimal Regret Bounds for Thompson Sampling
• Bootstrapped Thompson Sampling and Deep Exploration
• Spectral bandits for smooth graph functions
• Thompson sampling with the online bootstrap
• Customized Nonlinear Bandits for Online Response Selection in Neural Conversation Models

Cited by in corpus (4)

• Stochastic Bandits with Context Distributions
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Randomized Exploration for Non-Stationary Stochastic Linear Bandits
• CORe: Capitalizing On Rewards in Bandit Exploration