# Synchronous vs Asynchronous Active Learning

Mickael Binois, Rodolphe Le Riche

► To cite this version:

Mickael Binois, Rodolphe Le Riche. Synchronous vs Asynchronous Active Learning. École thématique. Asynchronous Bayesian Optimization, Centre Inria d'Université Côte d'Azur, France. 2026. hal-05508311

HAL Id: hal-05508311

https://hal.science/hal-05508311v1

Submitted on 13 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Synchronous vs Asynchronous Active Learning

Mickaël Binois

Inria Center at Université Côte d'Azur - Acumes team

Rodolphe Le Riche

LIMOS (UMR CNRS 6158) Ecole des Mines de Saint-Etienne and UCA

CIROQUO training

28/01/2026

the authors acknowledge funding of this workshop by the CIROQUO consortium, https://ciroquo.ec-lyon.fr/

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>
1. Background: GP and infill criteria

2. Synchronous batch- and lookahead- infill criteria

* Definitions

* (Some) Heuristics to compute and optimize them

3. Asynchronous infill criteria

* Definitions and link with synchronous infill criteria

* Computational aspects of the asynchronous logic

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>
# Motivation

In the analysis of complex simulators, when the evaluation budget is limited, sequentiality is key in surrogate-based approaches.

Compared to a one-shot design of experiments,

* as new data accumulates, the surrogate becomes more precise, benefiting the selection of the following observations;

* hence it allows to adaptively select new designs in the regions of interest.

The corresponding sequential/active learning approach is as follows (see, e.g.,<fnref n="1" />):

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<footnote n="1">¹R. B. Gramacy. Surrogates: Gaussian Process Modeling, Design, and Optimization for the Applied Sciences. CRC Press, 2020.</footnote>
Example with Bayesian Optimization

<figure><img src="image_15.png" /></figure>

For example:

1. Maximin Latin Hypercubes Samples

2. Gaussian process model

3. Expected Improvement

4. One at a time

5. Budget

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>
Start of background

Gaussian processes, Expected Improvement

You may want to skip this and goto "End of Background" slide 8

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>
# Surrogate modeling: Gaussian process regression

We use a zero mean GP prior on $f$, with covariance $k$: $Y \sim GP(0, k)$.

MVN conditional identities: the posterior given $D_n := (x_i, f(x_i))_{1\le i \le n}$ is:

$Y(\mathbf{x})|D_n \sim GP(\mu_n(\mathbf{x}), \sigma_n^2(\mathbf{x}))$ with
$$ \mu_n(\mathbf{x}) = \mathbb{E}(Y(\mathbf{x})|D_n) = \mathbf{k}(\mathbf{x})^\top \mathbf{K}_n^{-1} \mathbf{Y}, $$
$$ \sigma_n^2(\mathbf{x}) = \mathrm{Var}(Y(\mathbf{x})|D_n) = k(\mathbf{x}, \mathbf{x}) - \mathbf{k}(\mathbf{x})^\top \mathbf{K}_n^{-1} \mathbf{k}(\mathbf{x}), \text{ where} $$
$$ \mathbf{Y} = (f(\mathbf{x}_1), \dots, f(\mathbf{x}_n)), \quad \mathbf{k}(\mathbf{x}) = (k(\mathbf{x}, \mathbf{x}_1), \dots, k(\mathbf{x}, \mathbf{x}_n))^\top \text{ and} $$
$$ \mathbf{K}_n = (k(\mathbf{x}_i, \mathbf{x}_j))_{1\le i,j \le n}. $$

<figure><img src="image_22.png" /></figure>
## 2) Infill criterion - Expected Improvement<fnref n="2" />

Improvement: $I: \mathbf{x} \in \mathcal{X} \rightarrow \max \left\{ \hat{f}^* - Y(\mathbf{x}), 0 \right\} \in \mathbb{R}, \hat{f}^* = \min_{1 \le i \le n} y_i,$

Expected Improvement

