Online Inventory Problems: Beyond the i.i.d. Setting with Online Convex Optimization
Authors: Massil HIHAT
Stéphane Gaïffas
Guillaume Garrigos
Simon Bussy
Venue: NeurIPS 2023 poster (2023)
Keywords: online convex optimization
inventory control
newsvendor
online learning
regret analysis

Abstract: 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.

Online Inventory Problems: Beyond the i.i.d. Setting with Online Convex Optimization
Massil Hihat 1., Stéphane Gaiffas! Guillaume Garrigos 12, Simon Bussy'
LOPF, Califrais' Machine Learning Lab, Paris, France Université Paris Cité and Sorbonne Université, CNRS,
Laboratoire de Probabilités, Statistique et Modélisation, Paris, France
(hihat, stephane.gaiffas, garrigos)@1psm pwrp:ppppp..........aapaaaaapaip simon. bamoon.buse@ealifraaae
Abstract
We study multi-produs inventory control problems where manager makes se- quential replenishment decisions based on partial historical information in order to minimize its cumulative losses. Our motivation is to consider general de- mands, 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 per- ishability. We consider what we call non-degeneracy assumptions on the demand process, and argue that they necessary to allow learning.
1 Introduction
An inventory control problem is problem faced by an inventory manager that must decide how much goods to order at each time period to meet demand for its products. The manager's decision driven by the will to minimize a certain regret, which often penalizes missed sales and storage costs. is a standard problem in operations research and operations management, and the reader unfamiliar with the topic can find precise description of this problem in Section 2.
The classical literature inventory management focuses on optimizing an inventory system with complete knowledge of its parameters: we know in advance the demands, or the distribution they will be drawn from. Many efforts have been put into characterizing the optimal ordering policies, and providing efficient algorithms to find them. See e.g. the Economic Order Quantity model [7], Dynamic Lot-Size model [30] or the newsvendor model [1]. Nevertheless, many applications, the parameters of the inventory system are unknown. In this case, the manager faces joint learning and optimization problem that is typically framed as a sequential decision making problem: the manager bases its replenishment decisions (observable demand case) or past sales (censored demand case). The early attempts to solve these online inventory problems employed various techniques and provided only weak guarantees or no guarantees at all [23, 4, 6, 12).
data that collected over time, such as past demands
With the recent advances in online learning frameworks such as online convex optimization (OCO), bandits, or learning with expert advice, the literature of learning algorithms for inventory problems took great leap forward. There is currently growing body of research aiming at solving various online inventory problems while providing strong theoretical guarantees in the form of regret bounds [9, 13, 24, 3, 34, 25, 35, 15, 32, 33, 31].
However, these works rely on mathematically convenient but unrealistic assumptions. The most common one being that the demands are assumed to be independent and identically distributed (i.i.d)) across time, which rules out correlations and nonstationarities that common in real-world scenarios.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Furthermore, these works focus on specific cost structures (typically the newsvendor cost) and inventory dynamics (like lost sales models with nonperishable products), which we detail in Section 2.2. The main goal of this paper is to go beyond these restrictions and consider general demand processes, losses and dynamics, in order to provide numerical methods backed with theoretical guarantees compatible with real-world problems.
To do so, we recast the online inventory problem into new framework called Online Inventory Optimization (OIO), which extends OCO, Our main contribution is new algorithm called MaxCOSD, which can be seen as a generalization of the Online Subgradient Descent method. solves OIO problems with provable theoretical guarantees under minimial assumptions (see Section 4). Here is an informal version of our main statement:
Theorem 1 (Informal version of Theorem 12). Consider O10 problem that satisfies convexity and boundedness assumptions. Assume further that demands are not degenerate (see Assumption 10). Then, running MaxCOSD (see Algorithm 2) with adequate adaptive learning rates gives an optimal O(VT) regret, both in expectation and in high probability.
Our main assumption is a non-degeneracy hypothesis on the demand process, which we present and discuss in Section 5. This assumption generalizes typical hypotheses made in the inventory literature, while not requiring the demand to be i.i.d. We also show that this assumption is sharp. in the sense that the OIO cannot be solved without such assumption. Finally, in Section 6 we present numerical experiments on both synthetic and real-world data that validate empirically the versatility and performances of MaxCOSD, The appendices gather the proof' of all our statements.
This paper helps to bridge the gap between OCO and inventory optimization problems, and we hope that it will raise awareness of OCO researchers to this family of under-studied problems, while being of importance to the industry.
2 general model for online inventory problems
In this section, we present a new but simple model allowing study large class of online inventory problems. Then, in series of remarks we discuss particular instances of these problems and the limitations of our model.
2.1 Description of the model and main assumptions
In the following, n E N = (1. refers to the number of products and y C RT denotes the feasüble set. An online inventory optimization (OIO) problem is sequential decision problem where an inventory manager interacts with an environment according to the following protocol.
First, the environment sets the initial inventory state to zero (x1 = 0 E IR"),, and chooses (possibly random) demands de E IR and losses & R" + IR for every time period E N. Then, the interactions begin and unfold as follows, for every time period t N:
i) The manager observes the inventory state It E R", where ,t, encodes the quantity of the 7th product available in the inventory.
ii) The manager raises this level by choosing order-up-to level yt E y which satisfies the feasibility constraint:
Z
(1)
Then, the manager receives instantaneously yt.: Z4,5 2 O units of the 5th product.
iii) The manager suffers loss (e())) and observes subgradient Sr (y.).
iv) The environment updates the inventory state by choosing F++1 R. satisfying the following inventory dynamical constraint:
It++1 - [v. de1
The goal of the manager is to design an online algorithm that produces feasible order-up-to levels Yt which minimizes the cumulative loss suffered using past observations (past inventory states and subgradients). Let us emphasize here the fact that demands and losses are not directly observable. Throughout the paper, make the following assumptions the feasible set and the losses.

---

Assumption 2 (Convex and bounded problem).
i) (Convex and bounded construint) The feasible set y closed, convex, nonnegative () C [R.) and bounded: diam y I D for some D 2 O.
ïi (Convex losses) For every t N, the loss function l is convex.
mi) (Uniformly bounded subgradients) There exists G such that, for all t N, y E y and 9 E (y) we have ||9||2 S G.
Apart from the non- negativityy assumption C. Et which is specific inventory problems, Assump- tion 2 is very common in online convex optimization [36]. Definition 3 (Regret). Given an horizon T e N, we measure the performance of an algorithm with the usual notion of regret which is defined as:
T
RT Σ ((v))
in yEy
((v).
Observe that Ry is possibly random, so we call its expectation the expected regret E [Ry].
Notice that our model any constant strategy is feasible (see Lemma 26 in the appendix). Thus, the regret (3) is well-defined and can be interpreted as the difference between the cumulative loss incurred by the algorithm and that incurred by the best feasible constant strategy' It is an easy exercise to see that under Assumption 2 we always have Rr < DGT (see Lemma 27 in the appendix). Thus, our goal is to design algorithms with sublinear regret with respect to T, achieveing [[ S (T). Note that some authors consider the equivalent notion of averaged regret (1/T) Rr. In this context, we would talk about no-regre! algorithms.
2.2 Description of standard inventory models and limitations of our model
Remark 4 (On the demands), Demands are modeled by stochastic process (de) R. with fixed in advance distribution. In other words, we consider a general oblivious model for demands where make no assumptions of regularity, stationarity independence. Thus, our model accommodates both ii.d. 19. 3, 25, 32, 33, 31] and deterministic demands [13, 24, 34, 35, 15], while also allowing for correlations and nonstationarities that appear for instance in autoregressive models. However, rule out strategic behaviors: this is not a game-theoretic model.
Remark 5 (On the dynamic). Inventory states Z, are constrained by the inventory dynamical constraint (2) which links states, demands, and order-up-to levels. This constraint resembles the notion of partial perishability introduced in [9, Section 3.3] which imposes further that inventory states negative. In the following, we present
standard dynamics that conform to model. We warn the reader that we try here to simplify the vocabulary used in the scattered inventory literature, and that some authors [9. 3] may refer to these dynamics using different terms?.
Stateless dynamic. In stateless inventory problems, we assume that no product is carried over from one period to the other, i.e. 24 O. Observe that due to the non-negativity assumption ) C IRT, the feasibility constraint (1) is satisfied by any choice of y/ e in stateless problems. This means that stateless inventory problems coincide with the usual online convex optimization (OCO) framework [36]. See Appendix D.1 for discussion on the relationship between OCO and OIO. Any dynamic which is not stateless is called stateful, see below.
Backlogging dynamic. In backlogging inventory problems, excess demand stays on the books until it is satisfied and inventory leftovers are carried over to the next period. It corresponds to set Tt+1 Yt - de Notice that in this case the inventory state may be negative to represent backorders. This kind of dynamic has been widely studied in the context of classical inventory theory due to its linear nature, see e.g. [26, Chapter 4].
In the context of inventory problems, these constant strategies known under the name of (stationary) base-stock policies, S -S-oolicess, or order-up-to policies. e.g. [26. Chapter 4J. FFrr instance the stateless dynamic is usually referred to as the "perishable" setting, and lost sales and backlogging dynamics may both be referred to "nonperishable" settingg
3

---

Lost sales dynamic. Assume that products are nonperishable, excess demand is lost and inventory leftovers are carried over the next period. We refer to this case as the lost sales dynamic which corresponds to set Ft+1 = [y+ d.}². See e.g. [9, 25].
Perishable dynamic. In perishable inventory systems [19], newly ordered products are fresh units that have fixed usable lifetime. To model such a dynamic, it is necessary to track the entire age distribution of the on hand inventory and to specify the stockout type (lost sales or backlogging) and the issuing policy (i.e. how items are issued to meet demand). For instance, [32] describes a perishable setting modeling a single product with first-in-firs--r issuing policy, which satisfies our inventory dynamical constraint (2).
All those dynamics are what we call deterministic dynamics, in the sense that they take the form:
(vt E N) xt-1 Xy1,,, di,.... "......,ee. Vt. de);
where X, : (2' x RT)² + IR" is a fixed in advance function satisfying X1(Ví di...... Vle d,) =
[v/- - d']+t for all realizations (C)) (d)))eN and (vL)EE..
Remark 6 (On the feasible set), The feasible set Y' models fixed constraints on the order-up-to levels. Since it should satisfy Assumption 2.i), our framework does not allow for discrete sets as they appear in [15] for instance. This is one of the main limitations of our work. Typical choices include box constraints: y = I== (2,,, Vil. capacity constraints [25]: y = (y R Σi=1 Vi S M). Note that in some instances, the parameters of the box constraint is dictated by some assumptions on the problem. For instance, it is assumed in [9, 32] that y = [0, D] where D is a known upper bound for an optimal constant policy.
Remark 7 (On the losses). Losses (4E)ENN are random functions drawn before the interactions start. As for demands, we consider an oblivious model for the losses which allows handle both the i.i.d. case and the deterministic case. Most interestingly, losses can depend on the demands. This allows to consider the newsvendor loss, which writes (1) = cly, de) with:
cly. d) = Σ (h [y- d11 + pi [d, -0:--y))) vilt).
(5)
Here h4 E R4 and pt E R.+ are respectively the unit holding cost (a.k.a. overage cost) and unit lost sales penality cost (a.k.a. underage cost) of product E [n]. The newsvendor loss satisfy assumptions 2.ii) and 2.iii) with G = vn maxse[n] max(h;, p;). Our model also accommodates the newsvendor loss with time-varying unit cost parameters, as long as these remain bounded.
Because the losses are drawn before-hand, our model usually does not allow to incorporate costs that depend explicitly on the inventory states such purchase costs, outdating costs, or fixed costs. However, there are exceptions: when the dynamic is lost sales, purchase costs can be included into our model, by considering the newsvendor loss onto which cost transformation is applied (a.k.a. explicit formulation [26, Paragraph 4.3.2.4J). See also [9, 25] and the references therein.
Remark 8 (On the observability structure and subgradients). To handle arbitrary losses, we required in our model that in addition to inventory states vt, at least one subgradient gr E (t, is revealed at each period. In the case of the newsvendor loss, this is less demanding than both the observable demand setting and the censored demand setting [3]. In the former, the demand de is revealed instead of a subgradient 9t, meaning that the manager has complete information on the newsvendor loss & = e(-, d.). In the latter, the sale st == min ye, d,) } is revealed, allowing the manager to compute a subgradient through the following formula (see Lemma 28 in Appendix B):
(h: 1l (e..) pr (v..
seini sejm E (1:))
In this case, we see that no randomization is involved in the choice of the subgradient. This means that the subgradient selection is deterministic, in the sense that:
(Al E N) gt Te(Ce, M:),
where r, : RR. x x
R" is a fixed in advance function such that (4,,,81) E (6 for all realizations (C)EEN and (v))teN-
Remark 9 (OIO vs OCO). In this final remark, we would like to point out that OIO is a novel and strict extension of OCO, that is, OIO cannot be casted into OCO or one of its known extensions. More details on this are provided in Appendix D.I.

---

3 Partial results for simple inventory problems
Previous works online inventory problems mainly focused two settings: stateless inventory problems and stateful inventory problems with i.id. demands. Both settings are discussed here.
3.1 Stateless inventory problems
In the literature of stateless inventory problems, arbitrary deterministic demands have already been considered. This has been done for instance in [13, 34, 35], which assume demand observable and rely on the "learning with expert advice" framework. On the other hand [24] is the first work that considered the stateless setting with censored demand. See also [15] which tackled these problems in the discrete case, by reducing them to partial monitoring (an online learning framework that generalizes bandits). All these works achieve O(VT) regret (up to logarithmic terms), but are
restricted the newsvendor cost structure.
In our work, we aim at solving inventory problems with arbitrary demands and losses. Recall that under Assumption 2, stateless inventory problems coincide with the standard OCO framework [36] since feasibility (1) is trivially verified (see Remark 5). Thus. natural choice to solve stateless inventory problems the Online Subgradient Descent (OSD) method, which we recall in Algorithm 1.
Algorithm 1: OSD)
Parameters: learning rates (Me)eN, initial order-up-to level 1/1 y
2 for t = 1,2.... do
Output ye:
Observe 9: (b)(););
Set Ve+1 Projy n:B:):
Classical regret analysis of OSD (this is essentially proven in [8, Theorem 3.1]. see also Corollary 20 in the appendix) shows that taking decreasing learning rates of the form 1/2 =>D/ where 0, leads to regret bound Rt O(GDVT). It must be noted that the O(vT') scaling is optimal under Assumption (see e.g. [22, Theorem 5] or [21, Theorem 5.1]).
3.2 Stateful i.idd. inventory problems
When non-trivial dynamics are involved, inventory problems are much more complex and have mainly been studied in the i.i.d. demands framework. We review here the literature of joint learning and inventory control with censored demand and refer to the recent review of [5, Chapter 11] for further references. We stress that all those papers obtain rates for the pseudo-regret, lower bound of the expected regret which we consider in this paper (see Appendix D.2 for more details).
The seminal work of Huh and Rusmevichientong [9] is the first that derives regret bounds for the single- aaglectroduct i.i.d. newsvendor case under censored demand, it is also the sole work that considers general dynamics through their notion of partial perishability [9, Section 3.3]. They were able to design an algorithm called Adaptive Inventory Management (AIM) based on a subgradient descent and dynamic projections onto the feasibility constraint (1) which achieves a O(VT) pseudo-regret. Their main assumption that the demands should not be degenerate the sense that [d.] > 0 and that the manager should know a lower bound < < E [d1]. This lower bound is then used in AIM tune adequately the learning rate of the subgradient descent. Their analysis is based on results from queuing theory which rely heavily on the i.i.d. assumption.
Shi et al. [25] designed the Beivenriven Multi-productt (DDM) algorithm which extend the AIM method of [9] to the multi-product case under capacity constraints. They also derived a O(vT) pseudo-regret bound by assuming further that demands are pairwise independent across products and that E [d1.s] for all E [n]] amongst other regularity conditions.
Zhang al. [32] tackled the case of single-product i..d. perishable inventory systems with outdating costs. They designed the Cycle-Updaa Policy (CUP) algorithm which updates the order-up-to level according to subgradient descent, but only when the system experiences a stockout, i.e. when I 0, the order-up-to level remains unchanged otherwise. Feasibility is guaranteed using such
5

