Résumé Technique : Apprentissage par Renforcement Multi-Agent à partir de Retours de Marché Différés pour l'Adaptation des Poids d'Objectifs dans la Répartition Tripartite

Énoncé du Problème

La répartition de la livraison de repas est un problème de décision séquentielle au sein d'un marché tripartite impliquant des clients, des marchands et des coursiers. Le défi central consiste à équilibrer des objectifs concurrents : le regroupement (batching) (grouper les commandes pour améliorer l'efficacité des coursiers) versus la vitesse (minimiser le temps de livraison pour améliorer l'expérience client).

Dans les environnements de production comme DoorDash, ce compromis est traditionnellement géré par des poids heuristiques statiques qui sont ajustés manuellement de manière globale. Ces poids statiques sont fragiles face à des conditions locales et variables dans le temps ; par exemple, un regroupement excessif lors d'une congestion augmente les retards, tandis qu'un regroupement insuffisant pendant les périodes de faible activité gaspille l'efficacité. De plus, le système doit évaluer les décisions non pas par des étiquettes de préférence humaine immédiates, mais par des résultats opérationnels différés (par exemple, la vitesse de livraison, l'utilisation des coursiers, la congestion des marchands) qui sont couplés à travers le réseau. Les approches d'apprentissage par renforcement (RL) existantes tentent souvent de remplacer entièrement l'optimiseur d'assignation combinatoire, ce qui pose des risques importants pour la faisabilité et la sécurité en production.

Méthodologie

Les auteurs présentent un système de RL hors ligne déployé qui adapte les poids des objectifs de répartition en temps réel sans remplacer l'optimiseur d'assignation de production existant. Le système utilise une architecture de décision à deux couches :

1. Couche Interne (Optimiseur) : Un optimiseur d'assignation combinatoire qui cartographie les commandes, les coursiers et les contraintes vers des assignations réalisables basées sur les poids d'objectifs.
2. Couche Externe (Agent OWA-RL) : Un agent de politique au niveau du magasin qui observe les états locaux du marché et sélectionne un multiplicateur discret pour ajuster les poids d'objectifs de l'optimiseur.

Formulation

Le problème est formulé comme un processus de décision markovien (MDP) multi-agent décentralisé avec un entraînement centralisé hors ligne :

• Agents : Chaque magasin $i$ agit comme un agent.
• État ($s_t$) : Comprend le nombre de livraisons en attente ($d_t$), le temps d'attente du coursier ($cwt_t$) et une caractéristique de pression de l'offre localisée ($sup_t$). La pression de l'offre est remise à l'échelle par l'offre de coursiers effectifs pour exposer les variations au niveau du magasin cachées par les signaux régionaux.
• Action ($a_t$) : Un multiplicateur discret issu de l'ensemble $\{0.8, 0.9, 1.0, 1.1, 1.2\}$ appliqué au poids de base de l'objectif de vitesse de livraison (poids ASAP).
  • Des poids plus faibles favorisent le regroupement et l'efficacité du routage.
  • Des poids plus élevés privilégient la rapidité de complétion des commandes.
  • L'action neutre ($1.0$) restaure la base statique.
• Récompense ($r_t$) : Une récompense multi-objectif différée, agrégée au niveau régional pour capturer les effets de réseau. Elle est définie comme une somme pondérée de :
  • ASAP : Durée de livraison du point de vue du client ($t_{drop} - t_{create}$).
  • XCAT : Temps d'activité excédentaire du coursier au-delà de l'itinéraire direct ($CAT - T_{direct}$).
  • La fonction de récompense est $r = -\frac{1}{|D|} \sum (\alpha \cdot \text{ASAP} + \beta \cdot \text{XCAT})$.

Architecture d'Entraînement

Le système utilise l'apprentissage par renforcement hors ligne (offline RL) entraîné sur des données de marché enregistrées :

