Bayesian Optimization under Stochastic Delayed Feedback

Bayesian optimization (BO) (Shahriari et al., 2015; Frazier, 2018; Garnett, 2022) is a popular and widely-used sequential method for zeroth-order optimization of unknown black-box functions that are complex and expensive to compute. The existing BO methods assume that the function evaluation (feedback) is available to the learner immediately or after a fixed delay. However, these assumptions are impractical in many real-life problems where feedback is available after a random delay. To take advantage of the experimental parallelization in these problems, the learner needs to start new function evaluations without waiting for the randomly delayed feedback. We refer to this new BO problem as ‘Bayesian Optimization under Stochastic Delayed Feedback’ (BO-SDF). In this paper, we propose algorithms that efficiently address the problem of selecting new function queries while waiting for randomly delayed feedback. Specifically, we answer the following question:
How to start a new function query when the observations of the past function queries are randomly delayed?

Many real-life applications can be cast as BO-SDF problems. For example, when performing clinical trials to discover new medicines, we need to optimize the amount of different raw materials in order to find their most effective composition using a small number of clinical trials (Chow & Chang, 2006), which is a natural application for BO due to its sample efficiency. However, the evaluation of the effectiveness of a medicine needs to take into account the side effects which are usually not observed immediately but are instead revealed after a random period due to the varying physiology of different patients. Therefore, a natural challenge here is how to use BO to choose the next composition for testing, while accounting for the stochastically delayed observations from some previous clinical trials. A similar challenge also arises when we aim to find the most effective dose of a new medicine through clinical trials (Takahashi & Suzuki, 2021).

Another motivating example arises from online product recommendation (Chapelle, 2014; Diemert et al., 2017). Most online platforms make recommendations in milliseconds, but the user’s response (i.e., watching a movie or buying a product) generally happens after a random time period which may range from hours to days or even weeks. Furthermore, the issue of randomly delayed feedback also plagues other common applications of BO such as hyperparameter tuning of machine learning (ML) models (Snoek et al., 2012) (e.g., the training time of a neural network depends on the number of layers, network width, among others) and material discovery (Ueno et al., 2016).

The closest BO setting to our BO-SDF is batch BO (Desautels et al., 2014; Daxberger & Low, 2017; Chowdhury & Gopalan, 2019) which also allows multiple queries to be performed on the black-box function in parallel. Both problems require choosing an input query to evaluate the black-box function while the observations of some previously selected inputs are not available (i.e., delayed). However, there are important differences because the delays are fixed in a certain way in batch BO but can be random in BO-SDF. Interestingly, batch BO can be considered as a special case of our BO-SDF problem and hence, our algorithms proposed for BO-SDF can be applied to batch BO while achieving important improvements (Section 4).

Following the practice of BO, in order to choose the input queries to quickly approach the global optima, we employ a Gaussian process (GP) (Rasmussen & Williams, 2006) to model the black-box function, which builds a posterior belief of the function using the history of function queries and their feedback. However, when constructing this posterior belief in BO-SDF problems, we are faced with the important question of how to handle the randomly delayed feedback whose observations are not available. To this end, we replace the unavailable delayed feedback by the minimum function value,¹¹1In many problems, the minimum value of a function is known, e.g., a user’s minimum response in online recommendation systems is ‘no click’ (i.e., $0$) and the minimum accuracy for hyperparameter tuning of machine learning models is ‘$0$’. which we refer to as censored feedback. The use of censored feedback, interestingly, improves the exploration in BO-SDF problems (Section 3.1) and hence leads to better theoretical and empirical performances. With the posterior belief built using censored feedback, we propose algorithms using upper confidence bound (UCB) and Thompson sampling (TS), both of which enjoy sub-linear regret guarantees. Specifically, our contributions are as follows:

• •

  We introduce and formalize the notion of censored feedback in the BO-SDF problem, and propose UCB- and TS-based algorithms with sub-linear regret guarantees (Section 3).

• •

  Since batch BO is a special case of BO-SDF, we apply our proposed algorithms (Section 3) to batch BO and show that our algorithms enjoy tighter regret upper bounds than classic batch BO algorithms (Section 4). This gain is mainly attributed to the censored feedback, which leads to a better exploration policy.

