GP-UCB (Gaussian Process Upper Confidence Bound)#
GP-UCB is a sequential optimization method for expensive-to-evaluate objective functions, combining a surrogate model built from Gaussian Process (GP) regression with the Upper Confidence Bound (UCB) acquisition function, a linear combination of the predictive mean and predictive standard deviation.
Overview#
GP-UCB extends the UCB policy from the multi-armed bandit problem to GP optimization. In the bandit problem, it is known that continually choosing the arm with the highest upper confidence bound on its reward automatically balances exploration and exploitation.
GP-UCB applies this idea to GP regression over a continuous space, evaluating next the point that maximizes the upper confidence bound \(\mu(x) + \sqrt{\beta_t}\,\sigma(x)\) of a candidate point \(x\). A point with a high predictive mean \(\mu(x)\) corresponds to exploitation, while a point with a large predictive standard deviation \(\sigma(x)\) corresponds to exploration, and \(\beta_t\) controls the relative weight between these two terms.
The theoretical core of this method lies in choosing \(\beta_t\) not as a fixed value but as a function of the iteration count \(t\). Increasing \(\beta_t\) according to a specific logarithmic schedule derived from an upper bound on the information gain yields a sublinear upper bound on the cumulative regret [25]. The concrete procedure is shown in the pseudocode below.
Pseudocode#
Algorithm 2 (GP-UCB)
Inputs objective function \(f\) (maximized as a reward), search domain \(D\), GP prior \(\mu_0=0,\sigma_0,k\), confidence parameter sequence \(\beta_t\) Output best solution \(x^*\)
Set \(t=1\)
Choose the point \(x_t = \arg\max_{x \in D} \mu_{t-1}(x) + \sqrt{\beta_t}\,\sigma_{t-1}(x)\) that maximizes the upper confidence bound
Observe \(y_t = f(x_t) + \epsilon_t\)
Perform a Bayesian update with the observation \(y_t\), obtaining the posterior mean \(\mu_t(x)\) and posterior standard deviation \(\sigma_t(x)\)
Increment \(t\) by 1 and return to step 2 until the evaluation budget is reached
Flowchart#
flowchart TD
INIT["Initializer<br/>Sample initial population<br/>via LHS etc. → true evaluation"] --> ASK
subgraph GEN["One generation (IndividualBasedStrategy.step)"]
direction TB
ASK["GA.ask()<br/>Generate candidates"] --> SCORE["SurrogateManager<br/>Fit GP (L4)<br/>→ Score with LCB (L2)"]
SCORE --> SORT["Select top<br/>evaluation_ratio fraction by LCB<br/>(approximates argmax UCB)"]
SORT --> EVAL["True evaluation →<br/>add to archive<br/>(L3)"]
EVAL --> TELL["GA.tell()<br/>Update population"]
end
GEN --> TERM{"Evaluation budget<br/>reached?"}
TERM -- "Not yet (L5)" --> ASK
TERM -- "Reached" --> RESULT(["Best solution x*"])
Configuration in saealib#
The cited GP-UCB formulation is expressed as maximizing a reward, whereas LowerConfidenceBound assumes minimization and computes \(\mathrm{LCB}(x) = \mu(x) - \kappa\sigma(x)\), returning it with its sign flipped so that score comparisons line up with saealib’s other acquisition functions (to match saealib’s overall convention that “higher score is better”).
Converting \(\mu(x)\) into a minimization space and then flipping the sign gives \(-(\mu(x) - \kappa\sigma(x)) = -\mu(x) + \kappa\sigma(x)\), which matches the direction of the upper confidence bound \(\mu(x) + \kappa\sigma(x)\) in the maximization space.
Therefore, LowerConfidenceBound’s kappa corresponds to the paper’s \(\sqrt{\beta_t}\).
Role |
saealib implementation |
Corresponding step |
|---|---|---|
Search algorithm |
|
L2 |
Surrogate model |
|
L4 |
Acquisition function |
|
L2 |
Surrogate management |
|
L2, L4 |
Evaluation strategy |
|
L2-3 |
import numpy as np
from saealib import (
GA,
Optimizer,
Problem,
IndividualBasedStrategy,
SklearnGPRSurrogate,
LowerConfidenceBound,
)
from saealib.operators.crossover import CrossoverBLXAlpha
from saealib.operators.mutation import MutationUniform
from saealib.operators.selection import SequentialSelection, TruncationSelection
from saealib.surrogate import GlobalSurrogateManager
from saealib.termination import Termination, max_fe
def sphere(x: np.ndarray) -> float:
return np.sum(x**2)
problem = Problem(sphere, dim=5, lb=[-5] * 5, ub=[5] * 5, n_obj=1, direction=[-1])
algorithm = GA(
CrossoverBLXAlpha(prob=0.7, alpha=0.4),
MutationUniform(prob_var=0.3),
SequentialSelection(),
TruncationSelection(),
)
surrogate_manager = GlobalSurrogateManager(SklearnGPRSurrogate())
strategy = IndividualBasedStrategy(evaluation_ratio=0.2)
opt = (
Optimizer(problem)
.set_algorithm(algorithm)
.set_surrogate_manager(surrogate_manager)
.set_acquisition(LowerConfidenceBound(kappa=2.0))
.set_strategy(strategy)
.set_termination(Termination(max_fe(200)))
)
ctx = opt.run()
Differences from the source#
The original GP-UCB procedure finds the UCB maximizer at every iteration. saealib approximates this argmax UCB by selecting the top UCB candidates from the pool GA generates; IndividualBasedStrategy.evaluation_ratio lets several of the selected candidates receive true evaluation together.
For a finite set \(D\), the original method chooses the following \(\beta_t\), increasing logarithmically in the round index \(t\), to obtain a theoretical upper bound on cumulative regret:
The paper also reports that cross-validating a 1/5 scale factor on this schedule performs better in practice, since the theoretical schedule as-is is often too exploratory.
saealib’s default (kappa=2.0, fixed regardless of \(t\)) does not follow this schedule and carries no such guarantee.
Parameters and variants#
κ (exploration–exploitation trade-off): Adjusted via LowerConfidenceBound(kappa=...). The default is 2.0.
β_t schedule: Pass beta_schedule=gp_ucb_beta_schedule(domain_size, delta) to reproduce the \(\beta_t\) formula from “Differences from the source” above instead of a fixed kappa; domain_size is the cardinality \(|D|\) of a finite decision set, not a discretization-count proxy for saealib’s continuous search space (see below).
t = ctx.decision_count + 1 – the number of genuinely new evaluation plans the runtime has confirmed so far (synchronous or async), plus one for the decision about to be made.
One confirmed plan is one decision regardless of how many candidates it evaluates, so under the GA + evaluation_ratio configuration in this page’s own example, t is not the paper’s per-observation round index whenever evaluation_ratio selects more than one candidate per generation.
t matches the paper’s round index only when every confirmed plan evaluates exactly one candidate (synchronous execution, one true evaluation per decision) – but a matching t alone does not reproduce the cited regret bound.
Theorem 1 assumes exhaustively optimizing \(\mu_{t-1}(x) + \sqrt{\beta_t}\,\sigma_{t-1}(x)\) over an actual finite set \(D\); saealib’s GA-generated candidate pool only approximates this argmax over a resampled subset each generation, and passing an integer to gp_ucb_beta_schedule(domain_size=...) does not turn the continuous search space into that finite \(D\) – it only substitutes a number into the formula.
Reproducing the theorem’s guarantee additionally requires a component that optimizes exhaustively over a literal finite \(D\) (not part of saealib’s built-in GA/PSO algorithms) and a GP model matching the paper’s noise and kernel assumptions; saealib does not ship such a component.
The table below therefore describes only how t and kappa behave under each setting, not whether the cited regret bound holds.
Setting |
|
|
|---|---|---|
|
fixed |
n/a – no schedule, no regret guarantee at all |
|
\(\sqrt{\beta_t}\), per the schedule above |
undercounts observations |
|
\(\sqrt{\beta_t}\), per the schedule above |
matches |