Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization
Authors: Nathan Grinsztajn
Daniel Furelos-Blanco
Shikha Surana
Clément Bonnet
Thomas D Barrett
Venue: NeurIPS 2023 poster (2023)
Keywords: Combinatorial Optimization
Reinforcement Learning
TSP
CVRP
JSSP
TL;DR: We present a population-based RL method for CO problems: the training procedure makes the agents complementary to maximize the population's performance.

Abstract: Applying reinforcement learning (RL) to combinatorial optimization problems is attractive as it removes the need for expert knowledge or pre-solved instances. However, it is unrealistic to expect an agent to solve these (often NP-)hard problems in a single shot at inference due to their inherent complexity. Thus, leading approaches often implement additional search strategies, from stochastic sampling and beam-search to explicit fine-tuning. In this paper, we argue for the benefits of learning a population of complementary policies, which can be simultaneously rolled out at inference. To this end, we introduce Poppy, a simple training procedure for populations. Instead of relying on a predefined or hand-crafted notion of diversity, Poppy induces an unsupervised specialization targeted solely at maximizing the performance of the population. We show that Poppy produces a set of complementary policies, and obtains state-of-the-art RL results on three popular NP-hard problems: traveling salesman, capacitated vehicle routing, and job-shop scheduling.

Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization
Nathan Grinsztajn InstaDeep n. grinsstajnninssadegg.p.. com
Daniel Furelos-Blanco Imperial College London"
Shikha Surana InstaDeep
Clément Bonnet InstaDeep
Thomas D. Barrett InstaDeep
Abstract
Applying reinforcement learning (RL) combinatorial optimization problems is attractive as it removes the need for expert knowledge or pre-solved instances. However, it is unrealistic to expect an agent solve these (often NP-)hard prob- lems in a single shot at inference due to their inherent complexity. Thus, leading approaches often implement additional search strategies, from stochastic sampling and beam-search to explicit fine-tuning, In this paper, we argue for the benefits of learning population of complementary policies, which can be simultancously rolled out at inference. To this end, we introduce Poppy, a simple training proce- dure for populations. Instead of relying on predefined or hand-crafted notion of diversity, Poppy induces an unsupervised specialization targeted solely at maxi- mizing the performance of the population. We show that Poppy produces a of complementary policies, and obtains state-of-the-art RL results on four popular NP-hard problems: traveling salesman, capacitated vehicle routing, 0-1 knapsack, and job-shop scheduling.
1 Introduction
In recent years, machine learning (ML) approaches have overtaken algorithms that use handcrafted features and strategies across variety of challenging tasks [Mnih al., 2015, den Oord et al., 2016, Silver et al., 2018, Brown et al., 2020J. In particular, solving combinatorial optimization (CO) problems where the maxima minima of objective function acting a finite set of discrete variables is sought - has attracted significant interest [Bengio et al., 2021] due to both their (often NP) hard nature and numerous practical applications across domains varying from logistics [Sbihi and Eglese, 2007] to fundamental science [Wagner, 2020].
As the search space of feasible solutions typically grows exponentially with the problem size, exact solvers can be challenging to scale; hence, CO problems are often also tackled with handerafted heuristics using expert knowledge. Whilst diversity of ML-based heuristics have been proposed, reinforcement learning [RL: Sutton and Barto, 201 8] is a promising paradigm as it does not require pre-solved examples of these hard problems. Indeed, algorithmic improvements to RL-based CO solvers, coupled with low inference cost, and the fact that they are by design targeted at specific problem distributions, have progressively narrowed the gap with traditional solvers.
RL methods frame CO as sequential decision- decision-making problems, and can divided into two families [Mazyavkina al., 2021]. First, improvement methods start from feasible solution and iteratively
Work completed during an internship at InstaDeep.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

improve it through small modifications (actions). However, such incremental search cannot quickly access very different solutions, and requires handcrafted procedures to define a sensible action space, Second, construction methods incremenaally build a solution by selecting one element at time. In practice, it often unrealistic for learned heuristic to solve NP-hard problems in a single shot, therefore these methods are typically combined with search strategies, such as stochastic sampling or beam search. However, just as improvement methods are biased by the initial starting solution, construction methods are biased by the single underlying policy. Thus, balance must be struck between the exploitation of the learned policy (which may be ill-suited for given problem instance) and the exploration of different solutions (where the extreme case of purely random policy will likely be highly inefficient).
In this work, we propose Poppy, a construction method that uses population of agents with suitably diverse policies to improve the exploration of the solution space of hard CO problems. Whereas single agent aims to perform well across the entire problem distribution, and thus has to make compromises, a population can learn a set of heuristics such that only one of these has to be performant on any given problem instance. However, realizing this intuition presents several challenges: (i) naively training a population of agents expensive and challenging to scale, (ii) the trained population should have complementary policies that propose different solutions, and (iii) the training approach should not impose any handcrafted notion of diversity within the set of policies given the absence of clear behavioral markers aligned with performance for typical CO problems.
Challenge (i) can be addressed by sharing large fraction of the computations across the population. specializing only lightweight policy heads to realize the diversity of agents. Moreover, this can be done on top of a pre-trained model, which we clone to produce the population. Challenges (ii) and (iii) are jointly achieved by introducing an RL objective aimed at specializing agents on distinct subsets of the problem distribution. Concretely, we derive a policy gradient method for the population-level objective, which corresponds to training only the agent which performs best on each problem. This is intuitively justified as the performance of the population on a given problem is not improved by training an agent an instance where another agent already has better performance. Strikingly, we find that judicious application of this conceptually simple objective gives rise to population where the diversity of policies is obtained without explicit supervision (and hence is applicable across range of problems without modification) and essential for strong performance.
Our contributions are summarized as follows:
1. We motivate the use of populations for CO problems an efficient way to explore environ- ments that are not reliably solved by single-shot inference.
2. We derive a new training objective and present a practical training procedure that encourages performance-drive diversity (i.e. effective diversity without the use of explicit behavioral markers other external supervision).
3. We evaluate Poppy on four CO problems: traveling salesman (TSP), capacitated vehicle routing (CVRP), 0-1 knapsack (KP), and Poppy consistently outperforms all other RL-baased approaches.
jo job-shop scheduling (JSSP). In these four problems,
2 Related Work
ML for Combinatorial Optimization The first attempt to solve TSP with neural networks is due to Hopfield and Tank [1985], which only scaled up to 30 cities. Recent developments of bespoke neural architectures [Vinyals et al., 2015, Vaswani et al., 2017] and performant hardware have made MI. approaches increasingly efficient. Indeed, several architectures have been used to address CO problems, such as graph neural networks [Dai al., 2017], recurrent neural networks [Nazari et al., 2018], and attention mechanisms [Deudon et al., 2018]. Kool et al. [2019] proposed an encoder- decoder architecture that we employ for TSP, CVRP and KP. The costly encoder is run once per problem instance, and the resulting embeddings are fed to a small decoder iteratively rolled out to get the whole trajectory, which enables efficient inference. This approach was furthered by Kwon et al. [2020] and Kim et al. [2022], who leveraged the underlying symmetries of typical CO problems (e.g. of starting positions and rotations) to realize improved training and inference performance using instance augmentations. Kim et al. [2021] also draw on Kool et al. and use hierarchical strategy where a seeder proposes solution candidates, which are refined bit-by-bit by reviser. Closer to our work, Xin et al. [2021] train multiple policies using shared encoder and separate decoders.
2

---

Whilst this work (MDAM) shares our architecture and goal of training a population, our approach to enforcing diversity differs substantially. MDAM explicitly trades off performance with diversity by jointly optimizing policies and their KI. divergence. Moreover, as computing the KI. divergence for the whole trajectory is intractable, MDAM is restricted to only using to drive diversity at the first timestep. In contrast, Poppy drives diversity by maximizing population-level performance (i.e. without any explicit diversity metric), uses the whole trajectory and scales better with the population size (we have used up to 32 agents instead of only 5).
Additionally, ML approaches usually rely on mechanisms to generate multiple candidate solutions [Mazyavkina et al., 2021]. One such mechanism consists in using improvement methods on an initial solution: de O. da Costa et al. [2020] use policy gradients to learn a policy that selects local operators (2-opt) given a current solution in TSP, while Lu et al. [2020] and Wu et al. [2021] extend this method to CVRP. This idea has been extended to enable searching a learned latent space of solutions [Hottung et al., 2021]. However, these approaches have two limitations: they are environment-<pecific, and the search procedure is inherently biased by the initial solution.
An alternative exploration mechanism is to generate a diverse set of trajectories by stochastically sampling a learned policy, potentially with additional beam search [Joshi et al., 2019], Monte Carlo tree search [Fu et al., 2021]. dynamic programming [Kool et al., 2021], active search [Hottung et al., 2022], or simulation senuiddtoo-uuiedd search [Choo et al., 2022]. However, intuitively, the generated solutions tend to remain close to the underlying deterministic policy, implying that the benefits of additional sampled candidates diminish quickly.
Population- RL Populations have already been used in RL to learn diverse behaviors. In different context, Gupta et al. [2018], Eysenbach al. [2019], Hartikainen et al. [2020] and Pong et al. [2020] use a single policy conditioned on a set of goals as an implicit population for unsupervised skill discovery. Closer to our approach, another line of work revolves around explicitly storing a set of distinct policy parameters. Hong et al. [2018], Doan et al. [2020], Jung et al. [2020] and Parker-Holder et al. [2020] use a population to achieve a better coverage of the policy space. However, they enforce explicit sttractionrrepussion mechanisms, which is major difference with respect to approach where diversity is a pure byproduct of performance optimization.
Our method is also related to approaches combining RL with evolutionary algorithms [EA; Khadka and Tumer, 2018, Khadka et al., 2019, Pourchot and Sigaud, 2019], which benefit from the sample- efficient RL. policy updates while enjoying evolutionary population-level exploration. However, the population is a means to learn unique strong policy, whereas Poppy learns a set of complementary strategies. More closely related, Quality-Diversity [QD; Pugh et al., 2016, Cully and Demiris, 2018] is a popular EA framework that maintains a portfolio of diverse policies. Pierrot et al. [2022] has recently combined RL with a QD algorithm, Map-Elites [Mouret and Clune, 2015]; unlike Poppy, QD methods rely on handcrafted behavioral markers, which is not easily amenable to the CO context.
One of the drawbacks of population-base RL is its expensive cost. However, recent approaches have shown that modern hardware, as well as targeted frameworks, enable efficient vectorized population training [Flajolet et al., 2022], opening the door to wider range of applications.
3 Methods
3.1 Background and Motivation
RL Formulation A CO problem instance p sampled from some distribution D consists of a discrete set of N variables (c.g. city locations in TSP). We model CO problem as Markov decision process (MDP) defined by a state space S, an action space A, transition function T, and reward function R. A state is a trajectory through the problem instance т₁ (I1,..., .I1) E S where I; E p. and thus consists of an ordered list of variables (not necessarily of length N). An action, a E A S p. consists of choosing the next variable to add; thus, given state = (æ1...., .Fa) and action a, the next state is Th+1 T(Tr.a) a) = (fI,..., Lt, a). Let S* C S be the set of solutions, i.e. states that comply with the problem's 's constraints (e.g., sequence of cities such that each city is visited once and ends with the starting city in TSP). The reward function R : S* -> IR maps solutions into scalars. We assume the reward is maximized by the optimal solution (c.g. R returns the negative tour length in TSP).
3

