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

Technische Samenvatting: Optimale Hidden-Target Learning voor Online Inventarisoptimalisatie op Algemene Convexe Sets

Probleemformulering
Het artikel behandelt Online Inventarisoptimalisatie (OIO), een setting waarin een leerder order-up-to vectoren $y_t$ selecteert uit een capaciteitsset $Y \subseteq \mathbb{R}^n_+$ onderhevig aan fysieke voorraadbeperkingen. In tegenstelling tot standaard Online Convex Optimization (OCO), kenmerkt OIO zich door "fysiek geheugen": de haalbare actieset op tijdstip $t$, aangeduid als $J_t = Y \cap \{y \mid y \succeq x_t\}$, hangt af van de huidige voorraadstatus $x_t$. Voorraad wordt overgedragen, wat betekent dat een leerder niet simpelweg een gradiëntstap op $Y$ kan projecteren als de resulterende vector lager is dan het huidige voorraadniveau. De omgeving kiest een adversariële vraag $d_t$ en verliesfuncties $\ell_t$, en de leerder streeft naar het minimaliseren van dynamische of statische regret tegenover een comparator-sequentie.

Eerder werk, zoals MaxCOSD (Hihat et al., 2023), behandelde algemene convexe capaciteitssets met behulp van adaptieve cycli, waarbij een statische regret van $\tilde{O}(\sqrt{T/\mu})$ werd bereikt onder de Uniformly Probably Positive Demand (UPPD) conditie. Deze afhankelijkheid van $1/\mu$ (waarbij $\mu$ de waarschijnlijkheid van een gemeenschappelijke vraagshock is) was echter suboptimaal, en bestaande hidden-target methoden waren beperkt tot lineaire capaciteitsbeperkingen vanwege de afhankelijkheid van productgewijze "sell-out" analyses.

Methodologie: Norm-Aligned Hidden-Target Projectie
De auteurs stellen voor dat het eenvoudige principe van het handhaven van een verborgen doelwit $z_t$ en het projecteren ervan op de haalbare set $J_t$ voldoende is voor algemene convexe sets, mits de analyse gebruikmaakt van een specifieke geometrische framework.

1. Algoritme: De leerder onderhoudt een verborgen doelwit-sequentie $z_t \in Y$ gegenereerd door een basis online leeralgoritme (bijv. Online Gradient Descent). De geïmplementeerde actie is $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$, de projectie van $z_t$ op de haalbare set $J_t$, gemeten in een specifieke norm $\|\cdot\|$.
2. Norm Alignment Principe: Een cruciale methodologische bijdrage is de vereiste dat de projectienorm, de wachtrijstatus-meting en de doelwitbewegingsmetriek allemaal dezelfde toegestane norm $\|\cdot\|$ gebruiken. Een toegestane norm domineert de $\ell_\infty$ norm (d.w.z. $\|x\|_\infty \le \|x\|$).
3. Geometrische Wachtrij Reductie: De kern van de analyse definieert de "target-implementation gap" als $q_t = \|z_t - y_t\|$. De auteurs bewijzen een padwijze geometrische recursie (een Lindley-wachtrij):
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   waarbij $d^{\min}_t = \min_i d_{t,i}$ de gemeenschappelijke vraag is.
   • Interpretatie: De gap evolueert als een één-dimensionale wachtrij. Het bewegen van het verborgen doelwit ($z_{t+1} - z_t$) fungeert als "aankomst", terwijl de gemeenschappelijke vraag ($d^{\min}_t$) fungeert als "service".
   • Significantie: Deze reductie transformeert het complexe, statusafhankelijke haalbaarheidsprobleem in een standaard OCO-probleem met een toegevoegde switching cost. Dit vermijdt de noodzaak voor productgewijze boekhouding of lineaire beperkingen, wat voorheen de generalisatie naar gekromde convexe sets belemmerde.

Belangrijkste Bijdragen en Resultaten

