Solving Packing Problems by Conditional Query Learning
Authors: Dongda Li
Changwei Ren
Zhaoquan Gu
Yuexuan Wang
Francis Lau
Venue:  (2020)
Keywords: Neural Combinatorial Optimization
Reinforcement Learning
Packing Problem

Abstract: Neural Combinatorial Optimization (NCO) has shown the potential to solve traditional NP-hard problems recently. Previous studies have shown that NCO outperforms heuristic algorithms in many combinatorial optimization problems such as the routing problems. However, it is less efficient for more complicated problems such as packing, one type of optimization problem that  faces mutual conditioned action space. In this paper, we propose a Conditional Query Learning (CQL) method to handle the packing problem for both 2D and 3D settings. By embedding previous actions as a conditional query to the attention model, we design a fully end-to-end model and train it for 2D and 3D packing via reinforcement learning respectively. Through extensive experiments, the results show that our method could achieve lower bin gap ratio and variance for both 2D and 3D packing. Our model improves 7.2% space utilization ratio compared with genetic algorithm for 3D packing (30 boxes case), and reduces more than 10% bin gap ratio in almost every case compared with extant learning approaches. In addition, our model shows great scalability to packing box number. Furthermore, we provide a general test environment of 2D and 3D packing for learning algorithms. All source code of the model and the test environment is released.

Under review as a conference paper at ICLR 2020
SOLVING PACKING PROBLEMS BY CONDITIONAL QUERY LEARNING
Dongda Li', Changwei Ren², Zhaoquan Gu', Yuexuan Wang', Francis C.M. Lau' 'Cyberspace Institute of Advanced Technology. Guangzhou University, Guangzhou, China ?College of Computer Science, Zhejiang University, Zhejiang. China
'Department of Computer Science, The University of Hong Kong, Hong Kong, China 1 lidongdaß gzhu. edu.. en, rcwê ju. aauuuddd. edu. en, zqguê edu. cn amywangez ju ju. edu. en, Eemlauêcs, hku.hk
ABSTRACT
Neural Combinatorial Optimization (NCO) has shown the potential to solve tradi- tional NP-hard problems recently. Previous studies have shown that NCO outper- forms heuristic algorithms in many combinatorial optimization problems such the routing problems. However, it is less efficient for more complicated problems such as packing, one type of optimization problem that faces mutual conditioned action space. In this paper, we propose Conditional Query Learning (CQL) method to handle the packing problem for both 2D and 3D settings. By embed- ding previous actions as conditional query to the attention model, we design a fully end-to-end model and train it for 2D and 3D packing via reinforcement learn- ing respectively. Through extensive experiments, the results show that our method could achieve lower bin gap ratio and variance for both 2D and 3D packing. Our model improves 7.2% space utilization ratio compared with genetic algorithm for 3D packing (30 boxes case), and reduces more than 10% bin gap ratio in almost every case compared with extant learning approaches. In addition, shows great scalability to packing box number. Furthermore, we provide a gen- eral test environment of 2D and 3D packing for learning algorithms. All source code of the model and the test environment is released.
model
INTRODUCTION
How to pack boxes with the smallest bin size? With the development of globalization and E- Commerce, this question becomes more and more important. Boxes are packed to various bins such as shipping container and boxcar. Many these boxes are made by paper or plastic; packing boxes in more efficient way can greatly reduce material cost shipping energy.
The Bin Packing Problem (BPP) is one of the classic integer combinatorial optimization problems and it has been extensively studied for decades (Wu et al. 2010). is shown that BPP is strongly NP-hard problem (Martello et al., 2000), which requires exponential time to generate the optimal solution. Some heuristic algorithms (Baltacioglu et al.) (2066) try obtain a nearly optimal solution within polynomial time, but these methods require explicit rules for every specific problem setting. When the setting changes even very slightly, the original method cannot work properly. On con- trast, the explicit or hand-crafted rules can be interpreted as policies by neural networks to make decisions. which are insensitive to problem settings. Neural networks have achieved great success in many domains, such as computer vision (Liu et al. 2017). natural language processing (Vaswani et al. 2017), speech recognition (Chan et al.J (016). etc. Inspired by these booming techniques, many studies (Bello et al., (0166) adopt the neural networks and the recent advances in artificial in- telligence to solve the classic combinatorial optimization problems, such as the Travelling Salesman Problem (TSP), the Vehicle Routing Problem (VRP), etc. Some latest works propose the pointer net- work /Vinyals et al. | 2015b) and utilize the attention mechanism with reinforcement learning Naazari et al.
2018 Kool et al. 2019) to solve the TSP and the routing problems respectively.
There are also some Staming-based attempts for the packing problem, which utilize reinforcement learning in the neural network model since the optimal solution is unknown beforehand. For exam-

---