$$ \mathbb{E}[I(\mathbf{x})|D_n] = (\hat{f}^* - \mu_n(\mathbf{x})) \Phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) + \sigma_n(\mathbf{x}) \phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) $$

<figure><img src="image_23.png" /></figure>

EI can be extended to the noisy case, e.g., with $\hat{f}^* = \min_{1 \le i \le n} \mu_n(\mathbf{x}_i)$.

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<footnote n="2">²J. Mockus, V. Tiesis, and A. Zilinskas. "The application of Bayesian methods for seeking the extremum". In: *Towards Global Optimization* 2.117-129 (1978), p. 2.</footnote>
## 2) Infill criterion - Expected Improvement<fnref n="2" />

Improvement: $I: \mathbf{x} \in \mathcal{X} \rightarrow \max \{\hat{f}^* - Y(\mathbf{x}), 0\} \in \mathbb{R}, \hat{f}^* = \min_{1 \le i \le n} y_i,$

Expected Improvement

$$ \mathbb{E}[I(\mathbf{x})|D_n] = (\hat{f}^* - \mu_n(\mathbf{x})) \Phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) + \sigma_n(\mathbf{x}) \phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) $$

<figure><img src="image_27.png" /></figure>

EI can be extended to the noisy case, e.g., with $\hat{f}^* = \min_{1 \le i \le n} \mu_n(\mathbf{x}_i)$.

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

<footnote n="2">²Mockus, Tiesis, and Zilinskas, "The application of Bayesian methods for seeking the extremum".</footnote>
## 2) Infill criterion - Expected Improvement<fnref n="2" />

Improvement: $I: \mathbf{x} \in \mathcal{X} \rightarrow \max \{\hat{f}^* - Y(\mathbf{x}), 0\} \in \mathbb{R}, \hat{f}^* = \min_{1 \le i \le n} y_i,$

Expected Improvement

$$ \mathbb{E}[I(\mathbf{x})|D_n] = (\hat{f}^* - \mu_n(\mathbf{x})) \Phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) + \sigma_n(\mathbf{x}) \phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) $$

<figure><img src="image_31.png" /></figure>

EI can be extended to the noisy case, e.g., with $\hat{f}^* = \min_{1 \le i \le n} \mu_n(\mathbf{x}_i)$.

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

<figure><img src="image_34.png" /></figure>

<footnote n="2">²Mockus, Tiesis, and Zilinskas, "The application of Bayesian methods for seeking the extremum".</footnote>
## 2) Infill criterion - Expected Improvement<fnref n="2" />

Improvement: $I: \mathbf{x} \in \mathcal{X} \rightarrow \max \{\hat{f}^* - Y(\mathbf{x}), 0\} \in \mathbb{R}, \hat{f}^* = \min_{1 \le i \le n} y_i,$

Expected Improvement

$$ \mathbb{E}[I(\mathbf{x})|D_n] = (\hat{f}^* - \mu_n(\mathbf{x})) \Phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) + \sigma_n(\mathbf{x}) \phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) $$

<figure><img src="image_35.png" /></figure>

EI can be extended to the noisy case, e.g., with $\hat{f}^* = \min_{1 \le i \le n} \mu_n(\mathbf{x}_i)$.

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

<footnote n="2">²Mockus, Tiesis, and Zililskas, "The application of Bayesian methods for seeking the extremum".</footnote>
## 2) Infill criterion - Expected Improvement<fnref n="2" />

Improvement: $I: \mathbf{x} \in \mathcal{X} \rightarrow \max \left\{ \hat{f}^* - Y(\mathbf{x}), 0 \right\} \in \mathbb{R}, \hat{f}^* = \min_{1 \le i \le n} y_i,$

Expected Improvement

$$ \mathbb{E}[I(\mathbf{x})|D_n] = (\hat{f}^* - \mu_n(\mathbf{x})) \Phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) + \sigma_n(\mathbf{x}) \phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) $$

<figure><img src="image_39.png" /></figure>

