Efficient Kernel UCB for Contextual Bandits
In this paper, we tackle the computational efficiency of kernelized UCB algorithms in contextual bandits. While standard methods require a O(CT^3) complexity where T is the horizon and the constant C is related to optimizing the UCB rule, we propose an efficient contextual algorithm for large-scale problems. Specifically, our method relies on incremental Nystrom approximations of the joint kernel embedding of contexts and actions. This allows us to achieve a complexity of O(CTm^2) where m is the number of Nystrom points. To recover the same regret as the standard kernelized UCB algorithm, m needs to be of order of the effective dimension of the problem, which is at most O(\sqrt(T)) and nearly constant in some cases.
Code (1)
Tasks
Computational EfficiencyMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Finite-Time Analysis of Kernelised Contextual Bandits
We tackle the problem of online reward maximisation over a large finite set of actions described by their contexts. We focus on the case when the number of actions is too big to sample all of them even once. However we a…
Multi-Armed BanditsProvably and Practically Efficient Neural Contextual Bandits
We consider the neural contextual bandit problem. In contrast to the existing work which primarily focuses on ReLU neural nets, we consider a general set of smooth activation functions. Under this more general setting, (…
Multi-Armed BanditsKernel weighted importance sampling for off-policy evaluation in contextual bandits
This article presents a novel estimator for performing off-policy evaluation using only offline data for contextual bandits. The proposed estimator, Kernel-WIS is demonstrated to be asymptotically consistent and to empir…
Communication Efficient Distributed Learning for Kernelized Contextual Bandits
We tackle the communication efficiency challenge of learning kernelized contextual bandits in a distributed setting. Despite the recent advances in communication-efficient distributed bandit learning, existing solutions …
Multi-Armed BanditsBandits for Learning to Explain from Explanations
We introduce Explearn, an online algorithm that learns to jointly output predictions and explanations for those predictions. Explearn leverages Gaussian Processes (GP)-based contextual bandits. This brings two key benefi…
Gaussian ProcessesMulti-Armed Bandits