One Step is Enough: Multi-Agent Reinforcement Learning Based on One-Step Policy Optimization for Order Dispatch on Ride-Sharing Platforms

Abstract

Real-time order assignment in ride-sharing platforms involves complex decision-making, requiring the platform to dynamically bundle passenger orders and assign them to vehicles in real time. This problem is particularly challenging due to dynamic and uncertain passenger demand, high-dimensional state spaces, and the need for scalable, coordinated order assignment strategies. Existing Multi-Agent Reinforcement Learning (MARL) approaches are fundamentally constrained by their reliance on accurate value function estimation (Q-values or V-values), which is prone to estimation bias, especially in large-scale, real-world environments. While Policy Gradient (PG) methods eliminate bias, they introduce large variance through Monte Carlo sampling, which hinders convergence in large-scale multi-agent systems. In this work, we propose a novel RL framework that fundamentally bypasses value function estimation by leveraging Group Relative Policy Optimization (GRPO). Specifically, we tailor GRPO to the ride-sharing context by replacing conventional value-function baselines with a fleet-wide average reward-to-go, thereby eliminating critic estimation errors and yielding an unbiased policy-gradient estimator that, as a full-horizon Monte-Carlo method, still incurs relatively high variance. Building on this, we further introduce K-Froward Policy Optimization (KFPO), which exploits the symmetry of homogeneous AV agents and the rapid mixing property of large-scale ride-sharing systems to optimize the policy using only a short, $K$-forward cumulative rewards, thereby introducing a bounded bias in exchange for substantially reduced variance. Moreover, we prove that GRPO and One-Step Policy Optimization (OSPO) represent the two extremes of the KFPO family, balancing bias and variance. Although OSPO exhibits the largest bias within the KFPO family, this bias in fast-mixing homogeneous AV systems is outweighed by the accompanying variance reduction, making OSPO the most lightweight and efficient RL approach in this context. To further enhance adaptability to varying demand patterns and transition dynamics, we propose a novel single-parameter tuning mechanism that dynamically adjusts action certainty for the entire fleet, ensuring robust performance across diverse operational scenarios. Extensive experiments on real-world Manhattan ride-hailing data demonstrate that the proposed OSPO framework achieves strong performance even with simple multilayer perceptron networks and incurs the lowest training costs. With our single-parameter tuning, OSPO exhibits significant improvements across all scenarios, achieving State-Of-The-Art (SOTA) performance and surpassing existing SOTA results by approximately 4.08% in cumulative reward, 10.52% in pickup time, and 1.40% in service rate. Meanwhile, OSPO achieves the best objective value while maintaining the fastest runtime and lightweight GPU usage – for a 30-minute simulation, it uses less than 5.8 GB of GPU memory and completes within 34 seconds, compared with 3.9-21.5 GB and 35-92 seconds for competing methods. The code and trained parameters for this paper are available at https://github.com/RS2002/Scale-OSPO .