---

A policy parameterized by 0 can be used to generate solutions for any instance P D by iteratively sampling the next action a E AA according to the probability distribution To(- r.). We learn using REINFORCE [Williams, 1992]. This method aims at maximizing the RI. objective J(O) = PEp-DEETTT... R(T) ) by adjusting such that good trajectories are more likely to be sampled in the future. Formally, the policy parameters 0 are updated by gradient ascent using Vo.(()) Epp.DErrro.. (R((T) bp) Ve (T)( where (T = II, ma (a++1 p, Te) and 6, is a baseline. The gradient of the objective, VaJ, can be estimated empirically using Monte Carlo simulations.
Left? Right? Anyway, up is safer...
Let's splin! I tuy left!
Ok! tzy right!
Sale (2)
Risky (0 3)
Risky (0 3)
O
IIIII
IIIII
IIII
Figure I: this environment, the upward path always leads to a medium reward, while the left and right paths are intricate such that either one may lead to low reward or high reward with equal probability. Left: An agent trained to maximize its expected reward converges to taking the safe upward road since acting optimally is too computationally intensive, requires solving the maze. Right: A 2-agent population can always take the left and right paths and thus get the largest reward.
Motivating Example We argue for the benefits of training a population using the example in Figure 1. In this environment, there are three actions: Left, Right, and Up. Up leads to medium reward, while Left/Right lead to low/high or high/low rewards (the configuration is determined with equal probability the start of each episode). Crucially, the left and right paths are intricate, the agent cannot easily infer from its observation which one leads to a higher reward. Then, the best strategy for a computationally limited agent always go Up, as the guaranteed medium reward (2 scoops) is higher than the expected reward of guessing left or right (1.5 scoops). In contrast, two agents in a population can go in opposite directions and always find the maximum reward. There are two striking observations: (i) the agents do not need to perform optimally for the population performance to be optimal (one agent gets the maximum reward), and (ii) the performance of each individual agent is worse than in the single-agent case.
The discussed phenomenon observations and (ii) choices are irreversible (i.e. it is not possible to recover from a sub-optimal decision). This problem setting can be CO problem in a sequential decision-making setting. In the case of TSP, for example, the number of possible unique tours that could follow from each action exponentially large and, for any reasonably finite agent capacity, essentially provides the same obfuscation over the final returns. In this situation, as shown above, maximizing the performance of population will require agents to specialize and likely yield better results than in the single-agent case.
occur when (i) some optimal actions are too difficult to infer from
toy model for the challenge of solving an NP-hard
3.2 Poppy
We present the components of Poppy: an RL objective encouraging agent specialization, and an efficient training procedure taking advantage of a pre-trained policy.
Population- Objective At inference, reinforcement learning methods usually sample several candidates to find better solutions. This process, though, is not anticipated during training, which optimizes the 1-shot performance with the usual RI objective [() Ep-DDET-S. R(T) previously presented in Section 1. Intuitively, given K trials, we would like to find the best set of policies {TI,..., JK} to rollout once given problem. This gives the following population objective:

---

(pop(0,......000
E.p-DBB - max (R(T))..... R(TK)];
where each trajectory is sampled according to the policy *e,- Maximizing Joop leads to finding the best of K agents which can be rolled out parallel for any problem.
Theorem (Policy gradient for populations). The gradient of the population objective is:
V po .2,.0.,, 0x)
unn (R((T=) I[(;;-))) pa,- pa,- (Ti=),
where: i" = arg max (I....K) [R(T:)] (index of the agent that got the highest reward) and i"
arg m [[(+)) (index of the agent that got the second highest reward).
The proof is provided in Appendix B.1. Remarkably, corresponds to rolling out every agent and only training the that got the highest reward any problem. This formulation applies across various problems and directly optimizes for population-level performance without explicit supervision handcrafted behavioral markers.
The theorem trivially holds when instead of population, one single agent sampled K times, which 0x. In this case, the gradient becomes:
falls back to the specific case where 01 0₂
pop (0) = I2 PEpDDDBB ptppp//l................... .x.............................. Tx (R(T.-) R( Po(;)))
Remark. The occurrence of R(T;--) in the new gradient formulation can be surprising. However, Theorem can be intuitively understood as training each agent on its true contribution to the population's performance: if for any problem instance the best agent was removed, the population performance would fallback to the level of the second-best agent i**, hence its contribution is indeed R(T,-) R.
Optimizing the presented objective does not provide any strict diversity guarantee. However, note that diversity maximizes our objective in the highly probable case that, within the bounds of finite capacity and training, single agent does perform optimally on all subsets of the training distribution. Therefore, intuitively and later shown empirically, diversity emerges over training in the pursuit of maximizing the objective.
Algorithm 1 Poppy training
1: Input: problem distribution D, number of agents K, batch size B, number of training steps H, pre-trained parameters 8.
2: 81, fg....., 0g + CLONE(() (Clone the pre-trained agent K times.)
3: for step to H do
4: Pi Sample (D) Vi E II...,,
5: T. Rollout (pr, 0k) Vi I,..., B, vk I....,
6: ky + arg maxxass R(T,)) Vi l.... B (Select the best agent for each problem pr.]
7: VI(O1..... 0k) + B E,SB (EINFORCE(T.")) (Backpropagate through these only.)
8: (01 (O1....., 0k) < (01 0k) aV.( .k)
Training Procedure
The training procedure consists of two phases:
1. We train (or reuse) single agent using an architecture suitable for solving the CO problem hand. We later outline the architectures used for the different problems.
2. The agent trained in Phase is cloned K times form K-agent population. The population is trained as described in Algorithm I: only the best agent is trained on any problem. Agents implicitly specialize in different types of problem instances during this phase.
Phase enables training the model without the computational overhead of a population. Moreover, we informally note that applying the Poppy objective directly to a population of untrained agents can be unstable. Randomly initialized agents are often ill-distributed, hence single (or few) agent(s) dominate the performance across all instances. this case, only the initially dominating agents receive a training signal, further widening the performance gap. Whilst directly training population
5

---

Node iapa
Node anbolling
pobebiiiy
Masicl
Irising
Frozen
V
R2
V
Ra
Encoder
Desoder
Ensoler
Desoders
Phases of the training process with a model using static instance embeddings. Left (Phase 1): the encoder and the decoder are trained from scratch. Right (Phase 2): the decoder is cloned K times, and the whole model is trained using the Poppy training objective (i.e. the gradient only propagated through the decoder that yields the highest reward).
Figure 2:
of untrained agents for population-level performance may be achievable with suitable modifications, we instead opt for the described pre-training approach as it is efficient and stable. Throughout this article, we use the reinforcement learning bascline of POMO [Kwon al., 2020], which was proved to be efficient when training with multiple starting points, We investigate in Appendix C the effect of using the analytical baseline from Theorem instead, which we show leads improved performance.
Architecture To reduce the memory footprint of the population, some of the model parameters can be shared. For example, the architecture for TSP, CVRP, and KP uses the attention model by Kool al. [2019], which decomposes the policy model into instance as imput and outputs embeddings w for each of the variables in p. and (ii) a smaller decoder ds that takes the embeddings w and trajectory Tt input and outputs the probabilities of each possible action. Figure illustrates the training phases of such a model. For JSSP, we implement similar encoder-decoder architecture taken from Jumanji [Bonnet et al., 2023] with the encoder being shared across the population. For all problems, we build population the encoder he with all agents, and implementing agent-specific decoders lo, for (1...., K). This is motivated by (i) the encoder learning general representations that may be useful to all agents, and (ii) reducing the parameter overhead of training a population by keeping the total number of parameters close to the single-agent case. Please see Appendix A. for a discussion on model sizes.
parts: (i) large encoder he that takes an
size K by sharing
4 Experiments
We evaluate Poppy on four CO problems: TSP, CVRP, KP and JSSP. We use the JAX implementations from Jumanji [Bonnet et al., 2023] to leverage hardware accelerators (e.g. TPU). To emphasize the generality of our method, we use the hyperparameters from Kwon et [2020] for each problem when possible. We run Poppy for various population sizes to demonstrate its time-performance tradcoffs.
Training One training step corresponds computing policy gradients CVRP, KP) or 128 (JSSP) randomly generated instances for each agent in the population. Training time varies with problem complexity and training phase. For instance, in TSP with 100 cities, Phase takes 4.5M steps (5 days), whereas Phase 2 takes 400k training steps and lasts 1-4 days depending on the population size. We took advantage of our JAX-based implementation by running all our experiments on v3-8 TPU.
batch of 64 (TSP,
4.1 Routing Problems (TSP, CVRP)
Tasks We consider two routing tasks: TSP and CVRP. Given a set of n cities, TSP consists in visiting every city once and coming back to the starting city while minimizing the total traveled distance. CVRP is variant of TSP where vehicle with limited capacity departs from depot node and needs to fulfill the demands of the visited nodes. The vehicle's capacity is restored when the depot is visited.

---

Setup We use an mncoder-decoder architecture based on that by Kool et al. [2019] and Kwon et al. [2020] (see Appendix E for details). During Phase an architecture with a single decoder is trained; then, the decoder is cloned for each agent in the population and trained according to Algorithm 1. Following Kwon al. [2020], we generate multiple solutions for each instance p by considering a set of P E [1, M] starting points, where N is the number of instance variables, and use the same reinforce baseline at training. We refer the reader to Appendix A.2 for details.
The training instances are of size n-- 100 in both tasks. The testing instances for n = 100 are due to Kool et al. [2019] and Kwon al. [2020] for TSP and CVRP, respectively, whereas those for E {125, 150} are due to Hottung et al. [2022].
Baselines We use the exact TSP-solver Concorde Applegate et al. [2006] and the heuristic solver HGS [Vidal et al., 2012, Vidal, 2022] to compute the optimality gaps for TSP and CVRP, respec- tively. The performance of LKH3 [Helsgaun, 2017] is also reported for TSP. We highlight that the performance of HGS is not necessarily optimal.
In both TSP and CVRP, we evaluate the performance of the RL methods MDAM [Xin et al., 2021] with and without beam search, LIH [Wu al., 2021], and POMO [Kwon et al., 2020] in three settings: (i) with greedy rollouts, (ii) using r stochastic rollouts, and (iii) using ensemble of r decoders trained in parallel. The value of r corresponds to the largest tested population (i.e., 16 in TSP and 32 in CVRP). Setting (ii) is run to match Poppy's runtime with its largest population, while Setting (iii) performs Phase 2 without the population objective. We also report the performance of the RL methods MC-GSRN+MCTS [Fu et al., 2021] and 2-Opt-DL [de O. da Costa et al., 2020] in TSP, and NeuRewriter [Chen and Tian, 2019] and NLNS [Hottung and Tierney, 2020] in CVRP.
Results Tables and 2 display the results for TSP and CVRP, respectively. The columns show the average tour length, the optimality gap, and the total runtime for each test set. The baseline performances from Fu et al. [2021], Xin et al. [2021], Hottung et al. [2022] and Zhang et al. [2020] were obtained with different hardware (Nvidia GTX 1080 Ti, RTX 2080 Ti, and Tesla V100 GPUs, respectively) and framework (PyTorch); thus, for fairness, we mark these times with *. As a comparison guideline, we informally note that these GPU inference times should be approximately divided by 2 to get the converted TPU time.
In both TSP and CVRP, Concorde and HGS remain the best algorithms as they are highly specialized solvers. In relation to RL methods, Poppy reaches the best performance across every performance metric in just a few minutes and, remarkably, performance improves populations grow.
In TSP, Poppy outperforms Att-GCRN+MCTS despite the latter being known for scaling to larger instances than = 100, hence showing it trades off performance for scale. We also empha- size that specialization is crucial to achieving state-of-the-art performance: Poppy 16 outperforms POMO 16 (ensemble), which also trains 16 agents in parallel but without the population objective (i.e. without specializing to serve as an ablation of the objective).
In CVRP, we observe Poppy 32 has the same runtime as POMO with 32 stochastic rollouts while dividing by 2 the optimal gap for n 100. Interestingly, this ratio increases on the generalization instance sets with n E {125, 150), suggesting that Poppy is more robust to distributional shift.
Analysis Figure 3 illustrates the resulting behavior from using Poppy on TSP100. We display on the left the training curves of Poppy for three population sizes: 4, 8, 16. Starting from POMO, the population performances quickly improve. Strikingly, Poppy 4 outperforms POMO with 100 stochastic samples, despite using 25 times fewer rollouts. The rightmost plot shows that whilst the population-level performance improves with population size, the average performance of a random agent from the population on a random instance gets worse. We hypothesize that this is due to agent specialization: when each agent has a narrower target sub-distribution, it learns even more specialized policy, which is even better (resp. worse) for problem instances in (resp. out) of the target sub-distribution. This is in contrast with simple policy ensemble, for which the average agent performance would remain the same regardless of the population size. Additional analyses are made in Appendix I. where we show that every agent contributes to the population performance. Overall, this illustrates that Poppy agents have learned complementary policies: though they individually
A fine- -ne-graieed comparison between POMO with stochastic sampling and Poppy is in Appendix F.
7

---

Table 1: TSP results.
Inference (10k instances)
0-shot (Ik instances)
100
71
125
150
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Concorde
7.765
0.000%
82M
8.583
0.000%
12M
9.346
0.000%
17M
LKH3
7.765
0.000%
8H
8.583
0.000%
73M
9.346
0.000%
99M
MDAM (greedy)
7.93
2.19%
36S
MDAM (beam search)
7.79
0.38%
44M"
AI-GCRN+MCTS
0.037%
15M
2-Opt-DL
7.83
0.87%
41M"
LIH
7.87
1.42%
2H
POMO
7.796
0.41%
5S
8.635
0.61%
1S
9.439
0.99%
1S
POMO (16 samples)
7.785
0.27%
IM
8.619
0.42%
10S
9.423
0.81%
20S
POMO 16 (ensemble)
7.790
0.33%
1M
8.629
0.53%
10S
9.435
0.95%
20S
Poppy 4
7.777
0.15%
20S
8.60S
0.26%
3S
9.389
0.46%
5S
Poppy 8
7.772
0.09%
40S
8.598
0.18%
68
9.379
0.35%
10S
Poppy 16
7.770
0.07%
1M
8.594
0.14%
10S
9.372
0.27%
20S
Table 2: CVRP results.
Inference (10k instances)
O-shot (Ik instances)
O-shot (1k instances)
n
100
= 125
11 = 150
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
HGS
15.56
0.000%
3D
17.37
0.000%
12H
19.05
0.000%
16H
LKH3
15.65
0.53%
6D
17.50
0.75%
19H
19.22
0.89%
20H
MDAM (greedy)
16.40
5.38%
45S
MDAM (beam search)
15.99
2.74%
53M"
LIH
16.03
3.00%
5H
NeuRewriter
16.10
3.45%
66M
NLNS
15.99
2.74%
62M
18.07
4.00%
9M'
19.96
4.76%
12M'
POMO
15.87
2.00%
10S
17.82
2.55%
28
19.75
3.65%
3S
POMO (32 samples)
15.77
1.31%
5M
17.69
1.82%
19.61
2.94%
1M
POMO 32 (ensemble)
15.78
1.36%
17.70
1.87%
19.57
2.73%
Poppy 4
15.80
1.54%
IM
17.72
2.01%
10S
19.61
2.95%
20S
Poppy 8
15.77
1.31%
2M
17.68
1.78%
20S
19.58
2.75%
40S
Poppy 32
15.73
1.06%
5M
17.63
1.47%
1M
19,50
2.33%
1M
perform worse than the single agent baseline POMO, together they obtain better performance than an ensemble, with every agent contributing to the whole population performance.
4.2 Packing Problems IKP,JSI)
Tasks
To showcase the versatility of Poppy, we evaluate our method on two packing problems: KP and ISSP. In KP, the goal is to maximize the total value of packed items. JSSP can be seen as 2D packing problem in which the goal is minimize the schedule makespan under set of constraints.
Setup For KP,, we employ the same architecture and training as for TSP and CVRP. For JSSP, we attention-based actor-critic architecture proposed by Bonnet et al. [2023] and use REINFORCE with a critic as a baseline to train our agents. Furthermore, akin to the other problems, we first train the agent until convergence and then duplicate the heads make our population (see Appendix for more details). In both problems, the evaluation budget consists of 1,600 samples per instance distributed over the population.
Baselines evaluate our method on against several baselines including the optimal solution
based on dynamic programming. greedy heuristic, and POMO [K et al., 2020]. For JSSP, we compare Poppy against the optimal solution obtained by Google OR-Tools [Perron and Furnon, 2019], L2D [Zhang al., 2020] with greedy rollouts and stochastic sampling (consisting of 8,000 samples

---

0.4
POMO (1 sample)
Poppy
10"
0.9
Poppy
Optimality gap (96)
Poppy
16
Optinulity gap (%)
0.3
POMO (100 samples)
Average agent Population
0.154
0.1
10
0.099 0,008
100000
200000
300000
Training steps
Poppy 4
Poppy
Poppy 16
Figure 3: Analysis of Poppy TSPI00. Left: Starting from POMO clones, training curves of Poppy for three different population sizes (4, 8, 16). Right: With the population objective, the average performance gets worse as the population size increases, but the population-level performance improves.
per problem instance) and our own implementation of MDAM using the same network architecture and budget Poppy.
Results Table 3 shows the results for KP (3a) and JSSP (3b). The columns indicate the final performance the set, which is the average values of items packed for KP and the average schedule duration for ISSP, the optimality gap and the total runtime these evaluations. The L,2 Intel Core 19-10940X CPU and single Nvidia GeForce 2080Ti GPU,
results were obtained and thus, their runtimes are marked with +.
The results from both packing problems demonstrate that Poppy outperforms other RL baselines. For KP, we observe that Poppy leads to improved performance with a population of 16 agents, dividing the optimality gap with respect POMO sampling and ensemble by factor of 12 and 42 for the exact same runtime. We emphasize that although these gaps seem small, these differences are still significant: Poppy 16 is strictly better than POMO in 34.30% of the KP instances, and better in 99.95%. For ISSP, we show that Poppy significantly outperforms L.D in both greedy and sampling settings, and closes the optimality gap by 14.1% and 1.8%, respectively. It should be noted that Poppy outperforms I.2D sampling despite requiring 5 times fewer samples. Additionally, to further demonstrate the advantages of training a population of agents, we compare Poppy with single attention-based model (method named Single) evaluated with 16 stochastic samples. The results show that given the same evaluation budget, Poppy outperforms the single agent and closes the optimality gap by further 1%.
Table 3: Packing problems results.
(b) JSSP
KP
Testing (100 instances)
Testing (10k instances)
10 x 10
100
Method
Obj.
Gap
Time
Method
Obj.
Gap
Time
OR-Tools (optimal)
807.6
0.0%
37S
Optimal
40.437
Greedy
40.387
0.1250%
L.D (Greedy)
988.6
22.3%
20S
L.2D (Sampling)
871.7
8.0%
8H"
POMO (sampling)
40.435
0.0060%
2M
POMO (ensemble)
40.429
0.021%
2M
MDAM
875.0
8.3%
40M
Poppy 16
40.437
0.0005 %
2M
Single (16 samples)
866.0
7.2%
30M
Poppy 16
857.7
6.2%
30M
Conclusions
Poppy a population-basee RI method for CO problems. uses an RI. objective that incurs agent specialization with the purpose of maximizing population-level performance. Crucially, Poppy does

---

not rely on handcrafted notions of diversity to enforce specialization. We show that Poppy achieves state-of-the-ar performance on four popular NP-hard problems: TSP, CVRP, KP and JSSP.
This work opens the door to several directions for further investigation. Firstly we have experimented on populations of at most 32 agents; therefore, it is unclear what the consequences of training larger populations are. Whilst even larger populations could reasonably be expected to provide stronger performance, achieving this may not be straightforward. Aside from the increased computational burden, we also hypothesize that the population performance could eventually collapse once no additional specialization niches can be found, leaving agents with null contributions behind. Exploring strategies to scale and prevent such collapses is an interesting direction for future work.
Secondly, work has built on the current state- of-the-art RL for CO approaches in single- or few-shot inference setting to demonstrate the remarkable efficacy of a population- approach. However, there other paradigms that could consider. For example, active-search methods allow an increased number of solving attempts per problem and, in principle, such methods for inference-time adaption of the policy could be combined with an initially diverse population to further boost performance. Indeed, we investigate the performance of Poppy with larger time budget in Appendix D and find that Poppy combined with simple sampling procedure and fine-tuning matches, or even surpasses, the state-of-the-art active search approach of Hottung et al. [2022].
Finally, we recall that the motivation behind Poppy was dealing with problems where predicting optimal actions from observations is too difficult to be solved reliably by single agent. We believe that such settings are not strictly limited canonical CO problems, and that population- -hased approaches offer a promising direction for many challenging RI. applications. Specifically, Poppy is amenable in settings where (i) there is distribution of problem instances and (ii) these instances can be attempted multiple times at inference. These features encompass various fields such as code and image generation, theorem proving, and protein design. In this direction, we hope that approaches that alleviate the need for handcrafted behavioral markers whilst still realizing performant diversity akin to Poppy, could broaden the range of applications of nopulation-basee RL.
Acknowledgements
Research supported with Cloud TPUs from Google's ' TPU Research Cloud (TRC).
References
D. Applegate, R. Bixby, V. Chvatal, and W. Cook. Concorde TSP solver, 2006.
Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A method- ological tour d' d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
C. Bonnet, D. Luo, D. Byrne, S. Abramowitz, V. Coyette, P. Duckworth, D. Furelos-BB Baanno, N. Grin- sztajn, T. Kalloniatis, V. Le, O. Mahjoub, L. Midgley, S. Surana, C. Waters, and A. Laterre. Jumanji: a Suite of Diverse and Challenging Reinforcement Learning Environments in JAX, 2023. URL https:/ // /g thib.u...... com/ instadeepaiiin jumanji.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert- Voss. G. Krueger, Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, and C. Hesse. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
X. Chen and Y. Tian. Learning Perform Local Rewriting for Combinatorial Optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
J. Choo, Y.D. Kwon, J. Kim, J. Jae, A. Hottung, K. Tierney, and Y. Gwon. Simulation-guidde beam search for neural combinatorial optimization. In Advances in Neural Informaion Processing Systems (NeurIPS), 2022.
A. Cully and Y. Demiris. Quality and Diversity Optimization: A Unifying Modular Framework. IEEE Transactions on Evolutionary Computation, 22(2):245-259, 2018.
10

---

H. Dai, E. B. Khalil, Y. Zhang. B. Dilkina, and L. Song. Learning Combinatorial Optimization Algorithms over Graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
P. R. de O. da Costa, J. Rhuggenaath, Y. Zhang, and A. Akeay. Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning. In Asian Conference on Machine Learning (ACML), 2020.
M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau. Learning Heuristics for the TSP by Policy Gradient. In International Conference on the Integration of Consstriin Programming, Artificial Intelligence, and Operations Research (CPAIOR), 2018.
T. Doan, B. Mazoure, M. Abdar, A. Durand, Pineau, and R. D. Hjelm. Attraction Repulssion Actor-Critic for Continuous Control Reinforcement Learning, arXiv preprint arXiv:1909007543. 2020.
B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine. Diversity is All You Need: Learning Skills without a Reward Function. In International Conference on Learning Representations (ICLR), 2019.
A. Flajolet, C. B. Monroc, K. Beguir, and T. Pierrot. Fast Population- Based Reinforcement Learning on Single Machine. International Conference on Machine Learning (ICML). 2022.
Z. Fu, K. Qiu, and H. Zha. Generalize Small Pre-trained Model to Arbitrarily Large TSP Instances. In AAAI Conference on Artificial Intelligence (AAAT), 2021.
A. Gupta, R. Mendonca, Y. Liu, P. Abbeel, and S. Levine. Meta- Reiafreinfrrr Learning of Structured Exploration Strategies. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
K. Hartikainen, X. Geng, T. Haarnoja, and Levine. Dynamical Distance Learning for Semi- Supervised and Unsupervised Skill Discovery. In International Conference Learning Represen- tations (ICLR), 2020.
K. Helsgaun. An extension of the hn--kemighan-helsgaant helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Raskilde University, Tech. Rep., 2017.
Z.-W. Hong, T.-Y. Shann, S.-Y. Su, Y.-H. Chang, and C.-Y. Lee. Diversity-Driven Exploration Strategy for Deep Reinforcement Learning. Advances in Neural Information Processing Systems (NeurIPS), 2018.
J. J. Hopfield and W. D. Tank. "Neural" computation of decisions optimization problems. Biological cybernetics, 5213):14 1985.
A. Hottung and K. Tiemny. Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem. In European Conference on Artificial Intelligence (ECAI), 2020.
A. Hottung, B. Bhandari, and K. Tiemney Learning Latent Search Space for Routing Problems using Variational Autoencoders. In International Conference on Learning Representations (ICLR), 2021.
A. Hottung, Y.-D. Kwon, and K. Tierney. Efficient Active Search for Combinatorial Optimization Problems. In International Conference on Learning Representations (ICLR), 2022.
C. K. Joshi, T. Laurent, and Bresson. An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem. arXiv preprint
2019,
W. Jung, G. Park, and Y. Sung. Population-GGuided Parallel Policy Search for Reinforcement Learning. In International Conference on Learning Representations (ICLR), 2020.
S. Khadka and K. Tumer. InolutiinnGuidee Policy Gradient in Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2018
S. Khadka, S. Majumdar, T. Nassar, Z. Dwiel, E. Tumer, S. Miret, Y. Liu, and K. Tumer. Collaborative Evolutionary Reinforcement Learning. In International Conference on Machine Learning (ICMI.), 2019.

---

M. Kim, J. Park, and J. Kim. Learning Collaborative Policies to Solve NP-hard Routing Problems. In Advances in Neural Information Processing Systems (NeurIPS). 2021.
M. Kim, J. Park, and J. Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimiza- tion. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. In International Conference Learning Representations (ICLR), 2015.
W. Kool, H. van Hoof, and M. Welling, Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations (ICLR), 2019.
W. Kool, H. van Hoof, Gromicho, and M. Welling. Deep Policy Dynamic Programming for Vehicle Routing Problems. arXiv preprint arXiv:2102.11755 2021.
Y.-D. Kwon, B. K. Jinho Choo, Y. G. I1joo Yoon, and S. Min. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
H. Lu, X. Zhang, and S. Yang. A Learning-basee based Iterative Method for Solving Vehicle Routing Problems. In International Conference on Learning Representations (ICLR), 2020.
N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers Operations Research, 1 134:105400, 2021.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, Veness, M. G. Bellemare. A. Graves, M. A. Riedmiller, A. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, Wierstra, Legg, and D. Hassabis. Human-level control through deep reinforce- ment learning. Nature, 518:529-5333 2015.
J. Mouret and J. Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv: 1rXiv::504.044 04909, 2015.
M. Nazari, A. Oroojlooy, L. V. Snyder, and M. Takáč. Reinforcement Learning for Solving the Vehicle Routing Problem. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Parker-Holder, A. Pacchiano, K. Choromanski, and Roberts. Effective Diversity in Population Based Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
L. Perron and V. Furnon. OR-Tools, 2019. URL httpss://eeveloperss google..oggooooooooooooo.oo..... com/ optimization/.
T. Pierrot, V. Macé, F. Chalumeau, A. Flajolet, G. Cideron, K. Beguir, A. Cully, O. Sigaud, and N. Perrin-Gillbert. Diversity Policy Gradient for Sample Efficient Quality-Diversity Optimization. In Genetic and Evolutionary Computation Conference (GECCO), 2022.
V. H. Pong, M. Dalal, S. Lin, A. Nair, S. Bahl, and S. Levine. Skew-Fit: State-Covering Self- Supervised Reinforcement Learning. In International Conference on Machine Learning (ICML), 2020.
A. Pourchot and O. Sigaud. CEM-RL: Combining evolutionary and gradient-based methods for policy search. In International Conference on Learning Representations (ICLR), 2019.
J. K. Pugh, L. B. Soros, and K. O. Stanley. Quality Diversity: A New Frontier for Evolutionary Computation. Frontiers Robotics and AI, 3, 2016.
R. Qiu, Z. Sun, and Y. Yang. DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. In Advances in Neural Information Processing Systems (NeuriPS), 2023.
A. Sbihi and R. W. Eglese. Combinatorial optimization and green logistics. 4OR, 5:99-116, 2007.
D. Silver, T. Hubert, Schritwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanetot, L. Sifre, Ku- maran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 140-4449) 2018.
12

---

R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
A. van den Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, Kalchbrenner, A. Senior, and K. Kavukeuoglu. WaveNet: A Generative Model for Raw Audio, arXiv preprint arXiv:1609.03499. 2016.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. Gomez, L. Kaiser, and I. Polosukhin. Attention Is All You Need. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
T. Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap" neighborhood. Computers & Operations Research, 140:105643, 2022.
Vidal, G. Crainic, Gendreau, Lahrichi, and W. Rei. hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):61 1-624, 2012.
O. Vinyals, M. Fortunato, and N. Jaitly. Pointer Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
A. Z. Wagner. Refuting conjectures in extremal combinatorics via linear programming. Journal of Combinatorial Theory, Series A, 169: 169:105-130, 2020.
R. Williams. Simple statistical grolient-foloowing algorithms for connectionist reinforcement learning. Machine Learming, 8:229-256, 1992.
Y. Wu, W. Song, Z. Cao, J. Zhang, and A. Lim. Learning Improvement Heuristics for Solving Routing Problems. IEEE Transactions on Neural Networks and Learning Systems, pages 1-13, 2021.
Xin, W. Song, Z. Cao, and Zhang. Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems. In AAAI Conference Artificial Intelligence (AAAI), 2021.
C. Zhang, W. Song, Z. Cao, J. Zhang, P. S. Tan, and C. Xu. Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
13

---

Appendix
Table of Contents
A Additional Details Poppy
15
A.I
Number of Parameters (TSP)
15
A.2
Training Details
15
B Mathematical Elements
16
B.1 Gradient derivation
16
C Baseline Impact Analysis
17
D
Comparison to Active Search
18
E
Problems
19
E.1
Traveling Salesman Problem (TSP)
19
E.2
Capacitated Vehicle Routing Problem (CVRP)
21
E,3
0-1 Knapsack (KP)
22
E.4
Job-Shop Scheduling Problem (JSSP)
23
F
Time-performance Tradcoff
23
G Larger instances
24
14

---

Algorithm 2 Poppy training with starting points
1: Input: problem distribution D, number of starting points per instance P. number of agents K, batch size B. number of training steps H, a pretrained encoder hy and decoder 2e
2: Φ1, 22...., ØKK t- CLONE(O) [Clone the pre-trained decoder parameters K times.)
3: for step 1 H do
4:
+ Sample(D) Vi I....,
5: Dr.1,...,0..P & SelectStartPoints(p P
6: Tip - Rollout(pi, ai., 90.) vi 1..... B, Vp P. K
7: by P ((T
8: Kt, - arg & SK R(T Vi 1, I...., B, E I.....P |Select the best agent per BB Ei,p /
(instance, starting point).)
bi ki - Vlogoooe (Tip' KiP))
9:
(hbbp 201 902..................... 10x)
[Propa-
gate gradients through these only.}
10: (he, 9o. 90.: g0x t (hy, 9 :0.)...,90.. - (VV, 90. 902........ 90x)
A
Additional Details on Poppy
A.1 Number of Parameters (TSP)
Table 4 shows the total number of parameters of our models as a function of the population size when experimenting on TSP. Since the decoder represents less than 10% of the parameters, scaling the population size can be done efficiently. For instance, a population of 16 agents roughly doubles the model size. This observation transfers to CVRP and KP whose encoder-decoder architectures are similar TSP. The architecture for JSSP slightly different but the observation remains that the decoder represents a smaller part of the model ( 18%) and thus the population can be efficiently scaled.
Table 4: Number of parameters for different population sizes.
Population size
Encoder
Decoder
8
16
32
Parameters Extra parumeters
1,190,016
98,816
1,288,832 0%
832
1,585,280 23%
1, 1,980,544 54%
2.771.072 115%
4,352,128
238%
A.2 Training Details
In Section 3.2 (see "Training Procedure"), we described that Poppy consists of two phases. In nutshell, the first phase consists of training our model in single-agent setting (i.e., an encoder- decoder model with a single decoder head), whereas the second phase consists of keeping the encoder and cloning the previously trained decoder times (where K the number of agents) and specialize them using the population objective. Algorithm 2 shows the low-level implementation details of the training of the population (i.c., Phase 2) for environments where POMO [Kwon et al., 2020] uses several starting points; namely, given K agents and P starting points, P x K trajectories are rolled out for each instance, among which only P are effectively used for training.
Every approach was trained until convergence. Given TSP, CVRP, KP and JSSP, the single-agent baselines were trained for 5 days, days, day, and day respectively, while the largest populations we provide were trained for 4 days, days, 3 days, and 3 days respectively. We emphasize that Poppy already performant with less training budget; indeed, Figure (left) shows that the optimality gap of Poppy decreases very quickly at the beginning, although it takes time to reach convergence. Concretely, only a few hours of training is sufficient for Poppy reach the performance of POMO with 100 samples.
15

---

B Mathematical Elements
B.1 Gradient derivation
We recall that the population objective for K is defined as:
Jpap (f1, (nn))
0n) = EE-DEEn No. T... max [R(TI)...... ((Tr)).,,((())]]
Theorem (Policy gradient for the population objective). The gradient of the population objective is given by:
pp 02.000,...,,. -EpD D.IDDETTTT -.. ... THTOO (R(Te)) - R) (Te-)
where:
(index of the best trajectory) 8 arg second max [R(T)...... R....,,((T))))))))))))))))))(()) R(Tx)], (index of the second best trajectory)
8" = arg max
Proof. We first derive the gradient with respect to 0 for convenience. As all the agents play symmetrical role in the objective, the same procedure can be applied to any index.
Vo, Jpup (01, 02..................... .0.......... 0x0xx) Vo, E B TRINTR
max 1.,1, K}
[R(Ti]]
EpDD BennDEr
max
[((T:)) Va, log p(TTp....,,
(E(1,2.....
= =EpD Er, TK
max (E(1,2....,K)
[R(T:)] Va log( (T)) T0x (Tx))
Epp D
max (E(1,2....KK
[R(T;)] V (log (TI) + ... + log Tex (TK))
EppDEEr Er
max (E.........K)
[((T)) Ve, log ne, (T1),
We also have for any problem instance p and any trajectories .2...., TK:
E B in (2....,,KK
max [[(T))] Vo, log To, (m)
max
[((::) E m Vo, log To, (T))
iE(2....,
Vo, Ta, (Ti
[R(Ti)] E B
(2......K)
max
To (T1)
[R(Ti)] Σ Ve, Te, (T1)
max sE(
max iE(2....K)
[R(Ti)] V Σ
गe (TI)
"1
max
Vo,1 0
iE(2...,KK
Intuitively, maxie(2..... [T(]] does not depend on the first agent, so this derivation simply shows that max:: [((T))] can be used as a baseline for training 0,-
Subtracting this to the quantity obtained in Equation B.I, we have:
16

---

Vol popp(p00 00.. EpDD Ey
max
[ Vor log Te, (T1),
(E(1,2.....)
E B B By
max kE(1,2...,K)
[R(T:)] Vo, log To, (TI),
[M(TT))) Va, log ne, (TI),
EpDD Draa Era En
[[(T:)]]
max
max
(E(1.2....))
ie(2....K)
=EpD BanDDEEaaaao Bra En (+=1(((m)) - R( Vo. To (Ti),
= E - (R(T:)) - R((T.))) Vo, log na, (TI).
Equation (B.1) comes from the fact that ( [[(T.)] - max, (2.....k) [R(T:))) is of the best trajectory is not Tı, and R(m)) max.. [[(T=)] R(n) - R((T...) otherwise.
Finally, for any j E (1,..., K), the same derivation gives:
Vo, ppp 1, .2.....,Aa 0k) = Ep (r=)(((Ts)) - R(TT..))VV log Te, (Tz).
Therefore, we have:
V 8
E B 1== (R(Te-) RR(T+-)) log To, (T)),
V = EpwD E. m. (R(T:-) - R(T )) Vo,- log n0,- (Tr))
which concludes the proof.
C Baseline Impact Analysis
The results presented in the paper the same reinforcement learning baseline POMO [Kwon et al., 2020], the average reward over starting points, as presented Alg. 2. However, Theorem directly provides alternative baseline: the reward of the second-best agent. Figures 5-7 compare the performance of Poppy using the baseline from POMO against Poppy using the baseline analytically computed in Theorem 1.
In almost cases, we observe that the analytical baseline provides better or equal performance than the POMO baseline. We believe that this highlights both that intuitive "winner takes it all" approach works well even with slightly different choices of baseline, and that indeed our theoretical analysis correctly predicts modified baseline that can be used in practice with strong performance.
Table 5: TSP results.
Inference (10k instances)
0-shot (Ik instances)
n
150
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Concorde
7.765
0.000%
82M
8.583
0.000%
12M
9.346
0.000%
17M
LKH3
7.765
0.000%
8H
8,583
0.000%
73M
9.346
0.000%
99M
POMO 16 (ensemble)
7.790
0.33%
IM
8.629
0.53%
10S
9.435
0.95%
20S
Poppy 16 (POMO baseline)
7.770
0.07%
IM
8.594
0.14%
10S
9,372
0.27 %
20S
Poppy 16 (analytical baseline)
7.769
0.05%
IM
8,594
0.13%
10S
9.372
0.28%
20S
17

---

Table 6: CVRP results.
Inference (10k instances)
O-shot (1k instances)
O-shot (Ik instances)
n1
125
T
150
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
LKH3
15.65
0.000%
6D
17.50
0.000%
19H
19.22
0.000%
20H
POMO 32 (ensemble)
15.78
0.83%
5M
17.70
1.11%
IM
19.57
1883%
IM
Poppy 32 (POMO baseline)
15.73
0,52%
5M
17.63
0.71%
IM
19.50
1.43%
1M
Poppy 32 (analytical baseline)
15.72
0.48%
5M
17.63
0.71 %
IM
19.50
1.43%
IM
Table 7: Packing problems results.
(a) KP
(b) JSSP
Testing (10k instances)
Testing (100 instances)
v 100
10 x 10
Method
Obj.
Gap
Time
Method
Obj-
Gap
Optimul
40.437
Tools (optimal)
807.6
0.0%
37S
Greedy
40.387
0.1250%
Single (16 samples)
866.0
7.2%
30M
POMO (ensemble)
40.429
0.021%
2M
Poppy 16 (POMO baseline)
857.7
6.2%
30M
Poppy (POMO haseline)
40,437
0.0005%
2M
Poppy 16 (analytical baseline)
40.437
0.0001 %
2M
Poppy 16 (analytical baseline)
852.2
5.5%
30M
D Comparison to Active Search
We implement a simple sampling strategy to give a sense of the performance of Poppy with larger time budget. Given population of K agents, we first greedily rollout each of them on every starting point, and evenly distribute any remaining sampling budget across the most promising K (agent, starting point) pairs for each instance with stochastic rollouts. This two-step process is motivated by the idea that is not useful to sample several times an agent on an instance where it is outperformed by another one. For environments without starting points like JSSP, we stick the simplest approach of evenly distributing the rollouts across the population, although better performance could likely be obtained by selectively assigning more budget to the best agents.
Setup For TSP, CVRP and JSSP, we use the same test instances as in Tables 1, 2 and 3b. For TSP and CVRP, we generate a total of 200 8 N candidate solutions per instance (where corresponds to the augmentation strategy by Kwon et al. [2020] and N is the number of starting points), accounting for both the first and second phases. We evaluate our approach against POMO [Kwon et al., 2020], EAS [Hottung et al., 2022] with the same budget, and SGBS [Choo et al., 2022], as well as against the supervised methods GCN-BS [Joshi et al., 2019], CVAE-Opt [Hottung et al., 2021], and DPDP [Kool et al., 2021]. As EASand SGBS have different variants, we compare against those that do not require backpropagating gradients through the network, similarly to our approach; thus, it should match Poppy's 's compute time on the same hardware. We additionally compare against the evolutionary approach HGS [Vidal et al., 2012, Vidal, 2022]. For JSSP, we use the same setting as EAS [Hottung et al., 2022], and sample a total of 8,000 solutions per problem instance for each approach. For proper comparison, we reimplemented EAS with the same model architecture as Poppy.
Results Tables and 10 show the results for TSP, CVRP and JSSP respectively. With extra sampling, Poppy reaches performance gap of 0.002% on TSP100, and establishes a state-of-the-a for general ML-based approaches, even when compared to supervised methods. For CVRP, adding sampling to Poppy makes it on par with DPDP and EAS, depending on the problem size, and it is only outperformed by the active search approach EAS, which gives large improvements on CVRP. As the two-step sampling process used for Poppy is very rudimentary compared to the active search method described in Hottung et al. [2022], is likely that combining the two approaches could further boost performance, which we leave for future work.
18

---

Table 8: TSP results (active search)
Inference (10k instances)
O-shot (Ik instances)
100
125
1:
150
Method
Obj.
Gap
Time
Obj-
Gap
Time
Obj.
Gap
Time
Concorde
7.765
0.000%
82M
8.583
0.000%E
12M
9.346
0.000%
17M
LKH3
7.765
0.000%
8H
8,583
0.000%
73M
9.346
0.000%
99M
GCN-BS
7.87
1.39%
40M
CVAE-Opt
0.3-13%
8.646
0.736%
21H
9,482
1.45%
30H
DPDP
7.765
0.004%
2H
8.589
0.070%
31M
9.434
0.94%
44M"
POMO (200 samples)
7.769
0.056%
2H
8,594
0.13%
20M
9.376
0.31%
32M
SGBS
7.769
0.058%
9M"
9.367
0.22%
8M
EAS
7.768
0.048%
5H"
8.591
0.091%
49M
9.365
0.20%
Poppy 16 (200 samples)
7.765
0.002%
2H
8,584
0.009
20M
9.351
0.05 %
32M
Table 9: CVRP results (active search)
Inference (1Ok instances)
0-shot (Ik instances)
0-shot (Ik instances)
100
125
150
Method
Obj.
Gup
Time
Obj.
Gup
Time
Obj.
Gup
Time
HGS
15.56
0.00%
313
17.37
0.00%
12H
19.05
0.00%
16H
LKH3
15.65
0.53%
17.50
0.75%
19H
19.22
0.89%
20H
CVAE-OPt
1.90%
17.87
2.85%
36H
4.16%
46H
DPDP
15.63
0.40%
23H'
17.51
0.82%
3H"
19.31
1.38%
5H'
POMO (200 samples)
15.67
0.71%
4H
17,56
1.08%
43M
19.43
1.98%
1H
SGBS
15.66
0.61%
10M
19.43
1.96%
4M"
22
EAS
15.62
0,39%
17.49
0.75%
80M'
19.36
1.62%
2H'
Poppy 32 (200 samples)
15.62
0.39%
4H
17.49
0.65 %
42M
19.32
1.40%
IH
E
Problems
We here describe the details of the four CO problems we have used to evaluate Poppy, namely TSP. CVRP, KP and JSSP. We use the corresponding implementations from Jumanji [Bonnet et al., 2023]: TSP, CVRP, Knapsack and JobShop. For each problem, we describe below the training (e.g. architecture, hyperparameters) and the process of instance generation. In addition, we show some example solutions obtained by population agents on TSP and CVRP, Finally, we thoroughly analyze the performance of the populations in TSP.
E.1 Traveling Salesman Problem (TSP)
Instance Generation The cities that constitute each problem instance have their coordinates uniformly sampled from [0. 1)2.
Architecture We use the same model Kool et al. [2019] and Kwon et al. [2020] except for the noccaloommaiintionn layers, which are replaced by layer-normalization to ease parallel batch processing. We invert the mask used in the decoder computations (i.e., masking the available cities instead of the unavailable ones) after experimentally observing faster convergence rates. The results
Table 10: JSSP
Inference (100 instances)
10 x 10
Method
Obj.
Gap
Time
OR- TRR-ools (optimal)
807.6
0.0%
37S
L2D (Greedy)
988.6
22.3%
20S
L2D (Sampling)
871.7
8.0%
8H'
EAS-L2D
860.2
6.5%
8H'
Sampling
862.1
6.7%
3H
EAS
858.4
6.3%
3H
Poppy 16
849.77
5.2%
3H
19

---

reported for POMO were obtained with the same implementation changes to keep the comparison fair. These results are on par with those reported in POMO [Kwon et al., 2020].
Hyperparameters To match the setting used by Kwon et al. [2020], we use the Adam optimizer [Kingma and Ba, 2015] with learning rate 1l 10-4 and an L2 penalization coefficient of 10- The encoder is composed of 6 multi-head self-attention layers with 8 heads each. The dimension of the keys, queries and values is 16. Each attention layer is composed of feed-forward layer of size 512, and the final node embeddings have dimension of 128. The decoders are composed of 1 multi-head attention layer with heads and 16-dimensional key, query and value.
The number of starting points P is 50 for each instance. We determined this value after performing a grid-search based the first training steps with {20, 50, 100).
Example Solutions Figure shows some trajectories obtained from 16-agent population on TSPI00. Even though they look similar, small decisions differ between agents, thus frequently leading to different solutions. Interestingly, some agents (especially 6 and 11) give very poor trajectories. We hypothesize that is a consequence of specializing since agents have no incentive to provide good solution if another agent is already better on this instance.
Best solved by aggett
1.2
Population nisc
Number of iret anices (%)
20
16
Oplimality gap (36)
aoeats
1.0
15
0.8
0.6
0.4
10
15
16
2
12
14.
Agrnts
Sabpopalation size
Number of Instatus (86)
40
Optinality gop (9G)
0.0015
20
0.0005
10
8
9
10
11
13
11
15
16
8
10
15
16
Number agentt
Agentts
Figure 4: Upper left: Proportion of instances that each agent solves best among the population for Poppy 16 on TSPI00. Colors indicate the number of agents in the population giving the same solution for these sets of instances. Upper right: The mean performance of 1,000 randomly drawn sub-populations for Poppy I, 4, and 16. Bottom left: Proportion of test instances where any number of Poppy 16 agents reaches the exact same best solution. The best performance is reached by only a single agent in 47% the cases. Bottom Right: Optimality gap loss suffered when removing any agent from the population using Poppy 16. Although some agents contribute more (e.g. 7, 8) and some less (e.g. 15, 16), the distribution is relatively even, even though no explicit mechanism enforces this behavior
Population Analysis Figure 4 shows some additional information about individual agent perfor- mances. In the left figure, we observe that each agent gives on average the best solution for 20% of the instances, and that for around 4% it gives the unique best solution across the population. These numbers are generally evenly distributed, which shows that every agent contributes to the whole population performance. Furthermore, observe the performance is quite evenly distributed
20

---

across the population of Poppy 16; hence, showing that the population has not collapsed to a few hirh-performing agents, and that Poppy benefits from the population size, shown in the bottom figure. On the right is displayed the performance of several sub-populations of agents for Poppy 4, 8 and 16. Unsurprisingly, fixed size sub-popun sub-populatiins are generally better when sampled from smaller populations: one or two agents randomly sampled from Poppy perform better than when sampled from Poppy 8 or Poppy 16. This highlights the fact that agents have learned complementary behaviors which might be sub-optimal if part of the total population is missing, and this effect is stronger for large populations.
total length 2.578
tobal wwtggh 7.701
bobn lnngth 7:581
Total lmngth 7,587
total kingth 7.593
TdEal Heriirrggt 7.527
toto lungth 7.757
longth 2.025
10DO longth
Figure 5: Example TSP trajectories given by Poppy for 16-agent population from one starting point (red).
E.2 Capacitated Vehicle Routing Problem (CVRP)
Instance Generation The coordinates of the customer nodes and the depot are uniformly sampled in [0, 1]2 The demands are uniformly sampled from the discrete set { [ ...... 31 where = 50 for CVRP100, D 55 for CVRP125, and D 60 for CVRP150. The maximum vehicle capacity is The deliveries cannot split: each customer node visited once, and its whole demand taken off the vehicle's remaining capacity.
Architecture We use the same model in TSP. However, unlike TSP, the mask is not inverted: besides, it does not only prevent the agent from revisiting previous customer nodes, but also from
21

---

visiting the depot if it is the current location, and any customer node whose demand is higher than the current capacity.
We use the same hyperparameters as TSP except for the number of starting points P per instance used during training, which we 100 after performing grid-search with PE (20, 50, 100).
Hyperparameters
Example Solutions Figure 6 shows some trajectories obtained by 16 agents from a 32-agent population on CVRP100. Unlike TSP, the agent/vehicle performs several tours starting and finishing in the depot.
12 routes, distance 16.04
12 rontes, distanon 16. 1616
13 rontes, distannee 16.23
12 roates, distaner 16.20
12 rontes, distance 16.05
12 poutes, distance 15.63
12 rottes, distance 15.86
12 rostes, distance 16.18
12 rontes, distance 16.21
12 poutess distance 16.56
13 rontes, distance 16.17
12 roates, distance 16.24
12 routes, distance 1600
13 mitts, distance 16.16
12 rontos, distance 15.93
routes, distance 16.08
Figure 6: Example CVRP trajectories given by Poppy for 16 agents from a 32-agent population. The depot displayed black square. The edges from/to the depot omitted for clarity.
E.3 0-1 Knapsack (KP)
Problem Description Given set of items, each with weight and value, the goal is to determine which items to include in a collection so that the total weight is less than or equal to a given limit and the total value large possible.
Instance Generation Item values and weights are both uniformly sampled in [0, 1]. The bag capacity is fixed at 25.
22

---

Training For KP, and contrary to the other three environments, training an agent is lightning- fast as it only takes a few minutes. In this specific case, we noticed was not necessary to train a single decoder first. Instead, (i) we directly train population in parallel from scratch, and (ii) specialize the population exactly as done in the other environments.
Architecture We use the same model as in TSP. However, the mask used when decoding is not inverted, and the items that do not fit in the bag are masked together with the items taken so far.
Hyperparameters We use the same hyperparameters as in TSP except for the number of start- ing points P used during training, which we set 100 after performing a grid-search with P E {20, 50, 1003.
E.4 Job-Shop Scheduling Problem (JSSP)
Problem Description We consider the problem formulation described by Zhang et al. [2020] and also used in Bonnet al. [2023], in the setting of an equal number of machines, jobs and operations per job, A job-shop scheduling problem consists in N jobs that all have N operations that have to be scheduled on N machines. Each operation has to run on a specific machine for a given time. The solution to problem is schedule that respects few constraints:
for each job, its operations have to be processeddsccheduee in order and without overlap between two operations of the same job,
a machine can only work on one operation at time,
once started, an operation must run until completion.
The goal of the problem is to determine schedule that minimizes the time needed to process all the jobs. The length of the schedule is also known as its makespan.
Instance Generation We use the same generation process Zhang et al. [2020]. For each of the N jobs, we sample operation durations uniformly in [1, 99) Each operation is given a random machine to run on by sampling a random permutation of the machine IDs.
Transition Function To leverage JAX, we use the environment dynamics implemented in Ju- manji [Bonnet et al., 2023] which differs from framing proposed by L2D [Zhang et al., 2020]. However, the two formulations are equivalent, therefore our results the former would transfer to the latter. Our implementation choice was purely motivated by environment speed.
Architecture We use the actor-critic transformer architecture implemented in Jumanji which is composed of an attention layer on the machines' status, attention layer the operation durations (with positional encoding) and then two attention layers on the joint sequence of jobs and machines. The network outputs N marginal categorical distributions for all machines, as well as value for the critic. The actor and critic networks do not share any weights.
Hyperparameters Like in Zhang et al. [2020], we evaluate our algorithm with 10 jobs, operations and machines, i.e. 10 x 10 instances. We use REINFORCE with the critic as baseline (state-value function). Since episodes may take long time (for an arbitrary policy, the lowest upper episode horizon of 1250 and give reward penalty of
bound on the horizon is 98 x 3 we two times the episode horizon when producing a makespan of more than this limit.
F Time--performance Tradeoff
We present in figure 7 comparison of the time Lime-performance Pareto front between Poppy and POMO as we vary respectively the population size and the amount of stochastic sampling. Poppy consistently provides better performance for fixed number of trajectories. Strikingly, in almost every setting, matching Poppy's performance by increasing the number stochastic samples does not appear tractable.
23

---

0.35
Pope
Pupey POMO
Oplinally say (%)
0.300
POMO
Optimellty suu (30
0.5
0:35
0.20
0.3
0.15
Popper
Prper
0.10
Papgss
Papes
Figgy
Poppy 16
50
100
100
200
50
100
150
200
200
Number of sampled trajemmrtte (ler))
Number of sumpled tnjeetoorie (let)
(a) TSP100
(b) TSP125
1.4
1.41
Popper
POMO
Ponay
Optnnelly 19e (55)
Optinallty sap (50
00.8
1.0
Poppy
Lapoy S
Papuy
0.4
Prppy
0.6
Poppe 32
50
100
Namther sempled tragentomes (lez)
Number sampled trajectortes (let)
(c) TSP150
(d) CVRP100
5.00
Popper
Pappy POMO
1.0
POMO
2.75
Optinally pap (50
Opcicaltty sap (6)
2.00
Pappy
2.95
2.00
Poppe Poppe
1.0
Puppe
1.75
Roopy 32
2 Popoyy d2
100
150
500
250
50
100)
150
200
250
900
Numther of sempled trajecturies (162)
Number of campled trajectocies (2<2)
CVRP125
(f) CVRP150
0.011
POM0
0.012
Puger POMO
Optimales 6at 182
0.000
Optimakit gip (16)
0.008
00005
8
0001
Dipppy
00002
Popey
Phopy 16
0.000
10
15
20
20
80
Namber of amplla trajectucion (1i5)
Nambur of d'aoplee injustioiin (1x2)
(g) KP100
(h) JSSP100
Figure 7: Comparison of the pime-performance Pareto front of Poppy and POMO, for each problem used in the paper. The x-axis is the number of trajectories sampled per test instance, while the y-axis is the gap with the optimal solution for TSP, KP and ISSP, and the gap with LKH3 for CVRP.
G Larger instances
We display in Table I1 results for POMO and Poppy on much larger TSP instances with 1000 cities. Baselines are taken from Qiu et al. [2023].
24

---

Table 11: TSP results (TSP 1000)
Method
Type
Obj.
Gap
Time
Concorde
OR OR
23.12
0.000%
6.65H
LKH3
23.12
0.000%
2.57H
EAS (Tab)
RL w/ search
49.56
63H
Dimes
RL w/ search
23.69
2.16%
5H
POMO samples)
RL w/o search
50.80
120%
39M
Poppy 16
RL w/o seurch
39.70
71.7%
39M
25


Reviews:
[{"review_id": "OdKEfdY0Vu", "reviewer": "Reviewer_Ym2T", "summary": "The paper proposes that populations of agents can produce better results than using single agents. This leads to a new \"Poppy\" algorithm which performs policy gradient updates only on the agent which produced the highest reward. This is then applied to combinatorial optimization problems using attention-based architectures to demonstrate fast and competitive results.", "questions": "* Could the proposed Poppy RL algorithm be more generally applicable to any MDP? If so, which problems (outside of combinatorial optimization) do you think can be most benefited? \n* Following up on my weakness section - In which types of MDPs/cases could \"diversity\" behavior not appear from Poppy training, since diversity is not an explicitly optimized objective?", "limitations": "Limitations section appears comprehensive. No issues.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The proposed \"Poppy\" algorithm appears to be a novel policy gradient variant. I do wonder however, if such an algorithm can be extended to general RL settings, rather than only combinatorial optimization.\n* Overall the paper is a clean read and presentation is strong. I did not have any issues with understanding.\n* Experimental results are reasonable. The method demonstrates good performance and low inference costs.\n", "weaknesses": "The core issue of the proposed method, is that there is no explicit \"diversity\" objective being optimized, which makes this a theoretical weakness. However, the paper does defend against this through multiple explanations (e.g. agents will tend to specialize) and empirical evidence (e.g. best agent improves which population worsens).\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and appreciating the presentation and clarity of the work. We hope our answers address all concerns and are sufficient to reconsider the assessment.\n\n> Could the proposed Poppy RL algorithm be more generally applicable to any MDP? If so, which problems (outside of combinatorial optimization) do you think can be most benefited?\n\nThe Poppy framework (cloning a single agent, then applying the Poppy objective) is applicable to any model architecture. However, Poppy only makes sense in settings where (i) there is a distribution of problem instances and (ii) these instances can be attempted multiple times at inference (e.g., self-driving cars would not fit into this category). A lot of environments have these two features, including combinatorial problems, text/code generation problems or even theorem proving. Moreover, environments which are based on a simulator that we can repeatedly use satisfy (ii), as several attempts can be performed virtually before acting.\n\nWe make a brief reference to this question in lines 324-326, however, we agree that this is a natural question and will extend this to include the above discussion in the final version of the manuscript.\n\n> In which types of MDPs/cases could \"diversity\" behavior not appear from Poppy training, since diversity is not an explicitly optimized objective?\n\nWe note that diversity is not the aim of Poppy; rather we aim to maximize performance - therefore we expect diversity to emerge if, and only if, it increases the population-level performance (i.e. taking the best result from any agent in the population on each sampled problem instance). Correspondingly, if only a single policy can achieve the highest practical returns across all problem instances we would expect the population to collapse to have only one agent providing all of the performance (as the other agents are never the best on a sampled problem and thus never get trained). Trivial examples would be when the training distribution consists of only a single problem instance, or when a single simple strategy (that can be exactly learned by an agent) can reach optimal performance on all problem instances (e.g. if we train on only TSP problem instances where the shortest tour is obtained by always moving to the nearest unvisited city). \n\n> The core issue of the proposed method, is that there is no explicit \"diversity\" objective being optimized\n\nWe firmly believe that this is, in fact, a key strength of our approach, for the following reasons:\n* Population diversity is only a proxy for population performance. Poppy directly optimizes the target metrics and attains diversity as a by-product, which is more aligned with our objective of solving CO problems.\n* Diversity is tricky to measure and thus to optimize. The KL divergence has been used in CO (MDAM [6]), but it is challenging to scale as the complexity grows as the size of the population squared, and was only applied to the very first action, which limits the performance (as we argue on L85-L92). Another approach in the line of quality-diversity methods would be to encode explicit behavioral markers. However, this can be difficult to implement in the case of CO problems where there are no canonical behavioral markers, and so these would have to be handcrafted for each specific problem.\n* Even if we were to suppose that we have a way to measure and optimize diversity, it is not clear how to balance the RL and diversity objective. Indeed, different problems may necessitate various degrees of diversity and too much diversity can hurt final performance: this implies tuning the hyperparameter used in the loss trade-off, as done in [6].\n* We demonstrate empirically that optimizing our objective produces a set of diverse agents (e.g., see Figures 4-6 in the Appendix) across several domains *without* handcrafting any problem-specific notions of diversity. \n"}, {"review_id": "3gOUlyl2KO", "reviewer": "Reviewer_wqBo", "summary": "The paper proposes a new training procedure that allows to train a diverse set of policies for solving combinatorial optimization problems. Most existing approaches for these problems train a single policy/agent and aim to construct a solution in a single shot (or by sampling multiple solutions). In contrast, the authors propose to use a population of agents that is trained such that a diverse set of solutions can be obtained by solving a problem instance by each population member. To this end, the paper proposes a new training objective that aims to increase the maximum reward over all K population members. This is implemented by backpropagating only through the best performing agent for each instance during the training phase. Experimentally, the authors show that this approach is indeed able to learn a set/population of complementary policies. Furthermore, the results demonstrate that the performance of a population trained via the proposed approach is clearly superior to a population in which all agents are trained independently in standard-fashion.", "questions": " ", "limitations": "- The paper does not discuss limitations of the proposed method.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- While other papers have proposed to train a population of agents, the proposed training procedure (that always only trains the best agent of the population per instance) is novel.\n- The proposed methods show a significant performance improvement on the considered problems. For example, on the traveling salesperson problem the method finds solutions with a gap to optimality of 0.07% (in comparison to a gap of 0.27% of the state-of-the-art POMO method). To the best of my knowledge, the proposed method is currently the best neural combinatorial optimization method for quick solution generation (i.e., without a search component).\n- The method succeeds in training a population of complementary agents. The authors show experimentally that the average solution quality decreases during the training while the best performance over all agents increases. This means that the agents successfully specialize on specific strategies. \n- The authors evaluate their method on 4 different combinatorial optimization problems which demonstrates the wide applicability of the technique. On all problems, the method significantly improves the performance.\n- The considered problem of learning heuristics for combinatorial optimization problems has gotten a lot of attention in the literature and is a very promising research area.\n- The proposed method is simple and can be easily applied to other neural construction methods. Thus, it is likely that other researchers will use the proposed technique in their work.\n- Overall, the paper is well written and clearly organized.\n", "weaknesses": "- Overall, the additional training of a population with the proposed method is quite resource intensive because only one of the K rollouts is used for backpropagation. In some settings, the additional resources needed for the population training phase might not be worth the obtained performance improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and outlining the strengths of our work (novelty, performance, applicability, clarity). While there are no questions, we are happy to provide some feedback on a comment made in the review.\n\n> Overall, the additional training of a population with the proposed method is quite resource intensive because only one of the K rollouts is used for backpropagation. In some settings, the additional resources needed for the population training phase might not be worth the obtained performance improvements.\n\nWe agree with the reviewer that the training process can be intensive. However, we still would like to emphasize that the practical cost of training the population is still in the order of training a single agent (for example, Poppy 16 costs 80% of the training of the initial single agent, as we briefly mention on lines 214-215). Crucially, the cost of training the population is substantially reduced by cloning the final few layers of a pre-trained single agent to initialize the population and then fine-tuning each agent. Future works could consider strategies that enable the early detection of the poor performing agents and hence avoid full rollouts for them.\n"}, {"review_id": "8RYYZRtlYT", "reviewer": "Reviewer_51fw", "summary": "This paper proposes a construction method that learns a population of agents to improve the exploration of the solution space of combinatorial optimization problems. Experiments demonstrates that the proposed method improves the solving efficiency of four popular NP-hard problems.", "questions": "Please refer to Weaknesses for my questions.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow. \n2. Experiments demonstrate that the proposed method achieves state-of-the-art RL results on four popular combinatorial optimization problems.", "weaknesses": "1. The motivation is unconvincing. The authors provide a motivating example of a naïve decision-making environment in Figure 1. However, it would be more convincing if the authors could provide an example of combinatorial optimization problems, as this paper aims to develop effective methods to solve combinatorial optimization problems.\n2. The idea of learning a population of agents with diverse policies is incremental, as [1] has proposed a similar method.  \n3. The authors claim that their proposed method can produce a set of complementary policies. However, there is no proof for this claim. Thus, it would be more convincing if the authors could provide theoretical and/or empirical proof for this claim. \n4. The experiments are insufficient. \n(1) It would be more convincing if the authors could evaluate the proposed method on combinatorial optimization problems with larger sizes, such as TSP with 1000 cities.\n(2) Some important baselines are missing. First, the authors may want to compare their method with MDAM [1] on the packing problems. Second, the idea of learning a population of agents is similar to learning an ensemble of agents. Thus, the authors may want to compare their method with baselines with the ensemble learning trick.\n(3) It would be better if the authors could provide a time analysis of training cost, as training a population of agents may take much longer time than that of baselines.\n\n[1] Xin, Liang, et al. \"Multi-decoder attention model with embedding glimpse for solving vehicle routing problems.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 13. 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We believe our answers address the concerns raised and hope these enable the Reviewer to reconsider their assessment.\n\n> W1. [The motivation] would be more convincing if the authors could provide an example of combinatorial optimization problems [in Fig. 1].\n\nThe motivating example in Figure 1 was chosen because it illustrates the limitations of learning an optimal policy using a single agent: it cannot learn an optimal policy, whereas a population of two agents can. We agree that it is important to relate this to CO problems as these are the focus of our work. However, as we state on lines 154-158, this problem setting can in fact be seen as a toy model for the challenge of solving an NP-hard CO problem in a sequential decision-making setting. Concretely, we posit that the maze prevents the agent from being able to reason over the outcome of its actions, and thus it must learn heuristics over the expected (but uncertain) returns. If we instead consider the first action of a problem such as TSP, the number of possible unique tours that could follow from each action is exponentially large and, for any reasonably finite agent capacity, essentially provides the same obfuscation over the final returns.\n\nWe accept that we should have made this link more clear in our manuscript and are happy to extend the discussion of Figure 1 to include a summarized justification.\n\n> W2. The idea of learning a population of agents with diverse policies is incremental, as [1] has proposed a similar method [MDAM].\n\nWhilst MDAM and Poppy both share the intuition of training a population of agents for CO problems, there are substantial differences in both methodology and performance. We provide a comparison in the Related Works (lines 84-92) but to summarize:\n* MDAM trades off performance with diversity by jointly optimizing policies and their KL divergence. Poppy drives diversity by maximizing population-level performance *without* using any explicit diversity metric (which, as we argue in lines 173-175 and 326-328, is a major benefit of our approach).\n* MDAM only drives diversity at the first step of a trajectory since computing the KL divergence for the whole trajectory is intractable. Poppy, by contrast, can generate diverse policies over the entire trajectory.\n* Poppy scales better with population size than MDAM (which requires computing the KL divergence for each pair of agents and thus is only scaled to 5 agents in [1]).\n* Poppy significantly outperforms MDAM in TSP and CVRP (Tables 1 and 2).\n\nIn summary, we do not believe that MDAM can be used to detract from Poppy which makes significant contributions both algorithmically (a novel framework for population-based CO) and practically (with significant performance benefits).\n\n> W3. The authors claim that their proposed method can produce a set of complementary policies. However, there is no proof for this claim.\n\nWe do provide empirical evidence to support the claim that Poppy can produce a set of complementary policies and will ensure that this is highlighted in revised versions. Specifically:\n* In Fig 3 (right), it can be seen that the *average* agent performance in Poppy 8 has an optimality gap of 1.1%, far from the 0.4% of POMO. However, the performance of the population is 0.09%, outperforming even “POMO (100 samples)” despite using less than 12 times fewer rollouts. This can be interpreted as complementarity: alone, each agent performs worse than POMO, but together they perform far better.\n* Poppy outperforms ensemble methods (Table 1 and 2), showing that it is not reduced to a population of diverse agents.\n* In App. D.1, Fig. 4 (lines 546-557), we show that every agent contributes to the whole population performance.\n\n> W4.1. It would be more convincing if the authors could evaluate the proposed method on CO problems with larger sizes. \n\nEven though this work does not specifically focus on scalability, our method can easily be applied to larger instances since our method is agnostic to the network architecture. Concretely, the Poppy framework can be applied to architectures designed specifically for scalability, e.g. DIMES [1]. However, we use the POMO [2] architecture as it is widely established as the default option in our setting [4, 5, 6] and allows for direct comparison to the SOTA baseline methods. In this context, we scale to the same instance sizes as previous works [2-6].\n\n> W4.2.1.The authors may want to compare their method with MDAM on the packing problems. \n\nThe authors of MDAM did not report the performance of their method in KP and JSSP. We also note that on TSP and CVRP, where MDAM reports results, MDAM is not the strongest RL baseline to which we compare: POMO (ensemble) outperforms MDAM in all settings, and is in turn always outperformed by Poppy. Therefore, we believe that it is appropriate to focus on the strongest published baselines for later experiments; and hence use POMO (single and ensemble) for KP and the JSSP-specific RL SOTA method, L2D [3].\n\n> W4.2.2. The authors may want to compare their method with baselines with the ensemble learning trick.\n\nWe have indeed performed these experiments, which are denoted by POMO X (ensemble), where X is a number of agents. The results stated in Tables 1, 2, and 3a for TSP, CVRP, and KP, respectively, demonstrate that Poppy outperforms ensembles.\n\n> W4.3. It would be better if the authors could provide a time analysis of training cost.\n\nSingle-agent baselines were trained for 5D, 7D, 1D, and 1D for respectively TSP, CVRP, KP and JSSP, while the largest populations we provide were trained until convergence for 4D, 5D, 3D and 3D, which we will add to the paper. Additionally, we want to emphasize that Poppy is already performant with less training budget: Figure 3 (left) outlines the performance of Poppy after just a few hours of training, which is already sufficient for Poppy 4 to reach the performance of POMO (100 samples).\n"}, {"review_id": "RQG7nYrD9z", "reviewer": "Reviewer_ybFK", "summary": "This paper presents a multi-decoder (population) neural network structure and training method to solve the combinatorial optimization problem. In particular, the paper presents a model update method in which multiple decoders can specialize in different types of problem instances. The method proposed in this paper shows promising results in TSP, CVRP, KP, and JSSP experiments.", "questions": "**Q1.** In Algorithm 1, reward of the result of the second best agent $R(\\tau_i^{**})$ was used as the baseline(169\\~171), but Algorithm 2 seems to have used the POMO shared-baseline of the result of the best agent as the baseline(Algorithm 2, 7\\~9). In other words, parameter update by applying the POMO training algorithm only for the best agent for each instance. Is it correct? Please provide a more detailed explanation of the parameter update in Algorithm 2.\n\n**Q2.** How to determine the appropriate number of populations? Are there criteria, considerations, etc. for the decision?\n\n**Q3.** Can you show the change in accuracy, training time, inference time, etc. according to the change in the number of population?\n\n**Q4.** Algorithm 1 Input - Missing 'H' in 'number of training steps H'.\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**S1.** The idea of agent population and the training method used for building it are novel.\n\n**S2.** While the idea is simple and clear, the accuracy improvement by the proposed method is remarkable. When performing inference in a fast and simple form(i.e. without iterative searching for inference), Puppy showed superior results compared to POMO 16 samples or POMO 16 ensemble.\n\n**S3.** The method proposed in the paper is applicable to various types of CO problems.\n\n**S4.** The idea of applying the multi-agent method of this paper to the existing POMO training method is excellent.", "weaknesses": "There seems to be no major flaw in the methods presented in the paper. However, there are two opinions related to the TSP/CVRP experiment results.  \n\n\n**W1.** Recent studies that have shown good results in TSP and CVRP experiments are omitted as baselines in Tables 1 and 2, for example [1, 2, 3]. Especially in the case of CVRP experiments, EAS[1], DPDP[2] and SGBS[3] have outperformed LKH3.\n\n**W2.** HGS [4,5] shows better performance than LKH3 as a meta-heuristic algorithm. I recommend that paper authors consider adding HGS as a meta-heuristic baseline in Table 2.\n\n\n**References**\n\n[1] Andre Hottung, et al. Efficient active search for combinatorial optimization problems. International Conference on Learning Representations, 2022.  \n[2] Kool, Wouter, et al. Deep policy dynamic programming for vehicle routing problems. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2022.  \n[3] Jinho Choo, et al. Simulation-guided Beam Search for Neural Combinatorial Optimization. Advances in Neural Information Processing Systems 35, 2022.  \n[4] Thibaut Vidal, et al. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 2012.  \n[5] Thibaut Vidal. Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and appreciating the novelty, simplicity and applicability of our method. We hope our answers address the reviewer’s remaining concerns.\n\n> Q1. In Algorithm 1, reward of the result of the second best agent $R(\\tau_{i^{\\ast\\ast}})$ was used as the baseline(169-171), but Algorithm 2 seems to have used the POMO shared-baseline of the result of the best agent as the baseline(Algorithm 2, 7-9). Please provide a more detailed explanation.\n\nWe are grateful to the reviewer for raising this point; indeed we discuss two possible choices of baseline for our training algorithm. In both cases, we rollout our entire population on the problem and train only the best agent, but can consider:\n* POMO baseline: Use the standard shared-baseline introduced in [2] as per Algorithm 2. This is a minimal modification to our re-implementation of POMO and so was initially used for all presented results in the paper.\n* Analytical baseline: As presented in line (169~171); when subsequently deriving the analytical gradient of the population-level objective, we find that the baseline is not the average performance of all agents (i.e. POMO baseline), but rather the performance of the second best agent only.\n\nGiven this result, we have since re-run our experiments using the analytical baseline which we are provided below. In summary, we find that in almost all cases the analytical baseline provides better or equal performance than the POMO baseline. We believe that this highlights both that our intuitive “winner takes it all” approach works well even with slightly different choices of baseline, and that indeed our theoretical analysis correctly predicts a modified baseline that can be used in practice with strong performance.\n\nWe will include the new results in the appendix of the revised manuscript and add a summary of the above discussion in section 3 of the main text.\n\nOptimal gap (%):\n### TSP:\n\n| Method/Size | 100  | 125  | 150  |\n|-------------|------|------|------|\n| POMO (16 samples) | 0.27 | 0.42 | 0.81 |\n| Poppy 16 (POMO baseline) | 0.07 | 0.14 | 0.27 |\n| Poppy 16 (analytical baseline) | 0.06 | 0.13 | 0.28 |\n\n### CVRP:\n\n| Method/Size | 100  | 125  | 150  |\n|-------------|------|------|------|\n| POMO (32 samples) | 0.78 | 1.06 | 2.03 |\n| Poppy 32 (POMO baseline) | 0.52 | 0.71 | 1.43 |\n| Poppy 32 (analytical baseline) | 0.48 | 0.71 | 1.43 |\n\n### KP:\n\n| Method | Optimal gap |\n|--------|-------|\n| POMO (16 samples) | 0.006 |\n| Poppy 32 (POMO baseline) | 0.0005 |\n| Poppy 32 (analytical baseline) | 0.0001 |\n\n### JSSP:\n\n| Method | Optimal gap |\n|--------|-------|\n| Single (16 samples) | 7.2 |\n| Poppy 16 (POMO baseline) | 6.2 |\n| Poppy 16 (analytical baseline) | 5.5 |\n\n\n> Q2. How to determine the appropriate number of populations? Are there criteria, considerations, etc. for the decision?\n\nWe have experimentally observed that the performance increases with the size of the population (see Tables 1-2, Figure 3). However, larger populations incur higher training and inference costs. We also hypothesize that the population performance could collapse when the population is arbitrarily large, as briefly mentioned in Sec. 5 (lines 308-314). Practically, the primary limits to population size are the availability of compute during the training stage, as well as the inference budget, since populations provide various performance-time trade-offs (Fig 7).\n\n> Q3. Can you show the change in accuracy, training time, inference time, etc. according to the change in the number of population?\n\nWe briefly describe the cost of training in TSP with 100 cities in lines 214-216. More precisely, single agent baselines were trained for 5D, 1W, 1D, and 1D for respectively TSP, CVRP, KP and JSSP, while our largest populations were trained until convergence for 4D, 5D, 3D and 3D, which we will add to the paper. Additionally, we want to emphasize that Poppy is already performant with less training budget: Figure 3 (left) outlines the performance of Poppy after just a few hours of training, which is already sufficient for Poppy 4 to reach the performance of POMO (100 samples). The inference times (“Time” column) and accuracies (“Obj.”) for increasing population sizes are studied and provided in Tables 1 (TSP), and 2 (CVRP), and in Fig 7.\n\n> Q4. Algorithm 1 Input - Missing 'H' in 'number of training steps H'.\n\nThank you, we will fix it in future versions of the paper.\n\n> W1. Recent studies that have shown good results in TSP and CVRP are omitted as baselines (EAS, DPDP and SGBS).\n\nThe results presented in the main paper are achieved with pure inference without a search mechanism, which is why we excluded more expensive inference methods like EAS from the main paper. However, we present a comparison to these methods (EAS and DPDP) in Appendix C, referenced on line 322, which we will outline more clearly in the paper. We implement a naive stochastic sampling strategy to give a sense of the performance of Poppy with a larger time budget matching the number of rollouts of EAS. We show that this variant of Poppy can outperform EAS and DPDP even without an explicit adaptation at test time, further highlighting the performance of our approach. We also thank the reviewer for the reference to SGBS, which we will include in future versions.\n\nWe would also like to emphasize that EAS and SGBS are search methods used on top of pretrained models, and as such can be considered improvements orthogonal to Poppy. Indeed, in principle, Poppy could be combined with EAS and fine tuned at inference if the inference budget is large enough. We believe that leveraging populations of policies for more efficient inference-time search is a promising direction for future research but is beyond the scope of our current work. \n\n> W2. HGS shows better performance than LKH3.\n\nWe thank the reviewer for the reference. We will add it in future versions of the paper.\n"}]

Author rebuttal:
We thank the reviewers for their detailed feedback on our manuscript. We summarize some common points across reviewers:

* *Not having an explicit objective for diversity is an advantage, not a weakness.* We empirically show that Poppy attains diversity as a by-product of optimizing the proposed population objective. Crucially, Poppy does not require any problem-specific notion of diversity, which makes it generally applicable to a wide range of problems while still achieving SOTA performance across them. See answers to Reviewers Ym2T and 51fw for more details.
* *The cost incurred by training the population is comparable to that of training a single agent.* See answers to Reviewers wqBo, 51fw and ybFK for details.

In the future, we will *update* the paper in response to the reviewers’ comments. The main changes include:
* Include the results reported in the answer to Reviewer ybFK.
* Make the link between Fig. 1 (motivation for populations) and CO problems clearer.
* Clarify why the policies learned by the agents are complementary using Fig 3.
* Explain why Poppy is potentially applicable to problems other than CO.
* Include the solver HGS as a baseline for CVRP.
* Include SGBS as a baseline in Appendix C.

Additionally, we provide below several references used in the answers provided to the reviewers:


[1] Qiu et al. 2022. DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems.  
[2] Kwon et al. 2020. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning.  
[3] Zhang et al. 2020. Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning.  
[4] Hottung et al. 2022. Efficient Active Search for Combinatorial Optimization Problems.  
[5] Kool et al. 2019. Attention, Learn to Solve Routing Problems!  
[6] Xin et al. 2021. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems.  


Meta-review: The authors propose a population based training objective to use RL for solving combinatorial optimization problems. These techniques aim to learn policies that specialize and are diverse in the solution space. They show applicability to problems like TSP, CVRP, KP and JSSP. The reviewers mostly appreciated the motivation and methodology of the work and largely recommend an accept. 

It is important that you address their concerns in the final version: 
1. Better example for motivation
2. Experiments on combinatorial optimization problems with larger sizes, such as TSP with 1000 cities.
3. Some important baselines are missing - eg MDAM [1] on the packing problems.

The paper has interesting ideas to discuss, but addressing these 3 concerns would be very good for the camera ready.
Decision: Accept (poster)