EI can be extended to the noisy case, e.g., with $\hat{f}^* = \min_{1 \le i \le n} \mu_n(\mathbf{x}_i)$.

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<footnote n="2">²Mockus, Tiesis, and Zilinskas, "The application of Bayesian methods for seeking the extremum".</footnote>
## 2) Infill criterion - Expected Improvement<fnref n="2" />

Improvement: $I: \mathbf{x} \in \mathcal{X} \rightarrow \max \left\{ \hat{f}^* - Y(\mathbf{x}), 0 \right\} \in \mathbb{R}, \hat{f}^* = \min_{1 \le i \le n} y_i,$

Expected Improvement

$$ \mathbb{E}[I(\mathbf{x})|D_n] = (\hat{f}^* - \mu_n(\mathbf{x})) \Phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) + \sigma_n(\mathbf{x}) \phi \left( \frac{\hat{f}^* - \mu_n(\mathbf{x})}{\sigma_n(\mathbf{x})} \right) $$

<figure><img src="image_42.png" /></figure>

EI can be extended to the noisy case, e.g., with $\hat{f}^* = \min_{1 \le i \le n} \mu_n(\mathbf{x}_i)$.

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

<footnote n="2">²Mockus, Tiesis, and Zilinskas, "The application of Bayesian methods for seeking the extremum".</footnote>
# Other active learning policies

Optimization is perhaps the most commonly used active learning procedure, but there are many other ones:

* level-set estimation, e.g., with the Straddle scheme<fnref n="3" /> maximizing $\alpha(\mathbf{x}) = (-|\mu_n(\mathbf{x})| + \beta\sigma_n(\mathbf{x}))$,

* global accuracy, e.g., minimizing the integrated mean-square prediction error $\int_{\mathcal{X}} \sigma_{n+1}^2(\mathbf{x})d\mathbf{x}$,

* calibration (inverse problem), e.g., <fnref n="4" />,

* more exotic ones like Nash equilibria<fnref n="5" /> (also see<fnref n="6" />), ...

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>

<figure><img src="image_55.png" /></figure>

<footnote n="3">³B. Bryan and J. Schneider. "Actively learning level-sets of composite functions". In: *Proceedings of the 25th international conference on Machine learning*. 2008, pp. 80–87.</footnote>

<footnote n="4">⁴A. Barry et al. "Optimal Design of Physical and Numerical Experiments for Computer Code Calibration". In: (2024).</footnote>

<footnote n="5">⁵V. Picheny, M. Binois, and A. Habbal. "A Bayesian optimization approach to find Nash equilibria". In: *Journal of Global Optimization* (2018). ISSN: 1573-2916.</footnote>

<footnote n="6">⁶D. Ginsbourger. "Sequential Design of Computer Experiments". In: *Wiley StatsRef: Statistics Reference Online*. American Cancer Society, 2018, pp. 1–9.</footnote>
End of background

Gaussian processes, Expected Improvement

<figure><img src="image_56.png" /></figure>

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>
1. Background: GP and infill criteria

2. Synchronous batch- and lookahead- infill criteria

* Definitions

* (Some) Heuristics to compute and optimize them

3. Asynchronous infill criteria

* Definitions and link with synchronous infill criteria

* Computational aspects of the asynchronous logic

<figure><img src="image_59.png" /></figure>

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /></figure>
# Batch/parallel sequential design (synchronous) I

<figure><img src="image_62.png" /></figure>

Model fitting and infill criterion optimization times are often neglected.

With similar evaluation times for any *x* and a number of computing
workers larger than or equal to *q*, this synchronous framework is sufficient.

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>

<footnote>ªR. Garnett. *Bayesian Optimization*. Cambridge University Press, 2023.</footnote>
q-EI criterion

* {$\mathbf{x}'_1, \dots, \mathbf{x}'_q$} set of q unordered points

* q-Improvement:

$$ 
\begin{aligned}
ql: \{\mathbf{x}'_1, \dots, \mathbf{x}'_q\} &\rightarrow \max \{\hat{f}^* - \min (Y(\mathbf{x}'_1), \dots, Y(\mathbf{x}'_q)), 0\} \in \mathbb{R}^+, \\
\hat{f}^* &= \min_{1 \le i \le n} y_i
\end{aligned}
 $$

* q-EI($\{\mathbf{x}'_1, \dots, \mathbf{x}'_q\}$) = $\mathbb{E}[ql(\{\mathbf{x}'_1, \dots, \mathbf{x}'_q\}) | D_n]$

<figure><img src="image_65.png" /></figure>

<footnote n="7">⁷D. Ginsbourger, R. Le Riche, and L. Carraro. "Kriging is well-suited to parallelize optimization". In: *Computational Intelligence in Expensive Optimization Problems*. Springer, 2010, pp. 131-162.</footnote>
Optimality of *q*-points infill criteria

Most<fnref n="8" /> infill criteria can be generalized to *q* points : $\alpha(\mathbf{x}'_1, \dots, \mathbf{x}'_q)$

* El, probability of improvement of $\min(Y(\mathbf{x}'_1), \dots, Y(\mathbf{x}'_q))$

* *q*-steps ahead criteria calculated (knowledge gradient, entropy reductions<fnref n="9" />) with $D_n \cup \{\mathbf{x}'_1, \dots, \mathbf{x}'_q\}$

* *q* repetitions of Thomson sampling

All infill criteria are optimal in a specific way, which generalizes to *q* points:

* *q*-El is optimal in the sense of the expected improvement of the *q* last points choice;

* entropy reduction criteria bring the most information on the location of the optimum $\mathbf{x}^*$ by adding *q*-points;

* the *q*-knowledge gradient maximizes the 1-step-ahead expected gain in prediction; ...

<figure><img src="image_66.png" /></figure>

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

<footnote n="8">⁸Less obvious with UCB: it could be a cumulated UCB over the *q*-points with the kriging belief assumption.</footnote>

<footnote n="9">⁹J. Villemonteix, E. Vazquez, and E. Walter. "An informational approach to the global optimization of expensive-to-evaluate functions". In: *Journal of Global Optimization* 44.4 (2009), pp. 509-534. URL: http://www.springerlink.com/index/T670U067V47922VK.pdf.</footnote>
Lookahead criteria I

A closely related problem is to consider the sequence of future evaluations and (ideally) the full remaining evaluation budget. It leads to a dynamic optimization problem¹⁰:

$$ \mathbf{x}_q(D_{q-1}) = \arg\max_{\mathbf{x}} \alpha(\mathbf{x} \mid D_{q-1}), \quad D_{q-1} = \{\mathbf{x}_1, y(\mathbf{x}_1), \dots, \mathbf{x}_{q-1}, y(\mathbf{x}_{q-1})\} $$

$$ \mathbf{x}_{q-1}(D_{q-2}) = \arg\max_{\mathbf{x}} \mathbb{E}_{Y(q-2)} \alpha(\mathbf{x}, \mathbf{x}_q(D_{q-1})) , $$

$$ D_{q-1} = D_{q-2} \cup \{\mathbf{x}, Y^{(q-2)}(\mathbf{x})\} $$

$$ \mathbf{x}_{q-2}(D_{q-3}) = \arg\max_{\mathbf{x}} \mathbb{E}_{Y(q-3)} \alpha(\mathbf{x}, \mathbf{x}_{q-1}(D_{q-2}), \mathbf{x}_q(D_{q-1})) , $$

$$ D_{q-2} = D_{q-3} \cup \{\mathbf{x}, Y^{(q-3)}(\mathbf{x})\} , $$

$$ D_{q-1} = D_{q-2} \cup \{\mathbf{x}_{q-1}(D_{q-2}), Y^{(q-3)}(\mathbf{x}_{q-1}(D_{q-2}))\} $$

...

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /></figure>

<figure><img src="image_71.png" /></figure>
Note the marginalization on the future function values in the infill criteria. For instance, for the two-step lookahead EI, this writes:

