On Kernelized Multi-armed Bandits

Abstract

We consider the stochastic bandit problem with a continuous set of arms, with the expected reward function over the arms assumed to be fixed but unknown. We provide two new Gaussian process-based algorithms for continuous bandit optimization-Improved GP-UCB (IGP-UCB) and GP-Thomson sampling (GP-TS), and derive corresponding regret bounds. Specifically, the bounds hold when the expected reward function belongs to the reproducing kernel Hilbert space (RKHS) that naturally corresponds to a Gaussian process kernel used as input by the algorithms. Along the way, we derive a new self-normalized concentration inequality for vector- valued martingales of arbitrary, possibly infinite, dimension. Finally, experimental evaluation and comparisons to existing algorithms on synthetic and real-world environments are carried out that highlight the favorable gains of the proposed strategies in many cases.

References in corpus (4)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Multi-Armed Bandits in Metric Spaces
• Exploiting correlation and budget constraints in Bayesian multi-armed bandit optimization

Cited by in corpus (16)

• Online Learning: A Comprehensive Survey
• Is Pessimism Provably Efficient for Offline RL?
• Asynchronous Parallel Bayesian Optimisation via Thompson Sampling
• Safety-Guided Deep Reinforcement Learning via Online Gaussian Process Estimation
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Simple Regret Minimization for Contextual Bandits
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Distributed Bayesian Online Learning for Cooperative Manipulation
• Local Differential Privacy for Bayesian Optimization
• Rapidly Personalizing Mobile Health Treatment Policies with Limited Data
• Zeroth Order Non-convex optimization with Dueling-Choice Bandits
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits
• Weighted Gaussian Process Bandits for Non-stationary Environments
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization
• No-Regret Algorithms for Time-Varying Bayesian Optimization
• Neural Active Learning with Performance Guarantees