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

Sintesi Tecnica: Apprendimento Ottimale di Target Nascosto per l'Ottimizzazione dell'Inventario Online su Insiemi Convessi Generali

Formulazione del Problema
Il documento affronta l'Ottimizzazione dell'Inventario Online (OIO), un contesto in cui un apprendente seleziona vettori di riordino $y_t$ da un insieme di capacità $Y \subseteq \mathbb{R}^n_+$ soggetto a vincoli fisici di inventario. A differenza della standard Online Convex Optimization (OCO), l'OIO presenta una "memoria fisica": l'insieme delle azioni ammissibili al tempo $t$, denotato $J_t = Y \cap \{y \mid y \succeq x_t\}$, dipende dallo stato attuale dell'inventario $x_t$. L'inventario si accumula, il che significa che un apprendente non può semplicemente proiettare un passo di gradiente su $Y$ se il vettore risultante è inferiore al livello di scorta attuale. L'ambiente sceglie la domanda avversaria $d_t$ e le funzioni di perdita $\ell_t$, e l'apprendente mira a minimizzare il regret dinamico o statico rispetto a una sequenza di comparatori.

Il lavoro precedente, come MaxCOSD (Hihat et al., 2023), gestiva insiemi di capacità convessi generali utilizzando cicli adattivi, raggiungendo un regret statico di $\tilde{O}(\sqrt{T/\mu})$ sotto la condizione di Uniformly Probably Positive Demand (UPPD). Tuttavia, questa dipendenza da $1/\mu$ (dove $\mu$ è la probabilità di uno shock comune della domanda) era subottimale, e i metodi esistenti di hidden-target erano limitati a vincoli di capacità lineari a causa della dipendenza da analisi prodotto per prodotto ("sell-out").

Metodologia: Proiezione di Hidden-Target Allineata alla Norma
Gli autori propongono che il semplice principio di mantenere un target nascosto $z_t$ e proiettarlo sull'insieme ammissibile $J_t$ sia sufficiente per insiemi convessi generali, a condizione che l'analisi utilizzi un framework geometrico specifico.

1. Algoritmo: L'apprendente mantiene una sequenza di target nascosti $z_t \in Y$ generata da un algoritmo di apprendimento online di base (ad esempio, Online Gradient Descent). L'azione implementata è $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$, ovvero la proiezione di $z_t$ sull'insieme ammissibile $J_t$ misurata in una specifica norma $\|\cdot\|$.
2. Principio di Allineamento della Norma: Un contributo metodologico critico è il requisito che la norma di proiezione, la misurazione dello stato della coda e la metrica di movimento del target utilizzino tutte la stessa norma ammissibile $\|\cdot\|$. Una norma ammissibile domina la norma $\ell_\infty$ (ovvero, $\|x\|_\infty \le \|x\|$).
3. Riduzione Geometrica della Coda: Il nucleo dell'analisi definisce il "gap tra target e implementazione" come $q_t = \|z_t - y_t\|$. Gli autori dimostrano una ricorsione geometrica pathwise (una coda di Lindley):
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   dove $d^{\min}_t = \min_i d_{t,i}$ è la domanda comune.
   • Interpretazione: Il gap evolve come una coda monodimensionale. Il movimento del target nascosto ($z_{t+1} - z_t$) agisce come "arrivo", mentre la domanda comune ($d^{\min}_t$) agisce come "servizio".
   • Significato: Questa riduzione trasforma il complesso problema di ammissibilità dipendente dallo stato in un problema standard di OCO con un costo di commutazione (switching cost) aggiuntivo. Evita la necessità di contabilità prodotto per prodotto o vincoli lineari, che precedentemente ostacolavano la generalizzazione a insiemi convessi curvi.

Contributi Chiave e Risultati

1. Regret Statico Ottimale per Perdite Convesse:
   Istanziando il base learner con Online Gradient Descent (OGD), il documento raggiunge un regret statico di $\tilde{O}(\sqrt{T/\mu})$. Questo migliora la migliore garanzia nota per insiemi convessi generali da $O(1/\mu)$ a $O(1/\sqrt{\mu})$. Gli autori dimostrano un lower bound corrispondente di $\Omega(\sqrt{T/\mu})$, stabilendo questo tasso come minimax ottimale sotto UPPD.

2. Regret Polilogaritmico per Perdite Fortemente Convesse:
   Per perdite $\alpha$-fortemente convesse, lo stesso framework produce un limite di regret di $\tilde{O}(\log(T/\mu))$. Ciò risolve una questione aperta sul fatto se il regret polilogaritmico sia raggiungibile in OIO avversariale con insiemi di capacità convessi generali.

3. Regret Dinamico Migliorato:
   Il metodo fornisce garanzie di regret dinamico che dipendono dalla variazione di percorso euclidea $P_{T,2}$ del comparatore, piuttosto che dalla variazione $\ell_1$ $P_{T,1}$ usata nelle analisi precedenti di hidden-target. Ciò rimuove un fattore esplicito $n^{1/4}$ e rende più stringente il limite per movimenti densi del comparatore. Gli autori utilizzano sia l'OGD standard (per variazione nota) che il Smoothed OGD (SOGD) (per variazione ignota) per ottenere questi risultati.

4. Raffinamenti Sensibili alla Geometria tramite Mirror Descent:
   Il framework è esteso all'Online Mirror Descent (OMD) con regolarizzatori fortemente convessi. Ciò consente ai limiti di regret di adattarsi alla specifica geometria dell'insieme di capacità $Y$ e alla norma duale dei gradienti. Ad esempio, l'uso della regolarizzazione entropica su vincoli lineari migliora la dipendenza dalla dimensione $n$ rispetto alla proiezione euclidea quando i gradienti sono densi nelle coordinate.

5. Garanzie Indipendenti dalla Dimensione:
   I risultati sono indipendenti dalla dimensione nel senso standard di OCO; la dimensione $n$ entra solo attraverso i parametri del problema (come il diametro di $Y$ o i limiti dei gradienti) piuttosto che come un fattore moltiplicativo esplicito (ad esempio, $n^{1/4}$).

Significato e Rivendicazioni
Il documento sostiene che il principio di "proiezione del target nascosto", spesso visto come un euristica empirica o limitato ai vincoli lineari, è teoricamente ottimale per il modello completo di OIO convesso generale quando accoppiato con un'analisi geometrica "allineata alla norma".

• Unificazione Teorica: Il lavoro unifica il controllo dell'inventario con la standard OCO mostrando che il vincolo di ammissibilità fisica può essere disaccoppiato dall'algoritmo di apprendimento. Lo strato dell'inventario agisce come un meccanismo di svuotamento della coda che impone un costo di commutazione al base learner, senza richiedere che il base learner comprenda la dinamica dell'inventario.
• Risoluzione degli Ostacoli: Dimostra che gli ostacoli che impedivano l'estensione delle analisi di code a insiemi convessi generali (specificamente la mancanza di un'identità di conservazione per gli errori prodotto per prodotto) possono essere superati misurando lo stato come una singola distanza geometrica in una norma ammissibile.
• Validazione Empirica: Gli esperimenti su dati sintetici e dati reali della competizione di forecasting M5 confermano che l'algoritmo HT-OGD proposto supera MaxCOSD e DDM (un metodo prodotto per prodotto) sia in contesti di capacità lineari che curvi, validando i miglioramenti teorici nei limiti di regret.

Gli autori concludono che questo template modulare — separare l'apprendimento dei target nascosti dall'imposizione della ammissibilità fisica tramite code allineate alla norma — offre un framework robusto per futuri problemi online con vincoli dipendenti dallo stato.