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 $\tilde{O}(d\sqrt{n\log 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.

arXiv commentProceedings of the 23rd International Conference on Artificial Intelligence and Statistic

References in corpus (8)

• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Further Optimal Regret Bounds for Thompson Sampling
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems
• Spectral bandits for smooth graph functions
• Ensemble Sampling
• Customized Nonlinear Bandits for Online Response Selection in Neural Conversation Models
• On the Performance of Thompson Sampling on Logistic Bandits