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

Paper: 2606.14679 Authors: Anthony Pineci, Yunzong Xu Categories: cs.LG, eess.SY, math.OC, stat.ML

The Gap

Online inventory optimization (OIO) sits at the intersection of online convex optimization (OCO) and inventory theory. The twist that makes it hard: because inventory carries over across periods, the feasible action set at time t depends on your previous actions and realized demand. This is online convex optimization with memory.

Prior work handled two cases separately. Stochastic inventory learning gives optimal policies under strong distributional assumptions (e.g., i.i.d. demand with known distribution family). On the OCO side, the only general result for OIO with memory was a recent paper by Zhang et al. (2022) that achieved regret inversely proportional to the common-demand probability p — i.e., $O(1/p)$ — but only for a single linear capacity constraint. For general convex capacity sets (e.g., warehouse volume + weight constraints, or budget + storage limits), the best known guarantee was even worse, and no matching lower bound existed.

The gap is twofold: (1) Can we achieve regret that scales like $O(1/\sqrt\{p\})$ — the natural rate you’d expect from online learning with a fixed feasible set? (2) Can the algorithm handle arbitrary bounded convex capacity sets, not just a single linear constraint? This paper answers both affirmatively.

[Problem: Online Inventory Optimization with memory -- action set depends on past]
    |
    v
[Current state: Zhang et al. O(1/p) for single linear capacity only]
[Convex sets: no optimal guarantee; no matching lower bound]
    |
    v
[Key insight: Hidden-target learning + norm alignment reduces to 1D queue]
    |
    v
[Result: O(1/sqrt{p}) regret for general convex sets, matching lower bound]
[Also: first polylog regret for strongly convex losses; first dynamic regret]
    |
    v
[Evidence: synthetic & real inventory data confirm theory]
    |
    v
[Conclusion: The hidden-target principle is optimal for OIO on general convex sets]

The Increment

One sentence: Before this paper, the best regret for online inventory optimization on general convex capacity sets was $O(1/p)$ (inverse probability); after, it is $O(1/\sqrt\{p\})$ with a matching lower bound — plus the first polylogarithmic guarantee for strongly convex losses and the first dynamic regret bound.

Core Mechanism

The method builds on a natural principle used in stochastic inventory theory: maintain a hidden target chosen by an online learner (like online gradient descent), and at each time step implement the projection of that target onto the currently feasible “order-up-to” set. The authors prove that this simple principle is optimal for any bounded convex capacity set, not just a single linear constraint.

The engine is a new norm alignment idea. They equip the action space with a norm that matches the projection operator (specifically, the same norm used in the projection). This is critical: under the aligned norm, the distance from the hidden target to the feasible set evolves as a scalar queue. Target movement acts as the arrival process, and the common demand acts as service. The high-dimensional coupling between actions and inventory dynamics collapses to a one-dimensional queue control problem. This reduction lets them port all the regret analysis tools from OCO and queueing theory.

[Base Learner (e.g., OGD)] --- produces target t_k [unconstrained]
     |
     v
[Feasible Set S_k] = { x | x >= 0, capacity set applied after inventory carryover }
     |
     v
[Action x_k] = Project_{S_k}(t_k)  [closest point in S_k to t_k, under aligned norm]
     |
     v
[Cost incurred; demand realized; inventory updates]
     |
     v
[Queue: d_k = distance(t_k, S_k)] --- evolves as: d_{k+1} = max( d_k + (t_{k+1}-t_k) - demand_k, 0 )

Structural metaphor: Imagine a librarian who each day must place books on shelves, but the shelves’ positions depend on which books were placed yesterday (some shelves retract). The librarian picks an ideal shelf arrangement (the hidden target), but then must physically place books as close as possible to that ideal given the current shelf layout (the projection). The distance between ideal and actual placement is a backlog: if the ideal arrangement moves quickly, backlog grows; if a “common book return” (demand) arrives, some shelves reset and backlog shrinks. The librarian’s decision reduces to how far ahead she can push the ideal arrangement relative to the return rate — a one-dimensional slacking problem. The norm alignment guarantees that this backlog evolves exactly like a queue, no matter how complicated the shelves are.

Key Concepts

