Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper is in the line of works that uses reinforcement learning for combinatorial optimization (CO) problems. The main contribution is the idea of training a population of complementary agents for a given distribution of CO problems, with the objective function being optimizing the performance of the best agent instead of the average. The proposed training approach, POPPY, is evaluated on three benchmark tasks, including TSP, CVRP, and KP. It shows state-of-the-art performance on the TSP task. 
strength_and_weaknesses: Strengths: 
1) Using RL for CO problems is an interesting topic and of practical importance. 
2) The idea of training a (diverse) population agents for CO problems is interesting and novel. 
3) The rationale behind POPPY is well-motivated with the discusison of the line of related works, as well as using the simple example in Figure 1.
4) It shows considerable improvement over SOTA RL methods on the TSP benchmark task. 

Weaknesses:
1) The empirical evaluation is not entirely convincing -- 
1a) The improvements over SOTA RL methods like POMO are generally small on all of the three tasks. POMO itself is already pretty close to optimal solution, so that the edge of POPPY is barely significant (it is unclear if the authors have done t-tests). The evaluation would be more convincing if the authors can show that POPPY has more significant improvements. 
1b) On the CVRP task, POPPY is outperformed by EAS. 
1c) The baselines are missing for the KP task, making it even more challenging to evaluate the performance of POPPY. 

2) There are many engineering heuristics to make the system work (e.g., when to freeze or unfreeze the encoder, whether or not the optimal solution depends on the starting point). Therefore, the overall performance may be fragile to the specific training architecture. Especially that the edge of POPPY seems to be small compared to the baselines, so that it is questionable whether these kind of improvements are due to engineering tricks or structured improvements due to maintaining a population of agents. Also, the results may be hard to reproduce.  

3) It is unclear to me where the "diversity" in the population of agents lies in the objective function. It appears that POPPY is training a large set of agents with different policies, so that one of them "happens" to be good at a certain problem instance. As a fair comparison, perhaps you should separately train 16 POMO/LIH/EAS, and compare POPPY-16 with the best performance of those 16 policies. It is questionable whether POPPY can beat such a strong baseline. 
clarity,_quality,_novelty_and_reproducibility: My evaluation has 4 levels: Excellent, good, fair, poor. 

Clarity: fair. The claim that the method is "theoretically grounded" seems not to be supported. The lower bound of the objective is too weak to be a theory and people generally think of a gaurantee of some kind of performance when you say that. 

Quality: fair. 

Novelty: Excellent. This is a novel idea! 

Reproducibility: Fair. The description of the method seems clear and the method itself (the key idea) is not complicated. But there are some engineering tricks that make it a bit challenging to reproduce. 
summary_of_the_review: The idea of training a diverse population of agents to solve CO problems is generally interesting, novel, and well-motivated. But it is not clear where diversity is encouraged, and the evaluation is not entirely convincing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes Poppy, an RL-based approach to learn a population of constructive heuristics for combinatorial optimization problems.   The presented architecture is based on the encoder-decoder Attention Model, with a shared encoder and one decoder per agent of the population. Starting from a pretrained model, Poppy training is based on a policy gradient that only depends on the performance of the best agent for each instance; and serves to only update that agent’s parameters. Poppy is evaluated on three well-known CO problems: the TSP, CVRP and KP. 
strength_and_weaknesses: **Strengths**
1. The paper is clear and very well-written.
1. The idea of using a population of agents is well motivated.
1. The proposed loss that enables an effective diversity without explicitly guiding the specialization seems general enough and could be used in other contexts.
1. Experimental evaluation shows strong results on the selected tasks.

**Weaknesses**
1. A very similar idea of training multiple decoders for the Attention Model was explored in MDAM [1] and applied to the TSP and CVRP:
   * As far as I can see, the main contribution/difference of the present paper w.r.t MDAM is the different loss -- which considerably limits the novelty of the paper. 
   * Although the experimental results of the present paper seem stronger, this can also come from using POMO [2] training which is known to significantly improve the AM performance.
   * Including a precise discussion of the differences w.r.t to MDAM and including it in the experiments baselines would be useful.

1. The experimental evaluation focuses on datasets (synthetic TSP/CVRP instances with 100, 125 or 150 nodes and KP with 100 or 200 items) that do not seem challenging enough, today, for learning-based methods. Indeed:
    * The reported optimality gap of existing learning-based methods is already very small: less than 0.01% for TSP100 and 0.2% for TSP150, and less than 0.005% for the KP. These are already very good to excellent for heuristics in general.
    * In this context, even dividing the opt gap by 5 (as claimed in the abstract for TSP) does not seem very significant to me. This is especially visible in Table 3.
    * The scale of these problems is quite small compared to what other learning-based methods are able to solve (e.g. [3] solves TSP instances with up to 10,000 nodes, with supervision only on small graphs)
    * I would suggest to explore more challenging problems (e.g. larger sizes) to really showcase the experimental value of the proposed approach.
 
