Research map / Bandits and online learning / Online convex optimization and games
Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that hidden-target projection with a norm-aligned queue analysis is optimal for online inventory optimization on general bounded convex capacity sets under UPPD, giving sqrt(T/mu) static regret with matching lower bound, polylog strongly convex regret, and Euclidean dynamic regret.
Problem
Online inventory optimization (OIO) with inventory carryover on arbitrary bounded convex capacity sets under adversarial losses; prior guarantees depended on 1/mu, linear capacity, or extra n^{1/4} factors.
Approach
Maintain a hidden target from an online learner and implement its projection onto the feasible order-up-to set, measured in the same admissible norm; the norm-aligned distance from target to implementable set obeys a scalar Lindley queue recursion with target movement as arrival and common demand as service, reducing OIO to OCO with switching cost.</american_idea>
Key results
- HT-OGD achieves regret of order sqrt(T/mu) under UPPD on general convex sets, with a matching lower bound of c*sqrt(T/mu) for two-product linear instance.
- Under strongly convex losses, HT-OGD with 1/t stepsize gives O(log(T/delta) log T / mu) regret, the first polylogarithmic guarantee for general convex OIO.
- Experiments show HT-OGD attains lower regret than MaxCOSD and DDM in the Poisson linear-capacity setting and on the L2-ball capacity set.
Surprising findings
- Productwise (coordinatewise or l1) queue analyses cannot bridge to the implementation gap on general convex sets; a norm-misaligned queue yields exponential blow-up in the recursion.
Limitations
- Relies on uniformly probably positive demand, which can be very conservative when common clearing is rare in high-dimensional systems.
- Dimension-dependence hidden in mu, which can deteriorate with the number of products.
- Mirror-descent and SOGD instantiations require verification of local movement condition.
Experimental setup
Datasets: M5 forecasting competition demand traces synthetic Poisson demand synthetic power-law demand
Benchmarks: M5 forecasting demand traces synthetic Poisson inventory setting L2-ball capacity synthetic setting
Metrics: static regret dynamic regret
Baselines: MaxCOSD DDM HT (linear-capacity hidden-target method)
Builds on: MaxCOSD hidden-target OIO method DDM smoothed OGD online mirror descent
Closest papers by meaning
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.87)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.86)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.86)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.86)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.