Nonmyopic Bayesian Optimization in Dynamic Cost Settings

Dear Reviewer aZur,

Thank you for raising the need for a comprehensive argument regarding the advantages of multi-step planning over single-step planning with optimism. We appreciate the opportunity to provide a more detailed explanation and address your concerns. To illustrate our position, consider the example of optimizing a 1D function using a myopic approach (UCB) and our non-myopic method with a 6-step lookahead, as shown in the figure below. The top row highlights the receptive field - the region of influence for decisions—which varies with the planning horizon. In the myopic setting (left), the receptive field is narrow, focusing on short-term gains, as indicated by the limited shaded region. In contrast, the non-myopic approach (right) extends the receptive field, enabling the method to account for longer-term outcomes.

Figure

Both methods operate within the same radius (depicted as the area between the two dashed lines in the top row), but the key difference lies in the non-myopic method’s broader receptive field. This expanded perspective allows the method to better anticipate and account for future rewards. In contrast, the myopic approach, while potentially equipped with prior knowledge of the global optimum, prioritizes immediate rewards. This short-term focus may prevent it from overcoming local valleys to reach the global optimum.

Secondly, in our experiments on synthetic functions, we conducted additional ablation studies to rigorously evaluate the effectiveness of non-myopic planning under varying initial conditions and kernel choices. Additionally, we analyzed the impact of hyperparameter configurations for the UCB to demonstrate its susceptibility to local optima.

1. Number of Initial Samples: We investigated the effect of varying the number of initial samples on the optimization process. Our results show that with fewer initial points, the surrogate model struggles to approximate the ground-truth function accurately, increasing the likelihood of suboptimal outcomes across all methods. Figure for different inital samples

2. Kernel Choices: To assess the influence of the surrogate model’s kernel on performance, we evaluated different kernel functions, including the RBF kernel and the Matern kernel with $\nu = 1.5$. With this ablation, we can observe that with any well-fitted kernels, the nonmyopic approach can achieve the global optimum. Figure of RBF kernel Figure of Matern kernel

3. Hyperparameter Configurations for Baselines: We explored various settings for the $\beta$ parameter in UCB, which governs the trade-off between exploration and exploitation. The findings indicate that despite tuning, UCB frequently becomes trapped in local optima due to its myopic nature. For other acquisition functions (SR, PI, KG, EI, MSL), hyperparameters directly influencing this balance are absent, so no additional experiments were conducted for these methods.

Visualization for UCB

Metrics for UCB -- From the noon and in counter-clockwise: Ackley, Alpine and SynGP

Thirdly, regarding your concerns about the integration of cost functions into other baselines, we provide the following clarifications. Our optimization objective is presented in line 188. In our experiments, we set $\lambda = 1$ for consistency, though in real-world applications, $\lambda$ is scenario-dependent, reflecting human preferences and contextual constraints. For a fair comparison with other methods, we incorporated cost constraints into their respective acquisition functions. Specifically, their optimization objectives of EI, PI, SR, and UCB are adapted to:

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(f)} [\ell(f, x)] + \lambda c(x_{1:t}, x) \right],

$

and that of KG is

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(y | x)} [ \inf_{a \in \mathcal{A}} { \mathbb{E} _{p _{t+1}(f)} \ell(f, a)] + \lambda c(x_{1:t}, x, a) } \right].

$

This ensures that both myopic and non-myopic methods consider cost constraints in the optimization process. Our problem focuses on optimizing for the global maximum. Therefore, we use the final observed value in synthetic experiments and Bayesian regret in protein experiments as our evaluation metrics. Each experiment is given a fixed budget and will be terminated if the costs exceed the given budget.

Question 8: How does the regret reflect the cost of the chosen protein? That is, in what sense does the cost function c affect the outcome of the empirical evaluation at all?

Answer 8: In this experiment, we use the spotlight cost, which means that any edit not within the constraint incurs an infinite cost. We handle this cost by using regeneration, ensuring that all generated candidate proteins satisfy the constraint of having an edit distance equal to 1. As a result, the spotlight cost is effectively zero and does not impact the LLM optimization. Therefore, the reported regret solely indicates the quality of the generated proteins.

Question 9: It is not clear to me how the authors optimize the variational objective with the non-Bayesian LLM in this setting. Can the authors clarify in more detail how this is related to the algorithm proposed in the main text?

Answer 9: Thank you for your question. We use a variational network, i.e. a policy, and not a variational objective. The role of the neural network $\xi$ is to propose a new candidate: $\xi: (x \_{1:t}, y \_{1:t}) \mapsto x_{t+1}$, where $x_t$ represents the chosen protein at step $t$. Because the protein space is discrete, we cannot directly use equation (2) (line 256). Instead, we leverage the REINFORCE algorithm to optimize the neural network policy. We provide details of our objective function in line 269, where $\log p_t(x_{l+1} | x_{1:l}, \xi)$ is the log probability of the generated protein sequence from the neural network (which is differentiable), and $\text{EHIG} \_t(x \_{1:l+1})$ is the objective value computed by the surrogate model.

Question 10: It is mentioned that steps sometimes "fail" (line 494). Can the authors elaborate what is meant by this and clarify how often it fails for each of the discussed baselines?

Answer 10: The failure we mentioned in line 494 is that the LLM failed to generate a new sequence that satisfies the spotlight cost constraints (2 types of amino acids at 12 positions). For example, the LLM might be hallucinated or not follow the instructions so that it generates a sequence with a third amino acid (which is not in the allowed set) or it edits at the wrong position. In these cases, we re-generate the sequence again. Using a more robust LLM (such as LLama with 70B parameters) might not face these issues. However, to balance our computational budget, or in real use cases where computation is limited, we use Llama-3.2 3B, thus we have to deal with these issues.

