Thank you for taking the time to read and review our paper!

Please see our responses below. We've already uploaded some of the changes requested by the reviewers, and will incorporate all of them in the final version and credit anonymous reviewers in the acknowledgements. If you have any additional suggestions, we'd be happy to discuss them as well.

• Re: Real-time features Due to the format of our training examples (described shortly), using dynamic instead of static features would actually have no impact on training time or dataset disk space. Every example in our dataset consists of $(\tau, \mathcal{M}\_i)$ where $\tau$ is the demonstration trajectory and $\mathcal{M}\_i$ is the corresponding region MDP (with static features). Although this format uses significant disk space due to storing an MDP with every demonstration trajectory, it simplifies training since examples are fully self-contained and may be serially read from disk. Disk space is also relatively cheap compared to compute costs.

  To switch from static to dynamic features, one could simply replace the static features in $\mathcal{M}\_i$ with a snapshot of the dynamic features at the time of the demonstration $\tau$. There would be zero change to the training pipeline – the lack of dynamic features is purely a limitation of the upstream logging infrastructure that creates $\mathcal{M}\_i$ and not a limitation of our machine learning setup.

• Re: Multi-objective optimization problem Sorry, we're not sure we follow how this should be a multi-objective optimization problem, instead of a problem with scalar rewards. Do you have a reference? The existing work we're familiar with in this space uses scalar rewards [1, 2, 3, 4, 5]. Are you referring to adding user-dependent rewards, e.g. personalization [7]?

• Re: Road graph coarseness and choice of $H$ Broadly speaking, a coarser road graph will require a smaller choice of $H$. For example, if we split every road segment (node) into two equal shorter road segments, then one could double $H$ to get exactly equivalent training results. Note that with the 'merge' compression strategy, there is a single node between every feasible turn, meaning that the road graph is as coarse as possible without removing roads from the graph. As discussed in [6] and Section 6, we could prune additional nodes from the graph to make it even more coarse, although this creates significant engineering complexity.

  We would be happy to discuss any additional details about the road graph that you're interested in.

• Re: Fig 4 and 12 At least anecdotally, we observed this behavior across all geographies that we manually inspected. We suspect it occurs more frequently in regions with a higher rate of data quality issues, although statistically verifying this claim is challenging without knowing the true issue rate (an unobserved quantity).

• Re: Fig 7 We meant for this figure to convey the fact that our method performs consistently across regions $\mathcal{M}\_1, \dotsc, \mathcal{M}\_m$ with respect to the size of the region, and that the total worldwide lift was not due to large gains in a small number of regions.

References

[1] Ziebart, Brian D., et al. "Maximum entropy inverse reinforcement learning." AAAI. Vol. 8. 2008.

[2] Ho, Jonathan, and Stefano Ermon. "Generative adversarial imitation learning." Advances in Neural Information Processing Systems 29 (2016).

[3] Finn, Chelsea, Sergey Levine, and Pieter Abbeel. "Guided cost learning: Deep inverse optimal control via policy optimization." International Conference on Machine Learning. PMLR, 2016.

[4] Garg, Divyansh, et al. "IQ-Learn: Inverse soft-q learning for imitation." Advances in Neural Information Processing Systems 34 (2021).

[5] Kostrikov, Ilya, Ofir Nachum, and Jonathan Tompson. "Imitation learning via off-policy distribution matching." International Conference on Learning Representations (2020).

[6] Ziebart, Brian D. "Modeling purposeful adaptive behavior with the principle of maximum causal entropy." Carnegie Mellon University, 2010.

[7] Nguyen, Quoc Phong, Bryan Kian Hsiang Low, and Patrick Jaillet. "Inverse reinforcement learning with locally consistent reward functions." Advances in neural information processing systems 28 (2015).

Thank you for taking the time to read and review our paper!

Please see our responses below. We've already uploaded some of the changes requested by the reviewers, and will incorporate all of them in the final version and credit anonymous reviewers in the acknowledgements. If you have any additional suggestions, we'd be happy to discuss them as well.

• Re: I am unsure of the value of the methodological developments Some of our contributions are straightforward (e.g. geographic sharding) while others are much less obvious. For example, neither the MaxEnt++ initialization nor the RHIP methodological advancements were realized during the 15 years since the original MaxEnt paper was published. We believe those methodological developments, combined with a large-scale empirical study, new theoretical analyses that explains training instabilities in MaxEnt, and presentation of negative results represents a high-value publication for the inverse RL research community.