$$EI_2(\mathbf{x}) = EI(\mathbf{x}|D_n) + \mathbb{E}\left[\max_{\mathbf{x}_{n+2} \in \mathcal{X}} EI(\mathbf{x}_{n+2}|D_{n+1})\right]$$

where $D_{n+1} = D_n \cup \{\mathbf{x}, Y^{(n)}(\mathbf{x})\}$.

It becomes quickly intractable beyond looking a single step ahead.

But approximations are possible, see e.g.,<sup>11, 12</sup>.

<figure><img src="image_72.png" /></figure>

<footnote n="10"><sup>10</sup>To simplify notations, the current known DoE, $D_n$, is not explicitely written but it is always associated to any $\alpha$().</footnote>

<footnote n="11"><sup>11</sup>R. Lam, K. Willcox, and D. H. Wolpert. "Bayesian Optimization with a Finite Budget: An Approximate Dynamic Programming Approach". In: *Advances in Neural Information Processing Systems*. 2016, pp. 883–891.</footnote>

<footnote n="12"><sup>12</sup>J. Wu and P. Frazier. "Practical two-step lookahead Bayesian optimization". In: *Advances in neural information processing systems* 32 (2019).</footnote>
The infill criterion is different from its 1-step ahead counterpart:

<figure><img src="image_73.png" /></figure>

Figure 1: We demonstrate 2-OPT and EI minimizing a 1-d synthetic function sampled from a GP. Each row shows the posterior on $f$ (mean $\pm$/- one standard deviation) and the corresponding acquisition function, for EI (left) and 2-OPT (right). We plot progress over three iterations. On the first iteration, EI evaluates a point that refines an existing local optimum and could have provided a small one-step improvement, but provides little information of use in future evaluations. In contrast, 2-OPT explores more aggressively, which helps it identify a new global minimum in the next iteration.

<figure><img src="image_74.png" /></figure>

<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /></figure>

<footnote n="13">¹³Wu and Frazier, “Practical two-step lookahead Bayesian optimization”.</footnote>
# Link between batch and lookahead criteria

Importantly, batch criteria are reasonable approximations of lookahead ones.

Example: preceding 3-steps-ahead seen as a 3 points batch criterion:

$$ \max_{\mathbf{x}} \mathbb{E}_{Y(q-3)} \alpha(\mathbf{x}, \mathbf{x}_{q-1}(D_{q-2}), \mathbf{x}_q(D_{q-1})) \rightsquigarrow \max_{\mathbf{x}_{q-2}, \mathbf{x}_{q-1}, \mathbf{x}_q} \mathbb{E}_{Y(q-3)} \alpha(\mathbf{x}_{q-2}, \mathbf{x}_{q-1}, \mathbf{x}_q) $$

Given a budget, at time *t*, maximizing the infill criterion over the set of (budget – *t*) points is a proxy to the lookahead criterion.

Like the lookahead criteria, the batch criteria distribute points in different areas of the search space.

<figure><img src="image_77.png" /></figure>

<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>
Example of 2-EI from<fnref n="14" />

<figure><img src="image_80.png" /><figcaption>(a) Test function eq. (5) (dashed), kriging model based on 5 observations - predicted mean (blue), 2σ predicted confidence intervals (red).</figcaption></figure>

<figure><img src="image_81.png" /><figcaption>(b) One point EI, $EI(x)$.</figcaption></figure>

<figure><img src="image_82.png" /><figcaption>(c) Contour lines of 2 points EI, $EI^{(0,2)}(x)$</figcaption></figure>

<figure><img src="image_83.png" /><figcaption>(d) 3D plot of 2 points EI, $EI^{(0,2)}(x)$</figcaption></figure>

<footnote n="14">¹⁴ Janis Janusevskis, Rodolphe Le Riche, and David Ginsbourger. “Parallel expected improvements for global optimization: summary, bounds and speed-up”. In: (2011). HAL report https://hal.science/hal-0061399v1.</footnote>
# Other batch infill functions and direct optimization

