Reinforced In-Context Black-Box Optimization

Thanks for your valuable and constructive comments. Below please find our responses.

Q1: Behavioral policy limitations

Thanks for your comment. RIBBO is more close to the domain of offline RL [1], which leverages pre-existing data without the need for further online data acquisition. The most similar offline RL algorithm to RIBBO is Decision Transformer [2]. It represents a paradigm of upside down RL [3,4], which casts the problem of RL as conditional sequence modeling and enhances the performance of the model by incorporating return-to-go tokens. This also provides explanation for the RIBBO's ability, which employs conditional sequence modeling and incorporates regret-to-go tokens. We have revised to add more explanation. Thank you.

[1] Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems. arXiv 2020

[2] Decision Transformer: Reinforcement Learning via Sequence Modeling. NeurIPS 2021

[3] Reinforcement Learning Upside Down: Don't Predict Rewards - Just Map Them to Actions. arXiv 2019

[4] RvS: What is Essential for Offline RL via Supervised Learning? ICLR 2022

Q2: Justification for RTG inclusion

Thanks for your question. As shown in Eq.(4), the training loss is defined as the next token prediction loss, which essentially constitutes a conditional generation task. The context data and RTG tokens constitute the conditions that guide the generation of subsequent sampled point. The inclusion of RTG enables RIBBO to automatically generate sequences of query points that are related to the user-desired regret. In fact, our comparison experiments with BC have clearly shown the benefit of including RTG. BC is an important baseline to underscore the significance of RTG tokens, because the only difference from RIBBO is that we do not feed RTG tokens for BC and train to minimize the BC loss in Eq.(2). The experimental results in Figure 2 demonstrate the superiority of RIBBO over BC. Further ablations on RTG tokens in Figure 3(c) and 3(d) have also shown the influence of RTG tokens on the model's performance.

Q3: Transferability across BBO problems

Good point! The transferability across BBO problems is implemented in an in-context manner. The context data, collected from the new problems, provides insights for understanding the problems at hand. These contexts are integrated to construct the inputs, thereby influencing the resulting sampled points for new problems. We have revised to add more explanation. Thank you.

Q4: BBOB experiment clarifications

The dimensionality of the BBOB problem is set to $10$, and the x-axis represents the number of evaluations conducted.

Q5: Hyperparameter sensitivity

We did ablations for some important hyperparameters of RIBBO, including the model size and the sampled subsequence length $\tau$ during training. Please see the details in Appendix F.

Q6: Literature review addition

Thanks a lot for pointing out this related work. We have revised to add some discussion about Opt-GAN in our revised version.

Thank you very much for your constructive suggestions, which have really helped improve our work. We hope that our response has addressed your concerns, but if we missed anything please let us know.

Thanks for your valuable and constructive comments. Below please find our responses.

Q1: The major limitation of RIBBO

The major limitation of this approach is the absence of a comprehensive explanation regarding the mechanisms of in-context learning and the convergence properties of the learned model. A mathematical theoretical analysis about the cumulative regret analysis and generalization analysis would be valuable for this work. Such insights will be useful for refining the algorithmic designs and enhancing overall performance. We have revised to highlight this limitation.

Q2: Use shaded region for plots?

Thanks for your suggestion. We actually tried to use shaded region in the plots, but the standard deviation for some algorithms is very large, which leads to overlapping shaded regions. The overlap results in color mixing and can alter the appearance of the original hues and render the plots visually chaotic. We will try to find more effective methods to represent the experimental results. Thanks anyway.

Q3: How to select the initial RTG

Benefiting from the proposed HRR strategy in Section 3.2, we suggest simply setting the RTG to 0 at each iteration (including the initial RTG). As the RTG represents the cumulative future regret, a value of 0 can make the algorithm able to balance exploration and exploitation automatically, which is also validated by the good empirical performance using this setting. The ablations about the influence of the RTG token are provided in Figure 3(c) and Figure 6(b), respectively.

Thank you very much for your positive review and constructive suggestions.

Q6: Comparison to meta-learning individual components

In our paper, we focus on training an end-to-end model using offline datasets and introduce RTG tokens to enhance the performance. Therefore, the most related baselines are those training an end-to-end model with offline datasets, e.g., BC and OptFormer, and thus we also only compared them.

Thanks to your suggestion, we have revised to conduct experiments against FSBO [1], a method that meta-trains priors for GP and is widely used as a baseline in the meta-learning BBO studies [2,3,4]. The results are shown in Figure 8 in Appendix H of the revised version. FSBO has inferior performance to both BO and RIBBO, which may be because the methodology of meta-training priors to model the landscape may suffer from highly heterogeneous landscapes, derived through a sequence of transformations in the BBOB test functions. Even worse, an inappropriate prior might potentially degrade performance. RIBBO is designed to learn the whole optimizer, which has a greater expressive capacity and enables it to perform better in such scenarios.

