PaperlayerView exact revision on arXiv

Source-linked AI summary

A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning

Eric Brochu, Vlad M. Cora, Nando de Freitas

arXiv:1012.2599v1cs.LG

TL;DR

The paper addresses optimization when objective evaluations are expensive, noisy, derivative-free, or unavailable in closed form. It presents Bayesian optimization using priors, posteriors, and acquisition functions, then applies the framework to preference-based active user modeling and hierarchical reinforcement learning. The tutorial reports distinct sampling behavior across acquisition criteria and an image-search study where argmaxEI required fewer user clicks than competing algorithms.

  • Problem

    Many important objectives are costly or impossible to evaluate and lack known derivatives or convexity, making conventional optimization assumptions unsuitable.

  • Method

    The paper develops Bayesian optimization by combining prior beliefs and observations into a posterior, then selecting evaluations with acquisition functions that balance exploration and exploitation.

  • Results

    In an image-search user study, argmaxEI had a mean number of clicks less than half that of competing algorithms, while maximum variance performed little better than random.

  • Takeaways & Limitations

    The tutorial demonstrates Bayesian optimization extensions for preference-based active user modeling and hierarchical reinforcement learning, alongside a discussion of practical advantages and drawbacks.

  • Takeaways & Limitations

    Efficient performance depends critically on prior design, while weak or uncertain priors and exploration–exploitation choices remain difficult in practice.

Abstract

from arXiv · show

We present a tutorial on Bayesian optimization, a method of finding the maximum of expensive cost functions. Bayesian optimization employs the Bayesian technique of setting a prior over the objective function and combining it with evidence to get a posterior function. This permits a utility-based selection of the next observation to make on the objective function, which must take into account both exploration (sampling from areas of high uncertainty) and exploitation (sampling areas likely to offer improvement over the current best observation). We also present two detailed extensions of Bayesian optimization, with experiments---active user modelling with preferences, and hierarchical reinforcement learning---and a discussion of the pros and cons of Bayesian optimization based on our experiences.

1 Introduction

Bayesian optimization addresses black-box objectives that are expensive or impossible to evaluate by combining prior beliefs with observations and selecting samples through an exploration–exploitation trade-off. The tutorial develops the approach and extends it to preference-based active user modeling and hierarchical control.

  • Many learning problems violate classical optimization assumptions because objectives may be expensive or impossible to evaluate, with unknown derivatives and convexity.
  • Bayesian optimization is useful for expensive, noisy, derivative-free, and non-convex objectives when observations can be obtained at sampled inputs.
  • A prior over plausible objective functions is combined with observed data to form a posterior that represents updated beliefs about the unknown function.
  • An acquisition function chooses the next sample by trading off exploration of uncertain regions against exploitation of regions expected to have high objective values.
  • The tutorial covers Gaussian-process Bayesian optimization, covariance functions, acquisition functions, noise, history, preference galleries, hierarchical control, and practical pros and cons.

2 The Bayesian Optimization Approach

The Bayesian optimization approach targets global maximization of bounded black-box functions whose values may be noisy and whose derivatives or analytical forms are unavailable. It iteratively optimizes an acquisition function, evaluates the objective, updates the data, and revises the model.

  • The objective is treated as a bounded, global, black-box maximization problem without an analyzable expression or known derivatives.
  • Classical worst-case guarantees can require exponentially many samples in dimension, motivating the use of prior knowledge and evidence to guide efficient sampling.
  • Each iteration optimizes the acquisition function to choose x_t, samples y_t = f(x_t) + ε_t, augments the dataset, and updates the Gaussian process.
  • The framework assumes Gaussian measurement noise and may use Lipschitz continuity or bounded axis-aligned search spaces as simplifying conditions.
  • Bayesian optimization combines a prior with a likelihood to produce a posterior distribution over objective functions and defines an acquisition function as sampling utility.

2.1 Priors over functions

Gaussian-process priors represent uncertainty over objective functions through mean and covariance functions, then provide predictive distributions after observations are incorporated. Kernel choices determine how observations influence one another and thus encode prior structure.

  • The posterior can converge to the optimum under conditions on acquisition continuity and the decay of conditional variance near observations.
  • A Gaussian process is a distribution over functions specified by a mean function and covariance function, returning predictive means and variances at inputs.
  • With a zero-mean prior, sampled function values at selected inputs follow a multivariate normal distribution whose covariance is given by the kernel matrix.
  • The squared exponential kernel makes nearby points strongly influential and distant points weakly influential, supporting smoothness and convergence assumptions.
  • After observations, Gaussian-process properties yield a predictive distribution whose sufficient statistics are the posterior mean and standard deviation.

2.2 Choice of covariance functions

