Population-Based Reinforcement Learning for Combinatorial Optimization Problems
Authors: Nathan Grinsztajn
Daniel Furelos-Blanco
Thomas D Barrett
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
combinatorial optimization
population

Abstract: Applying reinforcement learning to combinatorial optimization problems is attractive as it obviates 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 are often augmented with 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 agents, which can be simultaneously rolled out at inference. To this end, we introduce Poppy, a simple theoretically grounded 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 whole population. We show that Poppy leads to a set of complementary heuristics, and obtain state-of-the-art results on three popular NP-hard problems: the traveling salesman (TSP), the capacitated vehicle routing (CVRP), and 0-1 knapsack (KP). On TSP specifically, Poppy divides by 5 the optimality gap while reducing the inference time by more than 10 compared to previous state-of-the-art reinforcement learning approaches.

Under review as a conference paper at ICLR 2023
POPULATION-BASED REINFORCEMENT LEARNING FOR COMBINATORIAL OPTIMIZATION PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Applying reinforcement learning (RL) to combinatorial optimization problems is attractive 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 prob- lems in single shot at inference due 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 simultaneously rolled out at inference. To this end, we introduce Poppy, a simple training pro- cedure for populations. Instead of relying on predefined or hand-crafted no- tion of diversity, Poppy induces an unsupervised specialization targeted solely 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: the traveling salesman (TSP), the capacitated vehicle routing (CVRP), and 0-1 knapsack (KP) problems. On TSP specifically, Poppy outperforms the previous state-of-the-an dividing the optimality gap by 5 while reducing the inference time by more than an order of magnitude.
INTRODUCTION
In recent years, machine learning (ML) approaches have overtaken algorithms that use handcrafted features and strategies across variety of challenging tasks (Mnih et al. 2015 van den Oord et al., 2016 SSileer et al. 2017 Brown et al. 2020). In particular, solving combinatorial optimization (CO) problems where the maxima or minima of objective function acting on a finite set of discrete variables is sought has attracted significant interest (Bengio et al., [222]] due to both their (often
NP) hard nature and numerous practical applications across domains varying from logistics (Sihhi & 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 handcrafted heuristics using expert knowledge. Whilst diversity of ML-based heuristies have been proposed, reinforcement learning [RL:|Suttonn & Barto (018) is a promising paradigm as 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.
To improve the quality of proposed solutions, RL methods typically generate multiple candidates with additional search procedures, which can be divided into two families (Mazyav First, improvement methods start from a feasible solution and iteratively improve it through small modifications (actions). However, such incremental search cannot quickly access very different so- lutions, and requires handcrafted procedures to define a sensible action space. Second, construction methods incrementally build a solution by selecting one element at time. Multiple solutions can be built using sampling strategies, such as stochastic sampling policies or beam search. However, just as improvement methods are biased by the initial starting solution, construction methods are bi- ased by the single underlying policy. Thus, a balance must be struck between the exploitation of the learned policy (which may be ill-suited for a given problem instance) and the exploration of different solutions (where the extreme case of a purely random policy will likely be highly inefficient).
al. 202I).

---

Under review as a conference paper at ICLR 2023
In this work, we propose Poppy, a construction method that uses a population of agents with suitably diverse policies to improve the exploration of the solution space of hard CO problems. Whereas a 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 perfor- mant on any given problem instance. However, realizing this intuition presents several challenges: (i) naively training a population of agents is expensive and challenging to scale, (ii) the trained pop- ulation 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) is addressed by sharing large fraction of the computations across the population, specializing only lightweight policy heads to realize the diversity of agents. Challenges (ii) and (iii) are jointly achieved by introducing an RI. objective aimed at specializing agents on distinct subsets of the problem distribution. Concretely, we derive lower bound of the true 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
instance where another agent already has better performance. Strikingly, 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 follows:
1. We motivate the use of populations for CO problems efficient way to explore envi- ronments that are not reliably solved by single-shot inference.
2. We derive a new training objective and present a practical training procedure that encour- ages performance-driven diversity (i.e. effective diversity without the use of explicit behav- ioral markers or other external supervision).
3. We evaluate Poppy on three CO problems: TSP, CVRP, and 0-1 knapsack (KP). On TSP and KP, Poppy significantly outperforms other RL-based approaches. On CVRP, it con- sistently outperforms other inference-only methods and approaches the performance of ac- tively fine-tuning problem-specific policies.
RELATED WORK
The first attempt to solve TSP with neural networks is due to Hopfield & Tank (1985), which only scaled up to 30 cities. Recent developments of bespoke neural architectures (Vinyals et al. 2015) Vaswani et al. (017) and performant hardware have made ML approaches increasingly efficient. Indeed, several architectures have been used to address CO problems, such as graph neural networks (Dai et al. 2017), recurrent neural networks (Nazari et al.) 2018), and attention mechanisms (Deudon et al. 2018). In this paper, we use encoder-decode architecture that draws from that proposed by Kool et al. (201)). The costly encoder is run once fed to small decoder iteratively rolled
ML for Combinatorial Optimization
per problem instance, and the resulting embeddings out to get the whole trajectory, which enables efficient inference. This approach was furthered by Kwon et al. (2020), 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. (202T) also draws on Kool et al. and uses hierarchical strategy where a seeder proposes solution candidates, which are refined bit by bit by reviser. Closer to our work, Xin et al. (202T) trains multiple policies using a shared encoder and separate decoders. Whilst this work (MDAM) shares our architecture and goal of training a population, our approach for enforeing diversity differs substantially. MDAM explicitly trades off performance with diversity by jointly optimizing policies and their KL divergence. Moreover, as computing the KL divergence for the whole trajectory is intractable, MDAM is restricted to only using it to drive diversity at the first timestep. In contrast, Poppy drives diversity by maximizing population-leve 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 an
2

---

