Whittle Index with Multiple Actions and State Constraint for Inventory Management

Dear Reviewer,

We greatly appreciate your insightful comments and the time you took to review our manuscript. Your feedback is essential to improving our work, and here we address your concerns:

No theoretical guarantee on the proposed method is provided. It seems that the framework sits between restless bandits and multi-agent reinforcement learning (MARL). That said, the reader would wonder if any theoretical results on either restless bandits or MARL extend to the particular problem setting of this paper.

Whittle index is an effective tool for restless bandits but lacks theoretical guarantee (only asymptotic results exist). Following this line of work, we leverage the Whittle index as a tool to tackle the large-scale multi-agent system and find it is hard to obtain rigorous theoretical results. Thanks to Q1 raised by the reviewer, we obtain an asymptotic optimality result (see the response to Q1 below). We also want to emphasize that our paper aims to look for a good learning policy in practice. It would be really appreciated if the reviewer could evaluate our paper more based on the empirical performance.

It is not clear how the joint inventory level constraint is satisfied by the WIMS policy. The WIMS policy controls individual stock-keeping units separately while the only joint control is on updating the dual variable. That said, in principle, one may use any algorithm for dealing with individual units. It is difficult to convince that the WIMS policy is particularly effective for the multi-agent setting studied in this paper.

The effectiveness of the WIMS policy is based on the following principle: When each agent generates an individual unit (scalar) to indicate the maximum affordable costs the agent is willing to pay for the shared resources (e.g., the inventory capacity), these agents can be well coordinated by a global dual variable indicating the global pricing for the shared resources. Therefore, the algorithms that generate other forms of the individual units may not result in an effective strategy.

Q1: Is it possible to prove that without the joint inventory level constraint, the Whittle index-based policy of this paper achieves optimality?

Yes, we can prove this asymptotic ($L_t \to \infty$) optimality. The proof is as follows: When $L_t \to \infty$, we want to show that the WIMS policy with the global cost $\lambda_g = 0$ is optimal. This policy can be written as

$a_t^i = \sum_{\alpha < A} \mathbb{I} [ [f(s_t^i)]_\alpha \ge 0 ] + 1$

$= \sum_{\alpha < A} \mathbb{I} [ Q_0^*(s, >\alpha) \ge Q_0^*(s, \le \alpha) ] + 1$

$= arg \max_\alpha Q_0^*(s, \alpha)$

where the first equation follows the definition of the WIMS policy (Eq. 3), the second equation follows Lemma 4.5, the third equation can be derived following the definition in Eq. 2. Notice that when the capacity limit is infinite, the optimal policy should always take the action $arg \max_\alpha Q_{\lambda = 0}^*(s, \alpha)$.

Q2: Is it possible to discover and explain any connection between the setting of this paper and the MARL settings, e.g., fully competitive and cooperative settings?

Our paper considers a fully cooperative MARL setting (since all agents share the same objective) with a global constraint on the state space.

Q3: Is it possible to compare the proposed framework of this paper and the existing single-agent inventory control methods combined with dual penalization as done in this paper?

We would be grateful if the reviewer could provide additional clarification on this question. For a single agent system, using the dual penalization may not be necessary since we can adjust the policy based on the inventory excess directly. We guess the reviewer refers to the "Primal-Dual" algorithm [Chen et al 2021] mentioned in our paper. The difference between WIMSN and Primal-Dual is that Primal-Dual trains a policy network directly that is not adaptive for other constraint levels. In contrast, by leveraging the concept of the Whittle index, WIMSN trains a Whittle index network that is adaptive to different constraint levels.

Dear Reviewer qxXR,

As the author reviewer discussion period is ending soon, we sincerely thank you for the invaluable feedback. Should our response effectively address your concerns, we kindly hope that you could consider raising the score rating for our work. We will also be happy to address any additional queries or points.

Best regards,

Authors

Dear Reviewer,

We greatly appreciate your insightful comments and the time you took to review our manuscript. Your feedback is essential to improving our work, and here we address your concerns:

In this paper, the authors assume that the multiple SKUs are independent and their total inventory level cannot exceed some capacity constraint. Unfortunately, this assumption is problematic and lack of justification. For example, rewards are not only independent in large-scale systems (a large number of SKU), and the substitution effect can occur.