Question 11: The paper provides no details on how the baselines are evaluated in this setting. Can the authors clarify this? In particular, can the authors clarify how "uncertainty" is measured in this context when we do not have a Bayesian model (as in the case of Llama-3.2). Or is a Bayesian linear regression uses, in which case I wonder how this can be compared to the Llama-3.2 policy network used in the proposed approach?

Answer 11: The baseline methods used in this study are based on myopic objectives, and we experimented with various myopic baselines employing different heuristics, such as UCB and Expected Improvement (EI). In all baseline methods, we used a policy network since traditional discrete Bayesian optimization is not suitable for this setting. Specifically, we utilized Bayesian linear regression as a surrogate model, which takes the embedding of newly generated proteins to predict the distribution of fluorescence levels. The acquisition function then uses this distribution to compute the acquisition value. For example, UCB computes the mean and standard deviation from this distribution to obtain the acquisition value, which is subsequently used as the reward for optimizing the neural network policy using the REINFORCE algorithm, as previously explained. The Llama-3.2 3B serves as the neural network policy, generating the next candidate protein based on previous proteins and fluorescence values. By sampling from the output distributions of the neural network policy, we obtain different output proteins. If some proteins do not satisfy the constraints of edit distance, we perform sampling again (as explained above). You can find more about our implementation at this anonymized Github: https://anonymous.4open.science/r/nonmyopia

Question 4: Given that predictions of an LLM are used as the "ground-truth" fluorescence levels, could the protein sequence with large edit distance (Figure 4) be outliers / wrong predictions of the LLM? Otherwise, what are alternative explanations for the S-shaped curve in Figure 4?

