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

Technische Zusammenfassung: Optimales Lernen verborgener Ziele für die Online-Inventaroptimierung auf allgemeinen konvexen Mengen

Problemformulierung
Das Paper adressiert die Online-Inventaroptimierung (Online Inventory Optimization, OIO), ein Szenario, in dem ein Lernender Order-up-to-Vektoren $y_t$ aus einer Kapazitätsmenge $Y \subseteq \mathbb{R}^n_+$ wählt, die unter Berücksichtigung physischer Inventarbeschränkungen steht. Im Gegensatz zur Standard-Online-Konvexen-Optimierung (OCO) weist OIO ein „physisches Gedächtnis“ auf: Die zulässige Aktionsmenge zum Zeitpunkt $t$, bezeichnet als $J_t = Y \cap \{y \mid y \succeq x_t\}$, hängt vom aktuellen Inventarzustand $x_t$ ab. Das Inventar wird fortgeführt, was bedeutet, dass ein Lernender nicht einfach einen Gradientenschritt auf $Y$ projizieren kann, wenn der resultierende Vektor unter dem aktuellen Lagerbestand liegt. Die Umgebung wählt eine adversarielle Nachfrage $d_t$ und Verlustfunktionen $\ell_t$, und der Lernende zielt darauf ab, den dynamischen oder statischen Regret gegenüber einer Vergleichssequenz zu minimieren.

Vorarbeiten wie MaxCOSD (Hihat et al., 2023) behandelten allgemeine konvexe Kapazitätsmengen mittels adaptiver Zyklen und erreichten einen statischen Regret von $\tilde{O}(\sqrt{T/\mu})$ unter der Bedingung der „Uniformly Probably Positive Demand“ (UPPD). Diese Abhängigkeit von $1/\mu$ (wobei $\mu$ die Wahrscheinlichkeit eines gemeinsamen Nachfrageschocks ist) war jedoch suboptimal, und bestehende Hidden-Target-Methoden waren aufgrund der Abhängigkeit von produktweisen „Sell-out“-Analysen auf lineare Kapazitätsbeschränkungen beschränkt.

Methodik: Norm-ausgerichtete Hidden-Target-Projektion
Die Autoren schlagen vor, dass das einfache Prinzip der Aufrechterhaltung eines verborgenen Ziels $z_t$ und dessen Projektion auf die zulässige Menge $J_t$ für allgemeine konvexe Mengen ausreicht, sofern die Analyse ein spezifisches geometrisches Framework nutzt.

1. Algorithmus: Der Lernende pflegt eine verborgene Zielsequenz $z_t \in Y$, die durch einen Basis-Online-Lernalgorithmus (z. B. Online Gradient Descent) generiert wird. Die implementierte Aktion ist $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$, die Projektion von $z_t$ auf die zulässige Menge $J_t$, gemessen in einer spezifischen Norm $\|\cdot\|$.
2. Norm-Ausrichtungsprinzip: Ein entscheidender methodischer Beitrag ist die Anforderung, dass die Projektionsnorm, die Warteschlangenzustandsmessung und die Metrik der Zielbewegung alle dieselbe zulässige Norm $\|\cdot\|$ verwenden. Eine zulässige Norm dominiert die $\ell_\infty$-Norm (d. h. $\|x\|_\infty \le \|x\|$).
3. Geometrische Warteschlangenreduktion: Der Kern der Analyse definiert die „Ziel-Implementierungs-Lücke“ als $q_t = \|z_t - y_t\|$. Die Autoren beweisen eine pfadweise geometrische Rekursion (eine Lindley-Warteschlange):
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   wobei $d^{\min}_t = \min_i d_{t,i}$ die gemeinsame Nachfrage ist.
   • Interpretation: Die Lücke entwickelt sich wie eine eindimensionale Warteschlange. Die Bewegung des verborgenen Ziels ($z_{t+1} - z_t$) wirkt als „Ankunft“, während die gemeinsame Nachfrage ($d^{\min}_t$) als „Bedienung“ fungiert.
   • Bedeutung: Diese Reduktion transformiert das komplexe, zustandsabhängige Zulässigkeitsproblem in ein Standard-OCO-Problem mit einem zusätzlichen Schaltkostenfaktor. Dies vermeidet die Notwendigkeit produktweiser Buchhaltung oder linearer Beschränkungen, was zuvor die Verallgemeinerung auf gekrümmte konvexe Mengen erschwert hatte.

Zentrale Beiträge und Ergebnisse