---

policy. However, in order to derive O(VT) pseudo-regret they need to ensure that the system experiences frequently stockouts. To do so, they consider stronger form non-degeneracy, namely. P P(d 2 D] > O where y = [0, PJ.
Variants of the subgradient descent have also been developed in order to achieve O(vT) pseudo- regret in inventory systems that includes lead times [33] or fixed costs [31] which are both beyond the scope of our model.
To summarize, an optimal ((VT) rate for the pseudo-regret is achievable in many stateful inventory problems, under the i.idd. assumption. To prove so, most of the cited works developed specific variants the subgradient descent that accommodates the specific dynamic at play. We will show in Section that this optimal (VVT) rate can be achieved by our algorithm MaxCOSD when applied to general inventory problems, with i.i.d. assumption the demand.
MaxCOSD: an algorithm for general inventory problems
In this section, we introduce and study our main algorithm: the Maximum Cyclic Online Subgradient Descent (MaxCOSD) algorithm. It is variant of the subgradient descent where instead of changing the order-up-to levels every period, updates are done only certain update periods denoted (fx)AEN. These define update cycles To = ( .4+1 - } during which the order-up-to level remains unchanged: Y/ = Yt, for all E Tи. Update periods are dynamically triggered by verifying. at the beginning of each time period t E N, whether a candidate order-up-to level ÿı is feasible or not. This candidate computed by making a subgradient step in the direction of the subgradients accumulated during the cycle and using the following adaptive learning rates,
DD
for all t E Tx
(7)
E Is
E.ET, 9el12
The pseudo-code for MaxCOSD is given in Algorithm
Algorithm 2: MaxCOSD
Parameters:
learning rate parameter y > 0, initial order-up-to level E y
Initialization:
Set in V1. t = 1, k= 1;
for t 1.2.... do
Output Vi:
Observe 9s (v.) and 11+1i
7
Compute M1+ = Projy (uee 1)s Ei=ue 9a)
where Th is defined Eq. (7);
if = 9c+1 then
L Set M+++ it+1, 14+1 L 1+ 1, +
10
else
11
Set yt+1 y/:
MaxCOSD is inspired by CUP [32], which handles the feasibility constraint through cyclical updates. This approach differs for instance from AIM [9] DDM [25], where the feasibility is enforced through projections onto the constraint. Among the differences between MaxCOSD and CUP is the fact that their cycle definition differ: in CUP stockouts trigger updates, whereas MaxCOSD relies directly on the feasibility condition, making its updates more frequent. Also, we use adaptive learning rates inspired by EdaGrad-Norma learning rates [27, Theorem 2] which allows us to be adaptive the constant G and obtain high probability regret bounds which are not available for CUP. Finally, and most importantly, the assumptions required by CUP are restrictive: i..dd demands, single-prodee perishable dynamic and strong form of demand non-degeneracy. On the other hand, MaxCOSI) performs well under much milder assumptions, which we introduce next.
It may happen that n is undefined due to denominator that in Eq. (7), in such set 0.

