Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

Technical Summary: Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

Problem Formulation
The paper addresses Online Inventory Optimization (OIO), a setting where a learner selects order-up-to vectors $y_t$ from a capacity set $Y \subseteq \mathbb{R}^n_+$ subject to physical inventory constraints. Unlike standard Online Convex Optimization (OCO), OIO features "physical memory": the feasible action set at time $t$, denoted $J_t = Y \cap \{y \mid y \succeq x_t\}$, depends on the current inventory state $x_t$. Inventory carries over, meaning a learner cannot simply project a gradient step onto $Y$ if the resulting vector is below the current stock level. The environment chooses adversarial demand $d_t$ and loss functions $\ell_t$, and the learner aims to minimize dynamic or static regret against a comparator sequence.

Prior work, such as MaxCOSD (Hihat et al., 2023), handled general convex capacity sets using adaptive cycles, achieving a static regret of $\tilde{O}(\sqrt{T/\mu})$ under the Uniformly Probably Positive Demand (UPPD) condition. However, this dependence on $1/\mu$ (where $\mu$ is the probability of a common demand shock) was suboptimal, and existing hidden-target methods were limited to linear capacity constraints due to reliance on product-wise "sell-out" analyses.

Methodology: Norm-Aligned Hidden-Target Projection
The authors propose that the simple principle of maintaining a hidden target $z_t$ and projecting it onto the feasible set $J_t$ is sufficient for general convex sets, provided the analysis utilizes a specific geometric framework.

1. Algorithm: The learner maintains a hidden target sequence $z_t \in Y$ generated by a base online learning algorithm (e.g., Online Gradient Descent). The implemented action is $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$, the projection of $z_t$ onto the feasible set $J_t$ measured in a specific norm $\|\cdot\|$.
2. Norm Alignment Principle: A critical methodological contribution is the requirement that the projection norm, the queue state measurement, and the target movement metric all use the same admissible norm $\|\cdot\|$. An admissible norm dominates the $\ell_\infty$ norm (i.e., $\|x\|_\infty \le \|x\|$).
3. Geometric Queue Reduction: The core of the analysis defines the "target-implementation gap" as $q_t = \|z_t - y_t\|$. The authors prove a pathwise geometric recursion (a Lindley queue):
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   where $d^{\min}_t = \min_i d_{t,i}$ is the common demand.
   • Interpretation: The gap evolves as a one-dimensional queue. Moving the hidden target ($z_{t+1} - z_t$) acts as "arrival," while common demand ($d^{\min}_t$) acts as "service."
   • Significance: This reduction transforms the complex, state-dependent feasibility problem into a standard OCO problem with an added switching cost. It avoids the need for product-wise accounting or linear constraints, which previously obstructed generalization to curved convex sets.

Key Contributions and Results

1. Optimal Static Regret for Convex Losses:
   By instantiating the base learner with Online Gradient Descent (OGD), the paper achieves a static regret of $\tilde{O}(\sqrt{T/\mu})$. This improves the best-known guarantee for general convex sets from $O(1/\mu)$ to $O(1/\sqrt{\mu})$. The authors prove a matching lower bound of $\Omega(\sqrt{T/\mu})$, establishing this rate as minimax optimal under UPPD.

2. Polylogarithmic Regret for Strongly Convex Losses:
   For $\alpha$-strongly convex losses, the same framework yields a regret bound of $\tilde{O}(\log(T/\mu))$. This resolves an open question regarding whether polylogarithmic regret is achievable in adversarial OIO with general capacity sets.

3. Improved Dynamic Regret:
   The method provides dynamic regret guarantees that depend on the Euclidean path variation $P_{T,2}$ of the comparator, rather than the $\ell_1$ variation $P_{T,1}$ used in prior hidden-target analyses. This removes an explicit $n^{1/4}$ factor and sharpens the bound for dense comparator movements. The authors utilize both standard OGD (for known variation) and Smoothed OGD (SOGD) (for unknown variation) to achieve these results.

4. Geometry-Sensitive Refinements via Mirror Descent:
   The framework is extended to Online Mirror Descent (OMD) with strongly convex regularizers. This allows the regret bounds to adapt to the specific geometry of the capacity set $Y$ and the dual norm of the gradients. For example, using entropic regularization on linear constraints improves the dependence on the dimension $n$ compared to Euclidean projection when gradients are coordinate-dense.

5. Dimension-Free Guarantees:
   The results are dimension-free in the standard OCO sense; the dimension $n$ enters only through problem parameters (like the diameter of $Y$ or gradient bounds) rather than as an explicit multiplicative factor (e.g., $n^{1/4}$).

Significance and Claims
The paper claims that the "hidden-target projection" principle, often viewed as an empirical heuristic or limited to linear constraints, is theoretically optimal for the full general-convex OIO model when paired with a "norm-aligned" geometric analysis.

• Theoretical Unification: The work unifies inventory control with standard OCO by showing that the physical feasibility constraint can be decoupled from the learning algorithm. The inventory layer acts as a queue clearing mechanism that imposes a switching cost on the base learner, without requiring the base learner to understand inventory dynamics.
• Resolution of Obstructions: It demonstrates that the obstructions preventing the extension of queueing analyses to general convex sets (specifically the lack of a conservation identity for product-wise errors) can be bypassed by measuring the state as a single geometric distance in an admissible norm.
• Empirical Validation: Experiments on synthetic data and real-world M5 forecasting competition data confirm that the proposed HT-OGD algorithm outperforms MaxCOSD and DDM (a product-wise method) in both linear and curved capacity settings, validating the theoretical improvements in regret bounds.

The authors conclude that this modular template—separating the learning of hidden targets from the enforcement of physical feasibility via norm-aligned queues—offers a robust framework for future online problems with state-dependent constraints.