Under review as a conference paper at ICLR 2020
ple, MTSL (Duan et al. the transitional greedy method to perform final positioning step. Laterre et al. (2018) enlighten by AlphaZero (Silver et al. 2017) adopt Monte Carlo Tree Search (MCTS) with self-competition rein- forcement learning to solve the packing problem, but it is restrained to pack boxes that have been preliminarily divided from bin. Cai al. (2019) simply
2019) separates selecting and rotating step by selected learning, and applies
reinforcement learning get some packing results, which serve as the initialization to accelerate the original heuristic algorithms.
However, these approaches either miss the connection between sub-actions or combine handicraft rules with a learning algorithm. Without the sub-action connection, the learning process becomes partial observable Markov Decision Process (MDP) (Sutton & Barto] 2018), which hard gen- eralize a good policy for the lack of information. Some methods generate all possible sub-action sequences at the same time, it still non-trivial for a neural network model to produce many mu- tual related outputs in single forward prorogation even though the setting of these methods are strict MDP. These methods combining handicraft rules are not only difficult achieve an optimal solution, but also sensitive to problem settings.
To the best of our knowledge, there is no end-to-end learning algorithm that solves standard pack- ing problems. In this paper, we propose Conditional Query Learning (CQL) model that directly addresses the gap between sub-actions. With the inner conditional query mechanism, the learning process becomes fully observable MDP, which makes the problem casier to apply the reinforcement learning. Compared with the model that outputs several sub-actions simultaneously, CQL model has smaller action space per forward step. Benefit from the small action space feature, can apply a simpler model to fit the policy, which work more efficiently. In addition, it would not sacrifice performance with the small action space. As a result, we do not require handicraft rules to feed the gaps between sub-actions since they are provided by conditional queries.
Specifically, the packing problem requires three mutual conditioned sub-actions: box selecting, ro- tating and positioning. To fill the gap between sub-actions, we adopt the CQL model as follows. First of all, the packing problem is formulated as an MDP to apply reinforcement learning. Then the previous sub-actions are embedded as a query to the next sub-action decoder. After all three sub-actions are generated, the environment performs one packing step and updates the observation. Finally, we adopt the actor-critic algorithm to update the model parameters.
We conduct extensive experiments to evaluate the models and the results show that the CQL model greatly outperforms the vanilla model which produces sub-actions in one step forward propagation without query. In addition, the CQL model achieves lower bin gap ratio in both 2D and 3D packing compared with extant learning approaches and heuristic algorithms. Specifically, proves 7.2% space utilization ratio in 3D packing (30 boxes) compared with genetic algorithm, and reduces more than 10% bin gap ratio in almost every case compared with the state-of-theeart learn- ing approaches. Furthermore, numerical results show that CQL greatly outperforms other methods when the scale of the problem increases. The learning carve and the variance of results also illustrate that CQL makes the training process more stable.
model im-
The contributions of this paper are summarized follows:
We propose the first end-to-end learning algorithm that solves the standard packing problem for both 2D and 3D settings;
We propose the conditional query learning (CQL) model to address the packing problem that has mutual conditioned multi-dimension actions;
We combine the conditional query learning with an attention mechanism to construct a new learning framework;
We conduct extensive experiments and the results show that our model outperforms both heuristic algorithms and the state-of-the-art learning-based models.
We also release our model implementation and 2D&3D packing environment for the community to test their algorithms.
The rest of the paper is organized as follows. We introduce related works in the next section. We introduce the preliminaries in Section Design of CQL model is presented in Section 4 We imple- ment CQL model and illustrate the comparison results in Section Finally, we conclude this paper in section G
2

---

Under review as a conference paper at ICLR 2020
2 RELATED WORKS
Getting an optimal solution of combinatorial optimization problems are computationally heavy, op- timal labeled data for supervised learning is expensive. Hence, when using Neural Networks (NNs) to solve these problems, one solution is to apply heuristic algorithm results as labeled data, but the performance of this approach cannot be better than the performance of the heuristic algorithm. The other solution is to apply reinforcement learning that makes the algorithm learn from its own expe- rience, which is possible to produce better results than existing algorithms. Here we focus on the reinforcement learning approaches and introduce some related works of reinforcement learning and neural combinatorial optimization.
2.1 SEQUENCE PROBLEM IN NEURAL COMBINATORIAL OPTIMIZATION
Enlighten by the recent success of Neural Networks (NNs), especially the fast progress sequence to sequence model, which is initially used in Neural Machine Translation (NMT) Bahddanau et al.,
2014 Vinyals et al., 2015a Luong et al. 2013 Vaswani al.] 2017: Shen al. 2018). Because many combinatorial optimization problems have similar input and output structure as NMT, many studies adopt NNs to solve sequential combinatorial optimization problems. |inyals et al. (2015b) propose Pointer Networks, which uses attention as pointer to select member of the input sequence as the output. Bello et al. (2016) and (Nazari et al. 2018) view TSP and VRP as MDP respectively, and they both apply policy gradient algorithm to train their models. Kool et al. (2019) further improve the result of routing problem using attention model (Vaswani et al. 2017
2.2 REINFORCEMEN LEARNING WITH PARAMETERIZED ACTION SPACE
Different from routing problems that only require one object selected from input sequence per step, the packing problem requires three sub- actions to pack a box into the bin. This kind of action space is called parameterized action space (Masson et al. 2016) reinforcement learning, which requires the agent to select multiple types of action every action step. HHausknecht & Stone (013) expand DDPG to parameterized action space and test on RoboCup soccer game, But this approach suffers from tanh saturation problem in continuous action space, so they apply inverse gradients trick to address it. Masson et al. (2016) introduce Q-PAMDP algorithm, which alternates learning action selection and parameter selection polices make the training process more stable, but the parameter policy have to output all the parameters for all discrete actions. The output size of the parameter policy can be explosion when the problem has large high dimensional parameters with large discrete actions. The authors of Wei et al.] (2018) propose a hierarchical approach, they condition the parameter policy on the output of discrete action policy, and they apply Variational Auto-Encoders (VAE) trick to make the model diffcrentiable.
However, all these researches only divide action to two parts, namely, a discrete action and set of actions as parameters that may include discrete or continuous actions. But the problems like packing contains several mutual conditioned actions that can not directly view as conventional parameterized action space problem, otherwise the number of outputs of the second model will be the product of the candidate output of each sub-actions, which makes the model has too many output options and is hard to generalize the problem and learn to produce good solution.
2.3 PACKING PROBLEM
As mentioned before, the packing problems are such problem that have mutually conditioned sub- actions, and there are some works trying to solve this problem by NCO. Enlighten by AlphaZero Sil- ver et al. (201)). Laterre et al. (0018) apply MCTS self play to search the better solution and learn how to pack, but their method only applies to the dataset which boxes are divided by random cuts from regular bin. Duan et al. (2019) propose a selected learning approach solving 3D flexible bin packing problem which balances sequence and orientation complexity. They adopt pointer networks with reinforcement learning to get the box selection and rotation results, and apply greedy algorithm to select the location of boxes, which is not end-to-end learning method and can not get better than greedy algorithm. More importantly, this hybrid method do not view the entire packing problem as one complete optimization process, so the learning process only tries to optimize part of problem. At the same time, different algorithms of sub-actions may have conflict goal in optimization process.
3

---

Under review as a conference paper at ICLR 2020
Different from previous methods, we simply embed the previous actions attention query for the model to reason the subsequent actions and after the full action step is finished, we perform one-step optimization along every sub-action model. In this way, we reduce the total output size to the sum of all sub-action candidate output, which makes the model smaller and easier to learn.
3 PRELIMINARIES
In this section, we introduce the Bin Packing Problem (BPP) and formulate it as MDP.
3.1 BIN PACKING PROBLEM
Bin packing problems are class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single bin as densely as possible or pack all objects using few bins as possible. For simplicity, have a number of boxes and we want to use minimal size of bin to pack all these boxes. Specifically, we have fixed bottom size rectangle (2D) or cube shape (3D) bin, and the object to minimize the final height of bin and achieve higher space utilization ratio. The problem is the strip packing problem with rotations (Christensen et al. 2017). which a subelass of BPPs, and we put the formal definition of this problem in Appendix 7.1 In the following sections, we elaborate our approach in the 3D BPP not specifically stated.
adopt the first goal, in which we
In respect of NCO, the packing procedure of each box can be divided into three sub-actions:
1. Selecting target box from all unpacked boxes.
2. Choosing the rotation of the selected box.
3. Outputting coordinates relative to the bin of the rotated box.
These three sub-actions are ordered and mutual conditioned, that is, to select rotation, choosing the box to be rotated should be done first, and each previous decision serves the following one. Each sub-action can not be viewed as independent optimization process, otherwise, there may be conflicts between optimization processes, resulting in sub-optimal and even some strange solutions.
3.2 FORMULATING PACKING PROBLEM AS MARKOV DECISION PROCESS
Since the packing problem is largely NP-hard, getting an optimal solution in acceptable time is not realistic, thus we have to view the problem an MDP and adopt reinforcement learning to make the agent learn from experience. In MDP, the probabilities given by p completely characterize the environment's dynamics. That is, the state of the environment must include information about all aspects of past egeettenvviromen interaction that make a difference for the future, and this kind of state is said have the Markov property.
To make the problem satisfy Markov property, we divide our model to encoder and decoder. The encoder state is 5 = {s1, $2, ..., sn), where s; (sp.i. It WA hi Fi, Vs. Vi)..) 21), and sp boolean variable that indicates whether the box is packed in the bin. (I, w;, ha) is box length, width and height, and (x,, W/; 2;) is the box left-front-oottom coordinate relative to the bin. From the perspec- tive of box packing step, giving is enough for MDP, however, if we divide the box packing step to the three sub-actions, then the rotating and positioning step is not strict MDP. The rotating step has to know which box is selected, and the positioning step has to know both the selected box and rotation from previous sub-actions. Therefore, we propose the attention encoder with dynamic state and conditional query decoder which is introduced in the next section. The detail of environment transition described in Appendix 7.2
4 CONDITIONAL QUERY LEARNING MODEL
In this section, introduce the CQL model. Our method adds conditional query to Multi-Hee Head Attention (MHA) (Vaswani et al. 2017) to make the model capable of solving mutual conditioned multi-dimensional optimization problems.
4

---

Under review as a conference paper at ICLR 2020
Sep oupua
Decocer
Deecder
Oucoodar
Just Auoe
Ereadar
Adl Parrs
ASd Hatn
AGS Taars
MILA
Insut Encodding
Enbradding
Stme
Frre
Obo
Obocc
Figure 1: Attention Encoder with Dynamic State for Boxes Case. Every previous packing step output leads to corresponding box state update and re-encodes the following step.
We divide this section into three parts, namely, encoder, decoder and training. We first show the dynamic state self-attention encoder model.
4.1 ATTENTION ENCODER WITH DYNAMIC STATE
As shown in Fig. [ adopt Transformer (Vaswani al. 2017) layers to encode input states. Different from Vaswani et al. 2017). the sequence of boxes are unordered packing problem, so remove the positional encoding in Vaswani et al. (2017). The input state of encoder contains box shape, box position, and the boolean variable that indicates whether the box has been packed. In addition, mask the box position in the input state if the box is not packed.
Unlike machine translation or routing problems which has fixed input feature in the procedure of inference, in packing problem, the rotation and coordinates of boxes updated immediately after one box has been packed, which makes the encoding embedding must update after every packing step, rather than keep fixed encoded hidden feature one training example.
To construct a strict MDP, we design the Attention Encoder with Dynamic State shown in Fig. [ where we first embed input state to fixed vectors and then feed it to layers Transformer
Table 1: box size update through rotation
Rotation
2 3
U. Ww J
1.w.h
I.h.w w.l.h w.h,1 h.l.w h.w.1
that contains Multi-Head Attention (MHA) layer and FeedForward (FF) layer. Each layer adds residual connection (He et al.) (0016) and batch normalization (Toffe & Szegedy 2015). We feed the embedded vector to conditional query decoder introduced later. The decoder chooses the packing box from unpacked boxes and the rotation, coordinates of the packing box. After finishing one step packing, we update the input state of encoder according the decoding result of last packing step, more specifically, set the packed state Sp.s to True and update the last packed box shape (4, w;, h.) according to the box rotation as shown in Table [ and replace the masked position with the packed box location (I,, Vi, 2)) as shown in Fig.
4.2 CONDITIONAL QUERY DECODER
After encoding the input state to an embedded vector for each box, we design the conditional query mechanism to handle the connection between sub-actions without greatly increasing the complexity of the model. As shown Fig. for packing problem, the model performs three sub-actions separately, namely, boxes selection, rotation and location for the selected box.
the box selection step, we first feed the dynamic input state to the encoder and get N hidden vectors H = (h,, lo,, lo,, fn)) as described before. Then we feed it to the selection decoder. In this step, all information from encoder is required, so we use self-attention followed by select head, which consists of several linear layers with N final outputs. To avoid the situation that boxes which have already been packed are selected, we mask the packed boxes on selection output and then perform sampling.
5

---

Under review as a conference paper at ICLR 2020
Araku
Headyr
Heady
Feelup
Herly
Head
Heealu
Heall
How
Dala
Sehuka
Sdian
Aicwnnkr
Al
AFcrookr
poe I saw
Iopi tabroking
how Inabciidia
bast Enbolling
Ies, I
Iex
bac
bio
Deu
BACk
Pile
dkyp poutie
daye
Jape
puidis
Selection step
Rosation stap
Location stap
Figure 2: Conditional Query Process. The figure demonstrates the condition query process when packing box i, which embed previous sub-action results as conditional query for current decoder.
In the rotation step. we construct a conditional query vector by picking up the selected box shape information from the input state and embedding it by linear layer. Besides, after choosing the box to pack, the model has to know the boxes which have been put into the bin, so we mask out the attention vector of unpacked boxes shown in Eq. [ in scaled dot-product attention 3 of the decoder. At last, we feed the decoder output hg to rotation head to produce rotation result (2 options for 2D and 6 options for 3D). Where the W K and WV are trainable parameters, k and t are key and value vector in attention model, and the q the embedded query vector.
k = W his U; = WV h4
(1)
$p.5 True
a
Vil
(2)
Sp.1 False
hg sof softmar(a.));
(3)
In the final step, the model calculates the position of the selected box relative to the bin. To comprise all previous results, the query have to combine rotation of selected box, and we do this by following rules in Table Then it is embedded and fed to the masked MHA. The model may generate coordi- nates outside the bin, and a fixed bound can not make sure all the boxes do not exceed the bin since the box sizes different. We bound the packing box coordinates according to the bin width and length after every packing step by moving the boxes outside the bin to the border of the bin.
Throughout the entire forward pass of packing one box, the data stream passes through the encoder and each decoder once. The target query is extracted from the input state based on the previous outputs. By conditional query, the model receives the information from hidden vectors of encoder as well as previous sub-action outputs, which ensures every sub-action decoding step is strict MDP.
4.3 TRAINING
As mentioned earlier, we view the packing process as a MDP and apply reinforcement learning, specifically, the actor-critic algorithm (Konda & Tsitsiklis 2000). The model we presented earlier is the actor model.
4.3.1
CRITIC NETWORK
The critic network consists of self-attention layers followed by value head. The input of critic is the dynamic state The graph embedding H hh.ttt of the last self-attention layer is fed to value head that contains several linear layers, where H is the mean of last hidden vectors of the last attention layer. To make the train process mare stable and easy to tune, we separate the actor network and critic network, that is, the networks do not share parameters.

---

Under review as a conference paper at ICLR 2020
4.3.2 VALUE FUNCTION ESTIMATION
In the actor-critic algorithm, to accurately estimate the advantages (A,) which have significant impact on optimization performance, a popular technique is learning the state value function V(s) and performing bootstraps to get low variance advantage estimations. However, using only one step bootstrap introduces too much value estimation error. Schulman et al. (2015b) propose the Gener- alized Advantage Estimation (GAE), which combines n-step bootstrap produce more accurate advantage. The GAE balances the bias and variance to achieve stable and accurate advantage esti- mation. As shown in Eq. 4 where t is the time index in [0,T]. with T-steps trajectory segment, and À is the hyper-parameter that adjust the trade-off between bias and variance.
A. -5 + (TA)6E+1 + + (72) DT-1,
(4)
where de =r + 7VV (8,)
4.3.3 REWARD FUNCTION
Unlike supervised learning, the agent in reinforcement learning studies from experience and tries to find the policy that gets more accumulated rewards. Therefore, how design the reward signal is a crucial factor for learning process. In the single bin packing problem, the goal is to minimize the height of the bin with given width and length. The most straightforward way is to adopt the negative change of bin height -Ah = h; hat1 as the reward signal in every packing step. However, this leads to sparse reward which is one of the biggest challenges (Andrychowicz et al. 2017) in reinforcement learning.
9: WLH, Σ (wylhhy)
(5)
r= Ag 9:-1 9:
To address the sparse reward problem, we design the reward signal based on the change of the current volume gap of the bin. As shown in Eq. [ the volume gap 9i of packing step is defined as current bin volume minus the total volume of packed boxes. Where the W, T., H is the width, length and height of the bin, respectively. The reward of packing step is defined Agi then the accumulated reward becomes the final gap of bin, which linear to the negative final bin height -II, as formulated in Eq. 6 By doing this, the agent always gets meaningful reward signal no matter the total bin height increase in that packing step.
R
Σ i=1
rs (0 91) (91 922 (9n-1 9n)
(6)
In = LH +
(wylyhg)
4.3.4 TRAINING PROCESS
In every training step, the critic network gets the dynamic state input to estimate the state value, and the actor network performs the three steps described before to get each sub-action output. Thereafter, one-step parameter update is performed for both actor and critic networks. Because our training data is randomly generated and is inexpensive, it is better to on-policy reinforcement learning which does not has the sample inefficient problem that is shown in off-policy methods (Schulman et al., 2015a).
L = L, + L. + BLent
(7a)
La, A, * Σ log(TTe, (8, + (8, (r)) + To (8, up)]
(7b)
aEA
L. MSE(Vo, (st), A, + (s:))
(7c)
Lent Σ
(mo, )
(7d)
AEA

---

Under review as a conference paper at ICLR 2020
The Eq. formulates the loss function calculation process, which includes actor, critic and entropy loss functions. The policy consists of three sub-action policies as shown in Eq. 7b] The actor loss is the advantage multiply policy gradient that encourage the action which achieves higher accumulate rewards. The critic network is trained through MSE loss 7c In addition, we add the negative entropy 7 item to loss to avoid the policy is too deterministic and encourage exploration.
Algorithm 1 Conditional Query Learning
1: Input Random produce N training set X
2: Initialize actor and critic network parameters 8,
3: for in (I.....N} do
Randomly sample a batch from 5: Make state a s8s,, I, w. h, I. y,
6: for j in O, nt/Ngac do
// is the the number of boxes
7:
for k in 0, Rgae do
// Getting mini-batch for GAE
Get Vo. (Sjongaett))
// Critic network for value
= {h1, h2....in) atto, (Sjangae -k)
// Encoder
10:
Sample box index from Ti,
// Selecting step
11:
Sample box rotation from To. [H (r.))
// Rotating step
12:
Update li w/, /t, via Table
// Update query based on rotation
Sample position æ, y from Ta, 9p.1)
Positioning step
14:
Update state and get reward end for
// D Dynamic state update
15:
16:
Calculate advantages by Eq. Calculate loss by Eq.
// GAB
0 +- atg ACa & e a. AC.
19:
end for
20:
end for
21:
Output 0.6
As shown in Alg. after initialization, the algorithm gets Sgge-SStp experiences for GAE. In every packing step, the encoder embeds input state to dmodet hidden vectors H, and the model gets packing box index, rotation, and position by conditional query process in the decoder (line 10~line 12). After finished one step packing, the input state and rewards are updated correspondingly.
5 EXPERIMENTS
We evaluate the CQL model 2D and 3D bin packing problems with different packing box numbers and compare the results with heuristic algorithms and learning methods.
5.1 PACKING ENVIRONMENT AND DATASET
We design the environment for 2D and 3D bin packing problems. Here we only describe the 3D condition that can be casily reduced to 2D. In our test environment, N boxes are initialized by random width, length and depth for packing. The bin is initialized by fixed width and length, specif- ically, from -1 to 1. The agent has to find solution sequence S(s, o, Z, y) that uses minimal bin depth and does not have any overlap boxes. The final result is assessed by the accumulated reward which is linear negative bin height. The environment is designed for reinforcement learning, and we also encourage others to test their algorithms on it.
To fully evaluate the learning model, the test dataset should be hard enough for packing, that is, the variance box size should not be too large or too small. When the variance is too large, some large boxes will dominate the bin, then other small boxes more likely packed below large boxes, which makes the position of small boxes has little impact on the total bin height. When the variance is too small, the boxes are similar to cubes. which makes the problem too easy to solve. Therefore, we choose the dataset with the box sizes sampled from [0.02, 0.4] for 2D and [0.2, 0.8) for 3D after few tests.
8