First, this independence assumption is widely adopted in recent studies on data-driven approaches for inventory management (e.g., [Perez et al 2021; Qi et al 2023]). People believe that the rewards/dynamics for different SKUs are largely independent in practice. As for the practical scenario where rewards/dynamics are not fully independent, we believe our solution provides a good approximate result.

Second, this independence assumption plays an important role in making the inventory management problem for large-scale systems tractable. For example, [Perez et al 2021; Qi et al 2023] can hardly account for the interdependency of different SKUs (such as the substitution effect) since modeling such interdependency calls for a simulator or hand-crafted rules that can predict counterfactual scenarios. It is still an open problem to deal with interdependency within a large-scale system.

First, this paper introduces a state constraint that must be satisfied in each time step in Section 4.1. However, WIMS is NOT guarantee to satisfy this constraint at all, and hence there is a gap between the formulated problem and the proposed solution.

Although our algorithm cannot guarantee the state constraint always holds, our empirical results show that this constraint strictly holds in most of the cases for our algorithm (see Table 1), and our algorithm incurs much less constraint violations than existing baselines From the mathematical modeling perspective, it is hard to maintain the constraint strictly when making decisions since we consider a constraint in the state space. From a practical perspective, it is unlikely to strictly prevent constraint violation (exceeding the capacity limit) w/o reducing the profitability. Specifically, there are many practical workarounds when the inventory overflows, such as clearance sale, renting additional storage space, or returning products, and these workarounds are preferable than using an overly conservative and low-profitability strategy.

Second, it is not quite clear if the proposed WIMS is asymptotically optimal or not, which is a key performance in restless bandits literature. For example, the state-of-the-art Whittle index policy is provably asymptotically optimal. However, Whittle index policy is designed for restless bandits with a constraint on the action, rather than on the state. It is not straightforward to the reviewer if the asymptotic proof of Whittle index policy can be generalized to that for WIMS.

The state-of-the-art performance guarantee for the Whittle index policy is studied when the number of arms is infinite. For our case, we can prove the optimality of the WIMS policy when the capacity limit is infinite, i.e., $L_t \to \infty$. The proof is as follows: When $L_t \to \infty$, we want to show that the WIMS policy with the global cost $\lambda_g = 0$ is optimal. This policy can be written as

$a_t^i = \sum_{\alpha < A} \mathbb{I} [ [f(s_t^i)]_\alpha \ge 0 ] + 1$

$= \sum_{\alpha < A} \mathbb{I} [ Q_0^*(s, >\alpha) \ge Q_0^*(s, \le \alpha) ] + 1$

$= arg \max_\alpha Q_0^*(s, \alpha)$

where the first equation follows the definition of the WIMS policy (Eq. 3), the second equation follows Lemma 4.5, the third equation can be derived following the definition in Eq. 2. Notice that when the capacity limit is infinite, the optimal policy should always take the action $arg \max_\alpha Q_{\lambda = 0}^*(s, \alpha)$.

Third, as discussed above, there is a gap between the problem formulation (with state constraint) and the proposed WIMS (ignore the constraint). To this end, this paper tunes the parameters of $\lambda_g$. Though empirical results are provided, it is unclear if this is theoretically sound given that there is not performance guarantee in this paper.

We acknowledge that the gap between the hard constraint in the formulation and our algorithm where the constraint is not strictly satisfied. As explained in the above response, since the transition dynamics can be arbitrary, it is hard to ensure such a state-space constraint is strictly satisfied without significantly sacrificing the profitability. Therefore, we emphasize that we should focus more on the empirical results which show that our algorithm results in a strategy that satisfies the constraint reasonably well (compared to existing baselines).

What about the computational complexity? The reviewer did not fully understand the results presented in Table 4. It seems that WIMS takes significant larger computational costs, measured in mins. Given these large numbers (mins), how could this algorithm adapt to dynamic settings?

