Pareto-Optimal Anytime Algorithms via Bayesian Racing

Jonathan Wurth; Helena Stegherr; Neele Kemper; Michael Heider; Jörg Hähner

cs.NEMar 9, 2026

Pareto-Optimal Anytime Algorithms via Bayesian Racing

Authors: Jonathan Wurth, Helena Stegherr, Neele Kemper, Michael Heider, Jörg Hähner

Organizations: Universität Augsburg, Augsburg, Germany

Abstract

Selecting an optimization algorithm requires comparing candidates across problem instances, but the computational budget for deployment is often unknown at benchmarking time. Current methods either collapse anytime performance into a scalar, require manual interpretation of plots, or produce conclusions that change when algorithms are added or removed. Moreover, methods based on raw objective values require normalization, which needs bounds or optima that are often unavailable and breaks coherent aggregation across instances. We propose a framework that formulates anytime algorithm comparison as Pareto optimization over time: an algorithm is non-dominated if no competitor beats it at every timepoint. By using rankings rather than objective values, our approach requires no bounds, no normalization, and aggregates coherently across arbitrary instance distributions without requiring known optima. We introduce PolarBear (Pareto-optimal anytime algorithms via Bayesian racing), a procedure that identifies the anytime Pareto set through adaptive sampling with calibrated uncertainty. Bayesian inference over a temporal Plackett-Luce ranking model provides posterior beliefs about pairwise dominance, enabling early elimination of confidently dominated algorithms. The output Pareto set together with the posterior supports downstream algorithm selection under arbitrary time preferences and risk profiles without additional experiments.

Figures & tables

Model	Prior structure	Space	Temporal	Complexity in $T$
Independent Dirichlet	$\theta(t)\sim\text{Dir}(\alpha)$	Simplex	Independent	$O(T)$
Hierarchical Dirichlet	$\theta(t)\sim\text{Dir}(\kappa/n)$ , shared $\kappa$	Simplex	Independent	$O(T)$
Gaussian Process (GP)	$\eta_{q}\sim\mathcal{GP}(0,k)$	Log	Smooth	$O(T^{3})$ / $O(T^{2}M)$
Hilbert Space GP	$\eta_{q}\approx\sum_{j}\beta_{j}\phi_{j}$	Log	Smooth	$O(Tm)$
Random Walk	$\eta_{q}(t_{i+1})\sim\mathcal{N}(\eta_{q}(t_{i}),\sigma^{2}\Delta t)$	Log	Markov	$O(T)$
B-spline	$\eta_{q}=\sum_{j}\beta_{j}B_{j}$	Log	Smooth	$O(TK)$

Table 1. Temporal Plackett-Luce model variants for anytime performance analysis.

Panel of Figure 1 — Figure 1. Mean execution time in seconds (5 repetitions) for selected models and approximation methods.

Panel of Figure 2 — Figure 2. A synthetic example with 5 algorithms. Figures (b) to (e) show the mean and 95% credible interval of the rating posterior (y-axis) over time (x-axis), with ground truth ratings from (a) as dotted lines. Figure (f) shows the resulting posterior over preference values for a uniform budget preference. Note that ratings at a specific $t$ always sum to 1.

Panel of Figure 3 — Figure 3. Dominance posterior probabilities over rounds. Points show $\max_{A\in\mathbf{A}}P(A\overset{\mathbf{T}}{\succ}B)$ for each algorithm $B$ at each round (left y-axis). Note that the left y-axis changes to a log-scale for $p>0.9$ . A cross marks elimination, i.e., when the dominance probability climbs above the decision threshold $\alpha$ . A diamond marks that the algorithm is fully resolved and a Pareto set member. The black line shows the proportion of resolved algorithm pairs (right y-axis).

Panel of Figure 4 — Figure 4. A synthetic example with 10 algorithms. Conventions as in Figure 2 .

Panel of Figure 5 — Figure 5. A synthetic example with 10 algorithms. Conventions as in Figure 2 . A resolved algorithm has all pairwise relationships determined; for non-eliminated algorithms, this confirms Pareto set membership.

Panel of Figure 6 — Figure 6. ECDF (a) and AOCC (b) for the MA-BBOB case study, using 1000 instances. The ECDF shows the mean attained fraction of the interval $[10^{-8},10^{2}]$ , scaled logarithmically. The shaded region is the 95% confidence interval of the mean, constructed by bootstrapping. The mean AOCC (dashes) is the area under the ECDF, using a linear x-axis. Points are the full AOCC distribution over instances.

Panel of Figure 7 — Figure 7. EAF difference of selected algorithm pairs of the MA-BBOB case study on 1000 instances. In the EAF, color encodes the proportion of runs that attained at least the objective target $z-f_{\text{opt}}$ (y-axis) at a specific number of function evaluations (x-axis). Here, the difference of two such EAF surfaces is shown, with color encoding the difference in run proportions (red means first algorithm better, blue means second better, gray means no difference). The dashed line shows the median EAF contour (i.e., for each $t$ , the $z-f_{\text{opt}}$ which 50% of runs have attained) of the first algorithm; dotted line shows the same of the second algorithm.

Panel of Figure 8 — Figure 8. Key PolarBear rounds for the MA-BBOB case study. The figures show the mean and 95% credible interval of the rating posterior (y-axis) over function evaluations (x-axis). A resolved algorithm has all pairwise relationships determined; for non-eliminated algorithms, this confirms Pareto set membership.