Answer 4: We would like to clarify as follows. In this experiment, our goal is to demonstrate that our method can be applied to real-world applications, especially complex, semantically-rich tasks like protein design with various constraints while balancing our available computational budget. For details, we start with an arbitrary protein sequence and mutate it at 12 positions with 2 amino acids each, resulting in a protein space of 4096 proteins for this experiment. We assign the reward value for each protein as the fluorescence value. Since we do not involve wet-lab testing, to obtain the fluorescence value for these proteins, we build a simple Bayesian linear regression model on a large protein fluorescence dataset (ProteinEA, https://huggingface.co/datasets/proteinea/fluorescence) and use it as the oracle (i.e., the ground-truth reward function). Originally, the space constructed using the oracle is nearly convex, which means any optimization methods (including myopic and non-myopic ones) can achieve the global optimum. This, however, does not showcase the power of non-myopic methods. Thus, we add a synthetic function $g(x)$ to the ground-truth reward (the predicted fluorescence from the oracle) to achieve the S-shaped curve shown in Figure 4. The S-curve includes one local mode, which can act as a trap for myopic methods, as they are optimized to achieve immediate rewards. Our method, however, tolerates lower immediate rewards to escape the local mode and achieve the global optimum. Moreover, we also include more protein experiments with a different starting protein and a different S-curve (including 2 local modes) to demonstrate the robustness of our method. In these two additional experiments, our method with lookahead capacity outperformed the other ones.

Same starting protein, different $g(x)$ with 2 local modes

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Different starting protein, same $g(x)$

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Question 5: How are the hyperparameters chosen? Are they chosen on the validation set over which is also optimized?

Answer 5: Some hyperparameters in our experiment are the number of lookahead steps and re-generation times. They were selected to balance our computational budget and optimization effectiveness. For instance, although a larger number of lookahead steps could be chosen, generating longer sequences with an LLM is very costly due to its quadratic complexity. We set the number of BO steps to at least 12, as the starting protein needed at least 12 edits to reach the global maximum. We chose 16 steps to provide a buffer for potential errors during the complex optimization process with the LLM.

Question 6: Why is the edit distance represented in the reward value (via g) and not only in the cost?

Answer 6 Thank you for the question. We realize our writing in the paper might have been confusing. We want to clarify that the function $g$ is chosen to be the oracle blackbox function, which depends on the edit distance to emulate the dynamic cost setting. By incorporating the edit distance into the reward value, $g$ effectively captures the relationship between modifications and their impact on the optimization process, providing a more realistic evaluation in a dynamic cost environment.

Question 7: How is λ chosen?

Answer 7: The $\lambda$ value is set to 1 in all of our synthetic experiments. In the protein experiment, the cost is spotlight cost and managed through re-generation, so we do not specify $\lambda$ in this context. In practice, the $\lambda$ value depends on various real-world factors and human preferences and should be determined on a case-by-case basis. For instance, when deciding on the best place to live, one might start by exploring nearby locations or opt to move to a distant place, depending on budget constraints and personal preferences.

Regarding your questions, we address them below:

Question 1: The paper discusses the idea of "pathwise sampling" in lines 276-. Can the authors clarify how this approach of sampling a function from the probabilistic model and then optimizing a sequence of steps over this (now fixed) function is different from trajectory sampling [1] used in PETS, with similar ideas being used in model-based RL with PILCO [2]?

Answer 1: We thank you for your question and the opportunity to clarify the idea of pathwise sampling. Regarding your concerns about the differences between the pathwise sampling approach discussed in the paper with trajectory sampling used in PETS and PILCO, the PE-TS paper presents an approach to modeling both aleatoric and epistemic uncertainty during planning. This method involves training multiple probabilistic neural networks using bootstrapped subsets of the observed data points. At each step, it initializes a number of particles (corresponding to the number of probabilistic neural networks) and assigns each particle to a probabilistic neural network for planning.

• The PILCO paper uses trajectory sampling to address the issue of model bias in model-based reinforcement learning. Model-based methods often suffer from model bias, where the learned dynamics model may not accurately represent the real environment. By using trajectory sampling, PILCO incorporates model uncertainty into long-term planning, thereby reducing the impact of model bias.

• Our method, however, leverages Thompson sampling, aiming to balance exploration and exploitation during planning. At each step, a posterior sample is drawn from the posterior distribution, as modeled by the surrogate probabilistic model, to guide the planning process. To improve efficiency, we adopt pathwise sampling [PathwiseSampling] for generating posterior samples, which circumvents the computational inefficiencies of traditional posterior sampling methods. By employing Thompson sampling in conjunction with pathwise sampling, our approach not only exploits knowledge from the current observed data but also preserves the exploratory capacity required for effective planning under uncertainty.

Question 2: Why did the authors choose 64 restarts? Are the results meaningfully different with a different number of restarts? Requiring such a large number of restarts seems like a drawback of the proposed approach. Moreover, it would benefit the manuscript to explain what is meant by a "restart"; I assume it refers to starting the optimization process from multiple initial conditions.

Answer 2: Thank you for the question. We use 64 restarts based on our computational budget. Restarting involves repeating the optimization process multiple times under the same conditions (i.e., initial points and surrogate model), which enhances robustness and ensures a more comprehensive exploration of the solution space. This technique is also employed in AlphaFold2 to identify the global optimal structure of proteins [AlphaFold_Multimer]. More restart generally leads to better performance, and we can afford 64 restarts in our experimental setting. In our implementation, we facilitate batching to handle the restarts. Specifically, with the current $x_t$, we expand it to a vector for a batch of 64 restarts and perform the same optimization procedure. This ensures robustness and increases the likelihood of finding the global optimum.

Question 3: It is mentioned that the MSL method is not applicable to "real-world" tasks and referred to Section 4.2 (line 395), but I do not find any reference to MSL in the following.

Answer 3: Thank you for the question. Typically, MSL assumes optimization directly on continuous input variables, which limits its applicability to real-world tasks such as protein design, where variables are discrete. Indeed, in Section 4.2, we elaborate on the protein design task, where the decision involves choosing which amino acid to mutate and which amino acid to mutate to. Even for a moderate-sized 300-token protein sequence and a myopic decision method, there are $300 \times 20$ options for a single decision. For a $T$-step lookahead, there are $(300 \times 20)^T$ discrete options, which is a scale at which many discrete optimizers required by MSL are likely to fail. Fortunately, these options exist in a semantic space, meaning that options similar to others are likely to have similar black-box outputs. Our approach exploits this by extending MSL with a variational network, allowing for efficient optimization in settings involving discrete variables.

References:

[AlphaFold_Multimer] Evans, Richard, et al. "Protein complex prediction with AlphaFold-Multimer. 2022; bioRxiv doi: 10 March 2022, https." doi. org/10.1101/2021.10 4.

[PathwiseSampling] Wilson, James T., et al. "Pathwise conditioning of Gaussian processes." Journal of Machine Learning Research 22.105 (2021): 1-47.

Regarding the minor points related to the DAD paper, we appreciate the reviewer’s suggestions and have corrected the reference citation. We also clarify the distinctions between the DAD method [DAD] and our approach:

1. Dynamic Cost Consideration: The DAD method does not account for dynamic costs, which limits its applicability to cost-constrained problems, such as protein design with restricted editing positions and amino acid choices. In contrast, our work specifically addresses non-myopic planning in dynamic cost settings, where the cost structure depends on specific problem. This capability is crucial for applications requiring adaptive optimization under such constraints.

2. Policy Network Adaptability: In the DAD method, the policy network $\pi_\theta$ is pre-optimized and remains fixed during the design process. This static policy is a significant limitation in dynamic cost settings, where the cost for subsequent queries depends on earlier queries. In contrast, our method adapts the policy network iteratively, allowing for accurate and effective planning in scenarios with evolving cost constraints.

Regarding concerns about our choice of surrogate models in synthetic settings, particularly the omission of Bayesian linear regression, it is important to note that this model is inherently limited to linear surface modeling. In our experiments, the synthetic settings involve a non-linear target function, making Bayesian linear regression unsuitable for accurately approximating the ground truth. To demonstrate this limitation, we compared the posterior surface generated by Bayesian linear regression with those of other kernel-based methods, as shown in the figure below. These results confirmed its inadequacy, leading us to exclude it from our ablation study.

Figure of posterior surfaces with different kernels

References: [DAD] Foster, Adam, et al. "Deep adaptive design: Amortizing sequential Bayesian experimental design." International conference on machine learning. PMLR, 2021.

Regarding your questions, we address them below:

Questions 1: Around line 100, the authors mentioned the synthetic functions “requiring 10 to 20 planning steps to find the global optimum”. How does one determine this number for a function?

Answer 1: In synthetic settings, we estimate the number of planning steps based on the spotlight radius. Specifically, we compute the distance between the initial point and the maximum point, then divide this distance by the spotlight radius. In practical use cases, with a good prior, we can estimate the number of planning steps in a similar manner. For example, in the case of delivering packages without knowing the exact map, a delivery man can estimate the distance between their current location and the target location based on their prior knowledge (e.g., having traveled to nearby locations before).

Questions 2: In the protein sequence experiment, how did the authors arrive at the specific form for g(x) (line 459)?

Answer 2: We design the function $g(x)$ by hand, aiming to find a non-convex function with one local mode to demonstrate the benefits of lookahead optimization. Specifically, myopic methods might have some information about the global mode, but their acquisition functions are optimized to receive the highest reward at the next step. This limitation prevents them from escaping the local mode. In contrast, our method, when it has signals of the global mode, can tolerate lower rewards in intermediate steps to achieve a higher reward in the end. Additionally, we have included more protein experiments with a different starting protein and a different S-curve (including 2 local modes) to demonstrate the robustness of our method. In these two additional experiments, our method with lookahead capacity outperformed the other ones.

Same starting protein, different $g(x)$ with 2 local modes

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Different starting protein, same $g(x)$

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Questions 3: Can the authors provide more details regarding using Llama-3.2 3B as the variational network (line 483)?

Answer 3: We employ Llama-3.2 3B as the variational network, conceptualizing the optimization process as a dialogue between the protein designer and the LLM. In this setup, the protein designer provides the Llama model with protein(s) and corresponding reward(s) (e.g., fluorescence levels) in the previous time step(s) and requests it to modify the latest protein to enhance its properties. We chose Llama-3.2 3B due to its robustness in following instructions and our limited computational budget. Its smaller size allows us to perform experiments more efficiently, and its ability to follow instructions carefully makes it easier to add constraints, such as limiting the number of possible amino acids. To acclimate the Llama model to the protein editing task, we conducted additional supervised fine-tuning before initiating the optimization process. Further details about this experiment are available in Appendix B. More information about our implementation can be found at this anonymized GitHub repository: anonymous.4open.science/r/nonmyopia.

Dear Reviewer h4kf,

Thank you for your valuable feedback. We would like to address the weaknesses and your questions below.

First, regarding the inclusion of additional lookahead baselines mentioned in [1, 2, 3], we are currently working on analyzing these methods and will add more details later.

Regarding [4], the primary difference between our approach and the one proposed in [4] lies in the integration of pathwise sampling and a variational network. While [4] introduces a cost-constrained lookahead acquisition function similar to ours, it does not incorporate pathwise sampling. Without pathwise sampling, the number of samples at each step grows exponentially. Additionally, without the variational network, the number of optimizing parameters also grows exponentially, which is intractable in settings requiring a large lookahead horizon. By integrating pathwise sampling and a variational network, our method significantly reduces computational complexity. This allows us to optimize language models for more complex practical tasks, addressing limitations that prior nonmyopic methods, including the one in [4], still face. We will include these analyses in the rebuttal revision.

Secondly, regarding the analysis of lookahead effects, we have included experimental results on the ablation of the number of lookahead steps. Specifically, we experimented with the MSL baseline and our method using 5-, 10-, and 15-step lookahead on three synthetic functions: Ackley, Alpine, and SynGP. These results illustrate the relationship between the number of lookahead steps and the robustness of the optimization, providing insights into how the performance of our approach varies with different horizon lengths. Notably, with a larger lookahead horizon, the chance of finding the global optimum increases.

Figure of ablation study on lookahead horizon

Our problem setting focuses on optimizing within a known and dynamic cost setting, which is an important cost structure in many practical applications as we motivated earlier. Previous literature has developed methods for complementary-but-distinct cost settings, and we believe that those methods are not suitable for the setting studied in this paper. We elaborate on our position further below by analyzing the cost structure of the suggested papers:

• The papers “Multi-step budgeted Bayesian optimization with unknown evaluation costs”, “A nonmyopic approach to cost-constrained Bayesian optimization”, and “Adaptive cost-aware Bayesian optimization” address cost structures characterized by unknown, heterogeneous costs. For instance, in the hyperparameter optimization (HPO) problem studied in these papers, the cost of evaluating a hyperparameter set (i.e., training the target model with that set) is unknown but static for a particular model and a set of hyperparameters and does not depend on previously chosen sets.

• The paper “Bayesian optimization over iterative learners with structured responses: A budget-aware planning approach” also incorporates an unknown, heterogeneous cost structure. The key distinction from the previously mentioned works is the inclusion of an additional cost factor: the number of training epochs for evaluating a hyperparameter set. In this context, for a given location $x$ (a set of hyperparameters) and a specific number of training epochs, the cost is unknown but fixed, as it does not depend on prior queries (previously chosen sets of hyperparameters) or prior choices of training epochs.

• Finally, the papers “Practical two-step lookahead Bayesian optimization”, “Bayesian optimization for dynamic problems”, and “Bayesian optimization with a finite budget: An approximate dynamic programming approach” focus on Bayesian optimization without accounting for cost structures. These works implicitly assume that all locations in the search space have the same, constant, and known cost. This implies that the cost is either zero or any fixed constant and, therefore, not subject to optimization.

Based on the above evidence, the settings in these works are fundamentally different from ours.

Regarding the non-myopic methods presented in the suggested papers [1–4], these approaches extend the Expected Improvement acquisition function to address non-myopic optimization challenges. While they provide valuable insights, these methods directly optimize free variables in a multi-step tree (MST), which introduces an exponential increase in the number of optimization variables as the lookahead horizon grows. In our context, incorporating their lookahead mechanisms would amount to combining a multi-step tree structure with a dynamic cost function, an approach that is already benchmarked in our work. The optimization objectives of these lookahead methods, once adapted, align with Equation (1) (lines 188–190) in our paper. Our planning algorithm distinguishes itself from the literature by integrating a policy neural network. In the context of this paper on the dynamic and known cost setting, we believe that our experiments have sufficiently benchmarked the previous planning strategy presented in the suggested papers. We are eager to hear the reviewer's thoughts on this to further improve our work and welcome any specific suggestions from the reviewer on how to incorporate the related nonmyopic BO methods as additional baselines for our setting. We again thank you for your thoughtful questions and we look forward to hearing more from you.

References: [1] Astudillo, R., Jiang, D., Balandat, M., Bakshy, E., & Frazier, P. (2021). Multi-step budgeted bayesian optimization with unknown evaluation costs. Advances in Neural Information Processing Systems, 34, 20197-20209.

[2] Lee, E. H., Eriksson, D., Perrone, V., & Seeger, M. (2021, December). A nonmyopic approach to cost-constrained Bayesian optimization. In Uncertainty in Artificial Intelligence (pp. 568-577). PMLR.

[3] Belakaria, S., Doppa, J. R., Fusi, N., & Sheth, R. (2023, April). Bayesian optimization over iterative learners with structured responses: A budget-aware planning approach. In International Conference on Artificial Intelligence and Statistics (pp. 9076-9093). PMLR.

[4] Jian Wu and Peter Frazier. Practical two-step lookahead Bayesian optimization. Advances in neural information processing systems, 32, 2019

[5] Nyikosa, F. M., Osborne, M. A., & Roberts, S. J. (2018). Bayesian optimization for dynamic problems. arXiv preprint arXiv:1803.03432.

[6] Lam, R., Willcox, K., & Wolpert, D. H. (2016). Bayesian optimization with a finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29.

[7] Luong, P., Nguyen, D., Gupta, S., Rana, S., & Venkatesh, S. (2021). Adaptive cost-aware Bayesian optimization. Knowledge-Based Systems, 232, 107481.

Thank you for your feedback on the related works concerning non-myopic Bayesian optimization methods for dynamic cost settings. We appreciate the opportunity to clarify the relation between our work and the previous ones in terms of the cost structure. To facilitate the discussion, we survey the prior literature on the topic broadly and come up with a taxonomy based on two factors of the cost function: uncertainty and variability.

• In terms of uncertainty, costs can be classified as known or unknown prior to making a decision. When the cost is unknown, it can be viewed as a random variable that can be modeled probabilistically.

• In terms of variability, the cost structure can be categorized into dynamic costs, which vary based on the query history, and static costs, which remain fixed for a particular query over time. We note that when the cost is static, the BO community also studies two variations of this structure: heterogeneous cost and homogeneous cost. Homogeneous cost is the setting where the cost of all queries is the same, whereas heterogeneous cost is the setting where the cost of a query is a function of the query itself.

Using this taxonomy, we classify the literature into four categories, as shown in the table below.

To further illustrate the distinction between cost structures, we visualize the uncertainty and variability of these structures as probabilistic graphical diagrams below. In these diagrams, $f$ represents the target black-box function, $x$ denotes the input query, $y$ is the output value, and $c$ is the cost incurred by querying $x$. On the left — the dynamic-known cost structure — the cost of querying $x_3$ can depend on $x_1$ and $x_2$. On the right — the static-unknown cost structure — the cost of querying $x_3$ is independent of other queries.

Comparison of cost structures

References:

[1] Astudillo, R., Jiang, D., Balandat, M., Bakshy, E., & Frazier, P. (2021). Multi-step budgeted bayesian optimization with unknown evaluation costs. Advances in Neural Information Processing Systems, 34, 20197-20209.

[2] Lee, E. H., Eriksson, D., Perrone, V., & Seeger, M. (2021, December). A nonmyopic approach to cost-constrained Bayesian optimization. In Uncertainty in Artificial Intelligence (pp. 568-577). PMLR.

[3] Belakaria, S., Doppa, J. R., Fusi, N., & Sheth, R. (2023, April). Bayesian optimization over iterative learners with structured responses: A budget-aware planning approach. In International Conference on Artificial Intelligence and Statistics (pp. 9076-9093). PMLR.

[4] Jian Wu and Peter Frazier. Practical two-step lookahead Bayesian optimization. Advances in neural information processing systems, 32, 2019

[5] Nyikosa, F. M., Osborne, M. A., & Roberts, S. J. (2018). Bayesian optimization for dynamic problems. arXiv preprint arXiv:1803.03432.

[6] Lam, R., Willcox, K., & Wolpert, D. H. (2016). Bayesian optimization with a finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29.

[7] Luong, P., Nguyen, D., Gupta, S., Rana, S., & Venkatesh, S. (2021). Adaptive cost-aware Bayesian optimization. Knowledge-Based Systems, 232, 107481.

Regarding your questions, we address them below:

Questions 1: What is the λ value assigned in the experiment? How to define this value in practice?

Answer 1: Currently, the $\lambda$ value is set to 1 in all of our synthetic experiments. In practice, the $\lambda$ value depends on various real-world factors and human preferences and should be determined on a case-by-case basis. For instance, when deciding on the best place to live, one might start by exploring nearby locations or opt to move to a distant place, depending on budget constraints and personal preferences. In the protein design experiment, we use the spotlight cost, which means that any edit not within the constraint incurs an infinite cost. We handle this cost by using regeneration (regenerate a new candidate protein if the current one fails to meet the spotlight cost constraint, line 493-496), ensuring that all generated candidate proteins satisfy the constraint of having an edit distance equal to 1. Thus, we do not specify the $\lambda$ for this experiment.

Question 2: In protein design experiment, the optional actions are restricted to 2 amino acid in each edited position. Why not use all 4 amino acid as candidate actions?

Answer 2: Currently, to balance between demonstrating the robustness of our method and our computational budget, we restrict the actions to 2 amino acids and 12 positions. This setup ensures that there is only one possible protein with the highest reward after 12 edits, imposing stricter constraints and requiring the method to be robust enough to find the global optimal solution. Allowing 4 amino acids per position could result in multiple proteins with the highest reward, making the problem easier. Moreover, our setting is closer to practical situations where amino acids are often replaced with those in the same group (e.g., having the same negative electric charge) to maintain protein functionality. We also performed two more protein design experiments with a different starting protein and a different synthetic function (with 2 local modes) as presented above. You can find more about our implementation at this anonymized Github: https://anonymous.4open.science/r/nonmyopia

Dear Reviewer 5XvL,

Thank you for your insightful feedback. In response to the weaknesses highlighted, we have performed more experiments and added more detailed descriptions. First, one of the major concerns was the limited scope of real-world experiments. To address this, we have included additional results that expand on our previous work with protein design experiments. Specifically, we conducted experiments using a different starting protein and a distinct synthetic function (including two local modes) to demonstrate the flexibility, applicability, and robustness of our approach across various scenarios. In these two additional experiments, our method with lookahead capacity outperformed the others.

Same starting protein, different $g(x)$ with 2 local modes

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Different starting protein, same $g(x)$

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Moreover, we are working on human travel optimization problems using maps captured from NASA's Earth Observatory (https://earthobservatory.nasa.gov/features/NightLights). This problem involves optimizing in a human travel space, modeled as a 2D continuous domain, providing a realistic and complex scenario with a continuous action space. Another concern raised by the reviewers was the lack of comparison with existing methods that address optimization problems with dynamic costs. In response, we have incorporated dynamic cost constraints into all our baselines (SR, EI, PI, UCB, KG, MSL) for comparison. To ensure a fair and comprehensive comparison, we modified these methods to integrate cost constraints directly into their respective acquisition functions. Specifically, their optimization objectives of EI, PI, SR, and UCB are adapted to:

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(f)} [\ell(f, x)] + \lambda c(x_{1:t}, x) \right],

