# BMG-Q: Localized Bipartite Match Graph Attention Q-Learning for Ride-Pooling Order Dispatch

arXiv: https://arxiv.org/abs/2501.13448 · HTML: https://mlsanity.com/paper/2501.13448/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 30 of its 53 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?](https://mlsanity.com/paper/2011.09533/) (2020)
- [Actor-Attention-Critic for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1810.02912/) (2018)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Multiagent Cooperation and Competition with Deep Reinforcement Learning](https://mlsanity.com/paper/1511.08779/) (2015)
- [Learning Attentional Communication for Multi-Agent Cooperation](https://mlsanity.com/paper/1805.07733/) (2018)
- [Graph Convolutional Reinforcement Learning](https://mlsanity.com/paper/1810.09202/) (2018)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Multi-Agent Game Abstraction via Graph Attention Neural Network](https://mlsanity.com/paper/1911.10715/) (2019)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [Neural Approximate Dynamic Programming for On-Demand Ride-Pooling](https://mlsanity.com/paper/1911.08842/) (2019)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Scalable Reinforcement Learning for Multi-Agent Networked Systems](https://mlsanity.com/paper/1912.02906/) (2019)
- [Hybrid Multi-agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2212.07313/) (2022)
- [Reinforcement Learning in the Wild: Scalable RL Dispatching Algorithm Deployed in Ridehailing Marketplace](https://mlsanity.com/paper/2202.05118/) (2022)
- [Real-time City-scale Ridesharing via Linear Assignment Problems](https://mlsanity.com/paper/1902.10676/) (2019)
- [Efficient Ridesharing Dispatch Using Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10897/) (2020)
- [AdaPool: A Diurnal-Adaptive Fleet Management Framework using Model-Free Deep Reinforcement Learning and Change Point Detection](https://mlsanity.com/paper/2104.00203/) (2021)

## Built on by (most cited first, 7 of 7)

- [One Step is Enough: Multi-Agent Reinforcement Learning based on One-Step Policy Optimization for Order Dispatch on Ride-Sharing Platforms](https://mlsanity.com/paper/2507.15351/) (2025)
- [Triple-BERT: Do We Really Need MARL for Order Dispatch on Ride-Sharing Platforms?](https://mlsanity.com/paper/2510.03257/) (2025)
- [Timing the Match: A Deep Reinforcement Learning Approach for Ride-Hailing and Ride-Pooling Services](https://mlsanity.com/paper/2503.13200/) (2025)
- [LLM-ODDR: A Large Language Model Framework for Joint Order Dispatching and Driver Repositioning](https://mlsanity.com/paper/2505.22695/) (2025)
- [Learning Optimal Dynamic Matching via Graph Neural Networks](https://mlsanity.com/paper/2607.28925/) (2026)
- [RideSkill: A Hierarchical Algorithm for Generalized Ride Sharing with LLM-Driven Automatic Evolution](https://mlsanity.com/paper/2609.02250/) (2026)
- [Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization](https://mlsanity.com/paper/2610.05270/) (2026)

## Abstract (arXiv)

This paper introduces Localized Bipartite Match Graph Attention Q-Learning (BMG-Q), a novel Multi-Agent Reinforcement Learning (MARL) algorithm framework tailored for ride-pooling order dispatch. BMG-Q advances ride-pooling decision-making process with the localized bipartite match graph underlying the Markov Decision Process, enabling the development of novel Graph Attention Double Deep Q Network (GATDDQN) as the MARL backbone to capture the dynamic interactions among ride-pooling vehicles in fleet. Our approach enriches the state information for each agent with GATDDQN by leveraging a localized bipartite interdependence graph and enables a centralized global coordinator to optimize order matching and agent behavior using Integer Linear Programming (ILP). Enhanced by gradient clipping and localized graph sampling, our GATDDQN improves scalability and robustness. Furthermore, the inclusion of a posterior score function in the ILP captures the online exploration-exploitation trade-off and reduces the potential overestimation bias of agents, thereby elevating the quality of the derived solutions. Through extensive experiments and validation, BMG-Q has demonstrated superior performance in both training and operations for thousands of vehicle agents, outperforming benchmark reinforcement learning frameworks by around 10% in accumulative rewards and showing a significant reduction in overestimation bias by over 50%. Additionally, it maintains robustness amidst task variations and fleet size changes, establishing BMG-Q as an effective, scalable, and robust framework for advancing ride-pooling order dispatch operations.