Figure 10. Allocation of function evaluations and instances per algorithm by PolarBear for the MA-BBOB case study. Color shows the number of instances that saw the respective amount of function evaluations. Pointwise elimination allows reducing sample costs even for non-dominated algorithms by evaluating algorithms only up to their largest unresolved budget. This adaptive allocation achieves 59% fewer total function evaluations compared to the standard practice of running all algorithms to completion on 1000 instances.

Variant	Adaptation mechanism	Complexity
COV	Full covariance with eigendecomposition	$O(d^{3})$
SEP	Diagonal only	$O(d)$
MAT	Direct transformation matrix (rank-one + rank- $\mu$ )	$O(d^{2})$
CHO	Cholesky factor with rank updates	$O(d^{2})$
CMSA	Exponential moving average + Cholesky recomputation	$O(d^{2})$
NAT	Matrix exponential of natural gradient	$O(d^{3})$

Table 2. Modular CMA-ES variants compared in the GP-BBOB case study, differing in covariance matrix adaptation mechanism. Complexity is per-generation cost in dimension

d

Panel of Figure 11 — Figure 11. Key PolarBear rounds and posteriors for the GP-BBOB case study. Figures (a) to (e) show the mean and 95% credible interval of the rating posterior (y-axis) over wall-clock time in seconds (x-axis). Figure (f) shows the resulting posterior over preference values for a uniform budget preference.

Figure 12. Dominance posterior probabilities over rounds for the GP-BBOB case study. Conventions as in Figure 3 . The drop in dominance posterior probability of CHO in round 6 can be attributed to high uncertainty whether it might cross NONE and SEP at 0.1s and 30s, respectively, given current observations (cf. Figure 11(b) ).

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Prior	Notes / support
$d$ (dimension)	$\mathrm{Trunc}\!\left(\mathcal{N}(240,30);\,[2,320]\right)$	integer cast
$y_{0}$ (offset)	$1000\cdot\mathrm{Cauchy}(0,1)$	scalar
$\mathbf{i}$ (instances)	$\mathrm{UnifInt}\{1,\dots,999\}^{24}$	i.i.d. per base function
$T$ (logits temperature)	$\mathrm{LN}(-0.5,\,0.5)$	$T>0$
$m$ (RFF features for logits GP)	$\mathrm{DU}\{32,\dots,128\}$	integer cast
$\ell$ (logits GP lengthscale)	$\mathrm{LN}(2.0,\,1.0)$	$\ell>0$

Appendix

Table 3. Priors used for GP-BBOB in the third case study. Here

\mathrm{LN}(\mu,\sigma)

denotes a LogNormal distribution with underlying normal parameters,

\mathrm{DU}\{a,\dots,b\}

a discrete uniform distribution on integers, and

\mathrm{Trunc}(\cdot;[a,b])

truncation (not clipping) to the interval

[a,b]

Panel of Figure 13 — Figure 13. A GP-BBOB instance with $d=2$ . Figure (a) shows $w(x)$ for all instances with any $w(x)>0.001$ . Figure (b) shows the sparsity level $k(x)$ , and (c) shows the resulting landscape $f(x)$ with minimal observed value $f_{\min}$ (from the plotting grid, not necessarily the global optimum) subtracted, then log-scaled.

Algorithm Selection

Algorithm selection predicts which solver, model, or strategy will work best for a given instance, context, or computational budget.

See all 50 papers

Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits
Jun 17, 2026Lennert Saerens, Bram Silue, Eleni Litsa +2Thompson Sampling Multi-Armed Bandits
Artificial Intelligence Lab, Departement of Computer Science, Vrije Universiteit Brussel, Brussels, Belgium · imec, Leuven, Belgium
Fast Bayesian Optimization Through Linear Models
Oct 21, 2026Colin Doumont, Henry Moss, Philipp HennigBayesian Optimization Surrogate Modeling
University of Tübingen, Tübingen AI Center · Lancaster University
SPEA2 $^+$ : Improved Density Estimation in SPEA2 with Provable Runtime Guarantees
Jun 10, 2026Duc-Cuong Dang, Andre Opris, Dirk SudholtEvolutionary Optimization Multi-Objective Evolutionary Optimization
University of Passau, Passau, Germany

Jun 17, 2026J/K move · Enter open · S save

Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits

Lennert Saerens, Bram Silue, Eleni Litsa, Peter Vrancx+1

Artificial Intelligence Lab, Departement of Computer Science, Vrije Universiteit Brussel, Brussels, Belgium · imec, Leuven, Belgium

Thompson Sampling Multi-Armed Bandits Combinatorial Multi-Armed Bandits Pareto Optimization

Open paper AskPDF arXiv

Identifying Pareto optimal solutions is critical to support multi-objective decision-making. We introduce the first anytime Multi-Objective Multi-Armed Bandit algorithm for the Pareto Set Identification problem, taking a Bayesian approach: Top-Two Pareto Front Thompson Sampling (TTPFTS). We benchmark TTPFTS against state-of-the-art fixed-budget Pareto Set Identification algorithms on synthetic environments. Next, we demonstrate its practical utility in a challenging multi-objective molecular discovery setting by efficiently exploring an ultra-large synthesis-on-demand molecular library. Furthermore, we introduce a novel uncertainty quantification metric that estimates our algorithm's confidence in the predicted Pareto set. We demonstrate that this metric effectively proxies true performance, yielding a robust methodology for monitoring learning progress in complex settings. Finally, we complement these empirical findings with a theoretical proof of the algorithm's asymptotic correctness.

Abstract

Algorithm Selection

Explore similar work

Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits

Fast Bayesian Optimization Through Linear Models

SPEA2+^++: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees

SPEA2 $^+$ : Improved Density Estimation in SPEA2 with Provable Runtime Guarantees