Some criteria like EI have a closed-form expression, see<fnref n="15" />. But mostly, they require approximations like entropy or stepwise uncertainty reduction ones, i.e.,<fnref n="16" />.

It is possible to optimize the batch acquisition function as usual.

**Pros:** it takes into account the uncertainty at un-evaluated designs.

**Cons:**

* The infill criterion optimization becomes a $q \times d$ dimensional optimization problem,

* It has symmetry properties since reordering the x's in the batch does not matter.

* Even with approximations, the computational cost is often non-negligible.

<figure><img src="image_84.png" /></figure>

<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

<footnote n="15">¹⁵C. Chevalier and D. Ginsbourger. "Fast computation of the multipoint Expected Improvement with applications in batch selection". In: *International conference on learning and intelligent optimization*. Springer. 2013, pp. 59–69.</footnote>

<footnote n="16">¹⁶C. Chevalier et al. "Fast parallel kriging-based stepwise uncertainty reduction with application to the identification of an excursion set". In: *Technometrics* 56.4 (2014), pp. 455–465.</footnote>
Greedy batch infill criteria I

To select a batch of *q* candidates, one way is to select them one by one with a standard criterion, assuming a virtual value for the unknown ones.

$$
\text{for } i = 1, \dots, q \\
\quad \mathbf{x}_i = \arg \max_{\mathbf{x}'_i} \alpha(\mathbf{x}'_i | \mathbf{x}_1, h(\mathbf{x}_1), \dots, \mathbf{x}_{i-1}, h(\mathbf{x}_{i-1})) \\
\quad \# h(\mathbf{x}) \text{ hallucination at } \mathbf{x}
$$

This leads to the so-called *kriging believer* (using the predictive mean) or *constant liar* (giving an arbitrary value) heuristics<sup>17</sup>. Later, this was coined as *hallucination* in the ML community, see e.g.,<sup>18</sup>.

Thompson sampling<sup>19</sup> is a version where the outcome $h(\mathbf{x})$ is sampled
from the posterior.

<figure><img src="image_87.png" /></figure>
**Pros:** this requires *q* optimizations over the *d*-dimensional space. The infill criterion evaluation time remains limited.

**Cons:** the uncertainty about the unknown function values is not propagated. The optimality of the batch criteria is lost with this greedy selection.

See also the GLASSES<fnref n="20" /> or BINOCULAR<fnref n="21" /> variants, penalizing around batch candidates.

<figure><img src="image_88.png" /></figure>

<figure><img src="image_89.png" /></figure>

<figure><img src="image_90.png" /></figure>

<footnote n="17">¹⁷Ginsbourger, Le Riche, and Carraro, "Kriging is well-suited to parallelize optimization".</footnote>

<footnote n="18">¹⁸T. Desautels, A. Krause, and J. W Burdick. "Parallelizing exploration-exploitation tradeoffs in Gaussian process bandit optimization.". In: *J. Mach. Learn. Res.* 15.1 (2014), pp. 3873–3923.</footnote>

<footnote n="19">¹⁹W. R. Thompson. "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples". In: *Biometrika* 25.3/4 (1933), pp. 285–294.</footnote>

<footnote n="20">²⁰J. González, M. Osborne, and N. D. Lawrence. "GLASSES: Relieving The Myopia Of Bayesian Optimisation". In: *Proceedings of the 19th International Conference on Artificial Intelligence and Statistics*. 2016, pp. 790–799.</footnote>

<footnote n="21">²¹S. Jiang et al. "BINOCULARS for efficient, nonmyopic sequential experimental design". In: *International Conference on Machine Learning*. PMLR. 2020, pp. 4794–4803.</footnote>
1. Background: GP and infill criteria

2. Synchronous batch- and lookahead- infill criteria

* Definitions

* (Some) Heuristics to compute and optimize them

3. Asynchronous infill criteria

* Definitions and link with synchronous infill criteria

* Computational aspects of the asynchronous logic

