Massively Scalable Inverse Reinforcement Learning in Google Maps
Authors: Matt Barnes
Matthew Abueg
Oliver F. Lange
Matt Deeds
Jason Trader
Denali Molitor
Markus Wulfmeier
Shawn O'Banion
Venue: ICLR 2024 spotlight (2024)
Keywords: Inverse reinforcement learning
route optimization
Primary area: reinforcement learning

Abstract: Inverse reinforcement learning (IRL) offers a powerful and general framework for learning humans' latent preferences in route recommendation, yet no approach has successfully addressed planetary-scale problems with hundreds of millions of states and demonstration trajectories. In this paper, we introduce scaling techniques based on graph compression, spatial parallelization, and improved initialization conditions inspired by a connection to eigenvector algorithms. We revisit classic IRL methods in the routing context, and make the key observation that there exists a trade-off between the use of cheap, deterministic planners and expensive yet robust stochastic policies. This insight is leveraged in Receding Horizon Inverse Planning (RHIP), a new generalization of classic IRL algorithms that provides fine-grained control over performance trade-offs via its planning horizon. Our contributions culminate in a policy that achieves a 16-24% improvement in route quality at a global scale, and to the best of our knowledge, represents the largest published study of IRL algorithms in a real-world setting to date. We conclude by conducting an ablation study of key components, presenting negative results from alternative eigenvalue solvers, and identifying opportunities to further improve scalability via IRL-specific batching strategies.

Published as a conference paper at ICLR 2024
MASSIVELY SCALABLE INVERSE REINFORCEMENT LEARNING IN GOOGLE MAPS
Matt Barnes' -M
Matthew Abueg!
Oliver F. Lange*
Matt Deeds²
Jason Trader2
Denali Molitor
Markus Wulfmeier
Shawn O'Banion"
Google Research
Goooge Maps
Google DeepMind
ABSTRACT
Inverse reinforcement learning (IRL) offers a powerful and general framework for learning humans' latent preferences in route recommendation, yet no approach has successfully addressed planetary-scale problems with hundreds of millions of states and demonstration trajectories. In this paper, we introduce scaling techniques based on graph compression, spatial parallelization, and improved initialization conditions inspired by connection to eigenvector algorithms. We revisit classic IRL methods in the routing context, and make the key observation that there exists a trade-off between the use of cheap, deterministic planners and expensive yet robust stochastic policies. This insight is leveraged in Receding Horizon Inverse Planning (RHIP), a new generalization of classic IRL algorithms that provides fine-graine control over performance trade-offss via its planning horizon. Our contributions culminate in a policy that achieves a 16-24% improvement in route quality at global scale, and to the best of our knowledge, represents the largest published study of IRL algorithms in a real-world setting to date. We conclude by conducting an ablation study of key com- ponents, presenting negative results from alternative eigenvalue solvers, and identify- ing opportunities to further improve scalability via IRL-specific batching strategies.
INTRODUCTION
Inverse reinforcement learning (IRL) is the problem of learning latent preferences from observed
sequential decision making behavior. First proposed by Rudolf Kálmán in 1964 (when went under the name of inverse optimal control (Kalman, 1964). and later structural estimation (Rust, 1994)),
IRL has now been studied in robotics (Abbeel al., 2008 Ratliff et al., 2009 Ratliff al., 2007). cognitive science (Baker et al., 2009), video games (Tastan and Sukthankar, 2011 Tucker et al., 2018).
human motion behavior (Kitani et al., 2012] Rhinehart and Kitani, 2020) and healthcare (Imani and Braga-Neto, 2019 Yu et al., 2019), among others.
In this paper, we address a key challenge in all these applications: scalability (Chan and Schaar, 2021 Michini et al., 2013] Wulfmeier al., 2016b). With several notable exceptions, IRL algorithms require solving an RL problem at every gradient step, in addition to performing standard backpropagation (Finn et al., 2016b; Swamy et 2023). This a significant computational challenge, and necessitates access to both an interactive MDP and a dataset of expert demonstrations that are often costly to collect. By addressing the scalability issue, we aim to leverage recent advancements in training foundation-sized models on large datasets.
To illustrate our claims, we focus on the classic route finding task, due to its immediate practical significance and the availability of large demonstration datasets. Given an origin and destination location any where in the world, the goal is to provide routes that best travelers' latent preferences. These preferences are only observed through their physical behavior, which implicitly trade-off factors including traffic conditions, distance, hills, safety, scenery, road conditions, etc. Although we primarily focus route finding, the advancements in this paper are general enough find use more broadly.
We address the scalability challenge by providing both (a) practical techniques to improve IRL scalability and (b) new view on classic IRL IRL algorithms that reveals novel generalization and enables fine-grained control of performance characteristics. Coneretely, our contributions are follows:
"Equal contribution. Correspondencect (mat baattbare raas, mattea, mwu1 fmeier, oban en) @google com

---