---

Assumption 10 (Uniformly probably positive demand), There exists E (0, 1] and p > 0 Ouch that, for all E N, almost surely,
IP
Vi E [n|] 2 4 2 n.
(8)
In simple settings we recover through Assumption 10 conditions that already appeared in the literature:
single-product iidd. newsvendor inventory problems, our assumption equivalent to the existence of > 0 such that IP [d1 2 p) > 0, that is, P [d] > 0] > 0, or equivalently E [di] > 0.
This is exactly the non-degeneracy assumption required by [9] AIM.
In its multi-product extension, [25] assumes also pairwise independence across products.
If we rather require mutual independence across products, then, Assumption 10 rewrites P id > 0j. [d1,a 0] which is also required by [25] in their algorithm DDM.
thus, our assumption reduces IE [d1,s] for all i [n]
We recover an assumption made for CUP [32] by requiring p = D where y = [0, DJ. and where D is also assumed to be large enough (see Remark 6).
If the demand is deterministic, then
and Eq. (8) becomes dz,; 2 for all i E [m]. the demand is discrete, i.e. dr, E {0, ..... for all E E, E [n]. then, we can take p = 1 and rewrite Eq. (8) as follows: P [i E [m)] dr, 0f61, di...................... ................................ 4-11, d=1]
μ.
In addition to Assumption 10 we also introduce a mild technical condition. Assumption 11 (Deterministic dynamic and subgradient selection). Dynamics and subgradient selections are deterministic, see Eq. (4) and Eq. (6).
We now state main result: under this new set of assumptions MaxCOSD achieves optimal O(VT) regret bound both in expectation and in high probability.
Theorem 12. Consider an inventory problem, and let assumptions 2, 10 and 11 hold. Then, Max- COSD (see Algorithm 2) run with y1 E y and y/ is feasible. Furthermore, when y E (0, D), enjoys the following regret bounds for all T TER N,
V2GD E [RR S
( 1 22
+ VT.
for any confidence level E (0, 1) we have with probability at least 6,
27 + +
(1+ ( log
1
(T) )7))²a
T VT.
Ri S GD
The obtained regret scales in O(VT), which is similar to other methods in the literature (see Section 3.2). As for the scaling in the constants and our rate scales like O ( and we do not know whether this can be improved or not. As a matter of comparison, CUP enjoys the same scaling (see [32, Theorem & Remark 3 & Assumption 1]).
5 Non-degenerate demands are needed for stateful inventory problems
Throughout this paper, we have seen instances of OIO which can be solved with sublinear regret rates: stateless OIO (equivalent to OCO), and some stateful OIO. It must be noted that, contrary to OCO, solving those stateful OIO problems required a non- non-degeneracy assumption on the demand (see Assumption 10 and Section 3.2). We argue here that such an assumption necessary for solving stateful OIO. Note that this idea is not new, and was already observed in the conclusion of [3] "To control the impact of overordering, demands must be bounded away from zero, least in expectation." ". Our contribution is to make this observation formal.
Proposition 13. Given any feasible deterministic* algorithm for the single-product lost sales newsven- dor inventory problem with observable demand over y [0, D), there exists sequence of demands such that the regret is linear, i.e. Ry = (T))
'In general, a deterministic algorithm is defined by fixed in advance functions Y: (RR" x R 1 + y and outputs y; (g( .2,..., ... 9t-1, 2x) for all E N..
7

---

Proposition 13 shows that Assumption is not sufficient to reach sublinear regret in general inventory problems. This is totally unusual from an OCO perspective, and is specificity of stateful OIO. Furthermore, the above result shows that what prevents us from reaching sublinear rates is not the limited feedback (demands and losses are observable in this example) but rather zemo demands. This is why it is necessary to make an assumption preventing demands to be too small, in some sense. Note that one may think of imposing positive demands to circumvent this difficulty, but this is not sufficient. Indeed, sequence of demands converging too fast to zero can also be problematic.
Proposition 14. Given any feasible algorithm for the single-product lost sales problem with observ- able demand over y = [0, D] such that y1 E (0, Dj, there exists a constant sequence of losses and a sequence of positive demands such that the regret is linear, i.c. R1 = ((T).
Let us now investigate why degenerated demand becomes problem when going from stateless to stateful OIO. The main difference between the two is that the feasibility constraint is always trivially satisfied for stateless OIO (see Remark 5). Instead, for stateful OIO, we can show that the higher is the demand, the easier it is for the feasibility constraint to be satisfied.
Lemma 15. Let v' d I8 If lly yll2 S minigej] di then, y' ž -y-dd* df" In particular, given an inventory problem and a time period E N. taking yt-1 E ) C R such that 11 gi d ensures that 1141 is feasible, in the sense that 1++1 I V-++-
Vo l2 S
The above lemma shows that if g is taken close enough from the previous yt, then the algorithm is feasible. The key point here is that "close enough" is controlled by the demand, meaning that when the demand is closer to zero there are less feasible choices for the manager. In such a case, we understand that it may be impossible to achieve sublinear regret, because the set of feasible choices could be too reduced.
The distance between two consecutive decisions can easily be controlled in methods based on subgradient descents, through their learning rates. This is why Lemma 15 is very helpful in the design of efficient feasible algorithms. It has been employed in the proof of our main result regarding MaxCOSD (Theorem 12). In the following, we further illustrate its usefulness by showing that OSD)
(see Algorithm 1) with adequate learning rates is feasible when the demand is uniformly positive.
Assumption 16 (Uniformly positive demand). There exists p >> 0 such that for all / E N, i E [m].
de, 2 p.
Theorem 17. Consider an inventory problem, and let assumptions 2 and 16 hold. Then, OSD (see Algorithm 1) run with y1 E y and nt = (DV((V/) where 7 E (0, D), is feasible and satisfies for all T E N that RT +
Numerical results
The goal of the following numerical experiments is to show the versatility and performances of MaxCOSD in various settings. Let consider the following problems.
Setting 1. Single-product lost sales inventory problem with i.i.d. demands drawn according to P1)s
Setting 2. Single-produc perishable inventory problem with a lifetime of periods and i.i.d. demands drawn according to Poisson(1).
Setting 3. Multi-product lost sales inventory problem with n 100 and capacity constraints. Demands are i.i.d. and drawn independently across products according to Poisson(A;) where the intensities >; have been drawn independently according to Uniform[1, 2].
Setting 4. Multi-product lost sales inventory problem with n 3049 and capacity constraints. Demands are taken from the real-world dataset of the M5 competition [17].
Setting 5. Multi-produce lost sales inventory problem with n = 3049 and box constraints. As in Setting 4 we considered demands from the M5 competition dataset [17].
'The code is available https: https:///gtthbb httpp:///ggituu..oo/aaaaaaeeeeee http://oo.oolllaaaa///e/eeeeeeee
8

---

10a
30
105
13
100
10
10
10
10
100
10
10
107
10"
101
AIN iParsilell
MaOCOD (Panalle)
10
10
-0
10
10
1.0
10
10
10
10-0
10-1
10
10
10
Figure 1: Regret in settings to 5 (from left to right) as a function of the learning rate parameter y..
We use the newsvendor loss all the settings. all the settings the cost parameters satisfy p./h: 200 since this ratio is known exceed 200 in many applications [10]. In settings 1, and
h; = and in settings 4 and 5, h; and pı are proportional to the real average selling costs.
In settings 1, 2, 3 and 4 we compare MaxCOSD against the following baselines: AIM [9] for Setting CUP [32] for Setting 2, and DDM [25] for settings and 4. In Setting 5, we ran parallelized version of MaxCOSD, that is, one instance of MaxCOSD per product, and parallelized version of AIM. Notice that in Settings 4 and demands are not i.i.d. and thus, do not fit the assumptions the baselines considered. Notice also that Theorem 12 requires MaxCOSD's learning rate to be small enough (y < D)D), which we do not try to enforce here. All the algorithms have been initialized with 1/1 0. Settings 1, and 3 have been run 10 times, with different demand realizations generated through independent samples.
Figure shows, for every setting, the regret obtained after T periods as function of the learning rate parameter 7 E [10-5, 10']. We picked T 1969 for all the settings because corresponds to the number of periods available in our real-world dataset [17]. We see that MaxCOSD) performs well compared to baselines whenever the number of handled products remains low (Settings 1,2,3,5). that MaxCOSD is less efficient when the number of products becomes large, in particular in the Setting 4. The performance MaxCOSD the large n regime can be explained by the fact that the cycles become longer, it becomes less likely that the feasibility condition satisfied. Indeed, we have seen in Lemma 15 that the larger the overall demand is, the easier feasibility holds. But when n grows, min, di becomes smaller, making the problem harder.
Instead,
7 Conclusion
In this paper, we address Online Inventory Optimization problems by introducing MaxCOSD, the first algorithm which can be applied to a wide variety real-world problems. More precisely, MaxCOSD enjoys an optimal O(VT) regret without assuming the demand be i.i.d, and can handle a large class of dynamics, including perishability models. We achieved this result by applying ideas and methods from online learning to OIO problems.
Still, there is lot of space for improvements and future developments, First, we observed that for problems with a large number of products and capacity constraints, the empirical performance of MaxCOSD could be improved. To do so, one would need to better handle the feasibility constraint, by using for instance projections onto the feasibilitly constraint, an idea already used by DDM, but with no theoretical guarantees so far in real-world scenarios. Second, we obtained regret bounds under minimal structural assumptions on the problem (convex lipschitz losses), but we could expect to obtain better rates by making stronger assumptions on the problem. One such assumption, which is classical in the Online Convex Optimization literature, to assume further that the losses are strongly convex or exp-concave, typically leading to logarithmic O(log()) regret. Another assumption,

---

which is more specific to the Online Inventory literature, is to make some regularity assumption directly on the demand, also leading to logarithmic pseudo-regret in the newsvendor case [3. Subsection 2.3]. Finally, even if our model is quite versatile, it has its limits, and more work is needed to improve it. For instance, we have seen Section 2.2 that we do not accommodate for outdating costs they appear in [32]. Also, we do not handle discrete feasible sets for which two promising techniques have been applied in the literature: expert algorithms [15] and probabilistic rounding [9, Subsection 3.4]. We could also hope further weaken non-degeneracy Assumption 10, by making an hypothesis which applies independently to each product, without having to assume pairwise independence across products. We believe that adequate adaptation of online convex optimization techniques to the online inventory framework will prove to be a successful strategy for overcoming those challenges.
Acknowledgement
We are thankful to Adeline Fermanian and the anonymous reviewers for helpful discussions and suggestions. Our work has been funded by the IOPF LabCom ANR-20-LCC1-0000 grant, provided by the French "Agence Nationale de la Recherche"..
References
Kenneth Arrow, Theodore Harris, and Jacob Marschak. Optimal inventory policy, Econometrica: Journal of the Econometric Sociery, pages 250-272, 1951.
[2] Masoud Badiei, Na Li, and Adam Wierman. Online convex optimization with ramp constraints. 2015 54th IEEE Conference on Decision and Control (CDC), pages 6730-6736.. IEEF, 20155
[3] Omar Besbes and Alp Muharremoglu, On implications of demand censoring in the newsvendor problem. Management Science, 1976)1407-1444, 2013.
[4] Apostolos N Burnetas and Craig Emmihh, Adaptive ordering and pricing for perishable products. Operations Research, 48(3):436 443, 2000.
[5] Xi Chen, Stefanus Jasin, and Cong Shi. The Elements Joint Learning and Optimization Operations Management, volume 18. Springer Nature, 2022.
[6] Gregory Godfrey and Warren Powell. An adaptive, distribution- free algorithm the newsvendor problem with censored demands, with applications to inventory and distribution. Management Science, 47 (8):1101-1111 2001.
[7] Ford W Harris. How many parts to make at once. 1913.
[8] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2 (3-4):157-33) 325, 2016.
[9] Woonghee Tim Huh and Paat Rusmevichicntong. A nonparametric asymptotic analysis of inventory planning with censored demand. Mathematics of Operations Research, 34(1):103-123, 2009.
[10] Woonghee Tim Huh, Ganesh Janakiraman, John Muckstadt, and Paat Rusmevichientong An adaptive algorithm finding the optimal base-stock policy lost sales inventory systems with censored demand. Mathematics of Operations Research, 34(2):397-466, 2009.
[11] Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimiza- tion with long-term constraints. In International Conference on Machine Learning, pages 402-411. PMLR, 2016.
[12] Retsef Levi, Robin O Roundy, and David Shmoys. Provably near-optimal sampling-based policies for stochastic inventory control models. Mathematics of Operations Research, 32(4):821 839, 2007.
[13] Tatsiana Levina, Yuri Levin, Jeff McGill, Mikhail Nediak, and Vladimir Vovk. Weak aggregating algorithm for the distribution-free perishable inventory problem. Operations Research Letters, 3866):516-211, 2010.
[14] Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-tenn tere budget constraints. In International Conference Machine Learning, pages
PMLR, 2019.
10

---

[15] Gábor Lugosi, Mihalis G Markakis, and Gergely Neu. On the hardness of inventory management with censored demand data. arXiv preprint urXiv:1710.05739, 2017.
[16] Mehrdad Mahdavi, Rong Jin, and Tianhao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1):2503-2233 2228. 2012.
[17] Spyros Makridakis, Evangelos Spiliotis, and Vassilios Assimakopoulos. The mš competition: Background, organization, and implementation. International Journal of Forecastinng 38(4):3325-1336 2022.
[18] Shic Mannor, John N Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(3). 2009.
[19] Steven Nahmias. Perishable inventory systems, volume 160. Springer Science & Business Media, 2011.
[20] Michael J Ncely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint arXiv: arXiv: 7402.0488, 2017.
[21] Francesco Orabona. A modern introduction to online learning, arXiv preprint arXiv:1912.13211 2019.
[22] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69, 2018.
[23] Herbert Scarf. Bayes solutions of the statistical inventory problem. The annals of mathematical statistics, 30(2):40-5508 1959.
[24] Peter Sempolinski and Amitabh Chaudhary. Online algorithms for the newsvendor problem with and without censored demands. In Frontiers in Algorithmics: 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceedings 4, pages 234 249. Springer, 2010.
[25] Cong Shi, Weidong Chen, and Izak Duenyas. Nonparametric data-driven algorithms for multiproduct inventory systems with censored demand. Operations Research, 64(2):362-370, 2016.
[26] Lawrence V Snyder and Zuo-Jun Max Shen. Fundamentals of supply chain theory. John Wiley & Sons, 2019.
[27] Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv:1002.er 1002.4862, 2010.
[28] Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety- algorithms for adversarial contextual bandit. In International Conference Machine Learning, pages 3280-3288. PMLR, 2017.
[29] Roman Vershynin. High digheddimessonal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[30] Harvey M Wagner and Thomson M Whitin. Dynamic version of the economic lot size model. Management science, 5(1):89-96) 96, 1958.
[31] Hao Yuan, Qi Luo, and Cong Shi. Marrying stochastic gradient descent with bandits: Learning algorithms for inventory systems with fixed costs. Management Science, 67(1))66089-6 6115, 2021.
[32] Huanan Zhang, Xiuli Chao, and Cong Shi. Perishable inventory systems: Convexity results for base-stock policies and learning algorithms under censored demand. Operations Research, (6(5):1276-1288 2018.
[33] Huanan Zhang, Xiuli Chao, and Cong Shi. Closing the gap: A learning algorithm for lost-sales inventory systems with lead times. Management Science, 1665):196 2020.
[34] Yong Zhang, Vladimir Vovk, and Weiguo Zhang. Probability-free solutions to the non-stationary newsven- dor problem. Annals of Operations Research, 223( 449, 2014.
[35] Yong Zhang, Xingyu Yang, and Baixun Li. Distribution-free solutions to the extended multi-period newsboy problem. Journal of Industrial & Management Optimization, 13(2):633, 2017.
[36] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceed- ings of the 20th international conference on machine learning (icml-03), pages 2003.
11

---

A Analysis of MaxCOSD
The goal of this appendix is to study the MaxCOSD algorithm (see Algorithm 2) and prove Theorem 12. To do so, start by introducing a generalized version of MaxCOSD named Cyclic Online Subgradient Descent (COSD) which has general update periods and learning rates (see Algorithm
3). In Proposition 19 provide general analysis of COSD which shows that it is sufficient control the cycles' length derive (vTT)) regret bounds. As a byproduct of this proposition we also derive the classical analysis of OSD (see Corollary 20), A way of ensuring that the cycles' lengths efficiently controlled is through a probabilistic property (see Assumption 21) which is similar to sub-exponential concentration [29. Section 2.7]. Finally, using Lemma 15 and Assumptions 2, 10 and II we show that when y E (0, p/ D] the cycles' length of MaxCOSD satisfy Assumption 21 which allows us to conclude with Theorem 12.
A.1 Design of COSD
The Cyclic Online Subgradient Descent (COSD) generalizes MaxCOSD by allowing arbitrary learning rates and update periods. Recall that update periods are allowed to dynamically defined, for this reason will refer sequence of update periods (t& &EN update strategy which is formally defined below.
Definition 18 (Update strategy). An update strategy MeN C a sequence of random variables such that, & 1, t < tk+1 for every & E N, and for every E N, k N, the event (tx t) is observable by the manager at the beginning of period t, i.e. it belongs to a a T2, -,,-,, 2t).
The pseudo-code COSD is given in Algorithm
Algorithm 3: COSD
Parameters: learning rates (N))EN, update strategy (tx) and y1 E y Initialization
Set = 1, 1;
for / - 111,,,, 1,2.... do
Output yt:
Observe 9t (v:) and 21+1; tf+ + then
Set Mt+1 Proiy (y12 Th Ei 9:):
Set k k+
10
else
11
Set Mc++1 = Ve:
By choosing appropriately the update strategy recover the following algorithms:
OSD. If updates are made every period, i.e. ty k, recover OSD. Its feasibility is not guaranteed.
Minibatch OSD. Given fixed minibatch size r E N, the updates period are defined offline via t + (k-1)r 1)T.
CUP. For every & E N, to is defined as the periods where the inventory is empty, that is,
t 1,
tx+1 inf to + 1 2, = 0} for A N.
(10)
This update strategy corresponds that used by CUP [32]. One easily sees that for such update periods th. feasibility always holds.
MaxCOSD. To recover MaxCOSD define dynamically the update strategy as the periods where the candidate order-up-to levels (ūr) are feasible. Formally, it writes:
1,
t++1 inf 2 + 1
9c) for k N.
(11)
12

