On Kernelized Multi-armed Bandits

By Sayak Ray Chowdhury, Aditya Gopalan. 2017

581 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Safe Model-based Reinforcement Learning with Stability Guarantees (2017, methodology): “From [34, Theorem 2] it follows that | f ( x , u , i ) − µ n 1 ( x , u , i ) ≤ β n σ n ( x , u , i ) holds with probability at least 1 − δ for all 1 ≤ i ≤ q . can over − | Following Remark 1, we model the multi-output function as a single-output function an extended parameter space.”
Parallelised Bayesian Optimisation via Thompson Sampling (2018, background): “TS has been explored for sequential BO [4, 39] and some recent theoretical advances have characterised the performance of TS in sequential settings [3, 7, 27, 35, 36].”
Online Learning: A Comprehensive Survey (2018, background): “Among these studies, one niche sub-topic is continuum-armed bandits (Kleinberg, 2005a; Chowdhury and Gopalan, 2017), where the arms lie in some Euclidean (or metric) space and their mean-reward is a deterministic and smooth (e.g., Lipschitz) function of the arms, a.k.a. Lipschitz Bandit (Magureanu…”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “(Valko et al., 2013; Chowdhury and Gopalan, 2017), who studied the regret bound when the features of each arm lies in some reproducing kernel Hilbert space.”
Constrained Efficient Global Optimization of Expensive Black-box Functions (2022, methodology): “This problem, when formulated as a (kernelized) multi-armed bandit problem, is widely studied in the literatures (Audibert et al., 2010; Srini-vas et al., 2012; Soare et al., 2014; Chowdhury & Gopalan, 2017a; Amani et al., 2019; Zhou & Ji, 2022).”
Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, background): “Some recent theoretical advances have characterised the performance of TS in sequential settings [3, 6, 31, 32].”
Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics (2016, unknown): “Directly follows from Chowdhury and Gopalan (2017). The only difference is that we obtain |I| measurements at every iteration, which causes the information capacity γ to grow at a faster rate.”
Towards Stable Test-Time Adaptation in Dynamic Wild World (2023, background): “OL (Hoi et al., 2021; Chowdhury & Gopalan, 2017; Zhao et al., 2011) conducts model learning from a sequence of data samples one by one at a time, which is common in many real-world applications ( e.g. , social web recommendation).”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “…function for promoting exploration in online RL (Jaksch et al., 2010; Abbasi-Yadkori et al., 2011; Russo and Van Roy, 2013; Osband and Van Roy, 2014; Chowdhury and Gopalan, 2017; Azar et al., 2017; Jin et al., 2018; 2020; Cai et al., 2020; Yang et al., 2020b; Ayoub et al., 2020; Wang et al.,…”