Published as a conference paper at ICLR 2024
Kaneas City
17%
20%
18%
10%
10%
Preguo
17%
25%
43%
Mam
Caro
13%
20%
14%
Las Vegas 30%
24%
Mania
13 %
Aodis Ababa 9%
24%
Uime 8%
16%
Sinrspore 10%
13%
Monole 15%
Condeba 10%
Cape Town
Sydney
5%
3%
Figure Google Maps route accuracy improvements in several world regions, when using our inverse reinforcement learning policy. Full results are presented in Table and Figure
MaxEnt++ An improved version of MaxEnt IRL (Ziebart et al., 2008 that inspired by con- nection to dominant eigenvectors to initialize the backward pass closer to the desired solution.
Spatial parallelization A simple, practical technique shard the global MDP by leveraging geography- -ased sparse mixture-off -faturreof--xperts.
Graph compression strategies Lossless and lossy methods to compress the graph matrices and reduce both the memory footprint and FLOP count across all IRL algorithms.
Receding Horizon Inverse Planning (RHIP) A novel IRL algorithm that generalizes MaxEnt BIRL (Ramachandran and Amir, 2007) and MMP (Ratliff et 2006). RHIP leverages our insight that there exists trade-off between the use of cheap, deterministic planners and expensive yet robust stochastic policies. Practically, RHIP enables interpolating between classic a algorithms to realize policies that are both fast and accurate.
Alternative solvers Secondary negative results when attempting to use Arnoldi iteration and a closed-form matrix geometric series in MaxEnt, which defer Appendix
MaxEnt theory Secondary theoretical analyses of MaxEnt, which we defer to Appendix B
Our work culminates in a global policy that achieves a 15.9% and 24. lift route accuracy for driving and two-wheelers, respectively (Figure T and was successfully applied to a large scale setting in Google Maps. To the best of our knowledge, this represents the largest published study of IRL methods in real-world setting to date.
2 INVERSE REINFORCEMENT LEARNING
A Markov decision process (MDP) M is defined by a discrete set of states S, actions A, transition kernel T and reward function (i.e. negative cost function). Given M Y and of state-action trajectory demonstrations D [ [Tn } sampled from a demonstration policy mg. the goal of IRL is to recover the latent r We denote the state and state-action distributions trajectory 7 by P and p respectively.
For expository purposes, we initially restrict our attention to the classic math-plamning problem, and discuss extensions in Section In line with prior work (Ziebart et al., 2008). define these MDPs as discrete, deterministic, and undiscounted where ro (8),88)) & 0 denotes the 6-parameterized reward of transitioning from state s; to state s, and conoalloaable transitions have reward -o0. There exists a single abs-bbbboring zero-reward destination state Sa, which implies that each unique destination
'This is an ill conditioned problem, multiple reward functions can induce the same trajectories. Methods impose regularization constraints to form unique solution, e.g. the principle of maximum entropy (Ziebart al., 2008
2

---

Published as a conference paper at ICLR 2024
induces slightly different MDP. However, for the sake of notational simplicity and without loss of generality, we consider the special case of a single origin state 8, and single destination state Sa. We do not make this simplification for any of our empirical results. In the path-planning context, states (i.e. nodes) represent road segments and allowable transitions (i.e. edges) between nodes represent turns.
Inverse reinforcement learning algorithms follow the two-player zero-sum game
minmax (TTE - ( w well BEe
minmax miinmx/(mm.aTt (TTE,TT,T)) rEllége
where r() = E E( (1,,5144)) (8,,))))))) denotes the value of the policy л under reward function ra. We consider primal strategies for the equilibrium computation, where the policy player follows no-regret strategy against best-response discriminative player (Swamy et al.. 2021). Classic IRL algorithms follow from Equation | by specifying certain policy classes and regularizers (see Aopendix[ffor details). Following Ziebart et al. (2008), we refer the backward pass as estimating the current policy и and the forward pass as rolling out the current policy.
Goal conditioning Learning function Tg using IRL provides concise representation of preferences and simplifies transfer across goal states s,. as the reward function is decomposed into general learned term and fixed modification at the destination aself-absorbing, zero-reward), In the tabular setting, the number of reward parameters is ((SA) A) even when conditioning on sg. This is in contrast to approaches that explicitly learn a policy, Q-function or value function (e.g. BC, IQ-Learn (Garg et al., (02T). VICEeDICE (Kostrikov et al., 2020), GAIL (Ho and Ermon, 2016). DAGGER (Ross and D. Bagnell, 2010), which require additional complexity when conditioning on sa. e.g. in the tabular setting, the number of policy parameters increases from (SSA) to ( A). ). By learning rewards instead of policies, we can evaluate re once offline for every edge in the graph, store the results in a database, precompute contraction hierarchies (Geisberger et al., 2012), and use a fast graph search algorithm to find the highest reward pati for online (8.,8a) requests. This is in contrast to learned policy, which must be evaluated online for every (8o:8a) request and for every step in the sampled route - a computationally untenable solution in many online environments.
RELATED WORK
IRL approaches can be categorized according to the form of their loss function MaxEnt (Ziebart et al.,, 2008) optimizes cross- cross-ntrrppy loss, MMP (Ratliff et al., (2006) optimizes margin loss, and BIRL (Ramachandran and Amir, 2 optimizes sequential Bayestan likelihood. LEARCH (Ratliff et al., 2009) replaces the quadratic programming optimization in MMP (Ratliff et al. 2006) with stochastic gradient descent. Choi and Kim (2011) replace the MCMC sampling in BIRL (Ramachandran and Amir, (007) with maximum a posteriori estimation. Extensions to continuous state-action spaces are possible through sampling-bass on Wulfmeier et al. (2015) and Mainprice et al. (2016), who applied MaxEnt and LEARCH to the deep function approximator setting.
techniques (Finn et al., al.,2016a| Fu et al., 2018). Our work builds
Existing approaches to scale IRL consider several orthogonal and often complimentary techniques. Michini et al. (2013) incorporate real-time dynamic programming (Barto et al., 1995). which is less applicable with modern accelerators' matrix operation parallelization. Chan and Schaar (202T) apply a variational perspective to BIRL. MMP is inherently more scalable, as its inner loop only requires calling a planning subroutine (c.g. Dijkstra) (Ratliff al., 2209).. However, it lacks robustness to real-world noise, and has lost favor to more stable and accurate probabilistic policies (Osa et 2018) MacGlashan and Littman (2015) similarly introduce a receding horizon to improve planning times] They assume zero reward beyond the horizon, whereas we assume a cheap deterministic planner beyond the horizon in order propagate rewards from distant goal states.
Recently, imitation learning approaches that directly attempt to recover the demonstrator policy have gained increased attention (Ho and Ermon, 2016 Ke et al., 2021). Behavior cloning avoids performing potentially expensive environment roll-outs, but suffers regret quadratic in the horizon (Ross and D. Bagnell. 2010). DAGGER solves the compounding errors problem by utilizing expert corrections
2The highest reward path is equivalent to the most likely path under MaxEnt (Ziebart et al., 2008).
'The IRI. route optimization problem is reducible supervised classification with infinitely many classes, where each class a valid route from the origin to the destination, the features are specified by the edges. and the la- bel is the demonstration route. Unlike typical supervised classes is intractable, so IRI. approaches take advantage of the MDP structure to efficiently compute loss gradients. MacGGashaa and Littman (2015) reduces BTRL. (Ramachandran and Amir, 2007) with infinite horizon.
problems, solving this directly by enumerating all
3

---

Published as a conference paper at ICLR 2024
Experts
Reinforcement Learning
Demonstrations
Graph
Loss Estimate
Sraph
Solver
Worldwide road network
Worldwide reward graph
Figure 2: Architecture overview. The final rewards are used serve online routing requests.
(Ross et al., 2011 Recent approaches use the demonstrators' distribution to reduce exploration in the RL subroutine (Swamy 2023) and complementary to our work. Mixed approaches such as GAIL simultaneously learn both a policy (generator) and reward function (discriminator) (Finn et 2016b) al1,, Ho and frmmon,2016, Ke et al., 202T). although can be susceptible training instabilities (Xing et al., (021). IQ-Learn (Girg et al., 2021) and ValueDICE (Kostrikov et al., 2020) directly learn Q-function and value function, respectively. We avoid explicitly learning policy, Q-function or value function due to the goal conditioning requirement discussed in Section
4 METHODS
The worldwide road network contains hundreds of millions nodes and edges. first glance, even attempting to fit the graph features into high-bandwidth memory to compute single gradient step infeasible. this section, we present a series advancements which enable solving the world-scale IRL route finding problem, summarized in Figure 2 At the end of Section 6 we provide useful summary other directions which yield negative results.
Parallelism strategies We use sparse Mixture of Experts (MoE) strategy (Shazeer et al., 201 7). where experts are uniquely associated to geographic regions and each demonstration sample deterministically assigned to a single expert (i.e. one-hot sparsity). This minimizes cross-expert samples and allows each expert to learn routing preferences specific to region. Specifically, we shard the global MDP M and demonstration dataset D into m disjoint subproblems (M...D)....(MM DD.). We train region-specific experts ro.....,''.., in parallel, and compute the final global rewards using r(s.a) To (s,a) where (s,a) M,, We additionally use standard data parallelism strategies within each expert to further partition minibatch samples across accelerator devices.
MaxEnt++ initialization MaxEnt (Ziebart et al., 2008 is typically initialized to the value (i.e. log partition) function (s,) = logI[s; = sa]. where I[s sa] is zero everywhere except at the destination node (see Appendix C.I This propagates information outwards from the destination, and requires that the number of dynamic programming steps is at least the graph diameter for arbitrary destinations. Instead, we initialize the values ((0) to be the highest reward to the destination from every node. This initialization is strictly closer to the desired solution by
[[ sa] sa]
min (r(r)
( u((s)
(2)
TEToçina
TETo
MaxEnt initialization
MaxEnt initialization
Solution
where Ts..s, is the (infinite) of all paths which begin and end at sa (see proof in Appendix B.3 Note that equality only holds on contrived MDPs, and the middle term can be cheaply computed via Dijkstra or A" We call this method MaxEnt++ (summarized in Algorithm 2
The correspondence between MaxEnt and power iteration provides more intuitive perspective. Specifically, the MaxEnt backward pass initialization ( defines the initial conditions of power iteration, and the solution e" is the dominant eigenvector of the graph. By more closely aligning the initialization (()) to the solution, the number of required power iteration steps is decreased.
a nod the improved initialization of k-means++ (Arthur and Vassilvitskii, 2006
4

---

Published as a conference paper at ICLR 2024
Algorithm RIII (Receding Horizon Inverse Planning)
Input:
Current reward ræ, horizon H. demonstration r with origin 8, and destination 8a
4
Output: Parameter update Vol
Policy estimation ( + (IKSSTA(rO,8s.5)) - Ta(a]s) Graody(ro(s.a)
Demonstration
Roll-out
for h 1.2......, do
1. Roll-out stochastic policy π. for H steps from demonstration
Qt (of.a)-ro((s.. e (())(s) + + a. (b) (s.a)
end for
(als)) (x.)
T.
[ (T.)) (To)
Equation 3
Ro Roll-out no -Td
P0 <- Rollout T ,T)
Pr Rollout 12:000 pt
Initial distrib.
Roll-out
Vof + --E
Ex.a( (p5% (sa
Return: Vof
2. Continue roll-out with deterministic policy a
Figure 3: RHIP rolls out the computationally expensive stochastic policy for H steps from the demon- stration path before transitioning to the cheaper deterministic policy ma, as described in Equation 3
DUKSTRA A computes the highest reward path from state to under rg. Greedy(QU) (((((()(())))))))))))))))))))))) { the deterministic policy that selects the action with the highest Q- value. Rollout (T. = pm computes the state-action distribution n from rolling out the policy ı from the initial state distribution p² until convergence the destination Sd-
Receding Horizon Inverse Planning (RHIP) In this section, our key insight that classic IRL algorithms exhibit trade-off between the use of cheap, deterministic planners (e.g. MMP (Ratliff al., 2006)) and the use of expensive yet robust stochastic policies (e.g. MaxEnt (Ziebart al., al.. 2008)). This insight reveals novel generalized algorithm that enables fine fine-graing ree-ggained control over performance characteristics and provides new view on classic methods.
First, T. denote the stochastic policy after H steps of MaxEnt+ and ma denote the deterministic policy that follows highest reward path, i.e. (a(as)) E {0,1). Let Tx.a denote the set of all paths which begin with state-action pair (s,a). We introduce new policy defined by
H
T <a)s)<x
Σ Ta(TH+1)
II h=1
T. (a(aa(8))
TET..s
Deterministic policy
Stochastic policy
The careful reader will notice that Equation 3 reduces to classic IRL algorithms for various choices of H. For ==o0 reduces to MaxEnt++, for H it reduces to BIRL (Ramachandran and Amir, 2007). and for H-0 it reduces to MMP (Ratliff al., 2006) with margin terms absorbed into rgg (see Oppendix[Cfoor details).
We call this generalization Receding Horizon Inverse Planning (RIIIP, pronounced rip). As described in A RIIP performs H/ backup steps MaxEnt++, rolls out the resulting stochastic policy n, for H steps, and switches to rolling out the deterministic policy T. until reaching the destination. The reced- ing horizon H controls RHIP's compute budget by trading off the number of stochastic and deterministic steps. The stochastic policy π, is both expensive to estimate (backward pass) and roll-out (forward pass) compared to the deterministic policy wa, which can be efficiently computed via Dijkstra's 's a algorithm.
5

---

Published as a conference paper at ICLR 2024
Table 1: Route quality of manually designed and IRL baselines. Due the high computational cost of training the global model (bottom rows), we also evaluate in smaller, more computationally tractable of metros (top section). Metries are NLL (negative log-likelihood), Acc (accuracy, i.c. perfect route match) and IoU (Intersection over Union of trajectory edges). Numbers in bold are statistically significant with p-value less than .12 (see Appendix D.3). Two-wheeler data is unavailable globally.
Drive
Two wheelers
Policy class
Reward
NLL
Acc
IoU
NLL
Acc
loU
ETA
Linear
.4344
.6566
.4506
.7050
ETA+penalties
Linear
.4744
.6823
.475
.7146
MMP/LEARCH (34, (34,35)
Linear
.4444
.6531
.6887
.7054
SparseLin
.4853
.7069
.5233
.7457
Deep LEARCH [29]
DNN
.4241
.6532
.4777
.7141
DNN+SparseL.n
.4682
.6781
.5220
.7300
BIRL [IRL[19,2]]
Linear
3.933
.4524
.6945
3.629
.4933
.7314
Sparsel.in
26.840
.4900
.7084
8.975
.5375
.7508
Deep BIRL.
DNN
3.621
.6677
.6958
3.308
.4973
.7340
DNN+SparseLin
2.970
.4988
.7063
2.689
.5546
.7587
MaxEnt [53], +axEnt++
Linear
4.4409
.4521
.6941
3.957
.4914
.7293
SparseLin
26.749
.4922
.7092
8.876
.5401
.7522
Deep MaxEnt [46]
DNN
3.729
.4544
.6864
3.493
.4961
.7308
DNN+SparseLin
2.889
.5007
.7062
2.920
.5490
.7516
RHIP
Linear
3,930
.4552
.6965
3.630
.4943
.7319
SparseLin
26.748
.4926
.7095
8.865
5408
.7522
DNN
3.590
.4226
.6955
3.295
5000
.7343
DNN+SparseLin
2.881
.5030
.7086
2.661
.5564
.7591
Global ETA
Linear
.3891
.6538
Global ETA+penalties
Linear
.4283
.6907
Global RHIP
DNN+SparseLin 8.194
.4958
.7208
Graph compression We introduce two graph compression techniques to reduce both the memory footprint and FLOP count across all IRL. algorithms.. The graph adjacency matrix represented by B x S x V tensor, where entry (b,s,v) contains the reward of the v' o'th edge emanating from node s in batch sample Thus, is the maximum node degree valency, and nodes with fewer than V outgoing edges are padded. For many problems, V is tightly bounded, e.g. typically V 10 in road networks. First, we perform lossless compression by 'spliting' nodes with degree close to V into multiple nodes with lower degree. Since the majority of nodes have much smaller degree than V. this slightly increases but can significantly decrease the effective V, thus reducing the overall tensor size BSV in lossless fashion. Second, perform lossy compression by 'merging' nodes with single outgoing edge into its downstream node as there is only one feasible action. Feature vectors of the merged nodes summed, which is lossless for linear re but introduces approximation error the nonlinear setting. Intuitively, these compression techniques balance the graph's ' node degree distribution to reduce both the tensor padding (memory) and FLOP counts.
EMPIRICAL STUDY
Road graph Our 200M state MDP is created from the Google Maps road network graph. Edge features contain predicted travel duration (estimated from historical traffic) and other relevant static road properties, including distance, surface condition, speed limit, name changes and road type.
Demonstration dataset Dataset D contains de-identified users' trips collected during active navigation mode (Google, 2024). We filter for data quality by removing trips which contain loops, have poor GPS quality, or are unusually long. The dataset is fixed-size subsample of these routes, spanning a period of two weeks and evenly split into training and evaluation are created for driving and two-wheelers, with the two-wheeler (e.g. mopeds, scooters) dataset being significantly smaller than the drive dataset due smaller region where this feature available. The total number of iterated training and validation demonstration routes are 1 110M and 10M, respectively. See Appendix D for details.
based date. Separate datasets

---

Published as a conference paper at ICLR 2024
Preferred route
Detour route
HALF
Open gate
Figure 4: Example of the 360M parameter sparse model finding and correcting a data quality error in Nottingham. The preferred route is incorrectly marked private property due to the presence of a gate (which is never closed), and incorrectly incurs a high cost. The detour route is long and narrow. The sparse model learns to correct the data error with large positive reward on the gated segment. Additional examples are provided in Appendix D
Experimental region Due to the high computational cost of training the global model, we perform initial hyperparameter selection on smaller set of experimental metros (Bekasi, Cairo, Cologne, Kolkata, Manchester, Manila, Nottingham, Orlando, and Syracuse). The top-performing configuration used to train the global driving model. Two-wheeler data is unavailable globally and thus not reported.
Baselines We evaluate both manually designed and IRL baselines. For fixed baselines, we consider (1) ETA: The fastest route, i.e. edge costs are the predicted travel duration and (2) ETA+pena lties: ETA plus manually-tuned penalties for intuitively undesirable qualities (e.g. u-turns, unpaved roads), delivered to us a closed form without visibility into the full set of underlying features. For IRL. policy baselines, we compare MaxFnt (Al (Algorithm 2) (Ziebart et al., 2008), Deep MaxFnt (Wulfmeier et al., 2015), the LEARCH (Ratliff et al., 2009) variation of MMP (Ratliff et al., 2006 (Algorithm 4 Deep LEARCH (Mainprice et al. 2016 and the maximum posteriori variation of BIRL (Choi and Kim, (Algorithm 3p.
2011
We also consider a deep version of BIRL similar to Brown and Niekum (2019).
Reward model descriptions We evaluate three MoE function approximator classes: (1) a simple linear model, (2) dense neural network (DNN) and (3) an f1-regularized reward parameter for every edge in the graph (SparseLin). The latter is of particular interest because it tends highlight
data-quality issues, for example in Figure 4 These models have 3.9k, 144k, and 360M global parameters, respectively. We constrain model weights to produce non-positive rewards and fine-tune all models from the ETA+ 1 cies baseline. DNN*SparseL.in indicates additive DNN and SparseLin components. See Appendix D.2 for details.
Metrics For serving online routing requests, we are interested in the highest reward path from 8o to 8a path under rg (and not a probabilistic sample from æ or a margin-augmentter highest reward path). For accuracy, route is considered correct if it perfectly matches the demonstration route. Intersection over Union (IoU) captures the amount of overlap with the demonstration route, and is computed based on unique edge ids. Negative eegliiellhood (NLL) loss is reported where applicable.
5.1 RESULTS
We train the final global policy for 1.4 GPU-years on large cluster of V100 machines, which results in a significant 15.9% and 24.1 % increase in route accuracy relative to the ETA+pena 1 ies baseline models for driving and two- wwo-wheelers, respectively. As shown in T this RHIP policy with the largest 360M parameter reward model achieves state-of-the. art results with statistically significant accuracy gains of 0.4% and 0.2% compared the next-best driving and two-wheeler IRL policies, respectively.
We observe dynamic programming convergence issues and large loss spikes in MaxEnt which tend to occur when the rewards become close to zero. In Appendix B we prove this phenomena occurs precisely when the dominant eigenvalue of the graph drops below critical threshold of I (briefly noted in Ziebart (2010) pg. 1 117)) and show the set of allowable 0 is provably convex in the linear case. Fortunately, we able manage the issue with careful initialization, learning rates, and stopping conditions. Note
7

---

Published as a conference paper at ICLR 2024
Graph
Steps
0.454
RHIP (sweop H1
N
V
NLL
Acc
compression
per sec
None
124,402
4.9
.373
9.371
.454
Acoreey
0.453
Split
125,278
3.0
.412
9.376
.455
Merge
84,069
4.9
.843
9.381
.455
Maxbat
Split+Merge
84,944
3.0
.993
9.389
.455
0.452
200
Training steps per
Figure 5: Impact of the horizon accuracy and training time. H = 10 has the highest accuracy and trains 70% faster than MaxEnt.
Table 2: Graph compression improves training time by
2. 2.7x with insignificant impact on route quality metrics.
that RHIP (for H co), BIRL and MMP provably do not suffer from this issue. All value functions (Algorithms) D and are computed in log-space to avoid significant numerical stability issues.
We empirically study the trade-off between the use of cheap, deterministic planners and more robust yet expensive stochastic policies in Figure 5] As expected, MaxEnt has high accuracy but is slow train due to expensive dynamic programming, and MaxEnt+ + 16% faster with no drop in accuracy. RHIP enables realizing broad set of policies via the choice of H. Interestingly, both the best quality routes and 70% faster training times than MaxEnt, i.e. MaxEnt is not on the Pareto front. We hypothesize this occurs due improved policy specification. BIRL and MaxEnt assume humans probabilistically select actions according to the highest reward path or reward of all paths begin- ning with the respective state-action pair, respectively. However, in practice, humans may take mixed approach- considering all paths within some horizon, and making approximations beyond that horizon.
find that H H=10 provides
Table[[shows shows the impact of graph compression in our experimental region. The sp1 it strategy is lossless (as expected), and the sp1. tmeegge strategy provides significant 2.7x speed-up with almost no impact on route quality metrics. All empirical results take advantage of the sp 1 i tt-merr rge graph compression. We find that data structure choice has significant impact training time. We try using unpadded, coordinate format (COO) sparse tensors to represent the graph adjacency matrix, but profiling results in initial test metro of Bekasi show it to be 50x slower.
In Figure we study the local geographic preferences learned by each expert in the mixture by performing an out-of-region generalization test. The drop in off-diagonal performance indicates the relative significance of local preferences. In Figure we examine the relationship between region size and the performance of the model. Accuracy is nearly constant with respect to the number of states. However, training is significantly faster with fewer states, implying more equally sized regions would improve computational load balancing.
Negative results We study several other ideas which, unlike the above contributions, do not mean- ingfully improve scalability, First, the MaxEnt backward pass is equivalent to applying power iteration to solve for the dominant eigenvector of the graph (Equation 4). Instead of using power iteration (Al- gorithm 2). consider using Arnoldi iteration from ARKACK (Lehoueq et 1198), but find it to be numerically unstable due to lacking a log-space implementation (see results Appendix A.II. Second, the forward pass used in MaxEnt has closed form solution via the matrix geometric series (Equation()). Using UMFPACK (Davis, 2004) to solve for this solution directly is faster on smaller graphs containing up around 10k nodes, but provides no benefit on larger graphs (see results in Appendix A..2) A.2)
DISCUSSION
Future research We study multiple techniques for improving the scalability of IRL and believe there exist several future directions which could lead to additional gains. First, demonstration paths with the same (or nearly the same) destination can be merged together into a single sample. Instead of performing one IRL backward and forward pass per mini-batch sample, we can now perform one iteration per destimation. This enables compressing large datasets and increasing the effective batch size, although reduces shuffling quality, i.e. samples are correlated during training. Second, the graph could be pruned by removing nodes along 'reasonable' path (i.e. within some margin of
8

---

Published as a conference paper at ICLR 2024
accuracy
Barcelona
0.0
6.0
-2.8
-3.7
-9.1
40%
Accurccy to basellls
Enschede
1.5
0.0
1.7
3.8
3.1
30%
Training region
Notinggtam
20%
0.4
2.8
0.0
1.0
4.4
10%
Strasbeorrg
0.4
3.3
-0.1
0.0
2.5
-2
0%
Syracuse
-02
0.7
1.2
22
0.0
Barcelona
Ensetede
Nottnghom
Strabburg
Syracuse
200k
400k
800k
1.6M
Nomber states
Evaluation region
Figure 6: Sparse mixture-of-cxperts learn prefer- ences specific to their geographic region, demon- strated by the drop in off-diagonal performance.
Figure 7:
Region accuracy for each expert in the worldwide mixture. Performance is consistent across the state space size.
the current best path) from 8 to Sa (Ziebart, 2010 pg. 119). However, this may be difficult to do in practice since the pruning is unique for every orgtinndetination pair.
From accuracy perspective, we find that the sparse mixture-of-expert learn routing preferences specific to geographic regions. This vein could be further pursued with personalization, potentially via hierarchical model (Choi and Kim, 2014 Choi and Kim, 2012). Due engineering constraints, we use static ETA predictions, but would like to incorporate the dynamic GraphNet ETA predictions from Berrow-Pinion et al. (202T). We find that sparse reward models tend highlight groups of edges which were impacted by the same underlying data quality issue. A group lasso penalty may be able leverage this insight. Including human domain knowledge may robustify and help shape the reward function (Wulfmeier et al., 2016a Wulfmeier et al., 2017). In this paper, we evaluate performance on driving and weo-wheelers, and would like incorporate other modes of transportation especially walking and cycling but are limited by engineering constraints.
Extensions to other MDPs For expository purposes, we restrict attention to discrete, deterministic, and undiscounted MDPs with single self-absorbing destination state. Our contributions naturally extend to other settings. MaxEnt++ and RIIIP can be applied to any MDP where MaxEnt is appropriate and (.) can be (efficiently) computed, e.g. via Dijkstra's. ss Our parallelization extends to all MDPs with reasonable partition strategy, and the graph compression extends stochastic MDPs (and with further approximation, discounted MDPs).
Limitations IRL limited by the quality of the demonstration routes. Even with significant effort to remove noisy and sub-optimal routes from D. our policy will inadvertently learn some rewards which do not reflect users' true latent preferences. Our MoE strategy based on geographic regions, which limits the sharing of information across large areas. This could be addressed with the addition of global model parameters. However, the abundance demonstrations and lack of correlation between region size and accuracy (Figure 7) suggests benefits may be minimal.
7 CONCLUSION
Increasing performance via increased scale both in terms of dataset size and model complexity has proven be persistent trend in machine learning. Similar gains for inverse reinforcement learning problems have historically remained elusive, largely due to additional challenges posed by scaling the MDP solver. We contribute both (a) techniques for scaling IRL to problems with hundreds of millions of states, demonstration trajectories, and reward parameters and (b) novel generalization that enables interpolating between classic IRL methods and provides fine-graing and planning time trade-offs. Our final policy is applied in a large scale setting with hundreds of millions of states and demonstration trajectories, which to the best of our knowledge represents the largest published study of IRL algorithms in a real- world setting to date.
control over accuracy

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We gratefully acknowledge the contributions of Renaud Hartert, Rui Song, Thomas Sharp, Rémi Robert, Zoltan Szego, Beth Luan, Brit Larabee and Agnieszka Madurska towards early exploration of this project for cyclists. Arno Eigenwillig provided useful suggestions for the graph's 's padded data structure, Jacob Moorman provided insightful discussions on the theoretical aspects of eigenvalue solvers, Jonathan Spencer provided helpful references for MaxEnt's theoretical analysis, and Ryan Epp explored the feasibility of an alternative approach to re-rank small set of candidate routes. We are thankful for Remi Munos', Michael Bloesch's ss Arun Ahuja's 's and the anonymous reviewers' feedback on final iterations of this work.
ETHICS STATEMENT
We strongly support open-sourcing experiments when legally and ethically permissible. The routing dataset used in this paper - and likely any routing dataset of similar scope cannot be publicly released due to strict user privacy requirements.
REFERENCES
Abbeel, Pieter al. (2008). "Apprenticeship Learning for Motion Planning with Application to Parking Lot Navigation". In: International Conference on Intelligent Robots and Systems.
Arthur, David and Sergei Vassilvitskii (2006). k-means+ The Advantages of Careful Seeding.
Baker, Chris L, Rebecca Saxe, and Joshua B Tenenbaum (2009). "Action Understanding as Inverse Planning". In: Cognition.
Barto, Andrew G, Steven J Bradtke, and Satinder P Singh (1995). "Learning to Act using Dynamic Programming". In: Artificial Intelligence.
Boyd, Stephen and Lieven Vandenberghe (2004). Convex Optimization. Cambridge University Press.
Brown, Daniel S. and Scott Niekum (2019). "Deep Bayesian Reward Learning from Preferences". In: ArXiv.
Chan, Alex J. and Mihaela der Schaar (2021). "Scalable Bayesian Inverse Reinforcement Learning"". In: International Conference on Learning Reprexentations.
Choi, Jaedeug and Kee-Eung Kim (2011). "MAP Inference for Bayesian Inverse Reinforcement Learning." In: Neural Information Processing Signals.
(2012). "Nonparametric Bayesian Inverse Reinforcement Learning for Multiple Reward Functions". In: Neural Information Processing Systems.
(2014). "Hierarchical Bayesian Inverse Reinforcement Learning".. In: IEEE Transactions on Cyber- netics.
Davis, Timothy A (2004)." "Algorithm 832: UMFPACK V4.3 an Unsymmetric-ppateem Multifrontal Method". In: ACM Transactions on Mathematical Software (TOMS).
Derrow-Pinion, Austin al. (2021). "ETA Prediction with Graph Neural Networks in Google Maps". In: International Conference on Information & Knowledge Management.
Difference of Proportion Hypothesis Test (2009). URL: https::/tttt nist..is..... gov//
Finn, Chelsea, Sergey Levine, and Pieter Abbeel (2016a). "Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization". In: International conference machine learning.
Finn, Chelsea et al. (2016b). "A Connection Between Generative Adversarial Networks, Inverse Reinforcement Learning, and Energy-Based Models". In: 1..0021611.03852.
10

---

Published as a conference paper at ICLR 2024
Fu, Justin, Katie Luo, and Sergey Levine (2018). "Learning Robust Rewards with Adversarial Inverse Reinforcement Learning". In: International Conference on Learning Representations.
Garg, Divyansh al. (2021). "IQ-Learn: Inverse Soft- Soft-Q Learning for Imitation". In: Neural Information Processing Systems.
Geisberger, Robert et al. (2012). "Exact Routing Large Road Networks using Contraction Hierar- chies". In: Transportation Science.
Google (2024). How Navigation Data Makes Maps for Everyone. URL: httpttttts::pppppooe google
Ho. Jonathan and Stefano Ermon (2016). "Generative Adversarial Imitation Learning". In: Neural Information Processing Systems.
Horn, Roger A. and Charles R. Johnson (2012). Matrix Analysis. Cambridge University Press.
Hubbard, John H. and Barbara Burke Hubbard (2003). "Vector Calculus, Linear Algebra, and Differen- tial Forms: A Unified Approach". In: The American Mathematical Monthly.
Imani, Mahdi and Ulisses M. Braga-Neto (2019). "Control of Gene Regulatory Networks using
Bayesian Inverse Reinforcement Learning". " In: Transactions on Computational Biology and Bioin- formatics.
Kalman, R. E. (1964). "When is a Linear Control System Optimal?" In: Journal of Fluids Engineering. Transactions of the ASME.
Ke, Liyiming et al. (2021). "Imitation Learning as f-divergence Minimization". In: Algorithmic Foundations of Robotics.
Kingman, J.F.C. (1961). "A Convexity Property of Positive Matrices", In: The Quarterly Journal of Mathematics.
Kitani, Kris M. al. (2012). "Activity Forecasting". In: European Conference on Computer Vision.
Kostrikov, Iya, Ofir Nachum, and Jonathan Tompson (2020). "Imitation Learning via Off-policy Distribution Matching". In: International Conference on Learning Representations.
Lehoucq. Richard B, Danny C Sorensen, and Chao Yang (1998). Users' Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods.
MacGlashan, James and Michael Littman (2015). "Between Imitation and Intention Learning". In: International Joint Conference on Artificial Intelligence.
Mainprice, Jim et al. (2016). "Functional Nanifold Projections in Deep-LEARRCH.. In: NewrIPS Workshop Neurorobotics.
Michini, Bernard, Mark Cutler, and Jonathan How (2013). "Scalable Reward Learning from Demon- stration". In: International Conference on Robotics and Automation.
Osa, Takayuki et al. (2018). "An Algorithmic Perspective on Imitation Learning". In: Foundations and Trends in Robotics.
Ramachandran, Deepak and Eyal Amir (2007). "Bayesian Inverse Reinforcement Learning." In: International Joint Conferences on Artificial Intelligence.
Ratliff, Nathan D., Andrew Bagnell, and Siddhartha S. Srinivasa (2007). "Imitation Learning for Locomotion and Manipulation", In: International Conference on Humanoid Robots.
Ratliff, Nathan D., Andrew Bagnell, and Martin A. Zinkevich (2006). "Maximum Margin Planning".
In: International Conference on Machine Learning.

---

Published as a conference paper at ICLR 2024
Ratliff, Nathan D., David Silver, and J. Andrew Bagnell (2009). "Learning to Search: Functional
Gradient Techniques for Imitation Learning.. In: Autonomous Robots.
Rhinehart, Nicholas and Kris M. Kitani (2020). "First-Person Activity Forecasting from Video with Online Inverse Reinforcement Learning". In: Transactions on Pattern Analysis and Machine Intelli- gence.
Ross, Stéphane and Drew Bagnell (2010). "Efficient Reductions for Imitation Learning". In: Interna- tional Conference on Artificial Intelligence and Statistics.
Ross, Stéphane, Geoffrey Gordon, and Drew Bagnell (2011). "A reduction of imitation learning and structured prediction to no-regret online learning". In: International Conference on Artificial Intelligence and Statistics.
Rust, John (1994). "Structural Estimation of Markov Decision Processes". In: Handbook of Economet- rics.
Shazeer, Noam al. (2017). "Outragcously Large Neural Networks: The Sparsely-Gated Mixture-of- Experts Layer". In: International Conference on Learning Representations.
Swamy, Gokul et al. (2021). "Of Moments and Matching: A Game-Thhoretti Framework for Closing the Imitation Gap". In: International Conference on Machine Learning.
Swamy, Gokul (2023). "Inverse Reinforcement Learning without Reinforcement Learning". In: International Conference on Machine Learning.
Tastan, Bulent and Gita Sukthankar (2011). "Learning Policies for First Person Shooter Games using Inverse Reinforcement Learning" In: Conference on Artificial Intelligence and Interactive Digital Entertainment.
Trefethen, Lloyd N. and David Bau (1997). Numerical Linear Algebru. SIAM.
Tucker, Aaron, Adam Gleave, and Stuart Russell (2018). "Inverse Reinforcement Learning for Video Games". In: arXiv: 10593.
Wasserman, Larry (2004). All of Statistics: A Concise Course in Statistical Inference. Springer.
Wulfmeier, Markus, Peter Ondruska, and Ingmar Posner (2015). "Maximum Entropy Deep Inverse Reinforcement Learning". In: arXiv::507. 04888.
Wulfmeier, Markus, Dushyant Rao, and Ingmar Posner (2016a). "Incorporating Human Domain Knowledge into Large Scale Cost Function Learning... In: ArXiv.
Wulfmeier, Markus, Dominic Zeng Wang, and Ingmar Posner (2016b). "Watch This: Scalable Cost- function Learning for Path Planning in Urban Environments". In: International Conference on Intelligent Robots and Systems.
Wulfmeier, Markus et al. (2017). "Large-scale Cost Function Learning for Path Planning using Deep inverse reinforcement Learning". In: The International Journal of Robotics Research.
Xing, Yue, Qifan Song, and Guang Cheng (2021). "On the Algorithmic Stability of Adversarial Training". In: Neural Information Processing Systems.
Yu, Chao, Guoqi Ren, and Jiming Liu (2019). "Deep Inverse Reinforcement Learning for Sepsis Treatment". In: International Conference on Healthcare Informatics.
Ziebart, Brian D. (2010). "Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy".
Ziebart, Brian D. et al. (2008). "Maximum Entropy Inverse Reinforcement Learning". In: AAAI Conference Artificial Intelligence.
12

---

Published as a conference paper at ICLR 2024
Appendix for "Massively Scalable Inverse Reinforcement Learning in Google Maps"
Notation
Let R.E ||S|X|
be the sparse reward matrix defined by Ru, -re (8).8)).
A NEGATIVE RESULTS
In this section, we provide negative results for two ideas to improve MaxEnt's scalability. We used a synthetic Manhattan-style street grid (i.e. GridWorld) in order to conduct controlled sweeps over the number of nodes. Edge rewards were fixed at constant values.
A.1 ARNOLDI ITERATION
The backward pass in MaxEnt is equivalent to performing power iteration to compute the dominant eigenvector of the graph
Aij Ru.
(4)
We attempted to use Arnoldi iteration, implemented in ARPACK, but found it to be numerically unsta- ble due to lacking a log-space version (Lchoueq et al.. 1998). In typical eigenvector applications, one concerned with the reconstruction error ||z- where = e" is eigenvector estimate of A. How- ever, in MaxEnt we are uniquely concerned with relative error between entries in rows of Q= Rt+ 1-0T, since this determines the policy = softmax(()) We found log-space reconstruction error [|o]|//))>)))))))) log(=))] to be far more significant in MaxEnt. As seen in Figure Arnoldi iteration's reconstruction error in linear space is reasonable, but quickly blows up in log space, unlike log-space power iteration.
10
[[log(Az) - logg2))
10
10-11-
||Az - z||
10
10-13
10-10
10-15-
10-13
Arnoldi Iteration
Log power Iteration
20
Number nodes
Number of nodes
Figure 8: Solving for the dominant eigenvector in the MaxEnt backward pass.
From a geometric perspective, this phenomena can be observed by examining eigenvector estimates in Figure Due the MDP structure containing a single absorbing zero-reward destination node, cigenvector entries z rapidly decay as one moves further away from the destination sa. Thus, the typical reconstruction error - is primarily a function of handful of nodes near the destination. Visually, Arnoldi and log-space power iteration appear to provide similar solutions for z. However, examining log(z) (2) reveals that log-space power iteration able gracefully estimate the exponentially decaying eigenvector entries. Arnoldi iteration successfully estimates the handful of nodes near sa. but further nodes inaccurate and often invalid (white spaces indicate and thus log(2) is undefined).
13

---

Published as a conference paper at ICLR 2024
10
D
D
0.6
0.2
D
D
-10
-20g
-25
-30
-40
(a) Log power iteration
(b) Amoldi iteration
Figure 9: Eigenvector estimates on 10 GridWorld enviromment for origin O and destination D.
A.2 MATRIX GEOMETRIC SERIES
The MaxEnt forward pass a matrix geometric series with the closed-font form solution defined in Equation 6 Instead of iteratively computing the series, used UMFP ACK to directly solve for this solution. As shown in Figure I0, this worked very well for graphs up to approximately 10k nodes, but provided no further benefit beyond this point. Neither approach had numerical stability issues.
Forward pass
10a
-
Rterative (CPU)
10
-
Closed form
Time (seconds)
10a
10:1
10
10a
10a
10
20a
10*
Number nodes
Figure 10: Closed-fome solution of the MaxEnt forward pass using UMFPACK.
A.3 NEGATIVE DESIGNS
We dismiss two other designs based on key pieces of evidence, First, we could learn to rerank the ~ routes returned by the Maps API (the approach taken by Ziebart et al. (2008)). This is trivial solution to scale, but significantly reduces the route accuracy headroom. The API returns handful of candidate routes from s, sa, which then form T,e.g. Equation 2 Equation 3 Instead of learning the best route
14

---

Published as a conference paper at ICLR 2024
from set of infinitely many routes, IRL now learns the best route among ~5. In many cases, the desired demonstration is often not among this set, and thus impossible to select an online setting. Second, could train in smaller geographic region and deploy worldwide. Not only does this preclude the use of the best-performing 360M parameter sparse reward function (as its parameters are unique to each edge), Figure inddictsss this would suffer from generalization error for other choices of ra-
B MAXENT THEORY
In this section, we provide theoretical results on MaxEnt, which are summarized here for convenience:
MaxEnt has finite loss if and only if the dominant eigenvalue Amax of the graph This was briefly noted in Ziebart (2010) pg. 117)), which we discovered after preparation of this publication.
Theorem B.1
is less than I.
Theorem
B.2
The set of finite losses convex in the linear setting.
Theorem B.3
The convergence rate of the backward pass is governed by the second largest
eigenvalue.
Figure [1 illustrates the first two phenomena on simple didactic MDP. Intuitively, there are two counteracting properties which determine the transition between finite and infinite loss. First, the number of paths of length n++ is larger than the number of paths of length n. This tends to accumulate probability mass on the set of longer paths. Second, paths of length n r have on average lower per- per-path reward, and thus lower per-path probability, than paths of length n. This favors the set of shorter paths. The question is, does the per-path probability decrease faster than the rate at which the number of paths increases? If yes, then the dominant eigenvalue is 1, the forward pass converges, and the loss is finite. If no, then the dominant eigenvalue is greater than the forward pass never converges, and loss infinite. As expected, infinite loss occurs in regions of high edge rewards, which agrees with Figure 11
B.1 PRELIMINARIES
Let A.j e be the elementwise exponential rewards. We restrict our attention to linear reward functions R.j (Txa; where Fij is set of edge features between nodes and j. If no edge exists between nodes and j. then the reward is negative infinite and Aij = O. Without loss of generality, we assume the destination node is the last row in A. Thus, A is block upper triangular (also called the irreducible normal or Frobenius normal form)
B 0
A=
B2
where Bi contains all the non-destination nodes and B2 is the self-absorbing destination node. B, and B2 both strongly connected (thus irreducible) and regular. B2 has a single eigenvalue Amax (B₂) = 1, and by the Perron-Frobennin theorem B3 has a dominant real eigenvalue Amax (B)) (called the Perron-Frood Froron-Foo eigenvalue of B1).
Likewise, we express an eigenvector of A
B1 0
21
21
B2
22
=
22
(5)
and the MaxEnt policy transition matrix as
P
π
0
P2
where Pa (==1] corresponds to the self-absorbing edge at the destination, and P1 corresponds to all other nodes.
The MaxEnt backward pass is unnormalized power iteration. After & iterations, = = A where I, is the one-hot vector at the destination node. This exactly (unnormalized) power iteration.
Likewise, the forward pass is a matrix geometric series. The fundamental matrix S (J. Hubbard and B. B. Hubbard, 2003) is defined as
5=1+P
(I-PP)
15

---

Published as a conference paper at ICLR 2024
01
51
0r
O2
02
(a) Simple MDP
30
20
3.0
25
25
18
28
200
20
26
6
144
24
12
0.5
22
0.0
100
0.0
0.5
10
155
2.0
25
3.0
0:
82
(b) Dominant eigenvalue
(c) MaxEnt loss
Figure 11: Demonstration our claims on a simple MDP. (a) The deterministic MDP with absorbing destination node sa, and parameterized edge costs (i.e. negative reward) 0 and 02. (b) The dominant eigenvalue of the graph as a function of 9. Note the set of parameters θ= @6 1mlx((e (f]==]] is convex. (c) The corresponding MaxEnt loss (for dataset with demonstration paths - $2 and $2 > 81 + sa). As explained by our theory, the loss is finite and convex when Amax = and infinite when Amax 1.
Then the forward pass is simply UJ S, where T. is the one-hot vector at the origin. If Pi is sub-stochastic, then the series converges and (1) is nonsingular. With these preliminaries, we now proceed to our main results.
B.2
MAIN RESULTS
Theorem B.1. {(0) < oo iff A has dominant eigenvalue of 1.
Proof. The spectrum A, denoted a (A), is the union of (B,) and (B2), including multiplicities Thus, there are three possible cases:
1. Case 1: Amax (B1) < 1. In this case, there exists a dominant eigenvector with eigenvalue from B3. This eigenvector must satisfy 22 > (proof by contradiction: assume 22 then B र1 = which contradicts Xmax (B1) < 1). Since > 0, P1 is substochastic (there is some probability of transitioning the destination node), the matrix geometric series (I+P)+ P22 +...) converges, and the loss is finite.
(
"by 8.3.P8 in Horn and Johnson (2012
16

---

Published as a conference paper at ICLR 2024
2. Case 2: Amax ( (B1 1. There exists dominant eigenvector with eigenvalue Amax [B ). Then by Equation 5 22 must equal zero. By the MaxEnt policy definition, the policy will never transition to the destination (ΛAN 0 vř * N), the forward pass geometric series diverges, and thus {()) =00
3. Case Amax (Bi) = 1. This determines whether the set is open or closed. We do not address this question in this paper, although we strongly suspect the set is open.
In both Cases and 2, there exists a dominant eigenvector. By standard power iteration analysis, the MaxEnt backward pass is guaranteed to converge to this dominant eigenvector. The MaxEnt loss { finite in Case when has a dominant eigenvalue of and infinite in Case 2.
Computing the dominant eigenvalue may be expensive. Fortunately, is often possible cheaply verify Case holds by use of the following simple inequalities
Xmaa (1) I <maxr;
Σ B1.i5 maxx,
Amax (B1) < maxc;
Σ B1,ij maxc,
where r; - -, Bi and E, are the row and column sums, respectively.
Theorem B.2. == < <o) is an open convex set.
Proof.
From the proof of Theorem B.I have the equivalence
+ = (0: Amaa (B) 1)}-
Let
Amaa (B))==(((((((()
where
Definition
Name
Relevant properties
f(0)=X0 X0
Edge rewards
Linear
-
Elementwise exponential
Convex, increasing Log-convex, increasing
((Bi)=Amax((
Dominant eigenvalue
The only non-obvious fact is that h is convex and increasing. Log- log-convexity follows from Kingman (196I). is increasing by the Frrron-Foobenuus theorem for non-negne non-negative irreducible matrices.
The proof follows standard convexity analysis (Boyd and Vandenberghe, convex since f is convex and is convex and increasing. The function hogo is convex since go f is convex and is convex and increasing. Finally, since Xuaax (Br) 1B)==hha hogo is convex in 0, the sublevel set in Equation 7 also convex.
The function go f
Theorem B.3. The error of the MaxEnt backward pass after k iterations
A2 &
[|2(k) ((6))=l1=00
(8)
A1
where X1 is the dominant eigenvalue of A (Ai 1 in Case 1), and X2 < A1 is the second largest eigenvalue.
Proof. This follows directly from standard power iteration analysis, e.g. Theorem 27.1 in Trefethen and Bau (1997).
by Lemma 8.1.21 and 8.1.P7 in Homn and Johnson 2012
17

---

Published as a conference paper at ICLR 2024
B.3 PROOF OF EQUATION 2
In Section[4 we claim our MaxEnt-+ initialization is closer to the desired solution than the original MaxEnt initialization
min e"(r)
(((r)
s=Ba
MaxFan initialization
MaxEnt++ initialization
Solation
The MaxEnt initialization -ę= is zero everywhere, except at sd where equals one. The MaxEnt+ + initialization min,eT.... (t(r) is non-negative (due the exponent), and is equal one at 8a (since there is single, rero-reward, self-abborbing edge at the destination). Thus, the Max- Ent++ initialization upper bounds the MaxEnt initialization. The solution EreT..,, e²(r) upper bounds the MaxEnt++ initialization by the inequality fin (z), where f(x) 20 Vz.
Note the claim in Equation 2
stronger than claiming a smaller vector distance.
C BASELINE ALGORITHMS
In this section, summarize the baseline IRL algorithms and provide reductions from RHIP.
C.I MAXENT+ AND MAXENT
MaxEnt (Ziebart al., 2008 assumes softmax distribution over trajectories.
x(e)
(9)
(als) x Σ rr(r
(10)
TET...
where Ts.a is the set of all trajectories which begin with state-action pair (s,a). Computing the gradient of the log-likelihood of Equation Donuationnrrsuule results in dynamic programming Algorithm 2
Algorithm 2 +axEnt++ and MaxEnt
Input: Reward rg. demonstration 7 with origin 8, and destination sd
Output: Parameter update Vaf
# Policy estimation ((()(s) + DUKSTRA((T,S,sa))
Equation 2
The original MaxEnt uses logll[s = sa]
for h 1,2,.. do
gh) (s.a)) + To +
(s) - log LogE. (xp((m)) (1) (8,a)
end for
(xpo (e.a)
T
Taa
b Equation
Ro Roll-out policy
0 < Rollout(TT..))
Vol+ ES.a -
Return: Vof
The reduction from RHIP to MaxEnt follows directly from Equation with -= Recall n. is the MaxEnt++ policy after H iterations, and let no denote the fully converged MaxEnt++ policy
18

---

Published as a conference paper at ICLR 2024
(equivalent the fully converged MaxEnt policy)
< x
Σ
Td Tu(TH+1]
II
Te (4nl8))
RHIP
TETa.
1=1
Σ
To (anlsn)
rETs,ul=1
Σ (T)
MaxEnt++ and MaxEnt
TET..
The careful reader will notice subtle distinction between Algorithm (RHIP) and Algorithm 2 (MaxEnt). The former computes the gradient via Equation I0] whereas the latter computes the gradient via Equation[9] The resulting gradients are identical, however, the latter results in simpler algorithm. Mechanically, Algorithm I with H =o reduces to the simpler Algorithm 2 via telescoping series.
C.2 BAYESIAN IRL
Bayesian IRL (Ramachandran and Amir, 2007 assumes the policy follows the form
(als) x e (s.a)
(11)
where Q" (s.a) is the Q-function of the optimal policy. In our setting, Ta is the optimal policy, and thus Q" (s.a) is the reward of taking (s,a) and then following wa. i.e. Q()) in Algorithm Computing the gradient of the log- ligelikl of Equation resultss Algorithm
Algorithm 3 Bayesian IRL
Input: Reward rg. demonstration 7 with origin s, and destination
Output: Parameter update Vef
Backup policy
((s)+ DUKK-DUSTRR((rs.....
Q(s.a) - To (s(
TT 8) + expQ(s.a) expQ(saaa)
Equation I1
Ro ool-out policy
0 Rollout( p²)
0- + Rollout Pt.. +
Vof+ Ea (s..
Return: Val
The reduction from RHIP to BIRL directly follows from Equation with H=1.
(als) x
Σ
ma(Tn+1)
II
(ana())))
RHIP
TE....
h=1
Σ
Ta(TH+1)m
TTT...
Σ (an(s))
reTmana
Σ (I(al(s))
*ETH...e
= (10)) =" (s.a)
BIRL
where TH.,,a is the set of all paths which begin with a state-action pair (s,a) and deterministically follow the highest reward path after horizon H.
19

---

Published as a conference paper at ICLR 2024
C.3 MAX MARGIN PLANNING
Max Margin Planning (Ratliff al.. 2006; Ratliff et 2009) assumes loss & of the form
((0) - Σ o (s,a)ra(ss.) - max (s(sollr((s)))mm
(12)
Demonstration path reward
Margin highss reward
-E Pr
where T is the set of all paths from S, to 8g. m, is the margin term, and Tsp is the margin margin-augment augmented highest reward path, i.c. Tup = DUJKTRRA(To 57 (0 The resulting MMP algorithm is shown in Algorithm
Algorithm 4 Max Margin Planning (MMP)
Input: Reward re. demonstration 7 with origin 8, and destination
Output: Parameter update Vof
Estimate and roll-out policy
Prp t DUKSTRA(ro+tm,,5005.)
Equation 12
Vef 1eftDD PeftEnn EE (s..
Return: Vof
The reduction from RHIP to MMP is possible by directly examining Algorithm | with H = 0 and absorbing the margin term into the reward function, i.e. r0))) r(0) +, With H n. in Beginning with the p" pp term in Algorithm
Algorithm |
1 p Rollout(T2220.' pr Rollout(z,p")
RHIP
Rollout Rollout(TT..P.... + Rollout(Ta..F)
H=0
p (allout(TTa,500
Telescoping series MMP
Pr Pro
D EXPERIMENTS
D.1 DATASET
The demonstration dataset contains 110M and 10M training and validation samples, respectively. Descriptive statistics of these routes are provided below.
Travel model
Distance (km)
Duration (min)
Road segments per demonstration
Drive -ho-wheeler
9.7
13.3
99.3
3.0
8.3
47.4
Table 3: Dataset summary statistics
GPS samples are matched the discrete road graph using a hidden Markov model. For data cleaning, we relied on several experts who had at least years of experience in curating routing databases. This is similar data cleaning processes followed in prior work, for example in Derrow-Pinion et al. 2021
D.2 HYPERPARAMETERS
The full hyperparameter sweep used in Table [ (exlluding global result in bottom row) is provided in Appendix D.2
20

---

Published as a conference paper at ICLR 2024
Category Policy
Hyperparameter
Values
Applicable methods
Softmax temperature
10, 20, 30
MaxEnt, BIRL
Horizon
2, 10, 100
RHIP
Margin
0.1, 0.2,
MMP
Fixed bias
Margin+0.001
MMP
Reward model
Hidden layer width
18
DNN
Hidden layer depth
2
DNN
Initialization
(1=.02) * EETTTAAPPPEe *EAAteaalliess 0
Linear, DNN
Weight initialization
SparseLin
LI regularization
le-7
SparseLin
Optimizer
SGD learning rate
0.05, 0.01
Linear, DNN
Adam learning rate
le-5, le-6
Sparsel.in
Adam 31
0.99
SparseL.in
Adam $2
.999
SparseL.nn
Adam c
le-7
SparseLin
LR warmup steps
100
All
Training
Steps per epoch Batch size Epochs
100
All
8
All
200, 400 3
All
Data compression
Max out degree
All
Table 4: Hyperparameters.
The worldwide 360M parameter RIIIP model (bottom of Table the same parameters as Appendix D.2 except that we only swept over the horizon parameter in H E (10,100) and the SGD learning rate, for efficiency. Temperature fixed 30 for linear and 10 for sparse. Adam learning rate was fixed at 0.05.
D.3 STATISTICAL SIGNIFICANCE ANALYSIS The p-values for Table are computed as follows:
Accuracy We used a two-sided difference proportions test (Differnnce of Proportion Hypothesis Test 2009). Our validation set in the experimental region contains n= 360,000 samples. RHIP outper- forms the next-best drive and two two-wheeler policies by ,0023 (p-value=:051 and .0018 (p- valuee. 122), respectively. Note that since policies share validation set, the routes which they have a perfect match are not independent but likely positively correlated, making these estimates conservative.
IOU We used a Hoeffding bound to construct a confidence interval for the difference of loU scores (Wasserman, 2004). We find RHIP does not provide statistically significant improvement.
21

---

Published as a conference paper at ICLR 2024
D.4
ADDITIONAL RESULTS
Preferred route
Bad detour
(a) Spokane A road is incorrectly marked drivable. The correct route takes users through the designated drive-through, as desired. The sparse model learns to correct the data with large negative reward the flex-posts segment.
Smalle Pa
doys
(b) Syracuse Similar to Figure 4 except this road segment is occasionally closed. The longer detour follows several back roads and parking lots.
Examples of the 360M parameter sparse model finding and correcting data quality errors. Locations were selected based on the largest sparse reward magnitudes in the respective regions.
Figure 12:
22


Reviews:
[{"review_id": "nrvTPxRNDh", "reviewer": "Reviewer_5CwT", "summary": "This paper considers the important problem of Inverse Reinforcement Learning for route optimization and planning, and specifically the practical limitations of existing methods when scaled to larger problems. The authors draw a unified theoretical perspective around Max Margin planning (Ratliff et al. 2006), the classic MaxEnt framework (Ziebart et al. 2008), and Bayesian IRL (Ramachandran and Amir 2007) which is helpful and insightful. Connections with graph theory methods lead to a novel IRL initialization and algorithm (MaxEnt++ and Receding Horizon Inverse Planning) which demonstrates significant improvements over other methods for large-scale problems. Several other graph optimization methods are presented which further allow scaling to global-scale routing problems.\n\nThe paper is well written, clear to read (despite covering a lot of theory and background), and the experimental evaluations are thorough and provide support for the claims.\n\nI have a background in Inverse Reinforcement Learning theory, however have focused in other areas of computer science more recently, so may be out-of-touch with some recent literature results when performing this review. I have read the paper and appendices closely, however did not check the proofs carefully.", "questions": "# Questions and comments\n\n * Unclear notation - Paragraph 'Parallelism strategies' under Sec 4 defines the global reward based on the sharded MDP as $r(s,a) = r_{\\theta_i}(s,a),(s,a) \\in \\mathcal{M}_i$. This notation isn't clear to me - is there a typo here? Is this mean to be a product over the sharded individual reward functions?\n\n# Minor comments and grammatical points\n\n * Typo in footnote 1 - 'rouute'", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* A compelling problem\n * Real-world empirical experimental problem considered\n * The paper does a good job straddling both novel theory advancements, and practical and engineering advancements, but presents the findings appropriately for the ICLR audience.\n * The connections with graph theoretic results (App. A1, A2, and Theorem B3) are useful and insightful.\n * The paper and appendices include negative results, in addition to the main results - this is encouraging to see (more papers should do this).\n * [Note to ACs and other reviewers]: Although the proposed method is framed for discrete MDP-based route optimization, note that there are several ways to generalize this framework to other interesting problem settings quite trivially, (see e.g. [A]) - as such, the findings here are actually quite broadly applicable, as noted by the authors in Sec 6.\n\n# References\n\n * [A] Byravan, Arunkumar, et al. \"Graph-Based Inverse Optimal Control for Robot Manipulation.\" IJCAI. Vol. 15. 2015.", "weaknesses": "* The literature review is compact and the theory background provides a rapid but very nice summary of classical IRL results (in particular the unifying view of stochastic vs. deterministic policy trade-offs is helpful). One relevant piece of prior work that isn't mentioned however is the improved MaxEnt approach(es) by Snoswell et al. (e.g. [B, C]) - which address theoretical and empirical limitations with Ziebart's MaxEnt model, and are specifically applied to the problem of route optimization (albeit at city scale, not a global scale).\n\n# References\n\n * [B] Snoswell, Aaron. \"Modelling and explaining behaviour with Inverse Reinforcement Learning: Maximum Entropy and Multiple Intent methods.\" (2022).\n * [C] Snoswell, Aaron J., Surya PN Singh, and Nan Ye. \"Revisiting maximum entropy inverse reinforcement learning: new perspectives and algorithms.\" 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uRIKcYonvx", "reviewer": "Reviewer_nMaV", "summary": "This paper mainly focuses on scaling inverse reinforcement learning (IRL) for route optimization by learning the reward function from expert demonstrations. The application scenario is a popular route recommendation platform that should be able to generalize globally. Given a dataset of expert trajectories, in this approach, a reward function is learned from these demonstrations and this reward then guides an action selection policy from the start state to the destination. \n\nBuilding on prior work in IRL, particularly MaxEnt IRL, the authors propose an initialization strategy that leads to faster convergence, called MaxEnt++. Next, they generalize these and other IRL algorithms in their proposed framework called RHIP (Receding Horizon Inverse Planning) that trades-off using an expensive stochastic policy upto a horizon H with a cheap deterministic planner afterwards. Additionally, a number of parallelized computation and graph compression techniques are implemented to further improve the scalability of their algorithm for the application setting. Experiments on held-out validation trajectories show the superior performance of their method compared to prior work in IRL for quality route recommendations.", "questions": "1. The paper does not provide much details about the road graph. Would the authors be able to provide any intuition about the relation between the coarseness of the road network graph and the choice of H? \n\n2. Fig 4 and 12 highlight an interesting outcome of the sparse reward modeling approach in correcting data quality errors. Is this a consistent observation across different geographical regions? Or is there any noticeable difference in the road graph network when this method of reward modeling demonstrates a particular benefit over others? \n\n3. It is not quite clear what Fig. 7 is meant to convey. Could the authors explain more?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors address a well-motivated and useful application to show the statistically significant gains obtained from scalable IRL in route recommendation. The techniques that worked for this task have been clearly explained, along with explanations and evidence for some techniques that didn't work. \n\n2. The proposed method unifies several prior IRL algorithms through the RHIP framework for trading-off quality of route recommendation with convergence speed. This helps improve understanding of the similarities and differences in these approaches.   \n\n3. Several ablation studies have been performed for different graph compression techniques and reward modeling approaches that help establish the significance of the experimental results.", "weaknesses": "1. The experimental results are not from real-time execution of the proposed method and utilizes static features of the road network for route optimization. Incorporating dynamic features, for example varying traffic flow throughout a day, planned or unplanned diversions and road closures etc. would increase the difficulty of obtaining a scalable DP approach.  \n\n2. The reward function is learning a scalar value, whereas in the real world for applications like route optimization, it should intuitively be a multi-objective optimization problem. It is not immediately clear whether such possibilities would fit into the proposed algorithmic framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "THVKYaSolV", "reviewer": "Reviewer_Ucz3", "summary": "The paper proposes MaxEnt++, an adaptation of the classical MaxEnt algorithm, to handle very large route instances with hundreds of millions of states and demonstration trajectories. Their techniques include MaxEnt++, a MaxEnt algorithm with a DIJKSTRA component, a new policy formulation that the authors call Receding Horizon Inverse Planning (RHIP), and a graph compression technique to reduce memory usage. The algorithm was then tested with a routing dataset of 200M states, showing some improvements compared to the standard MaxEnt and other baselines.", "questions": "I do not have many questions about the current work, as the current contributions are not convincing, and the paper clearly needs much more work to reach a publishable level.\n\n# Post-rebuttal: \n\nI have increased my score to 6. There are some remaining concerns but I think the paper has some good merits.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an interesting problem. Learning with very large-scale routing datasets would have significant applications in modern transportation systems. The techniques used in the paper (except for MaxEnt, as I will discuss in the Weaknesses) are sound and relevant. The algorithm seems to work well (but again, the experiments lack comparisons with more scalable IRL algorithms, as I will discuss later).", "weaknesses": "My biggest concern is that the paper primarily revolves around MaxEnt, which was developed about 15 years ago and is now very outdated. In the introduction, the authors state that MaxEnt is limited in its scalability, which is true. Recent literature on IRL has introduced many advanced algorithms to address this issue. For instance, Adversarial IRL [1] and IQ-Learn [2], value DICE [3] are well-known recent IRL algorithms that are much more scalable. Therefore, it is crucial to focus on these algorithms instead of the outdated MaxEnt.\n\n[1] Fu, Justin, Katie Luo, and Sergey Levine. \"Learning robust rewards with adversarial inverse reinforcement learning.\" ICLR 2018. \n\n[2] Garg, Divyansh, Shuvam Chakraborty, Chris Cundy, Jiaming Song, and Stefano Ermon. \"IQ-Learn: Inverse Soft-Q Learning for Imitation.\" Advances in Neural Information Processing Systems 34 (2021): 4028-4039.\n\n[3] Kostrikov, Ilya, Ofir Nachum, and Jonathan Tompson. \"Imitation learning via off-policy distribution matching.\" ICLR 2019\n\nI notice that the related work section exclusively references older papers and appears to be outdated. It would be beneficial for the authors to give greater consideration to more recent developments in the field of IRL/imitation learning.\n\nThis should be noted that the routing task is deterministic, so both online and offline IRL/imitation learning algorithm can be applied. The authors should look at relevant works and make a complete comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bXk1hAGRm4", "reviewer": "Reviewer_2Fnw", "summary": "This paper addresses the problem of route optimization. Given a set of demonstrations of chosen navigation routes that optimize a set of unknown preferences (e.g., concerning distance, traffic, pollution), the goal is to learn a model such that suitable routes can be suggested for (possibly unseen) route-destination pairs. The authors address this problem with inverse reinforcement learning, in which the goal is to learn the reward function underlying these preferences. Equipped with the reward function, routes can be suggested e.g. via finding the highest cumulative reward path between the source and destination.\n\nThe authors present a set of improvements over standard IRL algorithms, concerning an improved initialization of the MaxEnt algorithm,  learning separate reward functions per geographical region, and trading off between expensive stochastic rollouts and cheaper deterministic planners. The method is evaluated on a global dataset of routes in several cities, showing that the method compares favorably with other IRL algorithms.\n\n## Post-response update\nI am updating the score to 6 as a result of the discussion. I think the benefits of publishing the findings of this work outweigh the shortcomings.", "questions": "Please see W1/W2 above. In terms of additional comments:\n\n**C1**. The style of Figure 1 and Figure 2 is by now instantly recognizable and, in my opinion, represents a breach of anonymity.\n\n**C2**. The wording \"largest published benchmark of IRL algorithms [...]\" (abstract, p.2, p.9) is misleading. I assume that the authors do not intend to publish the actual benchmark (e.g., data and evaluation metrics), but solely the results of this evaluation. This should be revised.\n\n**C3**. Typos: \"rouute\" (Footnote 1)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**S1**. The work successfully scales IRL to a large, real-world setting, indeed representing (to the best of my knowledge) the largest-scale evaluation of IRL.\n\n**S2**. Furthermore, it provides an interesting perspective on the inherent challenges of global route optimization, for example regarding the \"locality\" of the learned policies, suggesting individuals navigate differently in different cities. This may have wider implications in other domains e.g. transportation science, neuroscience.", "weaknesses": "**W1**. Methodological contributions: with the exception of the MaxEnt initialization findings, I am unsure of the value of the methodological developments. The geographical split into multiple experts and the graph compression are, in my opinion, both straightforward. I think simplicity is desirable, but the contribution is oversold. \n\n**W2**. Generalizability and reproducibility: given the repeated nods to engineering and deployment constraints, how generalizable and reproducible are the results? How many organizations face global scale routing optimization? While the achieved improvements are definitely impressive in terms of e.g. customer satisfaction, the contribution to the scientific community is not clear-cut, especially given that code and data (I assume) will not be released. Reproducibility and code / data availability are not even mentioned in passing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)