<figure><img src="image_91.png" /></figure>

<figure><img src="image_92.png" /></figure>

<figure><img src="image_93.png" /></figure>
# Batch/parallel sequential design (asynchronous)

In many applications the evaluation time can vary significantly, plus the total time dedicated to the sequential procedure (GP learning + acquisition function optimization) matters.

It is thus important to make the most of a parallel architectures, limiting iddle times.

<figure><img src="image_94.png" /></figure>

Illustration inspired from²²:

<figure><img src="image_95.png" /></figure>

Next we present the changes with this asynchronous case.

²²K. Kandasamy et al. "Parallelised Bayesian optimisation via Thompson sampling". In: *International Conference on Artificial Intelligence and Statistics*. PMLR. 2018, pp. 133–142.

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>

<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>
From the methodological viewpoint, the main change between asynchronous and synchronous parallel active learning is to take into account running evaluations.

Indeed, the risk is to evaluate several times the same design.

Fortunately, for one-step lookahead infill criteria, this is already taken into account by batch infill criteria! See e.g., Section 11.4 in²³. It amounts to selecting *q* new points in a batch with *q* + *p* points, with *p* the designs currently under evaluation, where marginalization w.r.t. unknown functions values can be used again:

$$ \mathbf{x}_{p+1}, \dots, \mathbf{x}_{p+q} \in \arg \max_{\mathbf{x}_1, \dots, \mathbf{x}_q} \mathbb{E}_{[Y(\mathbf{x}) \& Y(\mathbf{x}')]} \alpha(\mathbf{x}'_1, \dots, \mathbf{x}'_q | \mathbf{x}_1, \dots, \mathbf{x}_p) $$

<figure><img src="image_102.png" /></figure>
Since $\mathbb{E}_{[Y(\mathbf{x}) \& Y(\mathbf{x}')]}\alpha(\mathbf{x}'_1, \dots, \mathbf{x}'_q | \mathbf{x}_1, \dots, \mathbf{x}_p) =$
$\mathbb{E}_{[Y(\mathbf{x})]}\mathbb{E}_{[Y(\mathbf{x}')]}\alpha(\mathbf{x}'_1, \dots, \mathbf{x}'_q | \mathbf{x}_1, Y(\mathbf{x}_1), \dots, \mathbf{x}_p, Y(\mathbf{x}_p))$

all infill criteria that cancel at already visited points will cancel at busy points. Otherwise (e.g., UCB), use a local penalty to stay away from busy points $\mathbf{x}^{24}$, or not$^{25}$. For UCB, marginalization over busy points is equivalent to the Kriging believer:

$\mathbb{E}_{Y(\mathbf{x})}[-\mu_n(\mathbf{x}') + \beta\sigma_n^2(\mathbf{x}')] = -\mu_{n+p}(\mathbf{x}') + \beta\sigma_{n+p}^2(\mathbf{x}')$ where $f(\mathbf{x}) = \mu_n(\mathbf{x})$. Note that for stochastic simulators, repeating observations may actually be beneficial, see e.g.,$^{26}$, but this is out of scope here.

<figure><img src="image_103.png" /></figure>

<figure><img src="image_104.png" /></figure>

<figure><img src="image_105.png" /></figure>

<footnote>$^{23}$Garnett, *Bayesian Optimization*.</footnote>

<footnote>$^{24}$A. Alvi et al. "Asynchronous Batch Bayesian Optimisation with Improved Local Penalisation". In: *International Conference on Machine Learning*. 2019, pp. 253-262.</footnote>

<footnote>$^{25}$B. Riegler, J. AC Odgers, and V. Fortuin. "Rethinking Exploration in Asynchronous Bayesian Optimization: Standard Acquisition is All You Need". In: *The Exploration in AI Today Workshop at ICML 2025*.</footnote>

<footnote>$^{26}$B. Zhang et al. "Batch-sequential design and heteroskedastic surrogate modeling for delta smelt conservation". In: *The Annals of Applied Statistics* 16.2 (2022), pp. 816-842.</footnote>
Example: Asynchronous Expected Improvement I

$x \equiv p$ busy points, $x' \equiv q$ new points

$$
\begin{align*}
EI(x', x) &= \mathbb{E} \max\{\hat{f}^* - \min(Y(x), Y(x')); 0\} \\
&= \mathbb{E} \max\{\hat{f}^* - Y(x), 0\} + \mathbb{E} \max\{\min(\hat{f}^*, Y(x)) - Y(x'), 0\} \\
&= EI(x) + EEI(x' | x) \\
& \quad \text{fixed term}
\end{align*}
$$

Asynchronous BO iteratively solves : $x_{\text{next}} \in \arg\max_{x'} EEI(x' | x)$
(from$^{27}$, $^{28}$)

<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /></figure>

<footnote n="27"><sup>27</sup> Janusevskis, Le Riche, and Ginsbourger, “Parallel expected improvements for global optimization: summary, bounds and speed-up”.</footnote>

<footnote n="28"><sup>28</sup> D. Ginsbourger et al. “Dealing with asynchronicity in Kriging-based parallel global optimization”. ERCIM conference, London, 2011. URL: http://www.emse.fr/~leriche/ERCIM_2011.pdf.</footnote>
Example: Asynchronous Expected Improvement II

<figure><img src="image_108.png" /></figure>

<figure><img src="image_109.png" /></figure>

(a) Test function (dashed),kriging model based on 5 observations predicted mean (blue), $2\sigma$ predicted confidence intervals (red).

(b) One point EI, $EI(x)$.

<figure><img src="image_110.png" /></figure>

(c) Contour lines of 2 points EI, $EI^{(0.2)}(x)$

<figure><img src="image_111.png" /></figure>

(d) 3D plot of 2 points EI, $EI^{(0.2)}(x)$

<figure><img src="image_112.png" /></figure>

(e) Contour lines of 2 points async. EI (busy point $x_{\text{Busy}} = (-0.34)$, $EI^{(1.2)}(x)$
(f) 3D plot of 2 points async. EI (busy point $x_{\text{Busy}} = (-0.34)$, $EI^{(1.2)}(x)$

<figure><img src="image_113.png" /></figure>

It remains to present the concepts related to handling asynchronicity and distributed workloads.

<figure><img src="image_114.png" /></figure>
# Distributed workloads - first example

The difficulty is to handle distributed workloads, where tasks (model fitting, infill criterion optimization and *f* evaluations) happen concurrently.

The simple version is to trigger the selection of a new candidate whenever an observation is returned.

<figure><img src="image_115.png" /></figure>

Implementations of distributed workloads will be presented later on today.

<figure><img src="image_116.png" /></figure>
# Distributed workloads - second example

For flexibility, the designs to evaluate are often inserted into a queue.

* It allows for changing the number of concurrent evaluations over time.

* It also helps decoupling the other tasks.

* The queue can be updated (reordered, removing elements, etc)

<figure><img src="image_117.png" /></figure>

<figure><img src="image_118.png" /></figure>

<figure><img src="image_119.png" /></figure>
* Agentify: evaluations ; metamodel creation ; infill criterion.

* Run diverse instances in parallel: diverse metamodels, infill criteria, optimization algorithms.

* Control mechanisms: queues balances, achieved *f* values, remaining budget, cf.<fnref n="29" /> for detecting optimizations converging to the same local optimum.

<figure><img src="image_120.png" /></figure>

<figure><img src="image_121.png" /></figure>

<figure><img src="image_122.png" /></figure>

<figure><img src="image_123.png" /></figure>

<footnote n="29">²⁹J. Larson and S. M. Wild. "Asynchronously parallel optimization solver for finding multiple minima". In: *Mathematical Programming Computation 10* (2018), pp. 303-332.</footnote>
Thanks for your attention!

<figure><img src="image_124.png" /></figure>

<figure><img src="image_125.png" /></figure>

<figure><img src="image_126.png" /></figure>