Neural Contextual Bandits without Regret

Abstract

Contextual bandits are a rich model for sequential decision making given side information, with important applications, e.g., in recommender systems. We propose novel algorithms for contextual bandits harnessing neural networks to approximate the unknown reward function. We resolve the open problem of proving sublinear regret bounds in this setting for general context sequences, considering both fully-connected and convolutional networks. To this end, we first analyze NTK-UCB, a kernelized bandit optimization algorithm employing the Neural Tangent Kernel (NTK), and bound its regret in terms of the NTK maximum information gain ${\gamma }_T$, a complexity parameter capturing the difficulty of learning. Our bounds on ${\gamma }_T$ for the NTK may be of independent interest. We then introduce our neural network based algorithm NN-UCB, and show that its regret closely tracks that of NTK-UCB. Under broad non-parametric assumptions about the reward function, our approach converges to the optimal policy at a $\tilde{\mathcal{O}}(T^{-1/2d})$ rate, where $d$ is the dimension of the context.

arXiv comment37 pages, 6 figures

References in corpus (17)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• On Exact Computation with an Infinitely Wide Neural Net
• On Lazy Training in Differentiable Programming
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Finite-Time Analysis of Kernelised Contextual Bandits
• Neural Thompson Sampling
• Distributionally Robust Bayesian Optimization
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Learning with invariances in random features and kernel models
• Stochastic Bandits with Context Distributions
• Deep Neural Linear Bandits: Overcoming Catastrophic Forgetting through Likelihood Matching
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• Corruption-Tolerant Gaussian Process Bandit Optimization
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Contextual Games: Multi-Agent Learning with Side Information
• Approximation and Learning with Deep Convolutional Models: a Kernel Perspective