Covariance functions determine the smoothness and relevance structure of Gaussian-process models. The tutorial discusses squared exponential and Matérn kernels, hyperparameters, automatic relevance determination, and model-selection requirements.

  • The covariance function is crucial because it determines the smoothness properties of functions sampled from the Gaussian process.
  • The squared exponential kernel is limited because divergences in all features affect covariance equally.
  • An isotropic hyperparameter θ controls kernel width, while ARD hyperparameters can remove irrelevant input dimensions when their values are small.
  • The Matérn kernel adds a smoothness parameter ς, reducing to the squared exponential kernel as ς → ∞ and to the unsquared exponential kernel at ς = 0.5.
  • Kernel selection typically combines engineering judgment with hierarchical Bayesian model selection or cross-validation, which require representative data.

2.3 Acquisition Functions for Bayesian Optimization

Acquisition functions guide Bayesian optimization by assigning utility to candidate evaluations, balancing predicted objective values against uncertainty. Probability of improvement, expected improvement, and upper confidence bound make different exploration–exploitation choices and therefore produce distinct sampling behavior.

  • Acquisition functions guide the search by favoring points with high predicted objective values, high uncertainty, or both.They determine the next location to sample and encode the exploration–exploitation trade-off.
  • Improvement-based acquisition functions: Probability of improvement selects points likely to exceed the incumbent, but its trade-off parameter ξ controls how locally or globally it searches.Small ξ can encourage local search, whereas larger ξ favors broader exploration.
  • Improvement-based acquisition functions: Expected improvement scores candidate points by the expected magnitude of improvement over the incumbent, combining high surrogate mean with high surrogate variance.The analytic expression uses the Gaussian-process predictive mean and variance, with ξ providing an additional exploration–exploitation control.
  • Confidence bound criteria: Probability of improvement, expected improvement, and upper confidence bound choose different maxima from the same Gaussian-process posterior.The figures illustrate that the acquisition criterion changes which candidate is selected for evaluation.
  • Confidence bound criteria: With ν = 1 and the specified τ_t schedule, GP-UCB has cumulative regret per iteration tending to zero with high probability.This is the paper’s stated no-regret guarantee as T approaches infinity.
  • Confidence bound criteria: Upper confidence bound methods can continue exploring uncertain regions that greedy expected improvement largely ignores.In the cited example, greedy EI ignores the region around x = 0.4, while GP-UCB continues to explore.

2.4 Noise

The tutorial extends Bayesian optimization to noisy observations by incorporating Gaussian noise into the GP model and adapting acquisition-function incumbents. These changes prevent optimization from relying on unreliable individual samples.

  • Noise model: Noisy observations are modeled as transformations of the latent objective rather than direct noise-free evaluations.The simplest case adds Gaussian noise ε ∼ N(0, σ^2_noise) to f(x).
  • Noise model: Additive Gaussian noise is incorporated into the observation distribution by replacing the kernel with a noise-adjusted kernel.Because the noise has zero mean, the kernel modification captures its effect on noisy observations.
  • Inference: The noisy GP produces a predictive distribution and sufficient statistics for subsequent Bayesian optimization decisions.These quantities support inference after accounting for observation noise.
  • Acquisition functions: In noisy PI and EI, the incumbent is the sample point with the highest expected value rather than the point with the best observed sample.This replaces direct comparison of potentially unreliable observations with comparison of their posterior distributions.
  • Acquisition functions: Using a distribution-based incumbent avoids maximizing improvement over an unreliable sample, while resampling can further improve incumbent estimates.The tutorial calls this resampling process intensification and also notes that nonstationary noise models are possible.

2.5 A brief history of Bayesian optimization

Bayesian optimization developed through several related lines of work, from early Wiener-process methods and expected improvement to Gaussian-process optimization and convergence analyses. The field also overlaps historically with kriging and experimental design.

  • Early Bayesian optimization: Kushner’s early one-dimensional method used Wiener processes and probability of improvement, with a parameter controlling global versus local optimization.This parameter reflects the exploration–exploitation trade-off.
  • Early Bayesian optimization: Močkus and colleagues introduced a multidimensional method using linear combinations of Wiener fields and described posterior expected improvement.Expected improvement later became widely adopted in Bayesian optimization.
  • Related approaches: Kriging emerged as a related approach for interpolating random fields with a linear predictor and Gaussian-process error model.Its development began in geostatistics and environmental science.
  • Modern developments: Gaussian-process Bayesian optimization has been applied to derivative-free optimization and experimental design under the name Efficient Global Optimization, or EGO.EGO is presented as a more recent application of the Bayesian optimization framework.
  • Theory: Consistency and convergence results have been established for several Bayesian optimization variants in one and multiple dimensions.The cited results include one-dimensional consistency, higher-dimensional simplicial partitioning, and multivariate Gaussian-process convergence.

