Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary: 
The 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. 


Comments:

The 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. 



review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: 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,

Overall, 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:

(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.

(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).  

(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.

(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.   

(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. 

(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. 

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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. 

Overall, 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. 

However, 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.

Minor comment:
- 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. 
- 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. 
review_title: Official Blind Review #2

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