Online Inventory Optimization in Non-Stationary Environment
Authors: Koji Ichikawa
Kei Takemura
Tatsuya Matsuoka
Venue: ICLR 2026 Poster (2026)
Keywords: Inventory Optimization
Online Learning
Online Convex Optimization
Dynamic Regret
Primary area: learning theory

Abstract: This paper addresses online inventory optimization (OIO), an extension of online convex optimization. OIO is a sequential decision-making process in inventory management cycles consisting of order arrival, stock consumption, and new order placement. One key challenge in OIO is managing demand fluctuations. However, most existing algorithms still cannot sufficiently handle this because they focus on a static regret guarantee, comparing their performance to a fixed order-up-to level strategy. In non-stationary environments, such static comparator is unsuitable due to demand fluctuations. In this paper, we propose an algorithm with near-optimal dynamic regret guarantee for OIO. Our algorithm also offers an improvement of $\sqrt{L_{\max}}$ for the static regret upper bound in existing studies. Here, $L_{\max}$ refers to the maximum sell-out period. Our algorithm employs a simple two-stage projection strategy, through which we prove that the OIO is connected to the smoothed online convex optimization.

Published as a conference paper at ICLR 2026
ONLINE INVENTORY OPTIMIZATION IN
ENVIRONMENT
Koji Ichikawa, Kei Takemura & Tatsuya Matsuoka
NEC Corporation
Tokyo, Japan
[k_ [k_ichikawad kei.takemura, ta ta..matsuokajeeecc.com
ABSTRACT
This paper addresses online inventory optimization (OIO), an extension of online convex optimization. OIO is a sequential decision-makinn making process in inventory management cycles consisting of order arrival, stock consumption, and new order placement. One key challenge in OIO is managing demand fluctuations. How- ever, most existing algorithms still cannot sufficiently handle this because they focus a static regret guarantee, comparing their performance to a fixed order- up-to level strategy. In non-stationary environments, such static comparator is unsuitable due demand fluctuations. In this paper, we propose algorithm with near-optimal dynamic regret guarantee for OIO. Our algorithm also offers an im- provement of VLmax for the static regret upper bound in existing studies. Here, Lmax refers to the maximum sell-out period. Our algorithm employs a simple two-stage projection strategy, through which prove that the OIO is connected to the smoothed online convex optimization.
INTRODUCTION
Inventory management is crucial in supply chain management, with extensive research focusing on optimal ordering strategies for various inventory systems. In particular, systems with periodic reviews and carryover stock are closely related to real-world problems. Numerous approaches have been proposed for these systems, assuming known demand models (see, e.g., Glock et al. (2014)). However, often challenging to obtain complete demand model in advance, which highlights the necessity for online learning techniques to adapt unknown demands.
Recently, Online Convex Optimization (OCO) (Hazan, 2016; Orabona, 2019; Shalev-Shwartz, 2012) has attracted attention in the online inventory management (Huh & Rusmevichientong. 2009; Shi et al., 2016; Zhang et al., 2018a; 2020; Yuan et al., 2021; Agrawal & Jia, 2022; Hihat et al., 2023). OCO is sequential learning framework in which for each round t E [T], the decision maker chooses an N-dimensional vector that is in a convex feasible region C C V and then the environment reveals convex loss function fz- The typical aim of the decision maker is to minimize the static regret, E, mminec E, fe(u). Here we note that in the inventory system, most loss functions, such the Newsvendor loss, are convex.
Online inventory optimization (OIO) is a variant of OCO, formulated by Hihat et al. (2023). In OIO, a sequential decision-making process involving the inventory cycle of order arrival, stock consumption, and new order placement is considered. During each round t E [T], the stock is replenished the order-up-to level of ye set in the previous round. The environment processes the subsequent demand and post-processing activities, revealing N-dimensional carryover stock level of x++1 and subgradient Si (y,)). that associated with the convex loss incurred by the decision yt. Then, the decision maker determines the next order-up-to level V++1 that is greater than It-1 and less than the capacity constraint the warchouse. In the OIO setting, Hihat et al. (2023) have proposed the MaxCOSD algorithm, which achieves a sublinear static regret.
However, the static regret guarantee is not sufficient for practical applications, especially in environ- ments with demand fluctuations. Consider simple example of single-item inventory system with a capacity limit of D. Set the fluctuating demand as d, Dt/T for t E [T] and the loss function as the Newsvendor loss of l (v) = ly del. A straightforward calculation shows that the minimum

---

Published as a conference paper at ICLR 2026
total loss of the static comparator is min Ei= (u( O(T)), whereas a time-varying comparator with 4 = de results in Exm1 (e(4)) = 0. Thus, even if we have an algorithm with O(VT) -static regret for this example, it may still suffer from -r(Trrr when comparing it to
Recent studies on OCO have intensively investigated algorithms for dynamic environments (Hall & Willett, 2013; Zhang al., 2018b; Zhao et al., 2020; 2024). The dynamic regret is an indica- tor that measures an algorithm's tolerance against changing environments. In the context OCO, the dynamic regret is defined as Rr(u1..... UT) == Ei= le(ve) Ei= (2(1)), which is a func- tion of time-varying comparator sequence u1,..., u A major approach for the dynamic regret is based on a two-layer structure, where a meta-algorithm adaptively accumulates the decisions of set of base learners (Zhang et al., 2018b; van Erven al., 2021; Zhang et al., 2022b). Such algorithms ensure O(v(1 Pr))) Pr)
regret, where Pr is the total path-length of the com- parator: PT = Vi= 114--1 - -vell. Therefore, in OIO, a key question is whether we can con- struct algorithm that ensures O(V(L + Pr))aadymaniic regret in the O10 setting. If we have such an algorithm, we obtain a sublinear dynamic regret for the aforementioned example because
Pj - E1= ODD)
One major difficulty in the dynamic regret minimization for OIO is the carryover stock constraint. While the order-up-to level must be greater than the carryover stock Z₁. the comparator u, is not subject to this constraint. Thus, the feasible region of u, is always a superset of that of 1/- Most algorithms for OCO provide regret guarantees only for comparators û, that are in the same feasible region as ye. Consequently, this naive application results in ((T)-regret due the gap between ân and ue For the static regret minimization, Hihat et al. (2023) overcome this difficulty by cyclical update approach, where yr is only updated to a candidate d/. when ÿt feasible.
When considering the dynamic regret, however, we cannot employ a standard two-layer structure with an OIO algorithm (such as MaxCOSD) as the base learner to leverage its theoretical guarantees. A fundamental difficulty is that this architecture contradicts key assumption for OIO algorithmss the carryover stock level T++1 must be less than the preceding replenished stock level yt- A meta- algorithm's 's decision ys might be larger than the output yf of base learner a. With small demand, Te-1 can exceed yf- For the base learners, this carryover stock level violates their assumption (r) < yt for all i). This inconsistency prevents from obtaining a theoretical guarantee for the two-layer structure.
1.1 CONTRIBUTIONS
The main contribution this paper is to propose OIO algorithms with near-optimal dynamic regret guarantee, as stated in the following theorem.
Theorem (Informal). Under the constraints of carryover stock and the warehouse capacity, there exists an algorithm that ensures
Rr(u UT) S 66 Lm Pr)),
for any comparator sequence U1,..., WT, without knowing Linax and Pr a priori.
Here, Ô an order symbol that ignores logarithmic factors. Lmax is the maximum sell-out pe- riod defined in Definition 1, which, informally speaking, indicates that the total demand over L rounds is at least the warehouse capacity. For static regret, the algorithm guarantees Ö(v L/maxx T)- regret, offering an improvement of / VTmax over the existing works. The regret bounds are summa- rized in Table 1
Our algorithm employs a simple two-stage projection strategy consisting of a base learner and its projection onto a feasible region. In each round an observed subgradient Sr fed to the base
'We note that, the standard OCO setting, a simpler algorithm such as Online Gradient Descent algorithm (OGD) also achieve (1v(1+ PT) -dynamic regret upper bound if the learner knows Pr in advance. However, this parameter generally difficult set a priori, which motivates the use of a meta-algorithm.
'The parameters corresponding to Lmax in each reference are follows: 1/r in Huh & Rusmevichientong (2009); 1/p in Zhang et al. (201 8a); 1 1/c2 in Zhang al. (2020); 1) in Agrawal & Jia (2022); p3 in Yuan et al. (2021); 1/1 in Shi et al. (2016); and 1/p / in Hihat et al. (2023).
2

---

