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

Gaussian processesBayesian optimizationbandits

Mathematics Subject Classification ID

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

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.

Recommendations

• Adaptive-treed bandits
• Convergence rates of efficient global optimization algorithms
• Gaussian process modelling of dependencies in multi-armed bandit problems
• Publication:5249599
• No-regret Bayesian optimization with unknown hyperparameters

Cites work

• scientific article; zbMATH DE number 6433488 (Why is no real title available?)
• scientific article; zbMATH DE number 5485582 (Why is no real title available?)
• 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.
• 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
• \(X\)-armed bandits

Cited in

(11)

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

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)