Technisches Resümee: Multi-Agent Reinforcement Learning aus verzögertem Marktplatz-Feedback zur Anpassung von Objektiv-Gewichtungen in der Drei-Seiten-Disposition

Problemstellung

Die Essensliefer-Disposition arbeitet als sequenzielles Entscheidungsproblem innerhalb eines Drei-Seiten-Marktplatzes, der Kunden, Händler und Kuriere umfasst. Die zentrale Herausforderung besteht darin, konkurrierende Ziele auszubalancieren: Batching (das Gruppieren von Bestellungen zur Verbesserung der Kurier-Effizienz) gegenüber Geschwindigkeit (Minimierung der Lieferzeit zur Verbesserung des Kundenerlebnisses).

In Produktionsumgebungen wie DoorDash wird dieser Tradeoff traditionell durch statische heuristische Gewichte verwaltet, die manuell global abgestimmt werden. Diese statischen Gewichte sind unter lokalen, zeitlich variierenden Bedingungen fragil; beispielsweise führt übermäßiges Batching während einer Überlastung zu Verspätungen, während unzureichendes Batching in Zeiten geringer Auslastung die Effizienz verschwendet. Darüber hinaus muss das System Entscheidungen nicht anhand unmittelbarer menschlicher Präferenzlabels bewerten, sondern anhand von verzögerten operativen Ergebnissen (z. B. Liefergeschwindigkeit, Kurier-Auslastung, Händler-Überlastung), die netzwerkweit gekoppelt sind. Bestehende Reinforcement Learning (RL)-Ansätze versuchen oft, den kombinatorischen Zuweisungsoptimierer vollständig zu ersetzen, was jedoch erhebliche Risiken für die Produktionsmachbarkeit und Sicherheit birgt.

Methodik

Die Autoren präsentieren ein eingesetztes Offline-RL-System, das die Dispatch-Objektivgewichte in Echtzeit anpasst, ohne den bestehenden Produktions-Zuweisungsoptimierer zu ersetzen. Das System verwendet eine zweischichtige Entscheidungsarchitektur:

1. Innere Schicht (Optimierer): Ein kombinatorischer Zuweisungsoptimierer, der Bestellungen, Kuriere und Constraints auf machbare Zuweisungen basierend auf Objektivgewichten abbildet.
2. Äußere Schicht (OWA-RL-Agent): Ein lokaler Policy-Agent auf Store-Ebene, der den lokalen Marktplatzzustand beobachtet und einen diskreten Multiplikator auswählt, um die Objektivgewichte des Optimierers anzupassen.

Formulierung

Das Problem wird als dezentraler Multi-Agent Markov-Entscheidungsprozess (MDP) mit zentralisiertem Offline-Training formuliert:

• Agenten: Jeder Store $i$ agiert als ein Agent.
• Zustand ($s_t$): Umfasst die Anzahl der ausstehenden Lieferungen ($d_t$), die Wartezeit der Kuriere ($cwt_t$) und ein lokalisiertes Angebotsdruck-Feature ($sup_t$). Der Angebotsdruck wird durch den effektiven Kurier-Anbietungsgrad skaliert, um lokale Variationen offenzulegen, die durch regionale Signale verborgen bleiben.
• Aktion ($a_t$): Ein diskreter Multiplikator aus der Menge $\{0.8, 0.9, 1.0, 1.1, 1.2\}$, der auf das Basisgewicht der Liefergeschwindigkeit (ASAP-Gewicht) angewendet wird.
  • Niedrigere Gewichte begünstigen Batching und Routing-Effizienz.
  • Höhere Gewichte priorisieren eine schnellere Auftragsabwicklung.
  • Die neutrale Aktion ($1.0$) stellt das statische Baseline-Verhalten wieder her.
• Belohnung ($r_t$): Eine verzögerte, multi-objektive Belohnung, die auf regionaler Ebene aggregiert wird, um Netzwerkeffekte zu erfassen. Sie ist definiert als gewichtete Summe aus:
  • ASAP: Kundenorientierte Lieferdauer ($t_{drop} - t_{create}$).
  • XCAT: Exzessive aktive Zeit des Kuriers über die direkte Route hinaus ($CAT - T_{direct}$).
  • Die Belohnungsfunktion ist $r = -\frac{1}{|D|} \sum (\alpha \cdot \text{ASAP} + \beta \cdot \text{XCAT})$.

Trainingsarchitektur

Das System nutzt Offline Reinforcement Learning, das auf protokollierten Marktplatzdaten trainiert wurde:

• Algorithmus: Double DQN (Double Deep Q-Network) mit einer geteilten Value-Funktion $Q_\theta(s, a)$.
• Targets: Verwendet Double Q-Learning Targets, um Maximierungs-Bias zu reduzieren:
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• Konservative Regularisierung: Um Out-of-Distribution (OOD) Wertüberschätzung zu verhindern – ein kritisches Problem im Offline RL – integrieren die Autoren einen konservativen Q-Learning (CQL) Regularisierer, der Aktionen bestraft, die nicht gut durch die protokolliert Datenverteilung unterstützt werden.
• Verlustfunktion: $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$.

Hauptbeiträge

Die Arbeit beschreibt drei primäre Beiträge:

1. RL-Architektur zur Anpassung von Objektiv-Gewichten: Führt ein System ein, das aus Marktplatz-Feedback lernt, um Dispatch-Gewichte über eine niedrigdimensionale Steuerungsschnittstelle anzupassen und dabei den bestehenden Produktions-Optimierer zu erhalten, statt ihn zu ersetzen.
2. Offline Multi-Agenten-Formulierung: Formuliert das Problem als eine Offline Multi-Agenten-Entscheidungsaufgabe mit dezentraler Ausführung auf Store-Ebene und verzögerten regionalen Belohnungen, wobei die Herausforderungen von verrauschtem, verzögertem und gekoppeltem Feedback adressiert werden.
3. Produktionsvalidierung: Liefert Belege aus einem produktionsnahen Switchback-Experiment, das zeigt, dass die gelernte Policy das Batching erhöhen und die Zeitkosten auf der Kurierseite reduzieren kann, ohne die kundenorientierte Lieferqualität zu beeinträchtigen.

Experimentelle Ergebnisse

Das System wurde in einem globalen Switchback-Experiment über zwei Wochen evaluiert, wobei etwa 4.000 geografische Regionen zwischen einer Kontrollgruppe (statische Baseline-Gewichte) und einer Treatment-Gruppe (OWA-RL-Policy) randomisiert wurden.

Wichtigste Erkenntnisse (Alle Tageszeiten):

• Effizienzgewinne:
  • Kurier-Aktive Zeit (CAT): Reduziert um 1,26 Sekunden (statistisch signifikant, $p=0,019$).
  • Kurier-Wartezeit (CWT): Reduziert um 0,86 Sekunden (statistisch signifikant, $p=0,004$).
  • Batching-Rate: Erhöht um 0,495 Prozentpunkte (statistisch signifikant, $p < 0,001$).
• Qualitätserhaltung:
  • ASAP (Liefergeschwindigkeit): Keine statistisch signifikante Verschlechterung ($p=0,264$).
  • 20-Minuten-Verspätung: Keine statistisch signifikante Verschlechterung ($p=0,237$).

Performance während der Abendspitze (Dinner Peak):
Ähnliche Trends wurden während der Abendstunden beobachtet, mit signifikanten Reduktionen bei CAT und CWT, erhöhtem Batching sowie leichten Verbesserungen bei der 20-Minuten-Verspätung, während ASAP stabil blieb.

Die Policy demonstrierte eine zustandsabhängige Adaptation, indem sie die Wahrscheinlichkeitsmasse während spezifischer Backlog- und Angebotsregime hin zu niedrigeren Multiplikatoren (Begünstigung von Batching) verschob, anstatt eine feste globale Neukalibrierung anzuwenden.

Bedeutung und Ansprüche

Die Arbeit behauptet, dass diese Arbeit illustriert, wie Welt-Feedback aus einem lebenden wirtschaftlichen und logistischen System genutzt werden kann, um Entscheidungs-Policies online sicher anzupassen. Durch die Beschränkung des RL-Agenten auf eine eng gefasste Objektiv-Gewicht-Schnittstelle behält das System die Produktionsmachbarkeit und operative Sicherheit bei und ermöglicht dennoch eine lokale Anpassung an dynamische Bedingungen.

Die Autoren betonen, dass dieser Ansatz die sichere Bereitstellung von RL in Systemen mit realen operativen und arbeitsbezogenen Auswirkungen ermöglicht, indem er:

• Eine beschränkte Steuerungsschicht nutzt, um Zuverlässigkeit und Skalierbarkeit zu gewährleisten.
• Offline-RL-Sicherheitsmechanismen (CQL) einsetzt, um Distribution Shifts und Datensparsamkeit zu handhaben.
• Sich auf Online-Experimentation (Switchback) verlässt, um Sicherheit und Wirksamkeit vor der vollständigen Implementierung zu validieren.

Die Arbeit dient als Fallstudie für die Integration von RL in komplexe Drei-Seiten-Marktplätze, in denen Entscheidungen mehrere Stakeholder beeinflussen und die Ergebnisse verzögert und gekoppelt sind.