• •

  We extend our algorithms for the BO-SDF problem to contextual Gaussian process bandits (Krause & Ong, 2011) with stochastic delayed feedback in Section 5. This new contribution is itself of independent interest.

• •

  Our experimental results in Section 6 validate the different performance aspects of our proposed algorithms on synthetic and real-life datasets.

This paper considers the Bayesian optimization (BO) problem where the function evaluations (feedback) are available to the learner after a random delay. Let $\mathcal{Q}\subset\mathbb{R}^{n}$ be a finite domain of all function queries where $n\geq 1$.²²2We assume $\mathcal{Q}$ to be finite, but it is straightforward to extend our theoretical results to a compact domain using a suitable discretization scheme (Li & Scarlett, 2022, Lemma 2). The learner selects a new function query as soon as enough resources are available (or when experiment parallelization is possible). We denote the $t$-th query by $x_{t}\in\mathcal{Q}$. After the learner selects the query $x_{t}$ to evaluate the unknown black-box function $f$, the environment generates a noisy function evaluation, denoted by feedback $y_{t}=f(x_{t})+\varepsilon_{t}$. We assume that $\varepsilon_{t}$ is an $R$-sub-Gaussian noise. The learner observes $y_{t}$ only after a stochastic delay $d_{t}$, which is generated from an unknown distribution $\mathcal{D}$.

We refer to this new BO problem as ‘Bayesian Optimization under Stochastic Delayed Feedback’ (BO-SDF). The unknown function $f$, query space $\mathcal{Q}$, and unknown delay distribution $\mathcal{D}$ identify an instance of the BO-SDF problem. The optimal query ($x^{\star}$) has the maximum function value (global maximizer), i.e., $x^{\star}\in\arg\!\max_{x\in\mathcal{Q}}f(x)$. After selecting a query $x_{t}$, the learner incurs a penalty (or instantaneous regret) $p_{t}=f(x^{\star})-f(x_{t})$.

Since the optimal function query is unknown, we sequentially estimate this using the available information of the selected queries and observed feedback. Our goal is to learn a sequential policy for selecting queries that finds the optimal query (or global maximizer) as quickly as possible. There are two common performance measures for evaluating a sequential policy. The first performance measure is simple regret. Let $x_{t}$ be the $t$-th function query selected by the policy. Then, after observing $T$ function evaluations, the simple regret is $r_{T}=f(x^{\star})-\max_{t\in\{1,\ldots,T\}}f(x_{t}).$ Any good policy must have no regret, i.e., $\lim_{T\to\infty}{r_{T}}=0$. The second performance measure of the policy is cumulative regret which is the sum of total penalties incurred by the learner. After observing $T$ function evaluations, the cumulative regret of a policy is given by $\mathfrak{R}_{T}=\sum_{t=1}^{T}\left(f(x^{\star})-f(x_{t})\right).$ Any good policy should have sub-linear regret, i.e., $\lim_{T\to\infty}{\mathfrak{R}_{T}}/T=0.$ Even though simple regret and cumulative regret are different performance measures, having a policy with no regret or sub-linear regret implies that the policy will eventually converge to the optimal query (or global optimizer).

A function estimator is the main component of any BO problem for achieving good performance. We use a Gaussian process (GP) as a surrogate for the posterior belief of the unknown function (Rasmussen & Williams, 2006; Srinivas et al., 2010). To deal with the delayed feedback, we will introduce the notion of censored feedback in GPs, in which the delayed feedback is replaced by the minimum function value. Finally, we will propose UCB- and TS-based algorithms with sub-linear regret guarantees.

Notably, our BO-SDF problem subsumes batch BO as a special case. Specifically, the function queries in batch BO can be viewed as being sequentially selected, in which some queries need to be selected while some other queries of the same batch are still incomplete (Desautels et al., 2014). Therefore, in batch BO with a batch size of $\mathcal{B}_{x}$, the incomplete queries can be viewed as delayed feedback with fixed delays s.t. $d_{s}\leq\mathcal{B}_{x}-1$. In this case, by choosing $m=\mathcal{B}_{x}-1$, we can ensure that $\rho_{m}=\mathbb{P}(d_{s}\leq\mathcal{B}_{x}-1)=1$. As a result, our method of censoring (Section 3.1) gives a better treatment to the incomplete queries than the classic technique from batch BO, which we will demonstrate next via both intuitive justification and regret comparison.