---

where (9t) is defined by:
ÿ1 V1. De+1 = Proiy
Ut. - T
Σ
9s
(12)
5
with k = max 2 1: t) or equivalently t E Ta = (tx...... f-- 1}. Notice that at update
periods the implemented order-up-to levels coincide with the candidate order-up-to level, that is, we have Vt, = Dt, for all k E N.
A.2 Analysis of COSD and OSD
The following proposition summarizes the main properties of COSD, For convenience, we will use the notation f = fx+1 for the last period of the k cycle Ts.
Proposition 19. Let assumptions 2.i) and 2.i be satisfied. Given any update strategy and any sequence of learning rates (ni keN such that: Me11 $ n, for all E N, COSD (see Algorithm 3) has the following properties:
i) it is feasible if and only for all E 32.3.... }. yt. = Ita
ii for all K E M, the regret at the end of the Kth cycle satisfies,
D2
Rix 5
gt
(13)
21TT
k=
LET T
Proof. Let us prove claim i). By definition, the algorithm produces feasible sequence of order-up-to levels if y/1 ž 2, for all E N. But for all E {4x + l..... [ for some k E N, we have necessarily
VI = Vt-1 = [ de-1]* |+= z v, where the last inequality comes from (2). Thus we only need to check feasibility at the update periods, İee. check that Ut, 2 St, for all h E N. Furthermore, it is clear that the latter verified for
since Ft, = x1 0 V/1
Now to prove the regret bound (claim ii)) we follow the lines of the classical analysis of OSD (see e.g. the proof of [8, Theorem 3.1] or that of [21, Theorem 2.13]) when run against the sequence of losses (EIETy keEE instead of (EN) For convenience, we will write 9x = Σ 9t for all & E N.
Let E y, K E N and l E [K], we start by bounding ΣieT, (((e)) - 4 (z)) By definition of the subgradient E (3)) we have:
Σ 4(1) (((v) = Σ
le(vne) -le()) (āk, Vos v)
(14)
TET
We rewrite this bound follows:
(let. - v112 + n² 11 (1( - 9) - my mm.
(āk. Ura. y)
2M
By using the property of non-expansiveness of the Euclidean projection we have:
| - y 2 Projj (Ve. mk) Projy 11( - -m. - y/
Combining the last two results leads
1 (leea v1l2 + n/ 11 11 - =1(2)
(āk. Vta v) S 2nF
13

---

Finally, we combine the last inequality with inequality (14) and sum these over l = 1..... K.
Fg
K The Me - 1)
(2))
e(())=
K
K
1
(Ieve. - -112 -1ytett - -112)
+
Σ
Me
11ăx
21JEx
2
k=1
k=1
1
|1/4, - 2112
|1 - 3112
K-1
1
||
2112
2
7/5
Th
Mi
K<
Me
|1
k=1
D2
+
K-1
D2
+
K
TFg
11
2
1p11
ne
2
km
Jom
D
The
1
21jTx
k=1
Claim ii) is thereby proved by taking the supremum over y E V
Proposition 19 gives us guidelines to design optimal update cycles and learning rates. First, this proposition states that it suffices to verify the feasibility constraint at the update periods to ensure that the whole sequence of order-up-to levels produced by COSD is feasible. On the other hand, to guarantee that this algorithm has a sublinear regret we will need to ensure that the cycles Ta are not too long, i.e. that update periods are frequent enough, and then consider adequate learning rates.
Since OSD is an instance of COSD, we can recover classical regret bounds of OSD (see e.g. [8. Theorem 3.1] ]]]] or [21, Theorem 2.13]) and in particular O(vT) regret bounds, as a corollary of Proposition 19.
Corollary 20. Let assumptions 2.i) and 2.ii) be satisfied. Given positive non-increasing learning rates (M)). i.e. 0 < M741 I Tt. for all E N, the regret of OSD (see Algorithm 1) satisfies for all TEM N.
D
T
Pr S
99
2
2mT
[=1
In particular, Th = =DDD/G)VV with 7 > O, we have
1 +y GDVI. 27
Ry S
Proof. The regret bound follows from claim ii) of Proposition 19, Indeed, by taking 4 = k for all k E N. COSD coincide with OSD, thus, for K {k- ' obtain the desired regret bound. O
A.3 Controlling the cycles' length
In this subsection we analyze COSD with eventually unbounded cycles as the case for the CUP or the MaxCOSD update strategy. We start by introducing assumption the cycles called geometric cycles which yields expected regret bounds and high probability regret bounds.
Assumption (Geometric eycles). Let μ (0, 1]. An update strategy (Ix)en has ju-geomeerid cycles if there exists C₁ 2 such that for any E N and h E N we have:
PP Plt+1 - 4 > m] < C₂ - mM
(15)
The name geometric cycles motivated by the fact that & is geometric random variable with parameter μ., i.e. & N and P| m] 1m for all m N, then Assumption 21 rewrites:
14