2.6 Kriging

Kriging models spatially correlated errors with Gaussian processes and combines regression with a stochastic residual model. Bayesian optimization and kriging are closely related but typically differ in how their models are fitted.

  • Kriging model: Kriging interpolates a random field using a linear predictor whose errors are typically modeled as dependent Gaussian-process residuals.This contrasts with common independent-residual assumptions in statistical and machine-learning models.
  • Kriging model: Kriging combines a regression model with a stochastic model for residual errors that vary with the input location.The residual process is represented as ε(x) ∼ N(0, σ^2(x)).
  • Kriging variants: Simple, ordinary, and universal kriging differ in whether the regression component is zero, constant unknown, or polynomial.Universal kriging uses a polynomial basis with coefficients β.
  • Relationship to Bayesian optimization: Kriging and Bayesian optimization are closely related, but Bayesian optimization usually fits models by maximum likelihood whereas kriging usually fits through a variogram.Kriging fitting may use least squares, related numerical methods, or expert inspection of variogram plots.

2.7 Experimental design

Experimental design selects experimental conditions to learn or optimize a model, traditionally using fixed designs but also supporting sequential approaches. Bayesian optimization connects to this area through kriging-based EGO and expected improvement.

  • Kriging-based design: DACE uses kriging for experimental design, with the goal of finding design points that optimize a chosen criterion.Its residual model is a noise-free Gaussian process and its regression model is a best linear unbiased predictor.
  • Kriging-based design: EGO combines the DACE model with sequential expected improvement and has been extended particularly to constrained optimization.Jones et al. introduced EGO as a refinement of SPACE.
  • Classical experimental design: Classical experimental design seeks parameters ζ of a function g_ζ from noisy outputs observed under experimental conditions x_i.The setup commonly assumes that g_ζ is linear.
  • Classical experimental design: A design matrix X records experimental inputs, while parameter-estimate variance and predictions quantify uncertainty and model output.The rows of X are the inputs x_1:t.
  • Design criteria: A-optimality, D-optimality, and E-optimality minimize the trace, determinant, or maximum eigenvalue of (X^T X)^−1, respectively.These criteria optimize different characteristics of the inverse moment matrix.
  • Adaptive design: Experimental design is usually non-adaptive, although sequential design is an active subfield in which decisions can be updated over time.The entire classical experiment is typically designed before data collection begins.

2.8 Active learning

Active learning adaptively selects candidates using a model updated with acquired data, often relying on human oracles and uncertainty or informativeness criteria. Its relationship to Bayesian optimization is close, while pool-based candidate selection and continuous-domain optimization distinguish common uses.

  • Active learning sequentially selects candidates for labelling, incorporates each new label into its model, and repeats the process.
  • Human beings frequently serve as the oracle that provides active-learning labels, as in interactive Bayesian optimization.
  • Active learning usually selects from a finite pool, whereas experimental design and optimization typically operate over continuous domains.
  • Active learning commonly learns classification or regression models while selecting candidates by informativeness or uncertainty criteria.
  • Gaussian-process active-learning examples include image categorization, preference ranking, and sensor placement using entropy or mutual information criteria.
  • Uncertainty sampling selects the point with maximum uncertainty, while GP posterior variance can be independent of the observations.

2.9 Applications

Prior work applies Bayesian optimization to robotics, controller learning, hierarchical policies, algorithm tuning, and sensor placement. These applications use sequential evaluations to optimize performance, policies, parameters, or prediction error in diverse settings.

  • Bayesian optimization learned Sony AIBO gait parameters for maximum velocity and outperformed earlier techniques with drastically fewer evaluations.
  • Bayesian optimization learned neural-network controller weights for balancing two vertical poles with different weights and lengths on a moving cart.
  • A hierarchical policy for simulated driving was learned by using vehicle controls as inputs and course fitness as the response.
  • Bayesian optimization was applied to robot path planning to minimize uncertainty about location, heading, and environmental navigation landmarks.
  • Sequential Bayesian optimization methods were developed for automatically tuning algorithm parameters.
  • Sensor-network optimization selected locations for heterogeneous sensors while minimizing the root mean squared error of network predictions.

3 Bayesian Optimization for Preference Galleries