The classic technique to handle the incomplete queries in batch BO is hallucination which was proposed by the GP-BUCB algorithm from (Desautels et al., 2014). It has also been adopted by a number of its extensions (Daxberger & Low, 2017; Chowdhury & Gopalan, 2019). In particular, the feedback of incomplete queries is hallucinated to be (i.e., censored with) the GP posterior mean computed using only the completed queries (excluding the incomplete queries). It is equivalent to keeping the GP posterior mean unchanged (i.e., unaffected by the incomplete queries) while updating the GP posterior variance using all selected queries (including the incomplete queries). Note that in contrast to the hallucination, our censoring technique sets the incomplete observations to the minimum function value (i.e., $0$) (Section 3.1). As a result, compared with the hallucination where the GP posterior mean is unaffected by the incomplete queries, our censoring can reduce the value of the GP posterior mean at the incomplete queries (because we have treated their observations as if they are $0$). As a result, our censoring can discourage these incomplete queries from being unnecessarily queried again. It encourages the algorithm to explore other unexplored regions, hence leading to better exploration.

Interestingly, the better exploration resulting from our censoring technique also translates to a tighter regret upper bound. Specifically, in batch BO with a batch size of $\mathcal{B}_{x}$, after plugging in $m=\mathcal{B}_{x}-1$ and $\rho_{m}=1$, our next result gives the regret upper bound of GP-UCB-SDF.

As long as $\gamma_{T}=\Omega(\log T)$ which holds for most commonly used kernels such as the squared exponential (SE) and Matérn kernels, both terms in 1 grow slower than $\mathfrak{R}_{T}=\tilde{O}(\gamma_{T}\sqrt{T}\exp(\gamma_{\mathcal{B}_{x}-1}))$ which is the regret upper bound of the GP-BUCB algorithm based on hallucination (Desautels et al., 2014). Importantly, to achieve a sub-linear regret upper bound (i.e., to ensure that $\exp(\gamma_{\mathcal{B}_{x}-1})$ can be upper-bounded by a constant), GP-BUCB (Desautels et al., 2014) and its extensions (Daxberger & Low, 2017; Kandasamy et al., 2018; Chowdhury & Gopalan, 2019) all require a special initialization scheme (i.e., uncertainty sampling). It is often found unnecessary in practice (Kandasamy et al., 2018) and hence represents a gap between theory and practice. Interestingly, our tighter regret upper bound from 1 has removed the dependence on $\exp(\gamma_{\mathcal{B}_{x}-1})$ and hence eliminated the need for uncertainty sampling, thereby closing this gap between theory and practice.

Note that our discussions above regarding the advantage of censoring over hallucination also apply to TS-based algorithms. In particular, in batch BO with a batch size of $\mathcal{B}_{x}$, the regret upper bound of GP-TS-SDF is given by the following result.

All three terms in 2 grow slower than $\mathfrak{R}_{T}=\tilde{O}(\exp(\gamma_{\mathcal{B}_{x}-1})\sqrt{T\gamma_{T}}(\sqrt{\gamma_{T}}+1))$ which is the regret upper bound of the GP-BTS algorithm based on hallucination (Chowdhury & Gopalan, 2019) as long as $\gamma_{T}=\Omega(\log T)$.

To summarize, though batch BO is only a special case of our BO-SDF problem, we have made non-trivial contributions to the algorithm and theory of batch BO. Our GP-UCB-SDF and GP-TS-SDF algorithms and our theoretical analyses may serve as inspiration for future works on batch BO.

Before making a decision, sometimes additional information is available to the learner in many real-life scenarios (e.g., users’ profile information for an online platform and patients’ medical history before clinical trials). This additional information is referred to as context in the literature, and the value of a function depends on the context (Agrawal & Goyal, 2013b; Chu et al., 2011; Krause & Ong, 2011; Li et al., 2010). The learner can design the algorithms to exploit the contextual information to make a better decision. We can extend our results for the BO-SDF problem to the contextual Gaussian process bandits (Krause & Ong, 2011) with stochastic delayed feedback where a non-linear function maps a context to the feedback.