• Algorithme : Double DQN (Double Deep Q-Network) avec une fonction de valeur partagée $Q_\theta(s, a)$.
• Cibles : Utilise des cibles de Double Q-learning pour réduire le biais de maximisation :
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• Régularisation Conservatrice : Pour prévenir la surestimation des valeurs hors distribution (OOD) — un problème critique en RL hors ligne — les auteurs incorporent un régulariseur de Q-Learning Conservateur (CQL) qui pénalise les actions qui ne sont pas bien soutenues par la distribution des données enregistrées.
• Fonction de Perte : $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$.

Principales Contributions

L'article présente trois contributions principales :

1. Architecture RL pour l'Adaptation des Poids d'Objectifs : Introduit un système qui apprend des retours du marché pour adapter les poids de répartition via une interface de contrôle de faible dimension, préservant l'optimiseur de production existant plutôt que de le remplacer.
2. Formulation Multi-Agent Hors Ligne : Formule le problème comme une tâche de prise de décision multi-agent hors ligne avec une exécution décentralisée par magasin et des récompenses régionales différées, traitant les défis des retours bruités, différés et couplés.
3. Validation en Production : Fournit des preuves issues d'une expérience de switchback en production démontrant que la politique apprise peut augmenter le taux de regroupement et réduire les coûts de temps côté coursier sans dégrader la qualité de livraison du point de vue du client.

Résultats Expérimentaux

Le système a été évalué lors d'une expérience de switchback globale sur deux semaines, randomisant environ 4 000 régions géographiques entre un groupe de contrôle (poids de base statiques) et un groupe de traitement (politique OWA-RL).

Principales Conclusions (Toutes les périodes de la journée) :

• Gains d'Efficacité :
  • Temps d'Activité du Coursier (CAT) : Réduit de 1,26 seconde (statistiquement significatif, $p=0.019$).
  • Temps d'Attente du Coursier (CWT) : Réduit de 0,86 seconde (statistiquement significatif, $p=0.004$).
  • Taux de Regroupement (Batching Rate) : Augmenté de 0,495 point de pourcentage (statistiquement significatif, $p < 0.001$).
• Préservation de la Qualité :
  • ASAP (Vitesse de Livraison) : Aucune dégradation statistiquement significative ($p=0.264$).
  • Retard de 20 Minutes : Aucune dégradation statistiquement significative ($p=0.237$).

Performance lors du Pic du Dîner :
Des tendances similaires ont été observées pendant les heures du dîner, avec des réductions significatives de CAT et CWT, une augmentation du regroupement, ainsi qu'une légère amélioration du retard de 20 minutes, tandis que l'ASAP est resté stable.

La politique a démontré une adaptation dépendante de l'état, déplaçant la masse de probabilité vers des multiplicateurs plus faibles (favorisant le regroupement) lors de régimes spécifiques de backlog et d'offre, plutôt que d'appliquer un réajustement global fixe.

Signification et Revendications

L'article affirme que ce travail illustre comment le feedback du monde réel provenant d'un système économique et logistique vivant peut être utilisé pour adapter en ligne les politiques de décision en toute sécurité. En contraignant l'agent RL à une interface étroite de poids d'objectifs, le système maintient la faisabilité de la production et les garde-fous opérationnels tout en permettant une adaptation locale aux conditions dynamiques.

Les auteurs soulignent que cette approche permet le déploiement sécurisé du RL dans des systèmes ayant des impacts réels sur l'exploitation et le travail en :

• Utilisant une couche de contrôle contrainte pour garantir la fiabilité et l'évolutivité.
• Employant des garde-fous de RL hors ligne (CQL) pour gérer les changements de distribution et la rareté des données.
• S'appuyant sur l'expérimentation en ligne (switchback) pour valider la sécurité et l'efficacité avant un déploiement complet.

Ce travail sert d'étude de cas pour l'intégration du RL dans des marchés complexes à trois côtés où les décisions affectent plusieurs parties prenantes et où les résultats sont différés et couplés.