One of the main advantages of WIMSN over the previous algorithm is that the model trained by WIMSN is applicable to different scenarios (with different number of SKUs and different capacity limits). Consequently, WIMSN only needs to train the model once and this model can result in good performance in all the scenarios (as shown in Table 1). In contrast, previous algorithms need to train separate models for different scenarios. Let us take the computational costs (measured in the training time on a same machine) of different algorithms shown in Table 4 as an example. If we aim to manage the inventory for 2k SKUs with the four possible capacity levels, we need to maintain 4 IPPO models which cost 1567+1618+1593+1548=6326 minutes to train but the WIMSN-d model only needs 2652 minutes and it outperforms the 4 IPPO models in their trained scenarios.

At last, we want to emphasize again that our paper aims to look for a good learning policy in practice. It would be really appreciated if the reviewer could evaluate our paper more based on the empirical performance.

References

• [Perez et al 2021] Perez, Hector D., et al. "Algorithmic approaches to inventory management optimization." Processes 9.1 (2021): 102.
• [Qi et al 2023] Qi, Meng, et al. "A Practical End-to-End Inventory Management Model with Deep Learning." Management Science 69.2 (2023): 759-773.

Dear Reviewer xHVA,

As the author reviewer discussion period is ending soon, we sincerely thank you for the invaluable feedback. Should our response effectively address your concerns, we kindly hope that you could consider raising the score rating for our work. We will also be happy to address any additional queries or points.

Best regards,

Authors

Dear Reviewer,

We greatly appreciate your insightful comments and the time you took to review our manuscript. Your feedback is essential to improving our work, and here we address your concerns:

There is no comprehensive exploration of the inherent limitations or challenges of using this index in a MARL context. It would be beneficial for the authors to outline specific assumptions made when integrating the Whittle Index.

In the MARL context considered in our paper, we integrate the Whittle index as a tool to decrease the effective size of the joint action space of multiple agents. The integration of Whittle index to the MARL context relies on the weak coupling problem structure mentioned in the paper, i.e., one possibly changing global constraint couples the otherwise independent dynamics of multiple agents. In other words, the independence of different agents (except the only global constraint) is the key assumption when integrating WIMS to the MARL setting.

This paper does not have details on how the dataset is partitioned into training, validation, and testing subsets. It's unclear from the given text what dataset was used for training and testing the proposed methods. This raises concerns about the generalizability and robustness of the proposed models. Are the datasets representative of real-world scenarios? Are they publicly available for verification and reproducibility?

Thanks for mentioning the dataset and we will add this information in the appendix. This dataset is provided by our partner who is a world-wide retail corporation, and thus we believe the dataset is representative of real scenarios. We will try to make the dataset public available after de-identification.

The experiments in our paper is based on the history of 2307 SKUs from 2018-08-01 to 2019-12-13. The training / validation / testing sets are set to be the subset 2018-08-01 to 2019-05-27 (300 days) / 2019-05-28 to 2019-09-04 (100 days) / 2019-09-05 to 2019-12-13 (100 days) respectively. For the experiments on 100/1000 SKUs, we sample a subset of SKUs uniformly randomly from the 2307 SKUs.

It would be helpful if the authors mentioned areas where their method (WIMSN) could be improved or further developed. By discussing potential future studies or enhancements, the authors would make their paper even more valuable.

Thanks for the good suggestion. The possible future directions are as follows: 1) Application: In principle, WIMS can solve a wider range of tasks as long as the weak coupling structure exists. For example, in portfolio management for quantitative investment, the investment on different stocks is largely independent but subject to a global constraint on the total asset. 2) Theory: Although the Whittle index usually achieves good performance in practice, it lacks performance guarantee in theory. We may try to achieve theoretical guarantee for applying the Whittle index (or its variance such as WIMS) to the MARL setting - possibly for some asymptotic case (such as the new asymptotic result where the optimality of the WIMS policy when the capacity limit is infinite, i.e., $L_t \to \infty$, is shown; see the response to Q1 of Reviewer qxXR for the proof).

The author reviewed a lot of works on the operation research and on independent learning based MARL without global constraints, and the main comparisons were made with works in 217,2018.

In the MARL field, researchers also focus on value decomposition based methods (such as VDN [Sunehag et al 2017], QMIX [Rashid et al 2020], QTRAN [Son et al 2019], and HARL [Zhong et al 2023]) and policy gradient based methods (such as MADDPG [Lowe et al 2017], COMA [Foerster et al 2018], and MAPPO [Yu et al 2022]). However, these algorithms require unaffordable computational resources in our case (with 2k+ agents). Therefore, we only compare our algorithms with independent learning based MARL algorithms in our experiments.

