Technische Samenvatting: Multi-Agent Reinforcement Learning vanuit Vertraagde Marktplaatsfeedback voor Objectief-Gewicht Adaptatie in Driezijdige Dispatch

Probleemstelling

Voedselbezorging-dispatch werkt als een sequentieel besluitvormingsprobleem binnen een driezijdige marktplaats bestaande uit klanten, winkeliers en koeriers. De kernuitdaging ligt in het balanceren van concurrerende doelstellingen: batching (het groeperen van bestellingen om de efficiëntie van koeriers te verbeteren) versus snelheid (het minimaliseren van de levertijd om de klantervaring te verbeteren).

In productieomgevingen zoals DoorDash wordt deze afweging traditioneel beheerd door statische heuristische gewichten die globaal handmatig worden afgesteld. Deze statische gewichten zijn broos onder lokale, tijdvariërende omstandigheden; bijvoorbeeld zorgt overmatige batching tijdens congestie voor vertraging, terwijl onvoldoende batching tijdens rustige periodes efficiëntie verspilt. Bovendien moet het systeem beslissingen niet evalueren op basis van directe menselijke voorkeursetiketten, maar op basis van vertraagde operationele uitkomsten (bijv. leveringssnelheid, koeriersbenutting, winkelcongestie) die gekoppeld zijn over het netwerk. Bestaande Reinforcement Learning (RL) benaderingen proberen vaak de combinatorische toewijzingsoptimizer volledig te vervangen, wat aanzienlijke risico's vormt voor de productiebestendigheid en veiligheid.

Methodologie

De auteurs presenteren een gedeponeerd offline RL-systeem dat de dispatch-objectiefgewichten in realtime aanpast zonder de bestaande productie-toewijzingsoptimizer te vervangen. Het systeem maakt gebruik van een twee-laagse beslissingsarchitectuur:

1. Binnenste laag (Optimizer): Een combinatorische toewijzingsoptimizer die bestellingen, koeriers en beperkingen in kaart brengt naar haalbare toewijzingen op basis van objectiefgewichten.
2. Buitenste laag (OWA-RL Agent): Een winkel-niveau beleidsagent die de lokale marktplaatsstatussen observeert en een discrete multiplier selecteert om de objectiefgewichten van de optimizer aan te passen.

Formulering

Het probleem wordt geformuleerd als een gedecentraliseerde multi-agent Markov Beslissingsproces (MDP) met gecentraliseerde offline training:

• Agenten: Elke winkel $i$ fungeert als een agent.
• Toestand ($s_t$): Omvat het aantal openstaande leveringen ($d_t$), de wachttijd van de koerier ($cwt_t$) en een gelokaliseerde aanboddruk-feature ($sup_t$). De aanboddruk is geschaald door de effectieve koeriersaanbod om winkel-niveau variaties bloot te leggen die verborgen blijven door regionale signalen.
• Actie ($a_t$): Een discrete multiplier uit de verzameling $\{0.8, 0.9, 1.0, 1.1, 1.2\}$ toegepast op het basisgewicht van de leveringssnelheid (ASAP-gewicht).
  • Lagere gewichten bevoordelen batching en routing-efficiëntie.
  • Hogere gewichten geven prioriteit aan snellere voltooiing van bestellingen.
  • De neutrale actie ($1.0$) herstelt de statische baseline.
• Beloning ($r_t$): Een vertraagde, multi-objectieve beloning die op regionaal niveau wordt geaggregeerd om netwerkeffecten te vangen. Deze is gedefinieerd als een gewogen som van:
  • ASAP: Klantgerichte leveringsduur ($t_{drop} - t_{create}$).
  • XCAT: Excessieve actieve tijd van de koerier buiten de directe route ($CAT - T_{direct}$).
  • De beloningsfunctie is $r = -\frac{1}{|D|} \sum (\alpha \cdot \text{ASAP} + \beta \cdot \text{XCAT})$.

Trainingsarchitectuur

Het systeem maakt gebruik van offline reinforcement learning getraind op gelogde marktplaatsdata:

• Algoritme: Double DQN (Double Deep Q-Network) met een gedeelde waardefunctie $Q_\theta(s, a)$.
• Targets: Gebruikt Double Q-learning targets om maximalisatiebias te verminderen:
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• Conservatieve Regularisatie: Om out-of-distribution (OOD) waarde-overschatting te voorkomen—een kritiek probleem in offline RL—hebben de auteurs een Conservative Q-Learning (CQL) regularisator toegevoegd. Deze straft acties af die niet goed ondersteund worden door de gelogde datadistributie.
• Verliesfunctie: $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$.

Belangrijkste Bijdragen

Het artikel beschrijft drie primaire bijdragen:

1. RL Architectuur voor Objectief-Gewicht Adaptatie: Introduceert een systeem dat leert van marktplaatsfeedback om dispatch-gewichten aan te passen via een laag-dimensionale controle-interface, waarbij de bestaande productie-optimizer behouden blijft in plaats van vervangen te worden.
2. Offline Multi-Agent Formulering: Formuleert het probleem als een offline multi-agent besluitvormingstaak met gedecentraliseerde winkel-niveau uitvoering en vertraagde regionale beloningen, waarbij de uitdagingen van ruisende, vertraagde en gekoppelde feedback worden aangepakt.
3. Productie Validatie: Levert bewijs uit een productie switchback-experiment dat aantoont dat het geleerde beleid de batching kan verhogen en de tijdkosten aan de koerierszijde kan verminderen zonder de klantgerichte leveringskwaliteit te verslechteren.

Experimentele Resultaten

Het systeem werd geëvalueerd in een globale switchback experiment over twee weken, waarbij ongeveer 4.000 geografische regio's werden gerandomiseerd tussen een controle groep (statische baseline gewichten) en een behandelingsgroep (OWA-RL beleid).

Belangrijkste Bevindingen (Alle dagdelen):

• Efficiëntiewinsten:
  • Koerier Actieve Tijd (CAT): Verminderd met 1,26 seconden (statistisch significant, $p=0,019$).
  • Koerier Wachttijd (CWT): Verminderd met 0,86 seconden (statistisch significant, $p=0,004$).
  • Batching Rate: Verhoogd met 0,495 procentpunt (statistisch significant, $p < 0,001$).
• Kwaliteitsbehoud:
  • ASAP (Leveringssnelheid): Geen statistisch significante degradatie ($p=0,264$).
  • 20-Minuten Lateness: Geen statistisch significante degradatie ($p=0,237$).

Prestaties tijdens het Avondpiekuur:
Vergelijkbare trends werden waargenomen tijdens de avonduren, met significante reducties in CAT en CWT, een verhoogde batching, en lichte verbeteringen in 20-minuten lateness, terwijl ASAP stabiel bleef.

Het beleid demonstreerde toestand-afhankelijke adaptatie, waarbij de waarschijnlijkheidsmassa verschoof naar lagere multipliers (bevoordeling van batching) tijdens specifieke achterstanden en aanbodregimes, in plaats van een vaste globale herafstemming toe te passen.

Betekenis en Claims

Het artikel claimt dat dit werk illustreert hoe wereldwijde feedback van een levend economisch en logistiek systeem gebruikt kan worden om beslissingsbeleid online veilig aan te passen. Door de RL-agent te beperken tot een nauwe objectief-gewicht interface, behoudt het systeem de productiebestendigheid en operationele waarborgen terwijl het lokale adaptatie aan dynamische condities mogelijk maakt.

De auteurs benadrukken dat deze benadering de veilige implementatie van RL in systemen met echte wereld operationele en arbeidseffecten mogelijk maakt door:

• Een beperkte controlelaag te gebruiken om betrouwbaarheid en schaalbaarheid te garanderen.
• Offline RL waarborgen (CQL) te gebruiken om distributieverschuivingen en dataschaarsheid aan te pakken.
• Te vertrouwen op online experimentatie (switchback) om veiligheid en effectiviteit te valideren vóór volledige uitrol.

Het werk dient als een casestudy voor de integratie van RL in complexe, drie-zijdige marktplaatsen waar beslissingen invloed hebben op meerdere belanghebbenden en uitkomsten vertraagd en gekoppeld zijn.