$

and that of KG is

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(y | x)} [ \inf_{a \in \mathcal{A}} { \mathbb{E} _{p _{t+1}(f)} \ell(f, a)] + \lambda c(x_{1:t}, x, a) } \right].

$

Using these objective functions, we ensured that all methods are under the same conditions, thus demonstrating the effectiveness of our method in terms of lookahead capacity. The baseline results in our paper are already derived from the modified methods as presented above.

Question 1: How does the performance of the proposed method change against baselines under increased batch sizes?

Answer 1: Thank you for your question. In the problem we are considering, at each BO step, the decision maker is allowed to make a single decision – which means the batch size is 1. Thus, all the methods we presented in our paper are designed to work with a batch size of 1. There is another term, batch size, used in the protein experiment in our paper, which might have caused some confusion. The term batch size in the protein design experiments refers to the batch size when fine-tuning the language model. This batch size is adjusted based on our computational budget and does not theoretically affect the proposed nonmyopic BO method.

Question 3: How do you evaluate the robustness of the proposed method with respect to the changes in reward function?

Answer 3: We conducted an ablation study focusing on different initial points for training the surrogate model. Our findings indicate that with a smaller number of initial points, all methods (both myopic and nonmyopic) exhibit reduced performance due to insufficient information or signals about the mode in the optimization space.

