Distributionally Robust Multi-Agent Reinforcement Learning for Dynamic Chute Mapping

Thank you for your insightful comments, thoughtful questions, and encouraging feedback. Your suggestions greatly improve the paper. Below are our responses, following the order of the reviewer comments, with references to tables and papers prefixed by “R-” for clarity.

We address all readability and presentation concerns in the revision.

In (1), actions are introduced as penalty to prevent MARL from over-allocating chutes to a few destinations, which could block incoming packages from other destinations. However, MARL still fails to generalize to OOD induction patterns. We will clarify this in the revision.

For small-scale problems, the observation space excludes recirculated packages, making the transition probability independent of induction $X$ and aligning with the assumptions in Lemma 3.2. For large-scale problems, as shown in Appendix C.5, the DR Bellman operator in Lemma 3.2 acts as an accurate estimator when the transition probability depends on $X$, which does not hinder DRMARL from learning an effective robust policy.

Ablation studies were performed under various warehouse layouts, primarily varying the number of chutes and unique induction destinations, which directly affect the action space and transition probability. STDs omitted due to character limits.

TABLE R-3: Relative recirculation rate improvement (↑) compared to the baseline MARL.

TABLE R-4: Relative recirculation rate improvement (↑) compared to the baseline MARL across different percentages of 120 destinations remains in the induction.

In Table R-3, DRMARL consistently outperforms MARL, demonstrating its effectiveness and robustness across different environments. In Table R-4, we examined the performance of both policies while gradually reducing the number of induction destinations. DRMARL maintained its performance, but MARL outperformed it when only 50% destinations remained. This occurs because DRMARL conservatively reserves available chutes for potential future inducts, even for destinations that have not yet appeared and may never appear with 50% destinations. In contrast, MARL aggressively allocates chutes to existing destinations without considering the risk of blocking newly inducted destinations.

Overly pessimistic decisions is a common risk in robust policies. We mitigate this by grouping induction data from multiple days rather than treating each day separately, reducing the impact of extreme outliers. Our experiments did not exhibit instability from extreme worst cases. However, if such cases arise, one can remove extreme outliers to stabilize training and switch to a heuristic policy in practice when extreme induction patterns are detected. This is a foreseeable drawback compared to MARL since the policy may become overly conservative with extreme inductions.

We compare DRMARL with 3 Robust RL (RRL) approaches: <1> an adversarial agent deliberately blocking available chutes [R-4], <2> an adversarial environment with perturbed transition probabilities [Pinto et al., 2017], and <3> a (non-distributionally) robustified reward function [Wiesemann et al., 2013]. Implementation and result details are provided in the revision. While certain robust policy (<2>) achieve comparable cumulative recirculation performance to DRMARL, DRMARL additionally guarantees improved worst-case performance by explicitly optimizing for it. To validate this, we analyze the empirical distributions of recirculated packages across all time steps and groups. In Table R-5, we report the relative reduction in both the worst-case and CVaR (5% confidence level) of recirculated packages. DRMARL outperforms all RRL due to its distribution awareness, leading to more accurate worst-case reward estimation and robust action value functions, ultimately optimizing worst-case performance. This is crucial, as sudden surges in recirculation can cause robot congestion, delaying the entire sorting process. Since congestion is not explicitly modeled in the simulation, DRMARL’s advantage over RRL is expected to be even greater in practice.

References:

[R-4] Mandlekar et al., Adversarially Robust Policy Learning: Active construction of physically-plausible perturbations, IROS 2017.

Thank you for your insightful comments and thoughtful questions. Your suggestions greatly improve the paper. Below are our responses, following the order of the reviewer comments, with references to tables prefixed by “R-” for clarity. If any referred content is missing here, please find it in the responses to other reviewers.

The proposed framework builds on existing methods, but their integration is novel and strategically bridges gaps in DRRL, particularly related to scalability for large-scale multi-agent RL problems. In the robotic sortation warehouse, the reward (recirculation) function is implicit and highly nonlinear. Consequently, unlike typical well-structured DRO formulations with finite-dimensional convex equivalent formulations, applying similar methods to the complex, large-scale chute mapping problem is infeasible. With millions of packages sorted daily, estimating the worst-case reward for each state-action pair becomes computationally impractical using existing DRRL techniques. Although group-DRO makes worst-case reward evaluation finite-dimensional, the complexity modeling of the warehouse sortation and the large number of groups render exhaustive search still infeasible. Unlike supervised learning, where soft reweighting can avoid exhaustive search, such techniques cannot be directly applied to RL, as the worst-case group and reward vary across state-action pairs. An important contribution of our work is to leverage a contextual bandit to significantly reduce the exploration cost for estimating the reward of the worst case group. This approach effectively bridges the gap in scalability and applicability.

We conducted extensive experiments for the comparison between DRMARL and naive Robust RL. Please kindly find the detailed result in Table R-5. Compared to naive Robust RL, DRMARL benefits from its distribution awareness for more accurate estimation of the worst-case reward and robust action value functions. Even certain naive Robust RL policy (<2>) achieves a comparable cumulative recirculation throughout the day, DRMARL still significantly outperforms it in terms of the step-wise recirculation amount (both worst-case and CVaR), which is the direct metric for robustness when comparing the performance of robust policies.

The proposed DRMARL framework is designed to address general RL problems where the reward function undergoes distribution shifts. Since Lemmas 3.1 and 3.2 are not specifically tailored to resource allocation problems, the framework is broadly applicable to other DRRL settings. It can also benefit large-scale RL problems with group-DRO, particularly when an exhaustive search is impractical. We see strong potential for extending this approach beyond sorting problems, as DRMARL directly addresses reward function ambiguity (i.e., environmental uncertainty). The core DRMARL framework (Algorithms 1 and 2) remains unchanged when applied to other resource allocation problems, with only the environment varying. We are currently working on extending this framework to general RL problems beyond resource allocation, with early-stage promising results, and we will report our findings in a separate manuscript.

