BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RL

Authors: Yu Heng Hung, Kai-Jie Lin, Yu-Heng Lin, Chien-Yi Wang, Cheng Sun, Ping-Chun Hsieh
Primary area: reinforcement learning
Keywords: Multi-Objective Bayesian Optimization, Transformers, Hyperparameter Optimization, Reinforcement Learning, Acquisition Function

Abstract:
Bayesian optimization (BO) offers an efficient pipeline for optimizing black-box functions with the help of a Gaussian process prior and an acquisition function (AF). Recently, in the context of single-objective BO, learning-based AFs witnessed promising empirical results given its favorable non-myopic nature. Despite this, the direct extension of these approaches to multi-objective Bayesian optimization (MOBO) suffer from the hypervolume identifiability issue, which results from the non-Markovian nature of MOBO problems. To tackle this, inspired by the non-Markovian RL literature and the success of Transformers in language modeling, we present a generalized deep Q-learning framework and propose BOFormer, which substantiates this framework for MOBO via sequence modeling. Through extensive evaluation, we demonstrate that BOFormer constantly achieves better performance than the benchmark rule-based and learning-based algorithms in various synthetic MOBO and real-world multi-objective hyperparameter optimization problems.

Decision: accept (poster)
Reviewer scores: 5, 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730321236286

thread_type:
official_review

<thread_object>
creator: reviewer_uwnd

<content>
summary:
This paper introduces BOFormer, a learning-based approach for Multi-Objective Bayesian Optimization (MOBO). The key idea is to replace the traditional handcrafted acquisition function with a Transformer-based network trained through non-Markovian reinforcement learning. The authors claim that MOBO is inherently non-Markovian due to the "hypervolume identifiability issue" and propose a generalized DQN framework incorporating historical information. The method is evaluated on both synthetic functions and real-world hyperparameter optimization tasks.

strengths:
* While there are several existing works on meta-learned acquisition functions for single-objective BO, BOFormer is the first work to apply a learning-based acquisition function to MOBO.
* The domain-agnostic representation, which only incorporates historical query information rather than maintaining information for all domain points, enables cross-domain transfer while being memory-efficient.
* Well-structured related work with clear categorization of existing approaches and insightful comparison with similar works, especially in distinguishing the unique aspects of BOFormer from OptFormer and NAP.
* The paper provides a comprehensive evaluation on various synthetic functions and real-world hyperparameter optimization tasks, both show strong performance of BOFormer. Besides, the paper conducts an additional ablation study on sequence length.

weaknesses:
* I have some doubts about the non-Markovian nature of MOBO. If we define the state as the complete set of historical queries along with the posterior distribution of candidate points, the problem naturally becomes Markovian, as the hypervolume improvement can be uniquely determined from this state representation. The non-Markovian property in your approach appears to be artificially induced by your choice of a simplified state representation. Please correct me if I am wrong or if I misunderstood something, as I am not from the field of reinforcement learning.
* A major weakness lies in the methodology section, particularly in the insufficient details about BOFormer. Figure 2 is not thoroughly discussed; for instance, positional encoding appears in the architecture diagram but is never mentioned in the text, while Equation 5 already seems to contain temporal information. Moreover, it's unclear how j/t in Equation 5 is combined and encoded with other inputs, as it appears to be merely an arithmetic sequence (e.g., numbers from 0.1 to 0.9 when t=10). Additionally, the introduction of Off-Policy Learning and Prioritized Trajectory Replay Buffer feels abrupt - what problems are they addressing? There's no proper introduction or motivation. I suggest the authors improve this section to present the problems and their solutions more clearly to readers.
* Another concern is the temporal information in the history representation. In BO, the historical queries should be permutation-invariant - the order of previous queries should not affect future decisions. However, by incorporating explicit temporal information, the method might be breaking this consistency. Or have you observed any benefit of incorporating temporal information? And is there any ablation study showing the impact of it?
* The paper lacks some experimental details. E.g., no configuration of the surrogate model such as the choice of the kernel and hyperparameters; Training cost for meta-training not reported.
* The paper contains several mathematical formulation issues and inconsistencies. E.g., Line 345, shouldn't it be $max$?; Line 347, I guess it should be $i$-th objective as $j$ is the time step; Inconsistent index notation, in line 344, $i$ indexes objective functions: $i \in [1,···,K]$, while in the equation at line 374, $i$ represents time steps; Line 225, the hypervolume formula contains an unexplained $x'$ that appears redundant; Line 819, shouldn't it be uniform distribution?
* There is no discussion about Figure 3, it might be better to give an introduction about performance profiles.
* There is no experiment to support the idea of demo-policy-guided exploration, thus it is hard to see the effect of this enhancement.
* Minor issues: Line 201: Incorrect appendix reference (B.2 instead of B); Line 820: Incomplete sentence ending abruptly.

