Monte Carlo Tree Search based Space Transfer for Black Box Optimization
Authors: Shukuan Wang
Ke Xue
Lei Song
Xiaobin Huang
Chao Qian
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Bayesian optimization
Black-box optimization
Transfer optimization
Primary area: optimization

Abstract: Bayesian optimization (BO) is a popular method for computationally expensive black-box optimization. However, traditional BO methods need to solve new problems from scratch, leading to slow convergence. Recent studies try to extend BO to a transfer learning setup to speed up the optimization, where search space transfer is one of the most promising approaches and has shown impressive performance on many tasks. However, existing search space transfer methods either lack an adaptive mechanism or are not flexible enough, making it difficult to efficiently identify promising search space during the optimization process. In this paper, we propose a search space transfer learning method based on Monte Carlo tree search (MCTS), called MCTS-transfer, to iteratively divide, select, and optimize in a learned subspace. MCTS-transfer can not only provide a well-performing search space for warm-start but also adaptively identify and leverage the information of similar source tasks to reconstruct the search space during the optimization process. Experiments on synthetic functions, real-world problems, Design-Bench and hyper-parameter optimization show that MCTS-transfer can demonstrate superior performance compared to other search space transfer methods under different settings. Our code is available at \url{https://github.com/lamda-bbo/mcts-transfer}.

Monte Carlo Tree Search based Space Transfer for Black-box Optimization
Shukuan Wang 2.2 Ke Xue Lei Song! Xiaobin Huang Chao Qian 1.2
National Key Laboratory for Novel Software Technology, Nanjing University School of Artificial Intelligence, Nanjing University {wangsk, xuek, huangxb, songl, qianc}&lamda nju. edu.cn
Abstract
Bayesian optimization (BO) is popular method for computationally expensive black-box optimization. However, traditional BO methods need to solve new prob- lems from scratch, leading slow convergence. Recent studies try to extend BO a transfer learning setup to speed up the optimization, where search space transfer is one of the most promising approaches and has shown impressive performance on many tasks. However, existing search space transfer methods either lack an adaptive mechanism or are flexible enough, making it difficult efficiently identify promising search space during the optimization process. In this paper, we propose search space transfer learning method based on Monte Carlo tree search (MCTS), called MCTS-transfer to iteratively divide, select, and optimize in learned subspace. NCTS-ttrnnser can not only provide well- cell-performing search space for warm-start but also adaptively identify and leverage the information of similar source tasks to reconstruct search space during the optimization process. Experiments synthetic functions, real-world problems, Design-Bende and hyper- parameter optimization show that MCTS- Serrs-rrnnserr can demonstrate superior perfor- mance compared to other search space transfer methods under different settings. Our code is available at phttt:: ///g/tttuub com/lamda bbo.bbooboooooooeee ceco/mcs---o tr cransfer
Introduction
hyper-paramette optimiza- 30 we often need to solve black-box optimization (BBO) problems, where the objective function has no analytical form and can only be evaluated by different inputs, regarded as a "black-box" function. BBO problems are often accompanied by expensive computational costs of the evaluations, requiring BBO algorithm to find good solution with small number of objective function evaluations.
In many real-world tasks such neural architecture search [56 41 42 tion (55) 4 and integrated circuit design
Bayesian optimization (BO) 29 g is widely used sample-efficient method for such problems. At each iteration, BO fits surrogate model, typically Gaussian process (GP) (26), to approximate the objective function, and maximizes an acquisition function to determine the next query point. Under the limited evaluation budget, traditional BO methods only have a few observations, which are, however, insufficient for constructing precise surrogate model, leading to slow convergence. Thus, traditional BO methods struggle to effectively solve expensive BBO problems, preventing their broader applications.
To tackle this issue, recent research tries to apply transfer learning methods for BO (2). Transfer BO methods operate under the assumption that similar tasks may share common characteristics, and
"quual Contribution Corresponding Author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the knowledge acquired from similar source tasks can be helpful for optimizing the current target task. They typically gather offline datasets from the source tasks and utilize them to expedite the target task. These methods can be categorized based on the learned components of BO, such as the
acquisition function [51 initialization point [45] 47 or search space 49 23 17
Among these, learning the search space is a promising research area due to its effectiveness and orthogonal relationship with optimization methods. By learning and partitioning the search space, we can more effectively utilize potential subspaces and significantly accelerate the algorithm's search for optimal solutions. While the methods for partitioning the search space have demonstrated great potential [22 14 17], they still have several limitations, particularly in terms of flexibly adjusting the search space for the current target task. In many scenarios, we are uncertain about which tasks are truly "similar" to the target task before optimizing it. Our comprehension about this similarity can only deepen gradually as we progress in optimizing the target task. Therefore, we hope that a search space transfer algorithm can automatically identify the most relevant source tasks during the optimization process, and give them more consideration when constructing the subspaces. However, existing methods have limited flexibility in adjusting in this manner.
In this paper, we propose search space transfer learning method based on Monte Carlo tree search (MCTS), called MCTS-transfer, to iteratively divide, select, and optimize in learned subspace. Each node of MCTS- -eenss-rrnseer represents a subspace, whose potential calculated as a weighted sum of the source and target sample values, assessing the node's utilization value. To better identify and leverage the information from source tasks, we assign different weights to different source tasks based on their similarity to the target task, which are adjusted dynamically during the optimization process. These weights are then used to calculate the potential of the node. Our proposed MCTS-transfer offers several notable advantages. First, it can provide better initial search space for a warm-start of the optimization of the target task. Second, it can provide multiple promising compact subspaces by MCTS, to improve optimization efficiency. The upper confidence bound (UCB)-basel node selection of MCTS can also automatically balance the trade-off between exploration and exploitation. Third, can automatically identify source tasks similar to the current target task based on new observations, and re-construct the search space to make it more consistent with the current target task.
To evaluate the effectiveness of the proposed method, we compare search space transfer methods and conduct experiments on multiple BBO tasks, including synthetic functions, real-world problems, Design-Bench and hyper-parameter optimization problems. In different scenarios, such as varying similarity between the source tasks and target task, MCTS- transfer demonstrates superior performance. We also analyze the effectiveness of the adaptive weight adjustment, showing that -rees-tr can identify source tasks that are similar to the target task and assign them higher weights accordingly. Note that MCTS-transfes can be combined with any BBO algorithm. We only implemented it with the basic BO algorithm (i.e., using GP as the surrogate model and expected improvement (EI) the acquisition function) in the experiments, and the performance can be further enhanced by advanced techniques.
with various
2 Background
2.1 Bayesian Optimization
We consider the problem max (x), where is black-box function and X' RDD is the domain. The basic framework of BO contains two critical components: a surrogate model and an acquisition function. GP is the most popular surrogate model. Given the sampled data points ((.,, 9:) H=) where y4 = (xx) + 6, and e, ~ ~N(0 (7) is the observation noise, GP at iteration t seeks to infer f ~ GP(((-)) k(.,) + I2),,, specified by the mean yu(-) and covariance kernel k(.; +). where I is the identity matrix of size D. After that, acquisition function, e.g., probability of improvement (PI) [5]. EI 12 or UCB 36). is optimized to determine the next query point 2;, balancing exploration and exploitation.
2.2 Transfer Bayesian Optimization
When solving new BBO problems, traditional BO methods need to conduct optimization from scratch, leading to slow convergence. Transfer learning reuses knowledge from source tasks to boost the performance of current tasks, and thus can be naturally applied to address this issue, i.., it can utilize

---

source task data to accelerate the convergence of current target task 22] The main assumption of transfer learning for BBO is that many real-world problems exhibit certain similarities, and similar tasks often share similar characteristies that can be exploited.
Various transfer learning approaches have been explored concerning the surrogate model, acquisition function, initialization, and search space of BO. Several methods learn all available information from both source and target tasks in a single GP surrogate, and make the data comparable through multi-task GP [37 16 38 noisy GP model 23 13, and deep kernel learning model 477 77700 10].
Additionally, certain approaches involve training multiple base surrogates and then combining them into a single surrogate [50, 28).
Transfer learning methods surrogate models, however, may encounter difficulties when scaling to high-dimensional cases, because the influence of the source tasks is easy to diminish progressively with the increase of new observation points [2] Alternatively, transferring knowledge via the acquisition function can circumvent these issues. Previous research has approached transfer learning
for acquisition functions through multi-task BO [37 20), ensemble GPs [51], and meta-learning
strategies such as reinforcement learning-driven strategies [40].
Several approaches consider selecting multiple valuable points for better initial evaluations for the warm-start of optimization. Feurer et al. 77 simply selected the best point from the t most similar tasks as the initialization point. Other works [48 45 achieved warm-start by constructing meta-loss, organically combining the mean function of the GP model from source tasks, and using gradient descent find set of solutions that minimize the meta-loss. Wistuba and Grabocka (47] tried to find suitable initial points to warm-start BO by minimizing the loss on the source tasks using an evolutionary algorithm.
2.3 Search Space Transfer
Compared to the aforementioned methods, search space transfer has many advantages, especially in not limiting the transfer specific algorithm component (e.g., acquisition function in BO), but considering the search space that can be used by all BBO algorithms as the transfer object. That is, the learned search space orthogonal to the optimization process and can be integrated with any advanced optimizer. A well-learned search space can greatly improve optimization efficiency and guide the optimization process to a good result.
The concept of search space transfer was first proposed by Wistuba et al. 49), which defined a region by a center point and diameter, and pruned away regions deemed less promising. Instead of pruning space, Perrone and Shen [23] considered designing a promising search space for the target task. This approach extracts an optimal solution x from each task, and employs a simple geometric form (e.g.. a box or ellipsoid) to define the smallest subspace encompassing all optimal solutions x; However, ignores the correlation between tasks, and the space constructed with regular geometry may be too loose for the target task. To address this issue, Li et al. (17) selected the most similar source tasks to the target task certain proportion, and used a binary classification method to learn good spaces and bad spaces among these tasks. A voting mechanism is then employed to aggregate information from all selected tasks to determine a newly generated search space for the target task.
These current space transfer methods, however, lack mechanisms to adjust the search space when it not well-suited for the target task. Furthermore, when source tasks differ significantly from the target task, they tend to devolve into full-space search. The binary nature of evaluating the search space as simply "good"
"bad" is another limitation. Our proposed method will overcome these drawbacks by adapting the search space dynamically according to the similarity between source tasks and the target task, applying MCTS to find proper subspace, and using a more nuanced and precise numerical evaluation for the goodness of search subspace.
2.4 Monte Carlo Tree Search
MCTS [5] is a search algorithm combining random sampling with a tree search structure, which has been widely applied in the filed of game-playing and decision-making 32 34
A tree node represents a particular state in the search space, e.g., stone positions on the board in a GO game. Each tree node has UCB I value during the search procedure, to balance exploration and exploitation.
3

---

The UCB of each tree node is calculated by its value Um and its visit times Rom, defined as:
ucbm
= Um
2Cp 2 log (np) /nm.
(I)
7m
where Cp is a hyper- parameter controlling the balance between exploration and exploitation, and np is the visit times of the parent node. In the iterative process of MCTS, leaf node is systematically se- lected for expansion, involving four key steps: selection, expansion, simulation, and back- propagattinn Initially, the algorithm recursively navigates from the root node child nodes, prioritizing those with higher UCB values to identify the leaf node m. Subsequently, an action is executed based on the state of m, leading to the expansion of a new child node (state), k. In the simulation step, the node value Us is determined through random sampling. Finally, through back-propagation, the value and visitation count of the ancestors of k are updated.
MCTS has been used to select important variables automatically for high dimensional BO [35]. LA-MCTS [43] is a scalable BBO algorithm based on learning space partition. Utilizing MCTS, it iteratively divides the search space into small subspaces for optimization. In this framework, the tree's 's root represents the entire search space denoted as 52, and each tree node represents sub-region 2 The value e. is determined by the average objective value of the sampled points within the sub-region 4. During each iteration, after selecting leaf node m, LA-MCTS conducts optimization within Ωm The sampled points are then employed for clustering and classification, leading to the bifurcation of 22,, into two distinet sub-regions: "good" and "bad". These sub-regions are expanded as two child nodes, with the left one denoted as "good" and the right as "bad".
3 MCTS-transser
In this section, we propose search space transfer learning method based on MCTS, called MCTS- transfer, which can be divided into two major stages: pre-learnigg stage and optimizing stage. The main idea is to apply MCTS to divide the entire space based source task data in the pre-learning stage, and adaptively adjust the partition based on newly generated target task data during the optimition process. MCTS-transfer iteratively chooses one partitioned subspace for search and adjusts the partition after sampling each new data point. Assume that there are K source tasks {f.)/r and a target task I' that we are going to optimize max fI()), where 12 is the entire search space. For the i-th source task, we have offline dataset D; = {( ((.) )= the observed objective value of æi.j. and [Di is the number of data points. Let tree TT denotes the search space division process by MCTS.
D.l. where Vs.j is
In the pre-learning stage, T initially has only one root node, representing the entire search space Ω. The expansion of tree node m corresponds to the division of the search space 2mm that the node m represents. The node expansion follows the rules below. With a set of source task samples {(x, 91) H= in the space 2m. we use k-means clustering to divide them into two groups. The cluster with a higher average objective value is regarded as the "good" cluster, while the other is the "bad"' one. A binary classifier then establishes a decision boundary between the two clusters. In our approach, the space associated with the good cluster becomes the left node, while the space of the bad cluster becomes the right node. We recursively apply this partition process within each node, as shown in Figure] [ The depth of the resulting Monte Carlo tree T is determined by threshold hyperparameter 8: a node divided if it contains more than samples and the contained samples can be clustered into two clusters. The tree T generated at this stage can give a suitable space partition in advance based on source task data, which serves as a warm-start for the following optimization process. Details of pre-learning will be introduced in Section 3.
In the optimization process, we follow the four key steps of MCTS: selection, expansion. simulation, and pack-propagation At each iteration, we select target node m by tracing the nodes' UCB values. That is, starting from the root, we recursively choose the child node with higher UCB value, until a leaf node m is reached, as Figure [ displayed. The space Ωm, represented by m is then considered as a promising search space, where a BO optimizer is used to optimize. The BO optimizer can build a surrogate model using samples in either 2m, or Ω. The newly sampled point will be evaluated and used for expanding the node m after updating the clustering in the node. It will further be utilized in poek-propagation, where the number of visits and the potential value of each node will be updated. The potential value of node is calculated by a weighted sum of objective values of the source and target task samples. Note that the tree structure will be reconstructed if there exists a node that the

---

ucbnit
ROOT
NODE SELECTION
SEARCH SPACE PRE-LERANING
OPTIMIZATION INITIALIZATION
Figure 1: The workflow of -rrnsferasf.r.... In pre-learning stage, transsrer builds the tree by clustering and classifying the samples apart recursively, until all nodes are splitable. In optimization stage, the initial search space is based on the pre-learned tree. We will trace child node with greater UCB from ROOT and find the target leaf node do optimization.
potential value of its right child exceeds that the left one, violating the rule of our tree construction and implying that the current structure is not good. Please Sections 3.2 and 3.3 for the details of node potential update and tree structure reconstruction.
Unlike LA-MCTS, MCTS- not only considers the information of the target task when calculating node values but also takes into account the information from source tasks, enabling it to be used for search space transfer. Additionally, we propose adaptive weights for source tasks and validate their effectiveness through our experiments.
3.1 Search Space Pre-Learning
Compared to standard BBO algorithms, which sample randomly across the entire space at the beginning, method leverages information from source tasks to concentrate sampling within generally "good" space, providing a warm-start initialization.
In the pre-learning stage, tree T initially has only one node, i.e., ROOT node. All source task samples are collected this node, recursively clustered and classified, leading node expansion. When none of the leaf nodes can be further bifurcated, i.e., contains more than 0 samples and can be clustered into two clusters, T is finally formed. this process, we keep the rule that the left node is "better" (i.e., has larger potential value) than the right node, that we can easily identify that the leftmost leaf is the best and the rightmost leaf is the worst. The potential value of node m in the pre-learning stage is estimated by the average Vi of all source task points within it, i.c..
Pm Σisk E(er, ( JE,,)., Bo.
Σisk DD m
This tree embed historically good regions into specific tree nodes. Intuitively, the spaces represented by left leaves have higher potential of being good spaces than right ones.
The first iteration of NCTS-ttrnsser will utilize the resulting tree T generated in the pre-learning stage. Starting from the root node, recursively selects nodes with higher UCB values until reaching a leaf node. The UCB value is calculated as Eq. (I), where is replaced by the potential value pm in Eq. (2). MCTS-transfer nm and np represent the number of samples, including those from source and target tasks, in the subspace Ω,, and the parent subspace of Ωm, respectively. Consequently, the algorithm preferentially samples from those regions that have shown yield favorable outcomes in the source tasks.
3.2
Node Potential Update
In each iteration of between the source tasks and the target task, and then update each node potential, Note that the potential value Pm used in the pre-learning stage only contains information from source tasks. But in
after evaluating new sample, use it to update the similarity
5

---

the optimizing stage, the calculation of Pm includes both information from the source tasks {D,) and the target task Dr (.TT MT (rrs))z=1 1=1 and considers the similarity between them, i.e.
Pm = 70 Eisk W.Yi.m
VT,m.
(3)
Disk W/:
where Di.m = "..,,,,, /i.s DD; 1. and fr.m E(er s. g. yrs/ Dr Pml. which are the average objective values of the samples of D; and Dr in Pm respectively, There two important parameters in Eq. (3.
7; A decay factor, which is used to adjust the overall influence source tasks throughout the optimization process. A smaller y accelerates the forgetting of the source task data.
wey A weighting factor, which reflects the influence of the i-th source task, and is determined by the similarity between the i-th source task and the target task. larger weight represents higher similarity and implies greater influence of the i-th source task's samples on the potential calculation of a tree node.
To calculate Wt. we measure the distance Pistance(DD, Dr) between the i-th source task and the target task by Distance(2;, x. where x and øÿ denote the mean of the best sampled points of these two tasks, respectively. The source tasks are ranked according to their distances to the target task. A smaller rank implies a smaller distance, i.e., a higher similarity. The weight w; is then calculated as
1.0 0.1
if < a. otherwise
aN
(4)
where r; is the rank of the i-th source task, Nm is the number of source tasks that have solutions located in Pm, and a E [0, 1J. After sampling new data point in each iteration of MCTS-transfer, the ranks and weights are updated accordingly, which are then used to update the potential value of each node. We also consider other ways of calculating distances and weights, which are introduced and empirically compared in Appendix
3.3 Tree Structure Reconstruction
When constructing the search tree, the left child of a node is always better than the right child, i.e., the potential of the left child always exceeds that of the right child. However, after sampling a new data point and updating the potential of each node in each iteration of MCTS-transfer, this property may violated. this happens, it indicates that the current space partition is not ideal and needs adjustment. Specifically, we backtrack from the problematic leaf nodes to the highest-level ancestor node that upholds the desired property, and then proceed to reconstruct the subtree from that ancestor node. The subtree reconstruction process is consistent with the process of node expansion.
The detailed process is presented in Algorithm 2
We apply breadth-first search to traverse all tree nodes and use queue Q to manage the sequence of nodes. In addition, we set queue N to store the nodes that need to reconstructed. If the potential of the right child of a node better than that of the left child (line 6), the subtree of this node is deleted (line 7), and it should be reconstructed and is added into the queue N (line 8). Otherwise, the two child nodes will enter into the queue Q (lines 10-11) and will be examined later. After traversing the tree T, we reconstruct the subtrees of nodes in A (lines 15-19). If a node in A' is splitable, i.e., the contained samples the node exceeds 0 and can be clustered and divided by a binary classifier, it will be further expanded. Thus, Treeify can fine-tune the tree structure and reserve some history information; meanwhile, it can adaptively be more suitable to the target task.
3.4 Details of MCTS-transfer
The detailed procedure of MCTS-transfer is presented in Algorithm [ begins with a pre-learnned MCTS model T based on source task data (line 1), and initializes an empty set Dr to store samples of the target task (line 2). In each iteration, it selects a leaf node m based on the UCB value (line 4). If the target task already has samples in the space Qm represented by m. the algorithm conducts BO within Ωmm and gets candidate point æт, (lines 8-9); otherwise, the candidate point is randomly selected in 2n (line 6). The sampled point æ is then evaluated and added into Dr (line 11). To

---

Algorithm MCTS-transfer
Input: Search space St objective function f-((),, data {D,),= of K source tasks, and number of objective evaluations
Initialize a MCTS model T by search space pre-learning as introduced in Section 3.1
2: Dr = 0:
3: for = 11, . do
4: Select leaf node m by UCB-based selection;
5: if [Drl then
6: Select candidate point ær, randomly in 2mm
7: else
8:
Train a GP model on Dr: Select a candidate 2t,, in 2m by optimizing an acquisition function
9:
10:
end if
11:
Evaluate 2T, to get y and let Dr = Dr { ( VT::)):
12:
Calculate Distance(D,, Dr), and sort them in ascending order to get the ranks Ta For each source task fi, update its weight w; by Eq. (4) where = ,,,,,,,,' For each node update its potential value pa. by Eq. if m.isSplitable then Expand end if
13:
14:
15:
16:
17:
18: Back-propagate and update the visit times and samples of nodes on the path to m,;
19: T < Treeify (T)
20: end for
make full use of the information from the source tasks, we take the similarity between source task and the target task into account, and try to assign higher weights to more similar source tasks, as introduced Section 3.2 With new samples added in Dr, the distance between each source task D, and the target task DT may change. Thus, the distance, rank and weight of each source task are re-calculated in lines 12-13 according to Eq. 4 and the potential value each node in the tree is re-evaluated in line 14 according to Eq. ( After that, the node is expanded in lines 15-17 it is splitale, i.e., contains more than 9 samples of the target task and can be clustered into two clusters. Note that for node expansion, only samples of the target task are considered. In line 18, the back-prec bookkpropaggtion step is performed to refresh the information each node on the path to m, including the visit times and the contained samples. Finally, we will check whether the updated tree conforms to the property that the left child of node has a larger potential value than its right node. For any node violating this property, its sub-tree will be reconstructed. This process is accomplished by employing the Treeify procedure in Algorithm 2 in Appendix A
In MCTS- the tree structure exhibits several properties that align with the requirements of search space transfer learning. 1) Tree structure natural to model the search space, where the root represents the entire search space, and the node expansion corresponds the space partition with each child node representing a subspace. 2) The node potential evaluation allows for the extraction of multiple irregularly shaped promising search subspaces represented by multiple leaf nodes. 3) The tree can be adjusted by updating and expanding nodes on the basis of the original tree, so that new information be absorbed while historical information also be retained, i.e., the tree structure inheritable. This enables the knowledge of space partition from source task data to be transferred to the target task.
Experiments
In this section, we introduce simple case to highlight the features of existing search space transfer algorithms and assess the effectiveness of MCTS-transser. We also conduct experiments across a variety of tasks, including the synthetic benchmark BBOB, real-world problems, Design-Bent Bench and the hyper-parameee optimization benchmark HPOB. The details of the problems, data and experimental results be seen in Appendix B.2 B.3 and
E
Compared methods. Our baselines consist of two non-transfer BO, i.e., basic GP, and LA- MCTS [43) three search space transfer algorithms, i.c., Box-GP 23), Ellipsoid-GP [23). Supervised-

---

GP (77). and one of-te-ff-hee-rr surrogate model transfer BO algorithm PFN 21. Detailed configurations and settings of the
for each algorithm are provided in Appendix [.I]
Basic Settings. In our experimental settings, we explore two types of transfer learning -imiiar and mixed transfer-to demonstrate the advantages of MCTSS in handling complex source tasks. Similar transfer involves using data from similar source tasks, while mixed transfer uses combination of similar and dissimilar source task data for pre-training. Given the challenges in real-world scenarios of determining task similarity and selecting appropriate tasks, our focus will be on evaluating MCTS-transfer performance in the more complex scenario, i.e., mixed transfer.
4.1 Motivating Cases: Sphere2D
We first conduct a simple but important experiment on Sphere2D verify our motivation and evaluate the performance of existing search space transfer methods. The Sphere2D function is defined as f(x) (x x²)² with x' representing the optimal solution. We generate three source task datasets (5.5), (5,-5), and 5)- each containing 100 samples, by assigning (5, 5), (5, -5). and (-5, 5) to x and sampled by standard BO. The target task is defined as f(x) with x" = (4, 4).
Unlike the basic setting, use the mixed setting and the dissimilar setting. Dissimilar setting uses only D(s.- 5) and 5 for pre-training, which are most dissimilar to the target task. This setting is to test -ernsssrr''''ssss s ability to handle extreme cases without similar source tasks.
MCTS-transfer-GP is compared against three search space transfer algorithms- Boo--Box-BB Ellipsoid- GP, and Supervised-GP--ll both mixed and dissimilar settings, as shown in Figure 2 Box-GP and Ellipsoid-GP ignore task similarity and limit the search space geometric areas encompassing all source task optima. In the dissimilar transfer setting, these methods fail because the target task's optimal solution x = (4, 4) lies outside the defined subspace source task optima. Supervised-GP takes task similarity to guide the selection and combination of promising region with voting system. Although pays attention to the importance of task similarity and can be applicable in dissimilar transfer, tends to be an entire- space optimization algorithm when source tasks exhibit high variance or are dissimilar to the target task. MCTS -transfr recursively divides the search space, dynamically ajusts task weights and evaluates the subspace potential based on the task similarity. In addition, the method tends to increasingly rely on target task data due to decay factor 7. Therefore, MCTS MCTS-transfer achieves successful convergence with low variance in mixed and dissimilar transfer. The right part of Figure[]displaan dissplays the weight change curves for the three source tasks, confirming the anticipated results. Higher weights are assigned to datasets P(6.5) and D(-5,5), indicating that method effectively recognizes and prioritizes tasks more similar to the target task.
Box-GP Ellipsoid-GP
Supervised-GP MCTS-transfer-GP * (-5,-5)
(-5,5)
(5,5)
Sohere2D-Mixed
Dphere2D-Dissimilar
2p-ere2D-Mixed
Sphere2D-Dissimine
150
150
1.0
100
Value
Weight
Weight
0.5
50
0
0.0
0.0
20
40
20
40
20
40
Number evaluations
Number of evaluations
Number of evaluations
Number of evaluations
(a) best value
(b) weight change curves
Figure 2: Comparison of MCTS-transfer and other algorithms on Sphere2D
4.2 Synthetic Functions
BBOB is a popular benchmark for BBO. It offers 24 synthetic functions tailored for the continuous domain. We randomly select one function from each of the five function classes of BBOB target task, i.c., GriewankRoseebroek, Lunacek, Rastrigin, Rosenbrock, and SharpRidge.
As shown in Figure 3a compared with LA-MCTS, we find that the results can indeed be greatly improved after space transfer, proving the effectiveness of MCTS-transfer In mixed transfer, MCTS- transfer can still maintain warm-start, thanks its ability to provide multiple compact promising

---

GP
LA-MCTS
Box-GP
Ellipsoid-GP
Supervised-GP
PFN
MCTS- GCTS-tranfer-GP
Similar
Mixed
Similar
Mixed
Rank
Ranke
Rank
Rank
4.
50
100
0
50
100
0
50
160
50
100
Number evaluations
Number of evalluatonn
Number of evaluations
Number of evaluations
(a) BBOB
(b) real-world problems
Figure 3: Comparison of -ranstransfer and other algorithms on BBOB and real-world problems
subspaces by effective search space pre-learning. Throughout the optimization process, MCTS- transfer, combined with a simple GP, is able to reach or even surpass SOTA's surrogate model transfer algorithm PFN, reflecting the superior performance.
4.3 Real-world Problems
To demonstrate the practical value of
test MCTS-transfer with three real-world problems, including LunarLander, RobotPush, and Rover.
Figure 3b shows comparison similar and mixed transfer. Based on the overall ranking, MCTS- transfer-GP GP outperforms other search space transfer baselines. mixed transfer, although it's sur- passed by PFN initially, dissimilar tasks misleading. The ability to adaptively correct the search space may come from the efficient utilization of source task data by reasonable node potential evaluation, node expansion, and tree reconstruction.
is finally able to find better solutions even if there are
4.4 Design-Bench Problems
We further verify the performance of MCTSS-trassfe in more complex and nigh-dimensional problems from Design-Bendl [39], including three continuous problems, Superconductor, Ant morphology and D' D'Kitty Morphology.
In similar and mixed transfer, performance indicates that the algorithm effectively transfer and utilize previous experience when facing different source tasks. This ability particularly important for black-box problems because allows the system quickly adapt to unseen situations while maintaining high performance.
gets the best ranking after 40 iterations. The stable
4.5 Hyper- Hlpeer-parameter Optimization
Hlype--paraeee optimization(HPOO is common application of BBO transfer learning. The HPO-B benchmark [24), sourced from OpenML, includes 176 search spaces/algorithns and 196 datasets, totaling 6.4 million HPO evaluations. Details of Source task data selection and curves of each problem are placed in Appendix B.3 and respectively.
The HPOB benchmark has several challenges. Firstly, for these problems, algorithms are easy to converge on a certain area, Icading to rapid convergence. Secondly, the source tasks are complex, presenting significant variability in data distribution and scale. To tackle the difficulties, the search algorithm should be equipped with ability to handle complex source tasks and robust optimization capabilities.
Experimental results are shown in Figure 4b] which represent the mean ranks and the variance of all algorithms on 39 test problems. In both transfer settings, the baseline ranks are very close, because there are only tiny gaps among final convergence values, which can be seen in Appendix D However, our method still have clear advantages. Although our method doesn't it have enough warm-start strength when the source tasks are diverse and complex, but can still adjust the search tree structure and locate the better search area, exceeding existing search space transfer algorithms.

---

GP
LA-MCTS
Box-GP
Ellipsoid-GP
Supervised-GP
PFN
MCTS -CTS-tranfer-GP
Similar
Mixed
Similar
Mixed
Rank
Rank
Rank 1
Rank
4.
2-
50
100
0
50
160
0
50
160
50
100
Number of evaluations
Number of evaluuatonn
Number of evaluations
Number of evaluations
(a) Design-Bench
(b) HPOB
Figure 4: Comparison of MCTS-transfer and other algorithms on Design-Bench and HPOB
4.6 Runtime Analysis
To verify whether NCTS-transser incurs excessive time overhead, we analyze the runtime propor- tion of each component of MCTS-transfer on BBOB and three real-world tasks (i.e., LunarLander, RobotPush, and Rover). We divide propogation and reconstruction. The evaluation time includes the time required for surrogate model fitting, candidate solution selection and evaluation, which is the common component shared by all optimization algorithms. Backpropagation and reconstruction constitute the two principal modules specific to MCTS-transfee
into three main components: evaluation, back-
As shown in Figure 5) the additional computational burden introduced by MCTS- -taannsferr (i.e., backpropagation and reconstruction) represents a relatively minor fraction of the total runtime, particularly in the three expensive real-world problems. In expensive evaluation problems, MCTS- transfer can bring great improvement by introducing small additional computational overhead. Other details, such as the exact time cost of each component and the frequency MCTS subtree reconstruction, are provided in Appendix F
evaluation time
backpropagation time
reconstruction time
BBOB
LunarLander
RobotPush
Figure 5: Time cost proportion of evaluation, backpropogation and reconstruction of MCTS-transfer
5 Conclusions and Limitations
In this paper, we propose MCTS-transfer to solve the expensive BBO problem. MCTS-transfer uses MCTS to perform search space transfer, extracting similar tasks during the optimization process and giving more accurate space partition results. Compared with other space transfer algorithms, our algorithm is more generalizable. Specifically, it can extract the most similar source tasks and give them higher weights accelerate optimization. Besides, it is reliable because it can dynamically adjust the tree structure, improving the probability that the optimal solution falls in search space of the chosen node. Comprehensive experiments on BBOB, real- world problems, Design- -ennch and HPOB demonstrate the effectiveness of our algorithm. However, there are still limitations, such as the inability of MCTS-transfer to handle search space transfer tasks for problems with different domains or different dimensions. Future work will focus solving the heterogeneous space transfer (6) exploring more accurate similarity measures and trying to give the theoretical analysis of the effectiveness of MCTS-trasn Stannsff...
10

---

Acknowledgments and Disclosure of Funding
We thank the reviewers for their insightful and valuable comments. This work was supported by the Science and Technology Project of the State Grid Corporation of China (5700-20224033222--12333
References
[1] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[2] Tianyi Bai, Yang Li, Yu Shen, Xinyi Zhang, Wentao Zhang, and Bin Cui. Transfer learning for Bayesian optimization: A survey. arXiv:2302.05927,
2023. 2023.
[3] James Bergstra and Yoshua Bengio. Random search for hyper- apper-parameter optimization. Journal of Machine Learning Research, 13:281-305, 2012.
[4] Bernd Bischl, Martin Binder, Michel Lang, Tobias Pielok, Jakob Richter, Stefan Coors, Janek Thomas, Theresa Ullmann, Mare Becker, Anne-Laure Boulesteix, Difan Deng, and Marius Lindauer. Hyperparameter optimization: Foundations, algorithms,, best practices, and open challenges. WIREs Data. Mining, Knowl. Discov, 13(2). 2023.
[5] Cameron Browne, Edward Jack Powley, Daniel Whitehouse, Simon M. Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez Liebana, Spyridon Samothrakis, and Simon Colton. survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4(1):1-43, 2012.
[6] Zhou Fan, Xinran Han, and Zi Wang. Transfer learning for bayesian optimization heteroge- neous search spaces. arXiv preprint arXiv:2309. 16597, 2023.
[7] Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Initializing Bayesian hyperparam- eter optimization via meta-learning. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAA/'15) 15), pages 1128-112 1135, Austin, TX, 2015.
[8] Peter I. Frazier. A tutorial on Bayesian optimization. arXiv:1807.02811 2018.
[9] Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. Deal-parameter black-box optimization benchmarking 2009: Noiseless functions definitions. Technical Report RR-6829, INRIA, 2009.
[10] Tomoharu Iwata. End-to-end learning of deep kernel acquisition functions for Bayesian opti- mization. vrXiv:2111.00633 2021.
[11] Hadi Samer Jomaa, Sebastian Pineda Arango, Lars Schmidt-Thieme, and Josif Grabocka. Transfer learning for Bayesian HPO with end-to-end meta-features, 2022.
[12] Donald R. Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455-492. 1998.
[13] Tinu Theckel Joy, Santu Rana, Sunil Gupta, and Svetha Venkatesh. A flexible transfer learning framework for Bayesian optimization with convergence guarantee. Expert Syst. Appl., 115: 656 672, 2019.
[14] Beomjoon Kim, Kyungjac Lee, Sungbin Lim, Leslic Pack Kaelbling, and Tomás Lozano-Péree -érez. Monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds. In The 34th AAAI Conference on Artificial Intelligence (AAA/'20), pages 9916-9924, New York, NY, 2020.
[15] Harold Kushner. new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 86(1):97-100 1964.
[16] Ho Chung Leon Law, Peilin Zhao, Leung Sing Chan, Junzhou Huang, and Dino Sejdinovic. Hy- perparameter learning via distributional transfer. In Advances in Neural Information Processing Systems 32 (NeurIPS' 18), pages 6801-6812, Vancouver, Canada, 2018

---

[17] Yang Li, Yu Shen, Huaijun Jiang, Tianyi Bai, Wentao Zhang, Ce Zhang, and Bin Cui. Transfer learning based search space design for hyperparameter tuning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (IDD)'22), pages 967-977, Washington, DC, 2022.
[18] Xingchen Ma and Matthew B. Blaschko. Additive tree-structured covariance function for conditional parameter spaces in bayesian optimization. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 20, pages 1015-1025, Palermo, Italy, 2020.
[19] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe W. J. Jiang, Ebrahim M. Songhori, Shen Wang, Young-Joor Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Anand Babu, Quoe V. Le, James Laudon, Richard Ho, Roger Carpenter, and Jeff Dean. Chip placement with deep reinforeement learning. ar0iv:2004. 10746, 2020.
[20] Henry B. Moss, David S. Leslie, and Paul Rayson. Mumbo: Multi-tas max-value Bayesian optimization. In Proceedings of the 31th Machine Learning and Knowledge Discovery in Databases: European Conference (ECML/PKDD 20), pages 447-462, Ghent, Belgium, 2020.
[21] Samuel Müller, Matthias Feurer, Noah Hollmann, and Frank Hutter. Pfns4bo: In-context learning for Bayesian optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML 233,, pages 25444 25470, Honolulu, HI, 2023.
[22] Rémi Munos. Optimistic optimization of deterministic function without the knowledge of its smoothness, In Advances in Neural Information Processing Systems 24 (NeurIPS'II) 11), pages 783-791, Granada, Spain, 2011.
[23] Valerio Perrone and Huibin Shen. Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning. In Advances in Neural Information Processing Systems 32 (NeurIPS' 19)), pages 12751-12761, Vancouver, Canada, 2019.
[24] Sebastian Arango, Hadi S. Jomaa, Martin Wistuba, and Josif Grabocka. HPO-B: A large-scale reproducible benchmark for black-box HPO based on openml. In Advances in Neural Information Processing Systems 34 (NeurlPS'2I), Virtual, 2021.
[25] Anil Ramachandran, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Selecting optimal source for transfer learning in Bayesian optimisation. In Proceedings of the 15th Pacific Rim International Conference on Artificial Intelligence (PRICAI'18) 18), pages 42-56, Nanjing, China, 2018.
[26] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, 2006.
[27] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized evolution for image classifier architecture search. In Proceedings of the 33rd AAAI Conference Artificial Intelligence (AAAI' 19), pages 4780-4788 Honolulu, HI, 2019.
[28] Nicolas Schilling, Martin Wistuba, and Lars Schmidt- Thieme. Scalable hyperparameter op- timization with products of Gaussian process experts. In Proceedings of the 27th Machine Learning and Knowledge Discovery in Databases: European Conference (ECMLPKKD 16), pages 199-214, Riva del Garda, Italy, 2016.
[29] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104 (1):148-17) 2016.
[30] Yunqi Shi, Ke Xue, Lei Song, and Chao Qian. Macro placement by wire-mask-guided black-box optimization. Advances in Neural Information Processing Systems 36, New Orleans, LA, 2023.
[31] Alistair Shilton, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Regret bounds for transfer learning Bayesian optimisation. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS' 17),, pages 307-315, Fort Lauderdale, FL, 2017.
12

---

[32] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schritwieser, Ioannis Antonogiou, Vedavyas Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Master- ing the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
[33] David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillierap. Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with general reinforcement learning algorithm.
2017.
[34] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of Go without human knowledge. Nature, 550(7676):354-35) 2017.
[35] Lei Song, Ke Xue, Xiaobin Huang, and Chao Qian. Monte carlo tree search based variable selection for high dimensional bayesian optimization. In Advances in Neural Information Processing Systems 35(NeurIPS 22), New Orleans, LA, 2022.
[36] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Information- theoretic regret bounds for Gaussian process optimization in the bandit setting. IEEE Transac- tions on Information Theory, 58(5):3250-3222 2012.
[37] Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams. Multi-task Bayesian optimization. In Advances in Neural Information Processing Systems 26 (NeurIPS' 13)), pages 2004-2012, Lake Tahoe, NV, 2013.
[38] Petru Tighineanu, Kathrin Skubeh, Paul Baireuther, Attila Reiss, Felix Berkenkamp, and Julia Vinogradska. Transfer learning with Gaussian processes for Bayesian optimization. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS' 22), pages 6152-6181, Virtual, 2022.
[39] Brandon Trabucco, Xinyang Geng, Aviral Kumar, and Sergey Levine. Design-bench: Bench- marks for data-driven offiine model-based optimization. In Proceedings of the 39th International Conference on Machine Learning (ICML'22) pages
Baltimore, MD, 2022.
[40] Michael Volpp. Lukas P. Fröhlich, Kirsten Fischer, Andreas Doerr, Stefan Falkner, Frank Hutter, and Christian Daniel. Meta-learning acquisition functions for transfer learning in Bayesian optimization. In Proceedings of the 8th International Conference on Learning Representations (ICLR'20), Addis Ababa, Ethiopia, 2019.
[41] Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efficient neural architecture search by learning action space. arXiv: 06832, 2019.
[42] Linnan Wang, Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca. Alphax: exploring neural architectures with deep neural networks and monte carlo tree search. arXiv: / 1059, 2019.
[43] Linnan Wang. Rodrigo Fonseca, and Yuandong Tian. Learning search space partition for black-box optimization using monte carlo tree search. In Advances in Neural Information Processing Systems 33 (NeurIPS 20), pages 19511-19522, Virtual, 2020.
[44] Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale Bayesian optimization in ligh-dimessional spaces. In Proceedings 21st International Conference on Artificial Intelligence and Statistics (AISTATS' 18), pages 745-754, Playa Blanca, Spain, 2018.
[45] Ying Wei, Peilin Zhao, and Junzhou Huang. Meta-learning hyperparameter performance prediction with neural processes. In Proceedings of the 38th International Conference Machine Learning (ICML 21), pages 1 1058--1067, Virtual, 2021.
[46] James T. Wilson, Riccardo Moriconi, Frank Hutter, and Mare Peter Deisenroth. The reparame- terization trick for acquisition functions. 1mXiv21712.00424,33
13

---

[47] Martin Wistuba and Josif Grabocka. Few-shot Bayesian optimization with deep kernel sur- rogates. In Proceedings of the 9th International Conference on Learning Representations (ICLR'2I), Virtual, 2021.
[48] Martin Wistuba, Nicolas Schilling, and Lars Schmidt-Thieme. Learning hyperparameter optimization initializations. In Proceedings of the 2nd IEEE International Conference on Data Science and Advanced Analytics (DSAA 15), pages 1-10, Paris, France, 2015.
[49] Martin Wistuba, Nicolas Schilling, and Lars Thimme. Hyperparameter search space pruning A new component for sequential model-based hyperparameter optimization. In Proceedings of the 26th Machine Learning and Knowledge Discovery Databases: European Conference (ECML/PKDD* 15), pages 104-119, Porto, Portugal, 2015.
[50] Martin Wistuba, Nicolas Schilling, and Lars Schmidt-Thieme. Two-stage transfer surrogate model for automatic hyperparameter optimization. In Proceedings of the 27th Machine Learning and Knowledge Discovery in Databases: European Conference (ECML/PKDD 16), pages 199-
214, Riva del Garda, Italy, 2016.
[51] Martin Wistuba, Nicolas Schilling, and Lars Schmidt-Thieme. Scalable Gaussian process-based transfer surrogates for hyperparameter optimization. Machine Learning, 107:43-78, 2017.
[52] Jian Wu and Peter Frazier. Practical two-step lookahead bayesian optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS' 19)), 2019.
[53] Shangda Yang, Vitaly Zankin, Maximilian Balandat, Stefan Scherer, Kevin T. Carlberg, Neil Walton, and Kody J. H. Law. Accelerating look-ahead bayesian optimization: Multilevel monte carlo is all you need. In Proceedings of the 41st International Conference on Machine Learning (ICML 24), Vienna, Austria, 2024.
[54] Xin-She Yang and Suash Deb. Fagle strategy using lévy walk and firefly algorithms for stochastic optimization. In Proceedings of the 4th Nature Inspired Cooperative Strategies for Optimization (NICSO' 10), pages 101-111, Granada, Spain, 2010.
[55] Quamming Yao, Mengshuo Wang, Hugo Jair Escalante, Isabelle Guyon, Yi-Qi Hu, Yu-Feng Li, Wei-Wei Tu, Qiang Yang, and Yang Yu. Taking human out of learning applications: A survey on automated machine learning.
2018
[56] Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. In Proceedings of the 5th International Conference Learning Representations (ICLR'17), Toulon, France, 2017.
14

---

A Treeify Pseudocode
To maintain the property that the potential of the left child should exceed the potential of the right child for each node, tree reconstruction should be implemented in each iteration. The process of adjusting the tree structure, i.e., deleting and reconstructing subtrees that violate the desired property, is called Treeify. The pseudocode is provided below, shown in Algorithm 2
Algorithm 2 Trecify
Input: MCTS model
Output: an updated MCTS model T
1: Initialize empty queues Q, :N;
2: < E.qqueee(ROOO of 7);
3: while not QiisEmpty do
4: node + Q.Dequeee;
5: if not node.isLeaf then
6:
Peode.Jeft < Prode.right then
7:
Delete the subtree of node;
8:
N + A (nnuuueee(nooe)
9:
else
10:
Q + Q. (nnueuu(
2 Q (nodeeue(nod))righ))
12:
end if
end if
14:
end while
for each node in N do
16: if nodeeiiSplittbll then
Expand node
18: end if
end for
B Detailed settings
B.1
Algorithms
We use the authors' reference implementations for LA-MCTS Box-GI Ellipsoid-Gri Supervised-
GF and PFNs4BO The hyper-parameters of compared algorithms are summarized as follows:
GP-EI. We use the GP model in Scikit-learr' and the ExpectedImprovementt acquisition [46]. The kernel is set to be Constant 110 Maater(leength 1aagggegettgtttl__t000 scale=1.0, nu=2.5). To optimize the acquisition function, generate 10000 points randomly and then select the with the maximum expected improvement to be evaluated, which similar to LA-MCTS
43
We set C.p- = 0.1,0 = 10. We adopt global GP as the modeling approach. SVM with rbf kernel is used for space division in Sphere2D, BBOB, and HPOB, while Logistic Regression is applied for real-world problems. In the sampling process, we sample the entire space 10,000 times, retaining qualifying candidate points, and repeat this process three times. The parameters of GP are consistent with GP-EI. All other parameters are set to their default values.
LA-MCTS 43
Supervised-GP. The sampling process consistent with LA-MCTS. The parameters of GP consistent with GP-EI. All other parameters are set to their default values.
15

---

Box-GP. The sampling process is consistent with LA-MCTS. The parameters of GP are consis- tent with GP-EI. All other parameters are set their default values.
Ellipsoid-GP. The sampling process consistent with LA-MCTS. The parameters of GP are consistent with GP-EI. All other parameters are set to their default values.
MCTS-trranfer-GP. We set = 0.99, a = 0.5. We adopt 5 best solutions distance as similarity measure and linear-change strategy weight assignment. Other parameters and sampling method is consistent with LA-MCTS. The parameters of GP are consistent with GP-EI.
PFN. We set epochs = 5000, batch size=256, learning rate=3e-4, warm up steps = 100, model dimension = 256, head = 4, layer number hidden layer size 256, dropout=0.1.
B.2 Problems
We consider the following three real-world problems in our experiments.
LumarLanderr" This problem is to learn the parameters of controller for a lunar lander, which is implemented OpenAl gym TO It involves a 12-dimensional continuous input space depicting the lander's s actions. Our goal is to enhance the control algorithm maximize the mean terminal reward across a consistent batch of 50 randomly generated landscapes, incorporating varying initial positions and velocities.
RobotPush This function computes the distance between predefined target location and two objects that are manipulated by pair of robotic appendages. The movement trajectory of these objects governed by set of parameters, which encapsulate attributes such as position, orientation, speed, and direction of motion. We need to control the robot to push items to designated location. This is implemented with physics engine Box21
Rover 13 The task optimizes 2D trajectories for a rover by defining start and goal positions and
cost function over the state space [44]. The trajectory costs c(x) computed for solutions within 60-dimensional unit hypercube. We need to design reasonable trajectory to minimize the cost.
To verify the performance of MCTS-tranfer in more complex and high-dimensional cases, consider the 3 continuous problems from Design-Bencl 14 (39.
Superconductor. It's a critical temperature maximization for superconducting materials. This task is taken from the domain of materials science, where the goal is design the chemical formula for superconducting material that has high critical temperature. The search space is a continuous space with 86 dimensions.
Ant morphology. It's a robot morphology optimization. The goal is to optimize the morphological structure of Ant from OpenAl Gym 115 make this quadruped robot run fast possible. The search space is a continuous space with 60 dimensions.
D' D'Kitty Morphology. It's robot morphology optimization. The goal is to optimize the morphology of D' D'Kttty robot to navigate the robot to a fixed location. The search space a continuous space with 56 dimensions.
B.3 Source Task Data Construction for Similar and Mixed Transfer
Data collection The source task data for pre-training is generated by seven optimization algorithms: Random Search 3 Shuffled Grid Search, Hill Climbing. Regularized Evolution [27), Eagle Strat- egy (54), and GP-EI [12]. These methods span heuristic, evolutionary, and BO techniques, providing
diverse of optimization behaviors for analysis.
"bttps://box2d..org//
functions/rover,
16

---

Real-world problems and Design-Bench problems Since it is difficult to find data with the same dimensions real-world problems, we choose to use the artificial function Sphere of the same dimension to generate similar data and dissimilar data and mix it into the source task data set. Among them, to simulate similar functions, we set the optimal point x" of the sphere function to be the optimal point of all these algorithms found so far; the optimal point of the Sphere function that simulates dissimilar functions set trajectories from the problem with different seeds and function transformations, combined with data In order to obtain similar souree task data of function f. we perform some similar trans- formations on f obtain function family Ff with seed from 0 to 499. Then we use the sampling algorithms mentioned above with randomly selected seed to collect 300 samples on each function in Fy. this section, we randomly select 20 datasets from datasets of Fy for function f. In the similar setting, We only use selected datasets of Fy. In mixed setting, we use selected datasets of all 5 synthetic functions.
BBOB
x². In the similar setting, we randomly select 20
generated by similar sphere function, as the dataset. In the mixed setting, we further add 7 trajectories from dissimilar sphere function. In this section, it is problem with significantly more similar source tasks than dissimilar tasks.
We choose search spaces from HPO-B-v3 and divide them into 4 groups based on dimen- sions. Specailly, we obtain group 5860 and 5970 with dimension 2. group 5859 and 5889 with dimension 5, group 7607 and 7609 with dimension 9, group 5806 and 5971 I with dimension 16. In the similar setting, we only use the training data from the search space itself for pre-learning. In the mixed setting, we use all training data of search spaces in the same group.
HPОB
C Discussions of methods
C.1 Task Similarity
Measuring the similarity of two tasks based on the dataset of a source task D; and the dataset of the target task Dr is complex task. We define task distance measure of similarity. Smaller distances between tasks represent greater similarity. Here we mainly focus on two types of methods: point-based similarity measures and distribution-based similarity measures. The former includes optimal solutions distance, best N solutions mean distance, best N percent solutions mean distance; and the latter includes Kendall coefficient of datasets, Kullback-Leibler Divergence(KI. Divergence) of distributions. Detailed description are as follows:
Optimal solutions distance
Let ay be the best solution of target task, and an be the best solution of target task. The task distance is calculated as Distance(x;7... .
Best N (or N percent) solutions mean distance Similar to optimal solutions distance, we replace 2f and æi with the mean of best N (or N percent) of target task and source task i, denoted as æi and कं. The task distance is Distance ( Φ,). Intuitively, it's more robust than directly using the best solution.
Kendall coefficient Kendall coefficient is a measure of rank correlation, which can be used to evaluate the consistency of two datasets. We first build a surrogate model (usually GP) M, on D,, and then predict all sample values in Dr. According the ranking results of all these data, we get the similarity of the two tasks by Eq (5), where I is the indicator function and @ is the exclusive-nor -oo operation, in which the statement value is true only if the two staeemttements return the same value.
Ek 1 [(M, (#TS) < M, (#T,K)) @ (VT, yT,K)) Distance(Dr..o D.) 2 ;1 2//T
Prl
(5)
Dr * ([Dr[-1)
KL. divergence of distribution KL divergence is a measure of the dissimilarity between two probability distributions, usually expressed as Eq. (6). For Dr and D,, we first use Guassian KDE to estimate their density of distribition, denoted p and q. Then we sample set of (æ, Ji in S and
17

---

evaluate them. KL divergence is calculated based on {p(x))/=1 and {(((x))=-
Distance (D. D2) = KT(ppl1)= = Σ p(x) log p(x)
(6)
g(x)
C.2 Weight Assignment
Based the similarity between the source tasks and the target task, rank the source tasks, and the smaller rank T; means higher weight assigned. We can choose different weight change strategies, for example, Linear Change Strategy in Eq. ( Exponential Change Strategy in Eq. (8 or All One Strategy, i.e., all source task weights are set to be 1, to control the proportion of influencial source tasks.
1.0 NN
if aN
W;
(7)
0.1
otherwise
W/ grh 0 S Nm -1
(8)
In Eq. 77)
Nm is the number of source tasks that have solutions located in Qm, and a E [0, controls the proportion. In Eq. (8) B [0, 1] is hyper-parameter of weight change speed.
C.3 Discussion on Conditional search space.
MCTS-transfer can also be applied in conditional search space, which is common hyper-parameter optimization. For conditional optimization, we consider the problem =i (a)) Specifically, the search space tree-structured, formulated as {V, F), where v E V is a node representing subspace and E E' is edge representing condition. The objective function is also defined based on T, formulated as (x) := fp..T (a:((),, where p, is a condition and æ|1; is the restriction of æ to 4j [18. In the pre-learning stage, it builds subtrees for each v E V and generates the MCTS model T' based on T. In each iteration, followed by UCB value, it finds the target node m located in the subtree of with condition pt, optimizes in 12m selects and evaluates the candidate using fp..7 F ( (.). After that, it updates the task weights and node potential in the whole tree T' and tries to reconstruct the tree. Note that the tree reconstruction only happens in each subtree of E V.
C.4 Discussion between the state value in MCTS of AlphaZero and MCTS-Transee
MCTS measures state value differently reinforcement learning and black box optimization. For example, AlphaZero [33 is designed to master complex games through self-play without relying on human knowledge or guidance. MCTS plays crucial role in AlphaZero's decision- decision-making process, whose state value is used to predict the expected future reward from the current state to the end, rather than the historical information. Different from that state's future reward of AlphaZero can be obtained through multi-step simulations, i.e., alternating decisions through self-play, evaluation values in BBO can only be obtained through actual evaluations. Consequently. MCTS-trrasti utilizes historical information. We have observed that some recent look-ahead BO works [52 53 have been used to predict the expected value of future steps in BBO problems, which have the potential to be applied in MCTS- -transfrr as estimates for state values to further improve the performance.
C.5 Discussion of combining MCTS-transfer with other advanced algorithms
MCTS-transfer is a general search space trans- fer learning framework, which can be com- bined with other advanced algorithms. We equip MCTS-transfer with PFN and test MCTS- transfer-PEN on mixed real-world problems. As shown in Figure 6, MCTS-trransfer-PF. makes further improvements compared to MCTS- transfer-GP and PFN after around 80 iterations, and its ranking is stable and excellent through- out the optimization. This result demonstrates the versatility MCTS-transte combining with advanced BO algorithms.
Mixed
GP
LA-MCTS
Rank +
Box-GP
Ellipsoid GP
Supervised-GP
2
MCTS-transfer-GR
25
50
75
100
MCTS-transfen-FN
Number of evaluations
Figure 6: Experimental results on mixed real world problems (with MCTS-transfe--PPI
18

---

D Sensitivity Analysis of Hyper-parameters of MCTS-transfer
MCTS- includes modeling approach, similarity measures, weight assignment strategies, decay factor 7, important source task ratio a, exploration factor Cp. spliting threshold 0 and the binary classifier. We conduct sensitivity analysis of these important parameters on real-world problems LunarLander, RobotPush, Rover under mixed setting.
Main
Modeling approach In MCTS-transfer, we can choose to train GP on full Dr dataset or on the selected points in Qm As shown Figure 7 the global GP can utilize more global information, demonstrating enhanced search capabilities in these three problems.
global
local
LunarLander-Mixed
RobotPush-Mixent
Rover-Mixed
300
200
Value
Value
Value
100
-10-
0
-100
50
100
50
100
50
100
Number of evaluations
Number of evaluations Number evaluations
Figure Sensitivity Analysis of Local and Global Modeling Approaches
Similarity measures We propose 5 similarity measures in this paper, including optimal solutions distance, best N N percent solutions displayed. The first three methods are point-based measures and the last three are distribution-base methods. Here we N=5 and N=30% separately for best N solutions and best N percent solutions, and use Gaussian KDE to evaluate KL divergence of distributions. The results can be seen in Figure 8 The distribution- searbbution-basedd methods give more precise measure of similarity, but the point- based methods are designed to focus on the optimal region. Each problem has its own suitable measure of similarity. In mixed transfer real-world problems, KL. divergence is more appropriate to the problem.
distance, Kendall coefficient and KI. divergence, C.
Optimal solutions distance
Best 5 solutions distance
Best 30% solutions distance
Kendall coefficient
KL divergence
LunarLander-Mixed
RobotPush-Mixes
Rover-Mixed
200
4
Value
Value
Value
-5
2
-10-
-200
100 Number of evaluations
100
100 Number of evaluations
Number of evaluations
Figure Sensitivity Analysis of Similarity Measures
Weight assignment To assign weights to source tasks, we consider three strategies: linear-change strategy(i.e. Eq. )7) the exponential-change strategy (i.e., Eq. (8) and all-one strategy. We set 0.5 for linear-change strategy, B = 0.5 for exponential-change strategy. As shown in Figure I0
19

---

the exponential-change strategy, since the weight decaying rapidly with the rank, can only effectively leverages the 1-3 source datasets. So tends have faster convergence speed if the similar tasks are effectively identified at the initial stage, as demonstrated in Rover. The all-one strategy are easy be disturbed by dissimilar data but can fully utilize information, so it may have higher convergence value at later stage. The linear-change strategy is relatively more stable because it takes the advantages the above two strategies into account.
Linear
Exponential
All-one
LunarLander-Mixed
RobotPush-Mixed
Rover-Mixed
6
200
4
Value
Value
Value
-5
-10
-200
50
100
100
50
100
Number of evaluations
Number of evaluations
Number evaluations
Figure 9: Sensitivity Analysis of Weight Change Strategy
Decay factor y. The decay factor 7 used control the influence of source tasks. A higher decay factor 7 results in quicker decay of source tasks' influence, thus making the node potential rely more on the target task's ' data. However, an excessively rapid decay of source task lead unstable evaluation outcomes and under-utilization of source task data. Specially, for the nodes preferred by source tasks, if they can't 't be selected as the sampling node at first, their potential will decrease rapidly and these nodes will be less likely to be selected. The analysis experiment of ry be seen in figure [0] and the result is as expected. The curves of MCTS-transee overlap, better than y 0.1 in most cases, due to data exploitation. And appropriate decay factor will help to combine information from source and target tasks to accelerate optimization.
with = 0.99 and ? = 1.0
y= 0.1
0.99
y= 1.0
LunarLander-Mixed
RobotPush-Mixed
Rover-Mixed
300
200
4-
Value
Value
Va Value
100
-10
0-
-100
100
50
100
50
100
Number of evaluations
Number of evaluations
Number evaluations
Figure 10: Sensitivity Analysis of Decay Factor y
Important source task ratio a linear-hange strategy, we can set a to determine the ratio of important source tasks that have high weights. We choose a 10%, 50% and 100% and he result is shown in Figure [I] A higher a means that more source tasks are influencial on evaluation of the tree node potential. However, this also increases the risk of the interference from dissimilar data. MCTS-transfer with smaller only trusts the most similar tasks and under-utilizing information from the source task, leading to slower convergence in early stage.
20

---

a
10%
a 50%
a 100%
LunarLander-Mixer
RobotPush-Mixed
Rover-Mixed
200
4
Value
Value
Value
2
-10
0
-200
50
100
50
100
50
100
Number of evaluations
Number of evaluations
Number of evaluations
Figure 11: Sensitivity Analysis of Important Source Task Ratio
Exploration factor C Cp controls the degree of exploration. large Cg prompts the MCTS- transfer to select less promising regions, enhancing exploration. As shown in the Figure too big Cp results in the reduction of exploit useful information, as the algorithm overexploits less promising areas, leading to slower convergence.
cp 0.1
Cp 1.0
Cp 10.0
Cp 100.0 Rover-Mixed
LunarLander-Mixed
RobotPush-Mixed
200
4
Value
100
Value
Value
-10
-20
-100
0.
50
100
50
100
100 Number evaluations
50
Number of evaluations
Number of evaluations
Figure 12: Sensitivity Analysis of Exploration Factor C
The splitting threshold 0 The threshold 0 controls the depth of the tree: a node is only allowed to be further divided when it contains more solutions than A smaller 0 leads a deeper tree. In our experiment (Figure 13). 0 = 100 means the tree nodes won't I be splitted in the optimization, so the suggesting search space will be bigger, which is less efficient.
= 10
=
θ = 100
LunarLander-Mixed
RobotPush-Mixed
Rover-Mixed
300
200
4
Value
Value
Value
100
-10-
0-
-100
0
50
100
50
100
0
50
100
Number of evaluations
Number of evaluations
Number of evaluations
Figure 13: Sensitivity Analysis of The Splitting Threshold 0
21

---

Binary classifier The binary classifier decides the boundary of "good" and "bad" clusters. We try the following classifiers: Logistic Regression and SVM (with rbf, linear, or poly kernel). According to the results in Figure 14, SVM with linear kernel and Logistic Regression give more effective search space partition. We can choose a binary classifier with higher partition efficiency according to specific scenarios.
LogisticRegression
kernel=rbf
kernel=linear
kernel=poly
LunarLander-Mixed
RobotPush-Mixed
Rover-Mixed
300
6
200
4
-5
Value
Value
Value
100
-10
2
-15
-100
-20
50
100
50
100
0
50
100
Number of evaluations
Number of evaluations
Number of evaluations
Figure 14: Sensitivity Analysis of Binary Classifier
22

---

E Detailed experimental results
The evaluation result curves on BBOB, real-world problems and Design-Bence are summarized in
figures 15 and T6 The curves of HPOB in similar setting and mixed setting are shown in figure [8
and figure
T9 and the format of subfigure titles is (search space id)-(dataset id)- (Sixeaa
GP
LA-MCTS
Box-GP
Ellipsoid-GP
Supervised-GP
PFN MCTS-tranfer-ee
Sieewankfooeebbockiiiiill
Gifewankfoseebrook-Mied
Value
50
Value
50
25
25
50
100
50
100
Number of evaluations Senacek-Simillrr
Number of evaluations
Lunacek-Mixed
400
Value
Value
200
50
100
50 Number of evaluations Rastrigin-Mixer
100
Number of evaluations
Rastrigin-Simine Similar
1000
1000
Value
Value
500
500
50
100
50
100
Number of evaluations
Number of evaluations
RosenbrockRotated Similar
RosebbrockRotated Romiaa Mixed
oooood
200000
Value
Value
100000
100000
50
100
50 Number of evaluations SharpRidge-Mixed
100
Number of evaluations
SharpRidge-Simias
2000
2000
Value
Value
1000
1000
50
100
50 Number of evaluations
100
Number of evaluations
Figure 15: Evaluations of MCTS S-trnnsfer and other algorithms on BBOB
23

---

GP LA-MCTS
Box-GP
Ellipsoid-GP
Supervised-GP
PFN
MCTS-tranfer-GP
LunarLander-Simile
LunarLander-Mixed
200
200
Value
value
-200
200
0
100
100
Number of evaluations
Number of evaluations
RobotPush-Simee Simillr
RobotPush-Mi Mixxed
5.0
5.0
Value
Value
2.5
2.5
0.0
-2.5
-2.5
0
50
100
50
100
Number of evaluations
Number of evaluations
Rover-Similar
Rover-Mixed
Value
Value
-10
-10
-20
-20
-30
50
100
100
Number of evaluations
Number of evaluations
Figure 16: Evaluations of MCTS-transte and other algorithms on Real-world Problems
GP
LA-MCTS
Box-GP
Ellipsoid-Gr
Supervised-GP
PFN
MCTS-tranfer-GP
Superconductor-Simeg Similar
Superconductor-Mixx Mixed
80
Value
60
Value
60
40
20
40
0
100
Number of evaluations Ant-Similar
Number of evaluations
Ant-M Ant-Mixed
Value
Value
-200
-200
0
50
100
50
100
Number of evaluations
Number of evaluations
Dkitty-Similar
Dkitty- Mixed
Value
Value
200
-250
-400
-500
-600
0
50
100
100
Number of evaluations
Number of evaluations
Figure 17: Evaluations of MCCTS-transiir and other algorithms on Design-Bench

---

GP
LA-MCTS
Box-GP
Ellipsoid-GP
Supervised-Gr
PFN
MCTS-tranffr-GG
5970 100-14499m-illll
1800-14955-Simiann
5860-3493-Simm
5860-9976-5h
0.60
Value
0.89
Value
0.64
value
0.55
Value
0.0001
0.50
0.0000
0.88
50
100
0.62
50
100
50
100
50
100
Number avaluations
Number evaluations
Number evaluations
Number evaluations
5970-345 5970-34536-Similln 36-Smmilar
5970-3492 3770-3492-Similar
5970-37 37-Smmllar
9970-49-Simina
0.60
Value
0.75
value
0.55
Value
0.653
0.50
0.652
0.6508
0
50
100
0
50
100
0
50
100
0
50
100
Number of evaluations
Number of evaluationn
Number evaluations
Number evaluations
5970-9952-Simm 9-mmllr
5859-125923-Simlee
5859-31-S
Value
0,7065
Value
0.72
Value
0.70
0.7064
0.6
0.70
0
50
100
6
50
100
0
5D
100
50
100
Number of evaluations tions
Number of evaluations
Number of evaluations
Number of evaluations
3859-3902-Similn
5859-9977-Simila
5859-998 3-99-99l
5889-3918-Sime
0.89
0.9
Value
Value
Value
Value
0.935
0.6
0.930
100
50
100
100
Number of evaluations
Number of evaluations
Number of evaluations 9607-14965-
Number evaluations 1607-3896-Simllr
5889-9971-Similar
1807-145976-$imlla
0.70
0.85
Valve
0.68
0.90
0.80
0.70
0.75
0.66
0.65
0.88
50
100
50
100
50
100
100
Number evaluations 7607-3903-SM
Number evaluations 7607-3913-Simlae
Number evaluations
Number evaluations 7607-9967-Sime
1607-9946-Simile
1.0
Value
0.895
0.8 0.825
Value
0.8
Value
0.800
0.885
50
100
0.775
0
50
100
5D
100
50
100
Number evaluation tions
Number evaluations
Number evaluations
Number evaluations
1609-125923-Simil
7509-145853-Similar
7609 145854-Similar
7609- 109e-l4587
0.8
1.0
1.0
Value
0.8
Value
Value
0.8
0.8
0.6
0
50
100
0
50
100
0
50
100
50
100
Number of evalua tions
Number of evaluations
Number of evaluations
Number of evaluations 5906-3 1906-3918-4 Similar
7609 3-53344377-777
7609-3908 Similar
7609-9967. 3509-9967-Simllas
0.90
0.93
Value
0.8
Value
0.89
Value
0.8
Value
0.92
0.6
50
100
50
100
0
50
100
50
100
Number of evaluations
Number of evaluations
Number of evaluations
Number of evaluations 771-3954-Simila
5906-9971-Siming
1971-10093-Simiin
5971 34536-Similar
0.72
1.0
1.0
Value
0.70
Value
0.8
Value
0.8
0.5
0.6
0.7
100
50
100
50
100
100
Number of evaluations 5971-43 43-Similar
Number of evaluations
Number of evaluations 5971 9970--mmlll
Number evaluations
5971 6566 -imiilr
1.0
Value
0.8
Value
0.6
0.6
50
100
0.0
0
50
100
50
100
Number evaluations
Number evaluations
Number evaluations
Figure 18: Evaluations of and algorithms on HPOB in similar setting

---

GP
LA-MCTS
Box-GP
Ellipsoid-GP
Supervised-Gr
PFN
MCTS-tranfert
5970-14951 Miixee
5860- 11600-1465--0 Mixed
3860-3493-Mixxe
5860-9976 M-xxed
Value
Value
Value
value
0,0001
0.89
0.64
0.50
0.0000
0.88
50
100
50
100
50
100
50
100
Number evaluations
Number evaluations
Number evaluations
Number evaluations 5970-49-Mixe
3970-34536-Mixx
3970-3492-Mixes
3970-37-Mixe
0.60
Value
0.75
Value
0.55
Value
0. 0.6510
0.6535
0.50
0.50
0.25
0.6508
0
50
100
0
50
100
0
50
100
50
100
Number of evaaluation tions
Number of evaluations 5859-12592344 Mixed
Number of evaluations
Number evaluations
5970-9952-84 99xx-M
3859-31-Mixes
5859-37-Mixed
Value
Value
0.72
Value
0.7060
0.70
0.7055
0.6
0.70
0.65
0
50
100
6
50
100
0
5D
100
50
100
Number of evaluations tions
Number of evaluations 5859-9977-Mixce
Number of evaluations
Number of evaluations
5859-3902 3i00-xiddd
5859-998 3---99983----000
5889-3918 3-xxxxxed
0.9
Value
Value
Value
0.935
0.6
0.930
50
100
100
Number of evaluations 5889-9971 1iii-
Number of evaluations
Number of evaluations 7607-14965-Mixx
Number of evaluations 7607-3896-Mixe
7607-145976-Mixel
0.70
0.75
0.85
Vallve
0.68
0.90
0.70
0.66
0.65
0.75
0.88
100
50
100
50
100
100
Number evaluations 7607-3903- 1007-3903-Mixed
Number evaluations
Number evaluations 7607-9946- 9946-Mixed
Number evaluations
7607-3913-Mixee
7607-9967-Mixce
0.90
1.0
Value
0.825
Value
0.8
Value
0.89
0.800
0.775
0
50
100
50
100
50
100
50
100
Number of evaluatiion tions 1---22299222-i--2
Number evaluations
Number evaluatinns
Number evaluations
(609-145853.1
7609-1 45855--iieed
16099-45878--0
0.8
1.0
1.0
Value
0.8
0.8
0.8
0.6
0.4
0
50
100
0
50
100
0
50
100
0
50
100
Number of evaluationn tions 7609-34537 Mixed
Number of evaluations
Number of evaluations
Number of evaluations 5906-3918-
3903-Mixed
Mixed
1.0
0.90
0.93
1.0
Value
0.8
Value
Value
Value
0.89
0.8
0.92
0.6
0
50
100
0
50
100
0
50
100
50
100
Number of evaluations 5906-9971 1-xe-Mixed
Number of evaluations
Number of evaluations 5971 2711-3533-Mixeee
Number of evaluations 5971-3954-
5971 0093 --Mieed
1.0
1.0
Value
Value
0.8
Value
0.8
0.6
100
50
100
50
100
0.6
100
Number of evaluations
Number of evaluations
Number of evaluations 5971-9970. Mixed
Number evaluations
5971 43
43-MMxed Mixed
1377166566-iixin
1.0
Value
0.8
Value
0.5
0.6
50
100
0
50
100
50
100
Number evaluations
Number evaluations
Number evaluations
Figure 19: Evaluations of MCCTS-rransfe and other algorithms on HPOB in mixed setting

---

Details of runtime analysis
In order analysis the additional computational overhead introduced by MCCT--rrnnser,, we calculate the time cost and the corresponding proportion of each component, and record the frequency of subtree reconstruction in each iteration.
Specifically, we divide MCTS-transe into three main components: evaluation, backpropagation and reconstruction. The evaluation component includes the time required for surrogate model fitting, candidate solution selection and evaluation, which is common component shared by all compared optimization algorithms. Backpropagation and reconstruction components are the two principal modules specific to MCTS-transter.
We test -CrTs-rannsfrr on BBOB benchmark and three real-world tasks (i.e., LunarLander, Robot- Push, and Rover). Among them, the evaluation process of the real-world tasks is more tine-consuming and the evaluation cost of BBOB relatively cheaper.
As illustrated in Figure 20 the additional computational burden introduced by MCTS-transfer (i.e., backpropagation and reconstruction) represents relatively minor fraction of the total runtime, particularly in the three real-world scenarios. These scenarios precisely exemplify the computationally intensive cases that transfer BO is designed address, wherein MCTS-transfer demonstrates small additional computational overhead..urthermoor Furthermore, our result reveals that the average frequency tree reconstructions is low, with the corresponding reconstruction time being almost negligible when compared to the evaluation time.
evaluation time
backpropagation time
reconstruction time
LunarLander
RobotPush
Rover
ВBОB
LunarLander
RobotPush
Rover
20:
2
10:
Time(s]
0
S0
100
50 Number of Iterations
100
50
100
100
Number Iterations BBOB
Number Iterations
Number Iterations Rover
LunarLander
RobotPush
0.50
1.0
Times
0.5.
0.5
0.25
1000
0.5
m
0.00
0.0
0.0
-0.25
-0.5
50
100
50
100
50
100
50
100
Number of Iterations
Number of Iterations
Number of Iterations
Number of Iterations
Figure 20: Time cost of different components in of components in optimization. The middle row: the time cost of components in each iteration (avg*std). The bottom row: the number of subtree recosruciion/rreonntntiiii times in each iteration (avgsstd).
The top row: the time proportion
27

---

G Visualization of Weight Change Curve of Source Tasks
Here we show the weight change curve of three mixed real-world problems. We the weight assignment stategy to be the linear change strategy with a = 0.5 and the decay factor to be 0.99. Figure 2T shows that the weights of real-world problem and similar sphere problem exceed those of dissimilar ar sphere problem in most cases, regardless of any inconsistencies in initialization. The results prove that the weight change strategy can prioritize similar source task data, which will lead to more accurate node potential evaluation and search space partition.
Real World Problem
Similar Sphere
Dissimilar Sphere
LumarLander-Mixed
RobotPush-Mixed
Rover-Mixed
1.00
0.8
0.6
0.75-
Weight
0.6
Weight
Weight
0.4
0.4
0.50
0.2
0.2
0.25
0.0
0.0
0.00
50
100
0
50
100
50
100
Number of evaluations
Number of evaluations
Number of evaluations
Figure 21:
Weight Changes: MCTS-transter
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Both the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are proposed in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The detailed information is provided in Appendix B and C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer: [Yes]
Justification:
We will submit code, data and instructions, and we will release the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.cc/pullc//uuuii wwwticccguie//eeeeeeeeeii CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The detailed information is provided in Appendix B and C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The error bars are already shown in figures in paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
31

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: We didn't 't provide computing resource- relattd content in the article because that content is not relevant to the topic of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: btctps://neuriptt httppp/bit///iiiecscieeeeeeeeeee
Answer: [Yes]
Justification:
Our research conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We describe it in introduction part.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We correctly cite the origin paper and sources.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "wvmHG4ymXd", "reviewer": "Reviewer_x4CE", "summary": "The paper proposes a tree-based search space division to enable transfer across different instances of related optimisation problems.\nThe authors propose both a scheme to divide the search space in a hierarchical fashion based on training task samples as well as a way of weighing the resulting subspaces against each other to acquire new evaluations for the task at hand. Since the similarity between the training tasks and the current task is updated as samples are acquired, the tree rankings have to be continuously updated as well.\nThe derived algorithm is evaluated on both an illustrating toy example and several more challenging benchmarks. The appendix contains further ablations regarding design choices and hyperparameter selections.", "questions": "1. How often is reconstruction of the search tree required? Would it be possible to add an analysis of how frequently the tree has to be rebuild as this presumably is a large factor in the runtime of the algorithm itself?\n\n2. Could the authors comment on how the search-space division is done for conditional search spaces (e.g. in the hyperparameter optimization settings)?", "limitations": "The authors point towards future work and more accurate task similarity measures as future work but beyond this do not discuss the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I found the paper very well-presented and easy to follow. The main ideas were clearly laid out and the overall structure made sense to me.\n\nTo my knowledge, the proposed approach is novel. Given that Bayesian Optimization is usually applied in tasks with limited evaluation budgets, search space transfer seems like a promising avenue of allocating these limited budgets more efficiently. It also circumvents the scaling issues that approaches based on synthetic data points have.\n\nThe empirical evaluation is sound and there are detailed ablation studies supporting the authors claims.", "weaknesses": "Arguable the biggest weakness of the paper is the lack of theoretical analysis of the provided algorithm. However, given the depth of the empirical evaluation, I believe this can be left as future work.\n\nI also feel that a comment on the runtime of the proposed framework would be helpful. MCTS-transfer requires the (re-)construction and update of an entire search tree as well as the training of several classifiers.  \n\nBeyond this, some minor points for consideration are:\n- From the description it is unclear, when the search space clustering (i.e. the subspace classifier) is updated. Does this only happen during tree reconstruction or during back-propagation as well?\n- I would not name LunarLander, RobotPush, and Rover as real-world problems. While the search spaces are higher dimensional, the problems themselves are relatively simple", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reviewing our paper and providing constructive comments, which have helped improve the work a lot. Below please find our responses.\n\n### Q1: Lack of theory\n\nThank you very much for your suggestions. We fully agree that theoretical analysis of MCTS-transfer is a very interesting topic. Here, we provide two potential perspectives for theoretical analysis:\n\n- One point of analysis could be the transfer efficiency in transfer learning. A possible approach is to analyze the space size covered by MCTS partitions at the optimal points [1]. The expected conclusion is that, compared to constructing LaMCTS from scratch, MCTS partitions cover optimal points more efficiently with the same number of partitions.\n\n- Another point that can be theoretically analyzed is the regret bound. A possible approach is to use the error bounds of Gaussian process regression [2] and the characteristics of MCTS space partitions to bound the instantaneous regret at each step.\n\nWe will add this discussion into our main paper and leave it as our future work. Thank you.\n\n[1] Multi-Objective Optimization by Learning Space Partitions. ICLR, 2022.\n\n[2] Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. ICML, 2010.\n\n### Q2: Lack of runtime analysis and reconstruction frequency analysis\n\nThank you for your valuable suggestions. Please refer to Q1 in general response. \n\n### Q3: When is the search space clustering updated?\n\nWe are sorry for not making it clear. The update of tree clustering happens both in backpropagation and reconstruction stage. In backpropagation stage, after we get a new sample $(\\boldsymbol{x}\\_t, f(\\boldsymbol{x}\\_t))$ in node $m$, we will update the node status along the path from $m$ to ROOT node, including the data contained in the node, the number of visits, and whether it is splittable. To check whether the node $m$ is splittable, we need to update the clustering of the search space $\\Omega\\_m$. If $m$ contains more than $\\theta$ samples and the samples can be clustered apart, we will expand $m$ into 2 child nodes. In reconstruction stage, we will prune the unqualified subtrees and reconstruct them.  During the subtree reconstruction, the clustering of the search space will also be updated. We will revise to make it clear. Thank you.\n\n### Q4: The real-world problems are relatively simple \n\nThanks for pointing this out. We will rename these problems as non-synthetic tasks. To further demonstrate the performance of MCTS-transfer in complex real-world problems, we add three new problems from Design-Bench [1]. The results still show the superiority of MCTS-transfer. Please refer to Q2 in general response.\n\n[1] Design-Bench: Benchmarks for Data-Driven Offline Model-Based Optimization. ICML, 2022\n\n### Q5: How to do the search-space division for conditional search spaces?\n\nThanks for your question. To apply our method to the conditional search space, we may apply the following process. For conditional optimization, we consider the problem $\\min \\_{\\boldsymbol{x} \\in \\mathcal{X} \\subset \\mathbb{R}^{d}} f(\\boldsymbol{x})$. Specifically, the search space is tree-structured, formulated as $\\mathcal{T}=\\\\{V,E\\\\}$, where $v\\in V$ is a node representing subspace and $e\\in E$ is an edge representing condition. The objective function is also defined based on $\\mathcal{T}$, formulated as $f\\_{\\mathcal{T}}(\\boldsymbol{x}):=f\\_{p\\_{j},\\mathcal{T}}(\\boldsymbol{x}|{l\\_{j}})$, where $p\\_j$ is a condition and $\\boldsymbol{x}|l\\_j$\nis the restriction of $\\boldsymbol{x}$ to $l\\_j$ [1]. In the pre-learning stage, it builds subtrees for each $v\\in V$ and generates the MCTS model $\\mathcal{T'}$ based on $\\mathcal{T}$. In each iteration, followed by UCB value, it finds the target node $m$ located in the subtree of $v$ with condition $p\\_i$,  optimizes in $\\Omega\\_m$, selects and evaluates the candidate using $f\\_{p\\_{i},\\mathcal{T}}(\\boldsymbol{x}|{l\\_{i}})$. After that, it updates the task weights and node potential in the whole tree $\\mathcal{T'}$ and tries to reconstruct the tree. Note that the tree reconstruction only happens in each subtree of $v\\in V$. We will revise to add some discussion.\n\n[1] Additive Tree-Structured Covariance Function for Conditional Parameter Spaces in Bayesian Optimization. AISTATS, 2020.\n\n\n### Q6: The limitations of the work\n\nThanks for your suggestions. Apart from lacking theoretical analysis and accurate task similarity measures, the limitations of our work include that it cannot handle search space transfer tasks for problems with different domains or with different dimensions. We will further improve the algorithm in this way by learning embedding space in future work. We will add this to our revised paper. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3XIyVqXCEP", "reviewer": "Reviewer_ygQe", "summary": "This paper proposes a new space transfer method for black-box optimization by using MCTS. The search space is divided by MCTS, and the data from source tasks are used to help evaluate the value of each node of the tree. The similarity between the source and target tasks is considered and adjusted dynamically. The authors performed experiments on various problems, and compared the propose method with state-of-the-art methods.", "questions": "See weakness.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The idea of the proposed method so-called MCTS-transfer is interesting and also natural. It extends the LA-MCTS method by using transfer learning: The data points of the source tasks are used to help evaluate the value of a node in the tree with weights related to their similarity to the target task. The similarity is updated using new sampled points from the target task and will become more accurate gradually. \n\nIn the initialization stage, the data of source tasks are used to construct a tree by clustering and binary classification. Particularly, the data points in a node are clustered into two clusters, where the cluster with better average objective value is treaded as “good” and the other cluster is “bad”. A binary classifier is then used to divide the space represented by the node into two parts. In the optimization stage, the proposed method uses MCTS to select one leaf node, and optimizes within the search space the leaf represents. The newly sampled points are further used to update the leaf node, e.g., expand the leaf.\n\nThe most interesting thing is the calculation of the potential value of each node, which is a weighted sum of objective values of sampled points from both source and target tasks. The weights consider the similarity between the source and target tasks; more similar, larger the weights. The authors calculated the weights by using the distance between the best points of the tasks, which will be updated after new data points of the target task are sampled. This makes the weights (or the similarity between the source and target tasks) adjustable during the optimization process. \n\nThe experiments are extensive. The authors compared state-of-the-art methods of transferring the search space, and some other recent related methods. The problems considered include BBOB, hyper-parameter optimization, and real-world problems. The results generally show the superior performance of MCTS-transfer. The authors also did various sensitivity analyses. The paper is overall well written, and easy to follow. The codes are provided.\n\nOverall, I think this work can provide a good complement to the space transfer method for black-box optimization.", "weaknesses": "The authors considered the number of evaluations in the experiments. This is OK. But I also want to see the running time comparison of each iteration, which will be useful in practice. It seems that the proposed method will cost more time, as it will use the procedure of Treeify to check the feasibility of the tree, i.e., whether a right child node has a larger value than the left one.\n\nIn the right subfigure of Figure 1(b), no blue line?\n\nIn the right subfigure of Figure 2(b), the PFN method is better than the proposed MCTS-transfer. I’d like to see some discussion. As MCTS-transfer can be equipped with any BO algorithm, can it achieve better results by combining advanced BO algorithms?\n\nLines 346-347, I cannot understand “we can still see the obvious strength in exploring the optimal solution at later stage,” can you give some explanation?\n\nI suggest moving the pseudo-code of Algorithm 1 (Treeify) to appendix. Instead, you can include more experimental results in the main paper.\n\nFor the hyper-parameters \\gamma and \\alpha in equation 3 and 4, how to set them in practice?\n\nThough the paper is overall well written, there are still some types.\n\n-- line 310: 3 search space transfer algorithms -> three search space transfer algorithms\n\n-- line 311: figure 1 -> Figure 1; line 322: figure 1 -> Figure 1; Please check throughout the paper.\n\n-- line 330: The sentence “The detailed experimental results …” is redundant.\n\n-- line 334: mcts-transfer -> MCTS-transfer\n\n-- line 336: “equal” -> “reach”\n\n-- line 337: “surprising performance”, I suggest using “superior performance”. The results are good, but not surprising. \n\n-- line 339: “We test” -> “we test”\n\n-- line 344: “in the RobotPush” -> “in RobotPush”\n\n-- line 354: “close final and random final”?\n\n-- line 360-361: in D -> in Appendix D; but it can -> it can\n\n-- line 600: missing the period\n\n-- line 621: \\alpha -> and \\alpha\n\n-- line 643-645: the sentence is not well written.\n\n-- line 641, 646: check the missing and redundant blank\n\n-- Caption of Figure 13: Real-World Problem -> Real-World Problems", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reviewing our paper and providing constructive comments, which have helped improve the work a lot. We are very glad that you appreciate our work. Below please find our responses.\n\n### Q1: The running time comparison of each iteration\n\nThank you for your valuable suggestions. Please refer to Q1 in general response.\n\n### Q2: Explain the lack of blue line in the right subfigure of Figure 1(b)\n\nIn Sphere2D, we consider mixed settings and dissimilar settings. As demonstrated in line 307-309, we use $D\\_{(-5,-5)},D\\_{(5,-5)},D\\_{(5,5)}$ as source datasets in mixed setting, and remove the most similar task $D\\_{(5,5)}$ in dissimilar setting. Figure 1(b) shows the curve of source task weight changes during the optimization process. As there are only two source tasks in dissimilar setting, only two lines are shown in right subfigure of Figure 1(b).\n\n### Q3: In Figure 2(b), PFN is better than MCTS-transfer; Combining MCTS-transfer with advanced BO algorithms to achieve better performance.\n\nThanks for your comments, but there are some misunderstandings that need to be clarified. In Figure 2(b), PFN just converges faster in the early stages, but performs worse than our MCTS-transfer after about 70 iterations. Our algorithm finally achieved better results as well.\n\nWe appreciate your suggestion that combining MCTS-transfer with other advanced BO algorithms, which is an interesting idea and can further strengthen our work. According to your suggestion, we combine MCTS-transfer with PFN and compare it with other algorithms in Figure 2(b). The results can be found in the right subfigure of Figure 2 in the PDF file. We find that MCTS-transfer-PFN makes further improvements compared to MCTS-transfer-GP and PFN, which shows the versatility of MCTS-transfer. We will include this experiment in our revised paper. Thank you very much.\n\n### Q4: Explain line 346,347\n\nWe are sorry for not expressing it clearly. \nIn RobotPush, MCTS-transfer has no advantage in the initial stage, but it can still effectively divide the search space and speed up optimization, as clearly shown in similar settings. In the later stage of optimization in similar setting, the speed of MCTS-transfer for finding the optimal solution exceeds all baselines, which may come from the efficient utilization of source task data by reasonable node potential evaluation, node expansion, and tree reconstruction.\n \n### Q5: How to set $\\gamma$ and $\\alpha$ in practice?\n\n$\\gamma$ is a decay factor controlling the weight decay of source tasks, and $\\alpha$ is to determine the source task ratio with high weights. We set $\\gamma=0.99$ and $\\alpha=0.5$ by default. Generally, if the source tasks are very relevant to the target task, i.e., very similar or important, you can set $\\gamma$ and $\\alpha$ higher; if the source tasks are diverse, $\\alpha$ should be set lower to prevent disturbance from unimportant tasks.\n\n### Q6: Remove treeify to appendix; Some typos in paper\n\nThank you very much for carefully pointing out the typos and providing your valuable suggestions on the paper organization. We will revise the paper carefully according to your suggestions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MT6nDjh0dw", "reviewer": "Reviewer_jvcN", "summary": "This paper proposes a search space transfer learning method based on Monte Carlo tree search (MCTS) called MCTS-transfer, which aims to accelerate the optimization process in computationally expensive black-box optimization problems.", "questions": "1. How does MCTS-transfer handle the computational overhead introduced by the MCTS component, especially in large and complex search spaces?\n2. Can the authors provide more specific examples or case studies where MCTS-transfer significantly outperforms other methods?\n3. What measures have been taken to ensure the reproducibility of the results? Is the code and dataset publicly available?", "limitations": "The authors should address the potential computational overhead and provide a more comprehensive discussion on the limitations of their method. Additionally, the impact of the method on different types of black-box optimization problems should be more thoroughly explored.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality: The integration of MCTS with search space transfer learning is a novel approach, which addresses the need for improved convergence in black-box optimization problems.\n- Clarity: The paper is generally well-written and structured, making the methodology and results comprehensible.", "weaknesses": "- Technical Depth: The paper lacks sufficient technical depth in explaining the underlying mechanics of MCTS-transfer. For instance, the specifics of how MCTS iteratively divides and selects subspaces are not clearly detailed.\n- Experimental Rigor: The experimental validation, although covering various scenarios, does not delve deeply into comparative baselines. The choice of baselines is limited and more recent advancements in the field should be included.\n- Adaptability and Scalability: There is insufficient discussion on the adaptability of MCTS-transfer to different problem domains and its scalability to very large search spaces. The potential computational overhead and limitations in such scenarios are not adequately addressed.\n- Theoretical Analysis: The theoretical analysis supporting the method's efficacy is minimal. It would be better if more rigorous proofs or detailed theoretical justifications would strengthen the paper.\n- Reproducibility: While the results are promising, more details should be presented to ensure reproducibility. Key implementation details, parameter settings, and the codebase are missing, which are crucial for the validation of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable and constructive comments. Below please find our responses.\n\n### Q1: How does MCTS iteratively divides and selects subspaces?\n\nWe're sorry that we didn't make this part clear. \n\n- How does MCTS iteratively divide subspaces? As described in Section 3.1, the division of space corresponds to the expansion of nodes. Starting from the ROOT node, if the node is splittable, we cluster the samples into two clusters and divide them apart, leading to the birth of two child nodes, where the node with better cluster is the left child node. Then, following the sequence of depth-first-search, we repeatedly try to expand the node and visit the child nodes if it's splittable, iteratively dividing the space.\n\n- How does MCTS iteratively select subspaces? We select the subspace by the guidance of UCB. Starting from the ROOT node, if the node has two child nodes, we will choose the node with higher UCB as the next node to visit. Following the sequence, we will finally locate the target leaf node and find the subspace.\n\n### Q2: Comparison with more advanced baselines\nThanks for your comments. However, we believe that our compared baselines are comprehensive. We include non-transfer BO (basic GP, LA-MCTS), existing search space transfer methods (Box-GP, Ellipsoid-GP, Supervised-GP), and state-of-the-art algorithm (PFN). If you have some specific suggestions of additional baselines, we are happy to discuss it. \n\n### Q3: Discuss the adaptability of MCTS-transfer to different problem domains and its scalability to very large search spaces\n\nThanks for your valuable comments. \n\n- Adaptability to different problem domains. We add three new complex real-world problems from Design-Bench to show the adaptability of MCTS-transfer to different problem domains. \n\n- Scalability to very large search spaces. MCTS-transfer is suitable for solving large search spaces, because the subspaces with high potential can be gradually discovered and extracted, thus improving the optimization efficiency. The three new real-world problems from Design-Bench are relatively high-dimensional, among which Superconductor has 86 dimensions, Ant morphology has 60 dimensions, and D’Kitty Morphology has 56 dimensions. We believe the results can reflect the performance of MCTS-transfer in large search spaces. \n\nPlease see Q2 in general response for details. \n\n\n### Q4: Lack of theoretical analysis \n\nThank you very much for your suggestions. We fully agree that theoretical analysis of MCTS-transfer is a very interesting topic. As also suggested by Reviewer x4CE, we provide two potential perspectives for theoretical analysis:\n\n- One point of analysis could be the transfer efficiency in transfer learning. A possible approach is to analyze the space size covered by MCTS partitions at the optimal points [1]. The expected conclusion is that, compared to constructing LaMCTS from scratch, MCTS partitions cover optimal points more efficiently with the same number of partitions.\n\n- Another point that can be theoretically analyzed is the regret bound. A possible approach is to use the error bounds of Gaussian process regression [2] and the characteristics of MCTS space partitions to bound the instantaneous regret at each step.\n\nWe will add this discussion into our main paper and leave it as our future work. Thank you.\n\n[1] Multi-Objective Optimization by Learning Space Partitions. ICLR, 2022.\n\n[2] Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. ICML, 2010.\n\n### Q5: Reproducibility issue\n\nOur code has been provided in the supplemental materials. All the implementation details can be found in it. Besides, the parameter settings and data collection methods are provided in appendix A.1 and A.3, respectively. \n\n### Q6: How does MCTS-transfer handle the computational overhead introduced by the MCTS component, especially in large and complex search spaces?\n\nWe acknowledge that building and maintaining MCTS in high-dimensional and complex search spaces will bring additional computational overhead. However, as shown in Figure 1 in the PDF file, the time of tree backpropagation and reconstruction seems minor compared to evaluation time. Additionally, if one wants to further reduce the time cost on MCTS, we can set the leaf size $\\theta$ higher to reduce the tree depth, or choose a fast binary classifier such as LinearRegression to divide the space.\n\n### Q7: Provide more specific examples or case studies where MCTS-transfer significantly outperforms other methods\n\nMCTS-transfer is suitable for expensive BBO, especially when we are uncertain about which tasks are similar to the target task. Our method can automatically identify the most relevant tasks and give more considerations on them when constructing the subspaces. Even if none of the source tasks are considered similar, MCTS-transfer can still correct the search direction by relying more on the collected target task data just as the motivating case in section 4.1 demonstrated. Hyperparameter optimization is a specific example in practice, where we don't know any properties in advance. However, we can collect other optimization trajectories on the same domain, and MCTS-transfer will automatically identify the relevant part to accelerate optimization.\n\n### Q8: Provide a more comprehensive discussion on the limitations of their method\n\nApart from lacking theory analysis and accurate task similarity measures, the limitations of our work include that it cannot handle search space transfer tasks for problems with different domains or with different dimensions. We will further improve the algorithm in this way by learning embedding space in future work. We will add this part in the new version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hnz5uAPCnI", "reviewer": "Reviewer_Tjsz", "summary": "This paper propose a search space transfer learning method based on Monte Carlo tree search, called MCTS-transfer, to iteratively divide, select, and optimize in a learned subspace. It can provide a well-performing search space for warm start for the target problem based on the source problems. It adaptively identify and leverage the information of similar source tasks to reconstruct the search space during the optimization process. Experiments on many situations have demonstrated the effectiveness of the algorithm.", "questions": "Please refer to the weakness part.", "limitations": "Please refer to the weakness part.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written, and is easily to understand.\n\n2. The experiments are conducted extensively and demonstrate the effectiveness of the algorithm across numerous application scenarios.\n\n3.  Introducing Monte-Carlo tree search into the search space transfer problem is quite novel, and this paper modifies some operations of MCTS based on its own application scenarios to make it work better.", "weaknesses": "1. It would be beneficial to analyze the algorithm's running time and computational cost if possible.\n\n2. In MCTS of AlphaZero, state value $v$ is used to predict the expected future reward from the current state to the end. In this paper, the evaluation of current state $p_m$, which can be treated as a summary of historical iterative path from the root to the current, is used as $v$. Can you discuss the differences between the two? What are the potential impacts to use historical $p_m$ to represent the future expected $v$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable and constructive comments. Below please find our responses.\n\n### Q1: Running time and computational cost analysis\nThanks for your valuable suggestions. Please refer to Q1 in general response.\n\n### Q2: Discussion between the state value in MCTS of AlphaZero and MCTS-Transfer\n\nGood points! Thank you very much for your interesting and insightful questions.  AlphaZero [1] is designed to master complex games through self-play without relying on human knowledge or guidance. MCTS plays a crucial role in AlphaZero's decision-making process, whose state value is used to predict the expected future reward from the current state to the end, rather than the historical information in our paper. Different from that a state's future reward of AlphaZero can be obtained through multi-step simulations, i.e., alternating decisions through self-play, evaluation values in BBO can only be obtained through actual evaluations. Consequently, we utilize historical information in our paper. We have observed that some recent look-ahead BO works [2-3] have been used to predict the expected value of future steps in BBO problems, which have the potential to be applied in MCTS-Transfer as estimates for state values to further improve the performance. We will incorporate this discussion into our revised paper. Thank you for bringing this to our attention.\n\n[1] A general reinforcement learning algorithm that masters chess, shogi and Go through self-play. Science, 2018.\n\n[2] Practical Two-Step Look-Ahead Bayesian Optimization. NeurIPS, 2019. \n\n[3] Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need. ICML, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are very grateful to the reviewers for carefully reviewing our paper and providing constructive comments and suggestions. Our response to individual reviewers can be found in the personal replies, but we also would like to make a brief summary of revisions about writing, discussion, and experiments for your convenience.

Writing:

- We have revised some typos and improved some expressions.

Discussions:

- We discuss the theoretical analysis of MCTS-Transfer, according to the suggestions of Reviewers x4CE and jvcN. 

- We discuss how to apply MCTS-Transfer to the conditional search space, according to the suggestions of Reviewer x4CE.

- We discuss the differences in MCTS between AlphaZero and MCTS-transfer, according to the suggestions of Reviewer Tjsz.

Experiments:

- We analyze the runtime of MCTS-transfer, according to the suggestions of Reviewers x4CE, ygQe, and Tjsz.

- We add three new real-world problems from Design-Bench to compare the performance of algorithms in complex and high-dimensional real-world problems, according to the suggestions of Reviewers x4CE and jvcN. 

- We equip MCTS-transfer with PFN on mixed real-world problems, demonstrating the versatility of MCTS-transfer combining with other advanced BO algorithms, according to the suggestions of Reviewer ygQe.

For the important questions many reviewers concerned about, we make general responses here.

### Q1 Runtime analysis

We conduct a comprehensive analysis of the runtime proportion of each component of MCTS-transfer and quantify the subtree reconstruction times on BBOB benchmark and three non-synthetic tasks (i.e., LunarLander, RobotPush, and Rover).  We divide MCTS-VS into three main components: evaluation, backpropogation and reconstruction.

- The evaluation component includes the time required for surrogate model fitting, candidate solution selection and evaluation. This component is common to all the compared optimization algorithms.
- Backpropagation and reconstruction constitute the two principal modules specific to MCTS-transfer.

As illustrated in Figure 1 of the PDF file, the additional computational burden introduced by MCTS-Transfer (i.e., backpropagation and reconstruction) represents a relatively minor fraction of the total runtime, particularly in the three non-synthetic scenarios. These scenarios precisely exemplify the computationally intensive cases that transfer BO is designed to address, wherein MCTS-Transfer demonstrates small additional computational overhead.

Furthermore, our result reveals that the average frequency of tree reconstructions is low, with the corresponding reconstruction time being almost negligible when compared to the evaluation time. We will include this discussion in our revised paper. Thank you. 

### Q2 More problem domains/complex real-world problems
To further verify the performance of MCTS-transfer in complex real-world problems, we add the following three problems from Design-Bench [1], which is a suite of diverse and realistic tasks derived from real-world optimization problems.

- Superconductor: critical temperature maximization for superconducting materials.  This task is taken from the domain of materials science, where the goal is to design the chemical formula for a superconducting material that has a high critical temperature. The search space is a continuous space with 86 dimensions.

- Ant morphology: robot morphology optimization. The goal is to optimize the morphological structure of Ant from OpenAI Gym to make this quadruped robot to run as fast as possible. The search space is a continuous space with 60 dimensions.

- D’Kitty Morphology: robot morphology optimization. The goal is to optimize the morphology of D’Kitty robot to navigate the robot to a fixed location. The search space is a continuous space with 56 dimensions.

The data collection methods are consistent with existing real-world tasks in our paper, and the parameters remain unchanged. The results shown in the left sub-figure of Figure 2 in the PDF validate the significant advantages of MCTS-transfer in these complex, high-dimensional, and realistic tasks.

[1] Design-Bench: Benchmarks for Data-Driven Offline Model-Based Optimization. ICML, 2022.

**We will include all these results into the revision of our paper, and will revise the paper carefully according to your comments and suggestions. We hope that our response has addressed your concerns, but if we missed anything please let us know.**

Meta-review: This paper proposes MCTS-transfer, which utilizes MCTS with a search space transfer method in black-box optimization problems. The core idea is to use MCTS to iteratively divide the search space and optimize within a learned subspace by incorporating a weighted factor from source tasks into target tasks. The weights are calculated based on the similarity between the source and target tasks, and these weights are further updated as the target task is optimized. This makes the weight adjustment adaptive and addresses the issue that previous black-box optimization methods did not consider cases where the source and target tasks are not similar. MCTS then reconstructs the search tree based on the newly calculated node potentials. The authors also conducted detailed empirical experiments across various benchmarks to demonstrate that MCTS-transfer outperforms previous methods.

This paper is well-written and well-structured, with sufficient background, clear motivation and methodology, and strong experimental results supporting the proposed method. One of the major concerns raised by reviewers was the time cost of reconstruction in MCTS-transfer. During the rebuttal, the authors provided additional experiments to demonstrate that this cost is almost negligible. These additional experiments should be included in the final version. I also suggest the authors include a figure providing an overview of the procedure at the beginning of Section 3 (before Section 3.1) to enhance readability. For example, the figure could illustrate the tree-forming process, such as how the root node $m$ is expanded, and display the node potential values within the tree to give readers a better understanding.

To sum up, this paper is technically solid in the field of black-box optimization. I recommend acceptance with a spotlight.
Decision: Accept (spotlight)