Adjustable Robust Reinforcement Learning for Online 3D Bin Packing
Authors: Yuxin Pan
Yize Chen
Fangzhen Lin
Venue: NeurIPS 2023 poster (2023)
Keywords: online 3D bin packing problem
combinatorial optimization problem
reinforcement learning
TL;DR: we propose an adjustable robust reinforcement learning framework for solving online 3D bin packing problem.

Abstract: Designing effective policies for the online 3D bin packing problem (3D-BPP) has been a long-standing challenge, primarily due to the unpredictable nature of incoming box sequences and stringent physical constraints.  While current deep reinforcement learning (DRL) methods for online 3D-BPP have shown promising results in optimizing average performance over an underlying box sequence distribution, they often fail in real-world settings where some worst-case scenarios can materialize. Standard robust DRL algorithms tend to overly prioritize optimizing the worst-case performance at the expense of performance under normal problem instance distribution. To address these issues, we first introduce a permutation-based attacker to investigate the practical robustness of both DRL-based and heuristic methods proposed for solving online 3D-BPP. Then, we propose an adjustable robust reinforcement learning (AR2L) framework that allows efficient adjustment of robustness weights to achieve the desired balance of the policy's performance in average and worst-case environments. Specifically, we formulate the objective function as a weighted sum of expected and worst-case returns, and derive the lower performance bound  by relating to the return under a mixture dynamics. To realize this lower bound, we adopt an iterative procedure that searches for the associated mixture dynamics and improves the corresponding policy. We integrate this procedure into two popular robust adversarial algorithms to develop the exact and approximate AR2L algorithms. Experiments demonstrate that AR2L is versatile in the sense that it improves policy robustness while maintaining an acceptable level of performance for the nominal case.