Major e-commerce companies have publicly reported double digit growth in retail sales YoY (Year-over-Year) in their Q4 earnings press releases on multiple years which translates in the package sortation context to large swings in induction rates YoY. Due to the double-blind policy, we will provide reference in the final paper. Package volume and distribution exhibit substantial seasonal and yearly shifts. Seasonality drives fluctuations during sales events and holidays, while yearly shifts reflect evolving customer behavior and business growth. To support our claims, we quantify distribution changes using the empirical Type-1 Wasserstein Distance [R-3], as shown in Table R-2. By comparing four selected weeks to Week 1 within each year, we reveal significant seasonal variations, while the Wasserstein distance between consecutive days is typically on the order of 20. The last column highlights yearly shifts by comparing the same period across years to Year 1, showing that yearly changes are even more pronounced than seasonal ones. Figure 5 and Table R-1, evaluated on production data, demonstrate that MARL struggles with large induction pattern changes, underscoring the necessity of DRMARL.

Table R-2: The first four columns represent Type-1 Wasserstein distances for each week compared to Week 1 of the same year. The last column represents the average Wasserstein distance of each year to Year 1.

References: [R-3] Villani, Cédric. Optimal transport: old and new. Vol. 338. Berlin: springer, 2008.

Thank you for your insightful comments, thoughtful questions, and encouraging feedback. Your suggestions greatly improve the paper. Below are our responses, following the order of the comments, with references to tables and papers prefixed by “R-” for clarity. If any referred content is missing here, please find it in the responses to other reviewers.

The contraction property of the DR Bellman operator is shown in the proof of Lemma 3.2 (Line 668). We explicitly highlight this in the revision for clarity, and replace the paragraph starting from Line 681 with:

Since $\gamma \in [0,1]$, this establishes that DR Bellman operator is a contraction mapping under the $\ell\infty$ norm. By Banach’s Fixed Point Theorem [R-1], there exists a unique fixed point $\tilde{Q}^*$ such that $\tilde{\mathcal{T}}_{\mathcal{G}}(\tilde{Q}^*) = \tilde{Q}^*$. Consequently, iteratively applying the operator ensures convergence to $\tilde{Q}^*$, proving the stability of the robust Q-learning algorithm. This contraction property of the DR Bellman operator was also addressed in [R-2] when the ambiguity set is defined for transition probability.

Due to the character limit, the induction rate, in short, is a vector that contains number (integer) of packages inducted per destination and hour. A comprehensive definition of induction rate/pattern is provided in the revision.

We provide a more detailed explanation of DRO in the revision.

In this formulation, the state space $\mathcal{S}$ represents the global state, while each agent $i$ has a local observation $\mathcal{O}_i \subset \mathcal{S}$ containing partial information about the global state. The observation features are detailed in Appendix C.1, Line 739. While the state provides full system information, each agent’s observation is limited to local aspects relevant to its decision-making. This partial observability requires agents to act based on their own experiences and available information. We will refine our explanation in Line 162 to better highlight this distinction.

We place the Figure 5 near Line 176 in the revision.

Lemma 3.2 defines the DR Bellman operator, derives its explicit form for group DRO with MARL, and establishes its contraction property. Its formal definition appears in Equation (20), Line 655, with benefits discussed in Line 220. Notably, minimizing the worst-case Bellman error among groups does not necessarily yield a policy optimal under worst-case rewards. This is because the worst-case Bellman error reflects the worst-case deviation from the target Q-function but does not guarantee convergence to the optimal robust Q-function. Instead, the DR Bellman operator and its corresponding DR Bellman error ensure robustness. We refine Lemma 3.2 and the corresponding text for clarity in the revision.

In Table 1, each group is tested 100 times. STDs are omitted for table readability, and are included in the revision.

In Line 372, $X$ denotes the induction pattern (packages per destination per hour) and is a realization of a random variable following the induction generating distribution. Thus, the immediate reward function (recirculation) depends on $X$.

Convex combinations of distribution groups aim to span the space of potential induction distributions, using available distribution groups to model the space of potential target distributions is a common approach in DRO. As we collect more production data, the distribution groups will expand to better capture year-to-year shifts without increasing the DRMARL training complexity. Figure 6 shows that the robust policy generalizes well to test distributions specifically designed outside $\mathfrak{M}$ without theoretical guarantees. Its Type-1 Wasserstein distance to $\mathfrak{M}$ is 818.19, while the average distance among distributions within $\mathfrak{M}$ is 542.96.

In Figure 9, the reward is indeed increasing as the y-axis is flipped. Fixed in the revision.

The years are ordered from past to present. Year 4 was chosen arbitrarily. In Table R-1, training the MARL policy on Year 1 also results in significant performance degradation on OOD data, with similar outcomes as MARL trained on Year 4 when compared with DRMARL.

Table R-1: Relative recirculation rate degradation compared to the baseline MARL (trained on Year 1) on induction data from Year 2-3.

The detailed chute allocation action and strategy difference are omitted due to the character limit and are presented in the revision. Please kindly refer to the text under Table R-4 and Table R-5 for high-level strategy difference and step-wise recirculation outcomes between MARL and DRMARL.

References:

[R-1] Rudin, W. Principles of Mathematical Analysis (3rd ed.). McGraw-Hill, 1976.

[R-2] Iyengar, G. Robust dynamic programming. Mathematics of Operations Research, 2005.