Gaussian process bandits with adaptive discretization

DOI10.1214/18-EJS1497MaRDI QIDQ1711556zbMATH OpenOpenAlexWikidataFDO

Authors Shubhanshu Shekhar, Tara Javidi

Publication date 18 January 2019

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.01447, https://projecteuclid.org/euclid.ejs/1543892564

zbMATH Keywords

banditsBayesian optimizationGaussian processes

Mathematics Subject Classification ID

Gaussian processes (60G15) Bayesian problems; characterization of Bayes procedures (62C10) Bayesian inference (62F15) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: In this paper, the problem of maximizing a black-box function $f:mathcalXomathbbR$ is studied in the Bayesian framework with a Gaussian Process (GP) prior. In particular, a new algorithm for this problem is proposed, and high probability bounds on its simple and cumulative regret are established. The query point selection rule in most existing methods involves an exhaustive search over an increasingly fine sequence of uniform discretizations of $mathcalX$. The proposed algorithm, in contrast, adaptively refines $mathcalX$ which leads to a lower computational complexity, particularly when $mathcalX$ is a subset of a high dimensional Euclidean space. In addition to the computational gains, sufficient conditions are identified under which the regret bounds of the new algorithm improve upon the known results. Finally an extension of the algorithm to the case of contextual bandits is proposed, and high probability bounds on the contextual regret are presented.

Review text

Problem: a black-box function is needed to be maximized in the Bayesian framework with a Gaussian process prior. A very illustrative title is given for the paper: Gaussian process bandits with adaptive discretization. A very nice statistical description is given to it, namely: \begin{itemize}\item general approach, \item tree based algorithm, \item analysis of algorithm like assumptions on the covariance function, details of the algorithm, regret bounds.\end{itemize} Computational benefits of the adaptivity, improved bounds for Matérn kernels, regret under noiseless observations are described. This paper gives several alternatives to the extensions. This work explains the algorithm very detailed.

Recommendations

• Adaptive-treed bandits
• Convergence rates of efficient global optimization algorithms
• Gaussian process modelling of dependencies in multi-armed bandit problems
• scientific article; zbMATH DE number 6433488
• No-regret Bayesian optimization with unknown hyperparameters

Cites work

• X-armed bandits
• Chaining, interpolation, and convexity
• Contextual bandits with similarity information
• Convergence rates of efficient global optimization algorithms
• First Passage Time for a Particular Gaussian Process
• From bandits to Monte-Carlo tree search: the optimistic principle applied to optimization and planning
• Gaussian processes for machine learning.
• scientific article; zbMATH DE number 6433488 (Why is no real title available?)
• scientific article; zbMATH DE number 5485582 (Why is no real title available?)
• Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
• Learning to optimize via posterior sampling
• Multi-fidelity Gaussian process bandit optimisation
• Prediction, Learning, and Games
• Pure exploration in finitely-armed and continuous-armed bandits
• The multi-armed bandit problem with covariates

Cited in

(11)

• A PAC algorithm in relative precision for bandit problem with costly sampling
• High-dimensional Bayesian optimization with projections using quantile Gaussian processes
• Bayesian optimization with partially specified queries
• Gaussian process modelling of dependencies in multi-armed bandit problems
• No-regret Bayesian optimization with unknown hyperparameters
• Multi-fidelity Gaussian process bandit optimisation
• scientific article; zbMATH DE number 6433488 (Why is no real title available?)
• Optimization on Manifolds via Graph Gaussian Processes
• Contextual ranking and selection with Gaussian processes and optimal computing budget allocation
• Stochastic zeroth order descent with structured directions
• Adaptive-treed bandits

This page was built for publication: Gaussian process bandits with adaptive discretization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711556)