Preference galleries adapt Bayesian optimization to human comparisons, using binary choices to infer a Gaussian-process utility model rather than requiring numerical ratings. The resulting preference model combines observed comparisons with prior assumptions about smoothness and noise, and supports efficient gallery search.

  • 3 Bayesian Optimization for Preference Galleries: Human preferences can be more accurate than ratings because people compare options more robustly than they assign consistent numerical values.Numerical ratings vary across users and over time because of drift and anchoring, whereas pairwise comparisons impose less cognitive burden.
  • 3.1 Probit model for binary observations: Binary preference observations are used to infer a latent valuation function through a probit model.
  • 3.1 Probit model for binary observations: Preference data consist of ranked pairs, where r ≻ c records that the user prefers item r to item c.
  • 3.1 Probit model for binary observations: The model assigns a nonparametric Gaussian-process prior to the unknown mean valuation over the observed training points.
  • 3.1 Probit model for binary observations: The posterior over the latent utility function is approximated with a Laplace approximation centered on its MAP estimate.
  • 3.1 Probit model for binary observations: Figure 8 maps preference relations in a table to an inferred Gaussian process that incorporates preference evidence and priors on smoothness and noise.
  • 3.2.1 User Study: In the user study, expected improvement required fewer clicks on average than competing algorithms, while maximum variance performed little better than random.The study measures n, the number of user clicks needed to find the target image.

4 Bayesian Optimization for Hierarchical Control

The paper integrates Bayesian active exploration with hierarchical reinforcement learning to speed learning in hybrid discrete and continuous control tasks. The approach uses task decomposition, state abstraction, and Bayesian optimization to focus expensive value-function evaluations, while retaining limits from hierarchy design and recursive optimality.

  • Hierarchical Reinforcement Learning: Hierarchical reinforcement learning structures repeated decision making into temporally extended tasks and subtasks over subsets of the world state.Each task is modeled as an SMDP, supporting temporal and state abstraction.
  • Hierarchical Reinforcement Learning: The paper integrates MAXQ with Bayesian active exploration to address slow exploration in HRL across discrete and continuous state and action spaces.The integration is demonstrated in an extended Taxi domain running in a 3D driving simulator.
  • Hierarchical Reinforcement Learning: MAXQ tasks combine subtasks, termination predicates, state abstraction functions, and learned policies, enabling discrete navigation to be integrated with continuous vehicle control.State abstraction filters irrelevant states when values are looked up and updated.
  • Hierarchical Reinforcement Learning: Recursive optimality makes each subtask locally optimal given its descendants, but can produce a suboptimal overall policy because later task effects are ignored.MAXQ can selectively enable hierarchical optimality by including relevant state features as task parameters.
  • Bayesian Optimization for Hierarchical Policies: Bayesian optimization improves direct policy search by avoiding derivatives, reducing susceptibility to local minima, and minimizing expensive value-function evaluations.Its acquisition mechanism balances exploration of uncertain regions with exploitation of promising values.
  • Bayesian Optimization for Hierarchical Policies: The continuous Drive policy uses 15 trained parameters to generate steer and throttle values, and became usable after approximately 50 additional samples beyond 30 initial Latin hypercube samples.The trajectory value is based on negative accumulated position and velocity error, with policy evaluations averaged over 10 episodes.
  • Simulations: In full hierarchical experiments, the fastest learner, VTM GP with ϵ = 0.2, drove for approximately 4 hours of real time before finding a good approximation of the Navigate value function.The comparison averaged results from 10 runs of RAR, MAXQ, and a Navigate-only value-learning variant.

5 Discussion and advice to practitioners

Bayesian optimization supports machine-learning problems where acquiring labels is costly, but its practical effectiveness depends on prior design, dimensionality, acquisition strategy, and application-specific extensions. The authors illustrate these considerations through active policy optimization, parameterized reinforcement-learning comparisons, and a discussion of unresolved limitations.

  • Bayesian optimization provides an efficient Bayesian framework for solving learning problems in which acquiring labels is the main difficulty.
  • The active policy optimizer searches 15 policy parameters while comparing Gaussian-process kernel sizes, using Expected Improvement and 30 shared Latin hypercube initialization samples.The plot averages 20 experimental runs.
  • Parameterized VTM is evaluated against Recursive Average Reward and MAXQ in path-learning experiments.
  • Kernel size controls how broadly a Gaussian-process observation influences the response surface: smaller values narrow its footprint, while larger values interpolate more widely.
  • Prior design is critical, yet limited objective-function knowledge forces a choice between uncertain strong assumptions and weak priors; acquisition functions also face exploration–exploitation trade-offs.Excessive exploration can delay improvement, whereas excessive exploitation can produce local maximization.
  • Higher dimensionality requires more samples and additional parameter or hyperparameter tuning, motivating automatic feature selection or independent per-dimension optimization.
  • The acquisition function is myopic and selects only one sample per iteration, limiting lookahead and batch-selection capabilities for reinforcement learning and fixed-observation budgets.
  • Application-specific extensions must accommodate adaptive, iterative optimization, and their difficulty can range from trivial to impossible.
Loading 1012.2599v1…