Monte Carlo Tree Search based Space Transfer for Black Box Optimization

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

Q1: Running time and computational cost analysis

Thanks for your valuable suggestions. Please refer to Q1 in general response.

Q2: Discussion between the state value in MCTS of AlphaZero and MCTS-Transfer

Good 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.

[1] A general reinforcement learning algorithm that masters chess, shogi and Go through self-play. Science, 2018.

[2] Practical Two-Step Look-Ahead Bayesian Optimization. NeurIPS, 2019.

[3] Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need. ICML, 2024.

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

Q1: How does MCTS iteratively divides and selects subspaces?

We're sorry that we didn't make this part clear.

• 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.

• 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.

Q2: Comparison with more advanced baselines

Thanks 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.

Q3: Discuss the adaptability of MCTS-transfer to different problem domains and its scalability to very large search spaces

Thanks for your valuable comments.

• 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.

• 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.

Please see Q2 in general response for details.

Q4: Lack of theoretical analysis

Thank 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:

• 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.

• 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.

We will add this discussion into our main paper and leave it as our future work. Thank you.

[1] Multi-Objective Optimization by Learning Space Partitions. ICLR, 2022.

[2] Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. ICML, 2010.

Q5: Reproducibility issue

Our 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.

Q6: How does MCTS-transfer handle the computational overhead introduced by the MCTS component, especially in large and complex search spaces?

We 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.

Q7: Provide more specific examples or case studies where MCTS-transfer significantly outperforms other methods

MCTS-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.

Q8: Provide a more comprehensive discussion on the limitations of their method

Apart 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.

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.

Q1: The running time comparison of each iteration

Thank you for your valuable suggestions. Please refer to Q1 in general response.

Q2: Explain the lack of blue line in the right subfigure of Figure 1(b)

In 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).

Q3: In Figure 2(b), PFN is better than MCTS-transfer; Combining MCTS-transfer with advanced BO algorithms to achieve better performance.

Thanks 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.

We 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.

Q4: Explain line 346,347

We are sorry for not expressing it clearly. In 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.

Q5: How to set $\gamma$ and $\alpha$ in practice?

$\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.

Q6: Remove treeify to appendix; Some typos in paper

Thank 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.

Thank you for carefully reviewing our paper and providing constructive comments, which have helped improve the work a lot. Below please find our responses.

Q1: Lack of theory

Thank 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:

• 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.

• 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.

We will add this discussion into our main paper and leave it as our future work. Thank you.

[1] Multi-Objective Optimization by Learning Space Partitions. ICLR, 2022.

[2] Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. ICML, 2010.

Q2: Lack of runtime analysis and reconstruction frequency analysis

Thank you for your valuable suggestions. Please refer to Q1 in general response.

Q3: When is the search space clustering updated?

We 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.

Q4: The real-world problems are relatively simple

Thanks 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.

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

Q5: How to do the search-space division for conditional search spaces?

Thanks 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$ is 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.

[1] Additive Tree-Structured Covariance Function for Conditional Parameter Spaces in Bayesian Optimization. AISTATS, 2020.

Q6: The limitations of the work

Thanks 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.

I thank the authors for their detailed response which have answered my questions and confirmed my rating.