# H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi Dispatch

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 5 May 2021.

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

- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [Control of Robotic Mobility-On-Demand Systems: a Queueing-Theoretical Perspective](https://mlsanity.com/paper/1404.4391/) (2014)
- [MOVI: A Model-Free Approach to Dynamic Fleet Management](https://mlsanity.com/paper/1804.04758/) (2018)
- [Deep Reinforcement Learning for Event-Driven Multi-Agent Decision Processes](https://mlsanity.com/paper/1709.06656/) (2017)
- [GLAS: Global-to-Local Safe Autonomy Synthesis for Multi-Robot Motion Planning with End-to-End Learning](https://mlsanity.com/paper/2002.11807/) (2020)
- [Taxi Dispatch with Real-Time Sensing Data in Metropolitan Areas: A Receding Horizon Control Approach](https://mlsanity.com/paper/1603.04418/) (2016)
- [Robust Controller Design for Stochastic Nonlinear Systems via Convex Optimization](https://mlsanity.com/paper/2006.04359/) (2020)
- [Distributed Bayesian Filtering using Logarithmic Opinion Pool for Dynamic Sensor Networks](https://mlsanity.com/paper/1712.04062/) (2017)
- [Optimizing Online Matching for Ride-Sourcing Services with Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1902.06228/) (2019)
- [Probabilistic and Distributed Control of a Large-Scale Swarm of Autonomous Agents](https://mlsanity.com/paper/1403.4134/) (2014)
- [Cooperative Adaptive Control for Cloud-Based Robotics](https://mlsanity.com/paper/1709.07112/) (2017)

## Abstract (arXiv)

We present H-TD2: Hybrid Temporal Difference Learning for Taxi Dispatch, a model-free, adaptive decision-making algorithm to coordinate a large fleet of automated taxis in a dynamic urban environment to minimize expected customer waiting times. Our scalable algorithm exploits the natural transportation network company topology by switching between two behaviors: distributed temporal-difference learning computed locally at each taxi and infrequent centralized Bellman updates computed at the dispatch center. We derive a regret bound and design the trigger condition between the two behaviors to explicitly control the trade-off between computational complexity and the individual taxi policy's bounded sub-optimality; this advances the state of the art by enabling distributed operation with bounded-suboptimality. Additionally, unlike recent reinforcement learning dispatch methods, this policy estimation is adaptive and robust to out-of-training domain events. This result is enabled by a two-step modelling approach: the policy is learned on an agent-agnostic, cell-based Markov Decision Process and individual taxis are coordinated using the learned policy in a distributed game-theoretic task assignment. We validate our algorithm against a receding horizon control baseline in a Gridworld environment with a simulated customer dataset, where the proposed solution decreases average customer waiting time by 50% over a wide range of parameters. We also validate in a Chicago city environment with real customer requests from the Chicago taxi public dataset where the proposed solution decreases average customer waiting time by 26% over irregular customer distributions during a 2016 Major League Baseball World Series game.