Published as a conference paper at ICLR 2026
Table 1: Regret bounds of [1] Huh & Rusmevichientong (2009); [2] Zhang al. (201 8a); [3] Zhang et al. (2020); [4] Agrawal & Jia (2022); [5] Yuan et al. (2021); [6] Shi et al. (2016); [7] Hihat et al. (2023); and our work. In the table, we list the regret bounds for each reference by replacing the demand characteristic parameters used in each paper with our indicator Lmax- C' in the fifth row is positive constant which depends on other parameters. In the references marked with a dagger, lead time is taken into account. We show the regret bounds when the lead time is equal to one. S/M in the Item column represents single-/multi-ttem setting. NV, O, and in the Loss column represent Newsvendor loss, outdating cost, and fixed cost, respectively. The warehouse capacity constraint used each reference is given in the Capacity column: Interval (zt E [0, D), where denotes the capacity); Linear (E I D); and Convex (ye C. for convex set C).
Regret
Reference
Upper Bound
Lower Bound
Item
Loss
Demand
Capacity
[1]
(Lmax VT)
NV
i..d.
Interval
[2]
O (Lmax VT)
2(vT) ((VT)
NV
ii.d.
Interval
[3]
O (Lmax VT)
NV
i..d.
Interval
Static
[4]*
0 (VT+ -Lmaa)
NV
i..d.
Interval
[5]
(e Clmmax
NV +
F
i.i.d.
Interval
[6]
Lmmxx
NV
indep.
Linear
[7]
O (Lmax VT)
Convex
non-i..d.
Convex
Static
Oly LImax T)
2 V Limax T)
[This work]
Convex non-i.id.
Linear
Dynamic
δ Tmmax (1 + PT)T)
learner to propose decision I(+1, which is then adjusted to yt+1 to meet carryover stock constraints. distinctive feature our algorithm is that the base learner's decision made independently of the carryover stock. We note that our update process differs from MaxCOSD's in that ours allows the order-up-to level ye to change, even if the base learner's decision de is infeasible.
Our primary technical contributions are twofold. First, we demonstrate that, under our two-stage projection, the dynamic regret can be bounded by the base learner's regret with switching costs pro- portional to Lmuax which eliminates the concerns regarding the dynamic carryover stock constraint. Leveraging this result, we achieve near-optimal dynamic regret by employing an algorithm for well-known Smoothed OCO (SOCO) (Lin et al., 2011; Zhang et al., 2021; 2022c;a) as the base learner, along with the doubling trick for unknown I.max- Second, we provide, for the first time, a R2 R(v Tomaxx T) lower bound for the OIO setting. Our matching upper and lower bounds establish that Ö(VLmax' T) nearly optimal, which resolves the open question raised by Hihat et al. (2023).
2 RELATED WORKS
Inventory Management Inventory management is long-standing research topic in the field of operations research. It addresses various conditions, such as demand model (deterministic or stochastic), carryover status (stateless or stateful), review frequencies (periodic or continuous), lead times (constant or probabilistic), item types (single or multiple), stockout types (backorders or lost opportunities), ordering costs (linear or non-linear, with or without fixed order cost), disposal losses, multi-echelon systems, and more (see, c.g., Zipkin (2000); Porteus (2002)). In particular, stateful inventory system with periodic reviews, i.e., situation where the remaining stock from the previ- ous period is carried over, is closely related to real-world problems. Numerous methods have been proposed for scenarios where the demand model is known in advance (Glock et al., 2014). How- ever, in many cases, obtaining a complete demand model in advance is challenging. This difficulty highlights the importance online learning for inventory optimization. As the objective function is often convex (e.g.. the Newsvendor loss), various studies have explored this online inventory opti- mization problem relation to OCO problems (Huh Rusmevichientong, 2009; Shi et al., 2016; Zhang al., 201 8a; 2020; Yuan al., 2021; Agrawal & Jia, 2022; Hihat et al., 2023).
3

---