1. Optimale Statische Regret voor Convexe Verliezen:
   Door de basisleerder te instantiëren met Online Gradient Descent (OGD), bereikt het artikel een statische regret van $\tilde{O}(\sqrt{T/\mu})$. Dit verbetert de best bekende garantie voor algemene convexe sets van $O(1/\mu)$ naar $O(1/\sqrt{\mu})$. De auteurs bewijzen een bijbehorende lower bound van $\Omega(\sqrt{T/\mu})$, waarmee zij vaststellen dat dit tempo minimax optimaal is onder UPPD.

2. Polylogarithmische Regret voor Sterk Convexe Verliezen:
   Voor $\alpha$-sterk convexe verliezen levert hetzelfde framework een regret bound van $\tilde{O}(\log(T/\mu))$. Dit lost een openstaande vraag op over de vraag of polylogarithmische regret haalbaar is in adversariële OIO met algemene capaciteitssets.

3. Verbeterde Dynamische Regret:
   De methode biedt dynamische regret garanties die afhangen van de Euclidische padvariatie $P_{T,2}$ van de comparator, in plaats van de $\ell_1$ variatie $P_{T,1}$ die in eerdere hidden-target analyses werd gebruikt. Dit verwijdert een expliciete $n^{1/4}$ factor en verscherpt de bound voor dichte comparator-bewegingen. De auteurs maken gebruik van zowel standaard OGD (voor bekende variatie) als Smoothed OGD (SOGD) (voor onbekende variatie) om deze resultaten te bereiken.

4. Geometrie-gevoelige Verfijningen via Mirror Descent:
   Het framework wordt uitgebreid naar Online Mirror Descent (OMD) met sterk convexe regularisaties. Dit stelt de regret bounds in staat om aan te passen aan de specifieke geometrie van de capaciteitsset $Y$ en de duale norm van de gradiënten. Bijvoorbeeld, het gebruik van entropische regularisatie op lineaire beperkingen verbetert de afhankelijkheid van de dimensie $n$ vergeleken met Euclidische projectie wanneer gradiënten coördinaat-dens zijn.

5. Dimensievrije Garanties:
   De resultaten zijn dimensievrij in de standaard OCO-zin; de dimensie $n$ komt alleen binnen via probleemparameters (zoals de diameter van $Y$ of gradiëntbounds) in plaats van als een expliciete multiplicatieve factor (bijv. $n^{1/4}$).

Significantie en Claims
Het artikel claimt dat het "hidden-target projection" principe, dat vaak wordt gezien als een empirische heuristiek of beperkt is tot lineaire beperkingen, theoretisch optimaal is voor de volledige algemene-convexe OIO-modellen wanneer het gepaard gaat met een "norm-aligned" geometrische analyse.

• Theoretische Unificatie: Het werk unificeert inventariscontrole met standaard OCO door aan te tonen dat de fysieke haalbaarheidsbeperking kan worden ontkoppeld van het leeralgoritme. De inventarislaag fungeert als een wachtrij-clearing mechanisme dat een switching cost oplegt aan de basisleerder, zonder dat de basisleerder de inventarisdynamiek hoeft te begrijpen.
• Resolutie van Obstakels: Het demonstreert dat de obstructies die analyses van wachtrijen naar algemene convexe sets verhinderden (specifiek het gebrek aan een behoudsidentiteit voor productgewijze fouten), kunnen worden omzeild door de status te meten als een enkele geometrische afstand in een toegestane norm.
• Empirische Validatie: Experimenten op synthetische data en real-world M5 forecasting competition data bevestigen dat het voorgestelde HT-OGD algoritme MaxCOSD en DDM (een productgewijze methode) overtreft in zowel lineaire als gekromde capaciteitssettings, wat de theoretische verbeteringen in regret bounds valideert.

De auteurs concluderen dat dit modulaire sjabloon — het scheiden van het leren van verborgen targets van het afdwingen van fysieke haalbaarheid via norm-aligned wachtrijen — een robuust framework biedt voor toekomstige online problemen met statusafhankelijke beperkingen.