OR-based methods was first mentioned without explanation, should add an abbreviation after first mentioning operation research.

Thanks for pointing this out. We will revise this.

While the paper mentions computational costs and standard deviations of daily profits, are there other metrics (like fill rate, stockout rate, etc.) used in inventory management that could provide a more comprehensive view of performance?

Thanks for the good suggestion. We will provide more metrics for evaluation in the appendix. In terms of fill rate and stockout rate, we observe that they are largely correlated with the profit metric presented in Table 1.

Typo in Proposition 3.3.

Thanks for pointing it out and we will revise this.

References

• [Sunehag et al 2017] Sunehag, Peter, et al. "Value-decomposition networks for cooperative multi-agent learning." arXiv preprint arXiv:1706.05296 (2017).
• [Rashid et al 2020] Rashid, Tabish, et al. "Monotonic value function factorisation for deep multi-agent reinforcement learning." The Journal of Machine Learning Research 21.1 (2020): 7234-7284.
• [Son et al 2019] Son, Kyunghwan, et al. "Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning." International conference on machine learning. PMLR, 2019.
• [Lowe et al 2017] Lowe, Ryan, et al. "Multi-agent actor-critic for mixed cooperative-competitive environments." Advances in neural information processing systems 30 (2017).
• [Foerster et al 2018] Foerster, Jakob, et al. "Counterfactual multi-agent policy gradients." Proceedings of the AAAI conference on artificial intelligence. Vol. 32. No. 1. 2018.
• [Yu et al 2022] Yu, Chao, et al. "The surprising effectiveness of ppo in cooperative multi-agent games." Advances in Neural Information Processing Systems 35 (2022): 24611-24624.
• [Zhong et al 2023] Zhong, Yifan, et al. "Heterogeneous-Agent Reinforcement Learning." arXiv preprint arXiv:2304.09870 (2023).
• [Minh et al 2015] Mnih, Volodymyr, et al. "Human-level control through deep reinforcement learning." nature 518.7540 (2015): 529-533.
• [Schaul et al 2015] Schaul, Tom, et al. "Prioritized experience replay." arXiv preprint arXiv:1511.05952 (2015).

If the constraint is only changed once a long time like once a seasons, it seems to me that wrong those previous algorithms and re-train the model does not bring many troubles. I feel that the comparison in Figure 2 does not complete or fair enough. The author compared their adaptive algorithm with two IPPO models trained with two different capacity limits, but the author didn’t mention any training cost or training time for IPPO, so I am wondering why the IPPO users can’t re-train their models on the 50th day, since the reward was compared on a daily manner.

Our algorithm is advantageous over the previous algorithms that need re-training in the following aspects: 1) Our algorithm decouples the training phase and the deployment phase, which means that the end user of the model (e.g., the store manager accessing limited or no computational resources in practice) do not need to be involved in model training. 2) Our algorithm is adaptive to not only the changing capacity limit but also the number of SKUs, whereas previous algorithms are not adaptive to the changing capacity limit nor the number of SKUs. Adding new SKUs or delisting SKUs occurs frequently in practice. As for the comparison on the training time, the training time of our algorithms is less than 2x the training time of previous algorithms for the same number of SKUs. See details in Table 4 in the appendix.

In the neural network training phase, in the network update steps, they sample a batch of transitions from the replay buffer, could this word “batch” be more clarified? And is this replay buffer something important to computational efficient of the algorithm? What is the difference from regular learning algorithms that runs a sequence of data first and without a replay buffer?

In Phase 1 of our algorithm, we largely follow the framework of DQN [Minh et al 2015] given the similarity of Eq (4) to the TD update in DQN. Accordingly, we adopt a similar design for the replay buffer. Specifically, the capacity of the replay buffer is set to 10M and the oldest samples are removed from the buffer if it is full. For each time, we sample a batch of 16K samples uniformly randomly from the replay buffer and use these samples to train the Q-network and the Whittle index network. This naive replay buffer does not influence computational efficiency significantly, in contrast to its variants such as prioritized experience replay [Schaul et al 2015]. We adopt the replay buffer to prevent the instability issue for such off-policy RL algorithms.