• Hidden-Target Learning: Instead of directly choosing an action from a time-varying feasible set, choose an unrestricted *target from the whole action space, then project it onto the current set. This decouples the learning (which adapts to costs) from the feasibility mechanics (which enforce constraints). The hidden target can be updated by any online algorithm; the projection handles the changing constraints. This is powerful because the learner never needs to know the exact shape of the feasible set ahead of time — it only needs to be able to project onto it.

• Norm Alignment: The distance between points in the action space can be measured with many different norms. The authors insist on using the *same norm for measuring distance and for performing the projection. This means the projection operator is non-expansive in that norm: the distance between two projected points is at most the distance between the original points. This seemingly small adjustment prevents the distance from the target to the feasible set from blowing up due to projection artifacts, and instead it evolves cleanly like a scalar queue.

• Queue Reduction: After norm alignment, the vector-valued state (inventory levels at each product) collapses to a single scalar: the distance from the target to the feasible set. The dynamics become $d_{t+1} = \max(d_t + \Delta_t - D_t, 0)$ where $\Delta_t$ is the drift of the target (controlled by the learner) and $D_t$ is the common demand (random). This is a classic discrete-time queue; the learner’s regret can be bounded using queueing arguments (arrival rate vs service rate). This reduction is what allows the analysis to extend to *any convex capacity set, whereas prior work handled each coordinate separately.

Framework Shift

Before (productwise decomposition):                After (norm alignment + queue reduction):
                                                   
Dimension 1:                                       All dimensions:
  inventory --- demand --- projection               hidden target t_k
    |    |    |    |       |                          |
    v    v    v    v       v                          v
  [analyze coordinate interactions]               feasible set S_k
                                                    |
Dimension 2:                                        v
  ...                                              distance d_k = dist(t_k, S_k)
                                                    |
                                                    v
                                                  1D queue dynamics: d_{k+1} = max(d_k + drift - demand, 0)

One sentence: From productwise decomposition (analyzing each inventory dimension separately, which fails for general convex sets) to a norm-aligned queue reduction that treats the entire system as a single scalar backlog — collapsing high-dimensional coupling into a 1D control problem.

Expert Assessment

Problem choice: Real gap. Online inventory optimization is relevant (supply chains, cloud resource allocation, etc.). The limitation to single linear capacity was a practical pain; general convex sets are common. The field needed a principled optimal bound, and this paper delivers it. Not manufactured.

Method maturity: Elegant insight — norm alignment plus queue reduction is the kind of idea that seems obvious in hindsight but takes a smart person to see. The technical work is heavy (proofs involve martingale bounds and queueing theory), but the core mechanism is simple enough to explain over coffee. No brute force; it’s clever.

Experimental integrity: The synthetic and real-world experiments (using retail demand data) compare against the prior best algorithms (e.g., Zhang et al.). The results show that their method achieves lower regret and adapts to varying convex constraints. No red flags — baselines are sensible, and the experiments validate both the regret rate and the queue reduction intuition. The paper also provides a matching lower bound, which is gold standard.

Writing quality: The abstract and introduction are crisp. The main technical sections are dense but well-organized. I’d rewrite the norm alignment definition section — it could use a simple concrete example (e.g., Euclidean vs Mahalanobis) to build intuition before the heavy analysis.

Verdict: strong accept — clean theory with matching lower bounds, a simple elegant mechanism, and immediate practical relevance.

Takeaways

• Hidden-target learning is a recipe for any online problem with time-varying feasible sets that depend on past actions: pick an unrestricted learning algorithm, then project onto the current feasible set. The projection becomes a separate module.
• Norm alignment is a design principle: if you want a distance metric to behave nicely under projections, use the same norm for both projection and measurement. This can simplify proof techniques in other constrained online learning problems.
• Queue reduction is a new analytical lens for online optimization with memory: the regret bound reduces to controlling the drift of a one-dimensional queue. This may transfer to other problems where the state space is high-dimensional but the constraint dynamics are linear (e.g., portfolio optimization with transaction costs).
• Practitioners can steal the specific algorithmic template: use OGD to produce a target, maintain a projection oracle for the capacity set, and implement the projection. The theory guarantees optimal regret without tuning per constraint shape.