Online Inventory Problems: Beyond the i.i.d. Setting with Online Convex Optimization

Cet article propose l'algorithme MaxCOSD, une méthode d'optimisation convexe en ligne qui garantit la minimisation des pertes cumulées dans des problèmes de gestion de stocks multi-produits avec des dynamiques d'état et des demandes non i.i.d., sous réserve d'hypothèses de non-dégénérescence nécessaires à l'apprentissage.

L'essentiel

🛒 Le Dilemme du Gérant de Magasin : Trop ou Pas Assez ?

Imaginez que vous êtes le gérant d'une grande chaîne de magasins. Chaque matin, vous devez décider combien de produits commander pour la journée. C'est un jeu de l'équilibre parfait :

• Si vous commandez trop, vous payez des frais de stockage et les produits risquent de pourrir (s'ils sont frais) ou de devenir obsolètes.
• Si vous commandez trop peu, vous ratez des ventes, les clients partent mécontents et vous perdez de l'argent.

Le problème, c'est que vous ne savez jamais exactement combien de clients vont venir. Dans le passé, les experts disaient : "Supposons que les clients arrivent de manière totalement aléatoire et identique chaque jour" (comme des dés qu'on lance). Mais dans la vraie vie, ce n'est pas vrai ! Parfois, il y a une vague de froid (plus de ventes de manteaux), parfois un jour férié, parfois une grève. Les demandes sont imprévisibles et changeantes.

🚫 Le Problème des Anciennes Méthodes

Les anciennes méthodes d'intelligence artificielle pour gérer ces stocks fonctionnaient bien... tant que les clients se comportaient comme des robots prévisibles. Dès qu'on introduisait la réalité (des demandes qui changent, des produits qui périssent, des retards), ces méthodes s'effondraient ou ne donnaient aucune garantie de réussite. C'était comme essayer de conduire une voiture avec une carte routière de 1950 dans une ville où les rues changent tous les matins.

✨ La Solution : MaxCOSD (Le Chef de Cuisine Intuitif)

Les auteurs de ce papier (Massil Hihat et son équipe) ont créé un nouvel algorithme appelé MaxCOSD. Pour le comprendre, utilisons une analogie culinaire.

Imaginez un Chef de Cuisine qui doit préparer des plats pour le service du soir.

1. L'approche classique (OSD) : Le chef ajuste sa recette à chaque seconde, même si le client n'a pas encore commandé. C'est trop rapide, il se trompe souvent.
2. L'approche précédente (CUP) : Le chef ne change sa recette que s'il n'a plus de stock du tout (panne). C'est trop lent, il perd des clients entre-temps.
3. L'approche MaxCOSD : C'est un chef qui observe, apprend, mais qui ne change sa stratégie que quand il est sûr que sa nouvelle idée est réalisable.

Comment ça marche ?
L'algorithme fonctionne par "cycles" :

• Il essaie une nouvelle quantité de commande (une "candidature").
• Il vérifie immédiatement : "Est-ce que cette quantité est faisable avec ce que j'ai en stock et ce qui arrive ?"
• Si oui : Il adopte cette nouvelle stratégie et continue.
• Si non : Il garde l'ancienne stratégie en attendant le moment idéal pour changer.

C'est comme si vous conduisiez une voiture : vous ne tournez pas le volant à chaque seconde de manière aléatoire. Vous attendez d'avoir de la visibilité et de l'espace (la faisabilité) pour faire un virage en douceur.

🔑 La Condition Magique : "Ne soyez pas trop paresseux"

L'une des découvertes les plus importantes du papier est une condition nécessaire pour que ce système fonctionne. L'algorithme a besoin que la demande ne soit jamais nulle pendant trop longtemps.

L'analogie du jardinier :
Imaginez que vous essayez d'apprendre à arroser un jardin.

• Si la pluie tombe tous les jours (même un peu), vous pouvez apprendre à ajuster votre arrosoir.
• Mais si la pluie s'arrête complètement pendant des mois, vous ne pouvez pas apprendre à gérer l'arrosage. Vous ne savez pas si c'est parce que vous avez trop arrosé ou pas assez, car le sol est déjà sec.

L'article prouve mathématiquement que si la demande tombe à zéro (ou presque) trop souvent, il est impossible d'apprendre à gérer les stocks correctement, peu importe l'intelligence de l'algorithme. Il faut que le "mouvement" (la demande) existe pour que l'apprentissage ait lieu.

🏆 Pourquoi c'est une révolution ?