Adjustable Robust Reinforcement Learning for Online
3D Bin Packing
Yuxin Pan' Yize Chen Fangzhen Lin
EMIA, The Hong Kong University of Science and Technology
2 AI Thrust, The Hong Kong University of Science and Technology (Guangzhou)
CCSE, The Hong Kong University of Science and Technology
yuxin. paneconnnnccontt.... ust. yizechen@ust. hk flin@cs ust. hk
Abstract
Designing effective policies for the online 3D bin packing problem (3D-BPP) has been a long-standing challenge, primarily due to the unpredictable nature of incoming box sequences and stringent physical constraints. While current deep reinforcement learning (DRL) methods for online 3D-BPP have shown promising results in optimizing average performance over an underlying box sequence distri- bution, they often fail in real-world settings where some worst-case scenarios can materialize. Standard robust DRL algorithms tend to overly prioritize optimizing the worst-case performance at the expense of performance under normal problem in- stance distribution. To address these issues, we first introduce a permutation based attacker to investigate the practical robustness of both DRL-based and heuristic methods proposed for solving online 3D-BPP. Then, we propose an adjustable robust reinforcement learning (AR2L) framework that allows efficient adjustment robustness weights to achieve the desired balance of the policy's 's performance in average and worst-case environments, Specifically, we formulate the objective function as a weighted sum of expected and worst-case returns, and derive the lower performance bound by relating the return under mixture dynamics. To realize this lower bound, we adopt an iterative procedure that searches for the asso- ciated mixture dynamics and improves the corresponding policy. We integrate this procedure into two popular robust adversarial algorithms to develop the exact and approximate AR2L algorithms. Experiments demonstrate that AR2L is versatile in the sense that it improves policy robustness while maintaining an acceptable level of performance for the nominal case.
1 Introduction
The offline 3D bin packing problem (3D-BPP) is classic NP-hard combinatorial optimization problem (COP) (de Castro Silva et al. 2003), which aims to optimally assign suboid-shaped items with varying sizes to the minimum number of containers while satisfying physical constraints (Martello ctt al. 2000). In such a setting, a range of physical constraints can be imposed to meet diverse packing requirements and preferences (Gzara et al. 2020). The primary constraint requires items to be packed stably, without any overlaps, and kept within the bin. The online counterpart 3D-BPP more prevalent and practical in logistics and warehousing (Wang and Hauser (020),, it does not require complete information about all the unpacked items in advance. In this setting, only a limited number of upcoming items conveyor be observed, and items must be packed after the preceding items are allocated (Seiden 2002). Thus, besides physical constraints already present
* Co-corresponding Authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in the offline counterpart, the item permutation on the conveyor introduces additional constraints, while the solution approach must take packing order into consideration.
Solution techniques for online 3D-BPP can be broadly categorized into heuristic and learning- based methods. As heuristics often heavily rely manually designed task-specific score func- tions (Chazelle, 1983; Ha et al. 2017), they have limitations in expressing complex packing pref- erences and adapting to diverse scenarios. By comparison, learning-basee methods usually involve utilizing deep reinforcement learning (DRL) techniques to develop a more adaptable packing policy capable of accommodating diverse packing requirements (Zhao et al. 2021 2022a Song al.. 2023). While emerging DRL-based methods for online 3D-BPP are effective at optimizing average performance, they do not account for worst-case scenarios. This is because these methods often fail on "hard" box sequences arising from the inherent uncertainty in incoming box sequences. In addition, few studies have investigated the robustness of these methods, as incoming item sequences can vary a lot in practice. These limit the practical usage of learning- baaiingg---edd--e approaches.
To study the algorithm robustness under worst-case scenarios, one plausible approach is to design an attacker that can produce perturbations commonly encountered in real-world settings. Various proposed attackers for perturbing RL models often add continuous- value noise to either received observations or performed actions (Tessler et al. 2019) Sun et al., (02T). Yet such methods are mostly not well-suited for online 3D-BPP, as the state defined by the bin configuration and the currently observed items, and adding continuous-val value noise may not correspond to real-world perturbations. As previously discussed, item permutations can significantly impact the performance of given packing strategy, and in real-world scenarios, the packing strategy may face challenging box sequences. By contrast, perturbing the bin configuration may violate practical constraints or packing preferences. Therefore, we argue that using diverse item permutations to evaluate the model's s robustness is a more suitable approach. Some of general robust reinforcement learning frameworks against perturbations can be applied to online 3D-BPP (Pinto et al. 2017 Ying al.) 2022 Ho et al.) 2022 Panaganti et al. 2022], yet these methods may develop overly conservative policies, as they usually prioritize improving worst-case performance at the expense of average performance. This motivates us to design a robust algorithm that can effectively handle worst-case problem instances while attaining satisfactory average performance.
In this paper, we develop a novel permutation- crauutation-baed attacker to practically evaluate robustness of both DRL-basedd and heuristic bin packing policies. We propose an Adjustable Robust Reinforcement Learning (AR2L) framework, which preserves high performance in both nominal and worst-case environments. Our learnable attacker selects an item and place it to the most preceding position in the observed incoming item sequence, as only the first item in this sequence has the priority to be packed first. Essentially, this attacker attempts to identify problem instance distribution that is challenging for a given packing policy by simply reordering item sequences. The developed AR2L incorporates such novel attacker along with adjustable robustmess weight parameter. Specifically, to consider both the average and worst-case performance, we formulate the packing objective as a weighted sum of expected and worst-case returns defined over space utilization rate. We derive a lower bound for the objective function by relating it to the return under a mixture dynamics, which guarantees AR2L's performance. To realize this lower bound, we turn to identifying a policy with the highest lower bound as the surrogate task. In this task, we use an iterative procedure that searches for the associated mixture dynamics for the policy evaluation, and improves the policy under the resulting mixture dynamics. To further put AR2L into practice, we find the connecting link between AR2L with the Robust Adversarial Reinforcement Learning (RARL) algorithm (Pinto et al., (017) and the Robust f-Divergence Markov Decision Process (RMMDP) algorithm (Ho et al. Panaganti et al. 2022). resulting in the exact AR2L and the approximate AR2L algorithms respectively. Empirical evidence shows our method is able to achieve competitive worst-case performance in terms of space utilization under the worst-case attack, while still maintaining good average performance compared to all previously proposed robust counterparts.
2 Related Work
Numerous heuristic Ha et al. (2017);
Karabulut and inceoğlu (2005): Wang and Hauser (2019) Li and
Zhang 2015); Hu et al. (201) | (020) and learning-based methods (Hu et al. 2017 Verma et al. [0200 Zhao et al. 2022 2022b Yang et al. [02T Zhao et al., 2022a] [Song et al. 2023) have been proposed
to solve online 3D-BPP. However, these methods typically only consider average performance and

---

may not be robust against perturbations, For more detailed reviews of related algorithms on 3D-BPP, please refer the Appendix.
Adversarial Attacks in Deep RL. More recently, several studies have demonstrated that deep RL algorithms vulnerable to adversarial perturbations from attackers, and robust policies can be
trained accordingly (Huang et al. 2017; Zhang et al., 2020 2021 1 Sun et al. 2021 Ding et al. (023). Yet standard DRL attack schemes cannot generate realistic attacks for 3D- due the setting of added perturbations. In the field of COP, Lu et al. (223) used a RL-based attacker to modify the underlying graph. Yet this method is limited to offline COPs that can be formulated as graph. Kong
et al. 2019) employed generative adversarial network (GAN) (Goodfellow et al. 2020) to generate some worst-case problem instances from Gaussian noise under restricted problem setting.
Robust RL. In order to find policies that are robust against various types of perturbations, a great
number of studies have investigated different strategies, such regularized-based methods (Zhang)
et al. 2020 Shen et al.] 2020 Oikarinen et al.] [202T] Kumar et al. 202T Kuang et al. 2022).
attack methods (Kos and Song 2017: Pattanaik et [017 Behzadan and Munir 2017).
novel bellman operators (Liang et al., 2022 Wang and Zou| 2021 2022), and conditional value
risk (CVaR) based methods (Chow et al.
2017 Tang et al.) 2019; Hiraoka et al. 2019 Ying
iet al. 2022). However, these methods are generally intended to deal with 1 --norm perturbations on vectorized observations, which could limit their applicability to online 3D-BPP. Built upon robust MDP framework {Iyengar 2005). Pinto et al. (2017) modeled the competition between the agent and the adversary as a zero-sum two-player game, but such game formulation has an excessive prioritization of the worst-case performance. Jiang et al. (202T) introduced Monotonic Robust Policy Optimization (MRPO) to enhance domain generalization by connecting worst-case and average performance. Yet such approach imposes Lipschitz continuity assumptions, which are unaligned with 3D-BPP. The recently developed robust f-divergence MDP can approximate the worst-case value of policy by utilizing nominal samples instead of relying on samples from an adversary (Ho et al., 2022] Panaganti et al., 2022). However, this method still cannot account for expected cases, as its Tocus is solely on learning values in worst-case scenarios.
3 Preliminaries
MDP Formulation of Online 3D-BPP. To leam a highly effective policy via RL, the online 3D- BPP is formulated as an MDP. Inspired by PCT (Zhao et al. (2022a), in this formulation, the state spack E Spack observed by the packing agent consists of the already packed Ne items C, in the bin, the observed incoming Ng items B,, and a set of potential positions Ly. The packed items in Ce have spatial properties like sizes and coordinates, while each item b,.1 E B,, {I, NB) } only provides size information. The potential positions are typically generated for the most preceding item in B, using heuristic methods (Martello al., 2000 Crainic al. 2008 Ha et al. (017). Then,
the action af quack E Apack is to choose one position le,t E Le.j {L, .., N for the first item in B, In the termination state ST (I' is the episode length), the agent cannot pack any more items. As a result, the agent receives a delayed reward IT that represents the space utilization
ST. instead of immediate rewards (r, = 0, f < T). The discount factor y here is set to 1. The aim is to maximize the space utilization by learning a stochastic packing policy Tpack (Tt, C.,, C,,
Robust MDP. The goal of robust MDP is to find the optimal robust policy that maximizes the value against the worst-case dynamics from an uncertainty set pw The uncertainty set is de- fined in the neighborhood of the nominal dynamics po = (Po 1 (8,a) E S x A) and sat- 8(s.))Sx 8,07 PHr isfies rectangularity condition (Iyengar) 2005), defined as p s,a+
(Pa.e A(S)= Drv x.a) p). where D-v(-) denotes the total variation (TV) dis- tance, @ is the Cartesian product, A(S) is set of probability measures defined on S, and E [0, is the radius of the uncertainty set. Consequently, the robust value function un- der a policy π is V. = p"Epr V...P". And the robust Bellman operator T, is defined as (s')], where s' denotes the next state. To empirically solve the robust MDP, Pinto et al. (2017) proposed RARL that learns the robust policy under the environment perturbed by a learned optimal adversary.
(s) Ea-r[r(s, a) + + inf Par EP= 2.e Eg sig
Robust foanust-divver /diivegencce MDP. To avoid the need for costly trained adversary. RfMDP (oo et al. 2022 Panaganti et al. 2022) formulates the problem as tractable constrained optimization task to approximate the robust value using samples from po, The objective is to find transition distribution
3

---

that minimizes the robust value function, subject to the constraint in 7d described by the f-divergence. As result, new robust Bellman operator introduced by solving the dual form of this constrained optimization problem through the Lagrangian multiplier method.
Adjustable Robust Reinforcement Learning
In this section, we begin by introducing a novel yet practical adversary capable of generating worst- case problem instances for the online 3D-BPP. Next, we present the adjustable robust reinforcement learning (AR2L) framework
address the robustnexs-performance tradeoff. Finally, we integrate AR2L into both the RARL algorithm and the RfMDP algorithm to derive the exact and approximate AR2L algorithms in a tractable manner.
4.1 Permutation- Attacker
In online 3D-BPP, a problem instance is comprised of sequence of items, and these items are randomly per- muted and placed conveyor. Such randomness can result in certain in- stances where trained policy may fail. Therefore, this observation motivates us to design simple yet realistic adversary called permutation-ben attacker. By reordering the item sequence for a given packing pol- icy, our approach can explore worst- case instances without compromising realism (See Figure [ for attacker overview). In contrast to the approach of directly permuting the entire item sequence as described in (Kong et al.) 2019). our method involves permuting the observable item sequence, thereby progressively transforming the entire item attacker in the Appendix, we
b
Bin Configuration C₃
Observable Items R,
Configuration Cre
is feardered to
Pormutation-based
Packing Policy
Attacker
Probabllty
Bin Configuration Cę
1/3
Observable Items Bü
Observable Items
Potential Positions L,
Figure 1: Overview of our attack framework.
sequence. Through the behavior analysis of our permutation-bassee observe the attacker appears to prefer smaller items when constructing harder instances as the number of observable items increases. This aligns with the findings mentioned in (Zhao et al. 2022a), where larger items simplify the scenario while smaller items introduce additional challenges. As result, the act of permuting the entire sequence might enable the attacker to trickily seleet certain types of items, and thus carries potential risks associated with shifts in the underlying item distribution. However, we aim to ensure that the attacker genuinely learns how to permute the item sequence to identify and create challenging scenarios. To mitigate these risks, limit the attacker's 's capacity by restricting the number Ng of observable items to proactively address concerns related to changes in the item distribution.
To target any type of solver intended for solving the online 3D-BPP for robustness evaluation, we train RI-saded policy which acts as the permutation- based attacker. The permuted state s.err E Sperm of the attacker is comprised of the current bin configuration C. and the item sequence B, The action aperm E AAeerm involves moving one item from B, to a position ahead of the other observed items, resulting in the reordered item sequence B' = (b/,). Then, the packing policy will pack the most preceding one into the bin based on the perturbed observation. The reward for the attacker is defined r perm pack since the objective is to minimize the space utilization by training an optimal stochastic policy Terrm (bv. C,, B,). The online packing process allows only the first item in the observable item sequence be packed each step. To address the issue of exponential growth in the action space as the number of observable items increases, the permutation based attacker strategically selects one item and positions ahead of the other items. We can consider simplified value function represented // (C,, B() p + p (C.+1. BB.1). This function indicates that the value of pack depends on pack C.+1, and B/ Furthermore, pack and C++1 are influenced by the first item in B', while the remaining items in B', combine with new item form new sequence, which undergoes further permutations as B As a result, the permutation of the remaining items at time step f is disregarded in the attack process. To model such

---

an attacker, we use the Transformer (Vaswani et al., 2017) that is capable of capturing long-range dependencies in spatial data and sequential data involved in the attacker's observation. Please refer to the Appendix for more details on the implementations.
4.2 Adjustable Robust Reinforcement Learning
For online 3D-BPP, item observed each timestep is independently generated from station- ary distribution pb(b,,)) that does not change over time. Once an item is placed into the con- tainer, the bin configuration C, becomes deterministic, and new item be+1,Ng a is appended to the observable item sequence to construct Bu+1- Thus, the nominal environment is defined as 1 BC, Br, at ) po(b++1.Nn). We omit L, for brevity. Since we use the permutation- based attacker to reorder the observable item sequence, the worst-case environment transition pn (C(+1, I By, pack) = Pb ) ( 1,4+1,1//+41 the worst-case dynamics.
Br+1), with pd as
Existing DRL-based methods are developed to learn packing policy that maximizes space utilization (cumulative reward) under the nominal distribution Po. However, in real-world scenarios where the order of items can be adversarially permuted, it is not sufficient to only consider the expected return under po, In contrast, the existing general robust methods that can be deployed to online 3D-BPP overly prioritize robustness at the cost of average performance by solely focusing on the return under the worst-case dynamics p To address these issues, we should be aware of the returns under both the average and worst-case scenarios. Given that nominal cases are more common than worst-case scenarios in the online 3D-BPP setting, the objective function is defined as
n arg max (,T,, Po) + onj(T, P*) #ell
where a E 10 the weight of robustness, 77()) is the return, and pa built on the optimal permutation-based attacker. Here symbols without superscripts represent those used by the packing agent (e.g., pack = T).
However, how can we learn such a policy with the presence of both p and po? To address this matter, we derive a lower bound for the objective function defined in Equation by relating the return under an unknown mixture dynamics defined as pmm as shown in the following theorem.
Theorem 1. The model discrepancy between two models can be described as di P1 P2) A max,,a Drv (-1s, P2 (2(-(s,a)) a)). The lower bound for objective 7 is derived as follows:
27/r max (d(P"I)PP)) + (al(P"))e (d(PP(IP"))
'T,,, Po) + (n P')) 2 (1 a))(T,, -1 7)2
The RHS of Inequality 2 provides the lower bound for the objective function defined in Equation where the first term represents the expected return of policy π under the mixture dynamics pm, while the second term denotes the weighted sum of deviations of pm from both po and pD, Motivated by Theorem [] we turn to maximizing the RHS of Inequality 2 to concurrently improve both the average and worst-case performance. Therefore, the primal problem in Equation iis equivalently reformulated to surrogate problem where we expect to identify an optimal policy with the maximal lower bound, represented as
π arg max max PTM) - (d(P")) PP)) + ad(P") P(")) #Ell PMEP
The objective of this optimization problem is to maximize the return by updating both the policy and the mixture dynamics controlled by robustness weight a, given the nominal and worst-case dynamics. Furthermore, the second term in Equation 3 can be viewed as constraint that penalizes the deviations between environments, resulting in a constrained optimization problem written as n arg m (max 7T P')) d( [MM] PP) However, this constraint renders the constrained form of Equation 3 iimpractical to solve. Instead, heuristic approximation is used for this constraint, which considers the TV distance at each state-action pair, leading to an uncertainty set for the mixture dynamics:
["') S P'), where p' [0. +a].
Tm ((a)))Sx P. = (Pr.. E A(S): Drv (Px.. (P.a) + aaDr
S Sp'}. (4)
The uncertainty set pm satisfies the rectangularity condition Iyengar| (2005). To solve the constrained optimization problem, carry out an iterative procedure which scarches for the associated mixture
5

---

Permutation-based Attacker
Permutation-based Attacker
Gradiant
Dasa
B
Distance Loss
C.
B₁
Nominal Dynamics
By, C.
Mixture- Misture-Dynamicc Model
Nominal Dynamics
Bd, C2.
mork
Adjustable Robust Value Function
Dienisution Ps
Distribution
B. Ce
Packing Policy
DRL
Packing Policy
DRL
(,B,CC))
(a) Exact AR2L Algorithm
(b) Approximate AR2L Algorithm
The exact AR2L algorithm requires to learn mixture-dynamics model to generate problem instances for the training of the packing policy. Right: The approximate AR2L algorithm relies on the samples from both the nominal dynamics and the permutation- attacker to estimate adjustable robust values of the packing policy.
Figure 2: Implementations of the AR2L algorithm. Left:
dynamics for the policy evaluation, and improves the policy under the resulting mixture dynamics. Therefore, define the adjustable robust value function as V suppp Va.P" evaluation, And the adjustable robust Bellman operator Ta can be defined as
Pm for the policy
TaVa (s) = Eess a) Prr EP
sup Er [V (s'I).
(5)
The adjustable robust Bellman operator assumes both the nominal and worst-case dynamics corre- sponding to π are available for constructing the uncertainty set pmm. Unlike the traditional robust Bellman operator (lyengar 2005) designed for the minimal value, our proposed operator focus on maximizing the value of given policy by updating the mixture dynamics. Meanwhile, to avoid the optimistic evaluation, the uncertainty set for the mixture dynamics used in Equation [3] is constrained with regard to both nominal and worst-case environment. Following policy evaluation, the policy is improved using samples drawn from the mixture dynamics. addition, the following theorem guarantees that To can facilitate the convergence of the value function to a fixed point.
Theorem 2. For any given policy and its corresponding worst-case dynamics P", the adjustable robust Bellman operator To contraction whose fixed point is V The operator equation TaV. = V has unique solution.
Exact AR2L Algorithm. The AR2L algorithm evaluates and improves policies based on the mixture dynamics that exists in the neighborhoods of both the nominal and worst-case scenarios. However, this algorithm remains impractical since the adjustable robust Bellman operator defined in Equation [3 involves computing the expectations w.r.t. all models in the uncertainty set pm. This potentially results in high computational complexity. Inspired by the classic RARL algorithm (Pinto et al., 2017) which trains robust policy utilizing perturbations injected by learned optimal adversary, we propose an iterative training approach that involves training mixture-dynamics model mmix alongside the packing policy pack and the permutation-based attacker rperm to obtain the exact AR2L algorithm. The mixture-dynamics model is corresponding to the mixture dynamics, and it permutes the observable item sequences B, B² based on observed packed items C.. As illustrated Figure 2(a) such model receives the same reward as the packing policy (r-mix = r.aack). Based on Equation the mixture-dynamics model strives to maximize the return under given policy, while also penalizing deviations between dynamics. As pm and p have the same form with the same underlying item distribution pb, can only measure the discrepancy between pm and pa by evaluating the deviation between maix and perrm- In practice, the Hellback-Leibles (KL) divergence is adopted to constrain the deviation between distributions. Thus, the training loss is
Lmix 1 (Tackk, Tmix) + (Dxx(1lllll (x=be...)) + a aD (Tmix (Tpem)))
where DEL is the KL divergence, and 1l (a=br+n,) 3 denotes the indicator function. Thus, the mixture- dynamics model is optimized by minimizing both the DRL loss (the first term) and the distance loss (the second term). Based on this, the exact AR2L algorithm iterates through three stages to progressively improve the packing policy. First, the permutation-ban given packing policy, as is done in RARL. the loss function defined in Equation 6, Finally, the packing policy is evaluated and improved using problem instances that are permuted by Tmix-
attacker optimized for a the mixture-dynamin model miix is learned using

---

Approximate AR2L Algorithm. Training the mixture- mixture-dynamic dynamics model in exact AR2L introduces additional computation to the entire framework. We thus propose the approximate AR2L algorithm. which uses samples from both the nominal and worst-case dynamics to estimate adjustable robust values for the policy iteration as shown in F Inspired by RMMDP (Ho et al. [022] Panaganti et al. ) we use the dual reformulation of the adjustable robust Bellman operator, as given below.
Proposition 1. The policy evaluation of AR2L can be formulated as a constrained optimization problem. The objective is to maximize the value function over the uncertainty set P"", subject to the constraint defined in Equation 4 By representing the TV distance using the f-divergence (Shapiro) 2017|, the adjustable robust Bellman operator Ta given in Equation [3 be equivalently written as
inf (Es-Py, D......VV (VT -mi(s)+++ Ta (s) = -Eawx -Eawx((ssa)) 1 1+a A.
(7)
aBp-pyy [V. (20))2(ss))- (5+)))+++ + μ Ap(1 + a])]
where [x]+ denotes max xz, 0}, μ1 (s) and p2(5) are Lagrangian mulripliers for each s E S; μ
(s( + (pp(s) holds for each s E S, and X max, " (s) (1)) VT) -2()),,) 0}.
The approximate AR2L algorithm eliminates the requirement of using samples from the mixture dynamics for policy evaluation, yet it introduces estimation errors into the process. In practice, this results in mild performance degradation and sometimes unstable learning. Nevertheless, it remains valuable the approximate AR2L still demonstrates superior performance compared to RIMDP.
In order to implement the AR2L algorithm, we opt to use the PPO algorithm (Schulman al. 2017)
to train packing policy "puckk permutation-basee attacker <perm and mixture-dynamics model Tmix- The packing policy is implemented using the PCT method (Zhao et al. 2022a) to accommodate the continuous solution space. All of the relevant implementation details, pseudocode for the algorithms, and both derivations and proofs are included in the Appendix.
5 Experiments
Training and Evaluation Settings In the online 3D-BPP setting, the container sizes S d E (I, y, 2} are equal for each dimension (S" = = = =, and the item sizes s E {x. V, 2} are limited to no greater than Sd /2 to create more complex scenarios. The stability of each item is checked based on constraints used in (Zhao et al. 2022a b). Moreover, we adopt two different popular settings used in (Zhao et al. 2022a b) for training DRL. policies. In the discrete setting, where item sizes are uniformly generated from discrete set, i.c., s E {1, 3, 4, 5), resulting in total of 125 types of items, and the container size 5d is fixed at 10. In the continuous setting, the container size St is set to 1. and item sizes s" d E {z.y) y follow a continuous uniform distribution (O..1, and s* is uniformly sampled from finite set {0.1, 0.2, 0.3. 0.5). Then, discrete and continuous datasets are created following instructions from the two aforementioned training settings to evaluate both heuristic and DRI--based methods. Each dataset consists of 3,000 problem instances, where each problem instance contains 150 items. We use three metrics to evaluate the performance of various packing strategies: Uti represents the average space utilization rate of the bin's volume; Std. is the standard deviation of space utilization which evaluates the algorithm's reliability across all instances; Num. evaluates the average number of packed items.
5.1 Algorithm Robustness under Permutation-baseee Attacks
In our experiment, we evaluate the robustness of six heuristic methods, including deep-bottommllft
(DBL) method (Karabulut and Inceoğlu 22055) ), best-match-first (BMF) method (Li and Zhang (015)) least-surface-area heuristies (LSAH) (Hu et al. (2017), online bin packing heuristies (OnlineBPH) (Ha) et al.) 2017), sigggttmapmmiimzzationn (HMM) method (Wang and Hauser 2019) and maximize- sooesible-convve-space (MACS) method (Hu al. 2020). For the baLedased methods, we evaluate the constrained deep reinforcement learning (CDRL) (Zhao et al. 2021) algorithm, and the packing configuration tree (PCT) method (Zhao et al.) 2022a). We train specific permutation- based attackers for each of them. Since the capacity of the permutation-basee of observable items of the attacker, we choose N₂ n = 5, 10, 15, 20 to obtain different attackers. Given that the number of observable items for the packing policy is typically limited to the first item in most methods, except for PCT, we can establish a consistent approach by setting the number of observable items for the packing policy to in this case.
attacker is highly related to the number
7

---

Table 1: The performance of existing methods under the perturbation in the discrete setting.
NB
NB = 10
NB = 15
NB = 20
w/o attack
Methods
(ti.(%
Std. Num. (1).(%)
Std. Nam. Uti.(%)
Std. Num. Utti(%%
Std. Num. Uti.(%)
Std. Num.
DBL
40.4
14.3
18.4
28.5
16.1
13.9
26.0
14.9
14.9
21.3
12.6
8.5
63.6
11.9
25.8
BMF
46.9
11.5
21.0
40.9
12.2
22.2
38.6
12.9
21.1
33.7
11.9
22.1
62.0
9.2
24.8
LSAH
46.0
10.1
20.3
42.2
11.3
20.9
38.6
11.0
19.4
35.6
11.8
21.3
60.9
10.9
24.6
OnlineBPH1
47.1
21.0
19.8
44.0
18.9
22.8
29.8
18.5
14.6
22.4
12.7
14.1
64.1
8.9
25.8
HMM
49.1
11.1
22.5
46.5
13.8
22.5
43.4
13.0
21.4
40.4
10.0
24.1
56.1
10.4
22.6
MACS
43.0
9.7
21.9
40.8
9.0
24.8
39.0
9.8
23.7
38.3
9.0
27.0
53.0
10.8
21.5
CDRL
61.5
7.8
27.9
56.1
6.9
28.7
54.6
7.6
31.3
51.0
7.1
29.9
74.1
7.3
29.1
PCT
63.6
9.9
27.3
58.7
11.3
25.8
50.9
13.1
25.6
40.5
15.3
21.8
76.6
6.0
30.0
Table I presents the performance of various methods under perturbations from corresponding permutation-base attackers in the discrete setting. We can observe that though the HMM al- gorithm does not perform the best in the nominal scenario compared to other heuristic methods, exhibits superior performance under attackers with different attack capacities. By comparison, the DBL method is the most vulnerable heuristic method. As attack capabilities increase, the CDRL algorithm demonstrates greater robustness compared to the PCT method, consistently achieving higher average number of packed items with smaller variance of volume ratio. It is worth noting that the larger the value of NB is, the more the performance can be degraded for all methods, indicating that harder problem instances can be explored by increasing the value of NB- In addition, the number of packed items does not necessarily decrease attack capacity increases. This is because permutation-baase attackers aim to minimize space utilization, which means they may select smaller items make the packing problem more challenging for the packing policy.
5.2 Performance of AR2L Algorithm
We then benchmark four other RL algorithms compatible with online 3D-BPP tasks, which in- clude packing configuration tree (PCT) (Zhao et al. 2022a) method, the Loi--ProxxilllPolicee Optimization (CPPO) (Ying et al. 2022) algorithm, the robust adversarial reinforcement learning (RARL) algorithm PPitoo et al. 2017). and the robust f-divergence MDP (RIMDP) (Ho et al. 2022 Panaganti et al. 2022). The PCT algorithm serves as the baseline method and is used as the packing policy for all other methods in implementations. The CPPO algorithm trains the packing policy with worst-case returns as a constraint, which can potentially improve both average and worst-case performance. The RARL algorithm is the baseline model for the exact AR2L algorithm due to its reliance on worst-case samples from the attacker. Likewise, the RIMDP framework serves as the baseline model for the approximate AR2L algorithm because it involves approximating values of the unknown dynamics. As both the exact AR2I (ExactAR21,) algorithm and the approximate AR2L algorithm (ApproxAR2L) can develop policies with different levels of robustness by adjusting the value of a, we choose a = 0.3, 0.5, 0.7, 1.0 to explore the relationship between a and policy robust- ness. Furthermore, we use different attackers with varying attack capabilities (Ng 5, 10, 15, 20) to investigate the robustness of packing policies. It is important to note that in this scenario, the packing policy is permitted to observe the same number of items as its corresponding attacker. During testing, we construct mixture datasets by randomly selecting 3%% nominal box sequences and reordering attacker for each packing policy. The empirical results
them using the learned permutation-bast in the continuous setting are included in the Appendix. Since we implement PCT with different training configurations, we conducted a comparison between our implementation and the official implementation in the Appendix.
Uti. Table 2 presents the results of evaluating multiple robust methods on various datasets that differ in the number of problem instances perturbed by different attackers. We denote the different values of a used by the ExactAR2L algorithm as ExactAR2L(a), and similarly for (p)roxAR2L(a). The results unequivocally indicate that the ExactAR2L algorithm, when employed with higher value of a, exhibits superior performance on nominal cases and competitive robustness in terms of space utilization when compared to other robust methods. When the value of a is increased, it allows the packing policy to encounter and learn from more worst-case samples during training. By experiencing wider range of adversarial situations, the packing policy can better adapt to mitigate the impact of attackers, enhancing its overall robustness. However, ExactAR2I. cannot consistently improve its average performance across all the settings with different values of Ng. For the scenario
8

---

Table 2: The performance of robust methods under the perturbation in the discrete setting.
Methods
B
75
U'i.(%%)
Num. (ti.(5)
Std. Num. Uti.( Std.
Uti.(9t)
Uti.(%) Num.
73.6
29.9
27.1
CPPO
75.5
6.9
29.6
73.1
8.0
29.0
70.7
8.4
28.5
67.9
8.2
27.9
65.2
7,3
27.4
RARL
74.6
6.2
29.2
73.1
7.3
29.2
70.8
8.4
29.0
67.8
8,4
28.4
66.7
8.1
28.5
ExactAR21.0.33
76.3
6.6
29.8
73.8
8.5
29.6
71,0
9.1
29.2
67.5
28.4
64.5
27.7
ExacIAR2((0.5)
76.5
30.1
73.5
8.8
29.4
70.5
10.4
28.8
68.2
10.3
28.1
65.3
10.0
27.6
ExacAA22(00.7)
76.8
6.1
30.1
74.4
7.7
29.7
71.1
8.9
29.1
68.8
9.7
28.7
66.3
8,6
28.5
(x.cIAR21(1.0)
77.4
6.5
30.2
74.3
9.3
29.5
72.0
9.5
29.0
69.5
10.0
28.4
66.5
8.7
27.9
RIMDP
75.5
29.6
71.8
9.8
28.8
69.6
9.4
28.5
67.1
28.0
63.9
27.3
ApproxAR2L(0.31
75.3
6.3
29.6
72.6
7.7
28.9
70.0
8.6
28.4
66.4
9.7
27.6
63.2
9.5
26.9
Approx A AR (0.5)
76.1
5.8
29.8
72.6
8.4
29.0
69.8
9.9
28.4
67.3
27.7
64.7
8.8
27.4
ApproxAR2L(0.
76.9
30.0
73.7
8.0
29.1
71.6
8.5
28.7
68.2
27.8
66.2
27.0
ApproxAR22((1.0)
76.5
6.5
30.1
73.4
8.9
29.2
70.8
9.3
28.6
686.4
9.3
28.0
65.7
8.5
27.5
PCT
76.4
6.6
29.9
70.6
12.4
28.5
65.1
14.5
27.3
61.4
14.8
26.4
55.7
12.9
25,2
CPPO
75.6
7.2
29.8
70.7
11.6
28.6
66.2
12.7
62.3
12.9
26.9
57.4
11.4
25.8
29.4
71.1
8.7
29.0
27.7
ExactAR2L(0.3
76.5
5.9
29.9
71.5
12.1
28.9
66.8
14.0
27.8
62.9
14.1
27.0
59.2
12.7
26,4
ExacIAR2L/0.55
77.6
5.8
30,3
73.1
10.2
29.5
68.0
13.1
28.8
64.0
12.7
28.0
59.7
10.2
27.4
ExactAR21.000
77.4
30,2
73.1
9.7
29.5
27.4
ExactAR2L(1.0)
76.0
7.0
29.8
72.4
9.7
30.0
70.3
9.4
30.3
66.7
9,3
30.3
63.8
8.0
30.6
RIMDP
74.4
7.2
29.7
70.5
11.4
28.7
65.7
14.3
28.0
60.8
14.4
26.8
55,9
12.5
25,9
ApproxAR2200.33
29.7
70.5
66.1
A Approx (021.
76.2
5.9
29.9
72.1
11.7
29.2
66.9
14.7
28.1
62.1
15.0
26.9
56.1
13.6
25.5
ApproxAR2L(0.7)
73.0
7.0
28.8
70,1
9.5
29.2
65.4
11.1
28.4
61.0
10.7
27.9
56.2
8.4
27.1
ApproxAR2L(1..0)
29.9
15.4
28.1
22.5
CPPO
75.2
7.7
29.3
69.9
13.1
28.2
63.8
15.2
26.8
$8.0
15.7
25.2
$2.3
13.3
23.9
RARL
73.2
7.2
28.7
70.3
9.1
28.7
67.2
10.9
28.4
63.1
12.4
28.0
5%.7
11.0
27.5
ExactAR21.00
30.1
71.4
29.3
26.5
ExactAR2L(005)
77.7
5.8
30.3
72.0
11.9
29.3
68.0
13.8
28.8
61.2
15.4
27.2
$5.0
13.3
26.0
FxactAR21.0077
76.5
7.5
30,0
71.5
13.4
29.0
66.4
14.8
28.0
62.0
14.5
26.7
56.3
12.3
25.6
ExactAR2L(1.0)
16.6
30.0
71.7
10.8
67.7
27.6
RIMDP
73.6
8.0
29.0
68.4
12.8
29.1
62.2
15.0
28.9
58.2
14.7
29.2
54.1
12.5
29.6
Approx (0.3)
75.4
7.3
29.5
69.9
12.3
29.4
65.5
13.5
29.2
59.3
13.2
28.0
54.5
10.6
27.5
(proxAR2L(0.5)
29.6
10.6
29.5
65.2
29.4
AgproxAR2L(0.7)
74.6
7.5
29.2
70.2
10.3
29.1
65.0
11.9
28.8
60.6
11.5
28.6
55.8
8.0
28.6
AppLoxAR22.(1.0
73.5
7,5
29.1
69.1
10.2
29.0
65.0
12.4
29.3
60.4
11.6
29.0
55.8
8.8
29.2
PCT
77.0
5,5
30.1
68.4
17.0
28.6
59.7
19.3
27.0
50.9
18.2
25.5
41.9
12.2
24.2
CPPO
27.9
59.1
RARL
72.0
28.4
68.6
9.4
29.1
64.6
10.6
29.3
61.7
10.0
30.0
58.7
8.4
30.4
ExactAR21.0.33
76.7
6.7
30,0
70.8
13.3
29.4
65.6
15.8
28.9
59.4
16.3
28.0
$2.7
14.3
27.4
ExactAR2L(0.55)
30.1
70.0
14.3
30.2
64.7
30.6
30.8
ExactAR2L(0.77
76.3
30.0
71.1
11.4
29,6
66.2
14.1
29.3
61.9
29.2
57.0
12.3
28.8
ExacAR22((10)
76.1
7.3
30.0
70,9
118
29.4
66.7
12.7
29.0
62.8
12.6
28.6
58.5
10.3
28.2
RIMDP
73.8
7.0
29.0
69.4
11.0
26.6
64.7
13.3
24.2
59.4
15.1
21.5
54.4
13.0
19.2
Approx LR)
29.8
70.3
12.1
30.4
64.1
14.1
57.7
31.0
$1.7
6.7
31.5
ApproxAR2L(0..5
75.0
7.6
29.5
70.1
12.2
30.1
63.9
15.4
30,5
58.8
14.4
30.7
53.1
11.7
31.1
ApproxAR2L.0 (2)(0.7)
74.1
6.9
29.0
68.9
10.8
29.3
64.0
11.9
30.0
59.4
11.3
30.4
54.1
7.1
30,5
Approx (1.))
28.9
68.2
13.2
28.7
57.6
12.9
28.8
where NB = 5, the distribution deviation between the perturbed data and the nominal data (B = 0) is comparatively minimal. This indicates that increasing the value of a and incorporating more challenging instances into the training settings of the nominal dynamics is an acceptable approach. By doing so, the generalization of the model can be enhanced, allowing it to handle wider range of scenarios. However, the distribution deviation between the perturbed data and the nominal data (3 0) increases the number of observable items inereases. In such cases, it becomes less desirable to significantly increase the value of a. As a result, in the cases of NB = 10 and Ng = 15 under
3 0, ExactAR2L tends to favor 0.5. Furthermore, in the scenario of NB 20, ExactAR2L
space 3 Sotaasiion
ppecee wtllicciiiiioooo
70
to
1.
10 MAN
ppace
40 60 120 120 tteaatoos(x2000)
60 120 120
2000
(a) NB 15
(b) Ng 20
(c) No
5.
1.0 (d)
No 10, 0.5
Figure 3: ((a) 3 depict the learning curves of robust RL algorithms for nominal problem instances.
3 ((d) show the influence of p on the performance of the ApproxAR2L algorithm.

---

cannot outperform PCT due to the larger distribution deviation caused by the increased number of observable items of the attacker. In a word, by including perturbed data with a small deviation from the nominal data during training, the enhanced generalization leads to the performance improvement in nominal cases (3 = 0). Conversely, the large distribution deviation between the perturbed data and the nominal data can degenerate the performance in nominal cases, as indicated by the RARL algorithm. We also observe that as the value of 3 increases, the ExactAR2L algorithm tends to favor a larger value of a. Furthermore, the Approx.RR2L algorithm exhibits a similar performance tendency in both nominal and worst-case scenarios as the ExactAR2L algorithm. Due to the introduced value estimation error, the ApproxAR2L algorithm cannot perform as well as the ExactAR2L algorithm. Despite this, the ApproxAR2L algorithm still performs better than its baseline model, the RIMDP algorithm. Additionally, as demonstrated in Figures ((a) 3(b) the ExactAR2L algorithm can learn faster than other robust RI. algorithms.
Std. As shown in Table 2 ExactAR21. demonstrates its superiority over PCT with smaller Std. in 17 tasks, while producing a slightly larger Std. in tasks. Thus, ExactAR2L can indeed improve the robustness. Furthermore, we observe when NB 5. 10. ExactAR2L tends to choose 0.7 for smaller Std.. On the other hand, for NB = 15, 20, ExactAR2L favors a = 1.0. Since ExactAR2L is trained on both nominal and worst-case dynamics, while RARL is trained only on the worst-case dynamics, the ExactAR2L policy is less conservative than the RARL policy. While the conservativeness may result in smaller Std. in most tasks, it produces worse results in terms of Uti. under the nominal dynamics. It is worth noting that the value of Std. from ExactAR2L is the closest to that of RARL. This observation shows ExactAR2L can trade off between conservative and risky behavior, as the Std. from ExactAR21 is between that of RARL and PCT. Similarly, Approx is less conservative than RfMDP, which causes Approx AR2L cannot achieve smaller Std. in all tasks.
N Num. The ExactAR2L(1.0) algorithm can pack more items in 17 tasks compared to PCT, and shows slight drop in 3 tasks, where the average drop is 0.2. We found that to pack more items, ExactAR2L consistently favors a = 1.0 across various tasks. Compared to RARL, ExactAR2L(1.0) can pack at least the same number of items in 16 tasks. Thus ExactAR2L(1.0) can produce competitive results compared to RARL and PCT in terms of N Num.. Compared to the baseline method RIMDP, (pproxAR2L(0.55) can pack more items in 16 tasks, and shows slight drop in only 4 tasks, where the average drop is 0.25.
Hyperparameter Configurationss Based on observations from Table a = 1.0 is the best choice for ExactAR2L, across different test settings. When B = 50, 75, ExactARR1L(1.0) performs the best compared to baselines and ExactAR2L with other values of a (with slight drop compared to ExactAR2L(0.7) when = 50, NB = 15). If 3 100, ExactAR2L(1.0) can still produce competitive results compared to RARL and significantly outperforms PCT. When 3 = 25, although a = 1.0 is not the optimal choice, ExactAR22(1.00 can still outperform other baselines. When 3 = O, ExactAR2L(1.0) significantly outperforms RARL, and the slight drop compared to PCT is acceptable, as our goal is to improve the robustness while maintaining average performance at an acceptable level. p is only used in ApproxAR2L algorithm. As shown in Figures ((c) 3(d]
choose different values of p in different settings. We found that p = 0.1 is a trustworthy choice for ApproxAR21. Based on the observations from Table Tan and Figures ((c) [(d] we conclude that م = 0.1 and 0.5 are the best choice for ApproxAR21., as it outperforms its corresponding baseline in almost all the tasks.
6 Conclusions and Limitations
In this work, we propose novel reinforcement learning approach, Adjustable Robust Reinforcement Learning (AR2L), for solving the online 3D Bin Packing Problem (BPP). AR2L achieves a balance between policy performance in nominal and worst-case scenarios by optimizing a weighted sum of returns. We use a surrogate task of identifying a policy with the largest lower bound of the return to optimize the objective function. We can seamlessly bridge AR2L into the RARL and RIMDP algorithms to obtain exact and approximate AR2L algorithms. Extensive experiments show that the exact AR2L algorithm improves the robustness of the packing policy while maintaining acceptable performance, but may introduce additional computational complexity due to the mixture-dynamine model. The approximate AR2L algorithm estimates values without samples from the mixture dynamics, yet performance is not up to our exact AR2L agent due to the existence of estimation error. Though our AR2L. framework designed for online 3D-BPP, can be also adapted to other decision-male making tasks. We will investigate more efficient and generalizable AR2L framework.
10

---

Acknowledgments and Disclosure of Funding
We appreciate the anonymous reviewers, (S)ACs, and PCs of NeurIPS2023 for their insightful comments to further improve our paper and their service to the community. We would like to thank the Turing Al Computing Cloud (TACC) (Xu et al. 2021 and HKUST iSING Lab for providing us computation resources on their platform.
References
Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017). Constrained policy optimization. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 22-31. PMLR.
Behzadan, V. and Munir, A. (2017). Whatever does not kill deep reinforcement learning, makes stronger. arXiv preprint arXiv: 1rXiv:1712.09344
Chazelle, B. (1983). The bottomn-left bin- packing heuristic: An efficient implementation. IEEE Transactions on Computers, 32(08))697-707.
Choo, J., Kwon, Y.-D., Kim, J., Jae, J., Hottung, A., Tierney, K., and Gwon, Y. (2022). Simulation- guided beam search for neural combinatorial optimization. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances in Neural Information Processing Systems.
Chow, Y., Ghavamzadeh, M., Janson, L., and Pavone, M. (2017). Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 181))6070-6120.
Crainic, T. G., Perboli, G., and Tadei, R. (2008). Extreme point-based heuristics for three-dimensional bin packing, Informs Journal on computing, 20(3):368-384
de Castro Silva, J., Soma, N., and Maculan, N. (2003). A greedy search for the three-dimensional bin packing problem: the packing static stability case. International Transactions in Operational Research, 10(2):141-155 141-153.
Ding, W., Shi, L., Chi, Y., and Zhao, D. (2023). Seeing is not believing: Robust reinforcement learning against spurious correlation. arXiv preprint vxXiv:230.007007
Elhedhli, S., Gzara, F., and Yildiz, B. (2019). Three-dimensional bin packing and mixed-case palletization. INFORMS Journal on Optimization, 1(4):323-352.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville. A., and Bengio, Y. (2020). Generative adversarial networks. Communications of the ACM, 63(11):139-144
Gzara, F., Elhedhli, S., and Yildiz, C. (2020). The pallet loading problem: diree-dimensional bin packing with practical constraints. European Journal of Operational Research, 287(3):1022-1074
Ha, C. T., Nguyen, T. T., Bui, L. T., and Wang, R. (2017). An online packing heuristic for the dinee-iimesioonal container loading problem in dynamic environments and the physical internet. In Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part 20, pages 140-155. Springer.
Hiraoka, T., Imagawa, T., Mori, T., Onishi, T., and Tsuruoka, Y. (2019). Learning robust options by conditional value at risk optimization. Advances in Neural Information Processing Systems, 32.
Ho, C. P., Petrik, M., and Wiesemann, W. (2022). Robust phi-divergence mdps. arXiv preprint arXiv:2205. 14202.
Hu, H., Zhang, X., Yan, X., Wang, L., and Xu, Y. (2017). Solving a new 3d bin packing problem with deep reinforcement learning method. arXiv preprint arXiv:7708.05933 059300
Hu, R., Xu, J., Chen, B., Gong, M., Zhang, H.,, and Huang, H. (2020). Tap-net: transport-and-pack using reinforcement learning. ACM Transactions on Graphics (TOG), 39(6):1115
Huang, S., Papernot, N., Goodfellow, I., Duan, Y., and Abbeel, P. (2017). Adversarial attacks on neural network policies. arXiv preprint arXiv: 1702.02

---

Iyengar, G. N. (2005). Robust dynamic programming. Mathematics of Operations Research, 30(2):55--280.
Jiang. Y., Li, C., Dai, W., Zou, J., and Xiong, (2021). Monotonic robust policy optimization with model discrepancy. In International Conference Machine Learning, pages 4951-4960. PMLR.
Karabulut, K. and Inceoglu, M. M. (2005). A hybrid genetic algorithm for packing in 3d with deepest bottom left with fill method. In Advances in Information Systems: Third International Conference, ADVIS 2004, lzmir, Turkey, October 20-22, 2004. Proceedings 3. pages 441-450. Springer.
Kim, M., Park, J.. and Park, J. (2022). Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances in Neural Information Processing Systems.
Kong, W. Liaw, C., Mehta, A., and Sivakumar, D. (2019). A new dog learns old tricks: RI finds classic optimization algorithms. In International conference on learning representations.
Kos, J. and Song, D. (2017). Delving into adversarial attacks on deep policies. arXiv preprint Axiv:1705.06455
Kuang, Y., Lu, M., Wang, J., Zhou, Q., Li, B., and Li, H. (2022). Learning robust policy against disturbance in transition dynamics via state-conservative policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7247-7254.
Kumar, A., Levine, A., and Feizi, S. (2021). Policy smoothing for provably robust reinforcement learning, arXiv preprint arXiv:2106. 1420..
Li, X. and Zhang, K. (2015). A hybrid differential evolution algorithm for multiple container loading problem with heterogeneous containers. Computers Industrial Engineering, 90:305-313.
Liang, Y., Sun, Y., Zheng, R., and Huang. F. (2022). Efficient adversarial training without attacking: Worst-case aware robust reinforcement learning. arXiv preprint arXiv:22/0.05927.
Lu, H., Li, Z.,, Wang, R., Ren, Q., Li, X., Yuan, M., Zeng. J., Yang, X., and Yan, J. (2023). Roco: A general framework for evaluating robustness of combinatorial optimization solvers on graphs. In The Eleventh International Conference on Learning Representations.
Martello, S., Pisinger, D.,, and Vigo, D. (2000). The three-dimensional bin packing problem. Opera- tions research, 48(2):256-267. 267.
Oikarinen, T., Zhang, W., Megretski, A., Daniel, L., and Weng, T.-W. (2021). Robust deep rein- forcement learning through adversarial loss. Advances in Neural Information Processing Systems, 34:26156 -61677.
Panaganti, K., Xu, Z., Kalathil, D., and Ghavamzadeh, M. (2022). Robust reinforcement learning using offline data. arXiv preprini MxXi::2088005199
Parreño, F., Alvarez-Valdés, R., Tamarit, J. M., and Oliveira, J. (2008). A maximal-space algorithm for the container loading problem. INFORMS Journal on Computing, 20(3):4
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, 7.,, Lin, 7.,, Desmaison, A., Antiga,
L., and Lerer, A. (2017). Automatic differentiation in pytorch.
Pattanaik, A.. Tang, Z., Liu, S., Bommannan, G., and Chowdhary, G. (2017). Robust deep reinforee- ment learning with ad adversarial attacks. arXiv preprint arXiv:
Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. (2017). Robust adversarial reinforcement PMLR.
learning. International Conference on Machine Learning, pages
Qiu, R., Sun, Z., and Yang, Y. (2022). DIMES: differentiable meta solver for combinatorial optimization problems. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances in Neural Information Processing Systems.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.063.
12

---

Seiden, S. S. (2002). On the online bin packing problem. Journal of the ACM (JACM), 6955).640-671
Shapiro, A. (2017). Distributionally robust stochastic programming. SIAM Journal on Optimization, 27(():2258-222 2275.
Shen, Q. Li, Y., Jiang, H., Wang, Z., and Zhao, (2020). Deep reinforcement learning with robust and smooth policy. In International Conference Machine Learning, pages 8707-8718. PMLR.
Song, S., Yang. S., Song, R., Chu, S., Zhang, W., et al. (2023). Towards online 3d bin packing: Learning synergies between packing and unpacking via drl. In Conference on Robot Learning, pages 1136-1145, PMLR.
Sun, Y., Zheng, R., Liang, Y., and Huang, F. (2021). Who is the strongest enemy? towards optimal and efficient evasion attacks in deep rl. arXiv preprint arXiv:2106.05087
Tang, Y. C., Zhang, J., and Salakhutdinov, R. (2019). Worst cases policy gradients. arXiv preprint arXiv:1911.036
Tessler, C.,, Efroni, Y., and Mannor, S. (2019). Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pages 1225-4224. PMLR.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, E.., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing
systems, 30.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. (2017). Graph attention networks. arXiv preprint arXiv:1710. 10903.
Verma, R., Singhal, A., Khadilkar, H., Basumatary, A., Nayak, S., Singh, H. V., Kumar, S., and Sinha, R. (2020). generalized reinforcement learning algorithm for online 3d bin- bin-packing. arXiv preprint arXiv:2007.00463
Wang. F. and Hauser, K. (2019). Stable bin packing of non-convex 3d objects with robot manipulator. In 2019 International Conference on Robotics and Automation (ICRA), pages 8698-8704. IEEE.
Wang, F. and Hauser, K. (2020). Robot packing with known items and nondeterministic arrival order. IEEE Transactions Automation Science and Engineering, 1944)_1901-1115
Wang, Y. and Zou, S. (2021). Online robust reinforcement learning with model uncertainty, Advances in Neural Information Processing Systems, 34:7193-7206
Wang, Y. and Zou, S. (2022). Policy gradient method for robust reinforcement learning. In Interna- PMLR.
tional Conference on Machine Learning, pages
Xu, K., Wan, X., Wang, H., Ren, 7., Liao, X., Sun, D., Zeng, C.,, and Chen, K. (2021). Tace: A full- stack cloud computing infrastructure for machine learning tasks. arXiv preprint 10.01156..
Yang, Z., Yang, S., Song, S., Zhang, W., Song, R., Cheng, J., and Li, Y. (2021). Packerbot: Variable- sized product packing with heuristic deep reinforcement learning. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5002-5008. IRRE.
Ying, C., Zhou, X., Su, H., Yan, D., Chen, N., and Zhu, J. (2022). Towards safe reinforcement learning via constraining conditional value-at-risk. arXiv preprint arXiv:2206.04436.
Yuan, J., Zhang, J., and Yan, J. (2023). Towards solving industrial sequential decision-making tasks under near-predicn preripredicttale dynamics via reinforcement learning: an implicit corrective value estimation approach.
Zhang, H., Chen, H., Boning, D., and Hsieh, C.-J. (2021). Robust reinforcement learning on state observations with learned optimal adversary. arXiv preprint arXiv:2101.0844
Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D., and Hsieh, C.-J. (2020). Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33:21024-21037.
13

---

Zhao, H., She, Q., Zhu, C., Yang, Y., and Xu, K. (2021). Online 3d bin packing with constrained deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pages 741-749.
Zhao, H., Yu, Y., and Xu, K. (2022a). Learning efficient online 3d bin packing on packing configura- tion trees. In International Conference on Learning Representations.
Zhao, H., Zhu, C., Xu, X., Huang, H., and Xu, K. (2022b). Learning practically feasible policies for online 3d bin packing. Science China Information Sciences, 65(1):112105.
14

---

A Appendix
A.1 Experiment
In addition to results in the discrete setting presented carlier in the main texts, this section focuses on introducing additional results in the continuous setting. For the continuous setting, the container size 8 d E {xr V, } is fixed at 1, and the sizes of items s d E {z.y} y} follow a continuous uniform distribution U (0.1, 0.5). To prevent impractical scenarios where packed items cannot form supportive plane for incoming items, the sf dimension of each item is uniformly sampled from a finite set of values {0.1, 0.2, 0.3, 0.4, 0.5) (Zhao et al. 2022a). Likewise, Each dataset consists of 3,000 problem instances, where each problem instance contains 150 items. We use three metrics to evaluate the performance of various packing strategies: Uli. represents the average space utilization rate of the bin's 's volume; Std. is the standard deviation of space utilization across all instances; N um. evaluates the average number of packed items. In the field of online 3D-BPP (Zhao et al., 2021 2022a; (Song et al., 2023), the standard deviation of space utilization across large number of problem instances (>1,000) is commonly used to assess the reliability and stability of a solver, rather than the error bar generated from multiple experiment runs (Kim et al. 2022; Choo eet al. 2022; Qiu et al., 2022). In addition, all the models are developed using Py Torch (Pazkee
et al. 2017) and trained Nvidia RTX 3090 GPU and Intel(R) Xeon(R) Gold 5218R CPU @
2.IGGHz.
A.1.1 Algorithm Robustness under Permutation-based Attacker
In the continuous setting, conduct empirical evaluations assess the robustness of four heuristic methods: deep-bottom-left (DBL) method (Karabulut and Inceoglu 2005). best-match-first (BMF) method (Li and Zhang 2015), least-surface-aree heuristic (LSAH) (Hu et al. 2017). and online bin packing heuristics (OnlineBPH) (Ha et al. (2017). In addition, we evaluated the packing configuration tree (PCT) algorithm (Zhao al. (022aa) for the DRL-based methods, other DRL-basee methods are limited to spatially discretized grid world. We also evaluate the robustness of each algorithm under varying attack capabilities by selecting different values for NB, including 5, 10, 15, and 20. Since except PCT, other methods can observe only the first item in the item sequence at each time step, the observable number of items of each packing strategy is fixed at to ensure a fair comparison between these packing strategies.
Table [ displays the performance of different packing strategies against permutations generated by their corresponding permutation- based attackers. We can see that the LSAH algorithm exhibits superior space utilization performance across various experimental settings with different values of NB. even though it does not perform as well as the OnlineBPH and DBL algorithms in the nominal dynamics. In contrast, the BMF method is the most susceptible to attacks across all settings with varying numbers of observable items used by permutation-bassee attackers. With the increase of the attack capability, the PCT algorithm consistently outperforms the heuristic methods in terms of space utilization and the number of packed items, which can be attributed to its generalizability across a large number of problem instances. Similar to the results in the discrete setting, increasing the value of NB results in more performance degradation for all methods, which suggests an opportunity to explore more challenging problem instances, and to design proper robust algorithms accordingly.
Table 1: The performance of existing methods under the perturbation in the continuous setting.
No
NB
10
NB
15
NB
20
w/o attack
Methods
(ti. Std. Num. (%)
Std. Nam. Uti (%) Std. Num. Uti.%%
Std. Num. (%)
Std. Nam.
DBL
37.8
8.7
17.3
30.7
8.3
16.1
27.1
6.5
16.1
23.0
7.0
15.9
48.3
10.5
18,6
BMF
27.5
8.6
13.3
21.6
7.3
12.5
17.4
6.5
12.0
14.1
4.7
11.0
42.1
8.2
16.4
LSAH
38.7
10.9
16.7
36.9
9.1
17.2
33.2
10.0
16.3
27.1
8.4
17.6
47.5
8.6
18.4
OnlineBPH
33.8
11.6
15.3
30.2
7.4
16.5
26.4
7.2
16.2
23.3
6.8
15.6
49.1
9.7
19.0
PCT
47.7
8.4
20.4
39.0
8.7
18.5
36.4
9.5
18.8
30.4
8.8
17.9
65.6
8.7
25.0
Figure I depicts item distributions under perturbations from different attackers using PCT packing policies in the discrete setting. Since the sizes s of items follow a uniform discrete distribution, the frequency of the sampled sizes are approximately equal, as illustrated in the leftmost bar chart in Figure It is apparent that as the number of observable items of the attacker increases, the attacker
15

---

0.25
attack
Frequench
0.2
No
0.15
No
Ne 15
0.1
Ng 20
0.05
Size
Figure Item distributions discrete settings with varying values of Ng for different attackers.
tends to select smaller items. Furthermore, as the attack capability increases, the underlying item distribution undergoes more significant changes. Therefore, in our setting, restricting the number of observable items is practical approach to create permuted new problem instances that are closer to challenging real-world scenarios, as opposed to allowing an unlimited number observable items.
In Figure 2 the item distributions from time step 1 to time step 20 are illustrated over different problem instances under perturbations from different attackers, using PCT packing policies in the discrete setting with NB = 15, 20. These item distributions not only partially reflect the problem instance distribution, but also reveal the preference of the attacker at each time step. the beginning. the attacker favors items with smaller sizes, but as the time steps increase, it tends to sample items uniformly. This variation tendency illustrates the behavior of the attacker. However, it does not necessarily imply that rearranging the item sequence in ascending order based on item volumes would be an optimal or even effective attack. As selecting smaller items intuitively reduces the likelihood of forming supportive planes for future incoming items, attackers tend to choose smaller items to minimize the space utilization of the packing policy. Therefore, essentially, the attacker aims select items that cannot be used to construct supportive plane, rather than blindly choosing smaller items. This also explains why the probability of larger items in the beginning phase does not decrease to zero in Figure 2 As shown in Figure 3 we use toy example to demonstrate that rearranging the item sequence in ascending order based on item sizes would not be an optimal or effective attack. In this example, the container sizes Sd d {x, are set to 2, and the item sequence consists of four items, denoted as = {b) 1b',b2.0 b+). The sizes of the items are as follows: b' (1 x 2 2), b² b3 (1 x 1 x 1). and b² = sequence B' = (b2 13, b1, b2} by rearranging B in ascending order based on item sizes. However, this rearrangement is not an effective attack since the optimal solution packing strategy. By comparison, moving both ba and from B to the middle between 1/2 and 1 results B", which is effective attack for achieving minimal space utilization. such a case, the packing agent cannot pack 6² into the container at the third time step.
1 x 2). We generate new item
still be obtained using
A.1.2 Performance of AR2L Algorithm
In the continuous setting, we benchmark four other RL algorithms that are adaptable to online 3D-BPP, including the packing configuration tree (PCT) (Zhao et al., (202a) method, the
cilley-Optimization (CPPO) (Ying et al. (022)) algorithm, the robust adversarial reinforcement
learning (RARL) (Pinto et al.) 2017 algorihm,, and the robust f-divergence MDP (RfMDP) (Ho
et al.) 2022 Panaganti et al. 2022) algorithm. Since both the exact AR2L (ExactAR2L) and
approximate AR2L (ApproxAR21) algorithms can adjust the value of a to develop policies that vary in their level of robustness, we use different values of 0.3. 0.5, 0.7, 1.0 to explore the robustness trends with varying values of a in this setting. Likewise, we construct mixture datasets by randomly selecting 3% nominal box sequences and rearranging them using the learned corresponding permutation- attacker for each packing policy.
Uti. Table displays the performance of different robust methods that are compatible with online 3D-BPP on datasets with varying number challenging problem instances in the continuous setting. ExactAR2L(a) represents the ExactAR2L algorithm taking different values for and similarly Ap)roxAR2L(a)). In the continuous setting, increasing the value a can lead to ExactAR2L producing more robust policies against their corresponding permutation-based attackers, as the larger value of a provides more worst-case problem instances during the training of the packing policy. However, they cannot consistently improve their performance on the nominal dynamics. As
16

---

0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
1
3
2
2
4
2
2
3
5
Frequency
0.4
0.2
0.2
0.2
0.2
0.2
5
0.4
0.4
0.4
0.4
0.4
0.2
1
3
4
1
2
4
2
4
2
5
2
3
5
Size
(a) Ng = 15
0.2
0.2
0.2
0.2
0.2
Frequency
0.4
0.4
0.4
0.4
0.4
0.1
0.4
0.4
0.4
0.2
2
5
3
5
3
1
3
2
4
0.2
0.2
0.2
0.2
0.2
5
5
3
2
Size
(b) NB 20
Figure 2: Item distribution at each time step in the discrete setting. From the top left chart the bottom right chart, it represents the item distribution from time step 1 to time step 20 in sequence.
17

---

Sequence
Packing
Step
Step
Step
Step
Item Sequence BY
Packing Process
b1
Step
Step
Packing
Step
Step 3
Figure 3: The toy example of packing processes with different item sequences.
the number of observable items of the attacker increases, there is a corresponding increase in the distribution deviation between the perturbed data and the nominal data (3 0). For the scenario when
NB 5, 10, the distribution deviation is comparatively small. Thus. it is acceptable to incorporate more challenging instances by increasing the value of 0.7. This adjustment will further enhance the generalization of the model and lead to improved performance in terms of space utilization compared PCT. By comparison, in the cases of NB 15 and NB 20, ExactAR2L tends to favor = 0.3 to produce satisfactory performance for f 0. Thus, by incorporating the perturbed data with small deviation from the nominal data during training, the generalization of the packing policy can be enhanced, leading to the performance improvement. But the larger deviation can degenerate performance the packing policy on the nominal datasets, as demonstrated RARL. Likewise to the tendency in discrete setting, the ExactAR2L algorithm prefers the larger value of a as the value of (3 increases. Furthermore, due its exact counterpart in most of tasks under the continuous setting. However, observed that in the case of NB 5, ApproxAR2L surpasses its corresponding exact counterpart in terms of performance. This could be attributed to the relatively small estimation eπror resulting from the small deviation in dynamics in this setting, where removing the mixture-dynamice model results in more stable learning process compared to the exact algorithm. In the remaining tasks, the estimation error in ApproxAR2L can result in more unstable learning, which makes the trend in performance across different values of less clear compared to the ExactAR2L algorithm.
value estimation error, Approx cannot perform as well
surprise,
St.. As shown in Table in almost all tasks, ExactAR2L with a larger value of (a 1.0) exhibits superiority over PCT in terms of Std. Thus, ExactAR2L can indeed improve the robustness in the continuous setting. However, should be noted that ExactAR2L does not consistently yield smaller values of Std. compared to RARL. This is because the ExactAR2L policy tends be less conservative than the RARL policy in the majority of tasks. Likewise, ApproxAR2L algorithm prefers larger value of to consistently achieve smaller Std. in different tasks.
N Wum. comparison PCT, the ExactAR2L(1.0 algorithm demonstrates the ability to pack more items in 19 tasks, with minor decrease observed in task. However, when compared to RARL, the (xactAR22((1.0) policy only outperforms in 9 tasks. This discrepancy can primarily attributed to the performance drop observed in the worst-case dynamics of the ExactAR21. algorithm. The ApproxAR21. policy tends to prefer a 0.7 over the RfMDP policy when it comes to packing more items across all the tasks.
18

---

Table 2: Performance of robust methods under the perturbation in the continuous setting.
Methods
B
75
Uei.(%%)
Num. Ut(.(5) Std. Num. (t(.(5E)
Std. (ti.(St)
Uti.(%%
Num.
24.8
56.4
21.0
CPPO
65.0
10.7
24.7
60.3
13.2
23.5
56.6
12.3
22.6
52.7
12.6
21.8
47.8
20.5
RARL
65.7
10.9
25.1
62.1
12.0
24.4
57.4
11.7
23.5
53.7
11.3
22.7
50.8
8.8
22.2
ExactAR21.0..3
65.9
8.8
25.3
61.6
10.7
24.2
57.7
10.5
23.3
53.5
11.5
22.4
48.9
21.3
ExacIAR2L(0.55
66.0
9.0
25,0
61.6
11.3
24,0
56.9
10.7
23.0
53.8
10.5
22.5
49.9
7.2
21.6
ExacAA22L10.7)
67.0
9.8
25.5
62.4
12.6
24.2
57.8
11.5
23.1
54.7
10.7
22.2
50.1
7,3
21.1
(1..
66.7
9,6
25.4
62.6
11.3
24,6
57.9
10.3
23.6
55.1
10.0
23.1
50.3
6.0
22.1
RIMDP
62.9
10.4
24.0
57.2
13.3
22.7
52.4
12.5
21.6
48.7
12.4
20.9
43.3
19.7
ApproxAR2L10.3
66.3
9.1
25.1
62.5
118
24.3
57.3
11.9
23.0
$2.5
11.7
22.0
48.2
7.6
21.1
Approx (0.5)
67.1
8.5
25.5
62.4
11.6
24.1
58.0
11.4
23.0
53.8
11.4
22.1
49.1
7.6
20.9
ApproxAR2L(01
67.4
25.6
63.3
10,9
24.6
58.4
11.0
23.5
54.1
22.5
49.5
21.2
ApproxAR2L(110))
64.3
9.4
24.6
60.7
11.0
23.6
57.2
11.0
22.9
53.4
11.1
22.1
49.7
8.1
21.4
PCT
65.3
9.6
24.8
$8,9
15.0
23.4
53.1
15.4
22.2
48.0
15.4
21.22
41.4
9.4
19.7
CPPO
65.5
10.5
24.9
59.0
15.1
23.9
52.3
22.7
46.1
14.0
21.7
39.9
20.7
58.6
12.1
23.6
54.7
22.5
ExactAR2L(0.3)
65.5
9.5
24.8
58.5
14.1
23.4
52.2
14.3
22.1
46.5
13.3
21.1
40.2
6.7
19.9
ExacIAR2L(0.5)
66.5
8.8
25.3
59.5
14.8
23.8
54.1
14.8
22.6
47.9
14.4
21.3
41.1
8.2
19.9
ExactAR21.00.
25.8
61.8
13,9
24.7
ExactAR2L(110)
65.9
9.5
25.0
60.6
13.1
24,3
54.4
13.3
23.2
50.6
12.6
22.7
45.3
7,9
22.1
RIMDP
62.5
8.7
23.8
55.6
13.5
22.3
50.0
13.4
21.3
45.2
12.9
20.5
39.2
7,9
19.2
ApproxAR2200.33
24.9
58.3
23.5
A AppoxAR2110.3.
65.8
9.2
24.9
59.9
14.3
23.7
54.
15.2
22.4
48.2
14.6
21.1
40.8
8.4
19.4
ApproxAR2L(0.7)
66.8
8.1
25.5
59.7
14.2
23.6
53.8
14.9
22.2
48.3
15.3
20.9
42.0
9.9
19.4
ApproxAR2L(1..0
12.5
23.7
21.9
25.0
$7.6
17.4
23.3
50.7
10.8
18.5
CPPO
64.6
10.2
24.6
57.4
17.1
23,1
50.0
17.9
21.2
42.2
17.7
19.5
33.5
10.4
17.6
RARL
62.7
8.7
23.9
$7.0
12.7
23.9
51.6
12.7
24.1
46.5
11.6
24.1
41.0
6.2
24.2
ExactAR21.00
15.0
23.7
19.2
(xac1AR2L(0.55
65.2
8,9
24.8
58.3
15.6
23,6
$2.0
16.2
22.5
44.8
16.3
21.0
37.7
11.1
19.7
FxactAR21
65.5
9.4
24.9
58.6
15.1
23,8
52.4
15.3
22.4
45.7
15.6
20.9
39.0
10.7
19.5
ExactAR2L(1.0)
59.5
15.4
24.3
52.4
22.6
10.2
21.5
RIMDP
62.8
10.2
23,9
55,3
17.0
22.5
47.9
17.8
20.9
41.4
17.0
19.5
34.5
11.9
17.9
Approx (0.3)
65.8
9.3
25.2
58.4
16.5
23,6
50.4
17.1
21.6
44.0
16.2
20.3
36.5
10.2
18.4
65.8
25.0
57.4
16.6
23.6
50.0
22.4
36.8
20.2
AgproxAR2L(0.7)
65.8
8.5
24.9
58.6
15.2
23.9
51.6
15.7
22.9
45.1
14.9
22.2
37.7
8.0
21.2
AR2....
65.5
9.3
24.8
58.2
15.2
23.4
51.6
14.9
22.5
45.4
14.8
21.33
38.2
9.8
20.2
PCT
65.8
10.1
25.0
57.6
17.4
23.3
50,7
17.5
21.9
42.8
16.5
20.1
35.9
10.8
18.5
CPPO
57.4
23.1
17.6
RARL
62.7
8.7
23.9
$7.0
12.7
23.9
$1.6
12.7
24.1
46.5
11.6
24.1
41.0
6.2
24.2
(xactAR21.0.33)
66.9
7.7
25.3
57.2
17.3
23.2
48.7
18.7
21.6
40.1
16.5
20.0
31.9
8.5
18.5
ExactAR2L(0.55
57.4
16.6
23.2
50.9
19.1
ExactAR2L(0.7)
9.1
24.8
57.7
16.1
23.4
49.9
17.5
21.8
42.9
16.9
20.5
35.3
11.3
18.7
ExacAR22L/100
64.9
9.2
24.5
58.1
15.6
23.6
51.3
17.2
22.4
44.6
16.9
21.3
37.4
12.0
19,9
RIMDP
62.8
10.2
23,9
S5.3
17.0
22.5
47.9
17.8
20.9
41.4
17.1
19.5
34.5
11.9
17,9
Approx AR
64.9
9.9
24.7
55.6
186
22.6
47.2
19.2
1944
30.9
17,3
ApproxAR2L(0.5)
65.8
10.8
25.0
57.5
17.9
23.7
49.4
19.0
22.4
41.7
17.8
21.1
32.9
8,9
19.3
(22(0.7
66.7
7.7
25.3
58.4
16.7
24.2
50.3
18.0
25.0
42.3
17.2
21.9
33.6
7.4
20.3
Approx (121
58.3
24.2
50.1
23.1
20.7
Hyperparameter Configurations. Based on the observations presented in Table 2 it can be concluded that 1.0 is the optimal choice for achieving desired balance between policy performance in both nominal and worst-case scenarios. The ExactAR2L (1.0) algorithm demonstrates competitive robustness and average performance when compared to both PCT and RARL. Compared to the baseline method RIMDP, ApproxAR2L chooses = 0.7 for the best performance.
In addition, although the convergence rate is not primary concern in evaluating the RL algorithm, we still intend to observe the trend in the learning curves across varying attack capabilities. Our ExactAR2L algorithm shows greater improvement in terms of convergence rate in both the discrete and continuous settings as the number of observable items of the attacker increases, as demonstrated clearly in Figure
A.1.3 Visualization Results
Figure g shows qualitative comparison of the visualized bin packing results obtained by the ExactAR2L, RARL, and PCT policies under the nominal and worst-case dynamics with varying numbers of observable items Ng = 15, 20 in the discrete setting. As shown in Figure ((a) 8(b) the ExactAR2L algorithm allows more smaller margin spaces in the container minimize sizes those unoccupied spaces. By comparison, the RARL algorithm attempts to create larger spaces, which may pose a risk of future items not fitting into those spaces. The visualization results of the ExactAR2I.
and PCT algorithms under their respective worst-case dynamics are depicted in Figure 8(c) and S(d)
19

---

utlizationSe
spains uu aatiatttonn
spacc utilizaion (K)
Spaae utitte ation 8
7o
30
8
(erations(x200)
(x000)
Itera (o00s(200))
Itera (x
(a) Na 5
(b) No 10
(c) No 15
(d) No 20
Figure 4: The learning curves of robust RL algorithms for nominal problem instances with different values of NB in the discrete setting.
space valizaaion5)
space vélizationn% 15
70
space celtzationns
space volizasion 18
80
Gradt 1.0 CRO
Gradkoo CPP
terations(x2200)
Ierations
terationstx200)
Ierationstxx200
(a) NB 5
(b) NB
10
(c) NB 15
(d) NB 20
Figure 5: The learning curves of robust RL algorithms for nominal problem instances with different values of Ng in the continuous setting.
One observation is that attackers designed for packing policies tend to prioritize smaller items at the beginning, a majority of smaller items likely occur the bottom of the container. In such scenario, the ExactAR2L policy prioritizes the creation of supportive planes for future items, even at the cost of producing smaller margin spaces.
A.1.4 Baselines Comparisons
Since we implement PCT with different training contigurations, we conducted a comparison between our implementation and the official implementation in this section. We conducted the comparison of the algorithms in terms of convergence rate across various values of NB. specifically NB 1, 10, 10. To ensure a fair and consistent comparison, we employed the same number of problem instances during training. Each iteration utilized fixed rollout length of 30, and we maintained constant number of 64 parallel processes throughout the experiments. As shown in Figure 6 and Figure 7 our results clearly demonstrate that our implementation exhibits faster convergence rate across different settings, considering various numbers of observable items.
A.1.5 Practicability of AR2L Algorithm
To validate the practicality of exact AR2L algorithm in real-world scenarios, we directly evaluated our model without retraining on the Mixed-iten -tem Dataset (MI Dataset) ( (Yuan et al. [023] Elheddhi al., 2019) which follows the generation scheme proposed by Elhedhli et al. (2019) for the realistic 3D-BPP instance generator. MI dataset has 10 thousand items, with 4668 species, and occurrences vary from I to 15. The pallet dimensions is set to the size often used in practice: S 120, SV 100, and 100. The results are presented in the Table
evident that in both settings of NB = 15
and NB 20, our exact AR2L algorithm demonstrates superior performance compared to PCT and
RARL across various metrics in the real-worle dataset.
Table 3: The performance of PCT, RARL and exact AR2L evaluated on the Mixed-Iten Dataset
NB 15
NB
20
Methods
(tt.(%)
Std.
Num.
(ti.(%)
Std.
Num.
PCT
48.3
8.5
48.7
10.1
16.9
RARL.
48.8
8.8
16.9
48.8
8.3
16.9
AR2I.
50.2
8.5
17.4
52.9
6.5
18.3
20

---

80
80
600
space utilization
space utilization(
space utilization!
75
75
70
65
65
65
Inolemantiiln
Inplementarion
Off Impremeetatooonn
Off Impremeniaiinn
60
60
60
40
80
120
100
140
20
60
100
140
iterations(x200)
iterations(x2001
iterations(x200)
(a) Ng
1
(b) Np = 5
(c) NB = 10
space utilization(55
space utillization())
75
75
70
ESTHArgence
CSTHRTSANCE
(terations(2200)
iterations(x2000 (x200)
(d) NB
15
(e) NB 20
Figure 6: The training curves of our implementation and the official implementation for PCT in the discrete setting.
space Atllization! (%))
space utilization (%)
70
space utilization
70
7.0
65
65
6.5
55
Inplementaiion
Inplementacion
Inolumentatin Offial Impremettaion
offical imperttttiioon
50
50
50
40
60
100
120
140
20
40
60
80
100 120 140
20
120 140 iterations(x200)
60
100
iterations
iterations
(a) No
1
(b) Ne 5
(c) NB 10
space utiliizaiion( (%)
space utilization(S:
70
55
ESTHArgence
55
ESTHATgARKE
50
(terations(2200)
(erations(x200)
(d)
Na 15
(e) No
20
Figure 7: The training curves of our implementation and the official implementation for PCT the continuous setting.
21

---

RARL
76.8%
80.8%
70.2%
72.4%
ExacIAR2L
79.755
91.0%
81.1%
7966
73.856
81.6%
(a) ExactAR2L and RARL algorithms the nominal dynamics with NA = 15.
RARL
78,0h
ExacIAR2L
04.0%
70.4%
71.5%
82.9%
81.3%
75.4%
(b) ExactAR2L and RARL algorithms in the nominal dynamics with Ng 20.
PCT
67.5%
55,3%
61.6%
69.8%
57.4%
56.4%
ExacIAR2L
ExactAR2L and PCT algorithms in the worst-case dynamics with NA 15.
PCT
51.8%
52.76
60.4%
$8.95
52.9%
61.1%
ExacIAR2L
56.056
60.0%
68.5%
75.0%
(d) ExactAR21 and PCT algorithms in the worst-case dynamics with NB 20.
Figure 8: Visualization results of various methods. The space utilization values for each sub-figure are displayed alongside respective visualization.
22

---

A.2 Proofs
Lemma 1. Acchaam al. (2017), (ppendix.10.1.1) Given a policy T(-[s), a transition model
P(-]s, a), and an initial state distribution μ(s), the discounted state visitation distribution (() under policy πt can be described as:
+ Ed.ndd)tttdssp(sssc
(1)
Theorem 1. The model discrepancy between two models can be described as d(P)|| - max,,a (P P3 a)). The lower bound for the newly defined objective is derived as follows:
27/r max (d(P")IPP) + ad(
nT,, Po) + an P") 2 (1 + o))( Pm) - (1 7)2
Given two dynamics models PI (-|s, a) and (2(,),, a), the absolute value of the difference of returns of policy can be represented
Proof.
[n( Pt) - 77T,, ) = [ (8) - (s)]l = Eamp(s) (+) - v (s)), (3)
Here, we set (v = pi (s) - p² (s), and it can be transformed as:
( Fa-- (r (8, a) F.s (V (5'))] Faaux (r(s, + Ba (VP (8'))
7 Baw (V (s')) BBan Es (a p2 (s'))
The term ! can be firstly written as:
Ea (V (s')) Eawr Bar (V (5')) By (V (s')) Eu Bu (V (s²))s))
(s')) + Emn E Ev (6') - Ba (2 (V (8))
Ey Enwa (P'(s's) (3 ()) (5')
(5)
We then derive an upper bound of the second term in Equation as:
Egsa (PP - p2 (s' a)) a))
max pp (8') (s')E (PP((s))s - p2(('1s,aa)
8
(6)
2/rl 1 Enn (sp((s)))))) - (2((1(8,a))
1 y
2 ///max Earx Drv (P* (-|s, a|ss (1)ss)
Next, Equation and can be plugged into Equation
4 written as:
27/r mmxx Enwx Drv (r
((8) < E AV()))
(7)
Thus, the expectation of (s)) can further upper bounded by: Eged_ A(s)
EEnd pi Ex 2 // Earx Drv (P' (P
1-7
=y [BNn E AV (s')) + 27/r|maxx Esrd, [E (1s.)) (8)
1-7
AV (V')) + 27/r
Sy
max (PP)
23

---

According to Lemma
Inequality can be simplified as:
27/r/max
Exsid A(s) -
max (1), + Iid, - (1=)))
8,a
(9)
Consequently, Eindd pi ((s) can be eliminated, and we can obtain:
|nt,, P') 17( P2)1 I Pe (s) -V (s)1 (=)( 27/7/max
(1- max Drv (Is((P(
(10)
For the newly defined objective function, we can introduce any unknown dynamics pm to obtain:
(T,,, Po) 17( pm) 2 maa (,T, Pd) - 1,, Pm)) max ((T, Po) + am(m, PT) (1 P)")
Drv (P) (1ss,
6;8
(11)
Drv PP a) (1s
s,a
Thus, the lower bound the objective function can be derived as:
Pm) |max
(1 7)2 (d(P=))IPo) ad(P")| (12)
where d( (22 & maxx, (P P2(11ss))
Theorem For any given policy ा and its corresponding worst-case dynamics p the adjust
Bellman operator Ta is a contraction whose fixed point is V The operator equation Ta V = V has unique solution.
Proof. For any given policy π and its corresponding worst-case dynamics p",, the adjustable robust Bellman operator Ta is defined as:
Ta V (s) ( +
sup pm EPm.
E B [ (s'),,
(13)
where the uncertainty set is defined as pm Drv (Psaa (P + aDrv P!..) S p'}.
(x.)ESxx P
Pm
{Pa,a E A(S)
For any two adjustable robust value functions V12 and V22, we have:
TTVV V2llox
max |na= a8) +7
sup pm Pp
Byc 0..
[Vi ) r(s,a) -7 sup Eg- [V(('))]
pm Pmm
max Ex-x Pm Ep
sup
Eg Pm [Vi(s')]
sup Pm Pm
Ev pm [V2(s')]
S max Eanal max Ea--
sup
Pm [i((')]
sup
E [V2(s')]
pm pP K.
Pm. Epm
[s()) - Em 2V2 [v2)))
max E
[V((')) - Vs((')Il
max E pm.. [i((') - Vs(s'))
max Ensn max Vi (s') V2(5')l
max Ennn 11 Volloo
>lVV V2lloc.
(14)
where pm.1 = argsup pm E Eg Vi(s) and s,a = arg sup Eanpm Ve(s).

---

Let us assume the existence of two different fixed points Vi and V22 for the adjustable Bellman operator. As both of these are fixed points, the following equality holds:
V
| = V/T.VV To 22
(15)
According to the proof in [4] the following inequality holds:
TTaVi - -V I >ilVi* - -V2ll=
(16)
Thus, for both Equation 15 and Equation Iquotion[Toto strictly hold true simultaneously, must be the case that VT is equal to V22
Definition 1. Let f (0, (0) + I be convex function with S() = 1. Let P and Q be two probability distributions on a measurable space. Then, the f-divergence defined as
Dy(pllQ)= = Belf( dQ dp
(17)
where dP is Radon-Nikodyn derivative.
dQ
Proposition 1. The policy evaluation of AR2L can be formulated as a constrained optimization problem. The objective is to maximize the value function over the uncertainty set pm subject to the constraint defined in pm, By representing the TV distance using the f-divergence (Shapiro) 2017).
the adjustable robust Bellman operator Ta can be equivalently written as
Ta Vo (s) Eewwarrre (r(s.
inf 1 a P2
(Benpa. (11))))
(18)
aBg-rr F. (VT p2(s'))+ 1 Ap(1 + a))]
where [z]+ denotes max(2. 2 0}, μn (s) and p2(s) are Lagrangian multipliers for each s S μ (s) + (sp2(s) holds for each s E S, and X = max, (V) ( -
Proof. The f divergeee can be utilized express the constraint defined in the uncertainty set pm as follows:
Drr (P. + DDr (Psa (s))l(")
2 S dP (dP..(s') (5s)(s')-ca 8.0 (s)))))
dP
a +
|d (UPs,(('') dP (8')l
2
5
1
/
dPs dP',a(s))
_|dPo sa + a
dP dP),o(s')
1|dP" s.a
(19)
2 dPaa(s")
2 S
dpw
8.0 (s')
2 (50 - 1IdPo 8.0 + a / (50( - 1|dP.. s,a
1
sp',
2 S
where Ç: - R4 is the measurable function. (3(s) dP()) aPo(s) measures the difference between two dynamics at each sample s E S. similarly for <.
In the policy evaluation step of the adjustable robust Bellman operator, the goal is to obtain a mixture dynamics pm that maximizes the adjustable value function while satisfying the constraint defined in Equation We hereby formulate this procedure as a constrained optimization problem, written as:
[ (s)P(ss + (s))
s.l.
(((((s))PP + (s))dP < ( (1+a)p
(20)
[ (S)) =s) a af (s)d
- (" = 0,
where the value function V is also measurable function. We use po and pa denote po and pw for brevity, p _ is the normalized radius constant, and d(z(s)) Hlz(s) 1 is
25

---

convex and lower semicontinuous function. We thus can use the Lagrangian multiplier method to solve the optimization problme 20 The Lagrangian function written as:
L( .5" (2, -1 () {
(21)
+a | [[((s) u2 + " - dd(p + Ap(11 + + p1 + u2a
The Lagrangian dual of problem 20 is
inf p22
sup L(S", 5" (2, 5
(22)
Since the measurable function space (S,, (S)), P) is decomposable, the supremum in 22 can be taken inside the integral (Shapiro 2017). that
sup L(C"; Sth .. M1. /2, Ma(s)) Js supl(V(s) M1 (a()))) Xo(
1 ta / supl(V - P2 2 [s((s) - + Ap(1 + a) + + +1+ P2a
(23)
We can observe that the two terms inside the integral are identical the definition of the conjugate function o² (v) suPxeR, {zy - o(z)). And ((x), as convex, semicontinuous function, is defined as 1 (s)s)) 1). resulting in 00(v)) (v) = max(y, 3. The dual problem can be transformed as: inf
1 inf / mV) 411 -k((s) - - AjdP -
L(,, M1, (s())) p20 (2.
1 ta max(V((s) - P2 us(ss) >A/dP=" +Ap(1 a μn 12a
(24)
We use [x]+ to represent max(x, 0} for brevity. It is then transformed as
inf S (V(()) - 11 - (a((5) + 2 ^
1
inf L(d, M1, M1, (2.11/1,333)))) x20,01 (20
1 ta / [V(()) - M2 + ualss
+ dP_ Ap(1 a) + 11 + (12 )a
2
(25)
Next, we set ps(s) = 11 Ms(s) 1/² and pb((s) p2 pss(s) 211 And we observe that \
vs E S, (s) + app(s)) = 11 - 2 + (122 aa. We thus set μ = (s) + asp(s)).
inf L(>, 11, 12, (2,
inf [ [1((s) - 11() +a [1((s) - - + Ap + a)) y
(26)
In addition, based on the analysis of the conjugate function o (y((y) in Panaganti et al. 2022). we can derive the following two incqualities:
((s) 1n (s(()) 1
V(s) 12 + (s( 1
(27)
2
We thus can obtain max, (V (s) (s), V (s) (s) 0}. Building on the proofs above, we can define the adjustable robust Bellman operator as shown in Equation T8
A.3 Pseudocode of Algorithms
The pseudocodes for both the exact AR2L algorithm and the approximate AR2L algorithm are presented in Algorithm and Algorithm 2 respectively. Note that in practice, the Kullback-Leibler (KI.) divergence adopted to constrain the deviation between distributions in the exact AR2I. algorithm.
26

---

Algorithm/ Exact AR2L Algorithm
Initialize: packing policy Ppack- permutation-basee attacker pperms mixture-dynamics model Tmixx
and their corresponding value functions Vlluuck, V Vperr
V Vimiz
Input: stationary item distribution ps;
Parameter: robustness weight a, number of observable items NR:
Output: packing policy Tpack:
for = 0 to maz iiteratio do
2: # train the
iermutaaiio-baan attacker 3: Reset the environment and observe Co, Bo ~ pbi
4: for = 0 to mar__fey do
5:
Get permuted item sequence: Bi = permm (C,, B.);
6:
Get location for by, 4 pack C, B));
7:
Pack 8/,1 into the bin, and observe C1+1, Bu+1 pb, reward pack termination d;;
8:
d2 = True then
Update perm on episode samples to maximize -E 10: end if
9:
pack,
11:
end for
12:
# train the mixture-dynamis model and the packing policy
13:
Reset the environment and observe Co, Bu ~ pb;
14:
fort 0 to maz maz_step do
15:
Get permuted item sequence: B" mixx (C,, B.); Get location for 8r 4 pack C,,, B;
16:
Pack b9,1 into the bin, and observe C.+1, Bu+1 po, reward pack, termination d,;
17:
if de True then
19:
Update mix: VTaix on episode samples to maximize
Erpack (DKz(Tmixl) (a=bber,)))) ) aDD ( perrm));
Update packk plaackk on episode samples to maximize Σ pack end if
20:
21:
22:
end for
23:
end for
A.4 Implementation Details
To implement packing policy that work in both the discretized grid world and the continuous solution space, we use the packing configuration tree (PCT)(Zhao al.) 2022a) represent the state, and employ a transformer Vaswani et al.) 2017) network as the packing policy. PCT is utilized to represent the bin configuration and available empty spaces for the most recently packed item, while the versatile transformer network is capable of handling the variable number of nodes in PCT. We adopt the same network configuration as reported in PCT for the packing policy, with the addition of positional encoding encode the position information of each item the observed item sequence.
In addition, those available spaces are generated using a heuristic method that takes into account the packing constraints and prefer- ences for the item to be packed. Specifically, in the discrete setting, we utilize the empty maximal spaces (EMSs) (Ha et al. (017)) heuris- tics to generate potential positions, and subsequently apply the same constraints used in PCT check the stability of these positions, thereby identifying the feasible positions L. In the continuous setting, we propose new heuristic methods called Intersection Points (IPs) to generate potential positions. Given the packed items the zoy plane, the intersection points are generated from the intersection of the sides of cuboid-shaped items and the bin, as shown Figure To extend this method from 2D to 3D cases, we allow candidate positions be obtained from the intersection points of the sides in the top view.
Figure 9: In the zoy plane, circles represent the potential positions generated by the IPs heuristics.
27

---

Algorithm 2 Approximate AR2L Algorithm
Initialize: packing policy paack permutation-basee attacker 7perms and their corresponding value
functions Vo" V*perm;
Input: stationary item distribution pb;
Parameter: robustness weight a, number of observable items NB;
Output: packing policy packi
1: for i = 0 to mnaz_ieeration do
2: # train the permutation
attacker
3: Reset the environment and observe Co, Bu ~ pbi
4: fort to maz __sttpppppp do
5: Get permuted item sequence: B = perrm Cr B:);
6:
Get location for b/,1 4 = pack (C,, Bi);
Pack 1/,1 into the bin, and observe C.+1, Bu+1 ~ po, reward pack termination d;;
7:
8:
if de = True then
9:
Update perm on episode samples to maximize - Ir.
10:
end if
11:
end for
12:
# train the packing policy
13:
Reset the environment and observe Co, Bo ps;
14:
for = 0 to mar_ maar_stpee do
15:
Get location for b 4 pack ( Cr2 B,); Pack b,, into bin, and observe C.+1, Br+1 ~ po. reward pack termination de;
17:
if d, = True then
Permute B,, / [0, 7] to BY, & E [0, 7] using perrm:
19:
Use 18 to compute target values for adjustable Bellman values
{C,, B₁, B,,
B,,,,, h4 r..ck de [0;
Update Tapck; paack on episode samples to maximize Σ rapack
20:
21: end if
22:
end for
23:
end for
In our implementations of both the permutation-basee attacker and the mixture-dynamics model, we utilize the transformer [Vaswani et al., 2017) network to model these policies. This choice is motivated by the variable number observed boxes in different real packing systems, as well as the dynamic changes in the number of packed items during each episode. The transformer is capable of capturing long-range dependencies in spatial data and sequential data. Specifically, we first use two independent element-wise fulle-connected (FC) layers to project heterogenous elements of the state into homogenous features. Then, the scaled dot-product attention is relied to calculate the weighted sum of features based on the relevance between given input features. Next, skip-connection operation and the dementtwwse feed-forward FC layer to obtaín the final features = (xc, x E 12 where ae R4,, Ne and æg E Rd, xdNx denote features of C2 and B, respectively, dz is the feature size, and N = No + NB denotes the variable feature number. Finally, the probability distribution over B, is described
the
IJ BB
Terrm (Brl Cr. B,) = softmax(Cremp tanh(y)),
No
(28)
drn
where ā == = EN Iz and Cremp is the temperature constant.
As the number of packed items C and the number of available feasible positions L both vary at different time steps and have irregular shapes, combine this data into one batch by filling C and L to fixed lengths of 80 and 120 in the discrete setting, and 100 and 120 in the continuous setting, respectively, using dummy elements. Each valid element in C is a vector that specifies the size and position of an item that has already been packed. Each vector in B represents the sizes of an item that has yet to packed. Each vector L contains the position of a feasible empty space that can accommodate a new item. To permute the observed item sequence, we feed both C and B to transformer network that serves as the attacker. this transformer network, the sizes of the two clement-wir wise fully connected (FC) layers are fixed at 64. Additionally, there is attention
28

---

layer with one head attention, and the sizes of the query. key, and value vectors are set to 64. The size of the element- feed-forward FC layer is also set 64, In our experiment, we utilize the PPO (Schulman et al. 2017) algorithm to effectively train the packing policy, permutation-basee model. PPO employs multiple parallel processes (64 in this case) to interact with their respective environments and collect data. The rollout length for each iteration set to 30, and the learning rate set to 0.0003, To ensure a fair comparison, we keep the same hyperparameter settings mentioned above for each of the methods that we have reproduced.
attacker, and mixture-dynanee
A.5 Related Work
Heuristic Methods. In heuristic methods proposed for solving 3D-BPP, the score function is often designed to rank item placements based on expert knowledge, which can represent the pack- ing requirements and preferences to some extent. (Ha et al.] (2017) relied on the deep-bottom-leff (DBL) KKrrbbuuut and Inceoglu, 2005) rule to sort empty maximal spaces (EMSs) (Parreño et al. 2008) for the current item. The best-match-first strategy (Li and Zhang 2015) gives priority to feasible placements that have the smallest margin for the observed item. Hu al. (2017) introduced the least surface area heuristic, which selects the maximal empty space and orientation that result in the smallest surface area. The Siigttaap-Mimmizattinn method (Wang and Hauser, 2019) favors items placement that result in the smallest occupied volume as observed from the loading direction. The maximize-accessiblle the empty space available for future, potentially large items. Despite their simplicity and effectiveness, these methods find difficulties in handling complex packing preferences and adapting to diverse scenarios for solving online BP. This is because their packing strategies rely heavily on expert experience and may not be flexible enough to accommodate different situations.
method, as described by Hu al. (2020), aims to optimize
DRL-based Methods. To further develop highly effective policies, DRL-based methods are broadly proposed by formulating the online 3D-BPP as sequential decision-making problem. In this formulation, the state usually includes the bin configuration, which contains information about both the container and the packed items, as well as the observed item the conveyor. To learn DRL-based policy, the container is discretized to represent the bin configuration, and a convolutional neural network (CNN) is served
policy (Hu et al.] 2017| Verma et al. 2020 Zhao et al. 1021 20226 Yang et al. 2021 Song et al. 2023). However, these learning-based methods only work in a grid world with limited spatial discretization accuracy, which reduces their practical applicability.
To deploy DRL-based methods on solving online 3D-BPP with continuous solution space, Zhao al. 2022a) utilized the Packing Configuration Tree (PCT) to represent the bin configuration and potential available spaces. They then employed a graph attention network (Veličković et al.) (017)) to encode the PCT and observed boxes, encode the PCT and observed boxes, and to select location from available spaces generated for the most preceding item. However, these methods often focus on optimizing average performance and do not account for worst-case scenarios.
29


Reviews:
[{"review_id": "M5asHU7dJP", "reviewer": "Reviewer_fVdw", "summary": "The paper is in the category of work that uses reinforcement learning for combinatorial optimization problems. More specifically, it focuses on the online version of the 3d-bin-packing problem (3D-BPP), and proposes a robust RL solution to address the uncertainty that arises from the permutation of an adversarial nature. At the core of their solution, Adjustable Robust Reinforcement Learning (AR2L), is 1) a new attacker that is based on permutation of the observable sequence of the items, 2) a new objective function that adjusts weights between nominal performance and worst-case performance, and 3) theories and algorithms that solve the new optimization.", "questions": "See questions in the weakness part.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ RL for combinatorial optimization is an interesting and trending topic. It can potentially draw interest from the RL/OR community.\n\n+ Robustness in 3D-BPP is a practical and important issue. \n\n+ Permutation-based attacker makes sense. \n\n+ The adjustable objective makes sense. \n\n+ The evaluation of robustness for existing methods is applausible.\n\n+ Connections of AR2L to RARA and RfMDP are interesting.", "weaknesses": "- The attacker capacity seems questionable. Because of the following reasons, the problem setting seems rather impractical. These make the formulation, theorems, and evaluation somewhat trivial. \n1) If you formulate the nature as an adversary, then the nature should have control over the permutation of the entire sequence of items that are not presented to the packing policy, not just the observable ones. \n2) Also, it seems that the evaluation assumes the packing policy only observes one item. This is a bit weired because in this case the attacker does not have any capacity. \n3) Moreover, the attacker's policy is to change only one item to the most preceding item, but the attacker should be able to change the entire permutation. This is really how the attacker makes the training robust, and evaluations should be conducted against such an attacker. \n4) Finally, the setting that the sequence of the observable items can be changed is also weired. This is because the packing agent/policy has already seen the set of observable items, you cannot suddenly change them without the notice from the packing agent. \n\n- The paper, along with its formulation, seems to be too much restricted to robustness to permutation-based attack in 3D-BPP. Do the theories/results generalize to other settings? There is a lack of discussion from that aspect. This makes the technical contribution rather limited. The paper would be stronger if it can shed light on how the algorithms are generally applicable to more combinatorial optimization problems with uncertainty.\n\n- Theorem 1: $\\gamma$ is not explained -- is it the discount factor? Isn't is assumed to be 1 in the Preliminaries section? If so, the denominator is 0. At least $1-\\gamma$ is a very small value, making the second term on the RHS of Equation (2) dominating the entire RHS. This significantly restricts the meaningfulness of Theorem 1 (a major theoretical contribution). It seems that the objective in Equation (3) makes sense by itself, but without Theorem 1 this is only a heuristic. Also, why the coefficients are thrown out in Equation (2) and turned into Equation (3) was not explained.\n\n- The empirical results are not convincing \n1) it looks like that the average performance of AR2L is outperformed by the baselines (esp. RARL) in many cases (esp. in the most challenging setting where $\\beta=100$. It is surprising that PCT is not the best even for the nominal setting ($\\beta=0$). These have not been discussed and explained. \n2) Also, although the paper is about robustness, it primarily focuses only on average performance (Uti), discussions of Std are limited even thought the results are shown. \n3) I was expecting to see some guidelines/lessons-learned from what values I should take for the hyperparameters $\\alpha$ and $\\rho$, but did not see. If I were to use the algorithms, how do I choose them? It seems that if I choose the wrong ones, I might end up with a solution that is worse than the baselines. The mysterious performances regarding hyperparas are very un-convincing.\n\nMinor issues:\n* Refereces to equations should be Equation (1), instead of 1. See e.g., Line 205. \n* A typo at the end of Equation (2). $P^0$ -> $P^w$.\n*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We appreciate your valuable feedback. However, we would like to clarify that there may be some misunderstandings regarding our settings. We would like to take this opportunity to address your concerns. Some shared concerns about AR2L's empirical performance is additionally addressed in global author rebuttal with additional results to broader RL tasks.\n\nQ1: The settings of attacker\n\n**Adversary setup**\nWe thank the reviewer for asking about the attacker capability. In the online bin packing, we assume two crucial components can control the entire item permutation, namely the item distribution and the permutation of the observable items. Since these two components are included in the environment for the packing policy, the attacker aims to change the environment parameter/setting by permuting the observable items. This setting aligns with RARL, which investigates the robustness against environment parameter changes.\n\nMost importantly, we want to emphasize that the permutation-based attacker's objective is to identify challenging instances by solely reordering the item sequence without selectively favoring specific types of items. But upon analyzing Figure 1 in Appendix, we observed that as the number of observable items increases, the attacker appears to prefer smaller items to make the instance harder. So if we do not limit the attacker's capabilities, it may trickily select certain types of items to construct harder instances, which goes against our intended goal.\n\n**Attacker capacity**\nIn section 5.1, it is important to note that the evaluated packing methods except PCT, can only observe the first item at each step. To ensure a fair comparison for the robustness evaluation, we set the number of observable items for packing policies to 1. To make the attacker effectively perturb the packing policy, *we allow the attacker to observe more items (i.e. $N_B=5, 10, 15, 20$)*, which is also aligned to changing the environment parameter/setting. Our evaluation ensures a fair comparison for the robustness studies, while also recognizing the attacker's need for more information about the item sequence to effectively perturb the packing policy in this scenario. \n\nIn section 5.2, we use PCT as the packing policy in all the algorithms, which allows the *packing policy to observe multiple items at each step*. Therefore, we set the number of observed items for both the attacker and the packing policy to be the same. It still provides a fair comparison for the robustness evaluation. In addition, although the attacker does not obtain more information compared to the packing policy, they can still effectively perturb the packing policy.\n\n\n**Attacker's permutation**\nWe thank the reviewer for bringing the setup issue out. In our designed attacker, the entire permutation is progressively changed as the time step increases. At each step, the attacker chooses to move one item from the observed items to the most preceding position. Since the attacker aims to choose the item with the highest potential to decrease the space utilization, *the entire permutation is actually altered throughout the attack*. By contrast, in the unperturbed item sequence, each item is randomly sampled and does not reduce the space utilization adversarially. Thus, the packing policy can learn to improve its robustness with the presence of item sequences progressively generated by the attacker.\n\n\n**Sequence of observed items**\nAs we mentioned earlier, the environment consists of both the item distribution and the permutation of observable items. The attacker first permutes the item sequence to change the environment, aligned to RARL. Then the packing policy packs the first item in the reordered item sequence.\n\n\nBased on these justifications, our setting of the permutation-based attacker with limited observable items aligns with practical considerations and our intended objectives. This ensures that our formulation and theorems are reasonable. By conducting a fair comparison in our evaluation, we verify the value and effectiveness of our work. It is important to note that our study provides the first comprehensive analysis of adjustable robustness by attacker training and integration, which is a nontrivial setup.\n\n\n\nQ2: The applicability of AR2L.\nTheorem 1 is general and derived from the standard MDP, and the adjustable Bellman operator in Theorem 2, is also a general operator like the robust Bellman operator. We are confident that our framework can be extended to other combinatorial optimization problems with uncertainty and applied to various RL problems beyond the scope of this study (please see global response).\n\nQ3: Theorem 1's parameter.\nWe thank the reviewer for pointing this out. $\\gamma$ is the discount factor in Theorem 1. And we want to emphasize that Theorem 1 is a general theorem. In our paper, it provides insight and guidance for estimating the lower bound of the general objective in Equation 1. Specifically, Theorem 1 suggests that to increase the lower bound of our objective, it is an option to increase $\\eta(\\pi, P^{m})$ and $-(d(P^{m}||P^{o}) + \\alpha d(P^{m}||P^{w}))$. Based on this analysis, we propose the new objective in Equation 3. We believe that this operation and objective transformation, guided by the insight from Theorem 1, is reasonable and commonly used in the field of RL. For example, in TRPO, the use of a similar coefficient can result in very small update step sizes, which is why they use the trust region constraint and discard the coefficient for practical implementation.\n\n\nQ4: Performance evaluation.\nWe apologize that due to the limited space we include the discussions about performance comparisons, metrics of $Std$ and $Num$, and the selection of hyperparameters to the global response. Please refer to the global response for details.\n\n\n### Minor Issues\nWe apologize for typos and refereces in equations and draft, and will revise them accordingly."}, {"review_id": "tXazJpOS7o", "reviewer": "Reviewer_Em3c", "summary": "This work addresses the problem of 3D bin packing problem (3D-BPP). Specifically, it develops a permutation-based attacker and subsequently proposes an adjustable robust reinforcement learning (AR2L) framework. This allows an algorithm to consider both the average and worst-case performance with the attacker, where the packing objective is a weighted sum of expected and worst-case returns over the space utilization rate. The proposed framework is integrated with prior work to develop the exact and approximate variant of the proposed AR2L.\n\n--------------------------\nI acknowledge the author's effort in the rebuttal and have made changes to the review accordingly.", "questions": "- In eqn 2, should the last term be  \\alpha d( P^m || P^w )?", "limitations": "No immediate limitations or impact raised from the novelties from this work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ This work proposes to train a novel permutation-based attacker (RL-based policy) that can re-order the sequence of the observed items to reduce the space utilization of bin packaging tasks. The permutation-based attacker is used to quantitatively evaluate a given algorithm's performance under the worst-case scenario. The empirical results show new insight into the robustness of existing works.\n \n+ This work developed an adjustable robust reinforcement learning (AR2L) approach, which learns a packing policy based on both average scenarios and worst-case scenarios. This can be achieved via a surrogate problem where an optimal policy can be identified with the maximal lower bound. \n\n+ Two forms of implementation of the AR2L algorithm are shown in this work. The exact AR2L algorithm performs better worst-case performance under the worst-case attack with additional computation to the entire framework. On the other hand, the approximate AR2L algorithm introduces estimation errors with the cost of performance drop. For both variants, it outperforms the corresponding baseline methods.", "weaknesses": "- This work shows comprehensive evaluation with different combination of \\alpa, \\beta, and N_B parameters. While this provides valuable insights, it is unclear what would be the most optimal configuration in real-world deployment since the conditions could vary across task.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere appreciation to the reviewer for acknowledging our contribution in developing the permutation-based attack method and the adjustable robust reinforcement learning algorithm. We are grateful for the feedback provided by the reviewer, and below, we address these concerns in detail. We also provide additional experimental validations and further explanations of the settings in the global response.\n\nQ1: Configurations of parameters and variables\n\nThe variables $\\beta$ and $N_B$ are used to indicate and evaluate the varying difficulty levels of problem instances used in the testing phase. Therefore, $\\beta$ and $N_B$ do not need to be tuned for best performance, and here we detail how $\\alpha$ affects the policy's performance. Based on observations from Table 2, the larger value of $\\alpha$ (i.e., $\\alpha=1$) is the best choice for ExactAR2L across different test settings. In tasks where $\\beta=50, 75$, ExactAR2L with $\\alpha=1$ performs the best compared to the baseline methods and ExactAR2L with other values of $\\alpha$ (with a slight drop compared to ExactAR2L with $\\alpha=0.7$ in the setting of $\\beta=50, N_B=15$). If $\\beta=100$, ExactAR2L with $\\alpha=1$ can still produce competitive results compared to RARL and significantly outperforms PCT. In the task of $\\beta=25$, although $\\alpha=1$ is not the optimal choice for ExactAR2L, ExactAR2L with $\\alpha=1$ can still outperform other baselines. In the task of $\\beta=0$, ExactAR2L with $\\alpha=1$ significantly outperforms RARL, and the slight drop of ExactAR2L with $\\alpha=1$ compared to PCT is acceptable, as our goal is to improve the robustness while maintaining average performance at an acceptable level. \n\nThe parameter $\\rho$ is only used in ApproxAR2L. As shown in Figures 3(c) and 3(d), we chose different values of $\\rho = 0.1, 0.2, 0.3, 0.4$ in different settings of $N_B$ and $\\beta$. We found that $\\rho=0.1$ is a trustworthy choice for ApproxAR2L. Based on the observations from Table 2 and Figures 3(c) and 3(d), we conclude that $\\rho=0.1$ and $\\alpha=0.5$ is the best choice for ApproxAR2L, as it outperforms its corresponding baseline (RfMDP) in almost all the tasks.\n\n\nWe would also like to note the AR2L algorithm has the practicality in real-world scenarios. We directly evaluated our model on the Mixed-item Dataset (MI Dataset) which follows the generation scheme proposed by Elhedhli et al. [1] for the realistic 3D-BPP instance generator. MI dataset has 10 thousand items, with 4668 species, and occurrences vary from 1 to 15. The pallet dimensions is set to the size often used in practice: L = 120, W = 100, and H = 100. The results are presented in the table below (or Table 1 in the submitted PDF file of the 'global' response). It is evident that in both settings of $N_B=15$ and $N_B=20$, our AR2L approach demonstrates superior performance compared to PCT and RARL across various metrics in the real-world dataset.\n\n\n**Table 1**: Algorithm evaluation on real-world MI Dataset\n|      |   -   | $N_B=15$ |   -   |   |   -   | $N_B=20$ |   -   |\n|:----:|:-----:|:--------:|:-----:|:-:|:-----:|:--------:|:-----:|\n|      | $Uti$ |   $Std$  | $Num$ |   | $Uti$ |   $Std$  | $Num$ |\n|  PCT |  48.3 |    8.5   |  16.8 |   |  48.7 |   10.1   |  16.9 |\n| RARL |  48.8 |    8.8   |  16.9 |   |  48.8 |    8.3   |  16.9 |\n| AR2L |  50.2 |    8.5   |  17.4 |   |  52.9 |    6.5   |  18.3 |\n\n\nQ2: Typo in Equation\n\nWe apologize for the typo in Equation (2), where the second term on RHS should be $(d(P^{m}||P^{o}) + \\alpha d(P^{m}||P^{w}))$. We will correct the references to the equations in our paper. We thank the reviewer for bringing up these concerns and questions. We hope our explanations have addressed these concerns.\n\n[1] Samir Elhedhli, Fatma Gzara, and Burak Yildiz. Three-dimensional bin packing and mixed-case palletization. INFORMS Journal on Optimization 2019.\n\n\n"}, {"review_id": "Q0SLjE2aYy", "reviewer": "Reviewer_HCvp", "summary": "This paper investigates the online three-dimensional bin packing problem (3D-BPP) and extends the PCT algorithm by proposing an adjustable robust reinforcement learning (AR2L) framework that balances the performance of policies in average and worst-case scenarios. The paper designs a permutation-based adversary and introduces an objective function that combines expected return and worst-case return with weights. A lower bound is derived to guide policy learning. The paper presents two algorithms to implement the AR2L framework, one exact that requires training a hybrid dynamics adversary, and another approximate that samples from the original dynamics and permutation-based adversary. Experiments are conducted in both discrete and continuous settings, demonstrating the effectiveness and superiority of the AR2L framework.", "questions": "1. If I understand correctly, in Table 2 of the main text and Table 2 in the appendix, each trained policy is still tested using data generated by the attacker (as the performance of the baseline algorithms varies with different beta values, indicating a change in the tested data). So, if we remove the attacker and everyone uses the same data for testing, what would be the performance of AR2L? I am very interested in the practical implications of packing policies and would like to know if the packing policy learned through adversarial training still has advantages when tested on normal data (e.g., object sizes following a uniform distribution). This inquiry is purely out of curiosity and will not affect my scoring.\n2. In the appendix, the authors mention that they failed to reproduce some PCT results. Based on my own attempt, I believe PCT is quite reliable. I suggest that the authors contact the PCT authors as they may be able to assist in successfully reproducing the results. It is possible that there are some issues related to the usage or implementation, as packing involves various complex settings that require consideration of multiple aspects, such as discrete domain, continuous domain, stability checks, and data types. The functionality of the code can be quite complex. I believe the authors of PCT will be willing to help you successfully reproduce the results, and I have sent them a message to notify them and draw their attention to possible coming inquiry emails.\n3. A quick question: I would like to reproduce the results mentioned in the paper. In the code provided, what does \"bal_policy\" represent? Does the code refer to the code for ExactAR2L or ApproxAR2L, or is there an option to switch between the two algorithms?", "limitations": "The paper only considers one type of permutation-based attacker and does not explore other possible attack methods, such as adding or removing items, modifying the size or shape of items, etc.\n\n----------------------After Rebuttal----------------------\n\nThe reviewer appreciates the author's response. However, the reviewer is still considering whether it is necessary to propose a new candidate generation method. During the rebuttal period, the reviewer downloaded the official implementation of PCT. The final test results were even higher than those reported in the PCT paper. Because the reviewer does not see a direct response in the rebuttal, holding onto this doubt, the reviewer intends to slightly lower the rating.\n\n\n\n\n", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The problem addressed in the paper is highly significant. The authors extend the state-of-the-art PCT algorithm by optimizing its worst-case performance through an adversarial approach. I also have a strong impression of the PCT work, as it intuitively and effectively solves the important online bin packing problem. It is great to see the functionality of PCT being further enhanced through this work.\n2. I appreciate the organization of the paper. The authors demonstrate a strong understanding of packing and reinforcement learning, supporting each argument with data or theory. The paper is clear, understandable, and reasonable, making it enjoyable to read.\n3. The proposed approach is clever. The authors introduce a novel robust reinforcement learning framework, where a permutation-based adversary is designed to generate worst-case problem instances. This is an innovative and practical method. Additionally, the paper derives a lower bound for an objective function and utilizes it to guide policy learning, providing a theoretical contribution.\n4. The paper presents two algorithms to implement the AR2L framework, one exact and one approximate, catering to different scenarios and requirements.\n5. The paper conducts extensive experiments, comparing the AR2L framework with multiple packing and benchmark methods, demonstrating its advantages in terms of average performance and robustness.", "weaknesses": "The paper does not provide guidance or suggestions on how to choose the hyperparameters α and ρ. I noticed that the optimal values of α vary when β changes in the best-performing AR2L algorithm. Perhaps this could be considered as future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for recognizing our contribution in developing the permutation-based attack method and the adjustable robust reinforcement learning algorithm. We are grateful for the reviewer's valuable feedback, and we would like to address their concerns as follows.\n\n\nQ1: The settings of hyperparameters\n\nThank you for raising the concern about the hyperparameters in our AR2L framework. \nBased on observations from Table 2, the larger value of $\\alpha$ (i.e., $\\alpha=1$) is the best choice for ExactAR2L across different test settings. In tasks where $\\beta=50, 75$, ExactAR2L with $\\alpha=1$ performs the best compared to the baseline methods and ExactAR2L with other values of $\\alpha$ (with a slight drop compared to ExactAR2L with $\\alpha=0.7$ in the setting of $\\beta=50, N_B=15$). If $\\beta=100$, ExactAR2L with $\\alpha=1$ can still produce competitive results compared to RARL and significantly outperforms PCT. In the task of $\\beta=25$, although $\\alpha=1$ is not the optimal choice for ExactAR2L, ExactAR2L with $\\alpha=1$ can still outperform other baselines. In the task of $\\beta=0$, ExactAR2L with $\\alpha=1$ significantly outperforms RARL, and the slight drop of ExactAR2L with $\\alpha=1$ compared to PCT is acceptable, as our goal is to improve the robustness while maintaining average performance at an acceptable level. \n\n\nThe parameter $\\rho$ is only used in ApproxAR2L. As shown in Figures 3(c) and 3(d), we chose different values of $\\rho = 0.1, 0.2, 0.3, 0.4$ in different settings of $N_B$ and $\\beta$. We found that $\\rho=0.1$ is a trustworthy choice for ApproxAR2L. Based on the observations from Table 2 and Figures 3(c) and 3(d), we conclude that $\\rho=0.1$ and $\\alpha=0.5$ is the best choice for ApproxAR2L, as it outperforms its corresponding baseline (RfMDP) in almost all the tasks. In the main text, we will justify more on the choices of hyperparameters, and will also investigate a more integrated way for adjusting these parameters in robust reinforcement learning settings.\n\n\nQ2: The setting of testing data and testing on normal data\n\nThank you for your insightful feedback regarding the experiment section. In Table 2, the column for $\\beta=0$ indicates that all the algorithms were exposed to the same dataset from the nominal dynamics, while for other $\\beta$ values, we construct mixture datasets by randomly selecting $\\beta\\%$ nominal box sequences and reordering them using the learned permutation-based attacker for each packing policy. We observed that in all tasks where $\\beta=0$, ExactAR2L with $\\alpha=1$ outperformed RARL, as RARL was too conservative to handle instances from the nominal dynamics. When compared to PCT, ExactAR2L with $\\alpha=1$ showed a slight drop in space utilization in the $\\beta=0$ tasks. This was because ExactAR2L had to consider instances from both the nominal and worst-case dynamics. If the deviation between the perturbed problem instance distribution and the nominal distribution was too large, the performance of ExactAR2L in the nominal dynamics would be degraded. However, when such deviation was constrained in an acceptable range, the training instances were diversified due to the mixture-dynamics attacker, improving the generalizability of the packing policy and resulting in better performance compared to PCT.\n\n\nQ3: Regarding the setting and implementation of PCT\n\nThank you for expressing your concerns regarding the implementation of the baseline method PCT. After reproducing it, we found that we could only obtain good results in the discrete settings with default hyperparameter settings. However, despite trying different hyperparameter configurations, we failed to reproduce the results as reported in PCT for the continuous setting. Therefore, we decided to propose a new heuristic method, the Intersection Point heuristic, to generate candidate locations in the continuous setting. And please refer to our Appendix 1.4 for more details on the Intersection Point heuristic. This approach provided satisfactory results for us. We appreciate your suggestions and will contact the authors of PCT to reproduce their results.\n\n\nQ4: Code naming\n\nWe apologize for the confusion caused by the naming conventions used in our code. To clarify, in our code, \"BPP_policy\" refers to the packing policy, \"adv_policy\" corresponds to the permutation-based attacker used for the worst-case dynamics, and \"bal_policy\" corresponds to the mixture-dynamics attacker. Thank you for asking about reproducing our work.\n\n\n\nQ5: Implementation of other possible attacks\n\nThank you for expressing your interest in extending our framework. The main focus of our paper is on the robustness against permutation-based attackers. And in practice, such permutation is happening and has to be considered for improving algorithm robustness. Other types of attack methods like you suggested could be explored in future work to study the extendibility of our method. "}, {"review_id": "4FtiulDY1o", "reviewer": "Reviewer_HsT1", "summary": "For solving the online 3D Bin Packing Problem (BPP), the authors employ an iterative procedure to search for relevant hybrid dynamics and refine their corresponding strategies. By optimizing the weighted sum of returns, AR2L algorithm which improves the robustness of the packing policy achieves a balance between nominal insurance performance and worst case insurance performance. ", "questions": "1.\tFor Figure 2, it should be ensured that the positions of the same modules remain unchanged, and the comparison changes should be highlighted, so as to achieve of the exact and approximate AR2L algorithm\n2.\tThe relationship between offline and online BPP introduced by introduce should be clarified, if not needed, offline should be deleted. Because the whole article does not focus on online BPP\n3.\tAt the same time, please supplement the experimental part in weaknesses\n", "limitations": "due to the mixture-dynamics attacker, it will introduce additional calculations to increase complexity. At the same time for the latency of the whole process will be increased as well.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In experiment, the authors evaluate the robustness of six heuristic method. Moreover, this paper gives the exact AR2L algorithm and Approximate AR2L algorithm which has positive results. This two part of solving online 3D Bin Packing Problem has been proved to have relatively good results theoretically and experimentally.", "weaknesses": "Experimentation is not sufficient. Continuously valued perturbations for addition may not correspond to distributions in the physical world. Is there any difference between the response of the baseline to the disturbance of these continuous values and the method in the paper to the disturbance of these continuous values. Whether there is a simulation or a robotic arm, a demo for dealing with extreme situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our gratitude to the reviewer for providing valuable feedback. We appreciate the reviewer's insights, and we would like to address the concerns raised. \n\n\nQ1: Illustration of schematic figure \n\nThank you for your valuable suggestions. We agree that it can make the comparison in Figure 2 more clear, and we appreciate your feedback. We will refine the two schematic diagrams in Figure 2 to better align with your suggestions.\n\n\nQ2: Offline and online BPP \n\nThank you for your feedback regarding the introduction of the relationship between offline BPP and online BPP in our paper. We appreciate your input and understand your point that our focus is on the online BPP rather than the offline BPP.\n\nWe included a brief introduction to the background of offline BPP as it is the foundation of the online BPP. However, we understand that it may not be directly relevant to the main focus of our paper. Therefore, we will refine this section as per your suggestion to streamline the paper and better align with our focus on the online BPP.\n\n\nQ3: Experiments on continuously valued perturbations\n\nThank you for your comments on the experiment section. Since the main focus of our paper is the *perturbations from the permutation of item sequence in the online 3D-BPP*, and we also considered that adding continuous-value noise may not correspond to real-world perturbations, given that the state is defined by the bin configuration and the currently observed item sequences. Therefore, we did not conduct experiments on continuously valued perturbations in our paper. However, we recognize the value of such experiments in extending our framework and better understanding the robustness of learning-based policies. As such, we supplement our paper with an additional experiments on continuously valued perturbations, as per your suggestion. Please refer to the global response for detailed simulation results.\n\nIn this experiment, we examine the performance of three different approaches, namely PPO, RARL, and our AR2L method. We conduct this study in the CartPole environment, where we introduce the continuously valued perturbation to the \"gravity\" parameter to investigate the robustness. The robustness to changes in the 'gravity' parameter is a well-established aspect of robust RL [1]. During the training phase, RARL trains a worst-case attacker to select a continuously valued perturbation to add to the 'gravity' parameter in the environment. On the other hand, AR2L trains a mixture-dynamics attacker to balance the worst-case dynamics derived from the worst-case attacker and the nominal dynamics. In the evaluation phase, we introduce various perturbations to the environment to test the performance of the different approaches across different settings. Please refer to Figure 1 from our submitted PDF file in the global response for the detailed experiment results. Upon analyzing the results, we observe that when larger perturbations (larger absolute x-axis values) are introduced, both AR2L and RARL consistently outperform PCT. However, as the perturbation decreases, RARL's performance shows a significant decline. On the other hand, AR2L's performance lies between that of PCT and RARL, indicating a more balanced and robust performance across varying perturbation levels.\n\nTo further validate the practicality of the AR2L algorithm in real-world scenarios, we directly evaluated our model on the Mixed-item Dataset (MI Dataset) which follows the generation scheme proposed by Elhedhli et al. [2] for the realistic 3D-BPP instance generator. MI dataset has 10 thousand items, with 4668 species, and occurrences vary from 1 to 15. The bin dimensions is set to the size often used in practice: L = 120, W = 100, and H = 100. The results are presented in the table below (or Table 1 in the submitted PDF file of the global response). It is evident that in both settings of $N_B=15$ and $N_B=20$, our AR2L approach demonstrates superior performance compared to PCT and RARL across various metrics in the real-world dataset.\n\n**Table 1**: Algorithm evaluation on real-world MI Dataset\n\n|      |   -   | $N_B=15$ |   -   |   |   -   | $N_B=20$ |   -   |\n|:----:|:-----:|:--------:|:-----:|:-:|:-----:|:--------:|:-----:|\n|      | $Uti$ |   $Std$  | $Num$ |   | $Uti$ |   $Std$  | $Num$ |\n|  PCT |  48.3 |    8.5   |  16.8 |   |  48.7 |   10.1   |  16.9 |\n| RARL |  48.8 |    8.8   |  16.9 |   |  48.8 |    8.3   |  16.9 |\n| AR2L |  50.2 |    8.5   |  17.4 |   |  52.9 |    6.5   |  18.3 |\n\n\n\nQ4: Demo of packing policy\n\nThanks for your concern regarding the demo of the packing policies. We have created a video that showcases the packing processes of the PCT policy, RARL policy, and AR2L policy in both the worst-case dynamics and the nominal dynamics. To adhere to the double-blind reviewing policy, we have submitted the video link to AC. Additionally, we have included visualized packing results in our Appendix.\n\nQ5: Additional calculations and latency of the algorithm\n\nWe thank the reviewer for bringing this out. In our conclusion and limitation section, we commented that the ExactAR2L algorithm introduces additional computational complexity *in the training phase due to the mixture-dynamics attacker*. The resulting robustness is coming from the additional training of the attacker. However, in the bin packing research community and industrial applications, the computational complexity during the inference phase is more important, as we require the packing strategy to efficiently determine the location for each item. From this perspective, AR2L does not introduce additional complexity during inference compared to RARL and PCT. \n\n\n[1] Panaganti, K., Xu, Z., Kalathil, D., Ghavamzadeh, M. (2022). Robust reinforcement learning using offline data. Neurips 2022\n[2] Samir Elhedhli, Fatma Gzara, and Burak Yildiz. Three-dimensional bin packing and mixed-case palletization. INFORMS Journal on Optimization 2019."}, {"review_id": "VDATiYcjkJ", "reviewer": "Reviewer_Ua6d", "summary": "This work proposed a novel adjustable and robust Reinforcement Learning framework for Online 3D Bin Packing task. The proposed method can achieve balance between performance and the worst-case environment.", "questions": "- Table 2 is the main result, where larger N_B and larger beta represent the harder problem, and we can see that throughout the table, the baseline RARL often achieves the best results, and the proposed Exact AR2L and Approx AR2L is inferior. What is your interpretation?\n\n- How to ensure the Approx AR2L can approximate the AR2L in the \"real-world\" setting? Since you do not perform experiments in the real world? I mean, can your added randomness correspond to a real-world robot arm use case (in some industry), and if so, what kind of distribution can characterize such randomness? I believe this must be addressed by data-driven experiments; however I do not see this in your paper. \n\n- Attacker: I understand the \"attacker\" is used to generate proper samples to train your DRL algorithm for policy improvement. However, do you have a better name for such adversarial or adversary other than an attacker, as they are used in a normal setting. If there is a true attacker of your DRL training, they will probably attack in other places the let the framework down. I understand this might be due to the term already used in the literature, I just want to not confusing the reader about technical terms.", "limitations": "There is no such limitation in this aspect for this paper.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The writing is clear, and the experimental results demonstrate that the proposed method works well compared with other RL methods for the targeted 3D Bin Packing problem.", "weaknesses": "- In the section of “Training and Evaluation Setting”, the author mentioned that they are using two different settings which are discrete and continuous. However, I did not find the table showing the experimental results using continuous setting.\n\n- The author mentioned that they use three metrics(U_ti, Std and Num) to evaluate the performance. But only the best U_ti are highlighted in Table 2. I do think the analysis for Table 2 needs more details especially for the Std and Num.\n\n- The computation complexity is also crucial for the RL algorithms. The comparison of computation complexity should be analyzed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We highly appreciate the valuable feedback provided by the reviewer. We have carefully considered these concerns, and we would like to address them in the following responses.\n\nQ1: Continuous setting results\n\nDue to space limit in the main text, for the experimental results under the continuous setting where item size follows a continuous distribution, please refer to the Appendix 1.1.2 in our supplementary material.\n\n\nQ2: Experiment results clarification\n\nWe thank the reviewer for looking into details of our algorithm performance. As illustrated in Table 2, the ExactAR2L algorithm demonstrates its superiority over PCT with smaller standard deviation (Std) in 17 tasks, while producing a slightly larger Std in only 3 tasks, which demonstrates that ExactAR2L can indeed improve the robustness of the packing policy. Since ExactAR2L is trained on instances from both the nominal and worst-case environments, while RARL is trained only on the worst-case dynamics, the resulting ExactAR2L policy is less conservative than the RARL policy. While the conservativeness of RARL may result in smaller Std in most tasks, it produces worse results when given nominal instances compared to AR2L. It is worth noting that compared to other methods, the value of Std from ExactAR2L is the closest to that of RARL. This observation tells us our ExactAR2L framework can trade off between conservative and risky behavior, as the Std from ExactAR2L is between that of RARL and PCT. Compared to the baseline method RfMDP, ApproxAR2L with $\\alpha=0.5$ has a smaller Std in half of the tasks. This is because, similar to ExactAR2L, ApproxAR2L is less conservative than RfMDP, which results in the fact that ApproxAR2L cannot achieve a smaller Std in all tasks.\n\n\nAs illustrated in Table 2, the ExactAR2L algorithm can pack more items in 17 tasks compared to PCT, and shows a slight drop in only 3 tasks, where the average drop is 0.2. We found that to achieve a higher score in terms of Num, ExactAR2L consistently favors $\\alpha=1.0$ across various tasks of different $N_B$ and $\\beta$. Compared to RARL, the ExactAR2L algorithm with $\\alpha=1$ can pack at least the same number of items in 16 tasks, and shows a slight drop in 4 tasks. We thus conclude that ExactAR2L with $\\alpha=1$ can produce competitive results compared to both RARL and PCT in terms of Num. Compared to the baseline method RfMDP, ApproxAR2L with $\\alpha=0.5$ can pack more items in 16 tasks, and shows a slight drop in 4 tasks, where the average drop is 0.25. In the revised paper, we would take the reviewer's suggestions and give more detailed and comprehensive discussions for the simulation results.\n\n\n\nQ3: Computation complexity of AR2L\n\nIn our conclusion and limitation section, we highlighted that the ExactAR2L algorithm introduces additional computational complexity in the training phase due to the mixture-dynamics attacker. However, in the bin packing research community and industrial applications, researchers are more concerned about the computational complexity during the inference phase, as we require the packing strategy to efficiently determine the location for each item. From this perspective, AR2L does not introduce additional complexity during inference compared to RARL and PCT.\n\nQ4: AR2L's performance compared to RARL\n\nThe AR2L policy is trained on instances from both the worst-case and the nominal dynamics. When evaluating the scenario of $\\beta=100$, due to the deviation between the data distributions used for training and testing, AR2L may not consistently outperform RARL. However, the objective of our paper is to *strike a balance between the policy's performance in average and worst-case environments*. As such, for $\\beta=0, 25, 50, 75$, AR2L outperforms RARL, demonstrating its superiority in achieving such balancing goal.\n\n\nQ5: Real world setting\n\nWe would like to clarify that our work focuses specifically on the bin packing problem. Our goal is to develop a packing policy that assigns a position for each item in a container to ensure the high space utilization. Our focus is not on the manipulation or locomotion of robots, which is a separate module from the location assignment problem of bin packing. The location assignment problem is commonly viewed as a combinatorial optimization (CO) problem, while robotics planning and control typically address the manipulation and locomotion of robots. In the bin packing research community, the real world data is well simulated by the item sequence environment, rather than using mujoco-like robotic environments for dynamics modeling. And we follow the exact setup as bin packing research community to *setup the environment to cover the real-world cases. Furthermore, our study is specifically designed to improve the robustness of the RL-based policy in a CO problem against the common randomness in the permutation of item sequence, rather than perturbations added to the robot arm*. We hope that this clarifies the scope of our research and the specific problem we are addressing. In addition, to validate the practicality of AR2L in real-world scenarios, we directly evaluated it on the Mixed-item Dataset (MI Dataset) [1] which follows the generation scheme for the realistic 3D-BPP instance. We apologize that due to limited space we have included the results on the MI dataset to Table 1 of the submitted PDF file of the global response. Upon analyzing the results, we observe that our AR2L approach outperforms both PCT and RARL across various metrics in the real-world MI dataset\n\n\nQ6: Naming of adversarial policy\n\nThank you for your suggestions regarding the name of the \"attacker\". We are considering using a more appropriate name to avoid any confusion.\n\n[1] Samir Elhedhli, Fatma Gzara, and Burak Yildiz. Three-dimensional bin packing and mixed-case palletization. INFORMS Journal on Optimization 2019."}]

Author rebuttal:
Dear Reviewers:

We appreciate your valuable comments and have made clarifications to all of your questions and concerns in our response. Below are some shared concerns among reviewers.

Q1: Practicability and generalizability of AR2L

To validate the practicality of AR2L in real-world scenarios, we directly evaluated our model on the Mixed-item Dataset which generates the realistic 3D-BPP instance. To assess the generalizability of AR2L, we applied AR2L to the CartPole environment. The results are presented in the submitted PDF file of the global response.
In addition, to adhere to the double-blind reviewing policy, we have submitted the link of the video demo of the packing process to AC.

Q2: Contributions of our work

In our work, we address the challenges posed by the randomness in the permutation of item sequences widely existed in online bin packing problem (BPP). To tackle this issue, we introduce the permutation-based attacker with limited capabilities. This attacker aligns with practical considerations and our research goals. To enhance the robustness of the packing policy while maintaining performance in nominal cases, we propose the AR2L algorithm based on the general theorems we derived. AR2L avoids overprioritization while also considering robustness. Our approach not only solves the BPP but also can extend to other RL problems of a more general nature.



Q3: Performance under $\beta=0$ and $\beta=100$

The AR2L policy is trained on instances from both the worst-case and nominal dynamics. When evaluating the scenario of $\beta=100$, due to the deviation between the data distributions used for training and testing, AR2L may not consistently outperform RARL. However, the objective of our paper is to *strike a balance between the policy's performance in average and worst-case environments*. As such, for $\beta=0, 25, 50, 75$, AR2L outperforms RARL, demonstrating its superiority in achieving such balancing goal.

The PCT policy is trained on instances from nominal dynamics, but it is important to note that random item permutation in the nominal dynamics can naturally produce some challenging instances. AR2L can diversify the training data by providing more challenging instances with various patterns. If instances are only generated from the nominal dynamics, challenging instances may be overwhelmed by moderate instances. By training on the diversified instances from AR2L, the policy can improve generalization, and can effectively handle both moderate and challenging instances from the nominal dynamics ($\beta=0$). However, we also recognize that larger $\alpha$ and $N_B$ may cause a large deviation between the data distributions. But AR2L still demonstrates its superiority in the cases of $\beta=25, 50, 75, 100$. It is important to keep in mind the "No Free Lunch Rule".


Q4: Discussions about $Std$ and $Num$.

As shown in Table 2, ExactAR2L demonstrates its superiority over PCT with smaller Std in 17 tasks, while producing a slightly larger Std in 3 tasks. Thus, ExactAR2L can indeed improve the robustness. Additionally, we observe when $N_B=5, 10$, ExactAR2L tends to choose $\alpha=0.7$ for smaller Std, and when $N_B=15, 20$, ExactAR2L favors $\alpha=1$. Since ExactAR2L is trained on both nominal and worst-case dynamics, while RARL is trained only on the worst-case dynamics, the ExactAR2L policy is less conservative than the RARL policy. While the conservativeness may result in smaller Std in most tasks, it produces worse results of Uti under nominal dynamics. It is worth noting that the value of Std from ExactAR2L is the closest to that of RARL. This observation shows ExactAR2L can trade off between conservative and risky behavior, as the Std from ExactAR2L is between that of RARL and PCT. Similarly, ApproxAR2L is less conservative than RfMDP, which causes ApproxAR2L cannot achieve a smaller Std in all tasks.

We use ExactAR2L(1) to denote ExactAR2L with $\alpha=1$. The ExactAR2L algorithm can pack more items in 17 tasks compared to PCT, and shows a slight drop in 3 tasks, where the average drop is 0.2. We found that to pack more items, ExactAR2L consistently favors $\alpha=1$ across various tasks. Compared to RARL, ExactAR2L(1) can pack at least the same number of items in 16 tasks. Thus ExactAR2L(1) can produce competitive results compared to RARL and PCT in terms of Num. Compared to the baseline method RfMDP, ApproxAR2L(0.5) can pack more items in 16 tasks, and shows a slight drop in only 4 tasks, where the average drop is 0.25. In the revised paper, we would take the reviewer's suggestions and give more detailed and comprehensive discussions.


Q5: Hyperparameter selection

$\beta$ and $N_B$ are used to indicate the varying difficulty levels of data used in the evaluation. Thus, they do not need to be tuned for best performance. Based on observations from Table 2, $\alpha=1$ is the best choice for ExactAR2L across different test settings. When $\beta=50, 75$, ExactAR2L(1) performs the best compared to baselines and ExactAR2L with other values of $\alpha$ (with a slight drop compared to ExactAR2L(0.7) when $\beta=50, N_B=15$). If $\beta=100$, ExactAR2L(1) can still produce competitive results compared to RARL and significantly outperforms PCT. When $\beta=25$, although $\alpha=1$ is not the optimal choice, ExactAR2L(1) can still outperform other baselines. When $\beta=0$, ExactAR2L(1) significantly outperforms RARL, and the slight drop compared to PCT is acceptable, as our goal is to improve the robustness while maintaining average performance at an acceptable level. 

$\rho$ is only used in ApproxAR2L. As shown in Figures 3(c), 3(d), we chose different values of $\rho$ in different settings. We found that $\rho=0.1$ is a trustworthy choice for ApproxAR2L. Based on the observations from Table 2 and Figures 3(c), 3(d), we conclude that $\rho=0.1$ and $\alpha=0.5$ are the best choice for ApproxAR2L, as it outperforms its corresponding baseline in almost all the tasks.

Meta-review: The paper has received mixed reviews. On the positive side, the paper has been commended for presenting a clever approach validated on an extensive set of experiments, which were confirmed by one reviewer. On the more skeptic side there have been inquiries into experimental concerns, regarding some of the choices in the adversary as well as comprehensiveness. 
The AC follows reviewer's HCvp assessment. The authors' rebuttal has been acknowledged. The AC urges the authors to take into account fVdw concerns and address them in the final publication.
Decision: Accept (poster)