Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes two novel methods for neural-network-based combinatorial optimization.
The two methods, SGBS and SGBS+EAS show promising performance for solving three types of combinatorial optimization problems (TSP, CVRP, and FFSP).

strengths_and_weaknesses: Strengths:
The authors proposed Simulation-Guided Beam Search (SGBS), combining Monte-Carlo Tree Search (MCTS) and beam search.
SBGS is also combined with an interesting existing technique, Efficient Active Search (EAS), which updates a small part of the network during the search.
The experiments show that SGBS+EAS performs better than many existing approaches.

Weaknesses:
The novelty is somewhat limited.
The key idea of EAS is already proposed in [1].
SGBS is very similar to an existing work, Monte-Carlo Beam Search [41].
The contribution of this paper is to prove that EAS works well when combined with MCTS.
questions: In my understanding, in the EAS paper [1], the solutions are simply sampled from the model.
Was there any theoretical/practical difficulty in extending the idea to MCTS?

I agree that SGBS easily utilizes batch parallelism, but it is not the only way.
Have you considered comparing the proposed method with existing parallel MCTS?
In my intuition, parallel MCTS equipped with progressive widening may also perform.

---
Post rebuttal comments.

Thank you for the detailed comment.
However, I did not think I needed to change my score.
limitations: There is a discussion about the two hyperparameters $\beta$ and $\gamma$.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper presents a Beam Search strategy augmented with Monte Carlo Rollouts evaluating the “return” potential of a sampled action, instead of the commonly used policy likelihood. Besides the immediate advantage of using a search mechanism on top of a network inference (as opposed to a single-shot inference), the paper highlights that the rollouts can act as a recourse mechanism to rectify incorrect decisions made by the network (when selecting the top-k most likely actions). To leverage the additional time allocated to the generation of a solution, the method is combined with the recently published Efficient Active Search (EAS) method. The paper shows interesting synergies between these two components. The approach and its variants are validated on a set of combinatorial optimization problems (TSP, CVRP, FFSP) as well as compared to Beam Search, EAS, MCTS and non-adaptive methods.
strengths_and_weaknesses: **Originality**

The method presented is relatively simple, i.e. augmenting the beam search procedure with greedy rollouts. Although I'm not aware of the exact same scheme being published before, the originality of the method is limited. In addition, most of the performance is driven by EAS. Interesting synergies are highlighted and constitute a novel contribution. Overall, although the method is well described and investigated, the originality and contribution are slightly under expectations.

**Significance**

Machine Learning for Combinatorial optimization problems is an important area of research as this family of problem it underlies many real-life applications. I don't consider the search mechanism to be of significant importance but rather see an interest in the discussion around EAS + SGBS. The search is however a good suggestion for practitioners to easily implement a lookahead mechanism (easier and more scalable than MCTS). 

**Quality:**

The paper is technically strong. The results are well reported (tables and figs), documented and discussed. The balance in the level of details provided in the main text and the appendix is adequate for the reader.

**Clarity:**

The quality of the writing meets the expected standards. The content is well structured and logically organized. The results are appropriately reported and discussed.
questions: - The rollout mechanism depends on the neural network as well — Could an argument be made against the fact that we assume that the network might make a mistake at step *t* but then takes a sensible sequence of greedy actions till the end of the episode (recourse mechanism of the SGBS)?
- Caption of Fig 2: “All methods evaluate the same number of candidate solutions per problem instance.” Can you describe what it means in terms of MCTS simulations, Gradient descents applied to the network for Active Search, etc?
- Fig 2 - What do these numbers vary as we grow or reduce the compute budget. Here the setup has been set to favour SGBS using (β = 4, γ = 4). Does the MCTS reach a higher asymptotic performance when given additional time? Given that the authors mentioned in the appendix that SGBS quickly plateaus, where (resources) do the methods cross in terms of performance? I'm surprised that a simple Beam Search with a random rollout to evaluate the nodes outperform the more structured MCTS search. Could the authors provide additional details on this?
- Fig 2c - why does the MCTS’s performance not follow the same performance trend as the SGBS when fine-tuning the model? SGBS seems to benefit more than the MCTS when the model is fine-tuned.
- I haven’t found the implementation of the MCTS or the Beam/SGBS search in the code linked to the paper. It seems that only the networks and environments are made available. Will that change in the future?
limitations: -
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces a general approach for solving combinatorial optimization problems using a hybrid Beam-Search approach that can update it's policy on the fly. In contrast to work that focuses on improving policy towards getting solutions in a single shot, this work attempts to make better use of available computation.  One trick here is replacing the compute-intensive MTCS with a simpler Beam-search to pick rollout candidates. Additionally, the authors use EAS to update the policy network to make more effective choices at test time. This paper contribution is in domains where queries to a ground truth simulator are cheap but the search space is combinatorial. 
strengths_and_weaknesses: ### Strengths
- Well-motivated paper. 
- Clean execution. 
- Code is provided and readable. 
- Algorithm is tested on reasonable benchmarks.

- I appreciated the section on the algorithm's strengths. 


### Weaknesses
Overall I found it a good paper, no major flaws. 
questions: .
limitations: I'm limited in my ability to evaluate this paper, especially in the broader context. I read the paper, and understand the main points, but I cannot place it in the wider literature. 

I'm confident it is well executed, and sensible in it's approach.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the problem of solving NP-hard combinatorial optimisation (CO) problems efficiently and near-optimally using machine learning, specifically in the context of beam search. Recent works have sought to use neural networks to evaluate and select candidates with the beam search optimisation heuristic, iteratively building partial solutions with the use of a decision tree in a breadth-first search manner until a near-optimal solution is found. However, such approaches are vulnerable to poor action evaluations made by any of the neural network’s imperfect predictions, which can be detrimental to overall performance.