---

P( - t ml I CE m] for all k.m E N. This property resembles sub-exponential concentration [29, Section 2.7]. This notion was inspired from a proof [32] where the authors observe, under their assumptions, that CUP's cycles length are geometrically distributed with parameter lower bounded by μ.. Assumption generalizes this property.
The following proposition summarizes some important properties of geometric cycles. Proposition 22. Consider an update strategy (4x KEN with μs geometric cycles (see Assumption 21),
then,
For all l E N, [ - -ta) =C/) and IE [(tx+1 -t,)² S 5
For all K N and any confidence level 6 (0, 1) we have with probability least 8,
(1++1 1111-4) (1+1--2222 (1 (1+
log(KC,//0)
VK.
1
Proof. First, let us observe that if μ 1 in Assumption 21 then, 4a = k for all k E N and one can easily check that all the claims are indeed verified. the following we assume E (0, 1).
Let & be geometric random variable of parameter that is, & E N and [L > m] = (1 - 1 for all m E N. Then, is well-known that E [c] = 1/p and E [s?] = (2 n)/p²²
We now prove the first claim by means of direct computations. For all & E N, we have:
+oc
C m] C, C₁,
E [1x+1 [&]
TP
[la++1
4 ml
/
Also, using the fact that for any integer a and real number b, we have, a if and only if [b]. we can upper bound E [tx-1 t as follows:
E [(1++
4x)
IP [[1++1 - (x)
ml
Σ
P [[1K++
1x)
LVml]
m=0
m==
C2PP [vml]
C, [
C,, 2-1 11
2C F
μ2a 12
m=0
Finally, let prove the second claim. Let K E N and
0, it is classical to that:
K
P
(t++1
+ >E
< P 3k [K]. (tx+1 - -xa)² > k2/K]
<
((++1-1a) (tet1-ta>>le//i
k= 1
We Assumption 21, which yields:
K
TP
(k41
- 16)
S KKC,(111))ttt -W)LE/RRRRR & KCp(11 (N)
Now for 5 (0,1) plug =1+
log(5/(KC..)
VK in the last result, obtain:
log(l-n" -14
K
(1441 -1 (1+
log(0/(KC))) VK, log(1 4)
Σ
with probability at least - 8. We conclude by simply observing that 11//ooo(1 - p)) S 1/p.
15

---

Using these tools, we are now ready to provide strong regret bounds for COSD under the assumption of geometric cycles. We are going from now on to focus on adaptive learning rates (see Eq. which will allow us to unlock high probability regret bounds.
Corollary 23. Consider an inventory problem satisfying Assumption and COSD (see Algorithm 3) with adaptive learning rates (see Eq. (7) and an update strategy with μ geometric cycles (see Assumption 21), then, the following regret bounds hold for all E N.
22 DG ( (1 ( VT.
E [Rr]
2
and any confidence level ô E (0, 1) we have with probability at least 6,
+ (1 1+
1
TCn
Pr S DG
log
VT.
27
1
Finally, COSD is feasible if and only for all (2,3,... ... yt. = Ztg.
Proof. Let T E N and K = min(k 2 1, S T. We start by bounding the regret Ry in terms of the regret at the end of K 1th cycle Rix- 1 Rix-1 and a remainder term as follows:
RT S Rix-1 + sup
((4e) lc(z) S Rix-1 sup Σ Σ wEy
(gt. Vs 3)
VEJ t=tk
where we used 9r E (yr). Applying Cauchy-Schwarl inequality, Assumption 2 and S (k+11 leads to:
Rr S Rix-1 + DG((t+1-1t -kk).
(16)
Let us now bound Rix-1- As a consequence of claim ii) of Proposition 19 and after substituting
by its value and applying Lemma 25 provided in Appendix B to f(x) = 1/(2/z) ao = 0 and
ag = ELET, 0ell2 for [K- we obtain:
Rix-1 < D 27
-1)
K-1
Σ
Σ
9t
S
DG
(
+7)
K
Σ
(tx+1 t2)2
27
LET
Combining this with inequality (16) leads to:
((/ +
(
K-1
R3 S DG
Σ (lE+1 - 1x)2 (lK+1 - 1x)
(1++1-167
K
< DG
1 + 27
Σ (tx+1 - 22
To obtain the expected regret bound, we start by noticing that K < T then taking the expectation in this last inequality, applying Jensen's ' inequality, then, Proposition 22 that bounds E [(tx+1 fx) <
2C,/p²² /2² we end up with the desired bound. Finally, to obtain the high probability regret bound, we notice again that K T and then apply the high probability bound of Proposition 22.
A.4 Proof of Theorem 12
In the following lemma we claim that under the assumptions of Theorem 12, MaxCOSD with the appropriate learning rates has geometric cycles (see Assumption 21).
Lemma 24. Consider an inventory problem and lei assumptions 2, 10 and 11 hold. Then, MaxCOSD with learning rates defined in Eq. (7) and y (0. p/ D) has y- geometric cycles with Cy = 1.
Proof. First, notice that if minlsej] dr, 2 p then T141 3 0c+1, i.e. + is an update period for MaxCOSD. This is consequence of Lemma 15, which applies since we have:
|| voll
Projy
Uth
T7t Σ
9s
Σ
9s
S
p
min d
s=tt
==
2
16

---

Now let k E N and m N. Using this initial observation we have:
Pl1++ I2 > m]
P
[ta+1 A Dt++h. tt A Dmetml
IP
min dey < P min dey +m- < EE(N)
iE(n)
IP
t 5, min da,t < p. .... min feind+tne d < p m
(E(n)
The last step of this proof is showing that in fact.
P t = S, min da,s P.
min de+m- < SP lts = s) -m se(n)
(17)
(E(N]
We prove this simple induction over m 1. Noticing that (4 5} E a (01, I2. ... Io- 11-1; C (E1, di..... f.-1, d,-1), where the last inclusion comes from Assumption 11, and using the basic properties conditional expectations we derive the inequality for
P
t = 8, min do,t < 2E
= E
P ty s, min da < ple di...., ,...,, d (E(n]
E Il st
min da, < f6............1... iE|n
- P 22 = 8) (1 10--0 p),
where the last inequality comes from Assumption 10. Assume now the relation (17) holds for m, let prove in similar way that it holds for + 1.
P
t2 s, min dg < iE(m]
min d do+m, < <p] vEnn]
E
ls 5, min da.s < p. kE(n)
min ds+m,i < ple,, (estt, 1, xE(n]
E
1 [tu [(+=x)
min <x,) 2E(m)
min d <pp
IP
min datm,s < pl62, d1. dett ds+m-1 [E(M)
< IP
ty = 8, min da,i < P.
min de+m-1, < (E
(1-4)
sEin]
< P It. = s] m+1
Summing the relations (17) over 8 2 leads to the final bound: P(1+1 - la > m] S (1 1mm which is our claim.
We are now ready prove Theorem 12.
Proof of Theorem 12. By definition, MaxCOSD is always feasible (independently of the learning rates chosen). Lemma 24 ensures that when (0, p/ D), MaxCOSD with adaptive learning rates as defined in Eq. (7) has μ --geometric cycles with C₁ = Thus, Corollary 23 applies and leads to the regret bounds claimed.
B Other lemmas
Lemma 25 (Lemma 4.13 of [21]). Let ag, aI....,05 0g be non-negative numbers and f R, - R. measurable non-increasing function, functiion,,,,, we have:
I =k=
a
ag
+
Σ
am
f(z)dr.

---

Proof. Define Sk= = -Em=t 2m=0 am-
The following holds for all & [K]
J
Sk axf((s) = -fa0 f(xx)dx & 1 f(z)dx.
a&f
do
+
Σ
am
SK-1
m=1
Summing over l: -,.... leads the desired bound.
Lemma 26. Consider an inventory problem with non-negative feasible set y C RT. Then, any non-decreasing sequence of order-up-to levels (ye)eN C C (i.e. such that yt yt+1 for all e N) is feasible. particular, constant strategies are feasible too.
Proof. Consider a non-decreasing sequence order-up-to levels (yE)EN C V C IR. First of all, y/ feasible since impose #1 0 and 11 E RT. Then, for every E N, write:
Vi+1 yr ly de] = 21+1-
The first inequality comes from the assumption that (yt)eN is non-decreasing, the second one from the monotonicity of the positive part and the fact that yr 124, finally, the last inequality is the inventory dynamical constraint. Thus, the whole strategy (yt)eN is feasible.
Lemma 27. Consider an inventory problem that satisfies Assumption 2, then, the regret of any algorithm is bounded as follows:
Rr DGT.
Proof. Let y V. For all t N, we have:
(y)) lx(y) S (g., Uh -) S 119tl12 1I v112 S GD,
where we used the definition of the subgradient 9: E (lz)))). then, Cauchy-Schwartz Schwartz incquality and finally Assumption 2. Summing these inequalities over 1,..., and taking the supremum over E y leads to the desired bound.
Lemma 28. Consider the newsvendor cost function defined in (5). Let d e R". A vector R" is a subgradient of the function of c(., at E R if and only for all E [n]] we have:
{hi), | hi, (-pi),
if y1 d,
9i
if yi d:
if < d.
In particular, denoting min(y, d), the vector (h; 1l (x: - Ps (w-=s:) )ie(i) is subgradient of
cl d) at
C Postponed proofs
C.1 Proof of Proposition
Proof of Proposition 13. Formally, in the lost sales single- product newsvendor setting with observ-
able demand over y = =0, D), a feasible deterministic algorithm is defined by sequence functions (Yi),eN of the form Y IR-_ ! - [0, D] satisfying Y4+1 (di,.... d.) 2 [Y:(d),...,, - de) for
all di,.... de R.,.
Let d E (0, D). and consider constant demand sequence defined by d, d every period N. Consider now (Ne) the sequence of order-up-to levels generated by this algorithm when facing We will now distinguish two cases.
this constant demand, that is, J. =
Consider the case where iz for all N. Taking y d in the regret definition (3) yields:
T
RT
c(0,
Σ
cld, d) = = 2(T).
18

---

ii Now, consider the case where there exists To 2 1 such that Ù1 = =...= - = 0 and dr, > 0. Consider a demand sequence (de) defined follows: dj
dr d and d: = 0 for 2 To. Denote by (yt)en the sequence order-up-to levels generated by the algorithm against the demand sequence (de)LEN, that is, 1/t
Since the algorithm is deterministic, we also have: Vr 0 for 1 < To 1. Indeed, we have, y/ (d ................................ de-1) Yr(d, ................................ d) it 0. On the other hand, we have for all f > To + y/ 2 [ve-1 d 1,-1, thus, y/ 2 yrb Dr, for all 2 To-
Taking y 0 in the regret definition (3) obtain for T > To.
RT 2
cyv, de) c(0,d))
Σ
cly,, 0)
Σ
hyr 2 (T To 1)hrr, 2(T).
T=
T=To
C.2 Proof of Proposition 14
Proof of Proposition 14. Take (d)) C 1 such that Ex= de < and define C = Vi Eis de > O. Notice that due to the feasibility constraint (1) and the lost sales dynamic we
have for all & E N. M++1 2 J++1 [y - de) )+ 2 Yt de. Thus, we have for every t E N.
V1 3/1 E (Vs+1 y.) 2 31 E.= de C. Now take the losses le(z) y. then,
RT = ΣT. y/ 2 CT for all T E N.
C.3 Proof of Lemma 15
Proof of Lemma 15. Since [y- - d) max 0} and vf > it enough to show th 2 y v-d. d.
The latter holds since, for any E [n]. we have y: 3o4 S Vly - yll2 S mingeen) d, S di.
C.4 Proof of Theorem 17
Proof of Theorem 17. The regret bound follows from the classical analysis of OSD, see our Corollary 20 or the proof of [8, Theorem 3.1]. Thus, we only need show the feasibility. For all t N, have,
96+1 - 3ell2 = P|orjyy - m.g:)) vell2 S ne 11
7D GV l1ael12 S
P V SP.
(18)
the first inequality is provided by the property of non-expansiveness of the Euclidean projection, the second inequality comes from y S p/D and ||91122 G. and the last incquality from vt > 1. Combining this result with Assumption 16, we obtain || - yr llz S min.e(n) de, According to Lemma 15 and the inventory dynamical constraint (2) this guarantees feasibility.
D
Discussion
D.1 On the relation between Online Inventory Optimization and Online Convex Optimization
In the usual Online Convex Optimization (OCO) framework introduced by [36] a decision-maker maker and an environment interact as follows: at every time period t E N, first, the decision- chooses a decision Ye E Y' and the environment chooses a loss function l,, then, the decision-maker receive some feedback which usually consist of either the loss function itself & (full- ffull-ifformation setting). the loss incurred (y())) (bandit setting) or subgradient Sr E dle (first-order feedback setting). The goal of the decision-maker is to minimize its cumulative loss incurred Σ ((y+))
OIO extend the OCO framework by adding the feasibility constraint (1). A naive solution to accommodate such constraints into the OCO framework is by adding to the losses the convex indicator of the feasibility constraint, that is, by considering the losses & (g) = (((y) + Xx(y), where Xe(y) (y) takes the value 0 if y z 2, holds and too otherwise. However, this is not satisfactory since by
19

---

doing so we also alter the regret (3) by imposing on the competitor y E y the feasibility constraints associated to the algorithm.
Many extensions of the OCO framework have been developed over the years. Of particular interest, those which include constraints of different forms like:
OCO with long-term constraints [16, 11], where m convex constraints of the form fi(-) < 0 for [m]] should be satisfied in the long run, that is, the goal minimize the cumulative loss while keeping low constraint violation Ei= fyr) for each E [m-]
OCO with long-term and time-varying constraints [20, 14] which compared the previous extension, considers time-varying convex constraints of the form ft.i(.) S 0 where fa, is revealed
the end of time period I. Even as long-term constraints, this learning task known to be unsolvable in general (see e.g. [28, Proposition 2.1] or [18, Proposition 4] for more precise statement), thus, restricted notions regret have been considered this context.
OCO with ramp constraints [2], where at each time period (2,3.... } the decision-maie should choose E y such that lr., - 9t-1,a S K2 for all E [n]].
We argue that OIO problems are different from these extensions. Indeed, our feasibility constraints (1) are neither long-term constraint since we do not allow for violations, nor ramp constraints since the bounds are time-varying. Also, our task is further challenging since we aim at bounding the regret (3) based competitor y y which does not suffer from the feasibility constraint (I).
D.2 On the notion of pseudo-regret
There exists an alternative notion of regret we call the pseudo-regret Rr which is in fact more common in the literature of online inventory problems [9, 3, 25, 32). It is defined as the difference between the expected cumulative loss of the algorithm and that of the best fixed constant strategy, that is, formally
I
RT
E
inf IE DEy
Σ 1c(w)
The difference between the expected regret E [Ry] and the pseudo-regret Ri is in the competitor y. In the former, the competitor is random and depends on the realization the losses, whereas, in the latter the competitor is fixed and depends only on the distribution of the losses. Notice that always have Rr E [Rr], thus, an upper bound obtained on the expected regret applies directly to the pseudo-regret.
20


Reviews:
[{"review_id": "EnbwheAvtr", "reviewer": "Reviewer_5kk9", "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.\n\n", "questions": "see above", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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:\n- 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?\n- 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.\n- 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.)\n\nOverall, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *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.* \n\nWe address this in our global response (in short: constant strategies are always feasible).\n\n2. *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?*\n\nWith our assumptions on the model (see remark 4) the adversary/environment is oblivious. Therefore, the regret and policy regret coincide, since the losses are oblivious and consist of functions of the current order-up-to level only. The loss functions do not change according to our decisions (oblivousness), only the states and thus the feasibility constraint vary. We will update remark 4 to make this clear to the reader. For more discussion on this topic, see maybe our answer number 3 to Reviewer ZTux, which asks us why we chose the environment to be oblivious.\n\n3. *The assumption that the order levels are continuous seems like a very important one [...] It would be useful to clarify this to the reader so they don't end up believing that this assumption is minor.* \n\nSee our global response (in short: we agree) \n\n4. On the rates: *I find it a bit disappointing that the regret bounds depend so heavily on the demand parameters mu and rho [...] How do we know that this dependence cannot be improved to log(1/mu) and log(1/rho) or something even better?*\n\nSee our global response (in short: we do not know, and other papers obtain similar constants)\n\n5. On the parameter $\\gamma$: *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.*\n\nWe agree with the reviewer. It is true that we run MaxCOSD for a wide range of parameters which might violate our condition $\\gamma \\leq \\rho/D$ in Theorem 12. For the record, in our experiments we always have $\\rho = 1$ and $D \\simeq 10,10,10^3,10^4,10^4$ for Settings 1-5 (in this order), while we explore the interval $[10^{-5}, 10^1]$. From this perspective, MaxCOSD lacks theoretical guarantees when using the parameters achieveing the best performance  (around $10^{-1}$) for Settings 3-4-5. This being said, we observe that we can force Theorem 12 to accept large stepsizes, by taking rho as large as needed. This would impact our Assumption 10 on the demand, and for things to work we would need to assume that there is a nonzero probability for all products to have a very high demand. This is either unrealistic in practice, or would hold with such a small mu that the rates would be meaningless.\nTo correct this, we propose to ponder our sentence \"*Remember that in this setting the baseline DDM has no whatsoever theoretical guarantees*\" with the information that MaxCOSD also violates our theory as well for large stepsizes.\n\n6. *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.*\n\nWe respectfully disagree. Our policy is quite similar to CUP's, which we discuss in Section 4. Instead, AIM performs projections onto the feasibility constraint, and do not involve cycles as we do. We agree that they share the same skeleton based on OSD, but from our perspective AIM is a rather different algorithm. "}, {"review_id": "xhnfV2sYYh", "reviewer": "Reviewer_UtoR", "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.\n\nWe want an online algorithm with a guarantee on the regret w.r.t. all possible constant levels.\n\nThe paper proposes an algorithm, which is an extension of the online subgradient descent (OSD). \n\nOSD 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.\n\nThe paper proceeds to obtain a $O(\\sqrt{T})$ regret bound for the algorithm.", "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?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *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.*\n\nOur answer : we address this in the global response.\n   \n2. *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?*\n\nOur answer : we address this in the global response (in short: our regret is always well defined in our context). "}, {"review_id": "vfuuDybCrc", "reviewer": "Reviewer_ZTux", "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. ", "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. \n\n- 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. \n\n- 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? \n\n- 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. ", "limitations": "Limitations are discussed. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall, this is a strong submission. \n\n- 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. \n\n- 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. \n\n- 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. \n\n- 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? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *One aspect I'm not sure is the novelty.* ; *The backbone of the proposed algorithm is a batch-update version of online gradient descent* ; *the novelty of the paper is mainly on the combination of OGD with inventory structures*\n\nWe address this in our global response.\n\n2. *Has the geometric cycle appeared in existing analyses?*\n\nYes. It appears in the proof of the CUP paper: with their assumptions, the authors observe that their cycles length are geometrically distributed with a parameter lower bounded by mu, which is a particular case of what we call “geometric cycles”. We did not see this concept as very important, but it is true that it would be fair to to explain the reader that this concept appeared before (even if unnamed). We will fix that.\n\n3. *It is assumed that the adversary is oblivious [...] Is there any particular reason for making this assumption? [...]*\n\nThis is a good question, which we debated while writing the paper. We eventually decided to set our paper with an oblivious adversary, which we explain below.\nThe first reason is that an oblivious adversary is the standard setting for online inventory problems. Indeed, fully adversarial environments make little sense from a modelling perspective. We would like to quote here the introduction of Lugosi et al. in [15], because we believe that it summarizes perfectly the situation: \"*[Oblivious adversarial] is also referred to in the literature as the “adversarial” approach, although this term is somewhat unfortunate: in our setting, the market chooses a sequence of demands for the different time periods arbitrarily, as far as the inventory manager is concerned. Importantly though, the market does not adapt its strategy according to the actions of the inventory manager. Indeed, it seems far-fetched to assume that an entire market adapts, and acts adversarially, to the inventory decisions of a firm. So, while our modeling framework can capture demand correlations and nonstationarities to a significant extent, it is certainly not a game theoretic model.*\"\nThe second reason is related to the notion of regret we want to use if the adversary is not oblivious. Let us consider for instance an \"adaptive\" adversary, in the sense precisely defined in *Online bandit learning against an adaptive adversary: from regret to policy regret* from Arora et al.. More precisely, it is a setting where the functions are chosen in advance but depend on all the past decisions. In such adaptive setting, we could use the classical notion of regret, but it would be more difficult to interpret. Indeed, the comparator (the constant strategy) would be evaluated against the losses chosen in reaction to the previous choices made by our algorithm. An other option would be to consider a policy regret (suggested by reviewer 5kk9)(note that in our oblivious setting policy regret is equal to regret). Policy regret makes more sense from a modelling perspective, but the counterpart is that it makes the analysis more difficult, and somehow requires to make some extra assumption (see for instance Theorem 1 in Arora et al.). We do not want to make superfluous assumptions on our problem, so we would need to make an assumption limiting how adaptive the adversary can be. We found one way of doing this: consider that the losses depend not only on y_t but also on the state x_t, in a very specific way. Precisely, assume that the losses have the form f_t(y,x) = L_t(y) + delta(y,x), where delta(y,x) is equal to 0 if y \\preceq x, +\\infty otherwise. Forcing the losses to have this form can be seen as a way to restrict the adaptive adversary. We observe that this is exactly equivalent to our current setting: a sequence y_t is feasible and has a certain classical regret bound if and only if the policy regret with those losses have the same bound. This is due to the fact that those new losses f_t are finite and equal to L_t if an only if the feasibility constraint is satisfied. We considered that it was not worth doing it, as it would introduce more technicalities in a paper for no apparent gain.\n\n4. *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.*\n\nSee our global response in the section about discrete sets (in short: it is a good idea but not trivial to apply because of the feasibility constraints).\n\n5. *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?* \n\nSee our global response (in short: yes for the dependency on T, more or less for mu)\n\n6. *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 [...] becomes more obscure.* \n\nIn our setting the competitor is always feasible (see our explanations in the global response).\nThis is why our approach makes sense, while the one described in Appendix D.1 is problematic.\n\n"}, {"review_id": "OA0OTaMS4A", "reviewer": "Reviewer_8ZLu", "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.", "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.\n- 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.", "limitations": "See Weakness and Questions sections.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The problem considered in this paper is interesting and has wide applications in real life.\n- 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.\n- 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.\n- Several claims made in this paper may need more explanations or clarifications.\n    - 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.\n    - The lower bound analysis is problematic or not rigorous. For proposition 13, in line 601, the authors argue that \n$(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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *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.* \n\n   See our global response.\n\n2. *Based on this, I think the regret $O(\\sqrt{T})$ is not very surprising.*\n\n   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. \n\n3. *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.*\n\n   We firmly disagree with the reviewer.\n   Each of the four critics raised by the reviewer rely on the assumption that some constants ($\\mu$, $\\rho$, $y_{T_0}$, or $y_1$) could depend on $T$. It is hard for us to make sense of this, as it is stated in our assumptions and statements that those quantities are *constant* and independant of $T$. This is for instance very clear in Assumption 10.\n   We conjecture that there is a confusion here, and that the reviewer has in mind an Online Learning setting where the horizon is *finite*. In such setting there is a fixed finite horizon $T \\in \\mathbb{N}$, and the learning dynamic unfolds on time periods $t=1,...,T$; at the end of which we compute a regret $R_T$. There we could indeed have parameters depending on the horizon $T$ (this happens in the corresponding literature), in which case the raised critics would be relevant. We stress that this is not our setting (we work with an *infinite horizon*).\n   There is also the possibility that the above is incorrect, and that we are completely missing something. In this case we would need further explanations from the reviewer?\n\n4. *The experiment results do not show a better performance of MaxCOSD compared to other algorithms*\n\n   This is correct, and stated in the paper (\"*we see that MaxCOSD is less efficient when the number of products becomes large*\").\n   Please note that the goal of this paper is not to improve on state-of-the-art performances in a specific setting. Instead, we provide a versatile algorithm able to tackle various (and new) settings while being theoretically grounded. We believe that wanting an algorithm which applies to a broader setting while at the same time beating the algorithms designed for solving a specific setting is irrealistic. This being said, we should not compromise on performance either, and we show that besides hard problems, our method performs comparatively to competitors.\n\n5. *This weakens the motivation of providing an algorithm that performs better in the adversarial environment.* \n\n We never make the claim that our algorithm performs better in an adversarial environment. \n\n6. *showing the error bar or the std of the algorithm would be better*\n\nWe considered doing this but chose not to do it for two reasons.\nThe first reason is that we use both synthetic data with real data, for which how to compute the std is not clear. The second reason is that it did not provide meaningful information for synthetic data. Indeed, in Settings 1-2 the variance is relatively very low overall ; and in Settings 3 the variance becomes significative only in the regime when $\\gamma$ is large (for both algorithms), which makes the plots look messy, while having little interest since it is the regime where the algorithms performs less well. For the sake of the conversation, we share in the global response our plots with the std displayed.\n\n7. *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.* \n\n   First of all, we emphasize that we do not make the claim that our Assumption 10 implies the Assumption 1 for CUP. Instead we say that we recover \"*an*\" assumption. Allow us to explain this in detail. Our point of view on the CUP algorithm is that Assumption 1 can be decomposed in two assumptions which have very different purposes.\n\n- First, the authors assume that the (unconstrained) problem they want to solve is equivalent to a problem with the constraint $\\mathcal{Y} = [0, \\bar S]$ . To do so, they assume that the optimal policy $S^*$ is lower than $\\bar S$. This assumption allows them to retrieve some compactness (which our paper has since we assume $\\mathcal{Y}$ to be compact).\n- Second, they make a non-degeneracy assumption on the demand to obtain $\\sqrt{T}$ rates : $\\mathbb{P}[d_t \\geq \\bar S] >0$. It is this assumption which is equivalent to our Assumption 10 when taking $\\mathcal{Y}=[0,D]$ and $\\rho = D$.\n  This is the reason why we did not refer to Assumption 1 as a whole in this sentence, but to *an* assumption.\n  We recognize that this is imprecise, and could be ambigous. In view to remove any ambiguity and make all this more understandable for the reader, we propose to add a sentence in Remark 6 (about the feasible set $\\mathcal{Y}$) explaining that in various papers (the CUP one, but also the AIM one) the authors first assume to know an upper bound $\\bar S$ on the optimal policy $S^*$, and then work with $\\mathcal{Y} = [0,\\bar S]$. This way our sentence in line 244 would make more sense, after eventually adding a call back to Remark 6.\n\n8. *On the optimality on the parameters $\\rho$ and $\\mu$ [...]* : \n\n   We address this in our global response (in short: we do not know, and as far as we know other competitors obtain the same kind of constants).\n\n"}]

Author rebuttal:
We will use this general response to address issues which were raised simultaneously by several reviewers. We responded to all the other issues in the individual responses to reviewers.

1) *Reviewers 5kk9, UtoR, ZTux raised concerns on the fact that the constant competitor in the regret definition might not staisfy the feasibility constraint.*

Our answer : There is no issue, because constant strategies are always feasible (we give a short proof below), so our regret is well-defined. This should absolutely appear in the paper, and we propose to state it clearly after Definition 3 (defining the regret), eventually pointing to a formal proof in the Appendix D.

The proof: Given any fixed order-up-to level $y\in\mathcal Y$, consider the constant strategy $y_t=y$ for all $t\in \mathbb{N}$, and denote by $x_t$ the states associated to this strategy. First of all, $y_1$ is feasible because we impose $x_1=0$. Then, for every $t\in\mathbb N$ we can write that $y_{t+1} = y \succeq [y-d_t]^+ = [y_t-d_t]^+ \succeq x_{t+1}$. The first inequality comes from the monotonicity of the positive part, while the last inequality is the inventory dynamical constraint.

2) *Reviewers 5kk9, ZTux point out that our action space is continuous instead of discrete.*

Our answer : Indeed, in our work, it is a crucial assumption that the feasible set is continuous. To handle the discrete case, two main ideas appear in the literature of online inventory problems. First, probabilistic rounding (see e.g. Huh and Rusmevichientong [9, Section 3.4] or Shi et al. [25, Section EC.4.2]) which, as mentioned by Reviewer 5kk9, even in the simple newsvendor case, requires additional knowledge, such as lost sales indicators, since a single subgradient may not provide enough information. Second, the use of expert algorithms as suggested by Reviewer ZTux, which has already been applied in stateless settings (see e.g. Lugosi et al. [15]). To adapt the cycle update technique to expert algorithms in stateful settings, we face the following challenge: how to bound efficiently the distance between consecutive (randomized) iterates? Answering this question is the key to design a sufficient condition for feasibility (as in our Lemma 15). 

We propose to rewrite the end of Remark 6 (on the feasible set) to highlight the fact that not being able to handle discrete sets is a major restriction of our model. We will further complete the conclusion by developing the above mentioned ideas to tackle this issue.

3) *Reviewers 5kk9, ZTux, 8ZLu made comments about the optimality of our regret rates, and their dependency in mu and rho.*

Our answer : In Section 3 we explain that all previous works obtain a $O(\sqrt{T})$ regret, and that it is somehow optimal for this class of problems. In Theorem 12 we obtain the same sublinear regret, but it is true that we do not make the connection with this literature review, and that we never discuss the constants appearing in the bound (which is roughly D^2G/(mu rho)). To the question of whether this constant is optimal, we have absolutely no answer. We were not able to find a worst-case example where the regret has a constant lower bounded by 1/mu. We are also not aware of any result in the literature with a better dependency in mu and rho. For instance, the CUP paper has more or less the same rates as ours. If we combine [32, Theorem 2 & Remark 3 & Assumption 1], we see that their  multiplicative constant is also GD^2/(mu rho). There is also the rates for AIM, where the multiplicative constant is explicited in [9, end of the proof of Theorem 2: equation 9]. It is a bit hard/unfair to compare to ours, because they directly make the assumption that $\mathbb{E}[d]$ is bounded below, and they obtain a constant which scales like $\mathbb{E}[d]^{-6}$. If we take the liberty to say that $\mathbb{E}[d]$ scales like $\rho\mu$ (vaguely justified by the fact that $\mathbb{E}[d] \geq \rho \mu$), then we could say that their constant scales like $(\rho\mu)^{-6}$. This last discussion is imprecise and hides a lot of other constants under the carpet, but we are confident to say that AIM doesn't depend logarithmically in $1/\mathbb{E}[d]$.

To make all this clear to the reader, we propose to add after Theorem 12 a few sentences recalling 1) that our rate recovers the same $O(\sqrt{T})$ scaling than other methods presented in Section 3 and 2) that we do not know if the scaling in $\mu, \rho$ is optimal or if it can be improved, also pointing to the above mentioned references.

4) *Reviewers UtoR, ZTux, 8ZLu raise concerns about the novelty of the paper*

Our answer : This topic is partially subjective, so we will try to keep our answer factual.
We believe that we are transparent about the nature of MaxCOSD in the paper (see the introduction where we present "*MaxCOSD, which can be seen as a generalization of the Online Subgradient Descent method.*"). We also make clear that OSD naturally solves online inventory problems in the stateless setting (Section 3.1 or Corollary 20). On the other hand, we would like to emphasize that applying naively OSD to stateless inventory problems does not work (see Section D.1 in the appendix). Even under strong assumptions on the demand, one needs to understand the link between stepsize and feasibility, which is what we explain around Theorem 17 and Lemma 15.
We would also like to stress that our contribution is not limited to Theorem 12 (which can be seen technically as a fine control on the size of an adaptively chosen batchsize for OSD), but also to the contents of Section 5. Our lower bound (Proposition 13) is also new, and formalizes an idea which was in the air (but not proven). 
Aside from this, we humbly hope that this paper will serve as a friendly introduction to inventory problems for the online learning community, motivating them to apply their techniques to a field where a lot of progress can still be made.

Meta-review: A good paper that provides an inventory control algorithm with theoretical guarantees that also perform well empirically. The ML community will appreciate the value of its power being leveraged in the inventory control application.
Decision: Accept (poster)