Figure for different inital samples

Question 4: Is the proposed approach flexible and generalizable? Can it work under different acquisition functions?

Answer 4: Yes, our approach is both flexible and generalizable. We demonstrated its versatility by implementing it with various acquisition functions, including Expected Improvement (EI), Probability of Improvement (PI), Simple Regret (SR), Upper Confidence Bound (UCB), Knowledge Gradient (KG), and Multi-step Tree, as detailed in the paper. Specifically, we replace the $\ell(\cdot)$ function with other acquisition functions. Specifically, their optimization objectives of EI, PI, SR, and UCB are adapted to:

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(f)} [\ell(f, x)] + \lambda c(x_{1:t}, x) \right],

$

and that of KG is

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(y | x)} [ \inf_{a \in \mathcal{A}} { \mathbb{E} _{p _{t+1}(f)} \ell(f, a)] + \lambda c(x_{1:t}, x, a) } \right].

$

Using these objective functions, we ensured that all methods are under the same conditions, thus demonstrating the effectiveness of our method in terms of lookahead capacity. The baseline results in our paper are already derived from the modified methods as presented above.

Question 5: Are the baselines other than the multistep tree implemented with a lookahead horizon=1 (myopic), is that right?

Answer 5: Other baselines (EI, PI, SR, UCB) are implemented as myopic approaches with a lookahead horizon equal to 0, which means these baselines optimize for immediate reward in the next step. The KG, which is equivalent to our approach without pathwise sampling and a variational network, is implemented with a lookahead horizon equal to 1. This means KG will look ahead for 1 step before making the final action. The mathematical optimization objectives of these baselines are presented as in the answer to the above question.

