Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets
arXiv:2606.14679v1 [cs.LG] 12 Jun 2026
Anthony Pineci UIUC [email protected]
Yunzong Xu UIUC [email protected]
Abstract Online inventory optimization (OIO) is online convex optimization with physical memory: inventory carryover makes the feasible action set depend on the past. A natural principle, used in stochastic inventory learning and recently in OIO under a single linear capacity constraint, is to maintain a hidden target chosen by an online learner and implement its projection onto the currently feasible order-up-to set. We prove that this simple principle is optimal for OIO on arbitrary bounded convex capacity sets. With online gradient descent as the base learner, the method improves the best known regret guarantee for OIO on general convex sets from inverse to inverse-square-root dependence on the common-demand probability, and we prove a matching lower bound. The same principle gives the first polylogarithmic regret guarantee for strongly convex losses and the first dynamic regret guarantee adapting to Euclidean path variation on general convex capacity sets. The analysis introduces a norm alignment principle: the right state variable is the distance from the hidden target to the feasible set, measured in the same norm as the projection. Under norm alignment, this distance evolves pathwise as a scalar queue, with target movement as arrival and common demand as service. This reduction to one-dimensional queue control resolves the state dependence and extends the guarantees to general convex capacity sets, beyond the reach of prior productwise approaches. Experiments on synthetic and real-world inventory data corroborate the theory.
1
Introduction
Inventory control is a foundational problem in operations research and stochastic control (Arrow et al., 1951, 1958; Dvoretzky et al., 1952b,a; Bellman et al., 1955; Porteus, 2002); classical inventory models were among the early motivations for dynamic programming.1 This paper studies its canonical periodic-review formulation: in each period, a retailer, warehouse, or fulfillment system selects target stock levels for multiple products, subject to general capacity constraints, while demand depletes inventory and costs are incurred over time. Recent work has brought this classical model into contact with online learning; see the survey by Chao et al. (2023). From an online-learning viewpoint, each period in inventory control resembles a round in online convex optimization (OCO): the learner chooses an action, observes local cost information, and is evaluated against a comparator. The analogy is incomplete, however, because it misses the central physical feature of inventory control: stock carries over. Inventory can be replenished componentwise up to a chosen order-up-to vector, but it can decrease only when demand consumes it. Thus a gradient step may point toward a lower stock vector, while the inventory already on the shelf makes that target physically infeasible. 1
According to Bellman (1958), “Two of the most interesting classes of dynamic programming processes, viewed from the vantage points of both analysis and application, are those of inventory control and production smoothing.”
1
The online inventory optimization (OIO) model of Hihat, Gaïffas, Garrigos, and Bussy (2023) is a recent formalization at the interface of inventory control and adversarial online learning. In OIO, the learner chooses an order-up-to vector in a capacity set Y ⊆ Rn+ , but the chosen vector must also dominate the current inventory state. If the inventory state were always zero, OIO would reduce to standard OCO on Y (Zinkevich, 2003; Shalev-Shwartz, 2012; Hazan, 2016; Orabona, 2019). Otherwise, inventory carryover makes feasibility state-dependent: past actions constrain future choices. Compared with classical periodic-review inventory models (Snyder and Shen, 2019), OIO does not require a known stochastic demand model. Compared with data-driven inventory learning under censored demand (Huh and Rusmevichientong, 2009; Shi et al., 2016; Zhang et al., 2018; Lyu et al., 2025; Guo et al., 2026), OIO broadens the learning formulation in two directions: losses and demand may vary adversarially over time, and capacity constraints may be arbitrary bounded convex sets. The first general-convex OIO algorithm, MaxCOSD (Hihat et al., 2023), handles the statedependent feasibility through adaptive cycles: it waits for moments when a proposed update to the implemented order level is compatible with the inventory state. This idea is robust enough to work for arbitrary bounded convex capacity sets and adversarial losses. Under uniformly probably positive demand (UPPD), a non-degeneracy condition on the common demand (i.e., minimum √ demand over e all products) with probability parameter µ, its high-probability static regret is O( T /µ). The 1/µ factor controls how long the system may wait before all products receive enough demand to reduce excess stock, and in large or intermittent-demand systems this waiting time can dominate the guarantee. A different algorithmic principle has long been attractive in inventory learning. Rather than tracking the implemented level directly, a base learner maintains a hidden desired level and projects it onto what the current state permits. This hidden-target idea appears in queueing analyses for single-product learning (Huh and Rusmevichientong, 2009), in multiproduct algorithms under a linear warehouse constraint (Shi et al., 2016), and most explicitly in the recent hidden-target OIO method of Ichikawa, Takemura, and Matsuoka (2026). The principle is also empirically appealing: Hihat et al. (2023) reports that this idea can improve MaxCOSD’s empirical performance in multi-product, multiconstraint settings, although no guarantee was known at MaxCOSD’s level of generality. However, extending existing analytical techniques to the general capacity setting faces a methodological barrier. These analyses rely on the linear warehouse constraint and productwise sell-out structure, but Appendix B shows why such productwise control cannot be extended to general convex capacity sets. The reliance on productwise control also leads to additional polynomial dependence on the number of products n, which is undesirable from the norm-based viewpoint standard in OCO.
1.1
Our contributions
This paper shows that the simple and natural hidden-target projection method is already powerful enough for the full general-convex OIO model. The missing ingredient is not a more complicated algorithm, but a better geometric analysis. At each round, the base learner produces hidden targets zt ∈ Y. Given the current implementable set Jt , the algorithm implements the projection ∥·∥ yt = ProjJt (zt ) measured in a given norm ∥ · ∥. We track the target-implementation gap qt = dist∥·∥ (zt , Jt ) = ∥zt − yt ∥ in the same norm ∥ · ∥. Letting dmin := mini dt,i denote common demand, t we establish that qt is governed by a standard Lindley queue recursion: + qt+1 ≤ qt + ∥zt+1 − zt ∥ − dmin . t This inequality is pathwise: it holds for every realization of the inventory dynamics, with no averaging or distributional assumption. Its proof is purely geometric, using only the convexity of Y, 2
Method (Reference)
Capacity Set
Demand Primitive
Regret type
Bound
MaxCOSD (Hihat et al., 2023)
general
UPPD µ
static
e O
HT (Ichikawa et al., 2026)
linear
sell-out period Lmax
static dynamic
HT (Ours)
general
UPPD µ
static (cvx)
static (s.c.) dynamic
√
T /µ
√ e n1/4 Lmax T O p e n1/4 Lmax (1 + PT,1 )T O p p e T /µ / Ω T /µ O with further norm refinement via mirror descent O(log(T p /δ) log(T )/µ) e (1 + PT,2 )T /µ O
Table 1: Closest adversarial-demand OIO guarantees, suppressing problem-dependent constants. HT stands for hidden-target methods. For Ichikawa et al. (2026), the n1/4 term appears explicitly in intermediate bounds and is absorbed into the big-O notation of their final stated regret. Here PT,1 and PT,2 denote comparator path variation in ℓ1 and ℓ2 , respectively. For (Ours), the static convex row lists p the upper bound and matching lower bound; the mirror descent refinement keeps e the same O( T /µ) rate while exposing sharper norm-based parameters; the strongly convex (s.c.) and dynamic bounds appear on separate rows. Appendix C relates UPPD and Lmax . the inventory dynamics, and the norm alignment principle (Section 2.4), rather than any special structure of the capacity set. Thus the target-implementation gap evolves as a one-dimensional queue: moving the learning target creates arrival while common demand supplies service. At this level of generality, the queue reduction is surprising. Queueing ideas entered inventory learning through Huh and Rusmevichientong (2009) and Shi et al. (2016), who used them to track productwise feasibility errors. Such queues naturally handle a single product or linear constraint, but extending them to general capacity constraints encounters genuine obstructions; see Appendix B and Lyu et al. (2025). Recent work has therefore replaced queueing with alternative devices, including minibatching, cyclic bookkeeping, or overshooting-loss control (Hihat et al., 2023; Lyu et al., 2025; Ichikawa et al., 2026; Guo et al., 2026). Our reduction revives the queueing route by changing the state variable: the queue is the norm-aligned distance from the hidden target to the implementable set. This geometric Lindley queue holds independent of specialized capacity structure, so its distribution-free control reduces OIO regret to the base learner’s OCO regret plus a switching-cost term under the UPPD condition. The reduction yields several state-of-the-art consequences, summarized in Table 1. 1. Under an instantiation of the hidden-target method with a simple online gradient descent (OGD) base learner, our static regret results improve the µ dependence of the best known general-convex OIO guarantee from µ−1 to µ−1/2 and establish optimality via a new lower bound. Even under a single linear capacity constraint, our queue-based analysis removes the explicit n1/4 factor exposed by the hidden-target analysis of Ichikawa et al. (2026). 2. Under strongly convex losses, the same algorithm obtains polylogarithmic regret, addressing an open direction raised by Hihat et al. (2023). 3. In dynamic environments, the bound depends on the Euclidean path variation PT,2 rather than the larger ℓ1 variation PT,1 , sharpening Ichikawa et al. (2026)’s result on more general geometry.
3
We instantiate this with OGD when PT,2 is known a priori and smoothed OGD (SOGD) (Zhang et al., 2022) when it is not; both achieve the same regret rate (up to polylogarithmic factors). 4. The reduction is not tied to Euclidean projection. If the base learner is online mirror descent (OMD) withpa strongly convex regularizer R, then a new HT-OMD algorithm obtains static e G∗ BR T /(σµ) , where G∗ is the corresponding dual-gradient bound, σ is the strongregret O convexity modulus of R, and BR is the relevant Bregman diameter. Thus arbitrary bounded convex capacity sets admit geometry-sensitive refinements once paired with a suitable regularizer. This extends the recent use of OMD in stochastic inventory learning (Guo et al., 2026) to adversarial OIO and general convex capacity sets. All our guarantees are dimension-free in the standard norm-based sense: dimension enters through problem parameters such as the capacity set diameter, gradient norm, and µ, but not through an additional explicit factor of dimension n. While the parameter µ can still deteriorate with dimension, our result isolates this difficulty in the demand primitive instead of adding a separate algorithmic dimension penalty.
1.2
Relation to prior work
√ Online convex optimization. Projected online gradient descent gives the classical O( T ) regret guarantee for Lipschitz convex losses (Zinkevich, 2003; Shalev-Shwartz, 2012; Hazan, 2016; Orabona, 2019), and logarithmic regret under curvature appears in the strongly convex and exp-concave OCO literature (Hazan et al., 2007). Dynamic regret compares against a changing comparator sequence and is controlled by path variation (Hall and Willett, 2013; Jadbabaie et al., 2015). Our OGD and strongly-convex analyses build on standard OCO arguments; the contribution is to show that the additional complexity of carryover effects in inventory control can be reduced to a switching-cost term via hidden-target learning. For unknown path variation, we use the smoothed OCO meta-learner of Zhang et al. (2022) as a base learner. Stochastic inventory learning. Stochastic inventory learning asks how to make inventory decisions when demand distributions are unknown, often under censoring, lost sales, or capacity constraints; see Chao et al. (2023) for a survey. A recurring obstacle is implementability: a learning rule may propose an inventory target that is not feasible from the current state. One influential response is queueing-style analysis, from the single-product recursion of Huh and Rusmevichientong (2009) to the multiproduct analysis of Shi et al. (2016). This queueing line has continued in several structured inventory-learning models (Chen et al., 2020; Yuan et al., 2021; Ding et al., 2024; Yang and Huh, 2024), but its arguments remain tied to a single product or linear capacity constraint. A complementary line has moved toward alternative algorithmic and analytical devices for refined guarantees or richer stochastic models. Guo et al. (2026) used cyclic online mirror descent to improve the product-dimension dependence in the linear-capacity setting of Shi et al. (2016); Zhang et al. (2018) used cycle subgradients and a bridging construction for perishable inventory; and Lyu et al. (2025) developed a minibatch-SGD metapolicy for several stochastic inventory systems, including multiproduct systems with multiple linear constraints and multiechelon serial systems. Our contribution is complementary to both lines. We show that queueing structure persists in far more general capacity geometry once the right state variable is used. The hidden target can be generated by a standard online convex optimization method, while a geometric queue-clearing argument enforces implementability. Thus, in our setting, feasibility does not require cyclic schedules, bridging constructions, or minibatching. The result gives guarantees for adversarial loss sequences on general convex capacity sets. 4
Online inventory optimization. To generalize stochastic inventory learning beyond i.i.d. demand, fixed dynamics, and newsvendor-specific losses, Hihat et al. (2023) introduced the adversarial OIO model, which contains OCO as a special case. Their MaxCOSD algorithm works for general convex capacity sets but controls learning through cycle boundaries, leading to µ−1 dependence under the UPPD parameter µ. Ichikawa et al. (2026) analyzed hidden-target projection and obtained dynamic regret guarantees in nonstationary environments, but their proof crucially relies on the linear capacity set and specialized productwise sell-out analysis (see Appendix B). The present paper keeps the hidden-target principle and replaces the sell-out analysis by a Euclidean/norm-aligned queue, giving optimal µ dependence on general convex sets. Learning-based inventory control. Deep reinforcement learning and simulation-based methods have recently become effective for large inventory systems with rich dynamics (Madeka et al., 2022; Alvo et al., 2023; Maggiar et al., 2025; Bloem et al., 2025). These methods emphasize empirical performance, differentiable simulation, network structure, or supply-chain-scale policies. They are complementary to the present work, whose goal is to establish sharp adversarial regret guarantees for simple and lightweight online-learning methods.
1.3
Notation and Organization
We denote N as the set of positive integers and write [m] := {1, . . . , m} for any m ∈ N. Let Rn denote n-dimensional Euclidean space, and let Rn+ and Rn++ denote its nonnegative and strictly positive orthants, respectively. For a scalar a, write a+ := max{a, 0}; for a vector v ∈ Rn , v + denotes the coordinatewise nonnegative part, (v + )i := max{vi , 0}. We use a ⪰ b for coordinatewise inequality. Throughout the framework, ∥ · ∥ is an admissible norm with dual ∥ · ∥∗ (see Section 2.3), while instantiations in Section 4 make further specifications on the exact norm that is used. Probabilistic statements are with respect to a filtration (Ft )t≥0 . The learner’s action at round t is Ft−1 -measurable, whereas the demand and loss chosen after the action are Ft -measurable. For nonnegative quantities f and g, we write f = O(g) and f = Ω(g) to mean that f ≤ Cg and f ≥ cg, respectively, for constants C, c > 0 independent of T, µ, Lmax , n. We write f = Θ(g) if both bounds hold. We use e to suppress polylogarithmic factors in T . O(·) The rest of the paper is organized as follows. Section 2 introduces the OIO model, the hiddentarget projection algorithm, and the norm-alignment principle. Section 3 proves the geometric Lindley recursion and the general hidden-target reduction. Section 4 instantiates the reduction with OGD, SOGD, and OMD to obtain static, strongly convex, dynamic, and mirror-descent regret guarantees. Section 5 presents numerical experiments, and Section 6 concludes. The appendix contains experiment details, the obstruction to productwise queue analyses on general convex sets, a discussion of UPPD, and all omitted proofs.
2
Model and hidden-target projection
2.1
The OIO model
We work in the model of Hihat et al. (2023), generalized to adaptive adversarial settings for the environment’s choice of demand and loss function. The environment first sets the initial inventory state to zero, i.e. x1 = 0, then for every round t = 1, . . . , T : 1. The learner observes an inventory state xt ∈ Rn+ and must choose an order level yt ∈ Y that
5
obeys the inventory feasibility constraint: yt ⪰ xt
(1)
The inventory is instantly replenished to yt . 2. The environment observes the learner’s action and chooses a demand dt ∈ Rn+ , then a loss function ℓt : Y → R. The next inventory state xt+1 ∈ Rn+ is updated so that it adheres to the inventory dynamics constraint: xt+1 ⪯ (yt − dt )+ (2) 3. The learner incurs a loss ℓt (yt ) and observes a subgradient gt ∈ ∂ℓt (yt ) that may help them make a choice in the next round. We use the same convexity and boundedness assumptions as Hihat et al. (2023): Assumption 2.1 (Convex and bounded OIO problem). Fix an admissible norm ∥ · ∥ on Rn (Definition 2.3) with dual norm ∥ · ∥∗ . The capacity set Y ⊆ Rn+ is nonempty, closed, convex, and bounded with diameter D := supu,v∈Y ∥u − v∥ measured in this norm. Each loss ℓt : Y → R is convex, and every observed subgradient gt ∈ ∂ℓt (yt ) satisfies ∥gt ∥∗ ≤ G∗ . Equality in (2) gives the usual lost-sales dynamics. The inequality allows for alternative dynamics incorporating additional depletion or perishability, as in Hihat et al. (2023). If the state never binds, the only constraint is yt ∈ Y and the model is ordinary OCO on Y. The difficulty is precisely that the feasible action set at time t is shaped by earlier order-up-to decisions. Since the demand is chosen prior to the loss function, this framework accommodates the standard newsvendor loss used in the inventory literature: ℓt (y; dt ) =
n X
ht,i (yi − dt,i )+ + pt,i (dt,i − yi )+ .
(3)
i=1
Here ht , pt ∈ Rn+ correspond to the holding cost (overage cost) and lost-sales penalty (underage cost) respectively. Following the OIO framework (Hihat et al., 2023), we do not permit the loss function ℓt to depend on the current inventory xt . However, under a lost-sales dynamic, newsvendor loss (3) can naturally accommodate purchasing costs using a standard cost transformation (Snyder and Shen, 2019, Paragraph 4.3.2.4). The framework’s requirement for subgradient observability does not require full demand observation. A realistic assumption is that the learner may only observe sales st = min{yt , dt } taken coordinatewise. In this case, the vector with coordinates given by ht,i 1{yt,i > st,i } − pt,i 1{yt,i = st,i } is an observable subgradient of (3) at yt . This shows that our subgradient requirement is sufficient for the canonical inventory loss, while the analysis permits arbitrary convex losses with local subgradient feedback. We measure algorithm performance using Regret. For a comparator sequence u1:T ∈ Y T , dynamic regret is T X RT (u1:T ) := ℓt (yt ) − ℓt (ut ) . t=1
Static regret is the special case ut ≡ u. 6
2.2
Hidden-target projection and the regret decomposition
At time t, define the implementable set Jt := Y ∩ {y ∈ Rn | y ⪰ xt }. This set is always nonempty: if yt ∈ Jt , then (2) gives xt+1 ⪯ yt , so the same point yt belongs to Jt+1 . We work in the standard projection-oracle model of OCO, assuming nearest-point projections in the norm ∥ · ∥ onto Y and onto Jt can be computed. Hidden-target projection lets an online learner move in the fixed set Y while a separate inventory layer enforces physical feasibility. When the base learner proposes zt ∈ Y, the implemented orderup-to level is ∥·∥ yt = ProjJt (zt ) ∈ arg min ∥zt − y∥. (4) y∈Jt
This is the algorithmic principle behind projected base-stock methods such as DDM (Shi et al., 2016) and the hidden-target OIO method of Ichikawa et al. (2026). After implementing yt , hidden-target projection observes only a subgradient gt ∈ ∂ℓt (yt ) at the implemented point. The linear loss ft (z) = ⟨gt , z⟩ is therefore the most informative function we can construct from this feedback, and so we take the base learner to be an online linear optimizer (OLO). The implementation is formalized in Algorithm 1. Algorithm 1: Hidden-Target Projection Meta-Algorithm Input: Capacity set Y, base learner (OLO) on Y, initial target z1 ∈ J1 for t = 1, 2, . . . , T do Observe inventory state xt and set Jt = Y ∩ {y ∈ Rn | y ⪰ xt }; ∥·∥
Implement yt = ProjJt (zt ); Observe gt ∈ ∂ℓt (yt ) and the next state xt+1 ; Feed the linearized loss ft (z) = ⟨gt , z⟩ to the base learner and receive zt+1 ∈ Y; end The regret analysis begins with a decomposition inherited from earlier hidden-target arguments, now measured in the general norm: ∆base T (u1:T ) :=
T X ⟨gt , zt − ut ⟩,
∆gap T :=
t=1
T X
∥zt − yt ∥,
t=1
∆mv T :=
T −1 X
∥zt+1 − zt ∥.
t=1
The first quantity is the ordinary OCO regret of the base learner. The second is the cost of physical implementation of the target. The third tracks target movement, which the queue reduction will charge as a switching cost on the base learner. Lemma 2.2 (Target regret plus implementation error). Let (zt )Tt=1 ∈ Y T be any hidden-target sequence, and let (yt )Tt=1 be defined by (4). Then for every comparator sequence u1:T ∈ Y T , gap RT (u1:T ) ≤ ∆base T (u1:T ) + G∗ ∆T .
(5)
The lemma reduces regret to a base learner’s OCO regret plus the cumulative implementation gap ∆gap T . However, controlling this gap is challenging because past actions carry over into the current implementable set Jt . Instead, we relate ∆gap to the base learner’s target movement ∆mv T T through a queue recursion (Section 3). At every round, this queue’s length is the gap qt = ∥zt − yt ∥, with target movement ∥zt+1 − zt ∥ as arrival and common demand dmin = mini dt,i as service. If t additionally the base learner’s cumulative target movement is bounded over every clearing window e −1 ), then UPPD ensures with high probability that the common demand clears of length Bδ = O(µ mv the queue, giving a bound ∆gap T ≤ Bδ ∆T . Thus, regret from the implementation gap becomes a switching cost weighted by the length of the clearing window. 7
For a single linear warehouse constraint, prior work (Shi et al., 2016; Ichikawa P et al., 2026) tracks the implementation term product by product, relying on the linear budget i yi ≤ D to tie the productwise bounds together. Curved convex sets have no such budget. Without it, a projection that drives one product up to meet inventory can force unrelated products down by arbitrarily larger amounts, breaking the per-product correspondence. Appendix B formalizes why no per-product analysis extends to general convex sets. The next section develops a different approach which controls the implementation term through a single geometric distance without using any per-product accounting.
2.3
Admissible norms
The queue recursion driving the analysis (Proposition 3.1 below) holds for a broad class of norms, characterized by a single compatibility condition with the coordinatewise structure of the inventory model. We call this class admissible. Definition 2.3 (Admissible norm). A norm ∥ · ∥ on Rn is admissible for OIO if it dominates the ℓ∞ norm: ∥x∥∞ ≤ ∥x∥ for every x ∈ Rn . Equivalently, |xi | ≤ ∥x∥ for every x ∈ Rn and every i ∈ [n]. Geometrically, a norm is admissible if its unit ball is contained in the ℓ∞ unit cube. This condition is precisely what is needed to convert movement in the norm ∥ · ∥ to a coordinatewise bound, which is in turn what allows the inventory dynamics constraint (2) to be satisfied through measuring the movement of order levels. Example√2.4. Every ℓp norm with p ∈ [1, ∞] is admissible. A diagonally weighted Euclidean norm ∥x∥W := x⊤ W x with W = diag(w1 , . . . , wn ) is admissible if and only if wi ≥ 1 for every i.
2.4
The norm alignment principle
The queue recursion driving our analysis depends on a single methodological commitment that we now state explicitly. Throughout the paper, we require the projection, the queue state, the target movement, and every lemma and proposition in the queue analysis to be expressed in the same admissible norm ∥ · ∥. We call this requirement the norm alignment principle: Principle 2.5 (Norm alignment). A hidden-target analysis is norm-aligned if a single admissible norm ∥ · ∥ serves simultaneously as: ∥·∥
1. The projection norm, yt = ProjJt (zt ), 2. The queue norm, qt = ∥zt − yt ∥, 3. The movement norm, ∥zt+1 − zt ∥, 4. The norm in which the queueing recursion (Proposition 3.1) and its supporting lemmas are stated and proved. We introduce this principle because it is what makes the queue recursion close without any multiplicative factors. Under norm alignment, the queue recursion follows geometrically using only convexity of Y, the norm axioms, and optimality of the nearest-point projection. The requirement is fundamental, not just a way to optimize constants or dimension factors. If the algorithm projects in one norm but the queue is measured in another, norm equivalence gives at best a multiplicative 8
y (2)
Y B∞(yt , d− t ) qt
zt
yt
yt −d− t 1
contained in Jt+1
d− t
(yt −dt )+
Jt possible xt+1
xt y (1)
Figure 1: A geometric illustration of the short move lemma. It shows that any y ′ ∈ B∥·∥ (yt , dmin t ) satisfies y ′ ⪰ xt+1 , so if y ′ is also in Y, then y ′ ∈ Jt+1 . constant inside the queue recursion. Such a factor compounds over a clearing window, yielding an exponentially looser bound. Norm conversion is therefore safe only after the aligned queue recursion has been established. Hidden-target analyses that mix norms across these roles, such as the ℓ1 switching cost with ℓ2 projection used by Shi et al. (2016) and Ichikawa et al. (2026), must compensate with constraintspecific structure to bypass the geometric queuing argument presented in this paper. For more details on why previous analytical approaches did not generalize to arbitrary convex sets, see Appendix B.
3
The target-implementation queue
The inventory-specific part of our analysis only depends on the path of the targets and inventory levels. No stationarity or independence of the demand realizations is needed until we convert the pathwise recursion into a high-probability clearing statement. With the admissible projection norm ∥ · ∥ from Section 2.3 fixed, let qt := dist∥·∥ (zt , Jt ) = ∥zt − yt ∥,
dmin := min dt,i . t
(6)
i∈[n]
∥·∥
Proposition 3.1 (Target-implementation queue). For the aligned implementation yt = ProjJt (zt ), under the inventory dynamics constraint (2), for every t ∈ [T − 1], + qt+1 ≤ qt + ∥zt+1 − zt ∥ − dmin . t
(7)
Figures 1 and 2 visualize the geometric proof with specific realizations of the demand and choices for the hidden target from the base learner. Throughout the figure, distances are shown using the Euclidean norm, but the geometric intuition remains the same as long as the norm is admissible. The proof relies on the following lemma to ensure that if a point moves from the previous order level by a sufficiently small amount, then it remains feasible.
9
y (2)
Y qt+1
zt+1 zt
yt+1 wt d − yt t
zt+1
∥zt+
1 −w t∥
zt
qt
dt− y
t
qt
∥zt+1 −zt ∥
Jt+1
(b) Triangle inequality
xt+1
xt+1 Jt
(a) Setup & interpolation
+ Figure 2: Geometric proof of the queue recursion qt+1 ≤ (qt + ∥zt+1 − zt ∥ − dmin t ) for the case where ∥zt+1 − yt ∥ > dmin t , building on the setup in Figure 1. (a) For any zt+1 ∈ Y, the interpolation point wt a distance dmin away from yt on the line from yt toward zt+1 must be feasible, providing a t segment whose length bounds qt+1 . (b) Isolating the relevant points, the triangle inequality gives the bound ∥zt+1 − wt ∥ + dmin ≤ qt +t∥zt+1 − zt ∥, which combines with the prior diagram to give the t final recursion. (1)
x
y
Lemma 3.2 (A short move remains feasible after demand). Let y, y ′ ∈ Rn+ and d ∈ Rn+ . If ∥y ′ − y∥ ≤ dmin := mini di , then y ′ ⪰ (y − d)+ . This result is shown visually in Figure 1. For an order level yt , any possible xt+1 must be coordinatewise smaller than any point in the ℓ∞ ball of radius dmin centered at yt . This in turn t means that any point that is coordinatewise at least as large as the corner of the ℓ∞ ball must satisfy the inventory feasibility constraint (1), including the ball itself. This explains our choice of an admissible norm: the ball around yt of radius dmin induced by ∥ · ∥ must be contained in the ℓ∞ t ball, and hence also satisfies the inventory feasibility constraint. Any point inside the intersection of this ball and Y must therefore be in the next feasible order-level set Jt+1 . When the next point zt+1 is chosen, there are two options. In the first case, zt+1 lies within distance dmin of the implemented point yt , but the short move lemma makes zt+1 feasible at the t next round so yt+1 = zt+1 and the queue clears with qt+1 = 0. Otherwise, for the second case where zt+1 lies outside the dmin ball around yt , we turn to Figure 2a. By the convexity of Y, we t interpolate between yt and zt+1 and choose the point wt that is distance dmin away from yt to make t it feasible. Crucially, the aligned projection certificate (Lemma D.5), which states that projecting in ∥ · ∥ minimizes the distance to any feasible witness, gives qt+1 ≤ ∥zt+1 − wt ∥. Finally, Figure 2b uses the triangle inequality to bound this distance. Combining with the first case gives the queue recursion. To obtain high-probability regret, we use the non-degeneracy demand condition introduced by Hihat et al. (2023).
10
Assumption 3.3 (Uniformly probably positive demand). There exist µ ∈ (0, 1] and ρ > 0 such that, for every round t, almost surely P(dmin ≥ ρ | Ft−1 ) ≥ µ. t UPPD says that, no matter the past, there is conditional probability at least µ of a common demand shock of size ρ. So over any sufficiently long window of rounds, at least one such shock occurs with high probability. To exploit this condition for queueing control, our analysis partitions [T ] into queue-clearing windows where the shocks can clear the accumulated queue, reducing the cumulative gap to a bound on the target’s movement. If the base learner moves sufficiently slowly, by at most ρ over each such window, the queue cannot persist across windows. Fixing a failure probability δ ∈ (0, 1), we write Bδ := ⌈µ−1 log(T /δ)⌉ for the corresponding clearing-window length under UPPD. Before moving to the regret reduction, we formally specify the conditions that the base learner must satisfy. We treat the base learner as a black box specified entirely by its inputs and outputs, with an additional requirement on the movement of its outputs. At each round the base learner receives the linearized loss ft (z) = ⟨gt , z⟩ on Y, where the gradient satisfies ∥gt ∥∗ ≤ G∗ , and produces a hidden target zt+1 ∈ Y. The reduction depends on the target sequence only through the following two conditions, both measured in the norm ∥ · ∥. Assumption 3.4 (Base learner conditions). The base learner produces targets (zt )Tt=1 ⊂ Y such that: (i) Linearized regret bound. There is a function RT (u1:T ) for which, for every comparator sequence u1:T ∈ Y T , ∆base T (u1:T ) ≤ RT (u1:T ). (ii) Windowed movement bound. For every t with 1 ≤ t ≤ T − Bδ , t+B δ −1 X
∥zr+1 − zr ∥ ≤ ρ.
(8)
r=t
The two parts of Assumption 3.4 are imposed on the target sequence, not on the internal mechanism of the base learner. Any specific algorithm, such as projected OGD, smoothed OGD, or mirror descent, defines a valid base learner once parts (i) and (ii) are verified in the projection norm. Section 4 carries the verification for these instantiations. Theorem 3.5 (Hidden-target reduction). Under Assumption 2.1 and UPPD (Assumption 3.3), suppose the base learner satisfies Assumption 3.4(ii) and initializes with a feasible target z1 ∈ J1 . Then, with probability at least 1 − δ, mv ∆gap T ≤ Bδ ∆T ,
mv RT (u1:T ) ≤ ∆base T (u1:T ) + G∗ Bδ ∆T
(9)
for every comparator sequence u1:T ∈ Y T . In particular, if Assumption 3.4(i) additionally holds with regret function R, then RT (u1:T ) ≤ RT (u1:T ) + G∗ Bδ ∆mv T Theorem 3.5 is a reduction from OIO to OCO with switching cost. The base learner must control two ordinary quantities, linearized regret and cumulative movement, while the inventory layer contributes only the clearing-window factor Bδ . This modularity is the advantage of the 11
norm-aligned queue construction: the inventory proof is agnostic to how zt was generated and to the specific admissible norm chosen, and the base learner never reasons about products or sell-out events. The lack of extra multiplicative factors in the queue recursion (7) is essential for our construction. + Using norm conversion would yield a recursion of the form qt+1 ≤ C[qt + at − dmin t ] with C > 1, but this does not support the same queue clearing argument. The constant multiplies the residual backlog before the next service opportunity, whereas our approach leverages norm alignment to ensure the queue clears regularly. Relation to sell-out reductions. The linear-capacity hidden-target analysis of Ichikawa et al. (2026) tracks productwise sell-out quantities and controls switching in ℓ1 . In contrast, our reduction uses the state variable dist∥·∥ (zt , Jt ), which makes it applicable to arbitrary convex feasible sets Y. This change also eliminates the explicit n1/4 factor arising from the ℓ1 movement control in Ichikawa et al. (2026), and replaces PT,1 in dynamic regret by the smaller Euclidean path variation PT,2 . This comparison should not be read as saying that the wrong norm merely costs powers of n. Rather, a productwise or misaligned queue needs a conservation identity that is absent on curved convex capacity sets. Appendix B provides a two-dimensional example to illustrate this obstruction. The tradeoff is the local movement condition of Assumption 3.4(ii) on the base learner, which is not required in Ichikawa et al. (2026). For the OGD and SOGD base learners used in Section 4, however, this condition is automatically satisfied once the stepsize or switching parameter is chosen at the clearing-window scale. Thus, for these algorithms, the additional requirement needed to handle general geometry imposes no further loss in the final regret guarantees.
4
Optimal and adaptive guarantees
We now instantiate the reduction. Except in Section 4.4, the instantiations in this section use gradient-descent base learners with the Euclidean norm ∥ · ∥2 as the projection norm. Section 4.4 then turns to mirror-descent base learners and non-Euclidean projection geometries. We also write D2 and G2 for the capacity-set diameter and dual gradient bound respectively from Assumption 2.1 specialized to the ℓ2 norm. Taken projected OGD as the base learner, the Hidden-Target OGD is given in Algorithm 2. Its update is ∥·∥
yt = ProjJt 2 (zt ),
∥·∥
zt+1 = ProjY 2 (zt − ηt gt ).
(10)
Algorithm 2: Hidden-Target OGD Input: Capacity set Y, initial target z1 ∈ J1 , stepsizes (ηt ) for t = 1, 2, . . . , T do Observe inventory state xt and set Jt = Y ∩ {y ∈ Rn | y ⪰ xt }; ∥·∥
Implement yt = ProjJt 2 (zt ); Observe gt ∈ ∂ℓt (yt ) and the next state xt+1 ; ∥·∥
Update zt+1 = ProjY 2 (zt − ηt gt ); end
4.1
Convex losses and the optimal dependence on µ
Theorem 4.1 (Hidden-Target OGD under UPPD). Assume Assumption 2.1 and UPPD (Assumption 3.3). Fix δ ∈ (0, 1) and set Bδ = ⌈µ−1 log(T /δ)⌉. Run HT-OGD (Algorithm 2) from z1 ∈ J1 12
√ √ with stepsize ηt = γD2 /(G2 t), where 0 < γ ≤ ρ/(2D2 Bδ ). Then, with probability at least 1 − δ, simultaneously for all u ∈ Y, RT (u) ≤ D2 G2
1
+ γ + 2γBδ
2γ
√
T.
√ In particular, choosing γ = ρ/(2D2 Bδ ) gives p D2 3ρ p e D2 G2 T /µ . RT (u) ≤ D2 G2 Bδ T = O + ρ 2D2 p Moreover, taking δ = 1/T and γ = ρ/(2D2 B1/T ) gives 3ρ q B1/T T + D2 G2 . ρ 2D2 √ The theorem balances two costs. OGD contributes O(D2 G2 T /γ) target regret, while the queue √ −1/2 reduction charges O(D2 G2 γBδ T ) for target movement. The clearing-scale choice γ = Θ(Bδ ) p e 2 G2 T /µ) rate. gives the optimal O(D p Theorem 4.2 (A T /µ lower bound under UPPD). There exists a universal constant c > 0 such that, for every µ ∈ (0, 1] and every T ≥ µ−1 , there is a two-product OIO instance with feasible set E[RT (u)] ≤ D2 G2
D
2
+
YL := {y ∈ R2+ | y1 + y2 = 1},
(11)
gradient bound G2 = 1, and UPPD parameter ρ = 1 for which every possibly randomized inventory algorithm satisfies s " T # T X X T E ℓt (yt ) − min ℓt (u) ≥ c . u∈YL µ t=1
t=1
The instance uses only the two linear losses ℓt (y) = y1 and ℓt (y) = y2 . Proof idea. The construction uses Bernoulli common-demand shocks. After a no-demand round, inventory feasibility and the equality constraint y1 + y2 = 1 pin the next order-up-to level to the previous one, so the learner plays the same action between any two shocks. This decomposes the period into random blocks of constant action. Each block then receives an independent random loss direction. The learner cannot exploit the direction within the block, while the best static comparator chooses the endpoint favored by the aggregate signed block length. Since p the squared block lengths are typically of order T /µ, this aggregate has an imbalance of order T /µ. This lower bound is different from the Lmax -based lower bound of Ichikawa et al. (2026). Their construction uses deterministic cycles with long zero-demand stretches, so it is not a UPPD lower bound with a positive µ. Our instance itself satisfies UPPD with parameter µ, and the randomness √ of the clearing times is exactly what produces the 1/ µ factor. Together, Theorems 4.1 and 4.2 characterize the minimax complexity of general-convex OIO under the UPPD condition.
4.2
Strongly convex losses
The same algorithm gives a fast rate when the losses have curvature. The argument follows the same reasoning as the convex case, with one structural difference: strongly convex losses require a different interface condition on the base learner. With strongly convex loss, the loss difference
13
P can be controlled not only by the linearized regret t ⟨gt , zt − u⟩ of Assumption 3.4(i) but also by a quadratic term ∥zt − u∥2 . We therefore replace this assumption with a curvature-augmented analog. The base learner satisfies the strongly convex linearized regret bound with curvature parameter α T if there exists a function Rsc T (u1:T ; α) such that for every comparator sequence u1:T ∈ Y , T X
⟨gt , zt − ut ⟩ − α4 ∥zt − ut ∥2
≤ Rsc T (u1:T ; α).
(12)
t=1
This generalizes Assumption 3.4(i) to the curvature-aware setting, and recovers the original assumption when no strong convexity is assumed, i.e. α = 0. The loss’s extra curvature allows the base learner to control a smaller quantity, and therefore attain lower overall regret bounds. This is formalized in the following generalization of the hidden target reduction in Theorem 3.5: Corollary 4.3 (Strongly convex hidden-target reduction). Under Assumption 2.1 and UPPD (Assumption 3.3), suppose each ℓt is α-strongly convex on Y with respect to ∥ · ∥. If the base learner produces targets (zt )Tt=1 ⊂ Y initialized at z1 ∈ J1 which satisfy Assumption 3.4(ii) and the strongly convex linearized regret bound (12), then with probability at least 1 − δ, for every comparator sequence u1:T ∈ Y T , αD RT (u1:T ) ≤ Rsc (u ; α) + G + Bδ ∆mv (13) ∗ 1:T T T . 2 This corollary provides an interface to use HT-OGD with a curvature-tuned stepsize to achieve polylogarithmic regret in the strongly convex setting. Theorem 4.4 (Strongly convex losses). Assume Assumption 2.1 and UPPD (Assumption 3.3). Take the projection norm to be Euclidean, ∥ · ∥ = ∥ · ∥2 . Suppose each ℓt is α-strongly convex on Y. Fix δ ∈ (0, 1) and define l 1 T m Bδ . Bδ := log , sδ := max 1, αρ/(2G ) 2 − 1 µ δ e Run HT-OGD (Algorithm 2) from z1 ∈ J1 with ηt = 2/(α(t + sδ )). Then, with probability at least 1 − δ, for all u ∈ Y, log(T /δ) log T RT (u) = O , µ where the hidden constant depends only on α, ρ, D2 , and G2 . √ Thus strong convexity converts the ordinary T target regret into polylogarithmic target regret, and the inventory layer contributes only O(Bδ log T ). This gives the first polylogarithmic-in-T adversarial-OIO guarantee for strongly convex losses on general convex capacity sets, resolving a major open direction raised by Hihat et al. (2023). The result also complements the logarithmic rates known under more stochastic inventory assumptions (Lyu et al., 2025).
4.3
Dynamic regret
For a comparator sequence u1:T , define PT,1 :=
T X
∥ut − ut−1 ∥1 ,
PT,2 :=
t=2
T X t=2
The Euclidean queue naturally controls PT,2 . 14
∥ut − ut−1 ∥2 .
(14)
Theorem 4.5 (Known path variation). Assume Assumption 2.1 and UPPD (Assumption 3.3). Fix δ ∈ (0, 1) and set Bδ := ⌈µ−1 log(T /δ)⌉. For a comparator sequence u1:T ∈ Y T with known path variation PT,2 , let s η ∗ :=
1 G2
D2 (D2 + 2PT,2 ) . (2Bδ + 1)T
If η ∗ ≤ ρ/(Bδ G2 ) and HT-OGD (Algorithm 2) is run with constant stepsize ηt ≡ η ∗ , then with probability at least 1 − δ, s ! q D2 (D2 + PT,2 )T e RT (u1:T ) ≤ G2 (2Bδ + 1)D2 (D2 + 2PT,2 )T = O G2 . µ Note that the best known dynamic regret guarantee for OIO was achieved by Ichikawa et al. (2026) using the same algorithm, with path variation measured by ℓ1 rather than ℓ2 , an additional n1/4 factor, and the restriction on a linear capacity constraint. Compared with their PT,1 -based √ guarantee, our PT,2 -based regret rate can be sharper by a factor as large as n for dense comparator movement. When PT,2 is unknown, we use the switching-aware SOGD base learner of Zhang et al. (2022), following the hidden-target architecture of Ichikawa et al. (2026). SOGD combines a grid of OGD experts with a smoothed meta-learner and satisfies a regret-plus-switching-cost guarantee. Appendix E.4.1 gives the base learner details and proves that its movement is slow enough for the queue reduction. For λ ≥ 1, define r 2PT,2 SOGD RT (u1:T ; λ) := 2G2 D2 (1 + λ)T 1 + D2 (15) r 2PT,2 + 120G2 D2 λT 1 + log T . D2 Theorem 4.6 (Unknown path variation). Assume Assumption 2.1 and UPPD (Assumption 3.3). Fix δ ∈ (0, 1) and set Bδ :=
l1
T m log , µ δ
l n 2D om 2 λδ := Bδ max 1, . ρ
Assume T ≥ max{32λδ log T, e}. Run the hidden-target projection layer with the SOGD base learner and switching parameter λδ . Then, with probability at least 1 − δ, for every comparator sequence u1:T ∈ Y T , RT (u1:T ) ≤ RSOGD (u1:T ; λδ ). (16) T Since λδ ≥ 1 and T ≥ e, this further implies the explicit bound s s T n D o T PT,2 2 RT (u1:T ) ≤ 500 G2 D2 1+ max 1, log log T . D2 ρ µ δ
4.4
(17)
Geometry-sensitive refinement via mirror descent
The hidden-target reduction in Theorem 3.5 is not intrinsically Euclidean. It asks only that the target sequence have OCO regret and controlled local movement in the same norm that measures the target-implementation gap. Online mirror descent (OMD) supplies exactly this interface whenever 15
its regularizer is strongly convex with respect to the chosen projection norm. Thus we can provide a single theorem specializing to OGD, p-norm OMD, entropic OMD, and other regularizer choices, with the regret constant adapting to the geometry of Y and to the corresponding dual gradient norm. Mirror descent has received much less attention than OGD in inventory learning. To our knowledge, Guo et al. (2026) first introduced OMD to stochastic multiproduct inventory learning, using cyclic updates under a linear warehouse constraint. Our reduction permits a broader use of OMD: it applies in the adversarial OIO model, allows arbitrary bounded convex capacity sets once a suitable regularizer is chosen, removes the need for cyclic updates, and gives guarantees for any strongly convex regularizer rather than only negative entropy. Let ∥ · ∥ be an admissible norm with dual ∥ · ∥∗ . Let R be a proper lower-semicontinuous convex regularizer on Y, and let D ⊆ Y denote the set on which R is finite and differentiable. We assume that R is σ-strongly convex with respect to ∥ · ∥ in the Bregman sense DR (u, v) ≥
σ ∥u − v∥2 2
for every u ∈ Y and v ∈ D,
and that the mirror-descent update below is initialized at z1 ∈ J1 ∩ D and returns points in D. The OMD base learner produces hidden targets as zt+1 = arg min ηt ⟨gt , z⟩ + DR (z, zt ) , (18) z∈Y
where DR (u, v) := R(u) − R(v) − ⟨∇R(v), u − v⟩ is the Bregman divergence of R when v ∈ D. Taking OMD as the base learner gives the HT-OMD algorithm in Algorithm 3. Algorithm 3: Hidden-Target OMD Input: Bounded Y ⊆ Rn+ , initial target z1 ∈ J1 ∩ D, constant stepsize η > 0 for t = 1, 2, . . . , T do Observe inventory state xt and define Jt = Y ∩ {y ∈ Rn | y ⪰ xt }; ∥·∥
Implement yt = ProjJt (zt ); Observe gt ∈ ∂ℓt (yt ) and the next state xt+1 ; Update zt+1 = arg minz∈Y η⟨gt , z⟩ + DR (z, zt ) ; end With an appropriate constant stepsize, the OMD base learner satisfies Assumption 3.4. Combining that verification with Theorem 3.5 and optimizing the stepsize yields the following regret guarantee. Theorem 4.7 (Hidden-Target OMD under UPPD). Assume Assumption 2.1 and UPPD (Assumption 3.3). Assume the OMD update returns points in D. Fix δ ∈ (0, 1), set Bδ := ⌈µ−1 log(T /δ)⌉, and write G∗ := supt ∥gt ∥∗ . Assume BR := supu∈Y DR (u, z1 ) < ∞ for an initialization z1 ∈ J1 ∩ D and G∗ > 0. Run HT-OMD (Algorithm 3) at the constant stepsize (s ) BR σ ρσ η = min , . (19) G2∗ (1/2 + Bδ )T Bδ G∗ Then with probability at least 1 − δ, for every u ∈ Y, RT (u) ≤
BR ηT G2∗ 1 + + B δ . 2 η σ
16
(20)
In particular, when T is sufficiently large such that the first term in the min operator in (19) is selected, then s ! r BR T (1/2 + Bδ ) B T R e G∗ . (21) RT (u) ≤ 2G∗ =O σ σµ Several familiar algorithms are recovered as instantiations of this constrained-stepsize bound (21). Specializations. With R(x) = 12 ∥x∥22 paired with an ℓ2 norm giving σ = 1 and BR = 12 D22 , the OMD update p collapses to projected OGD. Then its regret bound (21) reproduces Theorem 4.1’s rate e O(D2 G2 T /µ) with a constant stepsize rather than a decaying one. For p ∈ (1, 2], we may choose R(x) = 12 ∥x∥2p and an ℓp norm giving σ = p − 1 and BR ≤ Dp2 /2. Then one obtains the p-norm p e p Gp∗ T /((p − 1)µ)), where p∗ := p/(p − 1). OMD algorithm achieving the rate O(D Entropic OMD onPbounded Rn+ . A qualitatively different instantiation uses the negative-entropy regularizer R(x) := ni=1 xi log xi (Guo et al., 2026). Choosing the projection norm as ℓ1 and writing M := supx∈Y ∥x∥1 for the outer ℓ1 radius of Y, the regularizer R is (1/M )-strongly convex with respect to ℓ1 on the restricted positive domain {x ∈ Rn+ : ∥x∥1 ≤ M }, with the usual extended-value interpretation at the boundary. For the linear capacity constraint Y = {x : ∥x∥1 ≤ C}, we naturally have M = C, and the same analysis applies on any general convex set Y that contains the strictly positive initialization used below. Theorem 4.8 (Entropic OMD under UPPD). Assume Assumption 2.1 and UPPD (Assumption 3.3). Use ℓ1 as the projection norm and fix δ ∈ (0, 1). Write Bδ := ⌈µ−1 log(T /δ)⌉, M := supx∈Y ∥x∥1 , and G∞ := supt ∥gt ∥∞ . Assume M, G∞ > 0 and that the uniform vector z1 := (M/n,P. . . , M/n) ∈ Y ∩ Rn++ . Run HT-OMD (Algorithm 3) with negative-entropy regularizer R(x) := ni=1 xi log xi from the initialization z1 (the regularizer keeps all iterates in D with D = Y ∩ Rn++ , as verified in Appendix E.5.2). Choose ( ) √ 1 + log n ρ p . (22) η = min , G∞ (1/2 + Bδ )T M Bδ G∞ Then with probability at least 1 − δ, for every u ∈ Y, RT (u) ≤
M (1 + log n) + ηM G2∞ T 21 + Bδ . η
(23)
In particular, when T is sufficiently large such that the first term in the min operator in (22) is selected, then s ! p T log n e M G∞ RT (u) ≤ 2M G∞ T (1 + log n)(1/2 + Bδ ) = O . µ p p e BR /σ G∗ T /µ should When does OMD outperform OGD? The general HT-OMD rate O be p read as a geometry-sensitive refinement of the ℓ2 -based HT-OGD bound in Theorem 4.1. The T /µ dependence is the same p for all regularizers; the algorithmic constant is the product of an effective Bregman diameter BR /σ and the √ dual gradient bound G∗ . For ℓ2 -OGD this product √ is D2 G2 / 2, while for entropic OMD it is M 1 + log n G∞ . The reason that entropic OMD can 17
×106
2.25
HT-OGD MaxCOSD DDM
108
2.5
1.75
2.0 Regret
Regret
HT-OGD
2.00
1.50
107
1.5
1.25 1.00
1.0
106
×105
0.75 0.5
HT-OGD MaxCOSD DDM 10 5
10 4
0.50 0.25
0.0 10 3
10 2
10 1
100
(a) Learning-rate sweep.
101
0
1000
2000
T
3000
4000
(b) Regret over time.
5000
0
1000
2000
T
3000
4000
5000
(c) HT-OGD only.
Figure 3: Static regret on the linear warehouse capacity YC = {y ∈ Rn+ : ∥y∥1 ≤ C} (Setting 3 of Hihat et al. (2023)). Panel (a) reports regret at T = 5 × 103 over logarithmically spaced learning-rate multipliers. Panel (b) uses the best multiplier for each algorithm and plots regret over time. Panel (c) isolates HT-OGD on its own axes since its low-magnitude trajectory can be hard to read in the previous panel. √ improve over ℓ2 -OGD is dual-norm sensitivity: since G∞ ≤ G2 ≤ n G∞ , replacing an ℓ2 gradient √ bound by an ℓ∞ bound can save as much as n when gradients are spread across many coordinates. For the linear warehouse constraint Y = {x ∈ Rn+ : ∥x∥1 ≤ C}, the effective√Bregman diameters √ are comparable: M = C, D2 = C 2, and entropic OMD pays an additional log n KL-diameter factor — this overhead is small relative to the possible dual-norm gain. If gradients are coordinatep √ dense, G2 ≈ n G∞ , entropic OMD improves the ℓ2 -OGD rate by a factor on the order of n/ log n. If gradients are concentrated on a few coordinates, G∞ ≈ G2 , ℓ2 -OGD is sharper by at most the √ mild log n factor in this geometry. Hence, entropic OMD can be viewed as more suitable than ℓ2 -OGD for the linear warehouse constraint, improving on Ichikawa et al. (2026), since negative entropy is the natural regularizer on the simplex. The improvement extends the insights of Guo et al. (2026) to the adversarial OIO setting. For general convex capacity sets, the same principle applies with the appropriate regularizer: HT-OMD lets the bound follow the geometry of Y and the dual norm in which gradients are small, rather than forcing every instance into Euclidean constants.
5
Experiments
The experiments compare the three algorithmic principles available in the literature. MaxCOSD waits for a new proposed target to become feasible before committing to it (Hihat et al., 2023). DDM is a projected base-stock method designed for stochastic multiproduct systems with a linear warehouse constraint that only updates its target when unbiased gradient estimates become available (Shi et al., 2016). HT-OGD uses the simple every-round hidden-target projection principle. Since DDM was designed for a single linear warehouse constraint, most experiments use the common testing environment YC = {y ∈ Rn+ : ∥y∥1 ≤ C} with lost-sales dynamics and newsvendor loss. However, we also test with non-linear capacity constraints to demonstrate the generalizability of our results. The closest hidden-target OIO experiments in Ichikawa et al. (2026) are single-item, whereas our algorithmic comparisons are multiproduct. In experiments where we compare different stepsizes for HT-OGD suggested by our theoretical results in Section 4, we use a single product setting to establish a baseline for these new experimental settings. In this case, the linear feasible set YC reduces to an interval and we choose sufficiently large C to be non-binding. All experiments show 18
1.4 ×10
HT-OGD MaxCOSD DDM
108
1.2
×104
7
HT-OGD MaxCOSD DDM
10
1.0 Regret
Regret
107
106
0.8
8
0.6
6
0.4
4
0.2 105
0.0 10 4
10 3
10 2
10 1
100
101
(a) Learning-rate sweep.
102
HT-OGD
12
0
1
2
T
3
4
(b) Regret over time.
5 ×104
2
0
1
2
T
3
4
5 ×104
(c) HT-OGD only.
Figure 4: Static regret on the same setting as Figure 3, but with a curved capacity set Y = {y ∈ Rn+ : ∥y∥2 ≤ R}. Panels (a)–(c) follow the same convention as in Figure 3. an error envelope of ±2 standard error, though this is sufficiently small in some plots to be difficult to observe. Unless stated otherwise, hi = 1 and pi = 200 in newsvendor loss. We tune a scalar learning-rate multiplier γ for each method, compute static comparators offline by optimizing over the realized demand sequence, and plot ±2 standard-error envelopes over repeated runs. Appendix A gives the full parameter choices. Figure 3 reproduces Setting 3 of Hihat et al. (2023): n = 100 products, independent Poisson demands with rates drawn from Uniform[1, 2], and capacity C = 175. HT-OGD attains lower regret at its best tuning and is less sensitive to the learning-rate multiplier. In the time-series panel, MaxCOSD accumulates regret much faster on the plotted horizon, DDM behaves sublinearly, and HT-OGD remains the most stable. We additionally isolate the time-series regret plot for HT-OGD to see that its regret is still sublinear rather than flat, but at a significantly smaller scale than the algorithms. This stochastic instance is not meant to be a worst-case construction, it is a common benchmark showing that the hidden-target projection principle also behaves competitively in the capacitated multiproduct regime where cycle methods were originally tested. Figure 4 repeats the experiment on the curved capacity set Y = {y ∈ Rn+ : ∥y∥2 ≤ R}, a positive ℓ2 ball. While MaxCOSD and HT-OGD both have guarantees in this setting, the productwise sell-out arguments underlying DDM (Shi et al., 2016) require the linear structure of a warehouse polytope and so DDM has no formal guarantees in this setting. Despite this, we find the same pattern as in the linear capacity setting: the performance of each algorithm ranks in the order of HT-OGD, DDM, then MaxCOSD. This demonstrates HT-OGD’s efficacy is not limited to linear capacity sets and validates our theoretical findings. Figure 5 replaces the synthetic Poisson stream with demand traces from the M5 forecasting competition (Makridakis et al., 2022), a retail benchmark containing real demand traces from 10 Walmart stores with n = 3049 items over a period of T = 1913 days while using a linear capacity constraint. This probes behavior under non-stationary, non-i.i.d. demand and demonstrates the same story as the previous figures. Even without i.i.d. demand, HT-OGD achieves both improved theoretical guarantees and empirical performance. The remaining experiments probe different aspects of our theoretical results. Figure 6a uses a power-law demand experiment to test explicit dimension dependence while keeping aggregate demand and loss scale comparable. While regret may still grow based on other problem parameters like D and G, the plot demonstrates the dimensional-scaling advantage our analysis predicts. The strongly convex loss experiment in Figure 6b distinguishes the performance of HT-OGD under the 19
8 ×10
×108
109
HT-OGD MaxCOSD DDM
10
Regret
Regret
HT-OGD
7 6
8
5
6
4 3
4
108
7
2 2
HT-OGD MaxCOSD DDM 10 5
10 4
1 0
0
10 3
10 2
10 1
100
101
0
(a) Learning-rate sweep.
250
500
750
1000 T
1250
1500
1750
0
2000
250
(b) Regret over time.
500
750
1000 T
1250
1500
1750
2000
(c) HT-OGD only.
Figure 5: Static regret on demand traces from the M5 forecasting competition, a real-world retail benchmark with n = 3049 items. The dataset contains realizations from 10 stores which are treated as batches, resulting in larger error envelopes than other experiments. Panels (a)–(c) follow the convention of Figure 3. ×105
t t
1/ t 1/t
t
2.5
40
2.5
1/ t PT, 2/T
2.0 Regret
Regret
1.5
20 10
0.5 0
500
1000
1500 N
2000
2500
(a) Dimension scaling.
3000
0
1.5 1.0
1.0
0.0
t
30
2.0 Regret
×104
50
HT-OGD MaxCOSD DDM
3.0
0.5 0.0
0
2
4
T
6
8
(b) Strong convexity.
10 ×104
0
2
4
T
6
8
10 ×104
(c) Dynamic regret.
Figure 6: Additional experiments. (a) Static regret as the number of products grows under power-law √ demand dt,i ∝ i−1.1 . (b) Regret performance for quadratic strongly convex loss, comparing ηt ∝ 1/ t √ and ηt ∝ 1/t. (c) Dynamic regret for blockwise-constant demand with PT,2 = O( T ), comparing the static schedule with the known-variation constant stepsize. √ 1/t schedule from the general convex 1/ t schedule. The separation is consistent with our predicted polylogarithmic and sublinear regret rates for each corresponding stepsize. Lastly, the dynamic regret experiment in Figure 6c shows the advantage of using √ a known-variation constant stepsize for HT-OGD when the comparator p moves with PT,2 = O( T ). The plot shows that this adapted stepsize is consistent with the O( PT,2 T ) = O(T 3/4 ) dynamic regret predicted by Theorem 4.5.
6
Conclusion
This paper identifies the right geometric state variable for general-convex OIO: the norm-aligned distance from the hidden target to the implementable set. With norm alignment, this distance evolves as a queue with target movement as arrival and common demand as service, reducing general-convex OIO to OCO with switching cost. Under our analysis, the state-dependent feasibility cost which forced prior work into product-by-product accounting under linear capacity or into adaptive cycle control becomes an ordinary switching-cost penalty on the base learner’s target movement. Concretely, applying the reduction with a projected OGD base learner yields the optimal
20
p e T /µ) static regret on arbitrary bounded convex capacity sets, matched by a new lower bound O( under UPPD. The same reduction with a constant stepsize OGD base learner gives polylogarithmic regret under strongly convex losses, resolving an open direction raised by Hihat et al. (2023). With an SOGD base learner, it gives Euclidean-path-variation dynamic regret on general convex sets, sharpening Ichikawa et al. (2026)’s ℓ1 -path-variation bound. All three guarantees remove the explicit n1/4 dimension factor that appeared in prior ℓ1 -based analyses. Beyond the regret bounds themselves, the norm alignment principle decouples the inventory analysis from the learning algorithm. Any base learner producing hidden targets with controlled movement in the aligned norm plugs into the same reduction, which we demonstrate concretely with OGD, SOGD, and mirror descent. The inventory layer never inspects how targets are generated, and the base learner never reasons about sell-out events or feasible sets. We hope this modular template proves useful for other online problems where state-dependent feasibility constraints have previously demanded problem-specific treatments. This work suggests several directions for future research. The most immediate is to move beyond UPPD. In large-scale systems with thousands of products, the probability that the common demand exceeds a positive threshold becomes increasingly small for even simple demand sequences. A local clearing condition, requiring demand only where the implemented action exceeds the hidden target, would better match sparse demand while preserving the separation between learning and feasibility. Another direction is to develop adaptive guarantees that do not require advance knowledge of problem-dependent parameters such as µ or ρ. Our instantiations use these parameters in the choice of stepsize or clearing window that is passed to the base learner. The modular queue analysis is naturally compatible with parameter-free OCO methods (Orabona, 2019), and recovering the same rates without offline tuning would make the framework more powerful.
References Matias Alvo, Daniel Russo, Yash Kanoria, and Minuk Lee. Deep reinforcement learning for inventory networks: Toward reliable policy optimization. arXiv preprint arXiv:2306.11246, 2023. Version 3, 2025. Kenneth J Arrow, Theodore Harris, and Jacob Marschak. Optimal inventory policy. Econometrica: Journal of the Econometric Society, pages 250–272, 1951. Kenneth J. Arrow, Samuel Karlin, and Herbert E. Scarf, editors. Studies in the Mathematical Theory of Inventory and Production. Stanford University Press, 1958. Richard Bellman. Review of Studies in the Mathematical Theory of Inventory and Production, by K. Arrow, S. Karlin, and H. Scarf. Management Science, 5(1):139–141, 1958. Richard Bellman, Irving Glicksberg, and Oliver Gross. On the optimal inventory equation. Management Science, 2(1):83–104, 1955. Michael Bloem, Song Zhou, Kai He, Zhunyou Hua, and Yan Xia. Simulation-based online retailer supply chain inbound node arrival capacity control. In Proceedings of the 2025 Winter Simulation Conference, pages 438–449, 2025. Xiuli Chao, Boxiao Chen, and Huanan Zhang. Online learning in inventory and pricing optimization. In Research Handbook on Inventory Management, pages 333–378. Edward Elgar Publishing, 2023.
21
Weidong Chen, Cong Shi, and Izak Duenyas. Optimal learning algorithms for stochastic inventory systems with random capacities. Production and Operations Management, 29(7):1624–1649, 2020. Jingying Ding, Woonghee Tim Huh, and Ying Rong. Feature-based inventory control with censored demand. Manufacturing & Service Operations Management, 26(3):1157–1172, 2024. Aryeh Dvoretzky, J Kiefer, and Jacob Wolfowitz. The inventory problem: Ii. case of unknown distributions of demand. Econometrica: Journal of the Econometric Society, pages 450–466, 1952a. Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. The inventory problem: I. case of known distributions of demand. Econometrica: Journal of the Econometric Society, pages 187–222, 1952b. Sichen Guo, Cong Shi, Chaolin Yang, and Christos Zacharias. An online mirror descent learning algorithm for multiproduct inventory systems. Operations Research, 2026. Articles in Advance. Eric C. Hall and Rebecca M. Willett. Dynamical models and tracking regret in online convex programming. In Proceedings of the 30th International Conference on Machine Learning, pages 579–587, 2013. Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 (3–4):157–325, 2016. Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2–3):169–192, 2007. Massil Hihat, Stéphane Gaïffas, Guillaume Garrigos, and Simon Bussy. Online inventory problems: Beyond the i.i.d. setting with online convex optimization. In Advances in Neural Information Processing Systems, volume 36, pages 20421–20440, 2023. Woonghee Tim Huh and Paat Rusmevichientong. A nonparametric asymptotic analysis of inventory planning with censored demand. Mathematics of Operations Research, 34(1):103–123, 2009. Koji Ichikawa, Kei Takemura, and Tatsuya Matsuoka. Online inventory optimization in non-stationary environment. In The Fourteenth International Conference on Learning Representations, 2026. ICLR 2026 poster. Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Dynamic regret analysis of strongly convex and smooth problems. In Proceedings of the 28th Annual Conference on Learning Theory, pages 783–784, 2015. Jiameng Lyu, Jinxing Xie, Shilin Yuan, and Yuan Zhou. A minibatch stochastic gradient descentbased learning metapolicy for inventory systems with myopic optimal policy. Management Science, 71(7):5572–5588, 2025. Dhruv Madeka, Kari Torkkola, Carson Eisenach, Anna Luo, Dean P. Foster, and Sham M. Kakade. Deep inventory management. arXiv preprint arXiv:2210.03137, 2022. Alvaro Maggiar, Sohrab Andaz, Akhil Bagaria, Carson Eisenach, Dean Foster, Omer Gottesman, and Dominique Perrault-Joncas. Structure-informed deep reinforcement learning for inventory management. arXiv preprint arXiv:2507.22040, 2025. Spyros Makridakis, Evangelos Spiliotis, and Vassilios Assimakopoulos. The M5 competition: Background, organization, and implementation. International Journal of Forecasting, 38(4):1325–1336, 2022. 22
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.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. Technical note—nonparametric data-driven algorithms for multiproduct inventory systems with censored demand. Operations Research, 64(2):362–370, 2016. Lawrence V. Snyder and Zuo-Jun Max Shen. Stochastic inventory models: Periodic review. In Fundamentals of Supply Chain Theory, pages 87–154. John Wiley & Sons, 2019. Cong Yang and Woonghee Tim Huh. A nonparametric learning algorithm for a stochastic multiechelon inventory problem. Production and Operations Management, 33(3):701–720, 2024. Hao Yuan, Qi Luo, and Cong Shi. Marrying stochastic gradient descent with bandits: Learning algorithms for inventory systems with fixed costs. Management Science, 67(10):6089–6115, 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. Operations Research, 66(5):1276–1286, 2018. Lijun Zhang, Wei Jiang, Jinfeng Yi, and Tianbao Yang. Smoothed online convex optimization based on discounted-normal-predictor. In Advances in Neural Information Processing Systems, volume 35, pages 4928–4942, 2022. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928–936, 2003.
23
Appendix Contents A Detailed experiment setup
25
B Why productwise dynamics fail on general convex sets
26
C Discussion on UPPD and Lmax
29
D Omitted proofs from Section 2 and Section 3 30 D.1 Deterministic clearing and pathwise transfer . . . . . . . . . . . . . . . . . . . . . . . 30 D.2 Proof of Lemma 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 D.3 Proof of Proposition 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 D.4 Proof of Theorem D.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 D.5 Proof of Lemma D.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 D.6 Proof of Theorem 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 E Omitted proofs from Section 4 35 E.1 General convex losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 E.2 A matching lower bound under UPPD . . . . . . . . . . . . . . . . . . . . . . . . . . 37 E.3 Strongly convex losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 E.4 Dynamic regret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 E.5 Mirror descent base learners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
24
A
Detailed experiment setup
Unless stated otherwise, experiments use the linear warehouse set YC = {y ∈ Rn+ : ∥y∥1 ≤ C} so that HT-OGD, MaxCOSD, and DDM can be compared on the same feasible region. The L2 capacity experiment (Figure 4) replaces YC with the positive ℓ2 ball {y ∈ Rn+ : ∥y∥2 ≤ R}, on which DDM has no formal guarantees. The inventory dynamics are lost sales, xt+1 = (yt − dt )+ , and the basic loss is the newsvendor loss (3). A scalar multiplier γ rescales the nominal √ learning rate in each method. For the convex static experiments, HT-OGD and DDM use ηt ∝ 1/ t, while MaxCOSD uses the adaptive stepsize prescribed by Hihat et al. (2023). Static regret is computed against an offline fixed comparator obtained by projected OGD on the realized demand sequence until convergence. When applicable, tests are rerun to reduce variance from stochastic demand generation and we display ±2 standard error bars in the plots. All experimental results were computed on an Apple Mac Studio using a M4 Max chip with 48GB of memory. Each experiment finished execution in under 2 hours. Warehouse capacity (ℓ1 ) setting. For Figure 3, we use Setting 3 of Hihat et al. (2023): n = 100, independent demands dt,i ∼ Poisson(λi ), independent rates λi ∼ Uniform[1, 2], and capacity C = 175. While Hihat et al. (2023) did not report the value of C, we chose the value so that most demand realizations (≈ 97.5%) would fall within the capacity set. The learning-rate sweep evaluates at horizon T = 5 × 103 and logarithmically spaced multipliers γ ∈ [10−5 , 10] evaluating over 200 reruns. The time-series panel plots the regret up to the same horizon, using the best multiplier for each algorithm from the sweep. L2 capacity setting. The environment in Figure 4 uses the same number of products, horizon, and demand generation as in the warehouse capacity setting, but replaces the linear capacity set with a positive ℓ2 ball Y = {y ∈ Rn+ : ∥y∥2 ≤ R} with R = 22.5, also yielding most demand realizations falling in the capacity set as in the linear warehouse experiment. The learning-rate sweep evaluates over logarithmically spaced multipliers γ ∈ [10−4 , 102 ] across 20 reruns. The time-series panel uses the best multiplier for each algorithm from the sweep. M5 forecasting traces. For Figure 5, the demand traces are taken from the M5 forecasting competition dataset (Makridakis et al., 2022). This dataset consists of n = 3049 products over a period of T = 1913 days from 10 different Walmart stores in the states of California, Texas, and Wisconsin. While the dataset contains contextual information such as the product category, price, and day of the week, we only use the demand realizations in our experiments. We use a linear warehouse capacity set with capacity C = 6600, which causes most demand realizations to fall within the capacity set as in the previous experiments. We treat the 10 different stores as independent demand traces, meaning that the results are averaged over the simulations from each store. The learning-rate sweep uses logarithmically spaced multipliers γ ∈ [10−5 , 10]. Dimension scaling. Demands are computed as dt,i = i−α ut,i with α = 1.1 and independent ut,i ∼ Uniform[0, 1]. Since α > 1, the total demand magnitude remains comparable as n grows. This experiment is a stress test for algorithmic dimension scaling rather than a direct verification of UPPD, because common clearing can become rare in sparse high-dimensional systems. At all dimensions, we use a capacity of C = 2.75. The plot evaluates at logarithmically spaced number of products n ∈ [100, 3000] with 10 reruns.
25
Strong convexity. For the strongly convex experiment, we use a single-product quadratic loss ℓt (y) = 12 (y − dt )2 with i.i.d. Poisson(λ) demand with λ = 1.5. The capacity C = 20 is chosen to be sufficiently large to be non-binding. We compare HT-OGD with the general convex schedule √ ηt ∝ 1/ t and the strongly convex schedule ηt ∝ 1/t, tuning the scalar multiplier on a shorter horizon of T = 104 before evaluating at the plotted horizon up to T = 105 over 20 reruns. Dynamic regret. In the dynamic-regret √ panel, the single-product demand sequence is a sequence of constant blocks, with block length ⌈ T ⌉ and demand values cycling through the list {2, 3, 4}. Under lost-sales, the comparator ut = d√ t is optimal since it is feasible and has zero newsvendor loss, √ yielding a path variation of PT,2 = O( T ). We compare to the static-regret schedule ηt ∝ 1/ t with the constant stepsize suggested by Theorem 4.5. Note that since the constant stepsize depends on T , we rerun the algorithm at many different values of T rather than plotting the cumulative regret from one run with large T . The underage cost is set to p = 2 to avoid a degenerate myopic ordering rule. Since this is a deterministic demand sequence and the algorithm is also deterministic, there is no variance in the results so we do not display error bars.
B
Why productwise dynamics fail on general convex sets
Prior hidden-target analyses in inventory learning track an ℓ1 target-implementation gap, which differs from the norm-aligned one presented in this paper: both Shi et al. (2016); Ichikawa et al. (2026) focus on ∥yt − zt ∥1 under Euclidean projection, rather than the norm-aligned ∥yt − zt ∥2 (see Section 3). Shi et al. (2016) derived a queue recursion on ∥yt − zt ∥1 by a coordinatewise update on (i) (i) |yt − zt | (their Lemmas 4–6), and Ichikawa et al. (2026) conducted a per-product cycle analysis (their Lemmas 5–6) whose telescoping bound critically depends on the linear warehouse constraint P (i) ≤ D. Both strategies decompose the gap by coordinate and control each coordinate’s i zt evolution locally. This appendix explains why the queue recursion in general-convex OIO must be geometric rather than productwise. In Section 3, the regret decomposition charges the target-implementation gap ∆gap T =
qt := ∥zt − yt ∥,
T X
qt .
t=1
Thus a queue proof must show that common demand serves this distance. A productwise sell-out proof has a different native state variable. For a target z ∈ Y and inventory state x, define the coordinatewise feasibility violation ∥(x − z)+ ∥1 . This is the quantity on which the inventory dynamics acts directly: demand reduces the coordinates where the current state exceeds the target, while target movement can create new violation. Prior hidden-target analyses (Shi et al., 2016; Ichikawa et al., 2026) under a single linear warehouse constraint effectively bridge these two quantities by productwise accounting. They aim to control the ℓ1 implementation gap (1) qt := ∥zt − yt ∥1 , + but the local sell-out dynamics controls P productwise feasibility violations ∥(xt − zt ) ∥1 . For a linear warehouse set, the budget identity i yi ≤ D supplies a conservation law: mass added to some coordinates must be balanced by mass removed from others. This conservation law lets productwise bounds telescope. On a curved convex capacity set, there is no such identity.
26
The obstruction can be stated as the failure of the bridge one would need to turn a productwise queue into a regret bound. Write ∥·∥
J(x) := Y ∩ {y ′ ∈ Rn | y ′ ⪰ x},
y = ProjJ(x) (z).
A productwise proof would need to compare the regret-relevant gap ∥y − z∥1 with the productwise obstruction ∥(x − z)+ ∥1 , either coordinate by coordinate or after summing over products. The next proposition shows that neither comparison holds uniformly. Proposition B.1 (No productwise bridge to the implementation gap). There is no finite constant C with the following property: for every closed, convex, and bounded set Y ⊆ Rn+ , every z ∈ Y, every x ∈ Rn+ for which J(x) is nonempty, and every nearest point ∥·∥
y = ProjJ(x) (z), one has the coordinatewise bound |yi − zi | ≤ C (xi − zi )+
for all i ∈ [n].
Moreover, there is no finite constant C for which the aggregate bound ∥y − z∥1 ≤ C ∥(x − z)+ ∥1 holds uniformly over the same class of instances. Proof. Take Y = {(u, v) ∈ R2+ | u + v 2 ≤ 1}. This set is closed, bounded, and convex. For δ ∈ (0, 1], set z (δ) = (1 − δ 2 , δ),
x(δ) = (1, 0).
The set J(x(δ) ) contains only (1, 0), so the projection is y = (1, 0) in every norm. The coordinatewise claim fails in the second coordinate: (δ)
|y2 − z2 | = δ,
(δ)
(δ)
(x2 − z2 )+ = 0.
Thus no finite C can make δ ≤ C · 0 hold uniformly. The aggregate claim also fails, since ∥y − z (δ) ∥1 = δ + δ 2 , The ratio is
∥(x(δ) − z (δ) )+ ∥1 = δ 2 .
∥y − z (δ) ∥1 = 1 + δ −1 , ∥(x(δ) − z (δ) )+ ∥1
which diverges as δ ↓ 0. The consequence is not merely a loss of constants. The productwise queue ∥(x − z)+ ∥1 can be of order δ 2 while the target-implementation gap charged in regret is of order δ. A proof that only follows the coordinatewise obstruction therefore undercounts the implementation error. In the example, the inventory lower bound asks for only a δ 2 increase in the first coordinate, but the curved
27
boundary u + v 2 = 1 forces a displacement of size δ in the second coordinate. The large part of the projection gap occurs in a coordinate with no positive-part violation at all. This is the precise point at which productwise reasoning stops. Common demand can serve the feasibility violation (x − z)+ , but regret has already charged the projection distance ∥z − y∥1 . Without a geometry-free comparison between these two quantities, a recursion for the productwise obstruction does not imply a recursion for the target-implementation gap: control of ∥(xt − zt )+ ∥1
̸⇒
control of ∥zt − yt ∥1 .
Thus one cannot conclude a bound of the form T X
∥zt − yt ∥1 ≲ B
t=1
T −1 X
∥zt+1 − zt ∥1
t=1
from productwise sell-out accounting on general convex capacity sets. The geometric queue recursion in Proposition 3.1 avoids this failed bridge. It does not try to compare the implementation gap with ∥(xt − zt )+ ∥1 . Instead, after observing demand, it constructs a point wt ∈ Jt+1 directly. If zt+1 lies within distance dmin of the implemented point yt , the short t move lemma makes zt+1 feasible and the queue clears. Otherwise, convexity lets us move from yt toward zt+1 by distance dmin and obtain a feasible witness wt ∈ Jt+1 . t The decisive step is then the aligned projection certificate: qt+1 = dist∥·∥ (zt+1 , Jt+1 ) ≤ ∥zt+1 − wt ∥. This certificate is available only in the norm used to define the projection. Once it is available, the triangle inequality gives + qt+1 ≤ qt + ∥zt+1 − zt ∥ − dmin . t Thus common demand becomes service for the regret-relevant queue itself. The proof has transformed coordinatewise demand into geometric queue service without any productwise conservation identity. This also clarifies why a norm-conversion workaround does not repair the productwise argument. Suppose the implementation is the Euclidean projection ∥·∥
2 (zt+1 ), yt+1 = ProjJt+1
but we try to analyze the ℓ1 queue (1)
qt+1 := ∥zt+1 − yt+1 ∥1 . After constructing the witness wt ∈ Jt+1 , the geometric proof would need (1)
qt+1 ≤ ∥zt+1 − wt ∥1 . Euclidean projection does not certify this inequality. It certifies only ∥zt+1 − yt+1 ∥2 ≤ ∥zt+1 − wt ∥2 . Converting norms gives at best (1)
qt+1 ≤
√
n ∥zt+1 − yt+1 ∥2 ≤
√ √ n ∥zt+1 − wt ∥2 ≤ n ∥zt+1 − wt ∥1 .
28
√ The factor n now appears inside the recursion formula, not at the end of the argument. Between √ clearing shocks, repeated substitution weights earlier target movements by powers of n, causing exponential growth. Therefore the window condition t+B−1 X
∥zr+1 − zr ∥ ≤ ρ
r=t
no longer guarantees that one common-demand shock of size ρ clears the queue. The key insight from the discussion is that, for general convex capacity sets, norm alignment is the mechanism that converts common demand into service for the queue to which regret is actually charged.
C
Discussion on UPPD and Lmax
How to read the parameter µ. UPPD is best viewed as a common-clearing primitive. One practical model is a store-wide traffic or promotion shock: on ordinary days, demand may be sparse and product-specific, but with conditional probability µ a system-wide event brings at least ρ demand to every product class. In the expected clearing-window length is of order 1/µ. p √ such a model Improving a regret bound from T /µ to T /µ is therefore the difference between paying linearly for the waiting time and paying only its square root between common shocks. The improvement is most meaningful when common clearing is infrequent but not impossible; if µ is exponentially small in the number of products, all UPPD-based guarantees become conservative. This is why the main text states both sides: the µ−1/2 exponent is optimal under UPPD, while replacing UPPD by a more local clearing condition is the next modeling step. Ichikawa et al. (2026) use the maximum sell-out window Lmax as their demand primitive. Under 2 ). The elementary argument e UPPD, their stated high-probability estimate gives Lmax = O(1/µ e below tightens this relation to O(1/µ) for the linear-capacity model. This observation is useful for comparison; the main theorems avoid Lmax altogether and work directly on arbitrary convex capacity sets. Proposition C.1. Consider the linear-capacity model Ylin := y ∈ Rn+ | ∥y∥1 ≤ C where C > 0 is the capacity parameter. Suppose Assumption 3.3 holds with parameters (µ, ρ), and set m := ⌈C/ρ⌉. Then for every item i, every start time t with t + L − 1 ≤ T , and every L ∈ N, ! t+L−1 X µL i P ds < C ≤ exp m − (24) 2 s=t Consequently, if & Lδ :=
nT 2 l C m + log µ ρ δ
'
then with probability at least 1 − δ, every item receives at least C units of demand over every length-Lδ window contained in [T ]. Equivalently, in the high-probability sense of Remark 3 of Ichikawa et al. (2026), we have Lmax ≤ Lδ . Proof. Fix a product i and timestep t, and define the indicator Xs := 1{dmin ≥ ρ}, s
for all s = t, . . . , t + L − 1.
29
P P P dis < C implies t+L−1 Xs ≤ m − 1 because s Xs takes Since dis ≥ dmin ≥ ρXs , the event t+L−1 s s=t s=t integer values. For any θ > 0, a Chernoff bound gives ! " # t+L−1 t+L−1 X X P Xs ≤ m − 1 ≤ eθm E exp −θ Xs s=t
s=t
Write ps := P(dmin ≥ ρ | Fs−1 ). Assumption 3.3 gives ps ≥ µ almost surely, and therefore s E e−θXs | Fs−1 = 1 − ps + ps e−θ ≤ 1 − µ + µe−θ Iterating conditional expectations and using the tower property inductively yields " # t+L−1 X E exp −θ Xs ≤ (1 − µ + µe−θ )L s=t
Taking θ = log 2 gives P
t+L−1 X
! dis < C
≤P
t+L−1 X
s=t
! Xs ≤ m − 1
s=t
µL ≤ 2 (1 − µ/2) ≤ exp m − 2 m
L
where the last inequality used 2m < em and 1 − x ≤ e−x with x = µ/2, and thus proves (24). For L = Lδ , the right-hand side of (24) is at most δ/(nT ). A union bound over at most nT pairs of products and timesteps (i, t) gives the claim. Thus with probability at least 1 − δ, each product receives demand exceeding the warehouse capacity in at most Lδ rounds, so we must have Lmax ≤ Lδ .
D
Omitted proofs from Section 2 and Section 3
D.1
Deterministic clearing and pathwise transfer
The main text works directly with UPPD. The proofs pass through the following deterministic clearing event. Assumption D.1 (Windowed clearing). There exist B ∈ N and ρ > 0 such that every interval of B consecutive rounds contains a time s with dmin ≥ ρ. s Theorem D.2 (Pathwise implementation bound). Suppose q1 = 0 and Assumption D.1 holds. If B < T , assume that for every t ∈ [T − B], t+B−1 X
∥zr+1 − zr ∥ ≤ ρ.
(25)
r=t
(If B ≥ T , (25) is not needed.) Then ∆gap T =
T X t=1
qt ≤ B
T −1 X
∥zt+1 − zt ∥ = B∆mv T .
(26)
t=1
Theorem D.3 (OIO regret as target regret plus movement). Suppose q1 = 0, Assumption D.1 holds, and if B < T , (25) is satisfied. Then for every comparator sequence u1:T ∈ Y T , mv RT (u1:T ) ≤ ∆base T (u1:T ) + G∗ B∆T .
30
(27)
Lemma D.4 (Probabilistic clearing under UPPD). Under Assumption 3.3, for every B ∈ [T ], P ∃t ∈ [T − B + 1] such that dmin < ρ for all s = t, . . . , t + B − 1 ≤ T e−µB . s In particular, if Bδ := ⌈µ−1 log(T /δ)⌉ and Bδ < T , then with probability at least 1−δ, Assumption D.1 holds with B = Bδ . When Bδ ≥ T , the reduction uses the deterministic loose bound instead.
D.2
Proof of Lemma 2.2
Proof. For any t ∈ [T ], convexity of ℓt at yt and the subgradient gt ∈ ∂ℓt (yt ) gives ℓt (yt ) − ℓt (ut ) ≤ ⟨gt , yt − ut ⟩ = ⟨gt , zt − ut ⟩ + ⟨gt , yt − zt ⟩. Since ∥gt ∥∗ ≤ G∗ by Assumption 2.1 and using a generalized version of Hölder’s inequality, we have ⟨gt , yt − zt ⟩ ≤ G∗ ∥yt − zt ∥. Summing over t proves (5).
D.3
Proof of Proposition 3.1
The proof of the target-implementation gap recursion (Proposition 3.1) relies on the geometric Lemma 3.2 relating the distance between order levels and the inventory dynamics constraint (2). It also relies on the following projection certificate, which is the precise place where norm alignment enters the queue recursion. We first present these two elementary ingredients and then proceed to the proposition. Lemma D.5 (Aligned projection certificate). Fix a norm ∥ · ∥ and a nonempty closed set J ⊆ Rn . If y ∈ arg min ∥z − u∥, u∈J ∥·∥
equivalently y = ProjJ (z) for one choice of nearest point, then for every w ∈ J, ∥z − y∥ = dist∥·∥ (z, J) ≤ ∥z − w∥.
(28)
The statement is norm-specific: a projection in a different norm certifies distance only in that different norm. Proof. The inequality is the defining optimality property of a nearest point in the norm ∥ · ∥. If y minimizes ∥z − u∥ over u ∈ J, then no feasible witness w ∈ J can be closer to z in the same norm. Proof of Lemma 3.2. For each coordinate i, using |yi′ − yi | ≤ ∥y ′ − y∥ from admissibility of ∥ · ∥ (Definition 2.3), yi′ ≥ yi − |yi′ − yi | ≥ yi − ∥y ′ − y∥ ≥ yi − dmin ≥ yi − di . Since yi′ ≥ 0, this implies
yi′ ≥ max{yi − di , 0} = (yi − di )+ .
Proof of Proposition 3.1. Fix t ∈ [T − 1] and set rt := ∥zt+1 − yt ∥. All distances in this proof are measured in the projection norm, and yt+1 is the nearest point to zt+1 in that same norm. This alignment is what will allow us to apply Lemma D.5. We break the proof into cases dependent on the size of rt relative to dmin t : 31
Case 1. If rt ≤ dmin t , then Lemma 3.2 yields zt+1 ⪰ (yt − dt )+ ⪰ xt+1 , where the second inequality uses (2). Since zt+1 ∈ Y, we have zt+1 ∈ Jt+1 and therefore qt+1 = 0. Case 2. Now suppose rt > dmin t . Define αt :=
dmin t ∈ [0, 1) rt
wt := (1 − αt )yt + αt zt+1 .
and
Because Y is convex and yt , zt+1 ∈ Y, we have wt ∈ Y. By positive homogeneity of ∥ · ∥, ∥wt − yt ∥ = ∥αt (zt+1 − yt )∥ = αt rt = dmin t . Then applying Lemma 3.2 gives wt ⪰ (yt − dt )+ ⪰ xt+1 , so wt ∈ Jt+1 . By the aligned projection certificate (Lemma D.5) applied in the norm ∥ · ∥ to the feasible witness wt , qt+1 = dist∥·∥ (zt+1 , Jt+1 ) ≤ ∥zt+1 − wt ∥ = ∥(1 − αt )(zt+1 − yt )∥ = (1 − αt )rt = rt − dmin t .
(29)
Finally by the triangle inequality, rt = ∥zt+1 − yt ∥ ≤ ∥zt+1 − zt ∥ + ∥zt − yt ∥ = ∥zt+1 − zt ∥ + qt . So we may write: qt+1 ≤ qt + ∥zt+1 − zt ∥ − dmin t Combining the two cases proves (7). Bounding qt+1 by the distance from zt+1 to wt in (29) is the crucial step that utilizes norm ∥·∥ alignment. The same norm defines qt+1 , the projection ProjJt+1 (zt+1 ), and the distance to the witness wt . The coefficient of the queue’s residual in this inequality is exactly one because (29) was proved in the same norm that defines qt+1 . Replacing that step with a different norm via norm conversion would give a multiplicative constant inside the recursion rather than the queue recursion (7).
D.4
Proof of Theorem D.2
We first provide the proof’s outline and analytical approach. We divide the horizon into excursions of the queue away from zero. On each excursion, repeated use of the queue recursion bounds the queue by cumulative hidden movement. The windowed-clearing assumption then forces every full excursion to end within at most B rounds, and the last partial excursion has length at most B as well. Proof. For t ∈ [T − 1], set at := ∥zt+1 − zt ∥. We first record a horizon-free loose bound. If qτ = 0, then repeated use of (7) and dmin ≥ 0 gives r qt+1 ≤
t X
ar
for every t ∈ {τ, . . . , T − 1}.
r=τ
32
(30)
Indeed, this follows by induction from qτ = 0 and qr+1 ≤ qr + ar . If B ≥ T , then (30) with τ = 1 gives T T X t−1 T −1 T −1 X X X X qt ≤ ar ≤ T ar ≤ B ar , t=1
t=1 r=1
r=1
r=1
so the result holds. We therefore assume B < T for the rest of the proof. We next show that if the queue is empty and at least B rounds remain, then it empties again within the next B rounds. Fix τ ≤ T −B with qτ = 0. By Assumption D.1, there exists s ∈ {τ, . . . , τ +B−1} with dmin ≥ ρ. Applying (7) at time s, then using qs = 0 if s = τ or (30) otherwise, and then finally s applying (25), s i+ hτ +B−1 i+ X + hX min qs+1 ≤ qs + as − dmin ≤ a − d ≤ a − ρ = 0. r r s s r=τ
(31)
r=τ
Thus, if qτ = 0 and τ ≤ T − B, then there exists τ ′ ∈ {τ + 1, . . . , τ + B} with qτ ′ = 0. In other words, whenever the queue is empty and a full clearing window remains, it must empty again within the next B rounds. Now define zero times recursively. Let τ1 = 1. Given τj , if τj ≤ T − B, let τj+1 be the smallest index in {τj + 1, . . . , τj + B} such that qτj+1 = 0; if τj > T − B, set τj+1 = T + 1 and stop. This yields 1 = τ1 < τ2 < · · · < τm < τm+1 = T + 1, with qτj = 0 and τj+1 − τj ≤ B for every j ∈ [m]. For the last interval this follows because τm > T − B, hence τm+1 − τm = T + 1 − τm ≤ B. Now, fix j ∈ [m]. Since qτj = 0, we may apply (30) in the first inequality below to bound the sum of the queue lengths between τj and τj+1 − 1: τj+1 −1
τj+1 −1 t−1
τj+1 −2
τj+1 −2
X
X X
X
X
t=τj
qt ≤
ar =
t=τj r=τj
(τj+1 − 1 − r)ar ≤ B
r=τj
ar .
r=τj
where the last inequality used τj+1 − τj ≤ B. The index sets {τj , . . . , τj+1 − 2} are disjoint subsets of [T − 1], so summing over j yields ∆gap T =
m τj+1 X X−1 j=1 t=τj
qt ≤ B
T −1 X
at ,
t=1
which is exactly (26). The clearing argument leverages the exact coefficient of one in the recursion (7). If we utilized + norm conversion and instead produced an inequality of the form qt+1 ≤ C[qt + at − dmin t ] with C > 1, the factor C would sit inside the dynamics introducing a factor exponential in the window P length C B in the worst-case. The condition at ≤ ρ over a window would no longer imply that one demand shock of size ρ clears the queue and would instead leave residual backlog after the shock. This helps justify the necessity of norm alignment in the analysis.
33
D.5
Proof of Lemma D.4
Proof. For each s ∈ [T ], define the event As := {dmin < ρ}. Then since ds is Fs -measurable, so is s min ds and hence As . By UPPD, we have P(As |Fs−1 ) = 1 − P (dmin ≥ ρ|Fs−1 ) ≤ 1 − µ a.s. s
(32)
Assume B ≤ T ; otherwise the event in the statement is empty. Fixing any t ∈ [T − B + 1], we first show by induction on k ∈ [B] that P(∩t+k−1 As ) ≤ (1 − µ)k . The case for k = 1 follows from (32) s=t and the tower property: P(At ) = E[P(At |Ft−1 )] ≤ 1 − µ For the inductive step, we have P
t+k \
! As
= E[1At · · · 1At+k ]
s=t
= E E[1At · · · 1At+k |Ft+k−1 ]
= E[1At · · · 1At+k−1 · P(At+k |Ft+k−1 )] ≤ E[1At · · · 1At+k−1 (1 − µ)] ! t+k−1 \ = (1 − µ)P As s=t
≤ (1 − µ)(1 − µ)k = (1 − µ)k+1 where the second equality is due to the tower property, the first inequality follows from (32), and the last bound follows by the inductive hypothesis. This completes the induction. Now setting k = B and using 1 − µ ≤ e−µ , we have ! t+B−1 \ P As ≤ (1 − µ)B ≤ e−µB s=t −B+1 t+B−1 The event that we wish to show has low probability is then A := ∪Tt=1 ∩s=t As . Combining the previous bound with a union bound, we have ! T −B+1 T −B+1 t+B−1 \ X X P(A) ≤ P As ≤ e−µB ≤ T e−µB t=1
s=t
t=1
which completes the first part of the proof. For the second part, since µBδ ≥ log(T /δ), we may bound T e−µBδ by T e− log(T /δ) = δ thereby proving the second part of the lemma.
D.6
Proof of Theorem 3.5
Proof. If Bδ ≥ T , then the loose bound (30) from the proof of Theorem D.2, applied with τ = 1, mv mv gives deterministically ∆gap T ≤ T ∆T ≤ Bδ ∆T . If Bδ < T , Lemma D.4 gives windowed clearing with B = Bδ with probability at least 1 − δ. On this event, the movement condition Assumption 3.4(ii) is mv exactly (25) with B = Bδ , so Theorem D.2 gives ∆gap T ≤ Bδ ∆T . Combining this with Lemma 2.2 base mv yields RT (u1:T ) ≤ ∆T (u1:T ) + G∗ Bδ ∆T . If Assumption 3.4(i) additionally holds, substituting ∆base T (u1:T ) ≤ RT (u1:T ) gives the stated R-form of the bound. 34
E
Omitted proofs from Section 4
E.1
General convex losses
We first record the standard movement and regret estimates for Euclidean projected OGD: Lemma E.1. For an ℓ2 norm ∥ · ∥ = ∥ · ∥2 , the target states zt and subgradients gt in HT-OGD (Algorithm 2), a positive nonincreasing stepsize sequence η1 ≥ η2 ≥ · · · > 0, and a comparator u ∈ Y, we bound the following sum of inner products: T T X 1X D22 + ⟨gt , zt − u⟩ ≤ ηt ∥gt ∥22 2ηT 2 t=1
(33)
t=1
Proof. Using the linearity of the inner product, we may write: ⟨gt , zt − u⟩ =
1 ∥zt − u∥22 + ηt2 ∥gt ∥22 − ∥(zt − u) − ηt gt ∥22 2ηt
We relate this to zt+1 using nonexpansiveness of the Euclidean projection: ∥·∥
∥·∥
∥zt+1 − u∥22 = ∥ ProjY 2 (zt − ηt gt ) − ProjY 2 (u)∥22 ≤ ∥(zt − ηt gt ) − u∥22 Combining the previous two lines results in: ⟨gt , zt − u⟩ ≤
1 ∥zt − u∥22 + ηt2 ∥gt ∥22 − ∥zt+1 − u∥22 2ηt
Summing over t ∈ [T ] yields: T X
T X 1
T
1X ⟨gt , zt − u⟩ ≤ + ηt ∥gt ∥22 2ηt 2 t=1 t=1 t=1 ! T 2 2 1 ∥z1 − u∥2 ∥zT +1 − u∥2 X 1 1 = − + − ∥zt − u∥22 2 η1 ηT ηt ηt−1 ∥zt − u∥22 − ∥zt+1 − u∥22
t=2
+
1 2
1 ≤ 2 =
T X
ηt ∥gt ∥22
t=1 T
D22 X + η1
D22 1 + 2ηT 2
t=2 T X
1 1 − ηt ηt−1
T
! D22
+
1X ηt ∥gt ∥22 2 t=1
ηt ∥gt ∥22
t=1
where the last inequality used the monotonicity of the stepsizes and Assumption 2.1. To build to regret bound under UPPD, we first prove the following regret bound under a window clearing assumption:
35
Proposition E.2 (OGD verifies the base learner conditions on the Euclidean queue). Take the projection norm to be Euclidean, ∥ · ∥ = ∥ · ∥2 , and write D2 and G2 for the capacity-set diameter and dual gradient bound from Assumption 2.1 specialized to the ℓ2 queue. Fix δ ∈ (0, 1), set Bδ := ⌈µ−1 log(T /δ)⌉, and choose a learning-rate parameter γ and step sizes ηt according to 0<γ≤
ρ √
2D2 Bδ
,
ηt =
γD2 √ . G2 t
(34)
Then HT-OGD (Algorithm 2), initialized from any z1 ∈ J1 , produces a target sequence (zt )Tt=1 ⊂ Y satisfying Assumption 3.4: (i) Linearized regret bound holds with √ 1 RT (u) := D2 G2 2γ +γ T for every static comparator u ∈ Y. (ii) Windowed movement bound holds: for every t with 1 ≤ t ≤ T − Bδ , t+B δ −1 X
∥zr+1 − zr ∥2 ≤ ρ.
r=t
Moreover, the cumulative target movement satisfies √ ∆mv T ≤ 2γD2 T .
(35)
Proof. We start with a proof that HT-OGD satisfies the windowed movement bound (Assumption 3.4(ii)) and establish a bound on ∆mv T . Then, we apply Lemma E.1 to establish the linearized regret bound (Assumption 3.4(i)). Movement and part (ii). By nonexpansiveness of the ℓ2 projection and (34), for every t, γD2 ∥·∥ ∥·∥ ∥zt+1 − zt ∥2 = ∥ ProjY 2 (zt − ηt gt ) − ProjY 2 (zt )∥2 ≤ ηt ∥gt ∥2 ≤ ηt G2 = √ . t For any t with 1 ≤ t ≤ T − Bδ , t+B δ −1 X
∥zr+1 − zr ∥2 ≤ γD2
r=t
t+B δ −1 X r=t
Bδ X p 1 1 √ ≤ γD2 √ ≤ 2γD2 Bδ ≤ ρ, r r r=1
where the last inequality uses (34), proving part (ii). Using the identical argument,√summing the √ per-step bound ∥zt+1 − zt ∥2 = γD2 / t similarly over t ∈ [T − 1] gives ∆mv T ≤ 2γD2 T and proves (35). Part (i). By Lemma E.1 and Assumption 2.1, ∆base T (u) =
T X t=1
using
PT
√
t=1 1/
T
D22 1X + ηt G22 2ηT 2 t=1 √ T D2 G 2 T γD2 G2 X 1 √ = + 2γ 2 t t=1 √ 1 ≤ D2 G2 2γ +γ T
⟨gt , zt − u⟩ ≤
√ t ≤ 2 T. 36
Proof of Theorem 4.1. √ By Proposition E.2, the OGD target sequence satisfies Assumption 3.4 with √ 1 RT (u) = D2 G2 2γ + γ T , and the cumulative target movement is bounded by ∆mv T ≤ 2γD2 T via (35). Then Theorem 3.5 applies and gives with probability at least 1 − δ for every u ∈ Y, RT (u) ≤ RT (u) + G2 Bδ ∆mv T ≤ D2 G2
1 2γ
+ γ + 2γBδ
√
T.
1 Optimizing the inner expression, f (γ) := 2γ + γ(1 + 2Bδ ) over γ > 0, the unconstrained minimum p p ⋆ is at γ = √ 1/ 2(1 + 2Bδ ), giving RT ≤ D2 G2 2(1 + 2Bδ )T . This γ ⋆ satisfies the condition γ ≤ ρ/(2D2 Bδ ) whenever D2 ≤ ρ (and more generally whenever 2Bδ (D22 − ρ2 ) ≤ ρ2 ). When the √ constraint binds, the boundary choice γ = ρ/(2D2 Bδ ) gives √ D2 Bδ ρ(1 + 2Bδ ) D2 3ρ p √ f (γ) = + ≤ + Bδ ρ ρ 2D2 2D2 Bδ
using 1 ≤ Bδ in the second inequality. This gives the stated regret bound: p 3ρ p D2 e D2 G2 T /µ . Bδ T = O + RT (u) ≤ D2 G2 ρ 2D2 p For the expectation bound, take δ = 1/T and γ = ρ/(2D2 B1/T ), which satisfies the hypothesis of Proposition E.2. Let ET denote the event that the high-probability bound holds, so P(ET ) ≥ 1 − 1/T . On ET , D2 3ρ q RT (u) ≤ D2 G2 + B1/T T ρ 2D2 On the complement, we use the crude bound RT (u) ≤ D2 G2 T . Combining, D 3ρ q 2 E RT (u) ≤ D2 G2 + B1/T T + D2 G2 , ρ 2D2 which proves the claim.
E.2
A matching lower bound under UPPD
Proof of Theorem 4.2. As previously observed, a no-demand round on the line segment YL freezes the action. Bernoulli demand creates random blocks on which the learner must commit to a single point of YL . Formally, take x1 = (0, 0) and let ξ1 , . . . , ξT be i.i.d. Bernoulli(µ). Set dt := ξt (1, 1), Then dmin ∈ {0, 1} and t
xt+1 = (yt − dt )+
P(dmin ≥ 1 | Ft−1 ) = µ, t
so UPPD (Assumption 3.3) holds with ρ = 1. If ξt = 1, then xt+1 = (0, 0). If ξt = 0, then xt+1 = yt . Then for yt+1 to be a feasible action, we must have yt+1 ∈ YL and yt+1 ⪰ yt . Since both vectors have coordinate sum 1, this forces yt+1 = yt . Thus, the horizon is partitioned into blocks between clearings where ξt = 1, and the learner plays a constant action on each block. So, we count the number of these blocks: T −1 X N := ξt , K := N + 1, t=1
37
PK and let L1 , . . . , LK be the corresponding block lengths, so j=1 Lj = T . Set tK+1 := T + 1. Conditional on the demand path, we now generate the losses block by block. When block j begins, after the learner has committed to its action for that block and before the loss and feedback from the first round of the block are revealed, draw an independent Rademacher sign σj ∈ {−1, +1} and keep that sign fixed throughout the block. For every round t in block j, define ℓt (y) :=
1 − σj 1 + σj y1 + y2 2 2
These losses are linear and convex, with gradient e1 = (1, 0) when σj = −1 and e2 = (0, 1) when σj = +1, hence ∥∇ℓt ∥2 = 1 so we may choose G = 1. Since the learner is frozen within block j, it plays some point aj = (aj,1 , aj,2 ) ∈ YL throughout that block, and aj,1 + aj,2 = 1. The point aj is Ftj −1 -measurable: it depends only on the demand realizations d1:tj −1 before block j, the earlier block signs σ1:j−1 (revealed through past feedback), and the learner’s internal randomness. By construction, σj is drawn independently of Ftj −1 . To compute the expected total loss, we condition on the demand path. Let G := σ(ξ1:T ), which determines the block count K, the block start times t1 , . . . , tK , and the block lengths L1 , . . . , LK . By construction, the signs σ1 , . . . , σK are independent of G and of each other. Within block j, every round t ∈ {tj , . . . , tj+1 − 1} satisfies yt = aj , so tj+1 −1
X
ℓt (yt ) = Lj
1−σj 1+σj 2 aj,1 + 2 aj,2
= Lj
aj,2 −aj,1 1 σj 2 + 2
t=tj
Conditioning on G and on σ1:j−1 , the action aj is determined (up to learner randomness, which we average over), and σj remains independent and uniform on {−1, +1}. Therefore tj+1 −1 X Lj aj,2 − aj,1 Lj E ℓt (yt ) G, σ1:j−1 = + Lj E[σj | G, σ1:j−1 ] = 2 2 2 t=t j
Since the right-hand side is G-measurable, integrating out σ1:j−1 leaves it unchanged. Summing over j ∈ [K] then gives, " T # " " T ## K X X X L T j E ℓt (yt ) = E E ℓt (yt ) G = E = 2 2 t=1
t=1
j=1
Thus, any learner incurs loss T /2 in expectation. To bound the regret, we proceed with evaluating the loss of a comparator. Define K X S := Lj σj j=1
For any fixed comparator u = (u1 , u2 ) ∈ Y, where u2 = 1 − u1 , T X t=1
ℓt (u) =
K X j=1
Lj
1 − σj 1 + σj u1 + u2 2 2
=
T +S − u1 S 2
Hence the best static comparator is u⋆ = (1, 0) when S ≥ 0 and u⋆ = (0, 1) when S < 0, so min u∈Y
T X
ℓt (u) =
t=1
38
T |S| − 2 2
Therefore, the expected regret is " T # T X X 1 E ℓt (yt ) − min ℓt (u) = E|S| u∈Y 2 t=1
t=1
It remains to lower bound E|S|. Conditional on the block lengths L1:K , S is a Rademacher sum with K X 2 E[S | L1:K ] = L2j =: V j=1
and 4
2
E[S | L1:K ] = 3V − 2
K X
L4j ≤ 3V 2
j=1
Applying Paley–Zygmund to S 2 with θ = 1/2 yields 1 V2 1 V V2 2 ≥ · = P S ≥ L1:K ≥ (1/2)2 · 2 E[S 4 |L1:K ] 4 3V 2 12 p Now on the event {S 2 ≥ V /2}, we have |S| ≥ V /2 so r r V 1 V 2 E[|S| | L1:K ] ≥ E[|S| · 1{S 2 ≥V /2} | L1:K ] ≥ P(S ≥ V /2 | L1:K ) ≥ 2 12 2 Now we have a lower bound on the conditional expectation E[|S| | L1:K ]. To turn this into a bound on the unconditional expectation E|S|, we restrict to an event on which V is easy to control. To start, note that E[N ] = (T − 1)µ ≤ µT , so Markov’s inequality gives P(N ≥ 2µT ) ≤ 1/2, which implies 1 P(N ≤ 2µT ) ≥ 2 Equivalently, the event {K ≤ 2µT + 1} has probability at least 1/2. Because T ≥ µ−1 , then the event E := {K ≤ 3µT } also has probability at least 1/2. On E, Cauchy–Schwarz gives V =
K X
L2j ≥
j=1
T2 T ≥ K 3µ
Therefore √ √ 1 1 1 E|S| = E[E[|S| | L1:K ]] ≥ √ E[ V ] ≥ √ E[ V 1E ] ≥ √ 12 2 12 2 24 6 √ Substituting into the regret identity proves the claim with c = 1/(48 6).
s
T µ
Theorem 4.2 already applies on a line segment, namely the one-dimensional simplex {y ∈ R2+ | y1 + y2 = 1}. We use this geometry for a reason: on the interval [0, 1], a no-demand round only enforces yt+1 ≥ yt , whereas on the simplex it forces equality and hence true frozen blocks. The theorem is also genuinely different from Theorem 5 of Ichikawa et al. (2026). Their construction √ fixes deterministic cycles of length Lmax and proves an Ω( Lmax T ) barrier through that fixed-cycle geometry. Here the cycle lengths are random and induced by Bernoulli clearings, and the proof uses the random signed block sum S tied directly to UPPD. Appendix C explains how UPPD relates to the sell-out window Lmax ; the two lower bounds address different primitives. 39
E.3
Strongly convex losses
Lemma E.3 (Per-step inequality under strong convexity). Suppose ℓt is α-strongly convex on Y ∥·∥ with respect to ∥ · ∥. For yt = ProjJt (zt ), qt = ∥zt − yt ∥, and every u ∈ Y, ℓt (yt ) − ℓt (u) ≤ ⟨gt , zt − u⟩ + G∗ qt −
α α ∥zt − u∥2 + qt2 4 2
(36)
Proof. By α-strong convexity of ℓt at yt , ℓt (yt ) − ℓt (u) ≤ ⟨gt , yt − u⟩ −
α ∥yt − u∥2 2
Then we may split the inner product ⟨gt , yt − u⟩ = ⟨gt , zt − u⟩ + ⟨gt , yt − zt ⟩. Then by the generalized Hölder’s inequality, we may bound ⟨gt , yt − zt ⟩ ≤ ∥gt ∥∗ ∥yt − zt ∥ ≤ G∗ qt where the last inequality used the subgradient dual bound. The triangle inequality combined with (a + b)2 ≤ 2a2 + 2b2 gives ∥zt − u∥2 ≤ 2∥yt − u∥2 + 2qt2 Hence − α2 ∥yt − u∥2 ≤ − α4 ∥zt − u∥2 + α2 qt2 . Combining the previous inequalities gives the claim. Proof of Corollary 4.3. Summing (36) over t = 1, . . . , T gives RT (u1:T ) ≤
T X t=1
T
αX 2 α + ⟨gt , zt − ut ⟩ − ∥zt − ut ∥2 + G∗ ∆gap qt T 4 2 t=1
The first term is at most Rsc T (u1:T ; α) by (12). Since qt ≤ D by Assumption 2.1, then T X
qt2 ≤ D
t=1
T X
qt = D∆gap T
t=1
Combining, we rewrite the regret bound as: RT (u1:T ) ≤ Rsc T (u1:T ; α) +
αD G∗ + ∆gap T 2
mv Then (9) of Theorem 3.5 applies under Assumption 3.4(ii) and gives ∆gap T ≤ Bδ ∆T with probability at least 1 − δ. Applying this bound yields (13).
Proposition E.4 (HT-OGD base learner under strong convexity). Suppose Assumption 2.1 holds and each ℓt is α-strongly convex on Y with respect to ∥ · ∥2 . Fix δ ∈ (0, 1), set Bδ := ⌈µ−1 log(T /δ)⌉, and define Bδ 2 sδ := max 1, αρ/(2G ) , ηt := . 2 − 1 α(t + sδ ) e Then HT-OGD (Algorithm 2) initialized from any z1 ∈ J1 produces a target sequence (zt )Tt=1 ⊂ Y satisfying Assumption 3.4(ii) and the strongly convex linearized regret bound (12) with T αsδ D22 G22 Rsc (u; α) := + log 1 + . (37) T 4 α sδ Moreover, the cumulative target movement is bounded by 2G2 T ∆mv log 1 + . T ≤ α sδ 40
(38)
Proof. We first verify the windowed movement bound (Assumption 3.4(ii)) and the cumulative movement bound (38). By nonexpansiveness of the Euclidean projection, ∥·∥
∥·∥
∥zt+1 − zt ∥2 = ∥ ProjY 2 (zt − ηt gt ) − ProjY 2 (zt )∥2 ≤ ∥ηt gt ∥2 ≤ ηt G2 = For any window of length Bδ starting at t ∈ [T − Bδ ], using the bound gives t+B δ −1 X
∥zr+1 − zr ∥2 ≤
r=t
2G2 α
t+B δ −1 X r=t
2G2 . α(t + sδ )
PN
1 n=1 n+A ≤ log(1 + N/A)
Bδ 1 1 2G2 X 2G2 Bδ ≤ ≤ log 1 + ≤ ρ, r + sδ α r + sδ α sδ r=1
where the last inequality follows from the fact that sδ ≥ Bδ /(eαρ/(2G2 ) − 1) and rearranging for ρ. This proves Assumption 3.4(ii). Using the same argument but summing over t ∈ [T − 1] rather than a window of length Bδ proves (38). It remains to establish the strongly convex linearized regret bound (12) with Rsc T (u; α) defined in (37). By the OGD update and non-expansiveness of the Euclidean projection, ∥zt+1 − u∥22 ≤ ∥zt − ηt gt − u∥22 = ∥zt − u∥22 − 2ηt ⟨gt , zt − u⟩ + ηt2 ∥gt ∥22 , and by bounding ∥gt ∥2 with its gradient bound, this rearranges to ⟨gt , zt − u⟩ ≤
∥zt − u∥22 − ∥zt+1 − u∥22 ηt G22 + . 2ηt 2
It remains to bound the sum of ⟨gt , zt − u⟩ over t ∈ [T ]. By our choice of stepsize ηt = 2/(α(t + sδ )), we have the identity 1 1 α(t + sδ ) − α(t − 1 + sδ ) α − = = , 2ηt 2ηt−1 4 4 which lets us telescope the sum of the first term in the previous bound: T T X ∥zt − u∥22 − ∥zt+1 − u∥22 ∥z1 − u∥22 ∥zT +1 − u∥22 X 1 1 + = − − ∥zt − u∥22 2ηt 2η1 2ηT 2ηt 2ηt−1 t=1
t=2
T
∥z1 − u∥22 ∥zT +1 − u∥22 α X − + ∥zt − u∥22 = 2η1 2ηT 4 t=2
Splitting the leading coefficient as 1/(2η1 ) = αsδ /4 + α/4 lets us merge the leftover α4 ∥z1 − u∥22 piece into the running sum: T X ∥zt − u∥2 − ∥zt+1 − u∥2 2
2
2ηt
t=1
T
=
αsδ αX ∥zT +1 − u∥22 ∥zt − u∥22 − ∥z1 − u∥22 + . 4 4 2ηT t=1
Dropping the nonpositive last term and using ∥z1 − u∥2 ≤ D2 from Assumption 2.1, T X ∥zt − u∥2 − ∥zt+1 − u∥2 2
t=1
2
2ηt
T
αsδ D22 α X ≤ + ∥zt − u∥22 . 4 4 t=1
Combining with the per-step OGD inequality and rearranging, T X t=1
⟨gt , zt − u⟩ −
T
T
t=1
t=1
αX αsδ D22 G22 X ∥zt − u∥22 ≤ + ηt . 4 4 2 41
P P The stepsize sum satisfies Tt=1 ηt = (2/α) Tt=1 1/(t + sδ ) ≤ (2/α) log(1 + T /sδ ). Substituting yields (12) with Rsc T as in (37). Proof of Theorem 4.4. By Proposition E.4, HT-OGD with stepsize ηt = 2/(α(t + sδ )) satisfies Assumption 3.4(ii) and the strongly convex linearized regret bound (12) with Rsc T (u; α) given in (37), and the cumulative target movement is bounded by (38). Applying Corollary 4.3 yields, with probability at least 1 − δ, αsδ D22 G22 T αD2 2G2 T RT (u) ≤ + log 1 + + G2 + Bδ · log 1 + 4 α sδ 2 α sδ 2 G2 αsδ D2 T = + G2 (1 + 2Bδ ) + D2 Bδ log 1 + 4 α sδ T αsδ D22 3G2 ≤ + G 2 Bδ + D2 log 1 + 4 α sδ = O sδ + Bδ log(1 + T /sδ ) Since sδ = O(Bδ ) and Bδ = Θ(µ−1 log(T /δ)), this simplifies to RT (u) = O (log(T /δ) log T )/µ , as claimed.
E.4
Dynamic regret
Throughout, we extend the comparator sequence as necessary by setting uT +1 := uT . Proposition E.5 (Constant-stepsize OGD verifies the base learner conditions for dynamic comparators). Take the projection norm to be Euclidean, ∥·∥ = ∥·∥2 . Fix δ ∈ (0, 1), set Bδ := ⌈µ−1 log(T /δ)⌉, and choose a constant stepsize η ∈ (0, ρ/(Bδ G2 )]. Run HT-OGD (Algorithm 2) with ηt ≡ η from z1 ∈ J1 . Then for every comparator sequence u1:T ∈ Y T with path variation PT,2 , the target sequence (zt )Tt=1 ⊂ Y satisfies Assumption 3.4: (i) Linearized regret bound holds with RT (u1:T ) :=
D22 + 2D2 PT,2 ηG22 T + . 2η 2
(ii) Windowed movement bound holds: for every t with 1 ≤ t ≤ T − Bδ , t+B δ −1 X
∥zr+1 − zr ∥2 ≤ ρ.
r=t
Moreover, the cumulative target movement satisfies ∆mv T ≤ ηG2 T.
(39)
Proof. Movement and part (ii). By nonexpansiveness of the ℓ2 projection and the hypothesis η ≤ ρ/(Bδ G2 ), for every t, ∥·∥
∥·∥
∥zt+1 − zt ∥2 = ∥ ProjY 2 (zt − ηgt ) − ProjY 2 (zt )∥2 ≤ η∥gt ∥2 ≤ ηG2 . Therefore for every t with 1 ≤ t ≤ T − Bδ , t+B δ −1 X
∥zr+1 − zr ∥2 ≤ Bδ ηG2 ≤ ρ,
r=t
42
which is part (ii). Summing ∥zt+1 − zt ∥2 ≤ ηG2 over t ∈ [T − 1] gives (39). Part (i). By the one-step projection argument used in the proof of Lemma E.1, applied with comparator ut , the projected OGD update with constant stepsize gives ⟨gt , zt − ut ⟩ ≤
∥zt − ut ∥22 − ∥zt+1 − ut ∥22 ηG22 + . 2η 2
1 By inserting and subtracting 2η ∥zt+1 − ut+1 ∥22 then summing over t, we may telescope the series: T X t=1
T
1 X ∥zt+1 − ut+1 ∥22 − ∥zt+1 − ut ∥22 ⟨gt , zt − ut ⟩ ≤ 2η +
=
t=1 T X
1 2η
t=1
T 1 X
2η
ηG22 T ∥zt − ut ∥22 − ∥zt+1 − ut+1 ∥22 + 2
∥zt+1 − ut+1 ∥22 − ∥zt+1 − ut ∥22
t=1
ηG22 T 1 ∥z1 − u1 ∥22 − ∥zT +1 − uT +1 ∥22 + 2η 2 T ηG22 T 1 1 X ≤ ∥z1 − u1 ∥22 + ∥zt+1 − ut+1 ∥22 − ∥zt+1 − ut ∥22 + . 2η 2η 2 +
t=1
Since ∥z1 − u1 ∥2 ≤ D2 and ∥zt+1 − ut+1 ∥22 − ∥zt+1 − ut ∥22 ≤ 2D2 ∥ut+1 − ut ∥2 using the reverse triangle inequality and the diameter bound on Y, we obtain ∆base T (u1:T ) =
T X D2 + 2D2 PT,2 ηG22 T ⟨gt , zt − ut ⟩ ≤ 2 + = RT (u1:T ). 2η 2 t=1
Proof of Theorem 4.5. By Proposition E.5, the OGD target sequence satisfies Assumption 3.4 with RT (u1:T ) = (D22 + 2D2 PT,2 )/(2η) + ηG22 T /2 and ∆mv T ≤ ηG2 T via (39). Theorem 3.5 then gives with probability at least 1 − δ for every comparator sequence u1:T ∈ Y T , D22 + 2D2 PT,2 1 2 + Bδ + ηG2 T. 2η 2 q D2 (D2 +2PT,2 ) 1 ∗ ∗ Balancing the two terms, the unconstrained minimizer is η = G2 (2Bδ +1)T . Provided η ≤ ∗ ρ/(Bδ G2 ), substituting η gives the stated bound q RT (u1:T ) ≤ G2 (2Bδ + 1) D2 (D2 + 2PT,2 ) T . RT (u1:T ) ≤ RT (u1:T ) + G2 Bδ ∆mv T ≤
43
E.4.1
The SOGD base learner and proof of Theorem 4.6
The SOGD base learner is the smoothed OCO algorithm of Zhang et al. (2022). It runs a grid of OGD experts with different time scales and combines them with a meta-learner that penalizes switching. Ichikawa et al. (2026) used this learner for hidden-target inventory under a single linear capacity constraint. We use the same base learning primitive, but the inventory layer is different: the queue reduction only asks for a regret-plus-switching-cost bound and a local movement bound. Algorithm 4: Hidden-target method with an SOGD base learner Input: Domain Y, switching parameter λ > 0, horizon T , initial target z1 ∈ J1 Initialize the SOGD base learner of Zhang et al. (2022) on Y at z1 ; for t = 1, 2, . . . , T do Observe xt and define Jt = Y ∩ {y ∈ Rn | y ⪰ xt }; ∥·∥
Let zt be the current target produced by SOGD and implement yt = ProjJt 2 (zt ); Observe gt ∈ ∂ℓt (yt ) and the next state xt+1 ; Feed the shifted linear loss fet (z) = ⟨gt , z⟩ − minw∈Y ⟨gt , w⟩ to SOGD and receive zt+1 ; end The shifted loss is nonnegative and has the same linear regret difference, since fet (zt ) − fet (ut ) = ⟨gt , zt − ut ⟩ and is required by the SOGD algorithm. The hidden-target reduction (Theorem 3.5) does not require a separate abstract interface for switching-aware base learners. As we show below, the native SOGD bound can be rearranged into the form of Assumption 3.4(i), with the switching-cost coefficient producing exactly the cancellation needed in the reduction. We now verify that SOGD satisfies Assumption 3.4. The base learner architecture again follows Ichikawa et al. (2026): a grid of OGD experts is combined by a switching-aware smoothed OGD meta-learner. What must be re-established here is that this learner satisfies not only a switchingaware regret bound, but also the local hidden target movement condition required by the queue reduction on arbitrary convex sets. For the analysis, we use the concrete SOGD parameterization of Zhang et al. (2022) with the projection norm taken to be Euclidean: let j K := log2
k T + 1, 32 max{λ, 1} log T
n(k) := T 21−k ,
η (k) :=
D2 p G2 (1 + 2λ)n(k)
For each k ∈ [K], we run OGD expert Ak with step size η (k) and aggregate the experts with the discounted-normal-predictor combiner using M = 2 and Z = 1/T . With an additional assumption on the size of the horizon T , we prove that SOGD verifies the base learner conditions: Proposition E.6. Assume λ ≥ 1, T ≥ max{32λ log T, e}, and run Algorithm 4 with the SOGD parameterization above. Then the target sequence (zt )Tt=1 satisfies the per-step movement bound ∥zt+1 − zt ∥2 ≤
2D2 λ
for all t ∈ [T − 1],
(40)
SOGD ∆base (u1:T ; λ) − G2 λ∆mv T (u1:T ) ≤ RT T
(41)
and the linearized regret bound
holds for every comparator sequence u1:T ∈ Y T with path variation PT,2 , where RSOGD (u1:T ; λ) is T defined by (15).
44
mv ≤ Proof of Proposition E.6. Rearranging (41) into the equivalent form ∆base T (u1:T ) + G2 λ ∆T RSOGD (u1:T ; λ), this is the λ ≥ 1 specialization of Theorem 4 of Zhang et al. (2022) on the T interval [1, T √ ], withpG = G2 , D = D2 , and P1,T = PT,2 . The source theorem’s second term is 120GD max{ λ, 1} T (1 + 2P1,T /D) log T , which equals the second term in (15) because λ ≥ 1. The theorem applies since each fet is convex, takes values in [0, G2 D2 ] on Y, has gradient norm at most G2 , and satisfies fet (zt ) − fet (ut ) = ⟨gt , zt − ut ⟩.
It remains to prove the local movement bound (40). Following the framework of Algorithm 4 in (k) (k) Zhang et al. (2022), write at for the output of expert Ak , vt for the output of the kth aggregate, (k) (k) (k−1) (k) (K) and ωt ∈ [0, 1] for the combiner weight that forms vt from vt and at . Thus zt = vt . The proof uses two facts: each OGD expert moves by at most its step size times G2 , and each combiner weight changes slowly by Eq. (67) of Zhang et al. (2022). For the experts, nonexpansiveness of Euclidean projection gives (k)
D2
(k)
mk := sup ∥at+1 − at ∥2 ≤ η (k) G2 = p t
(1 + 2λ)n(k)
.
For the combiner weights, Eq. (67) of Zhang et al. (2022) with Z = 1/T and λ ≥ 1 yields ! r 1 1 log T (k) (k) + κk := sup |ωt+1 − ωt | ≤ √ 4T n(k) t λ Since n(k) ≤ T and T ≥ e, we have 1 1 1 ≤ √ ≤ 4T 4 4 T
r
log T n(k)
so we may loosen the bound on κk as: ! r r r log T 1 log T 5 log T 1 √ + ≤ κk ≤ √ 4 n(k) n(k) λ 4 λ n(k) Now define (k)
(k)
Mk := sup ∥vt+1 − vt ∥2 t
(1)
Since vt
(1)
= at , we have M1 = m1 . For k ≥ 2, (k)
vt (k)
(k)
(k−1)
= (1 − ωt )vt
(k) (k)
+ ω t at
(k)
Taking the difference of vt+1 and vt , we have (k) (k) (k) (k−1) (k) (k) (k) (k−1) (k) (k) vt+1 − vt = (1 − ωt+1 )vt+1 + ωt+1 at+1 − (1 − ωt )vt + ωt at (k)
(k−1)
Add and subtract (1 − ωt+1 )vt (k)
(k)
(k)
and ωt+1 at . Then using triangle inequality,
(k)
(k)
(k−1)
∥vt+1 − vt ∥2 ≤ (1 − ωt+1 )∥vt+1 (k)
(k)
(k−1)
− vt (k)
+ ωt+1 ∥at+1 − at ∥2 45
∥2
(k)
(k)
(k)
+ |ωt+1 − ωt | ∥at (k)
(k−1)
− vt
∥2
(k−1)
(k)
(k)
Both at and vt belong to Y, whose diameter is D2 , and since the weights ωt , ωt+1 ∈ [0, 1], we can bound these distances as Mk ≤ Mk−1 + mk + D2 κk Summing this recursion from k = 2 to k = K telescopes the Mk terms and gives MK ≤
K X
mk + D 2
k=1
K X
κk
k=2
bound the sum PKwhere1 the sum for the mk terms starts at 1 since M1 = m1 . Now, we will (k) √ = T 21−k and k=1 n(k) since this will be used to bound each of the two sums above. Because n our choice of K is j k T K = log2 +1 32λ log T we have n(K) ≥ 32λ log T . Therefore K X
√
k=1
1 n(k)
=√
1
K−1 X
n(K) k=0
2
−k/2
≤√
1
∞ X
n(K) k=0
−k/2
2
√ 2+ 2 1 = √ ≤√ (K) 2λ log T n
Consequently, K X
mk ≤ √
k=1
where we used
√
2λ ≤
√
K X D2 1 D2 1 D2 D2 √ ≤√ ·√ ≤ √ ≤ (k) 2λ 2λ log T 2λ log T 1 + 2λ k=1 n 1 + 2λ
2λ + 1 and T ≥ e. Similarly,
√ √ K 5D2 log T X 1 1 5D2 D2 5D2 log T √ √ √ D2 κk ≤ ·√ = √ ≤ ≤ λ 2λ log T 4λ 2 4 λ 4 λ n(k) k=2 k=2 K X
(K)
Combining these bounds, we have MK ≤ 2D2 /λ. Since zt = vt
, this proves (40).
This proposition lets us show that the SOGD instantiation satisfies Assumption 3.4 and invoke the hidden-target reduction. Proof of Theorem 4.6. Set λ = λδ . Since λδ ≥ Bδ ≥ 1 and T ≥ max{32λδ log T, e} by assumption, Proposition E.6 applies. The local movement bound (40) gives, for every t with 1 ≤ t ≤ T − Bδ , t+B δ −1 X
∥zr+1 − zr ∥2 ≤ Bδ ·
r=t
2D2 ≤ ρ, λδ
because λδ ≥ 2D2 Bδ /ρ by construction. This verifies Assumption 3.4(ii), and the linearized regret bound (41) verifies Assumption 3.4(i) with RT (u1:T ) = RSOGD (u1:T ; λδ ) − G2 λδ ∆mv T T . Applying Theorem 3.5, with probability at least 1 − δ, mv RT (u1:T ) ≤ RSOGD (u1:T ; λδ ) − G2 λδ ∆mv T T + G 2 Bδ ∆T
= RSOGD (u1:T ; λδ ) − G2 (λδ − Bδ )∆mv T T 46
≤ RSOGD (u1:T ; λδ ) T
since λδ ≥ Bδ , proving the regret bound (16). It remains to justify the explicit simplification in (17). Since λδ ≥ 1, log T ≥ 1, and 1 + λδ ≤ 2λδ , the native SOGD bound gives r 2PT,2 SOGD log T RT (u1:T ; λδ ) ≤ 2G2 D2 2λδ T 1 + D2 r 2PT,2 + 120G2 D2 λδ T 1 + log T D2 r √ 2PT,2 = (120 + 2 2)G2 D2 λδ T 1 + log T . D2 We now remove the ceilings. Since µ ≤ 1, T ≥ e, and δ ∈ (0, 1), 1 T log ≥ 1. µ δ Using ⌈x⌉ ≤ 2x for x ≥ 1, we get Bδ ≤
2 T log , µ δ
and hence n 2D o 8 T n D o 2 2 λδ ≤ 2Bδ max 1, ≤ log max 1, . ρ µ δ ρ Also, 1+
2PT,2 PT,2 ≤2 1+ . D2 D2
Substituting the last two displays into the preceding SOGD bound yields s s n D o T T √ P T,2 2 RSOGD (u ; λ ) ≤ 4(120 + 2 2)G D 1 + max 1, log log T 2 2 1:T δ T D2 ρ µ δ s s n D o T T PT,2 2 ≤ 500 G2 D2 1+ max 1, log log T , D2 ρ µ δ √ because 4(120 + 2 2) ≤ 500. This proves (17).
E.5
Mirror descent base learners
This appendix proves Proposition E.8 (the general mirror-descent base learner verification) and uses it to derive both the general OMD regret rate of Theorem 4.7 and the entropic-OMD instantiation of Theorem 4.8.
47
E.5.1
General mirror descent
Proposition E.7 (One-step mirror descent inequality). Assume zt , zt+1 ∈ D and that R satisfies the domain, differentiability, and Bregman strong-convexity assumptions stated in Section 4.4. Then under the OMD update (18), the following one-step inequality holds for every u ∈ Y: ⟨gt , zt − u⟩ ≤
DR (u, zt ) − DR (u, zt+1 ) ηt ∥gt ∥2∗ + . ηt 2σ
(42)
The proof is standard; we include it below for completeness. Proof. The OMD objective ϕ(z) := ηt ⟨gt , z⟩+DR (z, zt ) has gradient ∇ϕ(z) = ηt gt +∇R(z)−∇R(zt ). First-order optimality of zt+1 = arg minz∈Y ϕ(z) over the convex set Y gives ⟨∇ϕ(zt+1 ), u − zt+1 ⟩ ≥ 0 for every u ∈ Y. Substituting the expression for ∇ϕ(z) and rearranging, ηt ⟨gt , zt+1 − u⟩ ≤ ⟨∇R(zt+1 ) − ∇R(zt ), u − zt+1 ⟩.
(43)
Before continuing, we prove an identity that for a, b, c ∈ Y. Expanding the definition of DR we have: DR (c, a) − DR (c, b) = −R(a) − ⟨∇R(a), c − a⟩ + R(b) + ⟨∇R(b), c − b⟩ DR (b, a) = R(b) − R(a) − ⟨∇R(a), b − a⟩. Subtracting the second equation from the first, DR (c, a) − DR (c, b) − DR (b, a) = ⟨∇R(b), c − b⟩ − ⟨∇R(a), c − a⟩ + ⟨∇R(a), b − a⟩ The last two terms combine into ⟨∇R(a), b − c⟩, allowing us to write: ⟨∇R(b) − ∇R(a), c − b⟩ = DR (c, a) − DR (c, b) − DR (b, a)
(44)
Now, apply this identity with a = zt , b = zt+1 , c = u and substitute into (43): ηt ⟨gt , zt+1 − u⟩ ≤ DR (u, zt ) − DR (u, zt+1 ) − DR (zt+1 , zt ).
(45)
Rewriting the inner product in (45) with zt − u = (zt − zt+1 ) + (zt+1 − u), we write: ηt ⟨gt , zt − u⟩ ≤ ηt ⟨gt , zt − zt+1 ⟩ − DR (zt+1 , zt ) + DR (u, zt ) − DR (u, zt+1 ).
(46)
Now we bound the first two terms on the right hand side. By the generalized Hölder’s inequality, ⟨gt , zt − zt+1 ⟩ ≤ ∥gt ∥∗ ∥zt − zt+1 ∥. Then by Young’s inequality with a = ηt ∥gt ∥∗ and b = ∥zt − zt+1 ∥, ηt ∥gt ∥∗ · ∥zt − zt+1 ∥ ≤
ηt2 ∥gt ∥2∗ σ + ∥zt − zt+1 ∥2 2σ 2
Finally, by the Bregman strong-convexity assumption, DR (zt+1 , zt ) ≥ σ2 ∥zt+1 −zt ∥2 . Then combining these two bounds, we have ηt ⟨gt , zt − zt+1 ⟩ − DR (zt+1 , zt ) ≤
ηt2 ∥gt ∥2∗ σ σ η 2 ∥gt ∥2∗ + ∥zt − zt+1 ∥2 − ∥zt − zt+1 ∥2 = t 2σ 2 2 2σ
Substituting back into (46) and dividing by ηt > 0 proves (42).
48
Using the one-step inequality, we now verify that the OMD iterates satisfy the base learner conditions of Assumption 3.4. Proposition E.8 (Mirror descent verifies the base learner conditions). Take an admissible norm ∥ · ∥ with dual ∥ · ∥∗ and a regularizer R satisfying the domain, differentiability, and Bregman strong-convexity assumptions stated in Section 4.4. Write G∗ := supt ∥gt ∥∗ . Fix δ ∈ (0, 1), set Bδ := ⌈µ−1 log(T /δ)⌉, and pick a constant stepsize η ∈ (0, ρσ/(Bδ G∗ )]. Run hidden-target projection with the OMD update (18) from any z1 ∈ J1 ∩ D, and assume the update returns points in D. Then the target sequence (zt )Tt=1 ⊂ Y satisfies Assumption 3.4: (i) Linearized regret bound holds with RT (u) := DR (u, z1 )/η + ηT G2∗ /(2σ) for every u ∈ Y. (ii) Windowed movement bound: for every t with 1 ≤ t ≤ T − Bδ , t+B δ −1 X
∥zr+1 − zr ∥ ≤ Bδ ηG∗ /σ ≤ ρ.
r=t
Moreover, ∆mv T ≤ ηG∗ T /σ. Proof of Proposition E.8. Part (i). Summing (42) over t ∈ [T ] with constant stepsize η, the Bregman terms telescope and since the Bregman divergence is always non-negative, DR (u, zT +1 ) ≥ 0 gives ∆base T (u) =
T X DR (u, z1 ) − DR (u, zT +1 ) ηT G2∗ DR (u, z1 ) ηT G2∗ ⟨gt , zt − u⟩ ≤ + ≤ + η 2σ η 2σ t=1
where the right-hand side is RT (u), finishing the proof of part (i). Part (ii) and movement. By strong convexity of R, we have DR (zt , zt+1 ) ≥ σ2 ∥zt+1 − zt ∥2 . 2
2
t ∥∗ Then note that applying the one-step inequality (42) with u = zt , we have DR (zt , zt+1 ) ≤ η ∥g 2σ . Combining, we have r 2 η∥gt ∥∗ ηG∗ ∥zt+1 − zt ∥ ≤ DR (zt , zt+1 ) ≤ ≤ σ σ σ Summing over a window of Bδ consecutive rounds:
t+B δ −1 X
∥zr+1 − zr ∥ ≤
r=t
Bδ ηG∗ ≤ ρ, σ
using the stepsize hypothesis. Summing over t ∈ [T − 1] instead gives ∆mv T ≤ ηG∗ T /σ. Proof of Theorem 4.7. If G∗ = 0, then all linearized losses are constant on Y, the target movement bound is zero, and the claim is immediate. Assume G∗ > 0. Applying Theorem 3.5 with RT (u) and ∆mv T from Proposition E.8 gives RT (u) ≤
DR (u, z1 ) ηT G2∗ ηG∗ T DR (u, z1 ) ηT G2∗ 1 + + G∗ Bδ · = + + B . δ 2 η 2σ σ η σ
(47)
Bounding DR (u, z1 ) ≤ BR gives (20) for every admissible stepsize. The right-hand side is convex in η, and its unconstrained minimizer is s BR σ ∗ η = . G2∗ T (1/2 + Bδ ) 49
The minimizer over the feasible interval η ≤ ρσ/(Bδ G∗ ) is therefore min{η ∗ , ρσ/(Bδ G∗ )}. If η ∗ satisfies the boundary constraint, substituting η = η ∗ into (20) gives s ! r BR T (1/2 + Bδ ) B T R e G∗ , RT (u) ≤ 2G∗ =O σ σµ which is (21). E.5.2
Entropic OMD on bounded Rn+
Take Y ⊆ Rn+ bounded with M := supx∈Y ∥x∥1 . The projection norm is ℓ1 , the dual is ℓ∞ , and we write G∞P:= supt ∥gt ∥∞ . The base learner is mirror descent with the negative-entropy regularizer R(x) := ni=1 xi log xi , started from a strictly positive feasible target; Theorem 4.8 uses the uniform target and explicitly assumes it lies in Y. The Bregman divergence of the negative-entropy regularizer R on Rn+ is the unnormalized Kullback–Leibler divergence: DR (u, v) =
n X
ui log
i=1
ui − ∥u∥1 + ∥v∥1 vi
(48)
which reduces to the classical Kullback-Leibler divergence DKL when u and v are probability distributions since we would have ∥u∥1 = ∥v∥1 = 1. Strong convexity of the entropy on Y. To prove R is strongly convex with respect to ℓ1 , we use an equivalent definition based on R’s Hessian. On the positive orthant, the Hessian of R at x ∈ Rn++ is ∇2 R(x) = diag(1/xi ). By Cauchy–Schwarz, for any v ∈ Rn and x ∈ Rn++ , ∥v∥21 =
n X |vi | √ √ · xi xi
!2 ≤
n X v2
i=1
i=1
i
n X
xi
i=1
!
! xi
= ⟨v, ∇2 R(x)v⟩ · ∥x∥1
Hence ⟨v, ∇2 R(x)v⟩ ≥ ∥v∥21 /∥x∥1 ≥ ∥v∥21 /M for every x ∈ Y ∩ Rn++ . The associated Bregman inequality extends to boundary comparators by the lower-semicontinuity of the unnormalized KL divergence, so R is (1/M )-strongly convex with respect to ℓ1 in the sense used above. Proof of P Theorem 4.8. We apply Theorem 4.7 with ∥ · ∥ = ℓ1 , ∥ · ∥∗ = ℓ∞ , the entropy regularizer R(x) = i xi log xi , σ = 1/M (from the strong convexity argument above), and G∗ = G∞ . The boundary stepsize condition reads η ≤ ρ/(M Bδ G∞ ). By assumption the uniform initialization z1 = (M/n, . . . , M/n) lies in Y; since x1 = 0, we have J1 = Y and hence z1 ∈ J1 . It remains to justify the domain condition in Theorem 4.7. Suppose zt ∈ Y ∩ Rn++ and let ϕt (z) = η⟨gt , z⟩ + DR (z, zt ). Since Y is compact and ϕt is lower semicontinuous on Y, a minimizer exists. No minimizer can have a zero coordinate: ifPzi = 0 for some i, then the feasible points z ε = (1 − ε)z + εzt satisfy ϕt (z ε ) − ϕt (z) = O(ε) + i:zi =0 εzt,i log ε < 0 for all sufficiently small ε > 0. Hence every minimizer lies in Y ∩ Rn++ . Induction from the strictly positive z1 proves that all entropy iterates remain in D := Y ∩ Rn++ . Now we must bound DR (u, z1 ). Using the explicit form of DR in (48) with ∥z1 ∥1 = M , DR (u, z1 ) =
X
ui log
i
50
ui n − ∥u∥1 + M M
Write s := ∥u∥1 ∈ [0, M ] and parametrize ui = spi with p a probability vector with ∥p∥1 = 1 (taking p arbitrary if s = 0). Substituting, DR (u, z1 ) = s log
sn − sH(p) − s + M M
P where H(p) := − i pi log pi is the Shannon entropy of p and takes values in [0, log n]. So we have −sH(p) ≤ 0, giving sn −s+M DR (u, z1 ) ≤ g(s) := s log M On [0, M ], the function g has derivative g ′ (s) = log(sn/M ), so g is decreasing on [0, M/n] and increasing on [M/n, M ]. Thus, g attains its maximum at either endpoint of the interval: g(0) = M or g(M ) = M log n. Therefore BR ≤ max{M, M log n} ≤ M (1 + log n) Substituting BR ≤ M (1 + log n) and σ = 1/M in the constrained OMD bound (20) gives (23). In the square-root branch, substituting the same quantities in (21) gives s ! p T log n e M G∞ RT (u) ≤ 2M G∞ T (1 + log n)(1/2 + Bδ ) = O . µ
51