questions:
* Regarding OptFormer Implementation, how did you adapt OptFormer for MOBO? To my understanding it was originally designed for single-objective HPO tasks. Did you retrain the model from scratch for MOBO or fine-tune the existing model? It would be great if you could add some details for the baselines you compared with.
* Have you tried to compare the direct implementation you mentioned in Section 4.1 with your proposed method?
* I assume BOFormer can only accept discrete inputs, how does the method handle continuous domains in practice? Are there any discretization issues?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730563261952

thread_type:
official_review

<thread_object>
creator: reviewer_tuhd

<content>
summary:
This paper introduces BOFormer, a novel approach to multi-objective Bayesian optimization (MOBO) that leverages non-Markovian reinforcement learning. The authors' primary contribution is addressing the hypervolume identifiability issue in MOBO through a generalized DQN framework implemented via a Transformer architecture. The work introduces several practical enhancements, including Q-augmented observation representation, prioritized trajectory replay buffer, and demo-policy-guided exploration. The method is comprehensively evaluated on both synthetic functions and real-world hyperparameter optimization tasks for 3D Gaussian Splatting, demonstrating competitive performance against existing approaches. The authors also show promising transfer learning capabilities across different numbers of objective functions.

strengths:
The authors have identified and thoroughly addressed a fundamental issue in learning-based MOBO approaches - the hypervolume identifiability problem. This represents a significant contribution to the field. The theoretical framework connecting non-Markovian RL to MOBO is rigorously developed and mathematically sound. 

The experimental evaluation is comprehensive, comparing the method against both classical and learning-based baselines across diverse scenarios.

weaknesses:
The contribution appears somewhat incremental relative to existing approaches like OptFormer and NAP. While the authors introduce novel elements, the core methodology builds heavily on established techniques.

The motivation for using Transformers in this context needs stronger justification. Given the small data regime typical in Bayesian optimization, the choice of a Transformer architecture, which typically requires substantial data for effective training, requires more thorough explanation.

The theoretical justification for computational intractability due to "curse of dimensionality" (line 244) requires more precise argumentation and supporting references.

questions:
Could you provide details about the experimental methodology, specifically:
- How many random repetitions were performed to ensure statistical significance?
- Were the same network architectures used consistently across all experiments?
- What are the specific architectural details of the Transformer implementation?
- How was stability analysis conducted? ie, stability wrt different transformer models and also different initialization.

Would it be possible to present results on more challenging problems requiring significantly more than 100 samples? The current evaluation up to 100 samples may not fully reflect real-world BO scenarios.

The method's effectiveness with limited data (approximately 10 samples) is surprising given the typically large parameter count of Transformer architectures. Could you elaborate on how this is achieved?

How does the method's performance scale with increasing problem complexity and dimensionality?

Could you provide a more detailed justification for choosing a Transformer architecture in this small data regime compared to simpler alternatives?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691726711

thread_type:
official_review

<thread_object>
creator: reviewer_62xe