[1] Few-Shot Bayesian Optimization with Deep Kernel Surrogates. ICLR 2021

[2] Towards Learning Universal Hyperparameter Optimizers with Transformers. NeurIPS 2022

[3] Scalable Meta-Learning with Gaussian Processes. AISTATS 2024

[4] Pre-trained Gaussian Processes for Bayesian Optimization. JMLR 2024

Q7: RIBBO is frequently outperformed by GP-EI

In Appendix D, the experiments focus on cross-distribution generalization, where the same function family are excluded from the offline meta training set. The incorporation of inappropriate offline information from disparate function family may affect the performance, due to the heterogeneity among these function families. Despite this, RIBBO still manages to other end-to-end methods, e.g., BC and OptFormer, demonstrating its relative advantages. But as you indicated, generalization is a very important but challenging issue in the domain of meta-learning. In the future, it is a very interesting direction to develop more robust and generalizable optimizers.

Q8: When the new problems are more difficult, HRR leads to OOD RTGs

Yes, higher RTGs may occur in OOD when problems are more difficult. However, the model trained tends to exhibit a degree of tolerance to these OOD RTGs. A similar capacity is also noted in DT, where the return-to-go tokens are typically assigned values greater than those in the training datasets. OOD issues are a common problem in meta-learning and an interesting open challenge. Thanks for pointing out this, and we have revised to mention it in the future work.

Q9: The setting of $M$ and $T$ in the experiments

Thanks for your question. $M$ is set to 100,000 for synthetic functions and $150,000$ for rover problems. For HPO-B problems, it is 25,000. $T$ is set to $150$ for synthetic and rover problems, and 100 for HPO-B problems. We have revised to make them clear.

The results will be different as the size of training sets increases. In the experiments, we save the model per 100,000 steps during training and select the model with the smallest validation loss.

Q10: Why were the specific functions chosen

According to the properties of the BBOB functions, they are divided into $5$ categories, and we randomly selected one from each category for visualization. Thanks to your suggestion, we have revised to show the visualizations with the other test-functions in Figure 9 in Appendix I of the revised version.

Q11: RIBBO can be used to generate optimization trajectories satisfying a user-specified regret？

We are very sorry that we did not make it clear. As you indicated, it should be a positive correlation between the user-specified regret and the obtained regret. We have revised to make the statement more precise. Thank you very much.

Thank you very much for your constructive suggestions, which have really helped improve our work. We hope that our response has addressed your concerns, but if we missed anything please let us know.

Thanks for your valuable and constructive comments. Below please find our responses.

Q1: The comparison of regret-to-go and return-to-go

Good point! The benefit of using regret-to-go is its independence from a predetermined horizon length when using the HRR strategy, contrasting with the return-to-go method where the calculation is usually related to the product of the maximal achievable reward and the horizon length. Once established, the return-to-go is expected to decrease as the optimization progresses. Additionally, from the perspective of optimization, the cumulative regret provides a more meaningful measure of the performance (measuring the gap to the optimum), compared to the sum of $y$. Therefore, regret-to-go has been adopted as the preferred metric in the algorithm's design. Thanks to your suggestion, we have revised to add some discussion to make it clear. Thank you.

Q2: A comparison against DT as a baseline in the experiments should be provided

Thanks for your valuable suggestion. In fact, the comparison against DT using regret-to-go was provided in our paper. Figure 3(d) is a comparison between HRR and the naive regret updating strategy. The naive strategy in Section 3.2, is indeed the strategy used in DT, which specifies a desired performance as the initial regret $R_0$ and decreases it as $R_t = R_{t-1} - (y^*-y_t)$ using the regret at each iteration. The proposed HRR strategy consistently outperforms the naive strategy across the whole optimization stage, demonstrating the advantages of HRR over DT. We have revised this part to make it clearer. Thank you.

Q3: The assumption about the ''true'' optimum value

Yes, as you stated, the calculation of the regret-to-go tokens requires the ''true'' optimum value. In our experiments, we used the average of the best-observed values across the training tasks as a proxy for the optimum. Other ways may include using the maximum of the best-observed values across the training tasks.

Q4: Setting $R_t=0$ is executed in the ''exploitation regime''

Thanks for your comments. Setting $R_t=0$ will not purely exploit. As detailed in the final paragraph of Section 3.2, the immediate RTG tokens are designed to represent the performance based on cumulative regret over the future trajectories (i.e., $R_t=\sum_{t'=t+1}^T (y^* - y_{t'})$), rather than focusing solely on instantaneous regret $y^* - y_{t+1}$. Thus, setting the immediate RTG to $0$ inherently accounts for future regret, thereby enabling the algorithm to autonomously trade-off the exploration and exploitation.

Sampling the next query point $x_t$ is not only influenced by the RTG token, but also the previous history $(x_i, y_i, R_i)^{t-1}\_{i=0}$. The RTG token represents the goal that is intended to be achieved, while the historical data contains information about the problem. These elements are integrated to construct the inputs, influencing the resulting sampled point. Even if the RTG token is set to 0, implying a desire to sample the optimum, the short length of the history suggests limited knowledge about the problem, prompting the model to retain explorative behavior. As the history extends, suggesting a sufficient knowledge of the problem, the preference encoded by the RTG token shifts towards more greedy action.

The experiment in Table 2 has shown the variation of std of the output Gaussian head of $x$. The std is very large in the early stage and becomes small later, which demonstrates the ability to trade-off the exploration and exploitation. And we further examine the performance of RIBBO with different values of $R_t$. The results in Figure 6(b) show that setting to a value larger than $0$ will decrease the performance and converge to a worse value, validating the effectiveness of setting the immediate RTG as 0.

Q5: Comparison to BBO algorithm selection methods

Thanks for your suggestion. To our knowledge, there have been no meta-learning based BBO algorithm selection methods, that can choose appropriate BBO algorithms on the fly based on their historical performance on the meta-training set. Thus, we have revised to add the comparison with a simple yet commonly used bandit-based algorithm selection method, referred as Bandit. The probability of selecting the $i$-th algorithm in each iteration is proportional to $v_i + \sqrt{\frac{2*N}{n_i}}$, where $v_i$ is the average $y$ associated with the $i$-th algorithm, $n_i$ denotes the number of times the $i$-th algorithm has been chosen, and $N$ is the aggregate number of evaluations. The results are shown in Figure 8 in Appendix H of the revised version. The performance of Bandit is suboptimal, which may be because of the limited evaluation setting in our experiments. The evaluation allocation among different algorithms may waste evaluations on underperforming algorithms and thus result in worse overall performance.

I thank the authors for their detailed responses to my concerns and questions, and appreciate the author's efforts during the rebuttal. I increased my score for soundness based on the latest revision.

• Regarding Q2, I was referring to a comparison to DT with return-to-go tokens. I believe that such a comparison would be instructive, since the regret-to-go tokens are one of the main novelties of the paper. In its current form, I am not fully convinced by the arguments in favor of this approach.
• I appreciate that the authors mention that RIBBO requires a-priori knowledge of the true optimum before sampling the function. In my view, this is a major limitation of a method tackling black-box optimization, and I feel that this should be highlighted more prominently in the manuscript.
• I am not fully convinced by the given argument that the length of a history is a good proxy to determine if exploration was sufficient. This is clearly only the case if RIBBO is trained on data that is very similar to the test data. Furthermore, I still find this and the results in Appendix D, which show that RIBBO cannot robustly generalize across synthetic functions, concerning, and indicative of issues with the above points.

Based on these concerns, I am inclined to keep my current score.

Thanks for your valuable and constructive comments. Below please find our responses.

Q1: Generalize to new optimization problems

When applied to new optimization problems, the tuning of our method is executed in an in-context manner, with the model parameters being frozen. The context data collected from the optimization of new problems provides insights for understanding the problems at hand, and influences the resulting sampled points. It is hard to exactly judge how much context data is needed. A mathematical theoretical analysis about the cumulative regret analysis and generalization analysis can be helpful and is an interesting avenue for future work to explore. Thank you for your suggestion.

Q2: Run the algorithmic optimizer longer to get better solutions

Running the algorithmic optimizer longer typically enhances the quality of the obtained solutions. In our experiments, the behavior algorithms employed a consistent horizon to collect datasets, so we simply use the same horizon for inference. In the future, it is interesting to collect optimization histories with diverse horizons to serve as training datasets to enable the algorithmic optimizer to be robust to the horizon length. Further, we can incorporate the advanced length extrapolation techniques in transformer [1] to increase the inference horizon to obtain better solutions.

[1] Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation. ICLR 2022

Q3: Add local approximations methods as behavior algorithms

Yes, adding local approximations methods, such as gradient estimating techniques, can enhance our method. As outlined in Appendix B.2, the characteristics of the training datasets significantly affect the effectiveness of the model. It is recommended to utilize well-performing and diverse behavior algorithms for dataset generation. The integration of well-performing local approximation methods can increase the diversity of the datasets, thereby facilitating the development of a more potent learned model.

Thank you very much for your positive review and constructive suggestions. We have revised to add them as interesting future works, and will explore them in the future.