Regarding the ablation studies on the impact of different numbers of edits, we currently design the protein experiments to balance between demonstrating the effectiveness of our method and our computational budget. The number of edits required to reach the maximal reward protein is 12, so the number of BO steps must be at least 12. In practical scenarios, we will have a fixed, limited number of allowed steps. To make the experiment closer to a practical scenario, we assume that the maximal number of BO steps, ($T$), is 16. The results presented in our paper show that our method reaches the maximal protein at BO step 13, proving the effectiveness of our method. In short, setting the number of BO steps ($T$) larger than 16 is unnecessary in our case, and setting it smaller than 12 is inappropriate because of the problem setting.

In practical protein design, there might be cases where we need to edit more positions or allow more amino acids. These requirements do not increase the computational budget because the neural network we chose is an LLM, which has a fixed cost for generating any proteins of the same length. Regarding the number of BO steps, if we need to increase it due to a larger search space, the complexity increases linearly. This is because, with the same number of lookahead steps, all BO steps have the same complexity. In short, our proposed method is scalable for larger search space even in a complex, semantic-rich environment.

Nextly, we want to clarify our points about your concerns about BatchedBO, which is used in protein design. The idea of BatchedBO is sampling a batch of candidate protein simultaneously at each step using Thompson sampling. The difference between ours and BatchedBO is that we do not sample multiple $f$ instead we perform sampling when generating the sequences. For details, assuming the BatchedBO samples K $f$ at a BO step, then it computes the corresponding K generations. In our approach, we use LLM as the policy, thus the $f$ is the LLM’s parameters. Sampling multi $f$ in our case will be very costly and ineffective. Thus we perform sampling one $f$ and sampling when generation (using generation sampling techniques of LLM) and achieve the same number of K diverse generations. Doing this reduces the computational costs for generating candidate sequences.

