Neuro-algorithmic Policies for Discrete Planning
Authors: Marin Vlastelica Pogančić
Michal Rolinek
Georg Martius
Venue:  (2021)
Keywords: planning
reinforcement learning
combinatorial optimization
control
imitation learning

Abstract: Although model-based and model-free approaches to learning the control of systems have achieved impressive results on standard benchmarks, generalization to variations in the task are still unsatisfactory. Recent results suggest that generalization of standard architectures improves only after obtaining exhaustive amounts of data.We give evidence that the generalization capabilities are in many cases bottlenecked by the inability to generalize on the combinatorial aspects. Further, we show that for a certain subclass of the MDP framework, this can be alleviated by neuro-algorithmic architectures.

Many control problems require long-term planning that is hard to solve generically with  neural networks alone. We introduce a neuro-algorithmic policy architecture consisting of a neural network and an embedded time-depended shortest path solver. These policies can be trained end-to-end by blackbox differentiation. We show that this type of architecture generalizes well to unseen variations in the environment already after seeing a few examples.


https://sites.google.com/view/neuro-algorithmic

Under review as a conference paper at ICLR 2021
DISCRETE PLANNING WITH NEURO-ALGORITHMIC POLICIES
Anonymous authors Paper under houble-blind review
ABSTRACT
Although model-based and model-free approaches to learning the control of sys- tems have achieved impressive results on standard benchmarks, generalization variations in the task are still unsatisfactory. Recent results suggest that generaliza- tion standard architectures improves only after obtaining exhaustive amounts of data. We give evidence that the generalization capabilities in many cases bottlenecked by the inability to generalize on the combinatorial aspects. Further, show that for certain subclass of the MDP framework, this be alleviated by neuro-agorithmic architectures.
Many control problems require long-term planning that is hard to solve generically with neural networks alone. We introduce neuro-algorithmic policy architecture consisting of neural network and an embedded time-depended shortest path solver. These policies can be trained end-to-end by blackbox differentiation. We show that this type of architecture generalizes well to unseen variations in the environment already after seeing a few examples.
input
representation leaming
Dijkstra's shortest
predicted trajectory
Hamming distance
2 frames
trajectory
cost- predictor
C
ResNet18 8
goal- predictor
y(C)
8,
ResNe1l8
Figure I: Architecture of the neuro-algorithmic policy. Two subsequent frames are processed by two simplified ResNet18s: the cost-predictor outputs tensor (width height time) vertex costs oj and the goal-predictor outputs heatmaps for start and goal. The time-dependent shortest path solver finds the shortest path the goal. Hamming distance between the proposed and expert trajectory is used as loss for training.
INTRODUCTION
One of the central topics in machine learning research is learning control policies for autonomous agents. Many different problem settings exist within this area. On one end of the spectrum are imitation learning approaches, where prior expert data is available and the problem becomes supervised learning problem. On the other end of the spectrum lie approaches that require interaction with the environment to obtain data for policy extraction problem, also known the problem of exploration. Most Reinforcement Learning (RL) algorithms fall into the latter category. In this work. we concern ourselves primarily with the setting where limited expert data available, and a policy needs to be extracted by imitation learning.
Independently how a policy is extracted, a central question of interest is: how well will it generalize to variations in the environment and the task? Recent studies have shown that standard deep RL algorithms require exhaustive amounts of exposure to environmental variability before starting to generalize Cobbe et al. (2019)

---

