Articlegreen2012

Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting

Niranjan Srinivas · Andreas Krause · Sham M. Kakade · Matthias Seeger

2,098 citations0/0 files storedIEEE Transactions on Information Theory

No readable copy stored yet — this record is metadata only.

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Machine Learning and Algorithms

Abstract

Many applications require optimizing an unknown, noisy function that is expensive to evaluate. We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low norm in a reproducing kernel Hilbert space. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze an intuitive Gaussian process upper confidence bound (GP-UCB) algorithm, and bound its cumulative regret in terms of maximal in- formation gain, establishing a novel connection between GP optimization and experimental design. Moreover, by bounding the latter in terms of operator spectra, we obtain explicit sublinear regret bounds for many commonly used covariance functions. In some important cases, our bounds have surprisingly weak dependence on the dimensionality. In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches.

Citations in this library

Stored only when both papers are in the corpus — 2,098 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem 1952Some aspects of the sequential design of experiments 2010A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning 1995Bayesian Experimental Design: A Review

Cited by

2010A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning 2012Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems 2020Bandit Algorithms 2019Introduction to Multi-Armed Bandits 2015Scalable Bayesian Optimization Using Deep Neural Networks 2015Simulation optimization: a review of algorithms and applications 2020Bayesian Optimization for Adaptive Experimental Design: A Review 2014Learning to Optimize via Posterior Sampling

Imported from OpenAlex (CC0) — nothing here is generated.