Technical Summary: Multi-Agent Reinforcement Learning from Delayed Marketplace Feedback for Objective-Weight Adaptation in Three-Sided Dispatch

Problem Statement

Food-delivery dispatch operates as a sequential decision problem within a three-sided marketplace involving customers, merchants, and couriers. The core challenge lies in balancing competing objectives: batching (grouping orders to improve courier efficiency) versus speed (minimizing delivery time to enhance customer experience).

In production environments like DoorDash, this tradeoff is traditionally managed by static heuristic weights that are manually tuned globally. These static weights are brittle under local, time-varying conditions; for instance, over-batching during congestion increases lateness, while under-batching during slack periods wastes efficiency. Furthermore, the system must evaluate decisions not by immediate human preference labels, but by delayed operational outcomes (e.g., delivery speed, courier utilization, merchant congestion) that are coupled across the network. Existing Reinforcement Learning (RL) approaches often attempt to replace the combinatorial assignment optimizer entirely, which poses significant risks to production feasibility and safety.

Methodology

The authors present a deployed offline RL system that adapts dispatch objective weights in real-time without replacing the existing production assignment optimizer. The system employs a two-layer decision architecture:

1. Inner Layer (Optimizer): A combinatorial assignment optimizer that maps orders, couriers, and constraints to feasible assignments based on objective weights.
2. Outer Layer (OWA-RL Agent): A store-level policy agent that observes local marketplace states and selects a discrete multiplier to adjust the optimizer's objective weights.

Formulation

The problem is formulated as a decentralized multi-agent Markov Decision Process (MDP) with centralized offline training:

• Agents: Each store $i$ acts as an agent.
• State ($s_t$): Includes outstanding delivery count ($d_t$), courier wait time ($cwt_t$), and a localized supply-pressure feature ($sup_t$). The supply pressure is rescaled by effective courier supply to expose store-level variations hidden by regional signals.
• Action ($a_t$): A discrete multiplier from the set $\{0.8, 0.9, 1.0, 1.1, 1.2\}$ applied to the baseline delivery-speed objective weight (ASAP weight).
  • Lower weights favor batching and routing efficiency.
  • Higher weights prioritize faster order completion.
  • The neutral action ($1.0$) recovers the static baseline.
• Reward ($r_t$): A delayed, multi-objective reward aggregated at the regional level to capture network effects. It is defined as a weighted sum of:
  • ASAP: Customer-facing delivery duration ($t_{drop} - t_{create}$).
  • XCAT: Excess courier active time beyond the direct route ($CAT - T_{direct}$).
  • The reward function is $r = -\frac{1}{|D|} \sum (\alpha \cdot \text{ASAP} + \beta \cdot \text{XCAT})$.

Training Architecture

The system utilizes offline reinforcement learning trained on logged marketplace data:

• Algorithm: Double DQN (Double Deep Q-Network) with a shared value function $Q_\theta(s, a)$.
• Targets: Uses Double Q-learning targets to reduce maximization bias:
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• Conservative Regularization: To prevent out-of-distribution (OOD) value overestimation—a critical issue in offline RL—the authors incorporate a Conservative Q-Learning (CQL) regularizer. This penalizes actions that are not well-supported by the logged data distribution.
• Loss Function: $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$.

Key Contributions

The paper outlines three primary contributions:

1. RL Architecture for Objective-Weight Adaptation: Introduces a system that learns from marketplace feedback to adapt dispatch weights via a low-dimensional control interface, preserving the existing production optimizer rather than replacing it.
2. Offline Multi-Agent Formulation: Formulates the problem as an offline multi-agent decision-making task with decentralized store-level execution and delayed regional rewards, addressing the challenges of noisy, delayed, and coupled feedback.
3. Production Validation: Provides evidence from a production switchback experiment demonstrating that the learned policy can increase batching and reduce courier-side time costs without degrading customer-facing delivery quality.

Experimental Results

The system was evaluated in a global switchback experiment over two weeks, randomizing approximately 4,000 geographic regions between a control (static baseline weights) and treatment (OWA-RL policy) group.

Key Findings (All Day Parts):

• Efficiency Gains:
  • Courier Active Time (CAT): Reduced by 1.26 seconds (statistically significant, $p=0.019$).
  • Courier Wait Time (CWT): Reduced by 0.86 seconds (statistically significant, $p=0.004$).
  • Batching Rate: Increased by 0.495 percentage points (statistically significant, $p < 0.001$).
• Quality Preservation:
  • ASAP (Delivery Speed): No statistically significant degradation ($p=0.264$).
  • 20-Minute Lateness: No statistically significant degradation ($p=0.237$).

Dinner Peak Performance:
Similar trends were observed during dinner hours, with significant reductions in CAT and CWT, increased batching, and slight improvements in 20-minute lateness, while ASAP remained stable.

The policy demonstrated state-dependent adaptation, shifting probability mass toward lower multipliers (favoring batching) during specific backlog and supply regimes, rather than applying a fixed global retuning.

Significance and Claims

The paper claims that this work illustrates how world feedback from a live economic and logistics system can be used to safely adapt decision policies online. By constraining the RL agent to a narrow objective-weight interface, the system maintains production feasibility and operational safeguards while enabling local adaptation to dynamic conditions.

The authors emphasize that this approach allows for the safe deployment of RL in systems with real-world operational and labor impacts by:

• Utilizing a constrained control layer to ensure reliability and scalability.
• Employing offline RL safeguards (CQL) to handle distribution shifts and data sparsity.
• Relying on online experimentation (switchback) to validate safety and efficacy before full deployment.

The work serves as a case study for integrating RL into complex, three-sided marketplaces where decisions affect multiple stakeholders and outcomes are delayed and coupled.