1. Pas de règles strictes : Contrairement aux anciens modèles, MaxCOSD n'a pas besoin de savoir à l'avance si les clients sont prévisibles ou non. Il s'adapte à tout : produits frais, produits durables, demandes en folie ou calmes.
2. Garantie de performance : Même dans le chaos, l'algorithme promet de ne pas faire trop d'erreurs. Plus le temps passe, plus il devient efficace.
3. Testé sur la réalité : Les auteurs ont testé leur algorithme sur de vraies données de vente (le concours M5, qui utilise des données de milliers de produits réels). Résultat ? Ça marche mieux que les méthodes actuelles, surtout quand on a beaucoup de produits différents à gérer.

En Résumé

Ce papier dit aux entreprises : "Arrêtez de supposer que le monde est prévisible. Utilisez notre nouvel outil, MaxCOSD, qui apprend en marchant, qui s'adapte aux imprévus et qui ne se lance que lorsqu'il est sûr de ne pas faire de bêtise."

C'est passer d'une gestion de stock basée sur des suppositions rigides à une gestion intelligente, flexible et résiliente, capable de survivre dans le monde réel, chaotique et imprévisible des affaires.

Résumé technique

1. Problématique et Contexte

L'article aborde le problème du contrôle de stock en ligne (Online Inventory Control) dans un cadre multi-produits. Le défi consiste pour un gestionnaire à prendre des décisions de réapprovisionnement séquentielles basées sur des informations historiques partielles (états de stock passés, sous-gradients de pertes) afin de minimiser les pertes cumulées (coûts de stockage et pénalités de rupture).

Limites des approches existantes :
La littérature classique et les travaux récents en apprentissage en ligne (Online Learning) reposent souvent sur des hypothèses irréalistes :

• Demandes i.i.d. : L'hypothèse que les demandes sont indépendantes et identiquement distribuées exclut les corrélations temporelles et les non-stationnarités fréquentes dans la réalité.
• Dynamiques spécifiques : La plupart des algorithmes sont conçus pour des dynamiques simples (ex: ventes perdues sans péremption) ou des structures de coûts spécifiques (modèle du "newsvendor").
• Garanties faibles : Les algorithmes précédents offrent souvent des garanties théoriques faibles ou n'existent que pour des cas particuliers.

L'objectif de cet article est de dépasser ces restrictions en considérant des processus de demande, des pertes et des dynamiques de stock généraux, tout en fournissant des garanties théoriques solides.

2. Modèle et Cadre Théorique

Les auteurs introduisent un nouveau cadre appelé Optimisation de Stock en Ligne (OIO - Online Inventory Optimization), qui étend l'Optimisation Convexe en Ligne (OCO).

Le modèle OIO :

• État du système : À chaque période $t$, le gestionnaire observe l'état du stock $x_t$.
• Décision : Il choisit un niveau de réapprovisionnement $y_t$ (niveau "order-up-to") tel que $y_t \succeq x_t$ (contrainte de faisabilité).
• Dynamique : L'état suivant $x_{t+1}$ est mis à jour selon une dynamique contrainte : $x_{t+1} \preceq [y_t - d_t]^+$, où $d_t$ est la demande. Ce cadre englobe des dynamiques variées : sans état (stateless), avec retard (backlogging), ventes perdues (lost sales), et péremption (perishable).
• Feedback : Le gestionnaire subit une perte $\ell_t(y_t)$ et observe un sous-gradient $g_t \in \partial \ell_t(y_t)$.
• Objectif : Minimiser le regret $R_T$, défini comme la différence entre la perte cumulée de l'algorithme et celle de la meilleure stratégie constante (politique de base-stock) rétrospective.

Hypothèses clés :

• Convexité et bornitude de l'ensemble des décisions et des fonctions de perte.
• Hypothèse de non-dégénérescence de la demande (Assumption 10) : C'est le cœur de l'apport théorique. Les auteurs postulent qu'il existe une probabilité $\mu > 0$ et un seuil $\rho > 0$ tels que, conditionnellement à l'historique, la demande soit supérieure à $\rho$ pour tous les produits avec une probabilité au moins $\mu$. Cela généralise l'hypothèse $E[d] > 0$ des travaux antérieurs sans exiger l'i.i.d.

3. Méthodologie : L'algorithme MaxCOSD

Les auteurs proposent un nouvel algorithme nommé MaxCOSD (Maximum Cyclic Online Subgradient Descent).

Principe de fonctionnement :
MaxCOSD est une variante de la Descente de Sous-Gradient en Ligne (OSD) qui opère par cycles.