• Re: how generalizable and reproducible are the results? In Figure 6 we studied one aspect of generalizability, namely the ability of reward models to generalize across geographic regions. The p-value analysis in Table 1 and Appendix D.3 provides strong statistical guarantees on our claims. Not shown in this paper, we also studied the generalizability of our results across time, and only noted a minor drop in performance. We'd be happy to discuss other dimensions for testing the generalizability of the results. [For reproducibility concerns, see below discussion on data availability]

• Re: How many organizations face global scale routing optimization? We're aware of a few organizations, plus a larger number of open-source projects for global routing based on OpenStreetMaps [1]. Perhaps more importantly, we want to call out Reviewer 5CwT's comment:

[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.

We chose this setting primarily because it's the largest scale application we could find to test our methods on.

• Re: data and code availability Due to strict user privacy requirements, we believe it's unlikely a routing dataset of the scope used in this paper could be publicly released in the foreseeable future. We strongly support open-sourcing experiments when legally and ethically permissible.

• style of Figure 1 and Figure 2 is by now instantly recognizable and, in my opinion, represents a breach of anonymity We based the style on figures from other papers that we liked (e.g. Figure 1 in [2]), and created the graphics using the publicly available Adobe Illustrator with open-source fonts and graphics from Adobe Stock. Could you provide some more details to how this violates ICLR's anonymity requirements?

• Re: "largest published benchmark" Perhaps "largest published empirical study" is more precise? This could also be replaced with "empirical analysis" or "experiment".

• Re: Typo in footnote 1 Fixed! Thanks.

References

[1] https://wiki.openstreetmap.org/wiki/Routing#Developers

[2] Jumper, John, et al. "Highly accurate protein structure prediction with AlphaFold." Nature 596.7873 (2021): 583-589.

Thank you for taking the time to read and review our paper!

Please see our responses below. We've already uploaded some of the changes requested by the reviewers, and will incorporate all of them in the final version and credit anonymous reviewers in the acknowledgements. If you have any additional suggestions, we'd be happy to discuss them as well.

• Re: IQ-Learn, Adversarial IRL and ValueDICE We've used these algorithms in other domains, but there is a subtle aspect of the discrete routing problem that makes them poorly suited for this setting (a point we've discussed with some of the original authors of these papers as well). Specifically, the goal conditioning requirement specifies that each destination $s_d$ induces a slightly different MDP (where the destination state has been modified to be self-absorbing with zero-reward). In the tabular setting, the number of reward parameters is $\mathcal{O}(SA)$ even when conditioning on $s_d$. This is in contrast to approaches that explicitly learn a Q-function (e.g. IQ-Learn) or value function (e.g. ValueDICE), where the number of required parameters increases from $\mathcal{O}(SA)$ to $\mathcal{O}(S^2A)$ and $\mathcal{O}(S)$ to $\mathcal{O}(S^2)$, respectively. In other words, by directly learning rewards, we're able to trivially transfer across MDPs with different destination states $s_d$, unlike approaches that learn a policy, Q-function or value function.

  AIRL samples trajectories from the current policy, trains a binary trajectory discriminator, performs a simple transformation to compute rewards from the logistic discriminator probabilities, and then updates the policy with any policy optimization method. In discrete settings, it appears the original paper authors actually use the MaxEnt policy for the final step (see Section 7.1 of [2]). We could follow the same approach – one key difference between the resulting algorithm and the techniques we consider is that instead of exactly computing the policy's stationary distribution, the AIRL technique would sample trajectories. Although sampling trajectories is required in continuous settings, it will almost certainly have higher variance compared to exactly computing the policy's stationary distribution (which we're able to do in the discrete setting).

• Re: MaxEnt is outdated Recent works (including modern methods such as IQ-Learn!) build off MaxEnt. Our work similarly builds off and advances MaxEnt, and also incorporates modern optimization techniques and function approximators. The original MaxEnt is simply one of our baselines, and you can see in Table 1 that newer baselines (e.g. [1]) outperform the original paper, as expected.

• Re: Online and offline IRL/imitation learning algorithms can be applied Is there a specific method that you have in mind? We'd be more than happy to discuss alternatives that can be applied in this setting.

References

[1] Wulfmeier, Markus, Peter Ondruska, and Ingmar Posner. "Maximum entropy deep inverse reinforcement learning." arXiv:1507.04888 (2015).

[2] Fu, Justin, Katie Luo, and Sergey Levine. "Learning robust rewards with adversarial inverse reinforcement learning." International Conference on Learning Representations (2018).

Thanks for the fast response!

It seems the main point of contention is on the choice of baselines, and in particular the effects of adding destination-dependent Q and V functions to methods such as IQ-Learn and ValueDICE.

• Re: you just need to define and learn destination-dependent Q Exactly, destination-dependent IQ-Learn would learn $Q(s, a | s_d)$. In the tabular setting, this function requires a parameter for every state-action-destination tuple, for a total of $\mathcal{O}(S^2A)$ parameters.
• Re: Number of parameters If we instead "keep the same parameters across destinations" in the tabular setting, then won't this Q-function no longer be destination-dependent? Since the parameters are identical for each destination, then $Q(s, a | s_d) = Q(s, a) \forall s_d$ holds. In the tabular setting, it seems impossible to change from $Q(s, a)$ to $Q(s, a | s_d)$ without increasing the number of parameters. The analysis in the non-tabular setting is less straightforward, but the intuition is the same: IQ-Learn has to learn both the rewards and how to reach the destination, whereas reward-based techniques (MaxEnt, MMP, BIRL) only have to learn the former.
• Re: I do not find this point convincing without any experiments We initially considered these baselines (IQ-Learn, ValueDICE) for our experiments, but ultimately chose other baselines that we believed were stronger due to the above concerns. We include a large number of baselines in Table 1 that aren't impacted by destination dependency, and we believe follow reasonable selection criteria.

We also want to emphasize that for online routing requests, we require learned rewards to take advantage the reward pre-computation, contraction hierarchy, and fast graph search tricks described at the end of Section 3. These rewards could be estimated from IQ-Learn's Q-function, although this creates additional complexity, whereas we follow a more direct approach by directly learning the rewards.

Thanks the authors for the responses:

• $\mathcal{O}(S^2 A)$ parameters: Have you attempted to train with this setting. I do not think a large number of parameters is a big issue in modern DL. If it is not possible to learn with this large number of parameters, then you can provide a comparison using a smaller network setting.
• Will you make the code and data publicly available?

We appreciate your continued attention to discussing our paper!

• Re: $\mathcal{O}(S^2A)$ parameter setting The worldwide road graph contains $S \approx 200M$ states and $A < 10$ actions, implying that IRL methods such as destination-dependent IQ-Learn that scale $\mathcal{O}(S^2A)$ would require more than 4e16 parameters with these networks (thousands of times larger than GPT4). This scaling law holds with our best-performing reward models (DNN+SparseLin in Table 1), since they include a sparse reward parameter for every road in the graph, although not with some of the lower-quality reward networks (see discussion in next point).

• Re: Smaller settings IQ-Learn and ValueDICE could be studied with smaller road graphs or reward models that exclude the empirically beneficial SparseLin features. Since the focus of our paper is on massively scalable IRL, we chose to only include baselines that we thought had a reasonable chance at success in the full worldwide destination-dependent setting. We think that studying methods such as IQ-Learn and ValueDICE in other settings is perhaps best left for a separate paper.

• Re: data availability Due to strict user privacy requirements, we believe it's unlikely a routing dataset of the scope used in this paper could be publicly released in the foreseeable future. We strongly support open-sourcing experiments when legally and ethically permissible.

• Re: code availability We're investigating the feasibility of releasing our code independent of the dataset.

I thank the authors for their responses. I am now more positive about the contributions of the work. I, however, still think that there would be ways to make IQ-learn or AIRL work in your context. More discussions would be appreciated. Moreover, I am still concerned about the data and code availability because if you do not make them available, then no one can benchmark against your approach and it is impossible to validate your claims. I will increase my score to 6 as I think the paper has some good merits.

Thank you for taking the time to read and review our paper!

Please see our responses below. We've already uploaded some of the changes requested by the reviewers, and will incorporate all of them in the final version and credit anonymous reviewers in the acknowledgements. If you have any additional suggestions, we'd be happy to discuss them as well.

• Re: Snoswell et al. Good catch, thanks. We've added these to our related work section.

• Re: Sec 4 parallelism strategies notation [context] The global $\mathcal{M}$ is partitioned into $m$ disjoint MDPs $\mathcal{M}\_1, \dotsc, \mathcal{M}\_m$, where each state $s$ belongs to exactly one $\mathcal{M}\_i$. Each MDP $\mathcal{M}\_i$ has a corresponding learned reward $r\_{\theta\_i}$.

  We meant for the notation in this section to express the fact that for state-action pair $(s, a)$ corresponding to $\mathcal{M}\_i$, the reward $r(s, a)$ is solely determined by region-specific expert $r\_{\theta\_i}$. In other words, the reward of each $(s, a)$ is determined by a single $r\_{\theta\_i}$. Perhaps a more clear notation here would be $r(s, a) = r\_{\theta\_i}(s, a)$ where $(s, a) \in \mathcal{M}\_i$? We're open to alternative suggestions.

• Re: Typo in footnote 1 Fixed! Thanks.