Published as a conference paper at ICLR 2026
Online Convex Optimization Online convex optimization (OCO) (Shalev-Shwarle) 2012; Hazan, 2016; Orabona, 2019) is a sequential learning framework that chooses Ye and minimizes regret E, (xvr) Ee (u) for convex vime-varying function 4. It is shown that Online Gradient Descent algorithm (OGD) achieves the minimax optimal regret bound of O (VVT) (Zinkevich, 2003; Abernethy et al., 2008). For an exp-concave loss function, faster convergence can be achieved by Online Newton Step algorithm (Hazan et al., 2007), which enjoys a static regret bound of (log T).
In OCO, one of the important topics is developing algorithms that adapt to dynamic environments. There are two major performance metrics: dynamic regret and (strongly) adaptive regret. Dynamic regret, also known as switching or tracking regret, is defined as (y uT) = Σi= (Bee))
E (we) (Hall & Willett, 2013; Zhang et al., 2018h 8b; Zhao al., 2020; 2024). In Zhang et al. (2018)), it is shown that a two-layer algorithm called Ader achieves the optimal regret upper bound of (v(( + Pr)T). Adaptive regret (also known as interval regret) is defined as RT([s, e)) == EiE(...] (v.) minnee Eie|s,e) (u( Here the regret is function of the interval [s, e] == 8, + I,..., e L,e, where 1 S e < T. A weaker definition, considering the maximum regret, has been first proposed by Hazan & Seshadhri (2007). Later on, Daniely et al. (2015) have extended it to account for any interval length. Jun al. (2017) have proposed an algorithm achieving an adaptive regret of (VV PovTlogg1 T), where represents the length of the interval considered.
Smoothed OCO (SOCO)
variant of OCO that incorporates the switching cost A V++1 into the regret. The concept of switching cost is first motivated by data center management (Lin et al., 2011) and the standard setting, the cost function & is provided before making the decision Y/ (Bansal et al., 2015; Chen et al., 2018; Goel & Wierman, 2019; Goel et al., 2019). In the setting where the decision is made before observing the loss, OGD can achieve O(VXT) static regret (see, for example, Zhang et al. (2022a)). Zhang et al. (2021) have proposed an algorithm for the dynamic regret minimization based on Ader algorithm (Zhang et al., 2018b). Besides, it is pointed out that algorithms for OCO with memory guarantee the adaptive regret for SOCO (Zhang et al., 2022c; Gradu et al., 2023). Recently, Zhang et al. (2022a) have proposed an algorithm that guarantees upper bounds for both dynamic and adaptive regret by utilizing Discounted- -orettedd-ooaa---PPaee Normal-Predictor (Kapralov & Panigrahy, 2011).
PROBLEM SETTING
Algorithm Setting of online inventory optimization
1: Initialize the inventory level x E C(O), order-up-to level y/1 E C(z1), where C is defined in
Eq. (4).
2: for por==l. l... do
3: Observe an inventory level Z4+1 that satisfies 2/+1 E [0. vil for all i [N].
4: Observe subgradient 9: E (Mr).
5: Decide the next order-up-to level ye+1 that satisfies ye41 E C(x41).
6: end for
We consider the online inventory optimization problem for N items. The stock levels of each item are represented by components of --dimensional vector, which is an element of a convex set C C R. that defines the capacity constraints of the warehouse. At each round /. E [7), the decision maker receives the order placed in the previous round, resulting in the stock level reaching the order- level y/- Following this, the environment processes the subsequent demand and necessary post- processing activities, revealing a carryover stock level of 21+1 to the decision maker. Concurrently, subgradient 9: (V: that is associated with the convex loss incurred by the decision yi is observed. Then, the decision maker determines the next order-up-to level ye+1 such that yt-1 E C and v'41 1 2 z for all E [N]. The process is summarized in Alg. 1.
Remark 1. It can sometimes be challenging to observe opportunity loss. For instance, in retail stores, when an item is out of stock, customers rarely inquire with the store staff about its availabil- iry. As a result, retailers have limited knowledge about the actual demand for out-of stock items. Recently, Hihat et al. (2023) have addressed this issue in their 010 setting, highlighting that the subgradient of the loss function can often be derived without observing the demand quantity. This is
4

---

Published as a conference paper at ICLR 2026
because the penalty associated with the opportunity loss is typically given by multiplying the quantity of opportunity loss by a cost coefficient, as is the case with the Newsvendor loss: p pmax de yt where p is a cost coefficient and d, and yr demand and order-up-to level of round respectively. Since this penalty is linear with yts we can compute the subgradient only by observing whether a stockout occurred without knowing the demand quantity. Our problem setting also uses this frame- work.
We consider the following three conditions. First, we consider that the replenished stock up to yr is always greater than the carryover stock level I++1 after subsequent demand and post-procee post-processing:
" max(0, vt
d) S vi.
for all i E [N]. Here we define the demand for item i at round as dž E [0, D). noting that it may also include consumption from some post-processing activities.
Secondly, we define the feasible region for the order-up-to level y/s as the intersection of the lower bounds set by the carryover stocks
y N x
Vi E [M]
and the linear-sum constraints arising from inventory space
Σ D..
(3)
*E[N]
Specifically, we define the function for the feasible region C: [0, DJN -
- P(0, DI
C(x) = yy DJ
y' x" x² Vi [N], E 3 S D}.
(4)
iE[M]
Finally, we assume that the subgradients of the losses are bounded:
||ge|12 S G.
(5)
In our analysis, we deal with -nomm of the subgradient, which bounded as ||gh|] S /N NNllell2> VNG.
S
We consider the adversarial environment. After observing Vt, the environment can choose the de- mand de and convex loss function adversarially. The aim this paper is to construct a near-optimal algorithm for OIO under the adversarial environment.
Remark 2. Our study and Hihat et al. (2023) share the same setup except for the warehouse ca- pacity constraint. While Hihat et al. (2023) assumes general convex constraint, our work specif- ically addresses a linear constraint. Although the linear constraint is a special case of the convex constraint, it is commonly encountered in practical scenarios. Importantly, to our knowledge, no existing work establishes theoretically guaranteed algorithms for dynamic environments, even un- der the linear constraint. We also note that the linear constraint is applicable to cases in which each item occupies a different amount of space. Specifically, the weighted sum capacity constraint, E, C'y' < D where a' > 0 can be reduced Eq. (3) by redefining o' vi + yt and a' d' + di.
3.1 ENVIRONMENTAL DIFFICULTY INDICATOR
Algorithm's performance relies on the behavior of xz+1, which reflects the demand and post- processing in round t. In our analysis, focus on the period during which the inventory can meet demand, which is referred to as sell-out period.
Definition 1 (Sell-out period). We define Lmax as the minimum length of a period such that, for any item i and any starting time t, the cumulative demand of item reaches D, the (per-item) upper bound implied by the warehouse capacity constraint.
Lin(++L-1,77
Liux = min LE
Σ
d 2 D. for all E [T] and í [N]
Here, we hypothetically assume that di- D.
'Even when the demand d: exceeds the warehouse capacity, both our algorithm and analysis remain appli- cable as long as the subgradient for dž > Ds well-defined and observable, because our algorithm uses only the subgradient for updates. For example, in the Newsvendor loss, this subgradient is the same as the observed when a stockout occurs.
5

---

Published as a conference paper at ICLR 2026
Informally speaking, Lmax indicates that each item sells at least D units for any interval [t, t + Lmax - 1]. For example, for a static demand d', Lmax is given by [D/d".
We here note the relationship between the sell-out period and demand. Setting Lmax (T)) mildly constrains the duration of periods with small demand; this constraint prevents situations where the decision maker is forced incur holding costs
extended period due to the small demands. In fact, as we will show in our lower bound analysis, sublinear regret cannot be achieved when Lmax QQT). We also note that Lmax does not primarily constrain the fluctuations in demand. The fluctuation is only upper bounded during the period that determines Lmax, and there is no such constraint in the other rounds.
is straightforward to extend Lmax to a high probability upper bound. In this case, we consider that there exists parameter O < 8 < and winn://---tt
Remark 3.
d; 2 D) 2 1-8/NT holds for any E [M] and [T). This extension provides coob-brobbbility regret upper bounds. Furthermore, note that Lmax is essentially the same the other parameters defined in Shi et al. (2016) and Hihut et al. (2023). fact, the probabilistic extension is generalization of them. give detailed discussion of this point in the appendix.
3.2 REGRET
We consider the following dynamic regret for OlO:
T
R1 (uI..... , uT) Σ (())) ((u)) s Σ (gc. Vt uz)
(6)
Here y, E C(xe), and u, E C(O). The major difficulty arises from the fact that y/: and u, belong the different feasible regions. Specifically, the feasible region of u, is always a superset yi feasible region, meaning that employ stronger comparator than that of the standard OCO problem. In the OIO setting, the feasible region of y/ is affected by the previous decision; that is, the lower bound F, is constrained by ot. [0, v for all i [N]. Meanwhile, when adopt feasible comparator that satisfies max(0, ut df) < u the total path-length Pr becomes bounded. We provide detailed discussion in the appendix.
4 PROPOSED ALGORITHMS
Algorithm 2 Online inventory optimization algorithm for dynamic environments
Set ==
2: Initialize 0 and y1 E C((x)).
3: Initialize a base learner E(2T., T) with an initial state أ = y1.
4: ,,...,To do
5: Observe 9t E (y:) and Øz41 that satisfies 2/-1 E [0, vi] for [N].
6: Compute max L. where L, is defined in Eq. (9).
7:
if max L, > then
8:
Update L + 2L and restart E(2L, T) with the updated parameter L. end if
9:
10: Feed St to & and receive decision ůr+1 E C(O).
11: Update Vt+1 = TT( (1++))-
end for
Our algorithm employs simple two-stage projection strategy, described in Alg. 2. In each round t, the algorithm feeds It into the base learner E and receives the decision #c-1 C(O), which
*A simple example of Lmaxx a stochastic demand i.i.d. demand satisfying dj E {0. D/23 with P(d; > D/2)= 1/2. In this case, Proposition I in the appendix implies that the high-prohability upper bound of Tamax is four plus an additional number of rounds that depends the high-probabilityy parameter.

---

Published as a conference paper at ICLR 2026
only considers the warehouse capacity constraint (line 10). Then the algorithm projects it onto the feasible region with the carryover constraint: ((1+1)) (line 11).
The organization of this section is as follows: We first discuss the properties of the projection [[(())+)) in Scction 4.1. Our key lemma is Lemma I. By this lemma, we demonstrate that the regret upper bound of the decision //2 can be reduced that of the base learner's decision ÿr- Fur- thermore, we show that the carryover stock constraint leads to a switching cost for Ót in the base learner's S regret. In Section 4.2, we provide a regret guarantee for general base learner in Theo- rems 2. Finally, in Section 4.3, we introduce SOCO algorithms with a dynamic regret guarantee and present its regret upper bound in Theorem
4.1 PROJECTION PROPERTY
Our analysis is based on time- time-periods called cycles. For each item i, cycle is defined by the period during which of cannot be realized due the carryover stock z/. resulting in y D6. This is formally expressed as follows:
Definition 2 (Cycle). Let S; C [T] denote the set of rounds t [T] such that v S of. Suppose the elements E S; are indexed strictly increasing order as t < l2 < ... tis. We refer to the period lg, l. + 1, ...., 1 for l S as the k-th cycle of item and define the length of the k-th cycle as 1 == tk+1 tg. where we set [| =
Then, the following key lemma holds in our OIO setting:
Lemma 1, For any base learner E, Alg. 2 ensures
Σ (gt, Yt in) < 2G
Σ
(E(N) Li) llie -5i1-111111 0041ll1,
max
where Li is the current cycle length for item i, that is, L3 that satisfies tu S t < tut1 tu 1841 S,
Remark 4. Lemma shows that, under our two-stage projection strategy, 010 is linked to SOCO (Lin al., 2011; Zhang al., 2021; 2022c;u), eliminating the difficulty for the dynamic carryover stock constraint in the 010 setting.
In fact, under Alg. 2, the regret is bounded as
R
(gr, ût - ue) + 2GL @c+1ll1)
(8)
where L; max Li. The right-hand side is interpreted as the dynamic regret for SOCO problem for the base learner E, where for every t e [T]. & chooses dt C(O) and suffers loss (gt, ge) with switching cost of 22L;;-1ll--- - dell1. The main difference from the standard SOCO the coefficient Lj, which is dime-dependent and delayed in observability; it becomes observable only after the cycle for each item at time is completed." We propose an improved algorithm that works without prior knowledge of the switching cost in the next section.
4.2 DOUBLING TRICK FOR THE UNKNOWN SWITCHING COST
We address the unknown switching cost in Eq. (8) by introducing a doubling trick for L,. Alg. 2, described in lines 7 to 9, our algorithm restarts the base learner & with new parameter I. by
note that our algorithm can be applied for the æ1 * O case, incurring an additional regret of at most GD by adopting the zero-order strategy until the inventory level reaches O.
'e initialize in and beginning of the first cycle
appendix. We also omit brob-brrbbbilityy regrets the sake clarity, since extension is rather straightforward. See Remark 5 the appendix
omitted proofs are given
for details.
Another difference is that the switching cost appears fo-nrrm instead of the fg-nomm. We track this impact in the regret analyses.

---

Published as a conference paper at ICLR 2026
comparing the current parameter and the maximum observed cycle length max Lt. Here, define the set of the observed cycle lengths at round t as
4. = U [L 1 12 +1 S < lx+1, 4 E ES),, (E[N]
where - 1x + indicates lower bound of the current eycle length. We note that in Alg. 2, we do not store Li explicitly because the algorithm only needs max Lt. which can be tracked with O (N) memory. For the regret upper bound analysis, we use the following property of the cycle length:
Lemma 2. The cycle length is upper bounded by the sell-out period Lamax-
We assume that the base learner is an algorithm E() with an input parameter L and T that provides a regret upper bound of
(gr, 9c u.) GLIl )4+1l11) S R E(L.T) Σ
L,T
(10)
for any series of {9. 1
Then, the following regret upper bound holds for Alg. 2.
Theorem 2. Assume that under algorithm T), the regret upper bound E(L,T) RLT can be decom-
E(L,T) L for a 0 and the switching cost is bounded by l1. Øt+ 1|11 S
posed into RI,
) 3 2 0. Then, Alg. ensures
Rr S C(a))
2Lmoss. (.l)RRl22mmn E.2lmaan + A (I B),
where C(a) is an a-dependent factor and A (LImax B) denotes O if B < 1, OL log I if 8 and (Imax) if
1.
4.3 ALGORITIMMS FOR THE BASE LEARNER
In this section we introduce algorithms for SOCO that be used the base learner in Alg. 2. First, we introduce the standard Online Gradient Descent algorithm (OGD) described in Alg. 3.
Theorem 3. Assume T 2 Lmuax (3 - Pr/D). In Alg. 2, the base learner Alg. with an L- 2D(3D+P7)
parameterized learning rate = V G((/N++1/2]T ensures Rr S OmaLLmax Pr)T +
Lmax log Lmaa))
To obtain the optimal regret order, we must know Pr a priori when setting the learning rate т This parameter depends on the characteristics of the future demands and is sometimes difficult to determine advance.
Recently, Zhang al. (2022a) have proposed the Smoothed Online Gradient Descent algorithm (SOGD). the algorithm, the meta-algorithm sequentially aggregates multiple experts' decisions, where k-th decision in the sequence is obtained by combining k-th expert's decision V8+1 and - 1- combined decision sk-1 via the k-thh combiner B* The combiner combines the two inputs with weight Pt+1 that is adaptively computed by Discounted-Normal Kormaal-rredietor (Kapralov & Panigrahy, 201 1) with conservative updating using bit sequences
(ge: o o + GT(I] o llbt ;ー-1ا11) 1111
(11)
GGDNIAVT.
as described in line 5 11 in Alg. The meta-algorithm uses K-th decision as the output. Theorem 4. Assume T 2 Lmnax (log, T e). In Alg. the base learner Alg. 5 ensures Rr 0(v Immax (1 Py T log T + Lemaxe log Lunax)
8

---

Published as a conference paper at ICLR 2026
Algorithm 3 Online gradient descent
Algorithm 5 Smoothed online gradient de-
Require: Learning rate 77-
scent (Zhang et al., 2022a)
1: for | 1, do
Require: L > 0.
2: Receive subgradient gt-
Set K [log2 32 ma log + 1.
T
3: Return Di+1 = co, (Dr- ng.))
for k = ...... K do
4: end for
3: Set nz -
4: Initialize k-th instance A which
Alg. 3 with the learning rate of 17
Algorithm 4 k-th combiner
2D/GV /D/G/11(2V/L/// 1)n
Require: Two parameters: n² and L.
5: Initialize k-tth combiner B* which is Alg. with the input parameters n and L.
1: Initialize 21
2: Set g(2) = V n² terf( _ )e= ) /16n"
VBn
6: end for for 1 11.t= 1,...,7 T do 8: Receive a subgradient Jt-
3: Compute U (n²) : i1)
4: for t=rt= 1,..,, do
5: Receive 14--1 1 and 9r-
for k 1.... do
6: Compute of by Eq. (11).
10:
if I then
7: if 2, [0, [n")]
st < <n) >
11:
1/41 Al (gt).
or (E > (n") ))nk))n (b) < 0) then
12:
else
8:
2++1 (1 1/n 2 + b
13:
Di+1 (g()).
9:
else
14:
of + B (8trrl 91).
2++1 (1 1/1 )2t.
15:
end if
11:
end if
16:
end for
pÊ-1 = [1.11) (0(z+11)
17: Return #r+1 = iK
13:
Return oft1 = (1 p(+1)00
+
18:
end for
pi-
14: end for
We note that OLLmax log Lmax) in Theorems 3 and 4 is the overhead incurred by the doubling-trick mechanism and is subdominant for a broad range of horizons, e.g., T > T'max log T.max-
We finally comment on the computational overhead of our algorithm. In Alg. in order sup- press the dynamic regret upper bound, we adopt meta-algoritha that incurs computational cost of (KT)) = (T log T',, which is more expensive than OGD by a factor log Such overhead common in the OCO SOCO setting, when using meta-algorithms for non-stationary environ- ments. On the other hand, the doubling trick Alg. restarts the base learner at most Oloog Lmax) times, resulting in additional Ollog Tmmax) initialization overhead which does affect the per- round computational cost.
LOWER BOUND
In this section, we discuss the optimality of our regret analysis. OCO. Zhang al. (2018b) have established the 52( /(1 (1 + PT) lower bound. Our regret upper bound matches this lower bound up to a logarithmic factor. On the other hand, we also have VTmaa factor our bound. The following theorem ensures this optimality.
Theorem 5. For any algorithm A, there exists some sequence {gtte and some u E CCO0) such that
T
(or - u) S(GDV LmxxT))
where {vi IT is the sequence of the outputs by A.
As byproduct, this lower bound provides the optimality of the VL factor in the OGD and SOGD algorithms for the SOCO setting. This is because if there were an algorithm that can be improved upon, it can break the lower bound of OIO by adopting it as the base learner of our algorithm.

---

Published as a conference paper at ICLR 2026
Corollary 1. For SOCO with regret of (L), its lower bound is (((LLT).
In our study, OIO and SOCO are found to be connected, which provides an intriguing example of how one lower bound can constrain the other.
CONCLUSIONS AND LIMITATIONS
In this paper, we propose an algorithm for OIO with a near-optimal dynamic regret guarantee. We connect OIO to SOCO through a simple two-stage projection and the dynamic regret bound com- bining an algorithm for SOCO and doubling trick for unknown Lmax-
There are several interesting prospects for future investigation. First, the problem setting does not take into account the lead time and fixed-order costs. For i.i.d. demand, there are studies addressing these settings (Zhang al., 2020; Agrawal & Jia, 2022; Yuan et al., 2021). The extension dynamic environments is an interesting direction for future research. Secondly, we assume a linear capacity constraint described in Eq. (3). This assumption critical the proof of Lemmas 5 and 6. Although we believe that it is possible to extend this assumption to more general convex set, we leave it for future work.
REFERENCES
Jacob Abemnethy, Peter Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Conference Learning Theory, pp. 2p.4114-224 2008.
Shipra Agrawal and Randy Jia. Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management. Oper. Res., 1033):666-11611 2022.
Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein. A c-competitive algorithm for online convex optimization with switching costs. In Interna- tional Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 96-109, 2015.
Niangjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Conference on Learning Theory, pp. 1574-1594, 2018.
Amit Daniely, Alon Gonen, and Shai Shaley-Shwartz. Strongly adaptive online learning. In Inter- national Conference on Machine Learning, pp. 1405-1411, 2015.
Christoph H. Glock, Eric H. Grosse, and Jörg M. Ries. The lot sizing problem: A tertiary study, Int. Prod. Econ., 155:39-51, 2014.
Gautam Goel and Adam Wierman. An online algorithm for smoothed regression and LQR control. In International Conference on Artificial Intelligence and Staristics, pp. 2504 2513, 2019.
Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. In Advances in Neural Information Processing Systems, volume 32, pp. 1873-1883, 2019.
Paula Gradu, Elad Hazan, and Edgar Minasyan. Adaptive regret for control of time-varying dynam- ics. In Learning for Dynamics and Control Conference, pp. 560-572, 2023.
Eric Hall and Rebecca Willett. Dynamical models and tracking regret in online convex program- ming. International Conference on Machine Learning, pp. 579-587, 2013.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 33: 2016.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Elec- fronic colloquium computational complexity (ECCC), volume 14, 2007.
10

---

Published as a conference paper at ICLR 2026
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Mach. Learn., 69(2-3):169-112) 2007.
Massil Hihat, Stéphane Gaiffas, Guillaume Garrigos, and Simon Bussy. Online inventory prob- lems: beyond the iid setting with online convex optimization. In Advances in Neural Information Processing Systems, volume 36, pp. 20421-20440, 2023.
Woonghee Tim Huh and Paat Rusmevichientong. A nonparametric asymptotic analysis of inventory planning with censored demand. Math. Oper. Res., 34:103-123, 2009.
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In International Conference on Artificial Intelligence and Statistics, pp. 943-951 2017.
Michael Kapralov and Rina Panigrahy. Prediction strategies without loss. In Advances in Neural Information Processing Systems, volume 24, pp. 928-836, 2011.
Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic right-sizing for power-proportiona data centers. IEEE/ACM Transactions on Networking, 21:1378 1391, 2011.
Francesco Orabona. A modern introduction to online learning. arXiv preprins arXiv: 13213, 2019.
Evan L. Porteus. Foundations of Stochastic Inventory Theory. Stanford University Press, 2002.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
Cong Shi, Weidong Chen, and Izak Duenyas. Nonparametric data-driven algorithms for multiprod- uct inventory systems with censored demand. Oper. Res., 64(2):362-370, 2016.
Tim van Erven, Wouter M. Koolen, and Dirk der Hoeven. MetaGrad: Adaptation using multiple learning rates in online learning. Mach. Learn. Res., 22:161:1-161:61, 2021.
Hao Yuan, Qi Luo, and Cong Shi. Marrying stochastic gradient descent with bandits: Learning algorithms for inventory systems with fixed costs. Manag. Sci., (7(10))6089-611111 2021.
Huanan Zhang, Xiuli Chao, and Cong Shi. Technical note perishable inventory systems: Convexity results for base-stock policies and learning algorithms under censored demand. Oper. Res., 66: 1276-1286, 2018a
Huanan Zhang, Xiuli Chao, and Cong Shi. Closing the gap: A learning algorithm for lost-sales inventory systems with lead times. Manag. Sci., 66: 1962-1988, 2020.
Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems, volume 31, pp. 1330-1344 1340, 2018b.
Lijun Zhang, Wei Jiang, Shiyin Lu, and Tianbao Yang. Revisiting smoothed online learning. In Advances in Neural Information Processing Systems, volume 34, pp. 13599-13612, 2021.
Lijun Zhang, Wei Jiang, Jinfeng Yi, and Tianbao Yang. Smoothed online convex optimization based on iescounted-norman predicco. In Advances Neural Information Processing Systems, volume 35, pp. 4928 4942,992211 2022a.
Lijun Zhang, Guanghui Wang, Jinfeng Yi, and Tianbao Yang. A simple yet universal strategy for online convex optimization. In International Conference on Machine Learning, pp. 26605-26623, 2022b.
Zhiyu Zhang, Ashok Cutkosky, and Ioannis Paschalidis. Adversarial tracking control via strongly adaptive online learning with memory. In International Conference on Artificial Intelligence and Statistics, pp. 1458-8492. 2022c.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems, volume 33, pp. 12510-12520, 2020.
11

---

Published as a conference paper at ICLR 2026
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity Problem-dependent dynamic regret for online convex optimization. J. Mach. Learn. Res., 25 (98):1-52, 2024.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning, pp. 928-936, 2003.
Paul H. Zipkin. Foundations of Inventory Management. McGraw-Hill, 2000.
A DISCUSSION ON Liax
Existing works introduce the least amount of demands in each round. Shi al. (2016) assumes minimum demand. Hihat et al. (2023) introduces parameters p and μ. and assumes P [d] 2 ol 2 μ holds for E [T' almost surely. We here see the relation between Assumption 10 in Hihat al. (2023) and Remark 3 in our paper.
Proposition 1. If Assumption 10 Hihat et al. (2023) holds, then our assumption in Remark
holds. That is, if one has p and such that [d] 2 p] y holds for all & [T] almost surely, then
there exists Lmax such that IP and [
E Emin Lunax I,T+1) D) 2 11-8/ 8/NT holds for any i [N]
Proof.
We denote Lamax by L. Suppose Assumption 10 in Hihat et al. (2023) holds. Then, we have
P [ N p
for all / (7) almost surely. By Markov's inequality, obtain
E d
[
P
and thus [dj 2 pn holds. Our aim is obtain the number of rounds necessary for making the inventory sold out with the probability at least 8/NT for each eycle (by the fact that there exist at most 7 cycles from t = to 7 for all items and technique the union bound). Since we assume #//41 for all [N], we consider L. consecutive rounds only. Hereafter, consider some fixed [V]. Let denote
X, = {1
(d) p) 0 (d) < p)
and
Y, Σ -(X,)
By applying Azuma Hoeff-iog inequality, we obtain
P
Σ 1=1
X. S LH -
< < - YYo
P
Σ
X₂ S E
Σ X₁
[=1
82
< exp
2L
From
82
exp
2L
NT
we obtain
NT
2L log
8
12

---

Published as a conference paper at ICLR 2026
Therefore, Σ X I Lu- /2L log x holds with probability at least - 6/NT. If demand
larger than or equal to p occurs at least D/p times, then the inventory becomes sold out. Thus, the condition for L is
D - Lu
NT
2L log 5
Let us denote w VLp,a 2log NT
and = D/p, then we obtain
D
NT
$ Lμ / 2L
w²
aw
8
2
a
2
w
V
+
a
+
4
Then,
a +
NT log o
log
NT
D
+ b
L
4
24
p
NT log 5
log
D
Lu
+
+
2/u
11
P
log NT
2 log
NT
2D
Lp
+
11
P
holds, where the last part utilizes (a + 3) s 2(a² 2 + B²), Va, 3 E R. Therefore, one adopts L
satisfying
3log
NT
2D +
2D
log
NT 1
Lp 2
L2 +
PP
the inventory becomes sold out at most L rounds with the probability at least 8/NT.
B EXTENSION TO THE HIGH-PROBABILITT REGRET
Remark 5. The probabilistic definition for Lmax in Remark ensures that Li satisfies L S Liax with probability of -//NT. Given this definition, our regret upper bounds hold when all Ti satisfy Lt S Immax
E [T] Applying the union bound over all cycles and items, we bound its probability at least 1 1-6 8. Therefore, using the probabilistic expression for Lmaxe our results naturally extend to high-probability regrets, maintaining the same order of bounds with a probubility of -.
C ORDER ESTIMATION OF PT
Proposition 2. Under the feasible comparator that satisfies max(0, uf d)) s with- Pr is upper bounded by ND + 2 di.
Proof. For clarity, we first consider the single-item scenario. Consider set A {t E {2, T3 44-1 2 ) and write Pr as
T Pr
Σ
14-1
(4-- we) +
Σ
(u+ 4--1)
(12)
t=2
YEA
LE AE(2....T)IA
13

---

Published as a conference paper at ICLR 2026
The first term is upper bounded by the demand series {di} as
ut-1 Ut S de-1,
(13)
because the feasible space of u, is constrained by the carryover stock as u, 2 max(u4-1 ( 1, On the other hand, the second term be bounded by the first term as follows:
-D S u1 - UT
[u-- ( - -u) Σ 2EA
(1--1-10
E
(ue Ur-1).
(14)
1E/2,..,,'14
Combining these inequalities, we have
T
Pr S 2 (1-1
d D.
_
(15)
EEA
1EA
1=1
The bound in the multi-item each item, which concludes the proof.
be obtained straightforwardly the of the bounds for
We also note that the ideal feasible comparator typically yields Pr = =t= ||d:- dg del11. This is because, in most inventory system without lead-time, the ideal order-up-to decision {wt) matches the demand {de). which incurs neither lost-sales loss nor holding costs.
D PROOFS OF THE LEMMAS IN SECTIONS 4.1 AND 4.2
D.1 LEMMAS ON THE PROJECTION OPERATOR IT(x))
In this section, we provide lemmas regarding the relationships that hold between ÿ E C(O) and y = = where E C(O). We note that y, ÿ. and do not necessarily depend on I; other words, we do not assume that they are elements of a I-dependent series resulting from particular algorithm or environment.
For the subsequent proof', define the set of the item index I and its complement I= {i E [M] of < }. and I = [N] I (i E [N] y² > 5 respectively, Recall that C(xx) C(0) and the projection y = Il((w) (f) equal to = arg mingrec(())) 1y
Lemma 3. For i E I, y² x > 0.
Proof. We divide the proof into three cases regarding ÿ: (i) For á E C(x), it obvious that y holds. (ii) For C(x) and ÿ' < xx, observe e > 0 and y' = xx + decreasing to zero decreases the objective function without violating the constraint, which contradicts the minimality of y. We also note that xf > in this case because g' 2 O. (iii) Finally, for ÿ & C(x) and i' 2 x², we observe y² < j'. This is because if we have some and y" ÿ' decreasing to zero decreases the objective function without violating the constraint, which contradicts the minimality of y. In summary, y² > o only occurs in the case of (ii), which leads to s² x² >
x² > f This is because if we have some
Lemma 4. If there exists i [N] that satisfies of" < ff, then Eiez y D - w.
Proof. From Lemma 3, it is obvious y² = x for j E I. Therefore, y = [l(()) (0) implies that y minimizes Eier (2) 0²)² satisfying y² - D¹ and EieTy' S D Ejez v., Assume that EiEr y' < <D Exer x². Then, we can increase y" to 3³ without violating the constraint, which decreases objective function and contradicts the minimality of y.
D.2 PROOF OF LEMMA 1
To prove Lemma 1, we use the following two lemmas for the cycle property. Let Ij be the set of items such that t is the initial part of the cycle, i.e., I = {i E [N] v < Øf) Note that I, = [M] \ I, = (i e [N] of 0 is the set of items in the later part of the cycle. Then, the following lemmas hold.
14

---

Published as a conference paper at ICLR 2026
Lemma 5. For any t [T], EiEI, Vi vi EiEI, Vi V4
Lemma 6. For any & E [K')] where Kt is the number of cycles for item i: K = |S and 8
[L] 11. Putt tuuts ts S 20==00u4e -
Proof of Lemma 1. We divide the left-hand side of Eq. (7) into the initial and later parts of the cycle:
T
Σ gt D - 01) = Σ
Σ
gilvi
01) +
Σ
gi 00)
(16)
TET
AET,
For the first term, from Lemma 5, the following inequality holds:
T Σ ΣEsh VEI,
T Σ 11 Σ(vi - 1t)
silvi
11) S Σ 1.
E(i KELL
vi)
Lemma
(17)
iE..
where we use vi S 0 for i I. in the first incquality. This inequality suggests the following statement: the contributions from the initial part of the cycles in all items bounded by the contri- butions from the later parts of the cycles in all items. Therefore, the proof is completed by evaluating the contributions from the later parts of the cycles, i.e., the second term in Eq. (16).
For the second term in Eq. (16), using Lemma 6, we have
Kt
1
Σ
Σ 1ET.
01)
9 to
(Vi
K³ Li
Σ
l1 + alllll (oo
k=1
N
K L
Lemma 6
100 lol0
(18)
='=0
where we refer the definition of the summation of the later parts of the cycle for the first equality. Combining Eq. (16), Eq. (17), and Eq. (18), we finally have
d1)
Bq (17)
S
ΣΣΣ
N
K³
- Σ
11 2 (Vig- (lg
Fq (18)
N K 14
8-1
11 +oll+ Σ (o Digts/+1)
i=1
s'm0
N
K
L
2G
1= k=
s=1
s'=0
Lemma
2G Σ
(EA)0) (I. ((0-(o()) -1) (i) -841)
< 2G
max Liarc)) 11 - Set1ll1 iE[N]
T
< 2G
Li 0t+1ll1.
1=1
In the fourth line, apply Lemma 7. This concludes the proof.
15

---

Published as a conference paper at ICLR 2026
D.3 PROOF OF LEMMA 5
First, we consider the case = [M] In this case, we observe j' yf = 0 for all i E [N]. This can be proved follows: we have non-empty I' {i
Proof.
write 8' = D e where > 0 for j E I'' Then, EiE[N] V² = E 9 Σ jET el DD- el.
N y' V.).
Therefore, decreasing e's zero decreases the objective function without violating the constraint, which contradicts the minimality of
Then, we consider the case I * [VV af E I satisfies y' y/=00 =y' then Eier(0' y²) and the inequality holds. Otherwise, from Lemma 4, have EiET V EjeT x and
Σ EE
y
3' - D + Σ x
REI
JEI
Σ iE[N]
5/' - D +
Σ (xx) - 88)
JEI
Σ (x) 89)
Lomma
Σ (y² 8¹)
JEI
In the last inequality, use EVEN 1' < because 9 C(O).
D.4 PROOF OF LEMMA 6
Proof. For the sake of brevity, we omit index of ti. Li and K when is clear from the context. Consider the summation in the k-th cycle for item à:
Rie (vi ti. + t1 (1 Dia+1) + + g W -
From the definition the k-th cycle, we have
vh. S the
(19)
Moreover, for 1,..., La 1, because vi, +a Lemma 3. Thus, the following order property holds:
> Ulator we have Viyta xteto 0 from
Eq. (1) Fitss
Lemma 3
Plute 2 0, Via+o
(20)
for 1..... La 1. Using the above properties, for cycles of La 2 2, the following upper bound holds:
Vi.to Miato = wlute Dlute S Viuto-1 Viato
(Wiut--1 1i(+o-1) + (Wu+o-1 Via+s)
(Wl, Wi.) Σ
Wilror Dluto4+1) s'=00
Eq (19)
HFluss #luto'41)
which concludes the proof.
D.5 THE OTHER TECHNICAL LEMMA FOR LEMMA
Lemma 7. Suppose round I,... is divided into K segments of lengths Liy..., Lx that satisfy
1 < Ta < Tvk E [K] and EK Tak T. Let us define function (T] [K] which maps each
16

---

Published as a conference paper at ICLR 2026
roundt [T] the segment & E [K] that belongs to, i.e., x(t) minge [K) lo s.t., Σ Ly 2t. t. Then, for any series a1,.... OT and bi...., bg, the following equality holds:
L
Σ
Otg bb
Σ Sebncc)(Ennt (t (w(s)) 1]+
where tú : Ex= Le + 1 is the initial round of k-th segment and [x]+ == 211e 2 0].
Proof.
Lx -
K L+-1
a12-5.bk b/
abba t + s/
T K
arbnllk = k(t)][[[s' = =t- (x]
='=0
T L s-1
aebn -t-()( bx(0)
T Lu(gy11
(ebx - -12 +t- - -tm(e))
Σ aebret)) (Lx(() - - (t tx((t) + 1) 1[Lx(0 12 t tx(o)
arbr(tt) (x((t) (t tx(t))
D.6 PROOF OF LEMMA 2
Proof. Consider k-th cycle for item with cycle length Li. By definition, we have Di < via-s for 1.......4 L By Lemma 3, slats xluts Therefore, we have
yi. 21 +1 di vlut1 + di
11
-
x
du+t
If Li Lmax. then vi, D because xd This contradicts vi, < D.
f > 0 and Eli-2 di 2 Σ
2=
T'max
diats D.
E PROOF OF THEOREM 2
Proof. We start by defining a set of the restart rounds as f1...., tn+1, where the i-th restart occurs at and set each restart as Li...., L,. where L; = 2 1 In our algorithm, the base learner t..... f,....t..1 is E(24,, T). Note that since T., is most 2 TTmax. have < log, Immax 2. The regret can be
and tx+1 T + 1. We assign labels to the parameter used in
17

---

Published as a conference paper at ICLR 2026
divided into:
n
f--11
(g., Dr - un) + 26 - b++1ll1)=
(1gr. Dr - -u) + 2GL; - 9c+1ll1)
1=1
t=
4-1
4-1-1
((g,, Dr u.) 2GLillie #c+1lli)
Σ
Σ
2G(L; L.) @ct1ll1-
(21)
For the first term, using the assumptions for R RLT we have
E(,,T)
f+1-1 -1
(1e, Ur u2) + 2GT, 0tt1l11) S
((2L.T)
2L,,T
n
2 I
2
R(T)
Σ 2ai
R(T)
I (
where C(a) is an a-dependent constant. For the first inequality, we use the fact that when an algorithm guarantees upper bound RLT E(L,T) for regret (I)... it also ensures that R1 (L) I E(LT) for T' T. This can be observed by setting dr for & E {T" + 1,...,, T}, which extends the series M= in Rr (L) KEf This allows apply the same bound RL,T E(L.T) to (L).
RLT
In the second term of Eq. (21). positive contribution comes from the rounds where the parameter L; underestimates L; L; > Lj. Suppose the parameter is set to L, and the algorithm observes that a cycle starts round l. The algorithm can detect that the cycle length is longer than L4 has not finished at t + Li 1. Therefore, the underestimated period is at most L,. The second term is bounded as
fi1-1
Σ
2G(L L.)lū 11-1 S 2G
11 14+1l11144 > Li]
t=
t=
1-1-1
< C2G
L " >
Ld
t=t:
S C2GTmaas
I 1-8
C2GLmaas
211-1)(1-8)
O (L2-8 max
(8 < 1),
O Lmax log Limax)
(8 1).
(L
(3 > 1),
where C2 is constant. Combining these two inequalities concludes the proof.
F PROOF OF THEOREM 3
Below, in order to match the standard expression, we introduce : 2D which indicates the upper bound of the diameter of C(O):
|| 2|12 S | - -1l1 S ||0|| + 1lllh < 2D =: D
for any 3, C(O).
18

---

Published as a conference paper at ICLR 2026
Proof. We first bound R1 (L). The first term of (L) is bounded by Lemma 8, For the second term, we have
GL
De
D1+1ll1
GL
_ 1e (Io (9t =1ge))ll
$ GLVN N
11 (Ieco) (Be 791))l2
T
$ GLLNN
11
$ LT
Combining the first and second upper bounds, we have
D' (3D' + 2 + n/2
(VNI++ -) T.
(T) -
Then, by setting y to
D'
(3 + (3+2Pr/D')
7
G
2(VNL MINN++1/21) 1/2)T
we have
Rr(L) S 2V +
$ 2GD''N1/ (3 + 232PP/D')/T
= = PT)T).
Specifically, for (3 + 2Pr / < T, 11:e - de+1ll 1ll S MVNG & O(L-1). This corresponds to
1/2 and B = in Theorem which leads to
RT S O Lmax PP)T Lmax).
Lemma 8. Alg. ensures
3D"
D'
G
9t. d1 -2))
+ _-PP Pr +
2n
17
2
Proof. Let define V/.11 0r ngr. For any [T], setting ur+1 0, we have
(gr. E1 uz) = (Be
1.t1. 81 wz)
1
(1l
well2 + 11:6--1 - 0i112 - 11 uxl12)
2n
1
<
(ll
uell3 7 |1 1 11 us uel1))
21
1
(1l
wel13
11 - u41113 112 + -1 - -441113 |1ūc+1 - uell2 + 172119x 12)
27
1
(1
u+11l 11 + (2gr+1 u41 ue 24 u441) + 119:
21
1
(Ilie
1
|
uet 112 2D' 1|u - wet1ll1 1 + (9:
21
1
1 + l|ue u41 111 + G62
D'
<
(11
1
u441
21
2
19

---

Published as a conference paper at ICLR 2026
In the third line, the inequality The summation over E [7] leads to
[[[cço) Icoo (v) z ||
vll2 for any 2,
[0, DIN.
1
D
Σ (gtn Dt- uz) _
11
u1
14 ue+1 111 +
21
" t=
3D
D
uell + nGT
(22)
21
2
In the final line, use |²rt UT+1 |1 1 D'.
G PROOF OF THEOREM
In this section, we abuse notation, eliminating hats in the main paper: 24+ and vÊ+ are output of A and B in round respectively. yt+1 rf41 describes the final output of Alg. 5. For the sake of brevity, we also define
(x()))= = (gt, v + GL & Il:
(x(x²)== = (ge, v0) + GT
v 11.
Then, the bit for the combiner k is defined as
by ((( (((
(23)
3GD'NI/VVT.
Recall that of = =1 pt) )e - + pf where of is the weight computed by the k-th combiner B
Proof of Theorem 4. From Lemma 9 and 16, we have RS = O(V Pr) and 8 = 1.
Therefore, by Theorem 2, obtain
Rr S SO(V Lmax (1 (1+ Pr) T + Lmax).
Lemma 9. For T 2 max( log, T.e), Alg. 5 ensures
Rr(L) S O 1o)
Proof. We first consider large Pr case, where the following inequality holds:
2Pr
T
3+
D
32L log
Then the regret is bounded as
St Ue - ue) + +GLllyr - Me+1ll1 = Σ (gc. of - -w) + GGLI - -f
< 33GD'NI/AT 3GD'N VT
< 3/ (32L(3 + ( log
< /A + L / log
= OU
In the first inequality, we use Lemma 16 bound the switching cost. Below, consider the case of small Pr, where 3 + 2:2p/DD < T//32LLogg log T). Theorem shows that the optimal v) for OGD
is given by 17"h a333 2Pr/D', where
('/(G (2VNL 1)T). On the other hand,
20

---

Published as a conference paper at ICLR 2026
define the learning rates of A as 1/ av22-1, for k I,...,K K, where K [log2 321 log 7
T
1.
Because satisfies + /rr/D' - (32322Loog 7) I 2k there exists an a E [K] that satisfies
2Pr 2a 23 +
S 2" D
which implies 17" 1n S 2n Under r7", the regret upper bound of OGD is given by
T
D
2PT
(VNI+ + 1)
(g, Vi ue) + GI.lVV - Dit1ll1 5
3+
+n
27p
D'
22
2Pr)
+rr (VNL+) + ;) T
3+
2n
D'
V2+1
GV
D'(3D' (2
V2
< 3GD'N
(3+2PT/D')L
<GGDN (3
= P()
(24)
Using such a, the dynamic regret with switching cost can be decomposed of
T
Rr =
Σ 10t, U1 ue) +
GLIlye Detill1
Σ
gt, K ue) + GL - -0
1=1
Σ
(((kK)- - (i ue)
T Σ ((()tt - (((t-1))
T
Σ
- (4(09) + Σ (gt. yf - -u)) + +L.ll - -11+)l1))
W==+1
For the first term, we have
K Σ
Σ Σ (((tt)
1c((n-1)
Lomma 10
-3G VL.
(rit VT.lpt Petal)
k=0+1
K Σ
Lemmas 12 and 3GD'N!/VVI
U(itt)+ 1
+1 k=0+1
VL
Lomma
3/A'N
Σ
(AVn+log +2)
k=o+1
6GD'N 2 n log /2-k + (K a)
< 6GD'N 22V22 1) n2 log T + log
x 60GDN / Log 60GDN VLloTT
21

---

Published as a conference paper at ICLR 2026
In the last line, use n²" T2' I T. Similarly, for the second term, we have
((60)) - k2(2))) Lomma
S -3GD'NIVV
(48 - -1)b- -Lle pitzl)
Lemmas 12 and 14
3GD'NIAVL
T
(U(r9) + 2
)
+ +U(n)) + VT. +1)
VT.
< 3GD'NI/AVE T Un2) U(()) + 2T
+2
n2
Lemmna
S 3GI'NVIAVE 44T22og + 4 11 log T'
27
+2
11a
S 3GG 44 (3+ + 4 Tlog T + 2(3 + +2pp/D') +
< 3GD'N'VVVL 7
6(3 2
< 3GD'N'/ ( 6
s 54GDN /4 /
Lo
For the fifth line, recall that n2/2= = T2 <T/ < 2' = n² T. For the sixth line, because Pr < D', we use 3 + 2-2///'" =3 -3-2/P+/D PPr/D' 2 2342/TPrr/D s /2(9 + 4Pr/D'/T S /63 2Pr/D')T.
Finally, the third term is bounded by Eq. (24), that is,
T
Σ Lo Vi - u1) + GL
set S 6GDN PTD
Combining them, we have
(L) I P:) logT LT log
log + 60GDN /L log
which finishes the proof.
Lemma 10.
(e(o*)) - (((ut11)) S - 3/G VL
(p/b) VLDt - p)
T
T
Σ (B((0t) - -2((0)) - S3GD'N
((p) 176t - VIlpt - pital).
Proof. By using of = (1 -
-p pt yt
jut k-1 + pt v/ we have
(x(xx*) = (ge, v + GT - 1/1l
(1 11- Kir vt k 1 + p (gt, b -f) p. (1- $ 1 h-1 p vi
(1 (gr 2 1 + pt (gt, v (1-11)1)00 - +p -
vit1il1
+GL|Ix - - -
< (1
GD' + -
22

---

Published as a conference paper at ICLR 2026
Therefore, have
r
T -
((((*)) - (((0-11))
Σ
- (((")) GDLL - pi+al)
T
-3GD'N + - -pita)
T
33DD''N2/4
(ptt) vDlpt - 1t++
and
T
T $ (1-1)) - -1
Σ ((llrt) - ((()))
GD'L. -D''LI) p(+1l)
S -33GD'N'A L > (ot 11bE VDle p1t1)).
Lemma 11 (Eq. (11) in Zhang et al. (2022a)). U(n) S 4o
Lemma 12 (The former part of Theorem in Zhang et al. (2022a)). Suppose T 2 e and n N max(8e, 16l T). For any bit sequence b..... by. such that lb41 s 1/VL I the following inequality holds under Alg.4:
T
T 0,
T
2 v + U(n")++ (U(tt)+
Σ br VIlp. 1l 5 max
b >
+1
n²
VT.
Note that for * = T21-k in our algorithm, n* > max 16 log 7) is satisfied because n² > n = T21-K 2 32L log T 2 32L. In the last inequality, we use T e.
Lemma 13 (The latter part of Theorem Zhang et al. (2022a)). Under the setting in Lemma 12,
(V
Pitil VL
W log T
4T
Lemma 14. Assume T max( VL log, T, Then, |b/1 s 1/VL, for any E [K].
Proof.
1B4
((( Ec(e/t))
3GD'NN/AVI
1
(gc, 1 - vit + GT -- - GT. - vinllal
VI
(GD' GT.max((ll a 11v/ vi+ill))
3GD'N
VL
In the last line, we use Lemmas 15 and 16.
Lemma 15. llv." viaall D'N1/4 /N//A/L.for for any & [K].
23

---

Published as a conference paper at ICLR 2026
Proof. Since vi+1 is updated by OGD with the learning rate of 17", we have
llut vitall1 = I V & VNG. D'
2
GV
(2N1/2 L + 1)T
D'NI/4
2K-1
D'NI/4
D'NI/4
2T I
VL
VL
32L log
which concludes the proof.
Lemma 16. Assume T 2 max (T..og T, e). Then, 110. - -1-1ll S 2D /T. any k E [K].
Proof. We show it by induction. For 1, since ot ył. the inequality holds by Lemma 15. Suppose the inequality
D/N1/4
D'
1
1 - oftill1
log
(25)
VL
n
4T
holds for k 2 1. We note that this inequality satisfies LG]|uß - uftilli S 2GD' because
D'N1/1
D'
||u5 1/11111 I
log T +
L
VT.
n2
4T
i=2
D'N1/1
D'
K
2
Σ
log T +
L
VL
2T
47
1=2
D'N
D'
2
log T
T
log2 T
L
VL
V2
2T
32L log T
4T
D'NI/
D'
(V2
+1)
VTllog2 T
L
L
4
4T
D/N//4
D'
112+1)
L
L
4
4
21/N1/A
In the fifth line, we use log, T < T. We also note that the assumption T max (oav(VLlogg T, T,e) and Lemma 15 leads to 16t S 1/VL and Lemma 13 holds for + 1. Therefore, for t + have
|1u,+2
[[1 Pt
k+1 yut Pt Vi
k+1 k+1 (1 pitl o p1 #
S [[1 - pt x+1 (v, 2 + + (yt k+1 3/
k+t
(p. k+1 - -P - 3 )]
< (1 +++1)11 - rfiill + +r, +.t1 + llo
- v
|| + 1
-
k+1 ||] V/+1 k+1
||:
1/N
D'
1 log
4T ))
1
x+1 1/N
< (1 +1)
VL x=2
no
T
Pt
+ lpt A+1 P141 D'
1/N1/4
D'
k
Σ
log T
+
+ lp.
k+1
pt+l
D'.
L
VL
n
47
i=2
D'N1/4
D'
+
ni log T +
L
VL
47
2
In the fourth line, we use Eq. (25) and Lemma 15. Here we observe that Eq. (25) holds for Is + 1. Hence, by induction, conclude the proof.
24

---

Published as a conference paper at ICLR 2026
H
PROOF OF THEOREM 5
Proof. Let Dy a distribution of loss sequences, and & be the support Dg. Then, we have
BDg
Σ NELT]
(g), u)
sup Σ (gt, Ve u). hec BE(T]
Thus, will obtain our lower bound by showing lower bound of the expected regret. Moreover, we will construct a common distribution of instances for all algorithms. Hence, we can assume that the given algorithm deterministic without loss of generality.
We can assume that Lmax 2L + and T = Lmax K for some L, K >> 0 without loss of generality. Note that L (LLmax). We divide T rounds into K cycles, where a cycle has Lmax rounds. Let Łg be the first round in the k-th cycle.
We fix [K] arbitrarily. We consider the following distribution of instances.
yi
t
[t, tk + 2L 1] and t 2L
0
if i and t [tt, + --11
g
G(c++1)
if i and t E [ts + L,ts 2L -
2
otherwise
where εµ is Rademacher random variable, i... P(ce 1) P(ex -1) 1/2 Note that the demands of items in these instances do not rely on given algorithm. Indeed, we have
0 t [t. 2L 1]
d = D
t= +22
and 2 max(0, vi - d;) for all i E [N] and & E [T'. Note also that Lmax is an upper bound of the sell-out period since 2t becomes zero at the end of each cycle for all E [N].
Then, we discuss the cumulative loss by an algorithm. We have
22
+
2
(or, Uc)
Σ
(oc, Ut) +
Σ
for,
Ve)
15
t=t++
4 4+
G
4+22-1
Glex + 1)
Σ
2 Vi
yt
2
t=
t=
GL.
1++21-1
Glex + 1) yi
Σ
2 To
2
t=
where the inequality holds due to the definition of ot in the instances. Now, we focus on the second term the right-hand side. Since y! Ui for all E Its + L, 2L 1]. if eg have
to 4-L1-1
G(ex + +1)
Σ
V1 GLyI,+L-r
2
t= tx I
On the other hand, if cx 11 have
( 4----11
Gles + 1)
Σ
= 0.
2
to++b
Therefore, obtain
Ta +2
Gh
l 1+
Glex + +1)
(g, Me)
2
y + 1-1
+
Σ
y1
2 0.
(26)
2
1=t++
25

---

Published as a conference paper at ICLR 2026
Next, consider the cumulative loss by the comparator. Let T LK, e, E RN be the i-th canonical vector, and 2 = (0, De1}. Then, we have
min uEC(O)
(gt, u) = min
Kge,
u)
uEC(O)
tE[T]
kE[K]
t=
4
< min well
(g u)
kE(K]
t=1k
(4 (6+L-1
1+22111
G
G(Ee + 1)
min wEl
Σ
u
+
Σ
4²
2
2
kE(K]
1=
t=
GDLER
min well
Σ
2
KE(K]
GDL
min
Σ
ENU'.
(27)
2
(0.))
kE
Combining (26) and (27), we obtain
E
(gc. vc) - min
Σ
(ge, u)
E
Σ
Σ
(9t,
min uEC(O)
Σ
Σ
(ge, 2))
=EC(O)
[E|T)
(E[T]
kE[K]
t=
[K] t=
GDL:
E
min
CLu
2
urE(0,1)
kE[K]
GDL
E
max ('E(
Σ Egu
2
kE(K]
where the last equality derived from the fact that EE a Rademacher random variable. Finally, we obtain
GDL
E
max wE((,11
Σ curl"
GDL
E
Σ Ck
2
4
kE|K]
kEIK]
GDL
VK 2 R(GD Timax
where we used max(a, b) atb [a-b] in the equality, Khintchine inequality in the second in- equality, and K = L) in the last inequality.
I EXPERIMENTS
We present the results of numerical experiments using synthetic demand data. We conduct experi- ments varying the value of T e [2000, 5000, 10000, 20000, 50000) and measure the regret for each algorithm. We consider an inventory system for single item with warehouse capacity of D = 1, and a Newsvendor loss of (1)) = 5 max d4 y. 0) + max d,, 0), where de is the demand of round t. The demands are artificially generated as d, = D/2(1 (1 <(T)) sin(w(T)tt) where (T) 2.T log T/T and (TT) = 1/ log T. This parameterization ensures Lmax Ollog T) and demand fluctuation Σ |dc - d ~ O(log 7), which are dominated by <(T), and w('), respectively. We adopt the ideal comparator u, de which incurs zero loss and gives P1 = -i= -d- Initial inventory level and initial order are set to zero and 1/2, respectively. We set the parameter for MaxCOSD 7 0.5p/ D where P represents the minimum of the de- mand series (note that we consider a deterministic demand in this experiment). We note that OGD requires Pr input, whereas SOGD does not.
26

---

Published as a conference paper at ICLR 2026
MaxCOSD (Hinats, 2023)
(OGD)
Ours 1S0GD)
10
Regret
107
102
10000
20000
30000
40000
50000
Figure I: Experimental Results
The results are shown in Fig. In the experiment, our algorithms significantly outperform the base- line (MaxCOSD). We observe that the algorithms using the doubling trick (solid lines) sometimes achieve lower regret than those with Tmmax information (dashed lines). This because when using T.aax the learning rate is set smaller than that used in the doubling trick case. As result, it requires longer time to shift from the initial value to an appropriate order level, which can deteriorate the performance.
J THE USE OF LARGE LANGUAGE MODELS
In this paper, used large language models to refine and check our writing; we did not use them for any other significant tasks.
27


Reviews:
[{"review_id": "tQFxzqWrh6", "reviewer": "Reviewer_KX9o", "summary": "This paper addresses the Online Inventory Optimization (OIO) problem , which is an extension of Online Convex Optimization (OCO) that includes constraints from carryover stock. The authors make a strong case that the standard static regret metric is unsuitable for OIO, especially in non-stationary environments where demand fluctuates, as the best fixed strategy is often a poor comparator.  The main contribution is a new algorithm that provides a near-optimal dynamic regret guarantee , comparing the algorithm's performance to a time-varying sequence of decisions. This approach cleverly reveals a connection between OIO and Smoothed Online Convex Optimization (SOCO). This connection allows the authors to develop an algorithm with a dynamic regret bound of $\\tilde{\\mathcal{O}}(\\sqrt{L_{max}T(1+P_{T})})$ and an improved static regret of $\\tilde{\\mathcal{O}}(\\sqrt{L_{max}T})$, which is a $\\sqrt{L_{max}}$ improvement over existing work. The authors also provide a matching $\\Omega(\\sqrt{L_{max}T})$ lower bound for the static regret, resolving an open question from prior literature.", "questions": "1. Could you provide a bit more intuition for $L_{\\max}$? For example, in a simple stochastic setting with i.i.d. demand,  what would $L_{max}$ correspond to?\n\n2. The doubling trick restarts the base learner and the set $\\mathcal{L}_t$ seems to include the lengths of all previously completed cycles plus the current lengths of all active cycles. Does tracking this set introduce any significant computational or memory overhead, especially for large $N$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well structured and self-contained, with helpful summaries of prior results (Table 1). The example provided on page 1 does a good job of illustrating why dynamic regret is the more appropriate metric.\n\n2. The connection between OIO and SOCO via the projection lemma (Lemma 1) is interesting. It reduces a stateful inventory constraint problem to a well-studied smoothed OCO form.\n\n3. The paper provides the first near-optimal dynamic regret bound for the setting. Furthermore, it improves the static regret bound and provides a matching lower bound, which is solid. The appearance of $\\sqrt{L_{\\max}}$ is well motivated.", "weaknesses": "1. The paper is purely theoretical and lack of experimental validation.\n\n2. The paper simplifies the problem by assuming a linear warehouse capacity constraint.  The authors admit this is a limitation and that their proofs rely on it. This is a fair limitation, but it does reduce the generality of the result.\n\n3. The connection to adaptive regret or meta-OCO methods (e.g., MetaGrad, Ader) is acknowledged, but it’s unclear if simpler baselines could reach similar dynamic regret under relaxed constraints.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cLdibqkaPc", "reviewer": "Reviewer_KfMr", "summary": "This paper addresses Online Inventory Optimization (OIO) in non-stationary environments, a variant of Online Convex Optimization (OCO). It proposes a two-stage projection algorithm (base learner + feasible-region projection) that connects OIO to Smoothed OCO (SOCO), achieving near-optimal dynamic regret $\\tilde{O}(\\sqrt{L_{max}T(1+P_T)})$. The paper also provides the first $\\Omega(\\sqrt{L_{max}T})$ lower bound for OIO.", "questions": "1. Could you provide preliminary insights into extending the framework to include lead time or fixed ordering costs?\n2. In the high-probability extension of $L_{max}$, can you quantify how $\\delta$ influences the choice of $L_{max}$?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The two-stage projection strategy effectively eliminates carryover stock constraints by linking OIO to SOCO, a key innovation addressing dynamic environment limitations of prior OIO works.\n2. The paper establishes matching upper/lower bounds for OIO regret, and derives a lower bound as a valuable byproduct.", "weaknesses": "1. The paper does not evaluate the computational overhead of its algorithm. For example, the SOGD base learner requires $K=\\lfloor\\log_2 T/(32\\max(L,1)\\log T)\\rfloor+1$ experts and combiners, and the doubling trick involves restarting the base learner; the growth of computational cost with T or $L_{max}$ is unreported, which is critical for real-time inventory applications.\n\n2. The ideal comparator $u_t=d_t$ assumes $d_t\\leq D$ to satisfy $u_t\\in C(0)$. However, the paper does not discuss how the algorithm performs when demand $d_t>D$, which is a common real-world scenario, nor does it clarify whether the regret bound remains valid when $u_t$ must be capped at D.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eB09LVBDWR", "reviewer": "Reviewer_xAJn", "summary": "This paper studies the problem of online inventory optimization, which is a setting where the decision-maker sequentially chooses the order-up-to level such that the warehouse capacity is not exceeded, with the goal to minimize the total cost according to some loss function (that is revealed after choosing an action). They use the \"sell-out period\" as a measure of the difficulty of the environment. They propose an algorithm that uses the doubling trick to handle the fact that the sell-out period is not known, a base smoothed online convex optimization algorithm, and also a projection from the output of the base algorithm to the feasible set.", "questions": "- In Remark 1, the paper seems to suggest that the gradient of $\\ell(y_t) = p \\max(d_t - y_t)$ can be computed without knowledge of $d_t$. However, this is not correct.\n- It seems that in the definition of $L_\\max$, the sum over the items of the demand is greater than capacity. Otherwise, it seems to not make sense.\n- I found the first sentence of Definition 2 to be nonsensical.\n- Do all of the works in Table 1 use the same notion of $L_\\max$? I understand that the notation is different, but is the underlying quantity the same?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The algorithm appears to improve the regret rate beyond prior work that studied this problem. However, it is not clear that the referenced works are using the same assumptions as this paper.\n- The algorithm appears to provide dynamic regret rates in this setting, which appear to be new. There is a clear motivation for the utility of such analysis.\n- The use of smoothed OCO in this problem is a nice idea, although it is unclear to me how novel this idea is with respect to the literature.", "weaknesses": "- The comparison in Table 1 does not appear to be quite a fair comparison. In particular, the warehouse constraint in prior work Hihat et al. (2023) is a general convex set, whereas the one in the paper restricts the sum of the items to be less than the capacity. This seems to be quite a restrictive assumption of the items take up different space in the warehouse.\n- I found some of the presentation to be poor to the point that it was difficult to verify the theoretical results in the paper. I point these out and ask for clarification in the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)