Adversarial Contextual Bandits Go Kernelized
This work addresses decision-making in complex, adversarial environments for machine learning researchers, representing an incremental extension of existing bandit theory.
The paper tackles the problem of online learning in adversarial linear contextual bandits by extending it to loss functions in a reproducing kernel Hilbert space, achieving near-optimal regret bounds such as $\widetilde{O}(KT^{ rac{1}{2}(1+ rac{1}{c})})$ for polynomial eigendecay and $\widetilde{O}(\sqrt{T})$ for exponential eigendecay.
We study a generalization of the problem of online learning in adversarial linear contextual bandits by incorporating loss functions that belong to a reproducing kernel Hilbert space, which allows for a more flexible modeling of complex decision-making scenarios. We propose a computationally efficient algorithm that makes use of a new optimistically biased estimator for the loss functions and achieves near-optimal regret guarantees under a variety of eigenvalue decay assumptions made on the underlying kernel. Specifically, under the assumption of polynomial eigendecay with exponent $c>1$, the regret is $\widetilde{O}(KT^{\frac{1}{2}(1+\frac{1}{c})})$, where $T$ denotes the number of rounds and $K$ the number of actions. Furthermore, when the eigendecay follows an exponential pattern, we achieve an even tighter regret bound of $\widetilde{O}(\sqrt{T})$. These rates match the lower bounds in all special cases where lower bounds are known at all, and match the best known upper bounds available for the more well-studied stochastic counterpart of our problem.