1. I can see the interest of having a population of agents in Fig 3;  however, (again) the gains seem very small: 
    * in Fig 3 bottom left, we see that removing 1 agent from the population would lead to a deterioration of the opt gap of at most ~ 0.0004%. 
    * This raises the question of is it because the opt gap is already very small (cf previous point) or is it the influence of the individual agents that is not significant (i.e. how different are the agents). 
    * I wonder how, for example, taking the best of 4 samples x 4 agents would compare to greedily using 16 different agents. 


[1] Xin et al, Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems, AAAI 2021

[2] Kwon et al, POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, Neurips 2020

[3] Fu et al, Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances, AAAI 2021


clarity,_quality,_novelty_and_reproducibility: **Clarity & Quality**:
The paper is clear and very well-written, I enjoyed reading it. The idea of using a population of agents for CO is well motivated and illustrated on an intuitive example. Different plots (Fig 3) help to understand the effects of the proposed approach.

**Originality**:
Because of an existing closely related work [1], the technical originality is limited (see Weakness 1). In terms of experiments, the datasets and settings are standard.

**Reproducibility**: 
The experimental setting is described in detail; the code and datasets are not provided but it looks like they would be after the double-blind reviewing period.

**Questions/remarks:**

1. In Algorithm 1, the two last lines, I could not see how these formulas allow to only update the parameters of the “best” decoder for each trajectory.

1. About the Training Procedure, I wonder if there is any intuition on how to fix the number of training steps of phase 2. If too small, the mentioned imbalance between the decoders is an issue; if too large I guess the decoders may become too similar. Aside from tuning this number experimentally, I wonder if there is any criteria that can be used to switch from phase 2 to 3. 

1. A related work that's worth mentioning: [4].

[4] Kim et al, Learning Collaborative Policies to Solve NP-hard Routing Problems, Neurips 2021


summary_of_the_review: I would vote for reject, because of the combination of:

(i) The limited novelty, especially w.r.t [1]: since the population aspect has already been explored with a similar architecture for similar problems, the main novelty seems to be the loss -- although I encourage the authors to make a precise comparison and update their claims.

(ii) The experimental evaluation is not convincing because, in my opinion, it shows marginal gains on tasks where learning-based methods have already achieved excellent results. Evaluation on more challenging problems/settings (e.g larger instances) would greatly increase the empirical value of this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In summary, from top to bottom, the paper: 
* Attempts to explain why a population of agents may be more useful than a single agent, under a theoretical formulation of argmax(multiple agent outputs).
* Presents a lower bound objective which leads to a variant of policy gradient which involves only updating the policy which generated the best trajectory per problem instance.
* Sets up the architecture as a shared encoder but with multiple decoders to denote multiple policies.
* Demonstrates competitive experimental performance against classic and deep-learning based baselines in the literature, especially normalizing for wall-clock time.
strength_and_weaknesses: # Strengths
* Extensive experimental results demonstrate that the method empirically is solid. A brief read over the Appendix also contains relevant ablation studies, such as checking the diversity of the population of policies.
* I applaud the paper for providing Figures 1 and 2, which makes the paper more engaging to read, and also help explain the encoder/decoder method much better. 


# Weaknesses
* The theoretical motivations are quite subtle and I have quite a few questions, which if answered, could help make the paper much stronger in its theoretical/fundamental contributions:
    * How is the framework similar/different from e.g. describing evaluation objective as a maximum of $K$ sampled trajectories from a (potentially very expressive) policy $\pi_{\theta_{meta}}$? In the $K=2$ case, $\pi_{\theta_{meta}}$ for example, could be a very bimodal policy which can also produce diverse behaviors from its two modes.
    * Is Algorithm 1 an unbiased policy gradient estimator of $J_{poppy}$? 
    * The method has no explicit objective/regularizer to maximize behavioral diversity, but instead implicitly assumes that this occurs through the "argmax" training in Algorithm 1. Is there a way to theoretically capture/analyze this "implicit regularization"? Currently it seems that the behavioral diversity isn't theoretically guaranteed, but rather occurs I suspect mainly if the beginning of training allows each agent to "latch on" to their own specific strategy.
    * Algorithm 1 is written somewhat specifically for this particular case involving a shared encoder and multiple decoders. Can it be re-written as a general RL method? 
clarity,_quality,_novelty_and_reproducibility: **Clarity and Quality:** My main concern is with the theoretical motivations. Please see above in "Weaknesses". Furthermore, there are some presentation issues, e.g. Figure 3 is not described very well / the plots are confusing and unclear of their purpose. Otherwise the experimental results appear to be solid.

**Novelty and Originality:** The proposed idea has **potential** to be quite novel, if the theoretical components are analyzed better. However, currently it is presented as a somewhat ad-hoc experimental method.
summary_of_the_review: The experimental results are fine. However, I would really like to see more theoretical analysis of the proposed method, which would significantly increase the impact of the paper and also broaden its scope. Otherwise, currently from a devil's advocate point of view, the proposed method may be considered somewhat of a "hack" currently.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a new ensemble method for solving combinatorial optimization problems using RL. While the studied problem is a relevant and interesting application of RL, all reviewers agree that the technical novelty of the proposed algorithm is limited, and the experimental evaluation is weak: (1) the evaluated tasks are too simple, they are small-size synthetic problems; (2) the proposed method only slightly outperforms baselines, even many hand-tuning. I vote for rejection.
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Reject