To address this, the authors propose a simple algorithm, simulation-guided beam search (SGBS), which combines neural beam search with simulated rollouts similar to those used in Monte Carlo Tree Search (MCTS) algorithms but without the need for potentially complex state-action value backpropagation. Specifically, at each step in constructing the partial CO solution and the next depth-layer of the search tree, SGBS selects a group of candidate actions using a neural network to predict their complete CO solution score. It then simulates a greedy rollout from each of these actions to their terminal states, and then selects a sub-group (with size equal to the beam width) of these initially marked candidate actions to save in the search tree as the beam front, thus pruning initially marked actions with ultimately poor outcomes from the final search tree/solution. This process is repeated until a complete CO solution is found from root to leaf in the search tree.

Although SGBS alone performs well in time-restricted settings, the authors note that practitioners sometimes prefer allocating larger time budgets to find more optimal solutions. Since SGBS is a deterministic heuristic, it receives no benefit from larger time budgets other than adjustment of its hyperparameters, $\beta$ and $\gamma$, which the authors show have limited effect on performance beyond a certain point (which is quickly reached). To address this, the authors combine SGBS with the recently published ‘efficient active search’ (EAS) method of Hottung et al. 2022 to create a new algorithm, SGBS-EAS. The authors show that SGBS and EAS have a symbiotic relationship with one another whereby SGBS helps EAS to avoid local optimal while EAS provides an increasingly performant neural network model during test-time. Both SGBS and SGBS-EAS are shown to outperform some canonical CO heuristics and state-of-the-art ML solvers in both solution quality and solving time.
strengths_and_weaknesses: Strong points:
* All sections of the paper are excellently written and easy to understand.
* As far as I am aware, the idea to combine neural beam search and simulated rollouts in this way is novel, even if it is simple.
* The proposed method is easy to implement and integrate with existing neural beam search techniques.
* The experimental results outperform baselines on standard NP-hard CO problems; an important and significant application area of ML.

Weak points:
* Lack of comparison to/discussion of some other state-of-the-art graph neural network techniques which do not require simulated rollouts or search trees (see below).
* A few things which could be clarified (see below).
questions: * **Context and related work:** The proposed SGBS and SGBS-EAS algorithms, as well as the baseline agents compared to, rely on relatively expensive (in terms of both training time and inference) transformer models with additional training overhead at test time and/or simulated rollouts. Can the authors comment on how such techniques compare to other state-of-the-art ML-CO methods based on cheaper graph neural network models which do not require simulated rollouts (Dai et al. 2017, Abe et al. 2019, Li et al. 2018, Barrett et al. 2020 and 2022, Drori et al. 2020)? Would there be differences in optimality and training and inference time performance? Might the training overhead of EAS at test time incur disadvantages at test time in terms of both inference time and solution efficacy when initially deployed? How does SGBS/SGBS-EAS fit in the context of these other literature contributions?

* **Reward function:** In the SGBS Methodology section, the authors state that $P$ represents a set of target problem instances from which they sample different ‘reward functions’ $R’(S_N)$ during training, which enables the neural network to exploit the limited size of the distribution $P$ rather than having to train for the entire problem space. I’m not entire sure what this means - is it that $S_N$ (i.e. the final solution found by the RL agent) is changing and therefore that the total return evaluated by the reward function is changing (since the RL agent explores during training), or are the authors actually using different reward functions to evaluate the same solution $S_N$ in different ways? If the latter, what reward functions are used? How can the RL agent learn to predict the values of states and actions when the reward function in the MDP is changing? I do not entirely follow this MDP formulation or which reward function(s) were used for each CO problem class.

* **Action sampling methodology:** What policy is used for selecting actions in the SGBS greedy rollouts? Is it just the argmax of the $\pi_\theta(\cdot | s_{d})$ policy of the neural network, or some other heuristic?


### Miscellaneous minor issues
* Fig 1: Would be useful to have a key showing what the different colours, fills, and shapes of search tree edges and nodes mean. Also it may be helpful to add in the caption that Fig 1 is an SGBS step at $d=2$ for clarity

* Pg 7 line 218: ‘the’ typo: ‘...are displayed with the respect to...’

* Pg 4 line 129: Should ‘...the rewards are tagged to the...’ be ‘...the returns are tagged to the...’ given standard RL jargon which refers to per-step evaluation signals as rewards and total cumulative rewards across the episode as returns?


### References

* Andre Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. International Conference on Learning Representations, 2022.
* Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017
* Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving NP-Hard Problems on Graphs by Reinforcement Learning without Domain Knowledge. arXiv:1905.11623, 2019
* Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. In Advances in Neural Information Processing Systems, 2018
* Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020
* Thomas D. Barrett, Christopher W. F. Parsonson, and Alexandre Laterre. Learning to solve combinatorial graph partitioning problems via efficient exploration. arXiv:2205.14105, 2022
* Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. arXiv:2006.03750, 2020
limitations: N/A
review_title: null

Meta-review: metareview: The paper follows in the footsteps of alpha go and presents two methods for neural-network guided search, targeting in particular beam search. The paper was deemed a bit incremental, but the method is simple, is easier to parallelize than MCTS and obtains good results on problems under-explored in machine learning. Please review related literature in AI for games and neural guided search techniques in discrete inference.

confidence: Less certain
Decision: Accept