To further demonstrate our applicability, we have included additional results on protein design experiments using a different starting protein and a different synthetic function with 2 local modes. Furthermore, we are working on human travel optimization problems using maps captured from NASA (https://earthobservatory.nasa.gov/features/NightLights). These additions help to illustrate the versatility and robustness of our approach across different real-world problem domains.

Same starting protein, different $g(x)$ with 2 local modes

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Different starting protein, same $g(x)$

Figure of distribution of fluorescence level
Observed fluorescence level and Bayesian regret across BO steps

Regarding your suggested similar work [5], the primary difference between our approach and the one proposed in [5] lies in the integration of pathwise sampling and a variational network. While [5] introduces a cost-constrained lookahead acquisition function similar to ours, it does not incorporate pathwise sampling. Without pathwise sampling, the number of samples at each step grows exponentially. Additionally, without the variational network, the number of optimizing parameters also grows exponentially. By integrating pathwise sampling and a variational network, our method significantly reduces computational complexity, leading to an increased lookahead horizon and a higher chance of finding the global optimum. This allows us to optimize language models for more complex, semantic-rich tasks, addressing limitations that prior nonmyopic methods, including the one in [5], still face.

• For minor representation mistakes: We thank the reviewer for pointing out the mistakes, and we have fixed them for the revision.

Dear Reviewer xEWL,

Thank you for your valuable feedback. We would like to address the weaknesses and your questions below.

Regarding your concerns about the quality of approximation of reward function (i.e. the surrogate model), we have included results from experiments with different numbers of initial points. Our findings indicate that with fewer initial points, the surrogate model struggles to accurately approximate the ground-truth function, which can lead to suboptimal optimization outcomes in all methods.

Figure for different inital samples

Regarding your concerns about the flexibility and generalizability of our method, we would like to clarify them in the following. Our proposed method can indeed be seen as a generalized version of other myopic baselines used in our paper. Specifically, the $\ell(\cdot)$ function in line 188 can be replaced with any other acquisition function. In our paper, we adapted other acquisition functions such as Expected Improvement (EI), Probability of Improvement (PI), Simple Regret (SR), Upper Confidence Bound (UCB), and Knowledge Gradient (KG). Their optimization objectives of EI, PI, SR, and UCB are adapted as follows:

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(f)} [\ell(f, x)] + \lambda c(x_{1:t}, x) \right],

$

and that of KG is

$

x = \arg \inf_{x \in \mathcal{X}} \left[ \mathbb{E} _{p_t(y | x)} [ \inf_{a \in \mathcal{A}} { \mathbb{E} _{p _{t+1}(f)} \ell(f, a)] + \lambda c(x_{1:t}, x, a) } \right].

$

Using these objective functions, we ensured that all methods are under the same conditions, thus demonstrating the effectiveness of our method in terms of lookahead capacity. The baseline results in our paper are already resulted from the modified methods as presented above.

Additionally, we have included experimental results on the ablation of the number of lookahead steps in the revised version. These results illustrate the relationship between the number of lookahead steps and the robustness of the optimization, providing insights into how the performance of our approach varies with different horizon lengths. Specifically, with a smaller lookahead horizon, the probability of being trapped by local optima increases, leading to suboptimal optimization in all nonmyopic methods.

Figure of ablation on lookahead steps

Subsequently, regarding the effect of the quality of the surrogate model on the optimization process, we provide details about the number of training samples in Section 4.1 (line 349). We have included additional ablation results from experiments that examine the impact of different numbers of initial points (as we presented above) and different kernel choices (RBF and Matern with $\nu=1.5$). Our findings indicate that a poor prior with a bad surrogate model can lead to suboptimal solutions in all methods. We also observe that with any well-fitted kernels, the nonmyopic approach can achieve the global optimum, while the myopic approaches still struggle.

Figure of RBF kernel Figure of Matern kernel

In our experiment, we utilize a large language model (LLM) to perform the protein editing task. Theoretically, it is possible to fine-tune the LLM to edit all positions with all amino acid types. However, in practical scenarios [1, 2], protein editing is often constrained to a few positions with a limited number of amino acid types at a time. To reflect these practical constraints, we limited the number of positions and amino acids in our experiment. Moreover, constrained generation with an LLM is more challenging than allowing the LLM to change all positions of the sequence. We addressed this issue by carefully supervised fine-tuning the LLM before running the optimization process.

[1] Kunkel, T. A. (1985). Rapid and efficient site-specific mutagenesis without phenotypic selection. Proceedings of the National Academy of Sciences, 82(2), 488–492. [2] Dalbadie-McFarland, G., Cohen, L. W., Riggs, A. D., Morin, M. J., Itakura, K., & Richards, J. H. (1982). Oligonucleotide-directed mutagenesis as a general and powerful method for studies of protein function. Proceedings of the National Academy of Sciences, 79(21), 6409–6413.

Regarding computational efficiency, we demonstrate theoretical improvements. Specifically, the use of a policy network reduces the complexity to $O(1)$ in terms of the number of optimizing parameters. In contrast, previous nonmyopic BO methods exhibit a complexity of $O(k^T)$, where $k$ is the number of sampling samples per BO lookahead step and $T$ is the number of lookahead steps (lines 232-237).

Additionally, Pathwise sampling further enhances efficiency. The complexity is reduced to $O(C+K)$, where $C$ is the number of queried points and $K$ is a constant. This marks a significant improvement over traditional Monte Carlo sampling methods, which have a complexity of $O(K m^3)$, with $m$ representing the number of inducing points.

You can find more about our implementation at his anonymized Github: https://anonymous.4open.science/r/nonmyopia

Our problem setting focuses on optimizing within a known and dynamic cost setting, which is an important cost structure in many practical applications as we motivated earlier. Previous literature has developed methods for complementary-but-distinct cost settings, and we believe that those methods are not suitable for the setting studied in this paper. We elaborate on our position further below by analyzing the cost structure of the suggested papers:

• The papers “Multi-step budgeted Bayesian optimization with unknown evaluation costs”, “A nonmyopic approach to cost-constrained Bayesian optimization”, and “Adaptive cost-aware Bayesian optimization” address cost structures characterized by unknown, heterogeneous costs. For instance, in the hyperparameter optimization (HPO) problem studied in these papers, the cost of evaluating a hyperparameter set (i.e., training the target model with that set) is unknown but static for a particular model and a set of hyperparameters and does not depend on previously chosen sets.

• The paper “Bayesian optimization over iterative learners with structured responses: A budget-aware planning approach” also incorporates an unknown, heterogeneous cost structure. The key distinction from the previously mentioned works is the inclusion of an additional cost factor: the number of training epochs for evaluating a hyperparameter set. In this context, for a given location $x$ (a set of hyperparameters) and a specific number of training epochs, the cost is unknown but fixed, as it does not depend on prior queries (previously chosen sets of hyperparameters) or prior choices of training epochs.

