Adversarial Contextual Bandits Go Kernelized

2023/10/02 by Neu, Gergely, Olkhovskaya, Julia, Vakili, Sattar · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2310.01609

Abstract

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 \widetildeO(KT^{(1)/(2)(1+(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 \widetildeO(√(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.

Cited by

• Differential Privacy in Kernelized Contextual Bandits via Random Projections

Related

• Online learning with kernel losses
• Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits
• An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs