Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work proposes a tree-based learning method for online 3D packing problem. Packing configuration tree nodes is constructed using heuristic-based tree expansion, which acts as the action space of deep reinforcement learning. The tree search schema is interesting, but this work still has lots of space to improve in terms of its methodology and experiments.
main_review: It is important to handle Large scale packing problem with continuous action space. The authors expand the tree by using methods of heuristics, which reduces the action space to limited number of leaf nodes (actions). Then reinforcement learning is incorporated to optimize packing efficiency. As a result, the method reduces the size of action space which leads to better learning results.

However, there are some suggestions to improve the paper:
1. The method reduces the action space to discrete nodes via heuristic search, while after heuristic search, the packing action space is not fully covered because the heuristics only select part of action space. In fact, It is a trend-off between complexity and optimality. In addition, the complexity of the tree search will grow exponentially when lots of items have to be packed, which threaten the scalability of the proposed method. Worse, a large number of leaf node would makes the attention network computationally heavy since it is quadratic related to the number of nodes.
2. After determine the candidate points, the original heuristics select the placement point of new item by its own heuristic rules. Here, the authors replace the heuristic candidate points selection with DRL. But they do not compare with recent heuristics to show whether the DRL is indeed superior than these heuristic rules.
3. The dataset is too naive, which only discretizes each edge to 10, while conventional methods have much more resolution. In their continuous setting, their results degrade, but there is no explanation about this. The authors claim that the method works on continuous solution space, but they do not define the continuous solution space. Clearly, it is different from the continuous action space in reinforcement learning. In fact, the method works on discrete action space.
4. I think Section 4.4 should be modified. The distribution of adding a uniform random disturbance to each point of another uniform distribution is almost uniform. This is not the proper way to evaluate generalization.

There are some specific points: 
1. The author did not mention how many bins are used in the problem settings, which should be clearly state.
2. In the second paragraph of introduction, the authors said online packing ‘imposes additional constraints and difficulty’. but it is clear that offline packing is more complex than the its online variety since it includes the item selection step before the ‘online packing’ step. In the next sentence, the authors said ‘Learning-based approaches usually perform better than heuristic methods, especially under various complicated constraints’. Why Learning-based approaches perform better under various complicated constraints?
3. In equation 1, the right side use a capital S，I didn’t understand this, should this be a lowercase s? 
4. In the first paragraph of page 3,  ‘The flaw of their work is the heightmap (frontier) state representation like Zhang et al. (2021) is still used, while the underlying interactions that exist in packed items are missed’. what does the ‘underlying interactions’ mean?
5. In Section 3.1, the authors use \pi(L_t|L_t,n_t) to denote policy, but the policy is \pi(a|s) in RL. Therefore, people may be confused between the state and action when reading. This notion is very misleading. The same problem exists in the following text.

summary_of_the_review: The paper has studies an interesting problem but it still has lots of space to improve.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the problem of online 3D bin packing where the order of objects is out of the model's control and it must make placement decisions one object at a time. Training is framed as a deep RL problem closely following recent work [Zhao et al]. The main contribution is a rethinking of the state and action space which yields much better performance. Prior work trained models to predict placement in a voxelized grid that led to a large action space that could not scale well. Instead, this work represents existing objects and potential placement locations as nodes in a tree which are processed with a graph network. Given a new object, placement nodes can be heuristically instantiated to cover valid locations, and the model uses attention to output a distribution over these nodes and determine the object placement.
main_review: Strengths:

- structuring the state and action space in the proposed manner has many clear advantages over previous methods. This is demonstrated in quantitative comparisons and in the model's capacity to handle continuous spaces. Intuitively there are properties of a tree-based representation and the attention-based action space that would lend themselves better to learning.
- in the ablations in Table 5 we see that when introducing additional constraints the proposed method outperforms Zhao et al both in utilitzing space and meeting the additional task objective of the target constraint
- overall the paper is written clearly (a couple confusing spots here and there) but the overall organization is good and I think appropriate choices are made as to what details to leave in the appendices

Weaknesses:

There are some additional insights that would perhaps offer a clearer picture of what this model is learning to do and which parts of the proposed approach are necessary to do well in this problem setting:
- it might be nice to have some qualitative understanding of the learned leaf selection process. What behavior does the trained policy exhibit? Does the distribution over available leaves show clear preference for certain locations or is it somewhat uniform over possible options?
- The random baseline as described in Table 1 seems somewhat weak, for example, how does a random policy perform given the available leaves to choose from in the PCT & EV baseline?
- we see in Table 2 that removing the internal node set B altogether drops performance, but not too much. Are there simple alternatives to the state representation provided by processing a graph network over the nodes of B that might have performed just as well? Would there be any scaling issues when processing B with a large number of nodes?

I was confused about section 4.4, what exactly is being changed here? There is some set of items I and you are changing the probability of sampling a given object in that set? From Table 4 it doesn't seem like this is a particularly different setting that the model might have any difficulty with, the scores are the same across the board. How does the model handle items it has never seen? Or items with sizes that are far outside of the distribution of the items it has been trained on?
summary_of_the_review: I think the method presented in this paper is a good strategy for defining the state/action space for bin packing. The paper is clear and the experiments are convincing, so I recommend acceptance. It would be stronger with more compelling evidence that the graph network is learning non-trivial policy behavior, but overall the results are certainly strong over prior work and existing heuristics.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new method for online 3D bin packing problem (3D-BPP), with the newly designed packing configuration tree (PCT) for representing the state and graph attention networks (GAT) for learning the representations. Experimental comparisons with recent baselines and for different constraint settings are provided.
main_review: - The reviewer is not quite familiar with this research area, but the proposed PCT and the corresponding learning method seem to be quite novel and sound.
- This paper is written in a clear and thoughtful way.
- The evaluations and related studies have been conducted thoroughly. The performance gain over existing recent baselines is clear. Empirical results on generalization also well demonstrate the efficacy of this work.

I have a few (maybe dumb) following questions:
- Could you explain the constraint in Eq. (1)? What does it mean when $e_{ij}=0$ and $p_i^d + s_i^d \le p_j^d + S^d$?
- What is the inference time for the proposed method with different leaf node expansion schemes? The theoretical time complexities have been introduced in the appendix, and the practical timing is a question of interest.
- How is the density property considered in Setting 3?

summary_of_the_review: The reviewer is not actively working within the scope of this work. Still, it is a pleasure to read this paper, and it clearly describes and motivates the problem and proposes plausible and effective solutions with detailed experiments.

====
The reviewer has read all other reviews and the rebuttals and would very much thank the authors for the speedy and detailed response.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents PCT, a tree structure that integrates several packing heuristics for addressing the online 3D-BPP. The PCT 1) can be amenably incorporated into DRL as a term of the reward function and 2) makes the training tractable as it effectively trims the learning space defined by the low-level packing heuristics. 
main_review: Strengths:

1. The idea of PCT, as a whole, is novel and makes a good sense. It is also well illustrated and easy to follow.
2. The motivation of the work is well explained and the pros and cons of different methods are clearly discussed.
3. The experiments are extensive and the proposed method based on PCT outperforms all competing methods significantly.

Weaknesses:

1. PCT is expanded with only 3 existing rules of heuristics, including CP, EP and EMS. Such a strategy seems to oversimplify the problem. There exist a couple of heuristics and some of them were summarised in:

    - A generalized reinforcement learning algorithm for online 3d bin-packing. AAAI 2020.

    - A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 1996.

2. The authors claim that the proposed method is efficient. But there is neither theoretical analysis (e.g. some kind of complexity analysis) nor experimental results (e.g. run time, number of iterations needed for DRL convergence, visualisation of learning curves, etc.) for demonstrating it.

3. There is no real-world experiments, which makes the paper a bit weak especially because it attempts to demonstrate the efficiency of the PCT. A demo like the one provided with the following paper would be impressive. 

     - PackerBot: Variable-Sized Product Packing with Heuristic Deep Reinforcement Learning. IROS 2021.

In addition, the paper could be improved if the following issues can be clarified:

1. In Section 3.3, what is the physical meaning of the pointer mechanism (Vinyals et al., 2015) employed for leaf node selection?

2. In Section 3.4, the authors mentioned “we fullfill PCT to a fixed length with dummy nodes”. But how can we find a fixed length for different bin configurations? If it is too small, it will not be enough for holding all leaf nodes; if it is too large, it will make the learning space excessively large and hurt the efficiency significantly.

summary_of_the_review: The idea of PCT is holistically novel and seems effective for the online 3D-BPP, which is a very challenging issue anyway. Therefore, although the paper has some issues as listed above, I am still slightly positve to it.

------------ Post rebuttal -------------- 

Most of my concerns have been well addressed during the rebuttal period of time. I'd appreciate very much the effort made by the authors and am happy to lift my recommendation to a full acceptance. Btw, it seems that some references are missing in the revised version, such as the two recent ones for 3D-BPP listed below:

- A Generalized Reinforcement Learning Algorithm for Online 3D Bin-Packing. AAAI 2020.
- PackerBot: Variable-Sized Product Packing with Heuristic Deep Reinforcement Learning. IROS 2021.
review_title: null

Meta-review: This paper proposes a new approach to online 3D bin packing with deep reinforcement learning. It received mixed reviews. AC finds that the responses from authors have addressed the concerns satisfactorily.
Decision: Accept (Poster)