<content>
summary:
This paper introduces BOFormer, a novel learning-based acquisition function for multi-objective Bayesian optimization (MOBO) that combines reinforcement learning and sequence modeling with Transformers. BOFormer addresses the hypervolume identifiability issue in MOBO, which stems from its non-Markovian nature, by presenting a Generalized DQN framework and substantiating it through sequence modeling.
Several practical enhancements, such as Q-augmented observation representation and prioritized trajectory replay buffer, are incorporated to facilitate the training of BOFormer. Extensive experiments on synthetic and real-world hyperparameter optimization problems demonstrate that BOFormer consistently outperforms various benchmark methods, exhibits cross-domain transfer capabilities, and efficiently transfers learning across different numbers of objective functions.

strengths:
One of this paper's key strengths is its novel approach to addressing the hypervolume identifiability issue in multi-objective Bayesian optimization (MOBO). By presenting the Generalized DQN framework and implementing it through BOFormer, the authors tackle MOBO's inherent non-Markovian nature. This innovative perspective of reinterpreting MOBO as a sequence modeling problem using Transformers allows for a more effective and efficient solution to the identifiability issue.
Another strength lies in the practical enhancements introduced to facilitate the training of BOFormer. The Q-augmented observation representation provides an informative indicator of the prospective improvement in hypervolume while maintaining a domain-agnostic and memory-efficient representation. The prioritized trajectory replay buffer and off-policy learning enable better convergence and data efficiency during training. Furthermore, the demo-policy-guided exploration ensures efficient search space exploration, which is particularly important given the limited sampling budget in MOBO.

weaknesses:
Limited theoretical analysis: Although the paper introduces the Generalized DQN framework and provides empirical evidence of its effectiveness, it lacks an in-depth theoretical analysis of the proposed approach. A more rigorous theoretical foundation could help better understand BOFormer's convergence properties, optimality guarantees, and limitations.

Scalability to high-dimensional problems: While BOFormer performs well on the tested problems, its scalability to high-dimensional MOBO problems is not explicitly addressed. As the number of dimensions increases, the search space grows exponentially, potentially impacting the algorithm's performance. Further investigation into the scalability of BOFormer and performance on high-dimensional problems would be valuable.

questions:
How does the Generalized DQN framework differ from the standard DQN in terms of theoretical guarantees and convergence properties? Can the authors provide more insights into the theoretical foundations of their approach?

The paper introduces several practical enhancements, such as Q-augmented observation representation and prioritized trajectory replay buffer. How do these enhancements contribute to the performance of BOFormer individually, and are there any potential synergies or trade-offs between them?

The demo-policy-guided exploration is an interesting concept. How sensitive is BOFormer's performance to the choice of the demo policy, and what are the characteristics of a good demo policy for MOBO problems?

The paper showcases BOFormer's cross-domain transfer capabilities and efficient transfer learning across different numbers of objective functions. Can the authors elaborate on the potential limitations of this transfer learning approach and discuss scenarios where it might not be applicable or effective?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730859216266

thread_type:
official_review

<thread_object>
creator: reviewer_91dp

<content>
summary:
The paper introduces BOFormer, a novel approach for tackling multi-objective Bayesian optimization (MOBO) challenges, particularly the non-Markovian nature and hypervolume identifiability issues. BOFormer employs non-Markovian reinforcement learning and sequence modeling, leveraging the Transformer architecture to optimize long-term outcomes. The method demonstrates superior performance in various synthetic and real-world multi-objective optimization scenarios.

strengths:
The paper introduces an innovative approach by framing multi-objective Bayesian optimization (MOBO) as a non-Markovian reinforcement learning problem. This represents a creative combination of existing ideas from non-Markovian RL and Transformer-based sequence modeling, marking a fresh perspective in the field.
The use of diagrams and examples, such as the hypervolume identifiability issue, aids in understanding complex concepts.

