Neural Contextual Bandits without Regret
METADATA ONLY
Loading...
Author / Producer
Date
2022
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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 γT, a complexity parameter capturing the difficulty of learning. Our bounds on γ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 O~(T−1/2d) rate, where d is the dimension of the context.
Permanent link
Publication status
published
Book title
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics
Journal / series
Volume
151
Pages / Article No.
240 - 278
Publisher
PMLR
Event
25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03908 - Krause, Andreas / Krause, Andreas
Notes
Funding
815943 - Reliable Data-Driven Decision Making in Cyber-Physical Systems (EC)