Under review as a conference paper at ICLR 2021
There exist several approaches addressing the problem of generalization in control. One option is to employ model- based approaches that learn a transition model from data and use planning algorithms at runtime. This has been argued to be the best strategy in the presence of an accurate model and sufficient computation time (Daw et al. 2005). However, learning a precise transition model is often harder than learning a policy. This, in turn, makes them more general, but comes a cost of increasing the problem dimensionality. The transition model has a much larger dimensionality and it needs model aspects of the environmental dynamies that are perhaps irrelevant for the task. This is particularly true for learning in problems with high-ding sish-imnnsional inputs, such as raw images. In order alleviate this problem, learning specialized or partial models has shown to be viable alternative, e.g. in MuZero Schrittwieser et al. (2019).
We propose to use recent advances in making combinatorial algorithms differentiable in a blackbox fashion as proposed by Vlastelica et al. (2020) to train neuro-algorithmic policies with embedded planners end-to-end. More specifically, we use a time-dependent shortest path planner acting on a temporally evolving graph generated by deep network from the inputs. This enables us to learn the time-evolving costs of the graph and relates us to model-based approaches. We demonstrate the effectiveness of this approach in an offline imitation learning setting, where few expert trajectories are provided. Due to the combinatorial generalization capabilities of planners, our learned policy is able to generalize to new variations in the environment out of the box and orders of magnitude faster than naive learners. Using neuro-algorithmic architectures facilitates generalization by shifting the combinatorial aspect of the problem to efficient algorithms, while using neural networks extract a good representation for the problem at hand. They have potential to endow artificial agents with the main component of intelligence, the ability to reason.
Our contributions can be summarized as follows:
We identify that poor generalization is caused by lack of structural and combinatorial inductive biases and can be alleviated by introducing the correct inductive biases through neuro-algorithmic policies.
We show that architectures embedding TDSP solvers are applicable beyond goal-reaching environments.
We demonstrate learning neuro-algorithmic policies in dynamic game environments from images.
RELATED WORK
Planning There exist multiple lines of work aiming to improve classical planning algorithms such as improving sampling strategies of Rapidly-exploring Random Trees (Gammell et al.) 2014]
Kurect Burget et al.) 2016 Kuo et al. 2018). Similarly, along this direction, Kumar et al. (2019) propose a
conditional VAE architecture for sampling candidate waypoints. Orthogonal to this are approaches that learn representations such that planning is applicable in the latent space. |aanne et al. (2019)
employ latent multi-step transition model. [Savinov et al. (2018) propose a semi- cemi-parametric method for mapping observations to graph nodes and then applying a shortest path algorithm. Asai &
Fukunaga 2017); Asai & Kajino (2019) use an autoencoder architecture in order to learn a discrete
transition model suitable for classical planning algorithms. Li et al. (2020) learn compositional Koopman operators with graph neural networks mapping a linear dynamics latent space, which allows for fast planning. [Cenn et al. (2018); Amos et al. (2017) perform efficient planning by using a convex model formulation and convex optimization. Alternatively, the replay buffer can be used as a con-parametric model in order to select waypoints (Eysenbach et al.) (2019) or in an MPC fashion (Blundell et al. 2016). None of these methods perform differentiation through the planning algorithm in order to learn better latent representations.
Differentiation through planning Embedding differentiable planners has been proposed in previ- ous works, e.g. in the continuous case with CEM (Amos & Yarats 2020; Bharadhwaj et al. 2020). Wu et al. (2020) use (differentiable) recurrent neural network as planner. Tamar et al. (2016) use differentiable approximation of the value iteration algorithm to embed in a neural network. Silver et al. (2017b) differentiate through few steps of value prediction in a learned MDP to match the externally observed rewards. [Srinivas et al. (2018) use a differentiable forward dynamics model in latent space. Karkus et al. (209) suggest neural network architecture embedding MDP and POMDP
2

---

Under review as a conference paper at ICLR 2021
solvers and during the backward pass, they substitute the algorithms by learned approximations. In comparison, we do not perform any relaxation or approximation of the planner itself and we learn interpretable time- deeendeedddt costs of the latent planning graph based on expert demonstrations by differentiating through the planner. Similarly to our work, Yonetani et al. (2020) emhed an A algo- rithm into neural network, but in comparison, their method does not operate with time-dependent costs, subgoal selection and does not provide a policy for closed-loop control.
Inverse reinforcement learning and imitation learning Uncovering the expert objective function from demonstrations has been a central topic in reinforcement learning (Ng & Russell, 2000). Our method is connected to inverse reinforcement learning in the sense that we learn the objective function that the expert optimizes to extract an optimal policy, also called apprenticeship learning (Abbeel Ng] 2004 Neu & Szepesvári 2012] Aghasadeghi & Breil 2011). What separates our approach is that the inferred costs are inherently part of the learned neuro-al aouro-aggrithmiic policy in conjunction with the applied planner the costs.
Our method is an offline imitation learning method, but since we propose an end-to-end trainable policy, it is naturally extendable to the online case with method such as DAgger (Ross et al., 2011)
or other online reinforcement learning methods augmented with expert datasets (Reddy et al. 2019 Ho & Ermon 2016).
Offiine model-based reinforcement learning Model-based methods have shown promise by fa- cilitating better generalization (Janner et al. 2019). Approaches employing models fall into two camps: using models extract a policy in Dyna-style approach (Sutton [991 Janner al. 2019
Sutton et al. 2008 Yao et al.) 2009 Kaiser et al., 2019). or incorporating the model in a planning
loop, i.e. predicire control (Finn & Levine 2017 Racanière al.. 2017 Oh et al. 2017
Silver et al. 2017a). In this work, we consider the latter case where an implicit transition model is "hidden" within the predicted time-dependent costs.
Combinatorial algorithms in end-to-end trainable networks We suggest a hybrid policy con- sisting of neural network and an accompanying expert (shortest path) discrete solver that is trainable end-to-end. Incorporating expert discrete solvers into end-to-end trainable architectures a topic with exciting recent developments. For the simpler setup of comparing to ground-truth values on the solver output, numerous frameworks have been suggested such as the prrdict-and-optimine framework and its variants (Elmachtoub & Grigas 2017 Demirovic et al. [2019] Mandi et al. 2019).
Also, specializations for concrete cases such as sparse structured inference (Niculae et al. 2018).
logical satisfiability (Wang et al.) 2019). submodular optimization (Djolonga & Krause 2017) or
mixed integer programming (Ferber et al. 2020) have been proposed.
We are interested in the harder case of providing entirely hybrid architecture which may the solver at intermediate levels and is trainable end-to-end. For this case, two approaches have recently emerged (Vlastelica al. 2020 (Brrhhtt al., 2020). Vlastelica al. (2020) introduce efficient implicit piece-wise linear interpolation scheme, while Berthet et al. (220)) introduce Monte Carlo technique for estimating the Jacobian of Gaussian smoothing of the piecewise constant function. The approach from V Vlastelica et al. (2020) is especially appealing, since it allows for uses in which the solver is the computational bottleneck. Therefore, we follow it in this work. By formulating the control problem as time-dependent shortest path problem (TDSP), we show that the framework from Vlastelica et al. (2020) is applicable in specific control settings.
3 MARKOV DECISION PROCESSES AND SHORTEST PATHS
We follow the MDP framework Puterman 2014) in a goal-conditioned setting Schaul et al. (015)).
This is used in sequential decision making problems where specific terminal state has be reached.
Definition A goal-come noal-conditioned Markov Decision Process (gcMDP), M is defined by the tuple (S, A. 9. 9. r). where S is the state space, A the action space, p(s' a, the probability of making the transition s + s' when taking the action a, g is the goal, r(s, o, s', g) the reward obtained when transitioning from state to s' while taking action and aiming for goal g.
3

---

Under review as a conference paper at ICLR 2021
Concretely, concern ourselves with fully observable discrete MDPs, in which the Markov assump- tion for the state holds and where the state and action- are discrete. The goal of reinforcement learning is to maximize the return G = Σi= I of such process. In gcMDPs the reward is such that the maximal return can be achieved by reaching the goal state g.
Given access to the transition probabilities and rewards, an optimal policy can be extracted by dynamic programming Bertsekas et al. (1995). In graph representation an gcMDP, the set of vertices V corresponds to the set of states S, traversing an edge corresponds to making transition between states. We assume a deterministic process, such that the optimal policy can be extracted by standard shortest path algorithms, such as Dijkstra's 's algorithm.
In this work, we imitate expert trajectories by training a policy with an embedded time-depene dependent shortest path solver end-to-end. Although the actual gcMDP solved by the expert may be stochastic, learn deterministic latent approximate geMDP, .M. Assuming that have access to the topology of the gcMDP, by applying bacckbox-differeniiatiie theory Vlastelica et al. (020)) we are able to learn the underlying costs (instead of rewards) of M such that the optimal policy on M is also optimal in M.
Although the MDP Definition yields itself nicely towards learning the time-dependent edge costs cf. this can increase the problem dimensionality considerably with the out-degree of the vertices (here |A|). Thus, we consider cases where the reward function only depends on the current state and the goal: r(s, a, s', g)) = r(s, g). In this case, vertex costs c are sufficient for finding the optimal solution to the gcMDP. Accordingly, rely vertex-based version of the shortest path algorithm.
4 SHORTEST PATH ALGORITHM AND ITS DIFFERENTIATION
We will employ an efficient implementation of Dijkstra's algorithm for computing the shortest path. For differentiation, we rely on the framework for blackbox differentiation of combinatorial solvers Vlastelica et al. (2020).
4.1 TIME-DEPENDENT SHORTEST PATH
The purely combinatorial setup can be formalized follows. Let G = EV, be a graph. For every V, E V. let ct "..... of be non-negative real numbers; the costs of reaching the vertex vy at the planning horizon. The TIME-DEPENDENT-SHORE time-points 1, 2, .... T, where problem (TDSP) has as input the graph G, a pair of vertices s, E V (start and end) and the matrix Ce RIVIXT of the costs cf. This version of the shortest path problem can be solved by executing the Dijkstra shortest path algorithm Diiiittna 1959) on augmented graph. In particular, we set
V E = (((v1,)), (12,
1 1)): E (E,,,,,
where the cost of vertex (v,, () E V* simply of and E the original edge set appended with all self-loops. This allows to "wait" at fixed vertex from timestep t to timestep t + 1. In this graph, the task is to reach vertex (e, from (s, 1) with the minimum traversal cost.
The time-dependent shortest path problem can be used for model predictive control using receding horizon planning, as done in our approach.
4.2 APPLICABILITY OF BLACKBOX DIFFERENTIATION
The framework presented in Vlastelica et al. (2020) turns blackbox combinatorial solvers into neural network building blocks. The provided gradient is based on a piecewise linear interpolation of the true piecewise constant (possibly linearized) loss function, see Fig. 2 The exact gradient of this linear interpolation is computed efficiently via evaluating the solver on only one more instance (see Algorithm
Evvn though the classical formulation of Dijkstra's algorithm is edge-based, all of its properties hold true also in this vertex based formulation.
4

---

Under review as a conference paper at ICLR 2021
Algorithm Forward and backward Pass for the shortest-path algorithm
function FORWARDPASSCC, s, E)
Y = TDSP(C,s,e
II Run Dijkstra's 's algorithm
save Y.C.s.* return Y
Needed for backward pass
function BACKWARDPASS(VVLIY)) A)
load Y, Y,C,&
Cx == C+
Calculate modified costs If Run Dijkstra algo.
YA == TDSP(CX,s,e)
return } -
loss landscape
interpolation for
interpolation for
Figure 2: Differentiation of piecewise constant loss resulting from incorporating combinatorial
solver. A two-dimensional section of loss landscape shown (left) along with two differentiable interpolations of increasing strengths (middle and right).
In order to apply this differentiation scheme, the solver at hand needs to have a formulation which it minimizes an inner-product objective (under arbitrary constraints). To that end, for given graph G = (V, E') with time-dependent costs C' E RIVIXT we define Y E {0, 1J/VXx an indicator matrix of visited vertices. of such indicator matrices that correspond to valid paths in the graph (V*, EE)) will be denoted as Adm(G). (G). The time-dependent shortest path optimization problem can be then rewritten as
particular, Y = and only if vertex v; is visited at time point The set
TDSP(C, s,e)
arg min YEAdu(G)
(1)
(1.1)
This is an inner- amerrpproduct objective and thus the theory from Vlastelica al. (2020) applies. effect, the deep network producing the cost tensor C can be trained via supervision signal from ground truth shortest paths.
4.3 COST MARGIN
Our work is related to the problem of metric learning in the sense that learn the distance metric between the current position of the agent (state) and the target position in the underlying gcMDP, allowing us solve it with shortest path algorithm. It has been shown that inducing margin on the metric can be beneficial for generalization. Similarly to (Rolinek et al., (2200) in the context of rank- based metric learning, we induce a margin on the costs of the latent gcMDP, increasing the cost of ground truth path and decreasing the rest in the training stage of the algorithm:
ct
+
if (w,, Y if (v., Y (v,,()) EV
=
(2)
During evaluation, the cost margin is removed from the shortest path calculation.
5 NEURO-ALGORITHMEL POLICY ARCHITECTURE
We propose the Neuro-algorithe Policy (NAP) framework, that is an end-to-end trainable deep policy architecture embedding algorithmic component using the afore-mentionel techniques.
5

---

Under review as a conference paper at ICLR 2021
In this paper consider a concrete architecture consisting of two main components: backbone ResNet18 (without the final fully connected layers, detailed description is available in Sec. [f the appendix) architecture and the shortest path solver, see Fig. [ At each time step the policy receives two images concatenated channel-wise from which it predicts the cost matrix C' for the planning horizon T with the cost-predictor and the start vertex and end vertex with the goal predictor, explained below.
The cost matrix C' given the solver along with the start vertex and end vertex e to compute the time-dependent shortest path Y. The cost-predictor is trained using the Hamming distance between the predicted plan and the expert plan Y that we use for supervision.
The policy is used in model- -predccvre control setting, i.c. at execution time we predict the plan Y for horizon T' at each time step and execute the first action from the plan.
5.1 GOAL PREDICTION, GLOBAL AND LOCAL
In order to apply the solver to the learned latent graph representation, we need to map the current state of the environment appropriate start and end vertices (s,e). e). To this end, employ a second ResNet18 - the goal-predictor similar to the cost-predictor that learns to extract the agent start position and a suitable target position. The training of this predictor is using a Cross-Entropy loss and is independent of learning the costs of the latent graph representation.
At training time, given the expert trajectories Y have access the current position of the agent and its position in the future. Thus, for predicting we have simple supervision signal, namely the current position. For the goal prediction we extract set of suitable goal locations from the expert. Here, we distinguish between global and local planning.
In the global setting, the last position of the expert is the goal e, corresponding to, for instance, the jewel in CRASH JEWEL HUNT, see Fig.
In the local setting, we expect the end vertex to be an intermediate goal ("collect an orb"), which effectively allows for high-level planning strategies while the low-level planning is delegated to the discrete solver. this case, the positively labeled supervision at time are all locations of the (expert) agent between step + T and / + 27.
The local setting allows to limit the complexity of our method, which grows with the planning horizon. This is also trade-off between the combinatorial complexity solved by the TDSP solver and the goal predictor. Ideally, the planning horizon used for the cost-prediction is long enough to capture the combinatorial intricacies of the problem at hand, such creating detours towards the goal in the case of future dangerous states, or avoiding dead-ends in a maze.
The local setting formulation makes architecture hierarchical method similar to Blaes et al. (2019): Nachum et al. (2018). and allows for solving tasks that are not typical goal-reaching problems, such the CHASER environment.
EXPERIMENTS
To validate our hypothesis that embedding planners into neural network architectures leads to better generalization, we consider several procedurally generated environments (from the ProcGen suite Cobbe et al. (2019) and CRASH JEWEL Hunt) with considerable variation between levels.
We compare to two basclines: a standard behavior cloning imitation learning bascline using a ResNet18 architecture trained with cross-entropy classification loss the same dataset our method; and a reinforcement learning baseline using the PPO algorithm. More details on the training procedure and the hyperparameters can be found in appendix Sec. D
For the experimental validation, we aim to anwser the following questions:
Can NAP be trained to perform well as policies in procedurally generated environments?
Can NAP generalize in a low data regime, i.e. after seeing only few different levels?
Can we also solve non-goal-reaching environments?

---

Under review as a conference paper at ICLR 2021
6.1
CRASH JEWEL HUNT
(a) Frame
(b) Game logic
(c) Cost prediction example
input frames
prodicted costs casts
moving
bakees
Goad
Fox
NAN
True env-dynamics
The CRASH JEWEL HUNT environment. The goal for the fox, see (a), is to obtain the jewel in the right most column, while avoiding the moving wooden boxes (arrows in (b)). When the agent collides with a wooden box it instantly fails to solve the task. A prediction of the costs is shown in (c).
Figure 3:
We first consider environment constructed to test NAP, called CRASH JEWEL HUNT which can be seen in Fig. 3 The environment corresponds to a grid-worid of dimensions h x w where the goal is move the agent (Fox) from an arbitrary start position in the left-most column to the goal position (jewel) arbitrarily positioned in the right-most column. Between the agent and the goal are obstacles. wooden boxes that move downwards (with cyclic boundary conditions) with velocities that vary across levels but not within a level, see Fig. B riight). At each time step, the agent can choose to move horizontally or vertically in the grid by one cell or take no action.
To make the task challenging, we sample distinct environment configurations for the training set and the test set, respectively. More concretely, we vary the velocities, sizes and initial positions of the boxes as well as the start and goal positions.
6.2 PROCGEN BENCHMARK
In addition to the jewel hunt environment, we evaluate our method on the MAZF, LEAPER and CHASER environments from the ProcGen suite Cobbe et al. (2019). We have chosen these envi- ronments because their structure adheres to our assumptions. For the LEAPER we modified the environment such that grid-world dynamics applies (GEAPER(GRID)), Based on performance of (ERAD))(GRDD) the baselines, the resulting (LEAPER GRID)) is not an easier environment.
The MAZE and the LEAPER (ERDD) tasks have static goal whose position only varies across levels, whereas the CHASER requires collection of all orbs without contact with the spiders, so the local goals need be inferred on the fly. The CHASER environment is also particularly challenging as even the expert episodes require on average 150 steps, each of which carries a risk of dying. For this reason, used three expert trajectories per level.
6.3 RESULTS
We train our method (NAP) and the imitation learning baseline until saturation on a training set, resulting in virtually 100% success rate when evaluating on train configurations in the environment. For the PPO baseline we use the code from Cobbe et al. (2019) and provide also two subsequent frames and 200M time steps for training. For our method we also report performance of version with access to the true start and end-point prediction (NAP+ oracle), with the exception of the CHASER where true goals are not well-defined.
In Fig. 4 we show the performance of the methods when exposed to different number of levels at training time. As reported in Cobbe et al. (2019), the baselines have large generalization gap, and also poor performance when 10 000 levels are seen. We find that NAP shows strong generalization performance, already for < 500 levels. In some environments, such as the MAZE we obtain near 80% success rate already with just 100 levels which is reached by PPO after seeing 200 000 levels. For the CRASH JEWEL HUNT 5 x already with 30 trajectories a third of the 1000 test-levels can be solved, the baseline manages less than 50 out of the 1000.
7

---

Under review as a conference paper at ICLR 2021
CRASH
CRASH X 10
1.0
1.0
success rate
success rate
0.5
0.5
0.0
10
10
102
103
100
10a
102
10a
# #eevels
#levels
MAZE
LEAPER(GRID)
1.0
1.0
success rate
success rate
0.5
0.5
0.0
0.0
100
10a
102
10a
100
10
102
10a
# levels
#levels
imitation baseline test
NAP oracle test
NAP test
PPO test
imitation baseline train
NAP + oracle train
NAP train
PPO train
Figure 4: Generalization performance depending on the number of seen levels during training. Dashed lines indicate performance on training-levell and solid lines show the generalization to unseen levels.
NAP shows good generalization already after 100 levels in most cases.
(a) Performance on CHASER
(b) Short-horizon plans
test avg reward
5.0
2.5
0.0
10
#levels
PPO
NAP
Figure 5: Performance of NAP against PPO on the CHASER environment (a) trained on 10, 20, 50, and 100 levels. In (b) we show the short-horizon plans (white) of the agent (blue) at step and 110 in the environment.
6.4 SENSITIVITY TO THE PLANNING HORIZON
We provide a sensitivity analysis of the performance with different planning horizons. Our results indicate that longer horizons benefit environments with increased dynamical interactions. As apparent from Fig. 6 our method outperforms the imitation baseline in the crash environment, the gap between the methods being correlated with the complexity of the environment x vs 5 x 10). It can be seen also that making the planning horizon smaller in these environments hurts performance.
the other hand, for environments with no dynamics, such as the maze environment, there is no benefit in using -imedeependent costs, as expected. Nevertheless, there is still strong performance gain in generalization when using NAP oppose to vanilla imitation learning from expert trajectories.
8

---

Under review as a conference paper at ICLR 2021
CRASH 5x5
CRASH 5x10
test success rate
1.0
1.0
test success
0.5
0.5
0.0
0.0
100
10
102
10a
100
10a
10a
10a
#levels
#levels
MAZE
LEAPER(GRID)
1.0
1.0
test success
success
0.5
0.5
0.0
10
10a
102
10a
10c
102
10a
#levels
#levels
imitation baseline
horizon=5
horizon=15
horizon=1
horizon=10
Figure 6: Test success rate of our method with different horizon lengths. The solver assumes that the last horizon step costs remain to infinity. In this sense, the horizon of length corresponds to a static solver.
DISCUSSION
We have shown that hybrid neuro-algorithmic policies consisting of deep feature extraction and shortest path solver made differentiable via blackbox differentiation (Vlastelica al., 2020) enable learning policies that generalize unseen environment settings in the low-data regime. Hybrid architectures are a stepping stone towards better use inductive biases that enable stronger generalization. In NAP, the inductive bias that impose is the topology of the latent planning graph in conjunction with a planning algorithm. Introducing the shortest-patth solver as a module shifts the combinatorial complexity of the planning problem to efficient algorithmic implementations while alleviating the learning of good representations for planning.
Although there is clear benefit in using NAP, the method comes with certain caveats. We assume that the topological structure (i.e. that there an underlying grid structure with a set of 5 actions) of the latent planning graph is known a priori. Furthermore, we assume that the structure of the latent graph is fixed and not dynamically changing over time, i.e. that each available action at a vertex corresponds to the same edge. Any results allowing to abandon some of these assumption will vastly increase applicability of this method and should be of immediate interest.
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 1, 2004.
Navid Aghasadeghi and Timothy Bretl. Maximum entropy inverse reinforcement learning in continu- ous state spaces with path integrals. In 201 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1561-1566 IEEE, 2011.
Brandon Amos and Denis Yarats. The differentiable cross-entropy method. In International Confer- on Machine Learning, ICML. 2020.

---

Under review as a conference paper at ICLR 2021
Brandon Amos, Lei Xu, and J Zico Kolter. Input convex neural networks. In International Conference on Machine Learning, pp. 146-155, 2017.
Masataro Asai and Alex Fukunaga. Classical planning in deep latent space: Bridging the subsymbolic-- symbolic boundary. arXiv preprint 1rXxv:/705.0055:: 2017.
Masataro Asai and Hiroshi Kajino. Towards stable symbol grounding with pro-ssppressed state au- toencoder. In Proceedings of the International Conference on Automated Planning and Scheduling. volume 29, pp. 592-600, 2019.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable perturbed optimizers. arXiv preprint arXiv:2002.08666, 2020.
Dimitri P Bertsekas, Dimitri Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
Homanga Bharadhwaj. Kevin Xie, and Florian Shkurti. Model-predictive control via cross-entropy and gradient- based optimization. arXiv preprint arXiv:2004.09763, 2020.
Sebastian Blaes, Marin Vlastelica Pogančić, Jiajie Zhu, and Georg Martius. Control what you can: Intrinsically motivated task-planning agent. In Advances in Neural Information Processing Systems 32, pp. 12541-12552. Curran Associates, Inc., 2019.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint 2016.
Felix Burget, Maren Bennewitz, and Wolfram Burgard. Bi 2 nt:: An efficient sampling- based path planning framework for task-constrained mobile manipulation. In 2016 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3714-3721. IEEE, 2016.
Yize Chen, Yuanyuan Shi, and Baosen Zhang. Optimal control via neural networks: A convex approach. In International Conference on Learning Representations, 2018.
Karl Cobbe, Christopher Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforcement learning. arXiv 1912.01888 2019.
Nathaniel D Daw, Yael Niv, and Peter Dayan. Uncertainty-based competition between prefrontal and dorsolateral striatal systems for behavioral control. Nature neuroscience, 8(12):1704-1711 2005.
Emir Demirovic, Peter J. Stuckey, James Bailey, Jeffrey Chan, Christopher Leckie, Kotagiri Ramamo- hanarao, and Tias Guns. Predict+optimise with ranking objectives: Exhaustively learning linear functions. Sarit Kraus (ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. IJCAI 2019, Macao, China, August 16-16, 2019, pp. 1078 1085, ijcai.org, 2019, doi: 10.24963/ijcci.2011//55.. URL pestpa://doos org/ 10 2496 http://......................... 151
E. W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math., 1(1):269-271, December 1959. doi: 10.1007/BF011366900
Josip Djolonga and Andreas Krause. Differentiable learning of submodular models. In Advances in Neural Information Processing Systems, pp. 1013-1023, 2017.
Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". ArXiv, abs/1710.08005, 2017.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In Advances in Neural Information Processing Systems 32, pp. 15246-15257. Curran Associates, Inc., 2019.
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as layer. In AAAI, pp. 1504-1511, 2020.
Chelsea Finn and Sergey Levine. Deep visual foresight for planning robot motion. In 2017 IEEE International Conference Robotics and Automation (ICRA), pp. 2786-2793. IEFF, 2017.
10

---

Under review as a conference paper at ICLR 2021
Jonathan D Gammell, Siddhartha S Srinivasa, and Timothy D Barfoot. Informed rrt#: Optimal sampling-bast path planning focused via direct sampling of an admissible ellipsoidal heuristic. In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2997-3004. IEEE, 2014.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James
Davidson. Learning latent dynamics for planning from pixels. In International Conference Machine Learning, volume 97 of ICML' 19, pp. 2555 2565, Long Beach, California, USA, 2019.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in neural information processing systems, pp. 4565-4573, 4573, 2016.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. In Advances in Neural Information Processing Systems, pp. 12519-12530, 2019.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, al. Model-based reinforcement learning for atari. arXiv preprint arXiv: htt::::933003744 2019.
Péter Karkus, Xiao Ma, David Hsu, Leslie Pack Kaelbling, Wee Sun Lee, and Tomás Lozano-Pérez. Differentiable algorithm networks for composable robot learning. In Antonio Bicchi, Hadas Kress-Gazit, and Seth Hutchinson (eds.), Robotics: Science and Systems XV, University of Freiburg, Freiburg im Breisgau, Germany, June 22-26, 2019, 2019. doi: 10. 10.15607/RSS URL
httpps://oi.. http://.........../1/1501100. //SSS 201 9. XV 039
Rahul Kumar, Aditya Mandalika, S. Choudhury, and S. Srinivasa. Lego: Leveraging experience in
roadmap generation for sampling-basee planning. 2019 IEEE/RSI International Conference Intelligent Robots and Systems (IROS), pp. 1488-1495, 2019.
VengLing Kuo, Andrei Barbu, and Boris Katz. Deep sequential models for sampling bbsedd planning. In 2018 IEEE/RS. International Conference on Intelligent Robots and Systems (IROS), pp. 6490- 6497. IEEE, 2018.
Yunzhu Li, Hao He, Jiajun Wu, Dina Katabi, and Antonio Torralba. Learning compositional koopman operators for model-based control. In International Conference on Learning Representations, 2020.
URL httph:tt/://mm /ttp:////eeeeeeeeeeeeeeee / pnet/forunte forum? 12A4tPP
Jaynta Mandi, Emir Demirovic, Peter J. Stuckey, and Tias Guns. Smart predict-and-optimizz for hard combinatorial optimization problems. CoRR, abs/1911.10092, 2019. URL http:
//arxiv.erc/abs/113 10092
Ofrr Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3303-3313, 2018.
Gergely Neu and Csaba Szepesvári. Apprenticeship learning using inverse reinforcement learning and gradient methods. arXiv preprint 1206v:1200..500 2012.
Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In in Proc. 17th International Conf. on Machine Learning. Citeseer, 2000.
Vlad Niculae, André FT Martins, Mathieu Blondel, and Claire Cardie. Sparsemap: Differentiable sparse structured inference. arXiv preprint arXiv:1802..444 2018.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In Advances in Neural Information Processing Systems, pp. 6118 6128, 2017.
Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomenech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. Imagination-augnnen agents for deep reinforcement learning. Advances in neural information processing systems, 30:5690-5701, 2017.
11

---

Under review as a conference paper at ICLR 2021
Siddharth Reddy, Anca D Dragan, and Sergey Levine. Sqil: Imitation learning via reinforcement learning with sparse rewards. arXiv preprint 1rXiv:1905111008, 2019.
M. Rolínek, V. Musil, A. Paulus, M. Vlastelica, C. Michaelis, and G. Martius. Optimizing ranking- based metrics with blackbox differentiation. In Conference on Computer Vision and Puttern Recognition, CVPR'20 2020.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference artificial intelligence and statistics, pp. 627-635, 2011.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi- parimeaaamettic topological memory for navigation. In International Conference on Learning Representations, 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators.
In International Conference on Machine Learning, volume 37 of ICML, pp. 1312-1320, 2015.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. arXiv preprint arXiv: 1.08265, 2019.
David Silver, Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac- Amold, David Reichert, Neil Rabinowitz, Andre Barreto, al. The predictron: End-to-end learning and planning. In International Conference on Machine Learning, pp. 3191-3199. PMLR, 2017a.
David Silver, Hado van Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac- Amold, David Reichert, Neil Rabinowitz, Andre Barreto, and Thomas Degris. The predictron: End-to-end learning and planning. In International Conference on Machine Learning, volume 70 of ICML.'1, 17, pp. 3191-3199. PMLR, 2017b.
Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal plan- ning networks: Learning generalizable representations for visuomotor control. In International Conference on Machine Learning, volume 80 of ICML.' 18, pp. 4732-47411 Stockholmsmässan, Stockholm Sweden, 2018
Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting, ACM Sigart Bulletin, 164):160-163, 1991.
Richard S Sutton, Csaba Szepesvári, Alborz Geramifard, and Michael Bowling. Dyna-style planning with linear function approximation and prioritized sweeping. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, pp. 528-536, 2008.
Aviy Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. In Advances in Neural Information Processing Systems, pp. 2154-2162, 2016.
M. Vlastelica, A. Paulus, V. Musil, G. Martius, and M. Rolínck. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, ICLR 20, 2020.
Po-Wei Wang, Priya I. Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. arXiv preprint arXiv: 12049, 2019.
Ga Wu, Buser Say, and Scott Sanner. Scalable planning with deep neural network learned transition models. Journal of Artificial Intelligence Research, 68:571-606 2020.
Hengshuai Yao, Shalabh Bhatnagar, Dongeui Diao, Richard S Sutton, and Csaba Szepesvári. Multi- step dyna plamning for policy evaluation and control. In Advances in neural information processing systems, pp. 2187-2195, 2009.
Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, and Asako Kanezaki. Path planning using neural a* search. arXiv preprint arXiv:2009.07476 2020.
12

---

Under review as a conference paper at ICLR 2021
A DATA GENERATION
In order to do imitation learning, we needed to create expert data. For CRASH 5 x 5, CRASHI 5 5, LEAPER GRRID) and MAZE we can determine the exact ground truth costs leading to optimal behavior. As example, CRASH 5 x contains moving boxes that when encountered lead to instant death, meaning infinite costs and otherwise the fixed cost of moving around in the environment.
Since the environments become deterministic for fixed random seed, first unrolled their dynamics for each level. After obtaining the underlying grid structure and entities, we labeled them with costs and constructed graph that reflects the grid structure. An expert trajectory is constructed by applying Dijkstra's 's algorithm on this graph and the human-labeled costs and then executing in simulation.
For the CRASH JEWEL HUNT experiments, we randomly sampled 2000 solvable levels by varying number of boxes per column, their speed, the agent start position and the jewel position. The training levels were taken from the first half and the second half of levels was used for testing.For For the LEAPER (GRID) and MAZE environments we have taken the levels determined by seeds 0- 1000.
For CHASER, we applied similar procedure but additionally, we recorded two sets of human trajectories, as we observed benefits in performance by incorporating more different expert trajectories for the same level. Since both the search procedure and human labeling are time consuming for this environment, we collected fewer expert trajectories for the CHASER than for the other environments, 3 x 100, two thirds of which are from human players.
For this reason, we constructed the dataset for the CHASER by recording human trajectories. Moreover, we observed benefits in the training by incorporating more different expert trajectories for the same level.
Levels seeds 1000000-1001000 were taken for testing in the PROCGEN experiments.
B ENVIRONMENTS
Our method is applicable in discrete environments, therefore we evaluated on environments from the PROCGEN benchmark and the CRASH JEWEL HUNT environment.
We created the CRASH JEWEL HUNT environment evaluate our method, where the goal is for the fox (Crash) to reach the jewel. We found this environment convenient since we can influence the combinatorial difficulty directly, which not true for the PROCGEN benchmark where we are limited to the random seeds used in the OpenAl implementation. The sources of variation in the CR ASH JEWEI HUNT are the box velocities, initial positions, sizes, as well as the agent initial position and the jewel end position.
We modified the LEAPER environment to make discrete steps in the world in order to make our method applicable. This involved making the logs on the river move in discrete steps well as the agent. For an additional description the PROCGEN environmnets, we refer the reader to Cobbe et al. (2019).
C NETWORK ARCHITECTURE AND INPUT
For all of our experiments, we use the PyTorch implementation of the ResNet18 8 architecture as the base our model. All of the approaches receive two stacked frames of the two previous time steps as input in order to make dynamics prediction possible. For the PPO baseline, we didn't 't observe any benefit in adding the stacked frames as input and we used bableebaselines implementation from OpenAl in order to train it on the PROCGEN environments.
In the case of the behavior cloning bascline, the problem is a multi-class classification problem with the output being a multinomial distribution
actions.
For the variant NAP + oracle, we train a cost prediction network on top of which we run the Dijkstra algorithm the outputted costs of the planning graph. This requires modifications to the original ResNet18 architecture. We remove the linear readout the original ResNet18 architecture and replace it with the preceded by convolutional layer of filter size I and adaptive max pooling layer
13

---

Under review as a conference paper at ICLR 2021
obtain the desired dimensions of the underlying latent planning graph. More concretely, the output of the last ResNet18 block is followed by the following operation (as outputted by Py TyTorhh) to obtain the graph costs:
Sequential(
Conv2d(256,, 2, kemne__siz==(,, 1), stride=(1, 1))
Abs()
grid_ width))
Where grid_ (heighhttttt. denotes the height and width of the planning grid. For the full variant of NAP with goal and agent position prediction we have a separate position classifier that has the same base architecture the cost prediction network with 2 additional linear readouts for the likelihoods of the latent graph vertices, more concretely (as outputted by Py PyTorch):
Sequential(
Conv2d(256, 2, kernel_size=(1, 1), stride=(1, 1))
Abs()
AlapiixMaax/oooloouuuuusssieeees height, grid_ width)) Flatten()
Linear(grid__eiige x grid_width, grid_height grid_width)
For training the position classifier, we use standard cross-entropy loss on the likelihoods. For NAP with position classification, we use the ground-truth expert start and goal positions to calculate the Hamming loss of the predicted path by the solver. At evaluation time, NAP uses the position classifier to determine the start and end vertices the latent planning graph.
D TRAINING PROCEDURE
For CRASH 5 5. 5, CRASH 5 LEAPER(GRID) and MAZE train the models on the same #levels,
namely 1, 2. 5, 10, 20. 50, 100, 200. 500 and 1000. We evaluate on unseen 1000 levels in order to show that NAP exhibits superior generalization. The levels generated per description section For each dataset size we run experiments with 3 random seeds and normalize the data to be zero mean and unit variance. For all experiments, we make use the ADAM optimizer.
A
We determine the number of epochs for training depending on each dataset size as 15000) have roughly the same number of gradient updates in each ex- periment. We take the minimum over the 2 values because for smaller number of levels a large number iterations not necessary achieve good performance, but for larger number of levels necessary.
CRASH 5
CRASI 10
LEAPER(GRID)
MAZE
learning rate
10-3
10
10
10
0.2
0.2
0.15
0.15
A
20
20
20
20
resnet layers
kernel size
4
4
6
6
batch size
32
32
16
Table I:
Training hyperparameters, where alpha denotes the margin that used the vertex costs and À the interpolation parameter for blackbox differentiation od Dijkstra. We vary the kernel size of the initial convolution for ResNet18.
For the CHASER. the training conditions analogous the other environments, only of slightly smaller scale due to its higher complexity. Models were trained on 10, 20, 50, and 100 levels and evaluated on 200 unseen levels. Each model trained for 40 epochs.
14

---

Under review as a conference paper at ICLR 2021
CHASER
learning rate
le 3
0.2
40
resnet layers
kernel size
4
batch size
Table 2: Training hyperparameters for the CHASER experiment, where alpha denotes the margin that was used on the vertex costs and the interpolation parameter for blackbox differentiation od Dijkstra.
D.1 PPO TRAINING PROCEDURE
The training of the PPO baseline is exactly the described in Cobbe et al. (2019) using the official code from https: /ttg//gtttbb/bb/ com/ http///ppnaaaaaaee parrraiinnpoognn..... see Table 3 for the used parameters. The network architecture is the IMPALA-CNN. The algorithm is trained the specified number of levels for 200 million environments interactions. We report numbers for independent restarts.
learning rate
5e 4
0.2
discount y
0.999
entropy coefficient
0.01
steps per update
2
Table PPO hyperparameters, as used in Cobbe et al. 2019
15


Reviews:
[{"review_id": "nTJ13-GT17U", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a policy architecture that embeds graph search\nwithin it. The proposed architecture is suggested to show strong\ngeneralization capabilities due to the embedded combinatorial/discrete\nsearch. The authors study this architecture in the context of\nimitation learning from a small number of expert demonstrations. The\ncore approach builds on a previous work (Vlastelica et al. 2020) that\nprovides a framework for embedding combinatorial search within a\ndifferentiable model.\n\nOverall, I think this is a very solid work, and I recommend\nacceptance. The problem being studied is eminently important, and\nright now the field is in great need of policy optimization methods\nthat leverage the power of discrete search algorithms. The experiments\nare quite comprehensive, encompassing various gridworlds, and\ngenerally addressing the baselines I would have expected to see (most\nimportantly, Figure 6 which shows the performance vs. amount of data).\n\nThe biggest concern I have with the paper is that it is extremely\nunclear what exactly is meant by the assumption of a known topology of\nthe gcMDP. Does this topology basically represent the transition\nfunction (i.e., edges in the discrete state graph)? If so, then it\nseems unfair to compare to IL and RL baselines that are not given\naccess to this information. If not, then I really hope the authors can\nclearly convey (perhaps through a small example) what the topology is,\nand how much practical engineering effort is required to create it in\nyour domains.\n\nI am also curious how much stochasticity in the environment can be\nhandled by your method. This is in reference to the sentence \"Although\nthe actual gcMDP solved by the expert may be stochastic, we learn a\ndeterministic latent approximate gcMDP\".\n\nOne smaller question: when you say \"In gcMDPs the reward is such that\nthe maximal return can be achieved by reaching the goal state g\" --\nthis feels like a pretty weak condition to me, because it can be\nachieved by simply making the reward at g higher than the returns of\nany trajectory not reaching g. Is this condition necessary and\nsufficient for your approach to make sense?\n\nLooking ahead, I am curious if the authors have considered extending\nthe proposed system to continuous environments (e.g., if states are\nimages)? Perhaps a path forward here would be to learn an embedding to\na discrete latent space, and then apply NAP. I guess the challenge\nwould be that you would not be able to know the topology of that\nlatent a priori.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WdPphnUHPxK", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**SUMMARY**\n\nThis work proposes a novel neuro-algorithmic policy architecture for solving discrete planning tasks. It takes a high-dimensional image input and processes it through modified ResNet encoders to obtain a graph cost map and a start/goal heatmap. This is fed into a differentiable Dijkstra algorithm to obtain the shortest trajectory prediction which is trained using an expert-annotated trajectory via a Hamming distance loss. This module is evaluated in two dynamic game environments demonstrating generalization to unseen scenes.\n\n\n**STRENGTHS**\n- The general idea of integrating BlackBox combinatoric shortest path algorithms in a differentiable planning module is interesting and has a lot of potential to be useful. \n\n**WEAKNESSES**\n- The novelty compared to Vlastelica et al. (2020) is not clear.\n- The design choices are not clearly justified and the considered use-cases for this particular architecture are limited.\n- Important information is missing to make this work reproducible (see reproducibility section)\n- The evaluation considers only shortest-path planning scenarios that are amenable to the proposed architecture (see evaluation section). The authors should either provide a clear motivation of the considered scenario types or evaluation on scenarios learning more complex representations.\n\n**CLARITY**\n\nThe general idea of the work is clearly written although important information for reproducibility is missing (see below). I also felt that the authors did not make particularly good use of space. For example, Sec. 3 and Sec 4.1 could be condensed into a joint background section, leaving more space for more detailed experiments. The information in Sec 4.3 seems to be a better fit for either the related work or the conclusion section. \n\nSmaller clarification questions:\n- What is the y axis in fig 5 (a).\n- In the conclusion: What exactly is meant by knowing the topological structure of the latent planning graph a priori? How is this incorporated as an inductive bias into the neural network? \n\n**REPRODUCIBILITY**\n\nThe results in this work are not reproducible. Relevant information on training (e.g. which optimizer was used? what were the learning rates? ...), hyperparameters (which parameters were tuned? which range was considered? how were they tuned?), baseline method training (e.g., how long was PPO trained, how exactly were rewards defined, ...) and environment generation settings are missing.\n\n\n**EVALUATION**\n\nThe evaluation seems one of the weak points of this work. The problems here are threefold:\n1. the number of considered tasks is very limited and their type is very limited to scenarios where one image input provides enough information to generate a full cost map. This does not hold in most planning tasks. \n2. Because the architecture itself is a claimed contribution, this work would require a much more thorough evaluation of architecture design decisions such as which underlying CNN is used, what is the \n3. Simply using the PPO baseline is insufficient. First, there is no discussion on how and why this algorithm was chosen as a baseline. Second, more recent or closer related baselines are missing. Some of those are mentioned in related work and they seem to be more fair/useful comparison methods. \n\n\n**NOVELTY / IMPACT**\n\nThe work is not sufficiently motivated. While planning, in general, is an important problem and differentiable planners are an important research topic, the motivation of this work is not clear. The authors should not only name the use-cases where an intermediate planning module might be beneficial but also discuss what the main insights of this work are. As the authors write themselves, a differentiable implementation of TDSP in a neural network can simply be achieved by applying theory from Vlastelica et al. (2020). In fact, that paper already demonstrates the use of Dijkstra in a neural network computation graph. This opens up the question of what is the key idea and value of the present work? \n\nFurthermore, the authors did not sufficiently consider/discuss existing related work. The related work does not sufficiently cover state-of-the-art. Combining planning modules with deep learning pipelines (although in slightly different ways) has been considered in several works. More importantly, the related work should discuss why the proposed approach is beneficial compared to approaches containing differentiable planners. The related work is also missing numerous relevant papers. Some potential examples involve:\n\n- Kuo et al., Deep sequential models for sampling-based planning, IROS 2018\n- Kumar et al., LEGO: Leveraging Experience in Roadmap Generation for Sampling-Based Planning, IROS 2019\n- Gupta et al., Cognitive mapping and planning for visual navigation, CVPR 2017\n- Savinov et al., Semi-Parametric Topological Memory for Navigation, ICLR 2018\n- Tamar et al., Value Iteration Networks, NeurIPS 2016\n\nFinally, the related work section should not only provide a broader discussion of related works but also more clearly emphasize the relationship between these works and the present work (e.g. how and in what context is the present work better more useful than related works? Which ideas are used from related work and what is new to this work? ...).\n\n**REVIEW SUMMARY**\n\nOverall, I recommend rejection of this work because the issues raised in this review cannot be resolved without a significant amount of work. While this may be discouraging, I believe that the authors are considering an interesting topic that has a lot of potential and, after resolving the issues raised in this review, may result in a successful submission.\n\n**POST-DISCUSSION SUMMARY**\nI want to thank the authors for answering my questions and correcting misunderstandings and updating the paper. I still recommend rejection of this work given that the novelty is not yet fully clear. While the updated list of contributions is indeed a better match for this work, claiming that correct inductive biases improve generalization does not seem to be a new insight. As mentioned in my initial review, I still believe that the general line of work has a lot of potential and want to encourage the authors to fully address the general concerns raised in the reviews and resubmit the work.", "extra_scores": {}, "extra_text": {}}, {"review_id": "OneJypO3nuC", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary:\nThis paper presents a method to train a neural network to predict the time-dependent costs, and start and goal states needed to run time-dependent shortest-path planning in a dynamic 2-D environment. The non-differentiability of the path planning is handled by recent work on differentiating through blackbox combinatorial solvers from [1]. The method is trained in a supervised manner from expert trajectories. Evaluations are presented on 2-D time-varying games where the addition of the path-planner is shown to improve performance over an imitation learning and PPO baseline.\n\n##### Pros:\n- The method is simple and looks to perform well in the experiments.\n- The description of the approach is fairly clear and well written.\n\n##### Cons:\n- The novelty relative to [1] is quite low. Specifically, [1] already uses the blackbox differentiation to do shortest path solving using a neural network architecture to estimate the costs.\n- Overall, the evaluation is a bit lacking.\n- The paper is missing key details that would aid anyone trying to build off of or replicate this work.\n\n#### Decision:\nGiven the low novelty and not-so-strong evaluation, I do not recommend this paper for acceptance. \n\n#### Questions:\n1. As far as I can tell, the main novelty relative to [1] is the use of a time-varying cost function (albeit encoded into a shortest-path search as in [1]) and the learned start and goal encoder. Am I missing something else?\n2. How does this approach compare to the recent work of [2]?\n3. Is the imitation learning baseline behavior cloning or something else? This needs more detail.\n4. The set of baselines is insufficient since PPO does not make use of the expert trajectories. Something like GAIL [3] or SQIL [4], which combines RL and imitation learning, should be used in addition to the other two baselines.\n4. In Section 4.2, the set of admissible paths seems like it may be a hard constraint to satisfy. How do you accomplish this?\n\n#### Comments:\n1. Given that there don’t seem to be great baselines for these tasks, it would improve the evaluation to also show results on a simpler task that does have other baselines, such as non-time-varying shortest path search.\n2. Overall, the paper could use more detail on the architecture, the hyperparameters, the baselines, the domains, and anything else needed to get this to work. It would be quite nontrivial to reproduce this work from the paper alone. A subsection on training would also be nice, as the training details seem to be scattered throughout the other sections, which makes it hard to piece together exactly how it’s done.\n3. Please learn the difference between citep and citet (from natbib) and use them appropriately to make the citations more intelligible for the reader.\n4. The first paragraph of the intro doesn’t make it clear that this work falls on the first end of the discussed spectrum and uses expert demonstrations to learn from.\n5. For the related work section, don’t just list related work, contrast that work to your own so that the reader gets a better understanding of your method in the context of the existing work.\n6. Typo: preceding horizon planning → receding horizon planning.\n\n\n[1] Vlastelica, Paulus, Musil, Martius, Rolinek. Differentiation of Blackbox Combinatorial Solvers (2020).\n[2] Yonetani, Taniai, Barekatain, Nishimura, Kanezaki. Path Planning using Neural A* Search (2020).\n[3] Ho, Ermon. Generative Adversarial Imitation Learning (2016).\n[4] Reddy, Dragan, Levine. SQIL: Imitation Learning via Reinforcement Learning with Sparse Rewards (2019).\n\n\n\n****************************\n\nThank you for the response and updates to the paper. Given the number of changes required, I encourage the authors to resubmit elsewhere with the updated paper, ideally with additional experimental comparisons as discussed. Note that there are many other offline RL works, such as BCQ or BEAR, that you could use (see, e.g., \"D4RL: Datasets for Deep Data-Driven Reinforcement Learning\" or \"RL Unplugged: Benchmarks for Offline Reinforcement Learning\" for relevant algorithms). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0bc5TAuq_d6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper studies the problem of image-based planning in discrete state/action spaces. The paper proposes a neuro-algorithmic policy that can be trained end-to-end by differentiation and used together with a shortest path solver.\n\nStrengths:\n\ni) The motivation, organization and the overall writing of the paper are clear.\n\nWeakness:\n\ni) The manuscript is missing very relevant pieces of works that should have been discussed in detail and included as baselines in the experimental results section. Namely, the previous work (i.e., Latplan) [1,2] that performs (classical) planning from images in latent spaces using variational autoencoders in combination with off-the-shelf automated planners. Similarly, experimental comparison to work [3] is missing.\n\nii) How does the proposed approach (i.e., NAP) reason about the value of the planning horizon T which is an important aspect of automated planning? Note that Latplan would again provide useful insights here (since it leverages off-the-shelf automated planners).\n\niii) The benchmark domains seem too simple. For a more realistic image-based task, see Meta-World [4].\n\nAdditional comments:\n\nPage 1: In the third paragraph, can you please ground the claim for the statement “transition model is often harder than learning a policy”? Moreover, instead of just saying “there exists several approaches…”, you should include previous works [5,6,7] as references that learn such transition models for planning.\n\nPage 2: Second item in the list on page 2: generalizing policies -> generalized policies\n\nReferences:\n[1] Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary, Asai and Fukunaga AAAI-18.\n\n[2] Learning Neural-Symbolic Descriptive Planning Models via Cube-Space Priors: The Voyage Home (to STRIPS), Asai and Muise IJCAI-20.\n\n[3] Learning latent dynamics for planning from pixels, Hafner et al. ICML-19.\n\n[4] A benchmark and evaluation for multi-task and meta reinforcement learning, You et al. CoRL 2019.\n\n[5] Nonlinear Hybrid Planning with Deep Net Learned Transition Models and Mixed-Integer Linear Programming, Say et al., IJCAI-17.\n\n[6] Scalable Planning with Deep Neural Network Learned Transition Models, Wu et al. JAIR.\n\n[7] Optimal Control Via Neural Networks: A Convex Approach, Chen et al., ICLR 2019.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is about training a discrete policy that maps an image representation through a differentiable time-dependent path planning module. The method is based on [1] and the reviewers are concerned about lack of novelty with respect to this work, and also with [2], however the latter only appeared a few weeks before the ICLR deadline, so I am not factoring it in my recommendation. Unfortunately, in light of [1], 3/4 reviewers do not recommend acceptance, and I agree with them.

[1] Vlastelica, Paulus, Musil, Martius, Rolinek. Differentiation of Blackbox Combinatorial Solvers (2020). 
[2] Yonetani, Taniai, Barekatain, Nishimura, Kanezaki. Path Planning using Neural A* Search (2020).
Decision: Reject