---

Under review as a conference paper at ICLR 2020
5.2 IMPLEMENTATION DETAILS
Both actor and critic networks of our model have two self- attention layers. The box selection decoder has one self-attention layer, and both the box rotation and location decoder have one conditional query attention layer. Each attention layer applies batch normalization. We set the attention hidden dim as 64 both in 2D and 3D cases. Every decoder head has three linear layers with Relu (Nair & Hinton 20TO) activation function. The decoder calculates the probability distribution for each sub- actions. The box selection, rotation and position head generate N box selection choices, rotation choices, and 128 position discrete choices for each axis, respectively. The linear decay learning rate scheduler is applied with Adam (Kingma & Ba 2014) optimizer and 5e-5, 3e-4 initial learning rate for actor and critic, respectively. We train model training for 20 boxes cases. The Pytorch (Paszke et al. 2017) implementation of the CQL model is also open sourced.
single Tesla V100 GPU. It takes 2~33 days
5.3 RESULTS
We evaluate the model on various number packing boxes, specifically, 10 boxes, 16 boxes, 20 boxes and 30 boxes.
Baselines: The Multi-Task Selected learning (MTSL) (Duan al. 2019) model, which initially designed for minimize the surface area of bin, and the authors adopt reinforcement learning for box selecting step, supervised learning for rotation step and greedy method that minimizes bin surface usage for position step. For comparison purpose, we implement their model but set the reward function same as ours, specifically, the delta gap reward and set the positioning step model similar to their rotation step model, which is the attention from encoder and previous decoder steps. To verify the effectiveness of our conditional query mechanism, we remove the conditional query of model and get the box rotation and position from the box selection decoder. Besides, also test the rollout baseline with REINFORCE (Williams) 1992) algorithm proposed on Kool et al. (2019) computationally efficient.. Furthermore, the Genetic Algorithm (GÅ)
which they claimed is proposed on Wu et al. 2010) is tested in 3D BPP.
We evaluate previous mentioned algorithms by the bin gap ratio = Σ wilkh WLH.,, which is positively related to the final bin height. The variance of bin gap ratio is also evaluated to show the stability of learning algorithms. than 0%. Depending on the dataset and box number, the optimal gap ratio is different. In general, the more boxes are required to pack, the more likely gaps are filled, and filling the gaps in 3D condition even more difficult.
Metrics:
is worth noting that the optimal gap ratio of is greater
BIN10
BIN16
BIN20
BIN30
Model
Avg
Var
Avg
Var
Avg
Var
Avg
Var
Rollout
38.8%
0.0069
35.5%
0.0056
30.5%
0.0036
32.3%
0.0028
2D
No query
40.6%
0.0077
29.3%
0.0024
31.6%
0.0037
28.3%
0.0015
CQL
16.7%
0.0030
15.7%
0.0017
15.4%
0.0010
14.3%
0.0007
MTSL
50.2%
0.0097
45.3%
0.0065
42.6%
0.0054
40.6%
0.0037
Rollout
32.9%
0.0158
43.2%
0.0074
43.6%
0.0067
49.0%
0.0040
3D
No query
46.5%
0.0140
41.2%
0.0069
38.3%
0.0051
36.3%
0.0032
GA
27.2%
0.0056
31.5%
0.0030
33.9%
0.0030
37.4%
0.0023
CQL
27.4%
0.0126
30.6%
0.0087
32.4%
0.0046
30.2%
0.0028
Table 2: The gap ratio of conditional query learning (CQL) and baselines
Table 2 shows the bin gap ratios and its variances on 512 test instances after 100 epochs training for learning algorithm. We use the default settings for genetic algorithm. The results show that our CQL model achieves low bin gap ratio and variance in most cases. It is clear that the model with conditional query mechanism is better than no query model, which justifies that the CQL fills the gap between sub-action and makes the learning algorithm has the ability to reason following sub-action according the embedded previous outputs. Meanwhile, The rollout baseline with REINFORCE produces similar results query model but with higher variance. Because the rollout method

---

Under review as a conference paper at ICLR 2020
sums up all reward signal in every packing steps as the action value, its learning process treat every packing step equally and back propagate gradients for all steps no matter the step is good or bad.
The overall gap ratio and variance of CQL decrease the packing box number increases, which shows that the CQL model is scalable to problem size. Notice that in 10 boxes case of 3DBPP, the genetic algorithm achieve little bit lower gap ratio than the CQL model, we analyze the results and find that the optimal solution small packing box number tend to tile the bottom of bin, which is easy for heuristic algorithm find good solutions. But when the box number goes larger, heuristic algorithms tends to drop into local optimum since they are more greedy and difficult to generalize the entire solution space. Besides, the genetic algorithm has relative lower variance compare with learning approaches because it use some fixed rules that result in similar solutions for different examples, which leads to low performance for specific instances. The end to end MTSI. learning process shows poor results, because the model is not only partially observable MDP, but also suffers from sparse rewards due to the utilization of rollout method.
height 0.507
twight: 1,000
gap 0.102
gap. Sze: 0.289
(Mp_ratio: 0.141
(a) 2D-BIN20
(b) 2D-BIN30
(c) 3D-BIN20
(d) 3D-BIN30
Figure 4: The Packing Results of CQL. It is worth to note that the goal is to minimize the final bin height. Whether the boxes are close to each other does not affect the final height in many cases, so the results do not show very neat arrangement but already achieve near optimal bin height.
From the learning carve of training process shown in Fig. 3 the CQL model also shows superior stability than other learning algorithm, which leads lower variance as shown in Table 2 The learning carve of no query model is oscillating since the sampled result of earlier step do not pass to the later one. That is, the model can only estimate the solution that over- all good but not fit the specific example. The learn- ing carve of rollout method shows big jumping up in the beginning of training process because of the sud- den baseline update after the first epoch. In contrast, the CQL model benefits from conditional query struct a strict MDP and has meaningful reward signals from every box packing step, so shows smooth vergence process.
80a
0.5
33-31420
MTS
42
82 100
Figure 3: Learning carve of different models.
CONCLUSION AND FUTURE WORKS
In this paper, we propose the conditional query learning (CQL) model solve packing problems. Benefit from the conditional query mechanism, the CQL model is capable of generalizing the prob- lem that has mutual conditioned actions with relatively simple structure. Numerical results show that the conditional query learning greatly reduces the bin gap ratio both in 2D and 3D packing settings.
We excited about the future of the conditional query model and can apply it to other multi- dimension and parameterized action space problems. We can also extend the model with dynamic attention span and continuous action space further improve its scalability. In addition, the current test environment does not consider the physical gravity of boxes and the boxes are not packed close each other, will add these restrictions make it suitable for more practical bin packing.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Picter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In Advances in Neural Information Processing Systems, pp. 5048-5058, 2017.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473: 2014.
Erhan Baltacioglu, James T Moore, and Raymond R Hill Jr. The distributor's three-dimensional pallet-packing problem: a human intelligence- based heuristic approach. International Journal of Operational Research, 1(3):249-22) 266, 2006.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1rXxv:6611.0990 2016.
Qingpeng Cai, Will Hang. Azalia Mirhoseini, George Tucker, Jingtao Wang, and Wei Wei. Rein- forcement learning driven heuristic optimization. arXiv preprint arXiv:1906.0666 06639, 2019.
William Chan, Navdeep Jaitly, Quoc Le, and Oriol Vinyals. Listen, attend and spell: A neural network for large vocabulary conversational speech recogmition. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4960 4964. IEEE, 2016.
Henrik I Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24: 63-79, 2017.
Lu Duan, Haoyuan Hu, Yu Qian, Yu Gong, Xiaodong Zhang, Jiangwen Wei, and Yinghui Xu. A multi-task selected learning approach for solving 3d flexible bin packing problem. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1386-
1394. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Matthew Hausknecht and Peter Stone. Deep reinforcement learning in parameterized action space. arXiv preprint arXiv: 1t11:1511..4433 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03166 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.69880 2014.
Vijay Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances neural information processing systems, pp. 1008-1014, 2000.
Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019. URL httlttts//pppeeeiieee
net/ fttt/Eorum?icce wtw.uummmii-yylll dyrBB SEAEEEERRRRR SRYYm
Alexandre Laterre, Yunguan Fu, Mohamed Khalil Jabri, Alain-Sam Cohen, David Kas, Karl Ha- jjar, Torbjor S Dahl, Amine Kerkeni, and Karim Beguir. Ranked reward: Enabling self-play reinforcement learning for combinatorial optimization. arXiv preprint arXiv:1807.01677 2018.
Weibo Liu, Zidong Wang, Xiaohui Liu, Nianyin Zeng, Yurong Liu, and Fuad E Alsaadi. A survey of deep neural network architectures and their applications. Neurocomputing. 234:11-24 2017.
Thang Luong, Hicu Pham, and Christopher D Manning. Effective approaches to attention based neural machine translation. In Proceedings of the 2015 Conference Empirical Methods in Natural Language Processing, pp. 1412-1421, 2015.
Silvano Martello, David Pisinger, and Daniele Vigo. The three-dimensional bin packing problem. Operations research, 48(2):256-267, 2000.
11

---

Under review as a conference paper at ICLR 2020
Warwick Masson, Pravesh Ranchod, and George Konidaris. Reinforcement learning with parame- terized actions. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-1O), pp. 807-814, 2010.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems, pp. 9839-9849, 2018.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint
154.::5500002438, 2015b.
Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, and Chengqi Zhang. Bi-directional block self- attention for fast and memory-efficient sequence modeling. In International Conference on Learn ing Representations, 2018. htt.tttps:/// http:::::////peevvvieee
www.neee/eeoee Pofoormmiddiii.. cW
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self- self-play with general reinforcement learning algorithm. arXiv preprint 1xXiv:1712.088/11 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence sequence for sets. arXiv preprint arXiv:/51 2015a.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015b.
Ermo Wei, Drew Wicke, and Sean Luke. Hierarchical approaches for reinforcement learning in parameterized action space. In 2018 AAAI Spring Symposium Series, 2018.
Ronald J Williams. Simple statistical crradient-followiin algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-22 256, 1992.
Yong Wu, Wenkai Li, Mark Goh, and Robert de Souza. Three-dimensional bin packing problem with variable bin height. European journal of operational research, 202(2):347-355, 2010.
12