1. Optimaler statischer Regret für konvexe Verluste:
   Durch die Instanziierung des Basis-Learners mit Online Gradient Descent (OGD) erreicht das Paper einen statischen Regret von $\tilde{O}(\sqrt{T/\mu})$. Dies verbessert die bisher beste bekannte Garantie für allgemeine konvexe Mengen von $O(1/\mu)$ auf $O(1/\sqrt{\mu})$. Die Autoren beweisen einen passenden unteren Grenzwert von $\Omega(\sqrt{T/\mu})$ und etablieren damit diese Rate als minimax-optimal unter UPPD.

2. Polylogarithmischer Regret für stark konvexe Verluste:
   Für $\alpha$-stark konvexe Verluste liefert dasselbe Framework eine Regret-Schranke von $\tilde{O}(\log(T/\mu))$. Dies löst die offene Frage, ob ein polylogarithmischer Regret in adversariellem OIO mit allgemeinen Kapazitätsmengen erreichbar ist.

3. Verbesserter dynamischer Regret:
   Die Methode liefert Garantien für den dynamischen Regret, die von der euklidischen Pfadvariation $P_{T,2}$ des Vergleichers abhängen, anstatt von der $\ell_1$-Variation $P_{T,1}$, die in früheren Hidden-Target-Analysen verwendet wurde. Dies entfernt einen expliziten $n^{1/4}$-Faktor und schärft die Schranke für dichte Bewegungen des Vergleichers. Die Autoren nutzen sowohl Standard-OGD (für bekannte Variation) als auch Smoothed OGD (SOGD) (für unbekannte Variation), um diese Ergebnisse zu erzielen.

4. Geometrie-sensitive Verfeinerungen via Mirror Descent:
   Das Framework wird auf Online Mirror Descent (OMD) mit stark konvexen Regularisatoren erweitert. Dies ermöglicht es, dass die Regret-Schranken auf die spezifische Geometrie der Kapazitätsmenge $Y$ und die Dualnorm der Gradienten abgestimmt sind. Beispielsweise verbessert die Verwendung von entropischer Regularisierung auf linearen Beschränkungen die Abhängigkeit von der Dimension $n$ im Vergleich zur euklidischen Projektion, wenn die Gradienten koordinaten-dicht sind.

5. Dimensionsfreie Garantien:
   Die Ergebnisse sind im Sinne der Standard-OCO dimensionsfrei; die Dimension $n$ tritt nur durch Problemparameter (wie den Durchmesser von $Y$ oder Gradientenobergrenzen) auf, anstatt als expliziter multiplikativer Faktor (z. B. $n^{1/4}$).

Bedeutung und Ansprüche
Das Paper behauptet, dass das „Hidden-Target-Projektions“-Prinzip, das oft als empirische Heuristik oder auf lineare Beschränkungen begrenzt angesehen wird, für das volle allgemeine konvexe OIO-Modell optimal ist, wenn es mit einer „norm-ausgerichteten“ geometrischen Analyse kombiniert wird.

• Theoretische Vereinheitlichung: Die Arbeit vereinheitlicht die Inventarkontrolle mit Standard-OCO, indem sie zeigt, dass die physische Zulässigkeitsbeschränkung vom Basis-Lernalgorithmus entkoppelt werden kann. Die Inventarschicht fungiert als Warteschlangen-Bereinigungsmechanismus, der eine Schaltkostenkomponente auf den Basis-Lerner auferlegt, ohne dass der Basis-Lerner die Inventardynamik verstehen muss.
• Auflösung von Hindernissen: Es zeigt, dass die Hindernisse, die die Erweiterung von Warteschlangen-Analysen auf allgemeine konvexe Mengen verhinderten (speziell das Fehlen einer Erhaltungsidentität für produktweise Fehler), umgangen werden können, indem der Zustand als ein einzelner geometrischer Abstand in einer zulässigen Norm gemessen wird.
• Empirische Validierung: Experimente mit synthetischen Daten und realen M5-Forecasting-Wettbewerbsdaten bestätigen, dass der vorgeschlagene HT-OGD-Algorithmus MaxCOSD und DDM (eine produktweise Methode) sowohl in linearen als auch in gekrümmten Kapazitätssettings hinsichtlich des Regret übertrifft, was die theoretischen Verbesserungen der Regret-Schranken validiert.

Die Autoren kommen zu dem Schluss, dass dieses modulare Template – die Trennung des Lernens verborgener Ziele von der Durchsetzung der physischen Zulässigkeit via norm-ausgerichteter Warteschlangen – einen robusten Rahmen für zukünftige Online-Probleme mit zustandsabhängigen Beschränkungen bietet.