Randomized Exploration in Generalized Linear Bandits

Abstract

We study two randomized algorithms for generalized linear bandits. The first, GLM-TSL, samples a generalized linear model (GLM) from the Laplace approximation to the posterior distribution. The second, GLM-FPL, fits a GLM to a randomly perturbed history of past rewards. We analyze both algorithms and derive 𝑂̃ (𝑑𝑛log𝐾‾‾‾‾‾‾‾√)O~(dnlog⁡K) upper bounds on their 𝑛n-round regret, where 𝑑d is the number of features and 𝐾K is the number of arms. The former improves on prior work while the latter is the first for Gaussian noise perturbations in non-linear models. We empirically evaluate both GLM-TSL and GLM-FPL in logistic bandits, and apply GLM-FPL to neural network bandits. Our work showcases the role of randomization, beyond posterior sampling, in exploration.