We study multi-product inventory control problems where a manager makes sequential replenishment decisions based on partial historical information in order to minimize its cumulative losses. Our motivation is to consider general demands, losses and dynamics to go beyond standard models which usually rely on newsvendor-type losses, fixed dynamics, and unrealistic i.i.d. demand assumptions. We propose MaxCOSD, an online algorithm that has provable guarantees even for problems with non-i.i.d. demands and stateful dynamics, including for instance perishability. We consider what we call non-degeneracy assumptions on the demand process, and argue that they are necessary to allow learning.
Paper
Similar papers
Peer review
Summary
In this paper, the authors consider the classic online inventory control problem. While previous works mainly consider the case where the demand is stochastically drawn from a stationary distribution, this paper considers the case where the demand can be adversarial. In addition, the authors consider a more general framework Online Inventory Optimization (OIO), which includes many different setups in the inventory literature, i.e. censored demand / backlogged demand / perishable / non-perishable. Then, the authors proposed the algorithm MaxCOSD achieving $O(\sqrt{T})$ regret under the assumption on the lower boundedness of the demand (with constant probability). The algorithm shares similar ideas to the cyclical updates proposed in CUP [Zhang et al., 2018] but with a different definition on the cycle and an adaptive choice of learning rate. The algorithm keeps using the same base-stock level to collect enough gradient information until the time where the outcome from the (cumulative) gradient descent step gives a feasible strategy. The authors also discuss their demand assumptions and show that without lower bounded demand assumption, no deterministic algorithm can achieve sublinear regret. Experiments are also done to show the effectiveness of the algorithm MaxCOSD.
Strengths
- The problem considered in this paper is interesting and has wide applications in real life. - The proposed algorithm is clean and easy to follow. The proposed framework OIO is general and includes many different setups that are considered in the inventory literature. - Experiments on both synthetic data and real-world data are also done for their proposed algorithm.
Weaknesses
- One major concern is the novelty of the proposed algorithm. From the technical perspective, I think the analysis generally follows the classic analysis of online gradient descent with a self-confidence tuning of the learning rate in order to handle the issue raised by the scale of the gradient that may cumulate over rounds. Based on this, I think the $\sqrt{T}$ regret is not very surprising. - Several claims made in this paper may need more explanations or clarifications. - On Assumption 10, it is unclear how to transform the assumption that $\mathbb{E}[d]\geq \rho$ assumed in AIM to this assumption with the same theoretical guarantees. Specifically, with the current Assumption 10, when $\mu$ and $\rho$ is $\Theta(T^{-\alpha})$ and $\Theta(T^{-\beta})$, the regret bound becomes $T^{\frac{1}{2}+\alpha+\beta}$. It would be better if the authors can compare the guarantees of both algorithms under the same assumptions. - The lower bound analysis is problematic or not rigorous. For proposition 13, in line 601, the authors argue that $(T-T_0+1)hy_{T_0}=\Omega(T)$ , which does not hold when ${y}_{T_0}=o(T)$. Similarly, in Proposition 14, $y_1$ can also be $o(T)$ making the regret sublinear. A refined analysis on both propositions should be included. - The experiment results do not show a better performance of MaxCOSD compared to other algorithms in Settings 1-4, even though some algorithms are not designed to handle the adversarial/non-stationary demand. This weakens the motivation of providing an algorithm that performs better in the adversarial environment. In addition, for Settings 1-3, showing the error bar or the std of the algorithm would be better since the algorithm actually guarantees high-probability regret bound.
Questions
- In line 244, I do not understand why Assumption 10 with $\rho=D$ matches the assumption 1 made by CUP in [Zhang et al., 2018]. In CUP, they are assuming the knowledge of the upper bound on the optimal inventory level. - On the optimality on the parameters $\rho$ and $\mu$ in Theorem 12: I wonder whether there is lower bound on $\mu$ and $\rho$ for this problem? This may show further tightness of the obtained bound.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
See Weakness and Questions sections.
Summary
The paper studies a general online decision making problem for inventory management. The problem setting extends the generic online convex optimization by introducing structures such as states and demands. Compared to settings studied by related works in inventory management, the setting of this paper relaxes several restrictive assumptions on the loss functions, dynamics and demands. Then, the problem is solved by a new batch-update online gradient descent algorithm with an optimal regret upper bound, whose analysis relies on a geometric cycle property induced by the problem structure. The strengths and limitations of this algorithm are further demonstrated through experiments.
Strengths
Overall, this is a strong submission. - It is very well-written, with a smooth and clear coverage of the motivation, how the problem connects to classical online learning models, and the novelty of the proposed algorithm. - Related works on the inventory problem are discussed in detail. This is especially valuable since the readers are most likely from the machine learning community, who are not familiar with the necessary background. - Although I didn't check everything in the proof, the analysis is solid to my knowledge. Intuitions of the algorithm including the nondegeneracy assumption are clearly presented and natural. - Experiments are included, with both positive and negative results. The experimental methodology makes sense.
Weaknesses
I don't have much to complain in general. One aspect I'm not sure is the novelty. The backbone of the proposed algorithm is a batch-update version of online gradient descent, which is standard from the perspective of online learning. Hence, the novelty of the paper is mainly on the combination of OGD with inventory structures, which requires sufficient domain knowledge to appreciate. Unfortunately due to my unfamiliarity with inventory problems, I cannot make a very informed evaluation. This is more of my limitation rather than the limitation of this paper. Has the geometric cycle appeared in existing analyses?
Questions
- It is assumed that the adversary is oblivious, as the loss function and the demand sequence are determined at the beginning. Is there any particular reason for making this assumption? In online learning, people mainly need oblivious adversaries when the algorithm is randomized, but the algorithm in this paper is deterministic. - The paper leaves discrete feasible sets to future works (L135). I guess this might be handled by an expert algorithm, following the similar batch-update idea. Probably out of the scope of this paper, but it seems a reasonable addition. - The paper discusses the many ways that the setting of this paper generalizes existing works. Does the regret bound also recover existing bounds for more restrictive settings? - Appendix D compares the algorithm to a more direct approach based on OCO. The limitation of the latter is that the competitor is subject to the feasibility constraint. This leaves me wondering, if the competitor in this paper is not feasible, then technically we cannot implement it. Then, the meaning of the competitor term $\sum l_t(y)$ becomes more obscure.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
Limitations are discussed.
Summary
The paper introduces the online inventory optimisation problem. In the problem, we have $n$ products to stock and every day choose the levels to stock up the products to. We then suffer loss according to a convex loss function, which may vary from day to day (e.g., it may depend on the demand). We also get to know a subgradient of the loss. After the demand has wiped out some of the stock, we need to choose new levels to top up the remainders too etc. We want an online algorithm with a guarantee on the regret w.r.t. all possible constant levels. The paper proposes an algorithm, which is an extension of the online subgradient descent (OSD). OSD would have been applicable to the problem directly, if not for the presence of remainders (we cannot top up to a level below the current remainder). The version of the protocol without remainders is called stateless in the paper, so the proposed algorithm is a generalisation of the OSD to the "stateful" setup. The paper proceeds to obtain a $O(\sqrt{T})$ regret bound for the algorithm.
Strengths
I think the paper formulates an important problem and obtain a useful result.
Weaknesses
The algorithm and the pound in the paper are an extension of the online subgradient descent (OSD). One can argue that the result is of the incremental nature.
Questions
A constant strategy will only work if the constant is above the remainders all the time; otherwise it makes no sense. Am I correct that the regret is w.r.t. the constant strategies that work in this sense?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
Yes
Summary
The paper considers a general family of online inventory management problems under convex losses and stateful inventory dynamics. They propose a general algorithm based on an adaptation of ideas from online convex optimization. The method is essentially AdaGrad enhanced with an additional delayed update mechanism that ensures that the inventory constraints are always satisfied. The main result is a sublinear regret guarantee against the best fixed base-stock policy chosen in hindsight, given full knowledge of the realization of the demand sequence.
Strengths
The paper is very well-written when it comes to both its informal and technical content. In particular, the authors provide an excellent and succinct introduction into the relevant part of the management / operations literature, and discuss their results in this context extensively. The algorithm itself is natural and effective.
Weaknesses
While I generally like the paper, there are a couple of things that I would like to have some more clarity on before I can fully support its acceptance: - Regret is defined against the "best feasible constant strategy", as defined in Eq.(3). I worry that this comparator strategy is problematic in the stateful setting. First off, some fixed constant strategies may be infeasible when some of the carryover inventory levels x_t are large. Thus, the best feasible constant strategy may be a very poor one, ordering very high levels to make sure that the constraint is never violated. Second, I am concerned that evaluating a fixed policy on the loss sequence generated in response to the online agent's actions may be meaningless in the first place, and it might be more sensible to consider "policy regret" by taking into account the fact that the environment would respond differently to the comparator policy than to the agent. Treating this case, however, seems much harder than what is being handled in the present paper. Can the authors let me know if I'm missing something here? - The assumption that the order levels are continuous seems like a very important one. The authors themselves admit that this is a limitation of their method. However, I tend to believe that it is a rather major limitation, as just about every practically relevant problem instance in this space features discrete actions. In lack of continuity, one has to deal with the challenge of partial information due to lost sales, which makes it impossible to estimate the gradients even after convexifying the action space via randomization (as noted by Huh and Rusmevichientong [9]). It would be useful to clarify this to the reader so they don't end up believing that this assumption is minor. - I find it a bit disappointing that the regret bounds depend so heavily on the demand parameters mu and rho. I appreciate the negative results showing that certain degenerate demand sequences can lead to linear regret, but it's not clear to me if this justifies the poor linear dependence on 1/mu and 1/rho demonstrated by the bound. How do we know that this dependence cannot be improved to log(1/mu) and log(1/rho) or something even better? I really appreciate the experiments that plot performance as a function of the learning rate gamma, but I would also like to understand which values of gamma actually satisfy the constraint required by the theorem --- I suspect only the very very small ones, for which the algorithm works rather poorly. In this sense, it may be unfair to criticize DDM for not having performance guarantees since MaxCOSD doesn't have any either for the majority of the studied stepsizes. This is of course always a problem for theoretically motivated stepsizes, but it would be important to mention it at least once in passing. (A final note on the experiments: my impression was that AIM was also a very similar policy to what is being proposed here, but see no discussion on this.) Overall, I think this could be a good addition to the program, but I cannot confidently recommend acceptance until the authors respond to the above concerns.
Questions
see above
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
N/A
Thanks for your detailed and particularly straight-to-the-point response. It makes good sense to me, and I'll continue voting for acceptance.
Thank you for the detailed and honest response! I really appreciate the effort put into the rebuttal and in particular the detailed answers given to all my questions. Let me respond in detail: 1. Re feasibility of constant comparators: got it, thanks! 2. Re policy regret: thanks for the clarification! I guess I should have been more explicit about my concern here. What I worried about is that the losses may implicitly depend on the carryover state $x_t$, and it may be meaningless to compare the total loss of the learner with that of a comparator strategy that would have generated a different sequence of states. I now see that this is explicitly disallowed by the model. I am not super familiar with the inventory management literature so I am not sure if it makes sense to consider losses that depend on $x_t$ --- in my mind, it may make sense to model the cost of storing leftovers between order periods with such dependence. 3. Re continuous order levels: thanks for acknowledging the importance of this assumption! 4. Re lower bounded demands: OK, fair enough. I am still unsure about the importance of lower-bounded demands. E.g., Lugosi et al. [15] do not require such assumptions and still get good rates in a related setting. 5. Re parameter settings for the experiments: OK, that makes sense, please do add this clarification to the final version. 6. Re the relationship with AIM: sorry for phrasing this comment like that. I did not want to suggest that you failed to compare to AIM, but rather ask for a comment on the relationship (in particular any dis-/ similarities) between the proposed method and AIM. Overall, I am happy to recommend acceptance and have raised my score accordingly.
Answer to the comments by Reviewer 5kk9
We thank the reviewer for their feedback and for taking the time to participate to the discussion. Here are our answers to some of the comments: 2: Re losses depending on x_t: The reviewer's intuition is correct, it makes sense to consider losses depending on the inventory state x_t. Such losses appear in the literature, and fall outside of our model. We explain this limitation at the end of Remark 7 (on the losses). To make clear what exactly we are losing, we can say that 1) for lost sales dynamics, losses in x_t are often equivalent (up to a reparametrization) to losses in y_t. This is the case of the newsvendor loss, which is the mostly considered one in practice. This is due to the simple relation between x_t and y_t. 2) for dynamics involving perishability, the relation between x_t and y_t is more complicated, and there it can be natural to have losses depending in x_t (see e.g. [32] which considers an outdating cost). 4: Re the importance of lower bounded demands. Allow us to point out that [15] obtains optimal rates without this assumption because they are in a *stateless* setting. As we explain in Sections 3.1 and 5, a stateless setting does not require any assumption on the demand (which is usual for OCO). Our consideration of a more general dynamic forces us to make an assumption on the demand (as established in Proposition 13). That said, one could argue that our assumption can be replaced by a weaker one. But because our competitors need the same/similar assumption in their more specific settings (see below Assumption 10) we feel like replacing it will not be an easy task. 6: Re the relationship with AIM: thanks for further precising your comment. What we can do is to complete the paragraph following Algorithm 2, where we compare our method to CUP. We could add a sentence explaining that our method (and CUP) handle the feasibility constraint thanks to their cycles, which differs from the approach in AIM/DDM where projections onto the constraint are performed (we already explain in Section 3.2 that AIM is based on a subgradient descent and dynamic projection onto the feasibility constraint).
Thanks for the authors' response. However, I am still not convinced on the significance of the obtained results. - 1. We would like to highlight here that applying a classic analysis of OSD to inventory cannot lead to $O(\sqrt{T})$ rates. This is what we prove in Proposition 13. To get this rate we need to make assumptions which is totally unusual for online learning. Yes but I was referring to the $O(\sqrt{T})$ results with additional assumptions made (e.g. lower bounded density for the per-round demand distribution), which can be obtained by similar online gradient descent analysis in [9]. Also the adversarial demand lower bound is also not hard since you may accumulate too many inventory for one round while not getting these inventories sold in later rounds because of the adversarial demand. - 2. Several claims made in this paper may need more explanations or clarifications [...] The lower bound analysis is problematic or not rigorous [...] A refined analysis on both propositions should be included. I think the authors misunderstood my point in the sense that $y_1$ is a decision variable decided by **the algorithm** instead of the problem instance. If the algorithm decides $y_1$ to be $o(T)$, then your lower bound does not hold. - 3. This weakens the motivation of providing an algorithm that performs better in the adversarial environment. I was thinking the paper tries to consider the non-i.i.d demand case and design an algorithm which performs good in this environment (not necessarily adversarial). However, the experiments show that the performance of the algorithm designed for the i.i.d case (DDM) performs even better than the one proposed in this paper in setting 4, which is definitely not an i.i.d environment. This weakens the motivation of using the algorithm proposed in this paper, or in other words, whether the existing algorithms can already achieve so under these environment.
Answer about the misunderstanding regarding constants possibly depending on time
We again insist that $y_1$ is a constant real number chosen in the interval (0,D], as stated in our Proposition 14. It is not a function, and can by no means depend on T (which is a mute variable). As explained in our rebuttal, T is not a quantity fixed beforehand, because we are not in a fixed horizon setting. To illustrate this and further convince the reviewer, we provide below a simple technical explanation. Assume we fix some $T\in\mathbb N$ (say T=10) and set $y_1=T^{-1/2}$, then we could obtain in the proof of this proposition, $C=T^{-1/2}/2$ by choosing an appropriate sequence of demands $(d_t)$, this would indeed lead to $R_T\geq (\sqrt T)/ 2$. This does *not* contradict our claim, since this inequality is only valid for this **single value** of $T$. Consider now any $T’\in\mathbb N$ (a mute variable), then we obtain $R_{T’} \geq CT’ = T^{-1/2}T’/2$ which means that the regret grows linearly with time, which conforms to our claim. The same argument holds for all the other constant parameters.
Answer about the significance of the results
*"the results [...] can be obtained by similar online gradient descent analysis in [9]"* We disagree with the claim reducing the results in [9] to a classic analysis of OGD. For instance, the key part of the proof in [9] relies on additional results from queuing theory to prove these rates [9, Paragraph 3.2.3], see also the proof of [9, Proposition 4] in [9, Appendix B]. The final $O(\sqrt T)$ regret bound is indeed not very surprising but not so easy to obtain either. We recall that our work provide such rates for a significantly large range of settings, some of which have never been considered in the literature such as stateful non-iid settings or perishable multi-product settings. *"Also the adversarial demand lower bound is also not hard since you may accumulate too many inventory for one round while not getting these inventories sold in later rounds because of the adversarial demand"* Please note that we never claim that this lower bound is hard to obtain. We do claim this bound is new. *"I was thinking the paper tries to consider the non-i.i.d demand case and design an algorithm which performs good in this environment"* As explained in the abstract, in the introduction of the paper, as well as in our rebuttal: the goal of this paper is to provide an algorithm with *theoretical guarantees* in a specific setting (non-iid demands) where no such algorithm exists so far. Please acknowledge that this is a theoretical paper. *"DDM performs even better than the one proposed in this paper in setting 4"* Indeed, and our performance with respect to DDM is discussed in Section 4. It is indeed a non-iid setting but this environment also features lost sales, non-perishablity, capacity constraints and a large number of products. DDM has been specifically designed to handle these features while providing theoretical guarantees only in the iid setting. So, in Setting 4, MaxCOSD has proven guarantees whereas DDM has not (see the discussion with Reviewer 5kk9), but DDM performs better because of its design specific to the aforementioned features. Imagine for instance that we change Setting 4 by considering instead another feasible set $\mathcal Y$ or perishable products, then we would end up with a setting for which MaxCOSD can be applied (and still has provable guarantees) whereas, to the extent of our knowledge, no previously existing algorithm in the literature would be applicable. This fact alone should highlight the value of MaxCOSD and the significance of our results.
Decision
Accept (poster)