• Finally, the papers “Practical two-step lookahead Bayesian optimization”, “Bayesian optimization for dynamic problems”, and “Bayesian optimization with a finite budget: An approximate dynamic programming approach” focus on Bayesian optimization without accounting for cost structures. These works implicitly assume that all locations in the search space have the same, constant, and known cost. This implies that the cost is either zero or any fixed constant and, therefore, not subject to optimization.

Based on the above evidence, the settings in these works are fundamentally different from ours.

Regarding the non-myopic methods presented in the suggested papers [1–4], these approaches extend the Expected Improvement acquisition function to address non-myopic optimization challenges. While they provide valuable insights, these methods directly optimize free variables in a multi-step tree (MST), which introduces an exponential increase in the number of optimization variables as the lookahead horizon grows. In our context, incorporating their lookahead mechanisms would amount to combining a multi-step tree structure with a dynamic cost function, an approach that is already benchmarked in our work. The optimization objectives of these lookahead methods, once adapted, align with Equation (1) (lines 188–190) in our paper. Our planning algorithm distinguishes itself from the literature by integrating a policy neural network. In the context of this paper on the dynamic and known cost setting, we believe that our experiments have sufficiently benchmarked the previous planning strategy presented in the suggested papers. We are eager to hear the reviewer's thoughts on this to further improve our work and welcome any specific suggestions from the reviewer on how to incorporate the related nonmyopic BO methods as additional baselines for our setting. We again thank you for your thoughtful questions and we look forward to hearing more from you.

References: [1] Astudillo, R., Jiang, D., Balandat, M., Bakshy, E., & Frazier, P. (2021). Multi-step budgeted bayesian optimization with unknown evaluation costs. Advances in Neural Information Processing Systems, 34, 20197-20209.

[2] Lee, E. H., Eriksson, D., Perrone, V., & Seeger, M. (2021, December). A nonmyopic approach to cost-constrained Bayesian optimization. In Uncertainty in Artificial Intelligence (pp. 568-577). PMLR.

[3] Belakaria, S., Doppa, J. R., Fusi, N., & Sheth, R. (2023, April). Bayesian optimization over iterative learners with structured responses: A budget-aware planning approach. In International Conference on Artificial Intelligence and Statistics (pp. 9076-9093). PMLR.

[4] Jian Wu and Peter Frazier. Practical two-step lookahead Bayesian optimization. Advances in neural information processing systems, 32, 2019

[5] Nyikosa, F. M., Osborne, M. A., & Roberts, S. J. (2018). Bayesian optimization for dynamic problems. arXiv preprint arXiv:1803.03432.

[6] Lam, R., Willcox, K., & Wolpert, D. H. (2016). Bayesian optimization with a finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29.

[7] Luong, P., Nguyen, D., Gupta, S., Rana, S., & Venkatesh, S. (2021). Adaptive cost-aware Bayesian optimization. Knowledge-Based Systems, 232, 107481.

Thank you for your feedback on the related works concerning non-myopic Bayesian optimization methods for dynamic cost settings. We appreciate the opportunity to clarify the relation between our work and the previous ones in terms of the cost structure. To facilitate the discussion, we survey the prior literature on the topic broadly and come up with a taxonomy based on two factors of the cost function: uncertainty and variability.

• In terms of uncertainty, costs can be classified as known or unknown prior to making a decision. When the cost is unknown, it can be viewed as a random variable that can be modeled probabilistically.

• In terms of variability, the cost structure can be categorized into dynamic costs, which vary based on the query history, and static costs, which remain fixed for a particular query over time. We note that when the cost is static, the BO community also studies two variations of this structure: heterogeneous cost and homogeneous cost. Homogeneous cost is the setting where the cost of all queries is the same, whereas heterogeneous cost is the setting where the cost of a query is a function of the query itself.

Using this taxonomy, we classify the literature into four categories, as shown in the table below.

To further illustrate the distinction between cost structures, we visualize the uncertainty and variability of these structures as probabilistic graphical diagrams below. In these diagrams, $f$ represents the target black-box function, $x$ denotes the input query, $y$ is the output value, and $c$ is the cost incurred by querying $x$. On the left — the dynamic-known cost structure — the cost of querying $x_3$ can depend on $x_1$ and $x_2$. On the right — the static-unknown cost structure — the cost of querying $x_3$ is independent of other queries.

Comparison of cost structures

References:

[1] Astudillo, R., Jiang, D., Balandat, M., Bakshy, E., & Frazier, P. (2021). Multi-step budgeted bayesian optimization with unknown evaluation costs. Advances in Neural Information Processing Systems, 34, 20197-20209.

[2] Lee, E. H., Eriksson, D., Perrone, V., & Seeger, M. (2021, December). A nonmyopic approach to cost-constrained Bayesian optimization. In Uncertainty in Artificial Intelligence (pp. 568-577). PMLR.

[3] Belakaria, S., Doppa, J. R., Fusi, N., & Sheth, R. (2023, April). Bayesian optimization over iterative learners with structured responses: A budget-aware planning approach. In International Conference on Artificial Intelligence and Statistics (pp. 9076-9093). PMLR.

[4] Jian Wu and Peter Frazier. Practical two-step lookahead Bayesian optimization. Advances in neural information processing systems, 32, 2019

[5] Nyikosa, F. M., Osborne, M. A., & Roberts, S. J. (2018). Bayesian optimization for dynamic problems. arXiv preprint arXiv:1803.03432.

[6] Lam, R., Willcox, K., & Wolpert, D. H. (2016). Bayesian optimization with a finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29.

[7] Luong, P., Nguyen, D., Gupta, S., Rana, S., & Venkatesh, S. (2021). Adaptive cost-aware Bayesian optimization. Knowledge-Based Systems, 232, 107481.