Let $\mathcal{Q}\subset\mathbb{R}^{n}$ be a finite set of available actions (or queries) and $\mathcal{Z}\subset\mathbb{R}^{n^{\prime}}$ be a set of all contexts where $n,n^{\prime}\geq 1$. In round $t$, the environment generates a context $z_{t}\in\mathcal{Z}$. Then, the learner selects an action $x_{t}\in\mathcal{Q}$ and observes noisy feedback denoted by $y_{t}=g(z_{t},x_{t})+\varepsilon_{t}$. We assume that $g:\mathcal{Z}\times\mathcal{Q}\rightarrow\mathbb{R}$ and $\varepsilon_{t}$ is an $R$-sub-Gaussian noise. The $y_{t}$ is only observed after a random delay $d_{t}$, which is generated from an unknown distribution $\mathcal{D}$.

We refer to this new problem as ‘Contextual Gaussian process Bandits under Stochastic Delayed Feedback’ (CGB-SDF). The unknown function $g$, context space $\mathcal{Z}$, action space $\mathcal{Q}$, and unknown delay distribution $\mathcal{D}$ identify an instance of the CGB-SDF problem. The optimal action $x_{t}^{\star}$ for a given context $z_{t}$ is the action where the function $g$ has its maximum value, i.e., $x_{t}^{\star}=\arg\!\max_{x\in\mathcal{Q}}g(z_{t},x)$. The learner incurs a penalty of $\left(g(z_{t},x_{t}^{\star})-g(z_{t},x_{t})\right)$ for a context $z_{t}$ and action $x_{t}$. We aim to learn a policy that achieves the minimum cumulative penalties or regret which is given by $\mathfrak{R}_{T}=\sum_{t=1}^{T}\left(g(z_{t},x_{t}^{\star})-g(z_{t},x_{t})\right)$.

Our goal is to learn a policy that has a small sub-linear regret, i.e., $\lim_{T\rightarrow\infty}{\mathfrak{R}_{T}}/T\rightarrow 0$. The sub-linear regret here implies that the policy will eventually select the optimal action for a given context. We have adapted our algorithms for the BO-SDF problem to the CGB-SDF problem and shown that they also enjoy similar sub-linear regret guarantees; see Appendix B for more details.

We compare with previous baseline methods that can be applied to BO-SDF problems after modifications. Firstly, we compare with standard GP-UCB (Srinivas et al., 2010) which ignores the delayed observations when selecting the next query. Note that GP-UCB is likely to repeat previously selected queries in some iterations when the GP posterior remains unchanged (i.e., if no observation is newly collected between two iterations). Next, we also compare with the batch BO method of asy-TS (Kandasamy et al., 2018) which, similarly to GP-UCB, ignores the delayed observations when using TS to choose the next query. Lastly, we compare with the batch BO methods of GP-BUCB (Desautels et al., 2014) and GP-BTS (Chowdhury & Gopalan, 2019) which handle the delayed observations via hallucination (Section 4). Following the suggestion from (Vernade et al., 2020), if not specified otherwise, we set $m$ to be $2\mu$ where $\mu$ is the mean of the delay distribution. However, this is for convenience only since we will demonstrate (Section 6.1) that our algorithms consistently achieve competitive performances as long as $m$ is large enough. Therefore, $\mu$ does not need to be known in practice. We defer some experimental details to Appendix C due to space constraint. Our code is released at https://github.com/daizhongxiang/BO-SDF.

We have developed algorithms for the BO problems with stochastic delayed feedback. In the following, we briefly review the papers relevant to our problem.

Batch BO. Batch BO is the closest BO setting to our BO-SDF problem. Many algorithms have been proposed for different variants of batch BO problems in the literature (Desautels et al., 2014; González et al., 2016; Daxberger & Low, 2017; Kandasamy et al., 2018; Gong et al., 2019; Chowdhury & Gopalan, 2019; Balandat et al., 2020). However, the delay in observing feedback observations in all these batch BO problems is fixed. Some batch BO algorithms are based on the UCB index (Desautels et al., 2014; Daxberger & Low, 2017), while some others are based on TS (Kandasamy et al., 2018; Chowdhury & Gopalan, 2019; Gong et al., 2019). The batch BO methods like ‘local penalization’ (González et al., 2016) and ‘fantasize’ (Balandat et al., 2020) can not work with stochastically delayed feedback and have no theoretical guarantees. All variants of batch BO problems can be treated as special cases of the BO-SDF problem by fixing the delays appropriately. Therefore, our UCB- and TS-based algorithms can be used for any batch BO problem.