---

Under review as a conference paper at ICLR 2020
7 APPENDIX
7.1 PACKING PROBLEM
Now we formally define the packing problem with notations in Wu et al. (2010).
(4i, wi, h:): parameters indicating the length, width, and height of box i.
(I, W, H): length, width and height of the bin to be loaded, where H indicates that the bin height can be adjusted.
(I), Vi. 2:): coordinates of box i's www---otttomeiiidd corner.
X1,; Zi, Ym.: Zn,: binary variables indicating the orientation of box i, where X,, Z, indicate whether the length direction of box i is parallel to the bin's X and Z axes, and Y Zh, defines the width direction is parallel to the Y axis, or the height direction is parallel to the 2 axis respec- tively. For 3D view, there are six kind of orientation for box.
aij, bij, ci.; binary variables defining the relative placement of box i to carton j: variables will be 1 if box i is front of, to the right of, on top of box j. respectively; otherwise, 0.
M: a large enough number.
The objective is to minimize the variable bin height H. that is min H
subject the following set of constraints:
Iy + L,X1, + w. (Zi YYu, + En.) + h1111 - X1, - Z1, + Yuu
- -n.))
<= Iz + M(1 0iz);
i
(8a)
y/ + wiY Yw: + 1111 X1,- Zi,) + (X1; + +Z, - .Yw)) <= yj + M(1 biz);
(8b)
+ hn + w1 - Zzi Zn,,) + -111,
<= 2j + M(1 cis),
i
(8c)
04 1,11 + wi( (Z) Yuu Zn.)) h1 X1, Z1 + Yu: Zn. <= L
(9a)
y/ + 1. Yw, + 1111 - X1, - 21.) + h/4 (X1, + Zz, Yw.) <= W
(9b)
+ h: ZrZnn + w (1- Zı. Zn,) + 4.4, <= H
(9c)
an 1,0 + bij + + +o
i
(10)
X1, + Z1, <=
(Iaa
Z1 + Z2, <=
(1lb)
Z1, Yu, Zh, <=
(11c)
7,, Yn, + 7h, >= 0
(11d)
1 X1, Z, Yu,- Zh; <=
(1le)
1 - X1, Z₁, + Y,, Zh, >= 0
(11f)
X1, + 7, Y,; <=
(1lg)
X1, + 2, Y >= 0
(1th)
Constraints&Bensure that any two boxes i and do not overlap with each other. Constraints 9 keep all
boxes with the bin dimension. X1,- Zi, Yu; and Zn,, are used to calculate the respective mappings of box length, width and height the corresponding bin's 's X, Y and Z axes. Constraints 10 limits the relative position of any two boxes i and j. Constraints IT ensure that binary variables which determine the box position properly controlled to reflect practical positions.
13

---

Under review as a conference paper at ICLR 2020
7.2 PACKING PROBLEM ENVIRONMENT DETAIL
In packing problem environment, the model only needs to generate index, rotation and the horizontal coordinate of packing box in every packing step. That means that the environment auto- matically drops the box the lowest available position in the bin.
2 maar(2) (2b hb)
(12)
where box satisfies:
3i < Th + wb
Th J; + w
(13)
1/4 < y6 + lb
y/ y1 4
To avoid the model generates the positions outside of the bin, the environment forces the cross- border boxes to bin border.
2; min W we)
(14)
min yi)
7.3 EXTEND RESULTS
Here, we illustrate the experiment results of 2D, 3D bin packing problem with different box numbers by showing the placement of boxes of different algorithms. Fig. and Fig. 6 illustrate the results of 2D and 3D of CQL model in various packing box numbers. Obviously, when the number of the boxes increases, the boxes are placed denser and the gap ratio is become lower. Fig. 7 and Fig. show the results of different algorithms of 2D & 3D BPP in 20 boxes case. It is clear that our algorithm performs better than others.
twight: 0.513
height:
height 0.500
s.e: 0.123
wlz. 0.106
dize: 0.106
skoe. 0,200 sep. ratlo 0.141
gAoLralio: 0.197 0.197
gap roloraaooooom 0.117
pap_raliio 0.102
(a) 2D-BIN10
(b) 4D-BIN16
(c) 2D-BIN20
(d) 2D-BIN30
Figure 5: The Packing Results of CQL different cases of 2D BPP.
(a) 3D-BINI0
(b) 3D-BIN16
(c) 3D-BIN20
(d) 3D-BIN30
Figure 6: The Packing Results of CQL in different cases of 3D BPP.
14

---

