Research map / Reinforcement learning / Imitation learning
Massively Scalable Inverse Reinforcement Learning in Google Maps
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Scales maximum-entropy and related inverse RL to a 200M-state global road graph for route recommendation, via graph compression, geography-based mixture-of-experts parallelism, a dominant-eigenvector-inspired initialization (MaxEnt++), and a new receding-horizon family (RHIP) that interpolates MaxEnt, BIRL and MMP.
Problem
Inverse reinforcement learning for route recommendation has not been scaled to planetary-scale road graphs with hundreds of millions of states and demonstration trajectories.
Approach
Initialize MaxEnt's backward pass with the highest-reward-to-destination values (computed via Dijkstra) instead of a one-hot destination vector, and generalize classic IRL with a receding horizon H that rolls out a stochastic policy for H steps before switching to a deterministic shortest-path planner, while sharding the global MDP into geographic experts and compressing the graph tensor.
Key results
- Global RHIP policy with DNN+SparseLin reward reaches 0.4958 accuracy vs 0.4283 for global ETA+penalties, a 15.9% relative accuracy lift for driving.
- RHIP with H=10 trains about 70% faster than MaxEnt while achieving the best route quality in the experimental metros; MaxEnt++ is 16% faster than MaxEnt with no accuracy drop.
- Graph compression (split+merge) yields a 2.7x training speed-up with almost no change in route quality metrics.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use global RHIP with DNN+SparseLin instead of ETA+penalties | Global Drive routing · Global Drive | accuracy: .4283 -> .4958 | Helped |
| Use RHIP DNN+SparseLin instead of the next-best driving IRL policy | Driving route recommendation · 9 experimental metros, Drive | accuracy: .0023 | Helped |
| Use RHIP DNN+SparseLin instead of the next-best two-wheeler IRL policy | Two-wheeler route recommendation · 9 experimental metros, Two-wheelers | accuracy: .0018 | Helped |
| Set RHIP horizon to H=10 instead of using MaxEnt (ablation) | RHIP route recommendation · Experimental region | training time: 70% faster | Helped |
| Initialize MaxEnt with the highest-reward path to the destination (MaxEnt++) (ablation) | MaxEnt · Experimental region | training speed: 16% faster | Helped |
| Use split+merge graph compression instead of no compression (ablation) | IRL graph computation · Experimental region | steps per sec: .373 -> .993 | Helped |
| Use split+merge graph compression (ablation) | IRL graph computation · Experimental region | accuracy: .454 -> .455 | No clear effect |
| Use split graph compression (ablation) | IRL graph computation · Experimental region | accuracy: .454 -> .455 | No clear effect |
| Use merge graph compression (ablation) | IRL graph computation · Experimental region | accuracy: .454 -> .455 | No clear effect |
| Replace power iteration with Arnoldi iteration (ablation) | MaxEnt backward pass · GridWorld | log-space reconstruction error | Hurt |
| Replace iterative forward pass with the UMFPACK closed-form matrix geometric series (ablation) | MaxEnt forward pass · Graphs larger than around 10k nodes | scalability | No clear effect |
Surprising findings
- MaxEnt is not on the Pareto front: RHIP with H=10 gives both better route quality and faster training than MaxEnt.
- Arnoldi iteration (ARPACK) is numerically unstable for the MaxEnt backward pass due to lacking a log-space implementation, and UMFPACK direct solve only helps on graphs up to about 10k nodes.
Limitations
- Demonstration data is private and cannot be released, limiting reproducibility; IRL quality is bounded by noisy demonstrations.
- Geographic mixture-of-experts limits information sharing across large regions.
- Merging nodes in graph compression introduces approximation error in the nonlinear reward setting; IoU improvements were not statistically significant.
Experimental setup
Datasets: Google Maps de-identified user navigation trips (drive and two-wheeler)
Benchmarks: Google Maps route demonstrations (9 experimental metros and global validation set)
Metrics: route accuracy (perfect match) IoU NLL training steps per second
Baselines: ETA ETA+penalties MaxEnt Deep MaxEnt MMP/LEARCH Deep LEARCH BIRL Deep BIRL
Builds on: MaxEnt IRL Bayesian IRL Max Margin Planning LEARCH Deep MaxEnt
Closest papers by meaning
- How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach (NeurIPS 2024 · similarity 0.89)
- Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective (ICML 2024 · similarity 0.88)
- Recent Advancements in Inverse Reinforcement Learning (AAAI 2024 · similarity 0.87)
- Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms (ICML 2024 · similarity 0.87)
- GoIRL: Graph-Oriented Inverse Reinforcement Learning for Multimodal Trajectory Prediction (ICML 2025 · similarity 0.87)
- Hybrid Inverse Reinforcement Learning (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.