Contextual Gaussian Process (GP) Bandits. Several prior works consider the availability of additional information to the learner before making the decision. This line of work is popularly known as contextual bandits (Li et al., 2010). It has many applications in advertising, web search, and e-commerce. In contextual bandits, the mean reward is a function of context and often parameterized (e.g., linear (Li et al., 2010; Chu et al., 2011; Agrawal & Goyal, 2013b), GLM (Li et al., 2017), or non-linear (Valko et al., 2013)). Contextual GP bandits model the posterior belief of a non-linear function using GPs (Krause & Ong, 2011). To the best of our knowledge, our work is the first to introduce stochastic delayed feedback into contextual GP bandits.

Stochastic Delayed Feedback. Due to several practical applications, some works have explored fixed or stochastic delayed feedback in the stochastic multi-armed bandits (MAB) (Slivkins, 2019; Lattimore & Szepesvári, 2020) which is a simpler sequential decision-making framework than BO. In the MAB literature, the problems ranging from known fixed delay (Joulani et al., 2013), unknown delay (Zhong et al., 2017), unknown stochastic delay (Vernade et al., 2017; Grover et al., 2018), and unknown delays in the adversarial setting (Li et al., 2019) are well-studied. The setting of the unknown stochastic delay is further extended to the linear bandits (Zhou et al., 2019; Vernade et al., 2020) which is closest to our BO-SDF problem. However, these works on linear bandits assume that the black-box function is linear and has binary feedback, which may not hold in real-life applications.

This paper has studied the Bayesian optimization (BO) problem with stochastic delayed feedback (BO-SDF). We have used Gaussian processes as a surrogate model for the posterior belief of the unknown black-box function. To exploit the information of queries with delayed feedback (i.e., incomplete queries) for updating the posterior mean function, we have used censored feedback that assigns the minimum function value (or ‘0’) to the delayed feedback. It discourages the learner from selecting the incomplete queries (or queries near them) when choosing the next query and hence leads to more efficient exploration.

We have proposed UCB- and TS-based algorithms for the BO-SDF problem and given their sub-linear regret guarantees. Interestingly, when delays are fixed in a certain way, batch BO becomes a special case of the BO-SDF problem. Hence, we can adapt our algorithms for the batch BO problem. We have shown that our algorithms are theoretically and empirically better and do not need the special initialization scheme required for the existing batch BO algorithms. We also extended our algorithms to contextual Gaussian process bandits with stochastic delayed feedback, which is in itself a non-trivial contribution.

As the learning environment keeps changing in real life, an interesting future direction will be considering the BO-SDF problem with a non-stationary function. We also plan to generalize our algorithms to nonmyopic BO (Kharkovskii et al., 2020b; Ling et al., 2016), high-dimensional BO (Hoang et al., 2018), private outsourced BO (Kharkovskii et al., 2020a), preferential BO (Nguyen et al., 2021d), federated/collaborative BO (Dai et al., 2020b, 2021; Sim et al., 2021), meta-BO (Dai et al., 2022), and multi-fidelity BO (Zhang et al., 2017, 2019) settings, handle risks (Nguyen et al., 2021b, a; Tay et al., 2022) and information-theoretic acquisition functions (Nguyen et al., 2021c, e), incorporate early stopping (Dai et al., 2019), and/or recursive reasoning (Dai et al., 2020a), and consider its application to neural architecture search (Shu et al., 2022a, b) and inverse reinforcement learning (Balakrishnan et al., 2020). For applications with a huge budget of function evaluations, we like to couple our algorithms with the use of distributed/decentralized (Chen et al., 2012, 2013a, 2013b, 2015; Hoang et al., 2016, 2019; Low et al., 2015; Ouyang & Low, 2018), online/stochastic (Hoang et al., 2015, 2017; Low et al., 2014; Xu et al., 2014; Yu et al., 2019b), or deep sparse GP models (Yu et al., 2019a, 2021) to represent the belief of the unknown objective function efficiently.

This research/project is supported by A*STAR under its RIE$2020$ Advanced Manufacturing and Engineering (AME) Industry Alignment Fund – Pre Positioning (IAF-PP) (Award A$19$E$4$a$0101$) and by the Singapore Ministry of Education Academic Research Fund Tier $1$.