Under review as a conference paper at ICLR 2020
height sep 0.108
height:0.502
height:
(a) 2D-CQL.
(b) 2D-Rollout
(c) 2D-No-Query
Figure 7: The Packing Results of 2D BPP with different algorithms in the case of 20 boxes.
(a) 3D-CQL
(b) 3D-Rollut
(c) 3D-No-Query
(d) 3D-MTSL
Figure 8: The Packing Results of 3D BPP with different algorithms in the case of 20 boxes.
15


Reviews:
[{"review_id": "r1eDbB6-qr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe paper proposes heuristics to solve the bin packing problems based on reinforcement learning with deep neural networks. With a new heuristics of conditional queries, the proposed method works favorably with the previous RL-based approach and other baselines. \n\n\nComments:\n\nThe idea of applying reinforcement learning to combinatorial optimization itself is not new. The authors, on the other hand, propose new heuristics, called conditional queries, which divides a unit of actions (rotation, box, and etc.), which turns out to be effective compared to the previous reinforcement-learning based method. \n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgv7YQcYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims at solving geometric bin packing (2D or 3D) problems using a deep reinforcement learning framework. Namely, the framework is based on the actor-critic paradigm, and uses a conditional query learning model for performing composite actions (selections, rotations) in geometric bin packing. Experiments are performed on several instances of 2D-BPP and 3D-BPP,\n\nOverall, bin packing problems are challenging tasks for DRL, and I would encourage the authors to pursue this research topic. Unfortunately, I believe that the current manuscript is at a too early stage for being accepted at ICLR, due to the following reasons:\n\n(a) The paper is littered with spelling/grammar mistakes (just take the second sentence: “With the developing” -> “development”). For the next versions of the manuscript, I would recommend using a spell/grammar checker.\n\n(b) In the related work section, very little is said about Bin Packing Problems. There are various classes of BPPs, and it would be relevant to briefly present them. Moreover, BPPs have been extensively studied in theoretical computer science, with various approximation results. Again, a brief discussion about those results would be relevant. Notably, several classes of geometric bin packing problems admit polynomial-time approximation algorithms (for extended surveys about this topic, see e.g.  Arindam Khan’s Ph.D. thesis 2015; Christensen et. al. Computer Science Review 2017).  \n\n(c) According to the problem formulation and the experiments, it seems that the authors are studying a restricted subclass of 2D/3D bin packing problems: there is only “one” bin, so (it seems that) the authors are dealing with geometric knapsack problems (with rotations). Note that the 2D Knapsack problem with rotations admits a 3/2 + \\epsilon - approximation algorithm (Galvez et. al., FOCS 2017). A. Khan has also found approximation algorithms for the 3D Knapsack problem with rotations. So, even if those results do not preclude the use of sophisticated DRL techniques for solving geometric knapsack problems, it would be legitimate to empirically compare these techniques with the polytime asymptotic approximation algorithms already found in the literature.\n\n(d) The problem formulation is very unclear. Namely, the state representation is ambiguous: $s_p$ is obviously not a boolean variable, but a boolean vector (where each component is associated with an item). Nothing is said about actions and transitions and rewards (we have to read the AC framework in order to get a clue of these components). We don’t know if it is an episodic MDP (which is usually the case in DRL approaches to combinatorial optimization tasks). Also, it seems that the MDP is specified for a single instance of 3D-BPP. But this looks wrong since it should include the distribution of all instances of 3D-BPP.   \n\n(e) The Actor-Critic framework, coupled with a conditional query learning algorithm, is unfortunately unintelligible due to the fact that many notations are left unspecified. For example, in Eq (1) what are the dimensions K and V? In Eq (2) what is d_i? In the algorithm what is n_{gae}? Also in the algorithm, what are l’_i, w’_i and h’_i? Etc. \n\n(f) Even if the aforementioned issues are fixed, it seems that the framework is using many hyper-parameters (\\gamma, \\beta, \\alpha_t, etc.) which are left unspecified. Under such circumstances, it is quite impossible to reproduce experiments. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1xTSLjtuS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an end-to-end deep reinforcement learning-based algorithm for the 2D and 3D bin packing problems. Its main contribution is conditional query learning (CQL) which allows effective decision over mutually conditioned action spaces through policy expressed as a sequence of conditional distributions. Efficient neural architectures for modeling of such a policy is proposed. Experiments validate the effectiveness of the algorithm through comparisons with genetic algorithm and vanilla RL baselines. \n\nOverall, the paper provides a solid contribution by proposing a new RL-based algorithm for the bin packing problem. In particular, the dense reward design for the MDP is quite interesting. I also think solving the 2D and 3D bin packing problem via RL is already quite valuable as an application. \n\nHowever, I do not think the proposed method is novel enough. Most importantly, I perceive the concept of conditional query learning indifferent from the autoregressive modeling of the policy (with conditionally masked inputs). Although the authors divide the processing of each bin into three steps of MDP (not strictly), the steps can be merged into one without any change in the environment. Since other parts of the algorithm also come from the existing literature (except the reward design), I think this point is crucial for the paper to be published at the conference.\n\nMinor comment:\n- I think the genetic algorithm described in the experiments should be equipped with more details, i.e., the type of processor used and elapsed time. \n- In table 2, I think bold numbers for the lowest variance of performance is very confusing since it does not necessarily mean a better algorithm. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an end-to-end deep reinforcement learning-based algorithm for the 2D and 3D bin packing problems. Its main contribution is conditional query learning (CQL) which allows effective decision over mutually conditioned action spaces through policy expressed as a sequence of conditional distributions. Efficient neural architectures for modeling of such a policy is proposed. Experiments validate the effectiveness of the algorithm through comparisons with genetic algorithm and vanilla RL baselines.

The presentation is clear and the results are interesting, but the novelty seems insufficient for ICLR. The proposed model is based on transformer with the following changes:
* encoder: position embedding is removed, state embedding is added to the multi-head attention layer and feed forward layer of the original transformer encoder;
* decoder: three decoders one for the three steps, namely selection, rotation and location.
* training: actor-critic algorithm
Decision: Reject