weaknesses:
1. The discussion of shortcomings in the paper is relatively brief and does not clearly articulate the innovative aspects of the work. Furthermore, the contributions appear to be somewhat incremental rather than groundbreaking.
2. The use of Transformers may require substantial computational resources and memory, which could limit accessibility for some users.
3. The explanations regarding the experimental section lack clarity. The paper does not specify how the proposed algorithm's time efficiency compares to that of other algorithms. Additionally, it is unclear whether the non-Markovian nature of the process consumes more time than a Markovian approach. The improvements over baseline results also do not appear to be significant.

questions:
1. How does the time efficiency of your proposed algorithm compare to the baseline algorithms?
2. What is the intended meaning of the experimental results in your Figure 3?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732945575778

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to All Reviewers

comment:
We thank the reviewers for their insightful feedback and constructive suggestions. We have updated our manuscript to address the points raised, with modifications highlighted in blue. Below, we further highlight the responses to the key concerns.

## **(1) Additional experimental results**
* **Scalability of BOFormer to high-dimensional problems**

   We conducted additional experiments on black-box functions with higher-dimensional domains, including:

    - Matern52 and RBF (d=10 and 30): https://imgur.com/a/lbgyIuS
    - (Ackley, Rosenbrock) and (Ackley & Rastrigin) (d=40): https://imgur.com/a/ar-ara-dim40-F8KrQ3z
    - DTLZ (d=100): https://imgur.com/a/YMj2sZz
    
    The above results demonstrate that BOFormer remains competitive compared to other MOBO baseline algorithms on these high-dimensional tasks. Notably, all the above results are obtained under the same BOFormer model without any fine-tuning, and hence this further demonstrates the strong cross-domain transferability of BOFormer.

    **Remark 1**: DTLZ is a family of synthetic functions for MOBO and included in the [pymoo library](https://pymoo.org/).

    **Remark 2**: In the above, we compare BOFormer with the rule-based methods such as qNEHVI, JES, and qParEGO as well as the learning-based method like FSAF. These MOBO methods have been shown to be the most competitive among all the baselines (cf. Tables 1-2 in the original manuscript). Moreover, FSAF is a metaRL-based method and requires some metadata for few-shot adaptation. By contrast, BOFormer is evaluated on unseen testing functions in a zero-shot manner.

* **The performance of BOFormer on more challenging problems with more than 100 samples**
    
    We conducted additional experiments on various challenging problems with more than 100 samples, including scenarios with (1) higher domain dimensionality and (2) increased perturbation noise. Accordingly, we set $T=200$ or all the following experiments to better evaluate BOFormer and other baselines.
    
    - DTLZ (d=100): https://imgur.com/a/YMj2sZz
    - HPO-3DGS : https://imgur.com/a/nerf-t200-8l4cihz
    
    The results demonstrate that BOFormer remains competitive compared to other MOBO baseline methods across various types of challenging scenarios. These findings highlight BOFormer’s scalability, making it well-suited for more challenging black-box functions.

    **Remark 3**: To make the problems more challenging for the HPO-3DGS tasks, the perturbation noise is set as 0.1 to make the black-box functions more non-smooth.


## **(2) Ablation study of demo policy**
We conducted additional experiments comparing qNEHVI (the original choice) and NSGA2 as demo policies, as well as a baseline where no demo policy is used. For both BOFormer (w/i qNEHVI) and BOFormer (w/i NSGA2), we apply the same settings as the training configuration in the original manuscript. 

The results are available at https://imgur.com/a/s47MuTQ

Key Observations:
- BOFormer (w/i qNEHVI) achieves favorable improvement in attained hypervolume than that without using a demo policy. This demonstrates the benefit of off-policy learning via a demo policy in the context of MOBO. By contrast, the improvement offered by the NSGA2-based demo policy appears minimal. 
- Recall that qNEHVI performs generally better than NSGA2 on these tasks (i.e., RBF, Matern, and BC) as shown in Table 1 of the original manuscript and the performance profiles in Figure 3. Intuitively, we would expect that the trajectories contributed by qNEHVI can better help BOFormer explore the regions with higher hypervolume. This intuition also resonates with the general understanding that RL performance can be correlated with the data quality (e.g., [Kumar et al., 2019]).

## **(3) More explanation on the performance profiles in Figure 3**

The performance profiles in Figure 3 are meant to more reliably present the performance variability of BOFormer and other baselines across testing episodes than the interval estimates of aggregate metrics. Specifically, the performance profiles show the (empirical) score distributions, indicating the fraction of runs that achieve a score above a certain normalized threshold. The performance profile was originally introduced by [Dolan and Moré, 2002] for benchmarking optimization software and later recommended by [Agarwal et al., 2021] to deep RL.

In the context of MOBO, Figure 3 shows the score distribution of the attained final hypervolume, and the more top-right a curve resides the better. 
Based on Figure 3, we observe that in most tasks, the profiles of BOFormer (i.e., the curves in red) sit on the top right of the other MOBO baselines and hence enjoy a statistically better performance in terms of hypervolume.

In summary, Figure 3 shows that the improvements of BOFormer over baselines are indeed significant.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper frames multi-objective Bayesian optimization as a reinforcement learning problem.  They use deep Q-learning with a Transformer architecture to model the value function and use normalized hypervolume improvement as the reward.  This framing allows the authors to take the entire sequence of evaluations into account when proposing the next experiment to run.  The authors argue that this is an improvement over standard myopic procedures because it addresses what they call the 'hypervolume identifiability issue'.  Specifically, the same hypervolume improvement can be achieved in multiple ways which can't be distinguished with a myopic approach.  Thus knowing what has been attempted before is important to make the search more efficient.  The authors show that there method is effective across a variety of synthetic benchmarks and they construct an optimization benchmark on 3d object reconstruction problems.

The reviews are leaning positive with one leaning reject, two leaning accept and one accept (5, 6, 6, 8).  Thus the average score is a marginal accept.  Multiple reviewers found the paper somewhat incremental - i.e. existing literature has created RL acquisition functions based on Q-learning.   Although they noted that this paper does extend the setting to multi-objective and as including the sequence ("non-Markovian").  The reviewers also noted that there was not much theoretical justification for the proposed approach - e.g. there doesn't seem to be any understanding of convergence guarantees.  Reviewers also requested more details regarding the experimental setup (the authors appear to have added a significant amount in the rebuttal).   On the positive side, the reviewers seemed to find the problem setting compelling and the non-identifiability argument interesting and compelling.  They seemed to find the experiments comprehensive and convincing.

In my own reading of the paper, I found the paper somewhat unclear and difficult to follow.  The method doesn't really seem like Bayesian optimization in my opinion, i.e. it isn't really Bayesian AFAICT.  Instead, it seems more like using deep Q-learning with transformers for multi-objective optimization.  That said, the approach does seem novel, albeit perhaps somewhat incremental over existing Q-learning for single objective optimization approaches.  The identifiability issue is an interesting observation, and reviewers also found this insightful.  The experiments seem positive, i.e. the proposed approach is competitive or better than the baselines in general.  However, not all of the plots seem that convincing - e.g. in figure 3 BOFormer doesn't seem consistently better than other methods.  Also, it's customary to show error bars on plots for Bayesian optimization given the variability in performance of methods across different random restarts.  The authors state that they present average results, but it's unclear to me how many runs were averaged over.  Overall, the problem is well motivated, the approach is novel and there does seem to be merit in the approach and the ideas presented in the work.  In my own opinion, I don't necessarily object strongly to acceptance but I think the paper could be made stronger through some careful editing, revisions and by providing error bars on experiments.  In fact I think the lack of error-bars can be sufficient reason to reject - we don't know if the improvements are statistically significant and I would expect the results to be high-variance given the method (and optimization trajectories in general).