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

Résumé Technique : Apprentissage de Cible Cachée Optimal pour l'Optimisation de l'Inventaire en Ligne sur des Ensembles Convexes Généraux

Formulation du Problème
Le papier traite de l'Optimisation de l'Inventaire en Ligne (OIO - Online Inventory Optimization), un cadre où un apprenant sélectionne des vecteurs de commande « jusqu'à » $y_t$ à partir d'un ensemble de capacité $Y \subseteq \mathbb{R}^n_+$ soumis à des contraintes physiques d'inventaire. Contrairement à l'Optimisation Convexe en Ligne (OCO) standard, l'OIO présente une « mémoire physique » : l'ensemble des actions réalisables à l'instant $t$, noté $J_t = Y \cap \{y \mid y \succeq x_t\}$, dépend de l'état actuel de l'inventaire $x_t$. L'inventaire est reporté, ce qui signifie qu'un apprenant ne peut pas simplement projeter un pas de gradient sur $Y$ si le vecteur résultant est inférieur au niveau de stock actuel. L'environnement choisit une demande adverse $d_t$ et des fonctions de perte $\ell_t$, et l'apprenant vise à minimiser le regret dynamique ou statique par rapport à une séquence de comparateurs.

Les travaux antérieurs, tels que MaxCOSD (Hihat et al., 2023), traitaient des ensembles de capacité convexes généraux en utilisant des cycles adaptatifs, atteignant un regret statique de $\tilde{O}(\sqrt{T/\mu})$ sous la condition de Demande Uniformément Probablement Positive (UPPD). Cependant, cette dépendance envers $1/\mu$ (où $\mu$ est la probabilité d'un choc de demande commun) était sous-optimale, et les méthodes existantes de cible cachée étaient limitées aux contraintes de capacité linéaires en raison de leur dépendance à des analyses de « rupture de stock » produit par produit.

Méthodologie : Projection de Cible Cachée Alignée sur la Norme
Les auteurs proposent que le principe simple consistant à maintenir une cible cachée $z_t$ et à la projeter sur l'ensemble réalisable $J_t$ est suffisant pour des ensembles convexes généraux, à condition que l'analyse utilise un cadre géométrique spécifique.

1. Algorithme : L'apprenant maintient une séquence de cibles cachées $z_t \in Y$ générée par un algorithme d'apprentissage en ligne de base (par exemple, la Descente de Gradient en Ligne - OGD). L'action implémentée est $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$, la projection de $z_t$ sur l'ensemble réalisable $J_t$ mesurée selon une norme spécifique $\|\cdot\|$.
2. Principe d'Alignement de Norme : Une contribution méthodologique critique est l'exigence que la norme de projection, la mesure de l'état de la file d'attente et la métrique de mouvement de la cible utilisent toutes la même norme admissible $\|\cdot\|$. Une norme admissible domine la norme $\ell_\infty$ (c'est-à-dire $\|x\|_\infty \le \|x\|$).
3. Réduction Géométrique de la File d'Attente : Le cœur de l'analyse définit l'« écart cible-implémentation » comme $q_t = \|z_t - y_t\|$. Les auteurs prouvent une récursion géométrique par chemin (une file d'attente de Lindley) :
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   où $d^{\min}_t = \min_i d_{t,i}$ est la demande commune.
   • Interprétation : L'écart évolue comme une file d'attente unidimensionnelle. Le mouvement de la cible cachée ($z_{t+1} - z_t$) agit comme une « arrivée », tandis que la demande commune ($d^{\min}_t$) agit comme un « service ».
   • Signification : Cette réduction transforme le problème complexe de faisabilité dépendante de l'état en un problème d'OCO standard avec un coût de commutation ajouté. Cela évite le recours à une comptabilité produit par produit ou à des contraintes linéaires, ce qui obstruait auparavant la généralisation aux ensembles convexes courbes.

Contributions Clés et Résultats

1. Regret Statique Optimal pour les Pertes Convexes :
   En instanciant l'apprenant de base avec la Descente de Gradient en Ligne (OGD), le papier atteint un regret statique de $\tilde{O}(\sqrt{T/\mu})$. Cela améliore la meilleure garantie connue pour les ensembles convexes généraux, passant de $O(1/\mu)$ à $O(1/\sqrt{\mu})$. Les auteurs prouvent une borne inférieure correspondante de $\Omega(\sqrt{T/\mu})$, établissant ce taux comme étant minimax optimal sous la condition UPPD.

2. Regret Polylogarithmique pour les Pertes Fortement Convexes :
   Pour les pertes $\alpha$-fortement convexes, le même cadre produit une borne de regret de $\tilde{O}(\log(T/\mu))$. Cela résout une question ouverte concernant la possibilité d'atteindre un regret polylogarithmique dans l'OIO adverse avec des ensembles de capacité généraux.

3. Regret Dynamique Amélioré :
   La méthode fournit des garanties de regret dynamique qui dépendent de la variation de chemin euclidienne $P_{T,2}$ du comparateur, plutôt que de sa variation $\ell_1$ $P_{T,1}$ utilisée dans les analyses de cible cachée antérieures. Cela élimine un facteur explicite $n^{1/4}$ et affine la borne pour les mouvements denses du comparateur. Les auteurs utilisent à la fois l'OGD standard (pour la variation connue) et l'OGD lissé (SOGD) (pour la variation inconnue) pour obtenir ces résultats.

4. Raffinements Sensibles à la Géométrie via la Descente de Miroir :
   Le cadre est étendu à la Descente de Miroir en Ligne (OMD) avec des régularisateurs fortement convexes. Cela permet aux bornes de regret de s'adapter à la géométrie spécifique de l'ensemble de capacité $Y$ et à la norme duale des gradients. Par exemple, l'utilisation d'une régularisation entropique sur les contraintes linéaires améliore la dépendance vis-à-vis de la dimension $n$ par rapport à la projection euclidienne lorsque les gradients sont denses par coordonnée.

5. Garanties Indépendantes de la Dimension :
   Les résultats sont indépendants de la dimension au sens de l'OCO standard ; la dimension $n$ n'intervient qu'à travers les paramètres du problème (comme le diamètre de $Y$ ou les bornes de gradient) plutôt que comme un facteur multiplicatif explicite (par exemple, $n^{1/4}$).

Signification et Revendications
Le papier affirme que le principe de « projection de cible cachée », souvent considéré comme une heuristique empirique ou limité aux contraintes linéaires, est théoriquement optimal pour le modèle complet d'OIO à convexité générale lorsqu'il est couplé à une analyse géométrique « alignée sur la norme ».

• Unification Théorique : Ce travail unifie le contrôle des stocks avec l'OCO standard en montrant que la contrainte de faisabilité physique peut être découplée de l'algorithme d'apprentissage. La couche d'inventaire agit comme un mécanisme de vidage de file d'attente qui impose un coût de commutation sur l'apprenseur de base, sans nécessiter que l'apprenseur comprenne la dynamique de l'inventaire.
• Résolution des Obstructions : Il démontre que les obstructions empêchant l'extension des analyses de file d'attente aux ensembles convexes généraux (spécifiquement l'absence d'une identité de conservation pour les erreurs produit par produit) peuvent être contournées en mesurant l'état comme une distance géométrique unique dans une norme admissible.
• Validation Empirique : Des expériences sur des données synthétiques et des données réelles de la compétition de prévision M5 confirment que l'algorithme HT-OGD proposé surpasse MaxCOSD et DDM (une méthode produit par produit) tant dans les contextes de capacité linéaires que courbes, validant les améliorations théoriques des bornes de regret.

Les auteurs concluent que ce modèle modulaire — séparant l'apprentissage des cibles cachées de l'application de la faisabilité physique via des files d'attente alignées sur la norme — offre un cadre robuste pour les futurs problèmes en ligne avec des contraintes dépendant de l'état.