1. Mise à jour cyclique : Au lieu de mettre à jour le niveau de stock à chaque période, l'algorithme maintient le niveau de décision constant pendant un cycle $T_k$.
2. Déclenchement dynamique : La fin d'un cycle et le début du suivant sont déterminés dynamiquement. À chaque étape, un candidat $\hat{y}_t$ est calculé via une étape de sous-gradient accumulée. Si ce candidat est faisable (c'est-à-dire si la contrainte de dynamique $x_{t+1} \preceq \hat{y}_{t+1}$ est satisfaite), alors la décision est mise à jour et un nouveau cycle commence. Sinon, la décision reste inchangée.
3. Taux d'apprentissage adaptatif : L'algorithme utilise des taux d'apprentissage inspirés d'AdaGrad-Norm, adaptés à la norme des sous-gradients cumulés, permettant d'obtenir des bornes de regret en haute probabilité.

Différences avec les travaux antérieurs :

• Contrairement à l'algorithme CUP (Cycle-Update Policy) qui ne met à jour qu'en cas de rupture de stock (stockout), MaxCOSD vérifie la faisabilité à chaque étape, rendant les mises à jour plus fréquentes.
• Il ne nécessite pas d'hypothèse i.i.d. sur les demandes.

4. Résultats Principaux

Théorème de Regret (Théorème 12) :
Sous les hypothèses de convexité, de bornitude et de non-dégénérescence de la demande (Assumption 10), l'algorithme MaxCOSD garantit un regret optimal de l'ordre de $O(\sqrt{T})$ :

• En espérance : $E[R_T] \leq C \sqrt{T}$.
• En haute probabilité : Avec probabilité $1-\delta$, $R_T \leq C' \sqrt{T} \log(T/\delta)$.

Nécessité de l'hypothèse de non-dégénérescence (Section 5) :
Les auteurs démontrent par des contre-exemples (Propositions 13 et 14) que sans une hypothèse de non-dégénérescence (empêchant les demandes de tendre vers zéro trop rapidement ou d'être nulles), il est impossible d'obtenir un regret sous-linéaire pour les problèmes d'inventaire avec état (stateful).

• Dans les problèmes sans état (stateless), l'OSD classique suffit.
• Dans les problèmes avec état, la contrainte de faisabilité devient critique lorsque la demande est faible, réduisant l'ensemble des décisions possibles et rendant l'apprentissage impossible sans cette hypothèse.

5. Résultats Numériques

Les auteurs valident empiriquement MaxCOSD sur des données synthétiques et réelles (données de la compétition M5) :

• Scénarios testés : Inventaire à ventes perdues, inventaire périssable, problèmes mono-produit et multi-produits (jusqu'à 3049 produits).
• Comparaison : MaxCOSD est comparé à des algorithmes de référence (AIM, CUP, DDM) qui reposent sur des hypothèses i.i.d.
• Performance :
  • MaxCOSD surpasse ou égale les baselines dans la plupart des cas, même lorsque les hypothèses des baselines (i.i.d.) ne sont pas respectées.
  • Dans les cas à très grand nombre de produits (Setting 4), la performance relative diminue légèrement car les cycles deviennent plus longs (la probabilité de satisfaire la contrainte de faisabilité simultanément pour tous les produits diminue), mais l'algorithme reste robuste là où les autres échouent théoriquement.

6. Contributions et Signification

Contributions majeures :

1. Cadre général OIO : Définition d'un modèle unifié couvrant des dynamiques complexes (péremption, ventes perdues, etc.) et des demandes non-i.i.d.
2. Algorithme MaxCOSD : Premier algorithme avec garanties théoriques $O(\sqrt{T})$ pour des problèmes d'inventaire généraux sans hypothèse i.i.d.
3. Condition de non-dégénérescence : Identification et formalisation d'une condition nécessaire et suffisante (dans un sens) pour l'apprenabilité des systèmes d'inventaire avec état.
4. Pont entre OCO et Gestion de Stock : Démonstration que les techniques d'optimisation convexe en ligne peuvent être adaptées avec succès à des problèmes opérationnels complexes, au-delà des modèles simplistes.

Signification :
Ce travail comble un fossé important entre la théorie de l'apprentissage en ligne et la pratique de la gestion de la chaîne logistique. Il offre aux praticiens un outil robuste capable de s'adapter à des environnements dynamiques et non stationnaires, tout en fournissant aux chercheurs de nouvelles directions pour l'optimisation sous contraintes complexes. Les auteurs suggèrent que l'adaptation des techniques d'optimisation convexe (comme la convexité forte ou l'exp-concavité) pourrait encore améliorer les taux de convergence dans le futur.