Monte Carlo Tree Search based Space Transfer for Black-box Optimization

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.

Strengths

1. The paper is well written, and is easily to understand. 2. The experiments are conducted extensively and demonstrate the effectiveness of the algorithm across numerous application scenarios. 3. 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. 2. 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$?

Questions

Please refer to the weakness part.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Please refer to the weakness part.

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.

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

Questions

1. How does MCTS-transfer handle the computational overhead introduced by the MCTS component, especially in large and complex search spaces? 2. Can the authors provide more specific examples or case studies where MCTS-transfer significantly outperforms other methods? 3. What measures have been taken to ensure the reproducibility of the results? Is the code and dataset publicly available?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

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.

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.

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. In 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. The 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. The 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. Overall, 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. In the right subfigure of Figure 1(b), no blue line? In 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? Lines 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? I suggest moving the pseudo-code of Algorithm 1 (Treeify) to appendix. Instead, you can include more experimental results in the main paper. For the hyper-parameters \gamma and \alpha in equation 3 and 4, how to set them in practice? Though the paper is overall well written, there are still some types. -- line 310: 3 search space transfer algorithms -> three search space transfer algorithms -- line 311: figure 1 -> Figure 1; line 322: figure 1 -> Figure 1; Please check throughout the paper. -- line 330: The sentence “The detailed experimental results …” is redundant. -- line 334: mcts-transfer -> MCTS-transfer -- line 336: “equal” -> “reach” -- line 337: “surprising performance”, I suggest using “superior performance”. The results are good, but not surprising. -- line 339: “We test” -> “we test” -- line 344: “in the RobotPush” -> “in RobotPush” -- line 354: “close final and random final”? -- line 360-361: in D -> in Appendix D; but it can -> it can -- line 600: missing the period -- line 621: \alpha -> and \alpha -- line 643-645: the sentence is not well written. -- line 641, 646: check the missing and redundant blank -- Caption of Figure 13: Real-World Problem -> Real-World Problems

Questions

See weakness.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

Yes.

Summary

The paper proposes a tree-based search space division to enable transfer across different instances of related optimisation problems. The 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. The 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.

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. To 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. The 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. I 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. Beyond this, some minor points for consideration are: - 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? - 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

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? 2. Could the authors comment on how the search-space division is done for conditional search spaces (e.g. in the hyperparameter optimization settings)?

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

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.