Under review as a conference paper at ICLR 2023
initial solution: de O. da Costa et al. (2020) uses policy gradients to learn a policy that selects lo- cal operators (2-opt) given a current solution in TSP, while Lu et al. (2020) and [u et al. (2021) extend this method to CVRP. This idea has been extended to enable searching learned latent space of solutions (Hottung et al. 2021]. However, these approaches have two limitations: they environment-speciffe 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. 202T), dynamic programming (Kool et al. 2021) or active search (Hottung 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-Based RL Populations have already been used in RL to learn diverse behaviors. In a different context, Gupta et al.) (2018). Eysenbacch et al. (2019), Hartikainen et al. (2020) and Pong eet al. (2200) use a single policy conditioned on a set of goals as an implicit population for unsu- pervised skill discovery. Closer to our approach, another line of work revolves around explicitly
storing a set of distinct policy parameters. [Dan et al. (2020). Hong et al. (2018). B) Jung et al. (2020) and PodPaerr--Hlderr
al.] (2020) use a population achieve better coverage of the policy space. However, they enforce explicit attraction-repulsic
mechanisms, which is major difference with respect to our approach where diversity is pure byproduct of performance optimization.
Our method is also related to approaches combining RL with evolutionary algorithms (EA: Khadka & Tumerr 2018 Khadka et al., 2019; Pourchot Sigaud, 2019), which benefit from the sample- efficient RL policy updates while enjoying evolutionary population-level exploration. However, the population is means to learn a unique strong policy, whereas Poppy learns a set of complementary strategies. More closely related, Quality-Dvvessity (QD; |Pugh (QD: et al., 2016 Cully & Demiris 2018) is a popular EA framework which maintains a portfolio of diverse policies. Pierrot et al. (2022) has recently combined RL with QD algorithm, Map-Elites (Mouret & Clune (015); unlike Poppy, QD methods rely on handcrafted behavioral markers, which is not easily amenable to the CO context.
One of the drawbacks of population based RL is its expensive cost. However, recent approaches have shown that modern hardware as well as targeted frameworks enable efficient vectorized popu- lation training (Flajolet et al. 2022 opening the door to wider range of applications.
METHODS
3.1
BACKGROUND AND MOTIVATION
RL Formulation A CO problem instance p sampled from some distribution D consists of a dis- crete set of N variables (e.g. city locations in TSP). We model a CO problem as a Markov de- cision process (MDP) defined by state space S, an action space A, transition function T, reward function R and discount factor 7. A state is a trajectory through the problem instance T: (xI,,... ( Fie) E S where xj E p, and thus consists of an ordered list of variables (not nec- essarily of length N). An action, a E A C p. consists of choosing the next variable to add; thus, given state Te = (#1...., .z.) and action the next state is T(-1 T( a) (#1...... Ie, a). Let S* S be the set of solutions; that is, states that comply with the problem's 'ss constraints (c.g., a sequence of cities such that each city is visited once and ends with the starting city in TSP). The reward function R : S* - RR. maps solutions into scalars. We assume the reward is maximized by the optimal solution (e.g. R returns the negative tour length in TSP).
A policy na parameterized by 0 can be used to generate solutions for any instance ~ D by iteratively sampling the next action a E A according to the probability distribution ne (- (.).) We leam Tg using REINFORCE (Williams 1992). This method aims at maximizing the RL objective (() = Ey 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 vnJ E.p-DE,TTo,pl (R(7) - b,) Vo log(po(T)), where po(r) = II. no (at+1 p, Te) and b, is baseline. The gradient of the objective, VoJ. can be estimated empirically using Monte Carlo simulations.
Motivating Example We argue for the benefits of training a population using the example in Figure I In this environment, there are three actions: Left, Right, and Up. Up leads to medium
3

---

Under review as a conference paper at ICLR 2023
Up is safer...
Left!
Right!
IIII
IXIII
Figure 1: In this environment, the upward path always leads medium reward, while the left and right paths are intricate such that either one may lead to a low reward or high reward with equal probability. Left: An agent trained maximize a sum of rewards will converge taking the safe upward road since it does not have enough information to act optimally. Right: A two-agent population can always try the left and right paths and thus get the largest reward any instance.
reward, while Left/Right lead to low/high or high/low rewards (the configuration determined with equal probability at the start of each episode). Crucially, the left and right paths are intricate, so the agent cannot easily infer from its observation which one leads to a higher reward. Then, the best strategy for single agent is always go Up. the guaranteed medium reward (2 scoops) higher than the expected reward of guessing left or right (1.5 scoops). In contrast, two agents in 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 be optimal (one agent gets the maximum reward), and (ii) the average performance worse than in the single-agent case.
Specifically, the discussed phenomenon can occur when (i) some optimal actions are too difficult to infer from observations and (ii) choices are irreversible (i.e. it is not possible to recover from suboptimal decision). These conditions usually hold when solving hard CO problems. In these situa- tions, shown above, maximizing the performance of population will require agents to specialize and likely yield better results than in the single agent case.
3.2 POPPY
We present the three distinct components of Poppy: an architecture enabling efficient population rollouts, an RL. objective encouraging agent specialization, and the overall training procedure.
Architecture We use the attention model introduced by Kool al. (019). which decomposes the policy model into two parts. First, a large encoder hap takes an instance as input and outputs embeddings w for each of the variables in p. Second, smaller decoder qa takes the embeddings and trajectory Crucially, the expensive computation of embeddings can done once for every instance at the beginning of an episode since it is independent of any trajectories; hence, only lightweight decoding operations are performed at each timestep.
input, and outputs the probabilities of each of the next possible actions.
We exploit this framework to build population of K agents. The encoder hy is shared as a com- mon backbone for the whole population, whereas the decoders Zo, 902 9xx are unique each agent. This is motivated by (i) the encoder learning general representation useful for all agents, and (ii) reducing the overhead of training a population and keeping the total number of parameters low. A discussion the model sizes is provided in Appendix A.1
Population- Based Training Objective The usual RL objective J(0) EEp R((T) was previously presented in Section 3.1 Intuitively, the population objective corresponds to rolling out every agent in the population for each problem and using the best solution. For the parameters 0 (01, 02,.... ,xk of population of K agents, the population objective can be thus defined as:
Jpep (0) = EEpDEEn Cote Tr Tar TK max [R(,), R(72),.... R(Tx))-
4

---

Under review as a conference paper at ICLR 2023
In order to update 8, we derive simple lower bound designed at inducing agent specialization:
Jpup (0) = Epp 1 man ".. max (R((T)), R(T2), ...., B(Tx)],
Spopl (0) 2 E max BBnsay R(n)) ) Bianao, R(T2), Bry R R(Tx)
(0) 2 E [Erwaog B((T)] with 0% arg max IE (r R(().
0,50
This lower bound, which denote Jeepy and treat our RI. objective, corresponds to evaluating only the best performing agent on each instance. Importantly, Jpppy can be optimized using standard policy gradients (Sutton al.) 1999), with the difference that for each problem only the best agent is trained. As we do not have access to 2. we estimate these as those of the agent with the highest reward on p (breaking ties arbitrarily). This leads to an approximated optimization of J Japppy We analyze the resulting bias in the gradient estimation of the objective in Appendix B and find that vanishes in the limits of either deterministic agents (where only a single trajectory per agent is required to know the best policy) or perfect specializations (where each agent will always outperform the entire rest of the population on instances to which is specialized). Intuitively and empirically, therefore observe that the gradient bias reduces over the course of training. This formulation is applicable across a variety of problems and directly optimizes for population-Ievel performance without explicit supervision handcrafted behavioral markers.
We emphasize that optimizing the presented objective does not provide any strict diversity guarantee. However, note that diversity maximizes objective in the highly probable case that, within the bounds of finite capacity and training, a single agent is not optimal on all subsets of the training distribution. Therefore, intuitively (and, will show, practically) diversity emerges over training in the pursuit of maximizing the objective.
Algorithm 1: Poppy training
input: problem distribution D, number of agents K, batch size B, number of training steps H, K sets of parameters qo.: 9.2..... 9pk
for step I to do
Pi Sampl lel (D) Vi E...., B;
n +- Rollout (o.) Vi E I,...,,,.Y... E...., K;
/* Select the best agent for each problem P:.
k < arg max I(TAt) Vi 1i B:
/* Propagate the gradients through these only.
L((go "....... ........)))))))........))... + 1
B EisB REINFORCE(())
(for) 102....... (0x) + (1d1) lezi.... (0x) L.V Loar gox )
Training Procedure
The training procedure consists of two phases
1. A single-decoder architecture (i.e. single agent) is trained from scratch, as shown in Fig- ure ure (left). This step is identical to the training process Kwon et al. (020)).
2. The decoder trained in Phase is cloned K times form K-agent population. The whole model is trained using the approximated Jpopgy objective, as described in Algorithm and illustrated in Figure 2 (right). Agents implicitly specialize on different types of problem instances during this phase.
Phase 1 enables training the large encoder without the computational overhead of 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 a single (or few) agent(s) dominate the performance across all instances. In this case, only the initially dominating agents receive training signal, further widening the performance gap. Whilst directly training population of untrained agents for population- -leeel performance may be achievable with suitable modifications, we instead opt for the described pre- pre-training approach as is efficient and stable.
Some of the experiments presented later were run using an obsolete 3-phase training procedure. The details are provided in Appendix A.2
5

---

Under review as a conference paper at ICLR 2023
Node
Node embedking
probubilitt
Masked node
Training
Prozen
Ri V
R2
R3
Fnosder
Duceder
Fneeddrr
Disceders
Figure 2: Phases of the training process. Left (Phase I): the encoder and the decoder trained from scratch. Right (Phase 2): the decoder is cloned times, and the whole model is trained using the Poppy training scheme (i.e. the gradient is only propagated through the decoder that yields the highest reward).
Starting points Following Kwon et al. (2020), we generate multiple solutions for each instance starting points, where N is the number of instance variables. For
by considering set of P E [1, example, a starting point in a TSP instance could be any of cities. Therefore, across the different training phases, agents generate trajectories for (instance, starting point) pairs. The average reward across starting points is used as the REINFORCE baseline. By default, we consider each (instance, starting point) pair as a separate problem and, thus, train the best agent for each of them. We refer the reader to Appendix A.2 for details.
4 EXPERIMENTS
We evaluate Poppy on three CO problems: TSP, CVRP, and KP. To emphasize its generality, we use the same hyperparameters for each problem, taken from Kwon al. (2020). We run Poppy for populations of 4, 8, 16, or 32 agents, which exhibit various time-performance tradeoffs.
Training One training step corresponds to computing policy gradients over the same batch of 64 instances for each agent in the population. Training time varies with problem complexity and train- ing phase. For instance, in TSP with 100 cities, Phase takes 4.5M (5 days) steps, whereas Phase takes 400k training steps and lasts 1-4 days depending the population size. Our JAX-based im- plementation using environments from the Jumanji suite (Bonnet et al. (022), along with problem instances reproduce this work, available https:////// http///nnnymmuss 4open. science/
E/ r/poppy 6D20
All experiments were run on a v3-8 TPC.
Inference We greedily roll out each agent in the population, and use the augmentations proposed by Kwon al. (2020) for TSP and CVRP. Additionally, give with larger time budget, we implement a simple sampling strategy. Given population of K agents, first greedily rollout each of them every starting point, and evenly distribute any remaining sampling budget across the most promising K (agent, starting point) pairs for each instance.
of the performance of Poppy
Baselines We compare Poppy against exact solvers, heuristics, and state-of tiite--f-the-rr the--at art ML methods. Some baseline performances taken from Fu et al. (2021), I2 Xin et al. (2021) and Hottung et al. (2022) 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 in bles. As a comparison guideline, we informally note that these GPU inference times should be approximately divided by 2 to get the converted TPU time.
4.1 TRAVELING SALESMAN PROBLEM (TSP)
Given a set of n cities, the goal in TSP is to visit every city and come back to the starting city while minimizing the total traveled distance.

---

Under review as a conference paper at ICLR 2023
Setup We use the architecture used by Kool et al. (0119) and Kwon al. (2020) with slight modifications (see Appendix C. The testing instances are taken from Kool et al.
(219 for n = 100,
and from Hottung al. 2022) for {125, 150). The training is done on
100 instances. We
compare Poppy to (i) the specialized supervised learning (SL) methods GCN-BS (Joshi et al. 2019),
CVAE-Opt (Hottung al. (02T), DPDP (Kool et al.] 202T); ; (ii) the fast RL. methods with limited sampling budgets POMO with greedy rollout, POMO with 16 stochastic rollouts (to match Poppy 16 runtime), POMO with an ensemble of 16 decoder heads trained in parallel (i.e. using the architecture of Poppy's ' Phase 2 but without specializing), MDAM (Xin et al. 2021) with greedy rollouts, and Att- At-GCRN+MCTS (Fu et al.) 2021 ; and (iii) the slow RL methods (characterized by the inclusion of extensive search strategies) 2-Opt-DL (de O. da Costa et al.) 2020), LIH (Wu et al.) 2021), MDAM with beam search (beam size 50), POMO with 200 rollouts, and the fine-tuning approach EAS (Hottung et al. 2022). In addition to these ML-based approaches, we also compare to the exact solver Concorde (Apllegaee et al. 2006) and the hcuristic solver LKH3 (Helsgaun 2017).
Results Table 1 displays the average tour length, the optimality gap, and the total runtime for each test set. The best algorithm remains Concorde as highly specialized TSP solver. Re- markably, Poppy 16 with greedy rollouts reaches the best performance across every category in just a few minutes, except for one case where DPDP performs better; however, DPDP tackles specifi- cally routing problems and makes use of expert knowledge. With extra sampling, Poppy reaches performance gap of 0.001 %, which establishes a state-of-the-art for general MI.-hased approaches. Compared to DPDP, Poppy improves O-shot performance, suggesting that it is more robust to distri- bution shifts. AU-GCRN+-CTS is known for being scalable to larger TSP instances than TSP 100; however, it is outperformed by Poppy, showing that it trade off's performance for scale. Compared to the previous tate-of-the-an fast RL method, POMO, Poppy 16 obtains strictly better performance in 81.67% of the TSP100 instances, and better or equal performance in 98.02%. Finally, we em- phasize that specialization is crucial to achieve state-of-the art performance: Poppy 16 outperforms POMO 16 (ensemble), which also trains 16 agents in parallel but without the Jpopry objective (i.e. without specializing to serve as an ablation of our proposed objective).
Table I: TSP results.
Inference (10k instances)
O-shot (Ik instances)
100
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
GCN-BB
7.87
1.39%
40M
CVAE-Opt
0.343%
6D'
8,646
0.736%
21H
9.482
1.45%
30H
DPDP
7.765
0.0041%
2H'
8.589
0.070%
31M
9.434
0.94%
44M'
POMO
7.774
0.13%
37S
8.605
0.26%
9.393
0.50%
10S
RL (fast)
POMO (16 samples)
7.770
0.073%
9M
8.597
0.16%
IM
9.385
0.41%
2M
POMO 16 (ensemble)
7.773
0.10%
9M
8.603
0.23%
1M
9,393
0.50%
2M
MDAM (greedy)
7.93
2.19%
36S
MCCTS
0.037%
15M
Poppy
7.767
0.029%
2M
8.590
0.079%
23S
9,364
0.19%
38S
Poppy
7.766
0.015%
5M
8.587
0.046%
45S
9,360
0.14%
IM
Poppy 16
7.765
0,008 %
9M
8,585
0.029%
1M
9.356
0.10%
2M
2-Opt-DL
7.83
0.87%
41M"
(slow)
LIH
7.87
1.42%
2H"
MDAM (beam search)
7.79
0.38%
44M"
POMO (200 samples)
7.769
0.056%
2H
8,594
0.13%
20M
9,376
0,31%
32M
EAS
7.768
0.048%
8.591
0.091%
9.365
0.20%
1H"
Poppy 16 (200 samples)
7.765
0.002%
2H
8.584
0.009%
20M
9.351
0.05%
32M
Analysis Figure 3 helps understand the resulting behavior from using Poppy. The left plot shows that whilst the population-level performance improves with population size, the average performance of a random agent from the population gets worse. This shows a stronger specialization for larger populations, which J poppy appears to balance. Since Poppy produces unsupervised specialization favoring the best agents, it is natural to consider how performance distributes across the population. In the right plot, we observe the performance is quite evenly distributed across the population of Poppy 16; hence, showing that the population has not collapsed to a few high-performing agents, and that Poppy benefits from the population size, Additional analyses made in Appendix C.1.4
7

---

Under review as a conference paper at ICLR 2023
10
0-0
Optinality gap (KQ
0.0003
Optimality gop (5)
Averago
10
Best
0015
10
1O0I8
0.0000
POMO
Puppy 4
Poppy 8
Puppy 16
Agentsi
Figure 3: Analysis of Poppy TSPI00. Left: With poppy. the average performance gets worse as the population size increases, but the population-level performance improves. Right: Optimality gap loss suffered when removing any agent from the population using Poppy 16. Although some agents contribute more (e.g. 2, 7) and some less (e.g. 15, 16), the distribution is relatively even with all agents contributing, even though no explicit mechanism enforces this behavior.
4.2 CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
Given vehicle with limited capacity departing from a depot node and set of n nodes with different demands, the goal is find an optimal set of routes such that each node (except for the depot) is visited exactly once and has its demand covered. The vehicle's 's capacity diminishes by the demand of the visited node (which must fully covered) and it restored when the depot visited.
Setup We the test instances used by Kwon et al. (2020) for 100. and the sets from Hottung et al. (2022) to evaluate generalization to larger problems. We evaluate Poppy with populations of 8 and 32 agents. We compare Poppy the heuristic solver LKH3 (Helsgaun) (017), taken as reference to compute the gaps although its performances are not optimal. We also report results for the supervised ML methods CVAE-Opt (Hottung et al. [222]. DPDP (Kool et al., 2021), and RL methods NeuRewriter (Chen & Tian 2019). NLNS (Hottung & Tiemey (020), POMO (K won al. 2020), MDAM (Xin al. 2021), LIH (Wu al. 2021), and EAS (Hottung al. (022). As for TSP, evaluate POMO with greedy rollouts, 32 stochastic samples to match the runtime of our largest population, and 200 samples.
Results Table shows Poppy has the best time-performance tradeoff among the fast approaches, e.g. Poppy 32 has the same runtime as POMO with 32 stochastic rollouts while dividing by 1.5 the optimal gap 2 In addition, Poppy 32 is strictly better than POMO in 93.83% of the CVRP100 instances, and better or equal in 93.87%. Among the slow RL approaches, adding sampling to Poppy makes it on par with DPDP depending on the problem size, and it is only outperformed by the active search approach EAS, which gives large improvements on CVRP. However, active search (i) prevents parallelization (as scales linearly with the number samples) and (ii) could added top of Poppy instead of stochastic sampling to further boost performance, which we leave for future work.
4.3 0-1 KNAPSACK (KP)
We evaluate Poppy on demonstrate applicability beyond routing problems. Given set items with specific weights and values and bag of limited capacity, the goal is to determine which items to add such that the total weight does not exceed the capacity and the value maximal.
Setup We the setting employed by Kwon et al. (020):: action corresponds putting item in the bag, which is filled iteratively until no remaining item can be added. We evaluate Poppy on population sizes against the optimal solution based on dynamic programming, greedy heuristic, and POMO with and without sampling.
A fine- fine-grained comparison between POMO with stochastic sampling and Poppy is in Appendix
8

---

Under review as a conference paper at ICLR 2023
Table CVRP results.
Inference (10k instances)
0-shot (Ik instances)
0-shot (Ik instances)
100
125
150
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
LKH3
15.65
0.000%
17.50
0.000%
19H
19.22
0.000%
20H
CVAE-Opt
1.30%
11D'
17.87
2.08%
36H
19.84
3.24%
46H'
S1
DPDP
15.63
-0.13%
23H
17.51
0.07%
3H'
19.31
0.48%
5H
NeuRewriter
16.10
66M
NLNS
15.99
2.23%
62M"
18.07
3.23%
19.96
3.86%
12M"
RL (fast)
POMO
15.76
0.76%
17.68
1.02%
<1M
19.58
1.85%
1M
POMO (32 samples)
15.70
0.32%
43M
17.59
0.50%
8M
19.48
1.35%
12M
POMO (ensemble)
15.72
0.49%
17.63
1.37%
MDAM (greedy)
16.40
4.80%
45S
Poppy 4
15.72
0.45%
5M
17.62
0.69%
2M
19.49
1.38%
2M
Poppy 8
15.70
0.32%
17.60
0.54%
3M
1.22%
Poppy
15.68
0.20%
43M
17.57
0.40%
8M
19.41
1.00
12M
RL (slow)
LIH
16.03
2.47%
SH"
MDAM (beam search)
15.99
2.23%
53M
POMO (200 samples)
15.67
0.18%
17:56
0.33%
43M
1.08%
EAS
15.62
-0.14%
8H"
17.50
0.00%
80M
19.36
0.72%
2H"
Poppy (200 samples)
15.63
-0.10%
17.51
0.02%
42M
19.34
0.61 %
Results Table shows that Poppy leads to improved performance with a population of 16 agents, dividing the optimality gap with respect to POMO by 45 and 12 on KP100 and KP200 respectively, and by 12 and with respect to POMO with 16 stochastic samples for the exact same runtime. Poppy 16 is strictly better than POMO in 34.30% of the KPI00 instances, and better in 99.95%.
Table 3: KP results.
Testing (10k instances)
Testing (Ik instances)
n 100
n 200
Method
Obj-
Gap
Time
Obj.
Gap
Time
Optimal
40.437
57.729
Greedy
40.387
0.1250%
57.672
0.0986%
POMO
40.428
0.0224%
57.718
0.0191%
4S
POMO (16 samples)
40.435
$7.727
0.0082%
IM
POMO 16 (ensemble)
40.429
0.021%
2M
57.719
0.0170%
IM
Poppy
40.434
0.0081%
338
57.723
0.0099%
16S
Poppy
0.0032%
0.0058%
338
Poppy 16
40.437
0,0005 %
2M
57.728
0.0015%
IM
CONCLUSIONS
Poppy a population- based RL method for CO problems. uses an RL 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-art performance on three popular NP-hard problems: TSP, CVRP, and KP.
This work raises several questions. First, we have experimented on populations at most 32 agents; therefore, it is unclear what the consequences of training larger populations are. We hypothesize that the population performance would eventually collapse, leaving agents with null contributions behind. Exploring this direction, including possible strategies to prevent such collapses, is an inter- esting direction for future work. Second, we recall that the motivation behind Poppy was dealing with problems where predicting optimal actions from observations is too difficult to be solved liably by single agent. We believe that such settings may not be strictly limited to canonical CO problems, and that population-based approaches offer promising direction for many challenging RL applications. In this direction, we hope that approaches (such as Poppy) that alleviate the need for handcrafted behavioral markers, whilst still realizing performant diversity, could broaden the range of applications of population-based RI.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We provide in Appendix A.2 the detailed pseudocode of our method. Model architectures well as the training hyperparameters are given in Appendices C.1.2 C.2.2 and C.4 for TSP, CVRP and KP respectively. Source code and test instances are available at httpps://// anonymous. 4open. science/E/poppy-o0
REFERENCES
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2006.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: A methodological tour d d'horizon. European Journal of Operational Research, 290(2):
2021.
Clément Bonnet, Donal Byrne, Victor Le, Laurence Midgley, Daniel Luo, Cemlyn Waters, Sasha Abramowitz, Edan Toledo, Cyprien Courtot, Matthew Morris, Daniel Furelos-Blanco, Nathan Grinsztajn, Thomas D. Barrett, and Alexandre Laterre. Jumanji: Industry-driven hardware- accelerated RL environments, 2022. URL https://giithin com/ int.t/eeataaaaa////
jumanji
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel HerseertVVsss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, and Chris Hesse. Language models are few-shot learners. Ad- vances in Neural Information Processing Systems, 2020.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Advances in Neural Information Processing Systems, 2019.
Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation, 22(2):245-259, 2018. doi: 10.1109/EVV.2011..77011
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs In Advances in Neural Information Processing Systems, 2017.
Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Confer- ence on Machine Learning, 2020.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Pro- gramming, Artificial Intelligence. and Operations Research, pp. 170-181. Springer International Publishing, 2018
Thang Doan, Bogdan Mazoure, Moloud Abdar, Audrey Durand, Joelle Pineau, and R. Devon Hjelm. Attraction-repulsion actor-critic for continuous control reinforcement learning. arXiv preprint arXiv: /0X.00/999.07543 2020.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without reward function. In International Conference on Learning Representa- tions, 2019.
Arthur Flajolet, Claire Bizon Monroc, Karim Beguir, and Thomas Pierrot. Fast population-based reinforcement learning on a single machine. In International Conference on Machine Learning, 2022.
Zhang- Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbi- trarily large TSP instances. In Chirty-Fifth AAAI Conference on Artificial Intelligence. AAAI 2021, Thirty-Third Conference Innovative Applications of Artificial Intelligence, IAAI 2021,
10

---

Under review as a conference paper at ICLR 2023
The Eleventh Symposium Educational Advances in Artificial Intelligence, EAAI 2021, Virual Event. February 2-9, 2021, pp. 7474-7482, AAAI Press, 2021. URL hatpps://oss aaai.
org/index php/ AAAI Att.///Aa/aaaatttaeeaaaaeaaaaaet /vtee///vieeei/eeeee http/v/wwww////////// 16916
Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, and Sergey Levine. Meta- reinforcement learning of structured exploration strategies. In International Conference on Neural Information Processing Systems, 2018.
Kristian Hartikainen, Xinyang Geng, Tuomas Haarnoja, and Sergey Levine. Dynamical distance learning for semi-supervised and unsupervised skill discovery. In International Conference on Learning Representations, 2020.
K. Helsgaun. An extension of the inn-kernghhan-helsaan tsp solver for constrained traveling sales- man and vehicle routing problems. Roskilde University, Tech. Rep., 2017.
Zhang-Was Wei Hong, Tzu- Yun Shann, Shih-Yang Su, Yi-Hsiang Chang, and Chun-Yi Lee. Diversity- driven exploration strategy for deep reinforcement learning. In International Conference on Neu- ral Information Processing Systems, 2018.
J J Hopfield and W David Tank. "neural" computation of decisions optimization problems. Bio- logical cybernetics, 52(3):141-15,, 1985.
André Hottung and Kevin Tiemnyy Neural large neighborhood search for the capacitated vehicle routing problem. In 24th European Conference on Artificial Intelligence (ECAI 2020), 2020.
André Hottung, Bhanu Bhandari, and Kevin Tiemey. Learning latent search space for routing prob- lems using variational autoencoders. In International Conference on Learning Representations, 2021.
André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint wrXiv:1906.0122. 2019.
Whiyoung Jung, Giseung Park, and Youngchul Sung. Population-guided parallel policy search for reinforcement learning. In International Conference on Learning Representations, 2020.
Shauharda Khadka and Kagan Tumer. inoluttionguideen policy gradient in reinforcement learning. In Conference on Neural Information Processing Systems, 2018
Shauharda Khadka, Somdeb Majumdar, Tarek Nassar, Zach Dwiel, Evren Tumer, Santiago Miret, Yinyin Liu, and Kagan Tumer. Collaborative evolutionary reinforcement learning. In Interna- tional Conference on Machine Learning, 2019.
Minsu Kim, Jinkyoo Park, and joungho kim. Learning collaborative policies to solve np- ap-hard routing problems. In Advances in Neural Information Processing Systems, volume 34, pp. 10418-10430. Curran Associates, Inc., 2021. URL htttps::
neur ps cc cctppper/ .htm_
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. arXiv preprint arXiv:2102.11756, 2021.
Yeong-Das Kwon, Byoungjip Kim Jinho Choo, Youngjune Gwon Iljoo Yoon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, 2020.

---

Under review as a conference paper at ICLR 2023
Hao Lu, Xingwen Zhang, and Shuang Yang. learning- iterative method for solving vehicle routing problems. In International Conference on Learning Representations. 2020.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charlie Beattie, Amir Sadik, Ioannis Antonoglou. Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533. 2015.
Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint TrXX::1500.04499, Apr 2015.
Mohammadreza Nazari, Afshin Oroojlovy, Lawrence V. Snyder, and Martin Takáč. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, 2018.
Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective diver- sity in population based reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Thomas Pierrot, Valentin Macé, Félix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Be- guir, Antoine Cully, Olivier Sigaud, and Nicolas Perrin-Gilbert. Diversity policy gradient for sample efficient quality-diversity optimization. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2022.
Vitchyr H. Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew- fit: State-covering supervuue reinforcement learning. In International Conference Ma- chine Learning, 2020.
Alois Pourchot and Olivier Sigaud. Cem-rl: Combining evolutionary and gradient-basse based methods for policy search. International Conference on Learning Representations, 2019.
Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3, 2016. ISSN 2296-9144. doi: 10.3388/ffrob.22166.0000
Abdelkade Sbihi and Richard W. Eglese. Combinatorial optimization and green logistics. 4OR, 5: 99-116. 2007.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanetot, L. Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap, Karen Si- monyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforce- ment learning algorithm. ArXiv, abs/1712.01815, 2017.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http::/incempleeelddas htt.a///aaaa.eeeebbbaa//ee--bbao
html
Richard S. Sutton, David A. McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, pp. 1057-1063, 1999.
Aäron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alexander Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative 2016.
model for raw audio. ArXiv,
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
12

---

Under review as a conference paper at ICLR 2023
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In Advances in Neural Information Processing Systems, 2015.
Adam Zsolt Wagner. Refuting conjectures in extremal combinatorics via linear programming.
Journal of Combinatorial Theory, Series A, 169: 105130, Jan 2020. doi: 10. 10.1016/,,itta2011, 105130. URL https:/ /www www.scciencedi.. rect. com sci wwcciinneearttr. http:/aaaiccceeeaeaaea S00973165193000 9331111
Ronald Williams. Simple statistical cradient-following algorithms for connectionist remforrmmmt learning. Machine Learning. 8:229-256, 1992.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problems. IEEE Trunsactions on Neural Networks and Learning Systems, pp. 1-13, 2021. doi: 10. LLL10ONNNSSS22221336633333
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In In Proceedings of the 35th National Conference Artificial Intelligence, AAAI, 2021.
A ADDITIONAL DETAILS ON POPPY
A.1 NUMBER OF PARAMETERS
Table shows the total number of parameters of our models function of the population size. Since the decoder represents less than 10% of the parameters, scaling the population size can be done efficiently. For instance, population of 16 agents roughly doubles the model size.
Table Number of model parameters for different population sizes.
Population size
Encoder
Decoder
8
16
32
Parameters
1,190,016
98,816
1,288.832 0%%
1,585,280 23%
1,980,544 54%
2,771,072 115%
4,352.128 238%
Extru parumeters
A.2 TRAINING DETAILS
(see "Training Procedure"), we described that Poppy consists of two phases. In nut- shell, 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 K times (where K is the number of agents) and specialize them using the Jpuppy objective. Algorithm 2 shows the low-level implementation details of the training of the population (i.e., Phase 2) omitted in Algorithm [ for simplicity; namely, given K agents and P starting points, x K trajectories are rolled out for each instance, among which only are effectively used for training.
In Section 3.2
For historical reasons, we describe an alternative procedure which instead uses of three phases to achieve the same results. The experimental results for CVRP and KP (Sections 4.2 and 4.3) were obtained using this three-phase training procedure; however, with both approaches Icading to equiv- alent performance, retraining all models with the two-phase procedure is not necessary. In what follows, we detail these phases:
Equivalent to the current Phase 1.
2. The trained decoder discarded and population of decoder heads is randomly initialized. With the parameters of the shared encoder frozen, the decoders trained in parallel using the same training instances.
3. The encoder is unfrozen and trained jointly with the population decoders as described in the current Phase 2 (Section 3.2
13

---

Under review as a conference paper at ICLR 2023
Algorithm 2: Poppy training with starting points
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 he and a set of K decoders (0 L0g....... 96x
for step 1 to H do
Pi f Sample ViE B; Bi.1.....;00 < SelectstartPoiintsaa Vi l.....
7 Rollout(p: Bi (ow) vi E ,...,, B, Vp ,..., P, El...,K K;
iy ((Tip))
/* Select the best agent per (instance, starting point).
/
kr f arg max R(T vi
/* Propagate the gradients through these only.
VL(hs 96r "o...................... t BP Dip - Vo (Tp)): 90, (her9011
(Tepp
(he,
962..... ................................ 90x) + (he 9or 9621.... (0x)) aV 96: 9021 ......... 90x)
The crucial difference that motivates the use of an additional phase is the fact that after Phase the decoder heads are not cloned but randomly initialized. However, the purpose is exactly the same: have generally capable agents before specializing in order to avoid that only a few dominating agents are trained. We have opted for cloning the decoder from Phase 1 instead of training set of non- specialized decoders
parallel since: (i) there are less phases, and (ii) is less computationally demanding (i.e. we do not need to spend training time unnecessarily). Empirically, the training of the population is performed twice as fast with the two-phase procedure in TSP100.
B MATHEMATICAL ELEMENTS
B.1 BIAS IN THE GRADIENT ESTIMATION OF THE OBJECTIVE
We recall that the instance distribution is D, and that for the parameters = {02, .2, of population of K agents, Jppppy defined as:
Jppppy EppD
E, Er R(T) with 0g arg max E, (p(T).
0,E0
The purpose of this section to quantify the bias between the gradient of Jppppys and the empirical estimate computed from Alg. that we denote V Ppoppy
V V poppy = EpwD
V 0 T R(T)
K 11 mo maz
EPDD
Er iT
R(Tk)
= ED
Duo, =K0; V Be not -o 12 u.. TwTTO R(TH)
K
= EDDD
mm =Kog
Vg, E ETANTO R(Tx))
EDDD
1 Fop Σ
Bra Vo, R(TK) log Pooe (Tx)
K
= EDND
Branay 1 To =noz
Vo, R(Te) log Prop (Tk)
14

---

Under review as a conference paper at ICLR 2023
K
= PD
Prowat 12 x tomtog 1 nop =ko Vol R((a) log Pogg Proee (Tx)
now derive an expression of V g For given instance p. and .i..... TK random trajectories sampled from the K agents in the population, denote T7 arg max,, [R(Ta)] the best trajectory the population. The gradient computed with Alg. Tis:
K
U puppy (P.
TK)
Σ k=1
1 T Vo, R(Tk) log PTo, (Tk)-
Therefore, we can derive the expected gradient:
E V poppy
EpDDDBrr Brinni (T
In Vo, R((T) log Pro (Tr)
= E
Σ
Ry mot 7
T Vo, R(Tx) log Poo Prop (Tk)
TK
The bias can thus be written as:
E
V poppy
V ppoppy
=
EpiD
E : T2 mo TKNTER (Tr Lmn Vo, R(TT) log Prop (Tt)
Thus, denoting by M an upper bound of the gradient norm (e.g., using clipped gradient),
E
( poppy
Vgddpopry
< ME
E ree T2 To
I
mag
K
T
I MEE Er man To Ta- TRevia
Tu=;
1
me.
=
rp sampled from may. else O
E
< 2.M
D.MEp~D.E DD,,EEEEE, winh to ma to mu
Irgweay)
Denoting by ky the index of 4% corresponding the best agent in the population for the instance p. we thus have:
E
poppy
@:pppppy
< 2M p (TT + Tk:
Controlling the bias amounts controlling p(7, * Tk;)- Intuitively, it is the probability that the best trajectory sampled by rolling out the whole population does not belong the best agent. It is be noted that the bias is null in the limit of deterministic agents, or if agents are specialized (meaning that the best agent in expectancy on one instance p consistently outperforms the other agents this instance). We provide empirical insights on p(T) Tk;) in the next section.
B.2 EMPIRICAL BIAS ESTIMATION
To have a sense of (T + Twe in our setting, we computed this quantity for several early check-
points for TSP. obtained after few minutes of training. Interestingly,
Fig. that
15

---

Under review as a conference paper at ICLR 2023
(T+ Txp) (i.e the probability that the best trajectory among one sampling of the population does not belong to the best agent average) decreases quickly the very beginning of the training, which we interpret as specialization. A consequence is that our gradient estimation of Jepppy less biased as the training progresses. Another observation is that this probability increases with the population size, which is logical as the number of competitors to the best agent is greater. Although the bias thus larger for large populations, the empirical performances seem seen in T These results raise question, which we leave for future work: would techniques to alleviate the gradient bias improve the performances further, or are there other mechanisms at play which explain the good performance of large populations?
be affected, as
Popralation size
0.35
0.50
1
0.45
0.40
0.35
0.30
1000
Training steps
Figure 4: (1o + Tc:) computed 20 seeds for various early checkpoints TSP.
C
PROBLEMS
We here describe the details of the CO problems we have used to evaluate Poppy, including instance generation and training details (e.g. architecture, hyperparameters). In the case of TSP and CVRP, we show some example solutions obtained by population of agents. Besides, we thoroughly ana- lyze the performance of the populations in TSP.
C.I TRAVELING SALESMAN PROBLEM (TSP)
C.1.1 INSTANCE GENERATION
The n cities that constitute each problem's instance are uniformly sampled from [0, 1|2.
C.1.2 TRAINING DETAILS
Architecture We use the same model as Kool al. (2019) and Kwon et al. (2020) except for the batch-normalization layers, which are replaced by layer-normalization to ease parallel batch processing. We invert mask used in the decoder computations (i.e., masking the available cities instead of the unavailable ones) after having experimentally observed faster convergence rates.
Hyperparameters To match the setting used by Kwon et al. (2020), we use Adam optimizer Kingma & Ba 2015) with learning rate μ 10 and Le penalization of 10-6 The encoder is composed multi-head 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 128 dimensions. The decoders are composed of multi-head attention layer with 8 heads and 16- 16-dimensional key, query and value.
The number of starting points P is 20 for each instance. We determined this value after performing grid-search based the first training steps with P (20, 50, 100)-
16

---

Under review as a conference paper at ICLR 2023
C.1.3 EXAMPLE SOLUTIONS
Figure shows some trajectories obtained from 16-agent population TSP100. 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 consequence of specializing since agents have no incentive to provide good solution if another agent already better on this instance.
C.1.4 POPULATION ANALYSIS
Figure [J shows some additional information about individual agent performances. In the left figure, observe that each agent gives average the best solution for 35% of the instances, and that for around 2.5% gives the unique best solution across the population. These numbers are evenly distributed, which shows that every agent contributes to the whole population performance. Further- more, the best performance reached by single agent in around 25% of the cases, as shown in the bottom figure. On the right displayed the performance of several cub-populations of agents for Poppy 4, and 16. Unsurprisingly, any fixed size sub- uub-population is better when sampled from smaller populations: Poppy 16 needs 4 agents to recover the performance of Poppy 4, and agents to recover the performance of Poppy 8 for example. This highlights the fact that agents have learned complementary behaviors which might be sub-optimal if part of the total population missing.
Bestrallved bi
1.2
Population size
Nunber instanos (X)
lngent
16
Optimality gap (%6
aggents
1.0
16
0.8
0.6
10
2
8
9
10
311
12
33
14
15
16
2
6
8
10
12
14
16
Agunts
Sabpopalation
11
26
8
13
Figure 5: Left: Proportion of instances that each agent solves best among the population for Poppy 16 on TSP100. Colors indicate the number of agents the population giving the same solution for these sets of instances. Right: The mean performance of 1,000 randomly drawn sub- populations for Poppy 1, 4, 8 and 16. Bottom: Proportion of test instances where any number of agents reach the exact same best solution. A 26% of the instances are best solved by single agent, and almost a 50% by three agents or less.
17

---

Under review as a conference paper at ICLR 2023
total
total iedaliegghhio 7./08
totol 7381
IMIgHh 1281
7.527
7.800
TSTN BANZEN 7.573
TOEST INTEEN 7.501
10tH
TOEAT (WOOTh 2550
Figure 6: Example TSP trajectories given by Poppy for 16-agent population from one starting
point (red).
C.2 CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
C.2.1 INSTANCE GENERATION
The locations of the customer nodes and the depot uniformly sampled in [0. 1|2. The demands
are uniformly sampled from the discrete set 1 2 ..... 0 where D 50 for CVRP 100, = 55 for CVRP125, and D 60 for CVRP150. The maximum vehicle capacity is 1. The deliveries cannot be split: each customer node is visited once, and its whole demand is taken off the vehicle's remaining capacity.
C.2.2 TRAINING DETAILS
Architecture We use the same model as in TSP. However, unlike TSP, the mask is not inverted; besides, it does only prevent the agent from revisiting previous customer nodes, but also from visiting the depot if the current location, and any customer node whose demand is higher than the current capacity.
18

---

Under review as a conference paper at ICLR 2023
We use the same hyperparameters as in TSP except for the number of starting points per instance used during training, which we set to 50 after performing grid-search with P (20, 50, 100).
Hyperparameters
C.2.3 EXAMPLE SOLUTIONS
Figure 7 shows some trajectories obtained by 16 agents from 32-agent population on CVRP100. Unlike TSP, the agent/vehicle performs several tours starting and finishing in the depot.
routes, distance coutes, distance 16.16
13 distance
distance
distance
distance 16.63
12 distance distance 16.18
distance
distance 16.56
13 distance distance 16.21
12 rantes, distance 16.02
13 montes distanoe 16.16
12 distance 15.93
rostes, distance 16.08
Figure 7: Example CVRP trajectories given by Poppy for 16 agents from 32-agent population. The depot is displayed as black square. The edges from/to the depot are omitted for clarity.
C.3 0-1 KNAPSACK (KP)
C.3.1 INSTANCE GENERATION
Item values and weights uniformly sampled in [0, 1). The bag capacity is fixed to 25.
C.4 TRAINING DETAILS
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 masked together with the items taken so far.
19

---

Under review as a conference paper at ICLR 2023
Hyperparameters
We use the same hyperparameters in TSP except for the number of start- ing points P used during training, which we set to 100 after performing a grid-search with PE (20, 50, 100).
D PEME-PEROORMANCE TRADEOFF
We present Figure g comparison of the time-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 some vironments like TSPI00, TSP125, TSP150, CVRPI50 and KP100, matching Poppy's performance by increasing the number of stochastic samples does not appear tractable.
20

---

Under review as a conference paper at ICLR 2023
0.10
Poppy Sampling
Poppy Sampling
Optinality gpp (%6
0.08
Opiinality gap (%g
0.20
0.06
0.15
0.01
0.10
Poppy
Poppy
0.02
Popgy Poppyr
0.05
Poppy
16
Poppy 16
25
50
73
100
125
1561
50
100
1501
2000
Number of sampled teajectories (163)
Number of sampled trajectories (1e3)
(a) TSPI00
(b) TSP125
0.6
Poppy
0.7
Poppy Sampling
Sampling
Optinulit gup (80
0.5
Optitulity sap (%)
0.6
0.4
0.5
Poppy
0.3
0.4
Poppyr
0.2
Poppy
0.3
Poppy
0.2
Poppy 82
0.1
Poppe
16
50
100
150
200
250
25
50
75
100
125
150
Number sampled trajectories (1e3)
Number of sampled trajectories (1e3)
(c) TSP150
(d) CVRP100
1.0
Poppy
2.0
Poppy
Sampling
Sumpling
Optimality gap (96)
Opiimality gap (96)
1.8
0.8
Poppy
1.6
0.6
1.4
Poppe
Poggy
Poppy
1.2
0.4
Poppy 32
1.0
Poppy 32
50
100
150
200
50
100
150
200
250
Number of sampled trajectories (1e3)
Number of sampled trajectories (1e3)
(e) CVRP125
(f) CVRP150
0:0150
Popgy
0.010
Poppy 4
Poggy Sampling
Optinmiity gap (%)
0.0125
Sampling
Optimally gap (96)
0.008
0.0100
0.0075
Poppy 4
0.006
Poppy- 8
0.0050
0.001
Poppy 8
0.0025
Poppy
0.002
Poppy
0.0000
10
15
20
10
Number of sampled trajectories (163)
Number of sampled trajectories (1ell)
(g) KP100
(h) KP200
Figure 8: Comparison of the perforrmfomm 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 the gap with the optimal solution for TSP and KP, and the gap with LKH3 for CVRP.
21


Reviews:
[{"review_id": "t8vznsnILGJ", "reviewer": "Reviewer_rRMu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In summary, from top to bottom, the paper: \n* Attempts to explain why a population of agents may be more useful than a single agent, under a theoretical formulation of argmax(multiple agent outputs).\n* Presents a lower bound objective which leads to a variant of policy gradient which involves only updating the policy which generated the best trajectory per problem instance.\n* Sets up the architecture as a shared encoder but with multiple decoders to denote multiple policies.\n* Demonstrates competitive experimental performance against classic and deep-learning based baselines in the literature, especially normalizing for wall-clock time.", "summary_of_the_review": "The experimental results are fine. However, I would really like to see more theoretical analysis of the proposed method, which would significantly increase the impact of the paper and also broaden its scope. Otherwise, currently from a devil's advocate point of view, the proposed method may be considered somewhat of a \"hack\" currently.", "strength_and_weaknesses": "# Strengths\n* Extensive experimental results demonstrate that the method empirically is solid. A brief read over the Appendix also contains relevant ablation studies, such as checking the diversity of the population of policies.\n* I applaud the paper for providing Figures 1 and 2, which makes the paper more engaging to read, and also help explain the encoder/decoder method much better. \n\n\n# Weaknesses\n* The theoretical motivations are quite subtle and I have quite a few questions, which if answered, could help make the paper much stronger in its theoretical/fundamental contributions:\n    * How is the framework similar/different from e.g. describing evaluation objective as a maximum of $K$ sampled trajectories from a (potentially very expressive) policy $\\pi_{\\theta_{meta}}$? In the $K=2$ case, $\\pi_{\\theta_{meta}}$ for example, could be a very bimodal policy which can also produce diverse behaviors from its two modes.\n    * Is Algorithm 1 an unbiased policy gradient estimator of $J_{poppy}$? \n    * The method has no explicit objective/regularizer to maximize behavioral diversity, but instead implicitly assumes that this occurs through the \"argmax\" training in Algorithm 1. Is there a way to theoretically capture/analyze this \"implicit regularization\"? Currently it seems that the behavioral diversity isn't theoretically guaranteed, but rather occurs I suspect mainly if the beginning of training allows each agent to \"latch on\" to their own specific strategy.\n    * Algorithm 1 is written somewhat specifically for this particular case involving a shared encoder and multiple decoders. Can it be re-written as a general RL method? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cgKf4YfCy3W", "reviewer": "Reviewer_5SRy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper is in the line of works that uses reinforcement learning for combinatorial optimization (CO) problems. The main contribution is the idea of training a population of complementary agents for a given distribution of CO problems, with the objective function being optimizing the performance of the best agent instead of the average. The proposed training approach, POPPY, is evaluated on three benchmark tasks, including TSP, CVRP, and KP. It shows state-of-the-art performance on the TSP task. ", "summary_of_the_review": "The idea of training a diverse population of agents to solve CO problems is generally interesting, novel, and well-motivated. But it is not clear where diversity is encouraged, and the evaluation is not entirely convincing. ", "strength_and_weaknesses": "Strengths: \n1) Using RL for CO problems is an interesting topic and of practical importance. \n2) The idea of training a (diverse) population agents for CO problems is interesting and novel. \n3) The rationale behind POPPY is well-motivated with the discusison of the line of related works, as well as using the simple example in Figure 1.\n4) It shows considerable improvement over SOTA RL methods on the TSP benchmark task. \n\nWeaknesses:\n1) The empirical evaluation is not entirely convincing -- \n1a) The improvements over SOTA RL methods like POMO are generally small on all of the three tasks. POMO itself is already pretty close to optimal solution, so that the edge of POPPY is barely significant (it is unclear if the authors have done t-tests). The evaluation would be more convincing if the authors can show that POPPY has more significant improvements. \n1b) On the CVRP task, POPPY is outperformed by EAS. \n1c) The baselines are missing for the KP task, making it even more challenging to evaluate the performance of POPPY. \n\n2) There are many engineering heuristics to make the system work (e.g., when to freeze or unfreeze the encoder, whether or not the optimal solution depends on the starting point). Therefore, the overall performance may be fragile to the specific training architecture. Especially that the edge of POPPY seems to be small compared to the baselines, so that it is questionable whether these kind of improvements are due to engineering tricks or structured improvements due to maintaining a population of agents. Also, the results may be hard to reproduce.  \n\n3) It is unclear to me where the \"diversity\" in the population of agents lies in the objective function. It appears that POPPY is training a large set of agents with different policies, so that one of them \"happens\" to be good at a certain problem instance. As a fair comparison, perhaps you should separately train 16 POMO/LIH/EAS, and compare POPPY-16 with the best performance of those 16 policies. It is questionable whether POPPY can beat such a strong baseline. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KfLRSVlGfsw", "reviewer": "Reviewer_rpzd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes Poppy, an RL-based approach to learn a population of constructive heuristics for combinatorial optimization problems.   The presented architecture is based on the encoder-decoder Attention Model, with a shared encoder and one decoder per agent of the population. Starting from a pretrained model, Poppy training is based on a policy gradient that only depends on the performance of the best agent for each instance; and serves to only update that agent’s parameters. Poppy is evaluated on three well-known CO problems: the TSP, CVRP and KP. ", "summary_of_the_review": "I would vote for reject, because of the combination of:\n\n(i) The limited novelty, especially w.r.t [1]: since the population aspect has already been explored with a similar architecture for similar problems, the main novelty seems to be the loss -- although I encourage the authors to make a precise comparison and update their claims.\n\n(ii) The experimental evaluation is not convincing because, in my opinion, it shows marginal gains on tasks where learning-based methods have already achieved excellent results. Evaluation on more challenging problems/settings (e.g larger instances) would greatly increase the empirical value of this paper.\n\n", "strength_and_weaknesses": "**Strengths**\n1. The paper is clear and very well-written.\n1. The idea of using a population of agents is well motivated.\n1. The proposed loss that enables an effective diversity without explicitly guiding the specialization seems general enough and could be used in other contexts.\n1. Experimental evaluation shows strong results on the selected tasks.\n\n**Weaknesses**\n1. A very similar idea of training multiple decoders for the Attention Model was explored in MDAM [1] and applied to the TSP and CVRP:\n   * As far as I can see, the main contribution/difference of the present paper w.r.t MDAM is the different loss -- which considerably limits the novelty of the paper. \n   * Although the experimental results of the present paper seem stronger, this can also come from using POMO [2] training which is known to significantly improve the AM performance.\n   * Including a precise discussion of the differences w.r.t to MDAM and including it in the experiments baselines would be useful.\n\n1. The experimental evaluation focuses on datasets (synthetic TSP/CVRP instances with 100, 125 or 150 nodes and KP with 100 or 200 items) that do not seem challenging enough, today, for learning-based methods. Indeed:\n    * The reported optimality gap of existing learning-based methods is already very small: less than 0.01% for TSP100 and 0.2% for TSP150, and less than 0.005% for the KP. These are already very good to excellent for heuristics in general.\n    * In this context, even dividing the opt gap by 5 (as claimed in the abstract for TSP) does not seem very significant to me. This is especially visible in Table 3.\n    * The scale of these problems is quite small compared to what other learning-based methods are able to solve (e.g. [3] solves TSP instances with up to 10,000 nodes, with supervision only on small graphs)\n    * I would suggest to explore more challenging problems (e.g. larger sizes) to really showcase the experimental value of the proposed approach.\n \n1. I can see the interest of having a population of agents in Fig 3;  however, (again) the gains seem very small: \n    * in Fig 3 bottom left, we see that removing 1 agent from the population would lead to a deterioration of the opt gap of at most ~ 0.0004%. \n    * This raises the question of is it because the opt gap is already very small (cf previous point) or is it the influence of the individual agents that is not significant (i.e. how different are the agents). \n    * I wonder how, for example, taking the best of 4 samples x 4 agents would compare to greedily using 16 different agents. \n\n\n[1] Xin et al, Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems, AAAI 2021\n\n[2] Kwon et al, POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, Neurips 2020\n\n[3] Fu et al, Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances, AAAI 2021\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject