Scaling up and Stabilizing Differentiable Planning with Implicit Differentiation
Authors: Linfeng Zhao
Huazhe Xu
Lawson L.S. Wong
Venue: ICLR 2023 poster (2023)

Abstract: Differentiable planning promises end-to-end differentiability and adaptivity. However, an issue prevents it from scaling up to larger-scale problems: they need to differentiate through forward iteration layers to compute gradients, which couples forward computation and backpropagation and needs to balance forward planner performance and computational cost of the backward pass. To alleviate this issue, we propose to differentiate through the Bellman fixed-point equation to decouple forward and backward passes for Value Iteration Network and its variants, which enables constant backward cost (in planning horizon) and flexible forward budget and helps scale up to large tasks. We study the convergence stability, scalability, and efficiency of the proposed implicit version of VIN and its variants and demonstrate their superiorities on a range of planning tasks: 2D navigation, visual navigation, and 2-DOF manipulation in configuration space and workspace.

Published as a conference paper at ICLR 2023
SCALING UP AND STABILIZING DIFFERENTIABLE PLANNING WITH IMPLICIT DIFFERENTIATION
Linfeng Zhao'; Huazhe Xu Lawson L.S. Wong'
' Khooury College of Computer Sciences, Northeastern University.
Institute for Interdisciplinary Information Sciences, Tsinghua University, Shanghai Qi Zhi Institute
ABSTRACT
Differentiable planning promises end-to-end differentiability and adaptivity. However, issue prevents it from scaling up to larger-scale problems: they need to differentiate through forward iteration layers to compute gradients, which cou- ples forward computation and backpropagation and needs to balance forward plan- ner performance and computational cost of the backward pass. To alleviate this issue, we propose to differentiate through the Bellman fixed-point equation de- couple forward and backward passes for Value Iteration Network and its variants, which enables constant backward cost (in planning horizon) and flexible forward budget and helps scale up to large tasks. We study the convergence stability, scal- ability, and efficiency of the proposed implicit version of VIN and its variants and demonstrate their superiorities on range of planning tasks: 2D navigation, visual navigation, and 2-DOF manipulation in configuration space and workspace.
INTRODUCTION
Planning is crucial ability in artificial intelligence, robotics, and reinforcement learning Valle, 2006; Sutton & Barto, 2018). However, most planning algorithms require either a model that matches the true dynamics model learned from data. In contrast, differentiable planning (Tamar et al., 2016; Schrittwieser et al., 2019; Oh et al., 2017; Grimm et al., 2020; 2021) trains models and policies in an end-to-end manner. This approach allows learning a compact Markov Decision Pro- cess (MDP) and ensures that the learned value is equivalent to the original problem. For instance, differentiable planning can learn to play Atari games with minimal supervision (Oh et al., 2017).
However, differentiable planning faces scalability and convergence stability issues because it needs to differentiate through the planning computation. This process requires unrolling network layers iteratively to improve value estimates, especially for long- horizon planning problems. As result, it leads to slower inference and inefficient and unstable gradient computation through multiple network layers. Therefore, this work addresses the question: how can scale up differentiatiable planning and keep the training efficient and stable?
In this work, we focus on the bottleneck caused by algorithmic differentiation, which backpropa- gates gradients through layers and couples forward and backward passes and slows down inference and gradient computation. To address this issue, propose implicit differentiable planning (IDP). IDP uses implicit differentiation to solve the fixed-point problem defined by the Bellman equations without unrolling network layers. Value Iteration Networks (VINs) (Tamar et al., 2016) convo- lution networks to solve the fixed-point problem by embedding value iteration into its computation. We name it algorithmic differentiable planner, or ADP for short. We apply IDP to VIN-based plan- ners such as GPPN (Lee et al., 201 8) and SymVIN (Zhao et al., 2022). This implicit differentiation idea has also been recently studied in supervised learning (Bai et al., 2019; Winston & Kolter, 2021; Amos & Yarats, 2019; Amos & Kolter, 2019).
Using implicit differentiation in planning brings several benefits. It decouples forward and backward passes, so when the forward pass scales up to more iterations for long-horizon planning problems,
"Corresponding Author: Linfeng Zhao zhao. iin@nhorthesttern.coo

---

Published as a conference paper at ICLR 2023
%
Dx-1
Qx
Px V
Layerr
Bppu Aiject
R
Dx-1
Qx
Px te
Ic Hersiiin
L
Ippot Inject
R
Bockward Expliot Gradient
Pass: Implitt Gradient
Figure I: An overview of VIN, planner with algorithmic differentiation, and ID-VIN, our proposed planner with implicit differentiation. Lighter colors for the backward pass with algorithmic differentiation (solid red arrows) indicate larger backpropagation depth. For backward passes with implicit differentiation, the dashed red arrows start from the solved equilibrium V and end each forward layer (black arrows).
the backward pass can stay constant cost. also no longer constrained to differentiable forward solvers/planners, potentially allowing other non-differentiable operations in planning. It can po- tentially reuse intermediate computation from forward computation in the backward pass, which infeasible for algorithmic differentiation. We focus scaling up implicit differentiable planning to larger planning problems and stabilizing its convergence, and also experiment with different op- timization techniques and setups. In experiments various tasks, the planners with implicit differentiation can train on larger tasks, plan with longer horizon, use less (backward) time in training. converge more stably, and exhibit better performance compared to explicit counterparts. We summarize our contributions below:
We apply implicit differentiation VIN-based differentiable planning algorithms. This connects with deep equilibrium models (DEQ) (Bai et al., 2019) and prior work in both sides, including (Bai al., 2021; Nikishin al., 2021: Gehring al., 2021).
We propose a practical implicit differentiable planning pipeline and implement implicit differen- tiation version of VIN, as well as GPPN (Lee al., 2018) and Sym (Zhao et al., 2022).
We empirically study the convergence stability, scalability, and efficiency of the ADPs and pro- posed IDPs, on four planning tasks: 2D navigation, visual navigation, and 2 degrees of freedom (2-DOF) manipulation configuration space and workspace.
RELATED WORK
differentiable planning refer planning with neural networks, which can also be named learning to plan and may be viewed as a subclass of integrating planning and learning (Sutton Barto, 2018). It is promising because it can be inte- grated into a larger differentiable system to form a closed loop. Grimm et al. (2020; 2021) propose understand model-based planning algorithms from value equivalence perspective. Value iteration network (VIN) (Tamar et al., 2016) is a representative work that performs value iteration using con- volution on lattice grids, and has been further extended (Niu et al., 2017: Lee et al., 2018: Chaplot et al., 2021; Deac et al., 2021) and Abstract VIN (Schleich et al., 2019). Other than using convolu- tion network, the work on combining learning and planning includes (Oh al., 2017; Karkus al., 2017; Weber al., 2018; Srinivas et al., 2018; Schrittwieser et al., 2019; Amos & Yarats, 2019; Wang & Ba, 2019; Guez et al., 2019; Hafner et al., 2020; Pong et al., 2018; Clavera et al., 2020).
Differentiable Planning In this paper,
Implicit Differentiation Beyond computing gradients by following the forward pass layer-by- layer, the gradients can also be computed with implicit differentiation to bypass differentiating through some advanced root-find solvers. This strategy has been used in body of recent work
2

---

Published as a conference paper at ICLR 2023
Task 15 x55
Task x27
Task x949
0.8
Success Rate
0.6
VIN
SymVVN
ConvGPPN
0.2
#tterationsol.ayers Kayer
#lterations/Layerss Kuyer
#lterations/layers Kayer
Figure 2: Demonstration of differentiable planners with algorithmic differentiation, which cannot scale up to large tasks more iterations, duc coupled forward and backward pass.
(Chen al., 2019; Bai al., 2019; Amos & Kolter, 2019; Ghaoui et al., 2020). Particularly related, Bai et al. (2019) propose Deep Equilibrium Models (DEQ) that decouples the forward and backward pass and solve the backward pass iteratively also through a fixed-point system. Winston & Kolter (2021) study the convergence of fixed point iteration in specific type of deep network. Amos & Kolter (2019) formalize optimization as a layer, and Amos Yarats (2019) further apply the idea to iterative LQR. Gehring et al. (2021) theoretically study gradient dynamics of implicit parameter- ization of value function through the Bellman equation. Nikishin et al. (2021) similarly use implicit differentiation, while they explicitly solve the backward pass and only work small-scale tasks because explicit solving is not scalable. Bacon et al. (2019) instead focus on Lagrangian perspec- tive. Our work is focused on scalability and convergence stability differentiable planning, and experiments with challenging tasks in simulation to empirically justify the approach.
3 DIFFERENTIABLE PLANNING WITH ALGORITHMIC DIFFERENTIATION
Background: Value Iteration Networks. Value iteration is an instance of the dynamic program- ming (DP) method to solve Markov decision processes (MDPs). iteratively applies the Bellman (optimality) operator until convergence, which is based on the following Bellman (optimality) equa- tion: Q(8, a) = R(s,a) a) + +7 a
and V(s) = max, (s,
Tamar et al. (2016) used convolution network to parameterize value iteration, named Value Itera- tion Network (VIN). VINs jointly learn and plan in latent MDP on the 2D grid, which has the latent reward function R: 2² |AA and has transition probability P represented WV - R|
which only relies on differences between states. The value function is written as V Z - IR and Q 22
Al, Value iteration can be written as:
Qa.' Ra,i.
()-1) EWY
(e(k) (J
max 2(h)
(1)
If we let f be single application of the Bellman operator, Eq. can be written as: (K) ((V(k-1), R. VV) = max Re W.Y (k-1)) = max R ConnvDD(V(-D wY) (2)
where convolution WY V is implemented as a 2D convolution layer Conv2D with learnable weight WV_ For simplicity, later use 0 refer network weights, and write each iteration as Uk+1 f(ve, r, 0), where r stands for reward map R and Uy for value map (R))
Pitfall: Coupled forward and backward pass. The forward computation of VIN iteratively ap- plies the Bellman update f. Thus, the optimization needs automatic differentiation: differentiating through multiple layers of forward iterations fo f .... f. Using automatic differentiation for VIN has major drawback: the forward computation of value iteration ("forward pass") and the computation of its gradients ("backward pass") are coupled. That is, the planning horizon is en- larged, VINs would need larger number of iterations propagate the value from goals remaining positions. As used in VIN and GPPN (Tamar et al., 2016; Lee et al., 2018), it requires intensive memory usage to store every intermediate iterate (kk to enable automatic differentiation.
To illustrate the effects, show the performance of ADP in Figure 2, including three models with increasingly higher memory use and time cost: VIN, SIN (Zhao et al., 2022) and ConvGPPa (a modified version of GPPN (Lee et al., 2018)). They are trained on 15 15, 27 x 27, and 49 49 path
3

---

Published as a conference paper at ICLR 2023
planning tasks. To solve larger mazes, each model consumes more memory while also needing more iterations (x-axes). However, since algorithmic differentiation requires backpropagating gradients layer by layer, with more iterations or larger tasks, some models either diverge out of memory (11GB limit). We present further experimental details and analyses in Section 5.2.
4 APPROACH: FROM Explicit TO Implicit Differentiation FOR PLANNING
This section introduces a strategy with implicit differentiation to resolve the issue by decoupling the forward and backward computation. We first derive implicit differentiation for VIN-based planners, then propose pipeline for implementing those planners with implicit differentiation. We refer to them as implicit differentiable planners (IDP), in contrast to algorithmic differentiable plannrrs (ADP) with algorithmic differentiation. We analyze the technical differences and similarities of IDPs vs. ADPs afterward.
4.1 IMPLICIT DIFFERENTIATION FOR VALUE ITERATION
We derive implicit differentiation for VIN and variants, where each layer f is a step as in value iteration. Since the derivation does not rely the concrete instantiation of f. we freely replace from Conv2D with other types of layers. We will introduce these variants the next subsection.
Implicit differentiation. A fixed-point problem be solved iteratively by fixed-poin iteration and other algorithms. However, as pointed out in (Bai et al., 2019), naively differentiating through the solver would require intensive memory usage, since it needs to store every intermediate iterate (A) to enable automatic differentiation, recently in (Bai et al., 2019; Nikishin et al., 2021; Gehring et al., 2021), another solution is to instead differentiate directly through the fixed point 2* using the implicit function theorem and implicit differentiation. Then, we can skip all of this by decoupling forward (fixed-point iteration as the solver) and backward pass (differentiating through the solver).
in (Tamar al., 2016; Lee et al., 2018). As also used
We start with the fixed point equation v* = f(v", r(,""r,, 0) from the Bellman optimality equation. Below we use to stand for either input r or O. The implicit function theorem tells us that, under some mild conditions of the derivatives (f is continuously differentiable with non- non-singular Jacobian ()(w)))/Bm) o (az) a differentiable function x: locally: 0 = f(v" fxx) m)).
For fixed point equation, we can assume the fixed point solution o* is obtained, thus this can be used to compute the partial derivative w.r.t. to any quantity (input, parameter, etc) du ()/ao)). . It avoids backpropagating gradients through the forward fixed-poine iteration, which is computationally inef- ficient and requires considerable memory to store intermediate iteration variables. Additionally, also allows to even use of non-differentiable operations in the forward pass.
Diffcrentiating both sides the equation 2' = f(v", x)) and applying the chain rule:
do (.) af(v* x) Os(v*, x)) v+(-) 0s(0", x))
(3)
a(-)
0(-)
do 0())
((-)
where we use (.) to denote an arbitrary variable. Rearranging terms:
Ov-()
(T T a5(o", ,x)
0f(v", x))
(4)
a(.)
Ov
0(-)
Solving backward pass. To integrate into a deep learning framework for automatic differentia- tion, two quantities needed: VJP (vector-Jacobian product) and JVP (Jacobian-vector product) (Gilbert, 1992). Nevertheless, the computation of the inverse term (I af(e" ==)/o=)) can be a major bottleneck due its dimension (O(d)) or O(m²), where m is the map size) (Bai et al., 2019; 2021). l). Additionally, when applied to VINs, we concatenate a policy layer that maps the final equilibrium E Rm action logits Rm and compute the cross-entropy loss E(-) (Tamar et al., 2016). Thus, the derivative of loss is:
m² is the matrix width and
ai do+()) dE (1 0f(v*.z) dv
-1 Of(u* x))
(5)
0())
Fv 0(.)
Fe"
0(-)
4

---

Published as a conference paper at ICLR 2023
Vx
Mapper
Envronment
3aniio
R
Planner
Figure 3: The proposed pipeline of implicit differentiable planning by using implicit differentiation.
Defining w as follows forms a linear fixed-point system (Bai et al., 2019):
Ov" (1
de
0f(v" x
0f(v" x))
w
T
w
w
(6)
O0
Ov
Oo
This backward pass fixed-point point equation can also be solved by a generic fixed-point solver or root finder. Then, we can substitute the solution w back: 8F/ac.) = w 8f("" "f("",m//a() The computation is then purely based on VJP and JVP. summary, an IDP needs to solve both the (nonlinear) forward fixed-point system and the (linear) backward fixed-point system, as in DEQ.
4.2 PIPELINE OF IMPLICIT DIFFERENTIABLE PLANNING
We can derive variants of VIN using implicit differentiation by abstracting out the implementation of value iteration layer. In this section, we propose generic implicit planning pipeline to extend our approach Gated Path Planning Networks (GPPN) (Lee et al., 2018) and Symmetric VIN (SymVIN) (Zhao et al., 2022). Spatial Planning Transformers (SPT) (Chaplot et al., 2021) also fits into the pipeline, but performs less well, as discussed Section
Figure shows the general pipeline, where the network layer fo can be replaced by any single layer that is capable of iterating values. The pipeline follows VIN and GPPN, where for 2D path planning map z² + {0, 1} is provided, and the planners' output actions (their logits) for each position 2 + RIAI, All these tasks can be represented as taking form of map "signal" over grid Z2, as previously been done (Zhao al., 2022; Chaplot et al., 2021).
Planner instantiations. We now introduce the instantiations of implicit planners one by one. We focus on the value iteration part (omit map input and action output), and planners follow the form (k++1) fe( (V)),,, R) (bars omitted later). There are two design principles: (I) input inject (R must be imput, as input x) and (2) weight-tied (0 is shared across layers f), as also used in DEQ (Bai et al., 2019). Specifically, the purpose of input inject is that fixed-point solution V does not depend on initialization (0), so we must pass information of the map through input inject (by R).
(i) ID-VIN uses regular 2D translation-equuvarianl
convolution layer, where f(V, = max, Rt + Conv2D(V; 0). (ii) ID-Sym aims integrate symmetry into planning and uses equivariant E(e)-steeaable CNN (Weiler & Cesa, 2021). It has similar form to VIN and just replaces Conv2D with SteerableConv, thus the form is f(V, R) max, R SteerableConv(*
(iii) ID-ConGGPPN is based on our modified version of GPPN (Kong, 2022; Zhao et al., 2022), where we (1) use GRU since it has single input with form z' GRU(z, x:) and is easier to integrate into our current form, (2) replace all fully connected layers with convolution layers, and (3) inject to every step. The result is that every layer a ConvGRU instead of LSTM in GPPN: S(V, Rt) ConvGRU(V, Rt 0). Note that the GPPN variants do not have max in each iteration anymore and directly take reward R to the recurrent cell (Lee et al., 2018).
Mapper Layer. We can handle tasks with more challenging input, such as visual navigation and workspace manipulation (Lee et al., 2018; Chaplot et al., 2021; Zhao et al., 2022), by learning an additional mapping network (mapper) to first map the input environments and mapper implementation are deferred to Section 5.1 and Section C.
2D map. Further details about
Optimization. We build upon the deep equilibrium model (DEQ) and relevant work (Bai et al., 2019; 2020; 2021), 1), which includes several effective techniques. By representing the implementation of value iteration fixed-poin point solving, have the flexibility any fixed-point root solver
5

---

Published as a conference paper at ICLR 2023
Task x5
Task 27.
Task
0.8
model
Soccess
0.4
ID SymVIN ID-CorVGPPN
0.0
30
50
30
50
Forward Pass lterations Krad
Forward Pass Iterations Kewe
Forward Pass keerations Kedi
Figure 4: Performance of implicit differentiable planners 2D navigation tasks. Since the forward and backward pass are decoupled, the IDPs keep consistent runtime and memory cost for hackward pass while have forward pass value iteration converged for large tasks and iterations.
for f(v.0) 0) = v or v VIN's feedforward network (Tamar al., 2016). However, recent work has employed Anderson's or Broyden's method (Bai et al., 2019; 2020). In our experiments, we compare the use of forward iteration and the Anderson solver in both forward and backward passes. Notably, the SymVIN architecture requires the entire forward pass to be equivariant, so extra attention is necessary when designing the forward solver. Further details and results can be found in Sections C and E.
= 0. A straightforward solver forward iteration, as used in
4.3 IMPLICIT VS. EXPLICIT DIFFERENTIABLE PLANNERS
Underlying computational similarity. The gradient computation done by automatic differen- tiation (Gilbert, 1992). For algorithmic differentiation, the gradients are computed through direct backpropagation and the implementation is also based on efficiently computing vector-Jacobian product (VJP) and Jacobian-vector product (JVP) (Bai et al., 2019). Christianson (1994) studied automatic differentiation for implicit differentiation of fixed-point system. The only difference the number of operations required and that implicit differentiation is based on the Jacobian at the equilibrium. We derive the connection in Section B.
Implicit vs. algorithmic differentiation. In Figure 4, we compare the performance of three IEPs with different numbers of iterations in the forward pass. Unlike the ADPs shown in Figure 2, our IDPs converge stably with larger forward-pas pass iterations (horizontal axis), while ADPs sometimes diverge on large iterations. Note that we should not directly compare IDPs and ADPs with the same number of forward iterations since they refer to different things: IDPs compute an equilibrium and use it for backward pass (more forward iterations would be better), while for ADPs # iterations # layers (more iterations/layers leads instability). Further analyses in Section 5.2.
Comparison:
The quality of equilibrium. Theoretically, IDPs have a constant cost of the backward pass with respect to the forward planning horizon. However, the backward pass requires the Jacobian of the final equilibrium v* sJ UK from the forward pass. If the equilibrium v* is not solved reason- ably well, the backward pass Eq. 6 would iterate based on an inaccurate Jacobian (f (f(="".))00 .n)/au" which would cause poor performance. In contrast, because ADPs compute exact gradients by back- propagation through layers, they do not suffer from this issue. Additionally, fewer iterations (layers) would also alleviate their convergence issues.
Tradeoff:
Empirically, with fewer forward iterations (e.g.. 10), we observe a performance drop from IDPs. Although ADPs also perform worse with fewer layers, they have smaller drop compared to IDPs. However, when scaling up to more forward iterations Kiwd (e.g. 2 30 iterations, which are necessary for maps > 27 27) IDPs may solve the equilibrium well enough and are more favorable because of their efficient backward pass. Moreover, we find that using around Kowd Ps 15 iterations for backward pass works well enough consistently across different map sizes (15 15 through 49 49). Since both algorithmic and implicit differentiation use a similar amount of vector vector-matrix products, using more than K inyer 15 R Khod would consume more resources and favor IDPs.
EMPIRICAL ANALYSIS
We present more results on convergence, scalability, generalization, and efficiency, which extends the study in previous sections comparing implicit algorithmic differentiable planners.

---

Published as a conference paper at ICLR 2023
Visslized Panoramic View
Workspace To C-spce
Endito-erd en-
Diections)
Learned (or iteravee alpratin
2D Novigation and Visual Mavigation
Workspace Monipulction and Cupace Menipuattion
Figure 5: (Left) We randomly generate occupancy grid z {0, 1] for 2D navigation. For visual naviga- tion, each position provides 32 x 32 3 egocentric panoramic RGB images 4 directions each location z² + Ig+ xxxxxxxxxxx22 One location is visualized. (Right) The top-down view (left) is the workspace of a 2-DOF manipulation task. For workspace manipulation. it is converted by mapper layer to configuration space, shown in the right subfigure. For C-space manipulation, ground- truth C-space is provided to planners.
5.1 ENVIRONMENTS AND SETUP
Environments and datasets. We run implicit and algorithmic differentiable planners on four types of tasks: (1) 2D navigation, (2) visual navigation, (3) 2 degrees of freedom (2-DOF) configuration space manipulation, and (4) 2-DOF workspace manipulation. These tasks require planning on manipulation) or learned maps (visual navigation and 2-DOF workspace manipulation). where the maps are 2D regular grid as in prior work (Tamar et al., 2016; Lee et al., 2018; Chaplot et al., 2021). To learn maps, planner needs to jointly learn mapper that converts egocentric panoramic images (visual navigation) or workspace states (workspace manipulation) into a 2D grid. We follow the setup in (Lee et al., 2018; Chaplot et al., 2021) and further discuss in Section D. both cases, we randomly generate training, validation and test data of 10K /2K /2K maps for all map sizes. For all maps, the action space is to move in 4 O directions: A = (north, west, south, east).
either given (2D navigation and 2-DOF configuration-spar
Training and evaluation. We report success rate and training curves over 5 seeds. The training process (on given maps) follows (Tamar et al., 2016; Lee et al., 2018; Zhao et al., 2022), where we train 60 epochs with batch size 32, and use kernel size F = 3 by default. We use RTX 2080 Ti cards with 1GB memory for training, thus we use 1GB as the memory limit for all models.
5.2 CONVERGENCE AND SCALABILITY
In the previous sections with Figure 2 and 4, we have presented quantitive analysis of IDPs and ADPs in terms of convergence with more iterations and scalability larger tasks. Here, we provide the detailed setup of the experiment and put the attention more on the qualitative side.
Setup. We train all models on 2D maze navigation tasks with map sizes 15 15, 27 27, and 49 x 49. We use Kinyer = 30, 50, 80 iterations for ADPs, which is effectively the number of layers in their networks. Correspondingly, for IDPs, we choose use forward iteration solver for forward pass and Anderson solver for backward pass. We fix the number of iterations of backward solver as Kowd 15 and of forward solver as Kiwd 30, 50, 80.
We examine results by algorithm and focus on their trend with iteration number (x-axis) and map size (column), not just the absolute numbers. The conclusion already mentioned in the above section: Beyond an intermediate iteration number (around 30-50), IDPs are more favorable because of scalability and computational cost. We present other analyses here.
Results.
We start from ConyGPPN and ID-ConyGPPN, which perform the best in ADPs and IDPs class, re- spectively. They also have the most number of parameters and use greatest time because of the gates in ConvGRU units. As shown in Figure 2, this also caused two issues of ConvGPPN: scalability to larger maps/iterations (out of memory for 27 x 27 80 iterations and 49 x 49 50 and 80 iterations), and also convergence stability (e.g. 27 27 50 iterations).
For Sym and ID- SIN they replace Conv2D with SteerableCont with computational cost slightly higher than VIN and much lower than ConvGPPN, Thus, they successfully run all tasks and iteration numbers. However, we find that explicit Sym may diverge due bad ini- tialization, and this is more severe if the network is deeper (more iterations), in Figure 2's 50 and

---

Published as a conference paper at ICLR 2023
Forward Time
Task 15
Task x
Task 49
Forward Time
Task 15
27 27
Task
200
200
100
1.00
50 #Layers Kuyer
50
Layers Kayer
Kiws
Kees
Kivi
Backoward Time
Task 27
Backward Time
Task
Task 27
Task 49
100
50
50
Layyers Kayw
Kiva
Forward Kies
Forward Kiva
SymViN
ID-SymVII
ID-CanvCPPM
Figure 6: The runtime (in seconds) on 2D navigation tasks with size 15, 27 x 27, 49 x 49, averaged over 5 seeds. The ADPs are on the left six figures and the IDPs on the right. Missing dots are due to out of memory caused by algorithmic differentiation. The upper row is for forward pass runtime, and the lower row is for backward runtime. The horizontal number iterations, and (2) IDPs: the forward pass iterations Krud.
differently: (1) ADPs: the number of layers K Kayer also
2.2
Su00ss0 tate
Succesttu Sate
0.5
0.4
20
20
32
52
50
20
20 Epacha
50
60
Spocts
<TH
D-W
SymiiM
D. 5-yymi
Figure 7: (Left) Training curves 2D maze navigation 15 15 maps, with 80 layers for ADPs and 80 iterations for IDPs. (Right) Training curves x 49 maps, with 30 layers for ADPs (due scalability issuc) and 80 iterations for IDPs.
80 iterations. Nevertheless, ID-SymVIN alleviates this issue, since implicit differentiable planning decouples forward and backward pass, so the gradient computation is not affected by forward pass.
Furthermore, VIN and ID-VIN are surprisingly less affected by the number of iterations and problem scale. We find their forward passes tends to converge faster to reasonable equilibria, thus further increasing iteration does not help, nor break convergence as long as memory is sufficient.
Forward and backward runtime. We visualize the runtime of IDPs and ADPs in Figure 6. For IDPs, we use the forward-iteration solver for the forward pass and Anderson solver for the backward pass. Note that in the bottom left, we intentionally plot backward runtime vs. forward pass iterations. This emphasizes that IDPs decouple forward and backward passes because the backward runtime does rely forward pass iterations. Instead, for ADPs, value iteration is done by network layers, thus the backward pass coupled: the runtime increases with depth and some runs failed due to limited memory (1IGB, see missing dots).
Therefore, this set of figures shows better scalability of IDPs (no missing dots out of memory and constant backward time). In terms of absolute time, the forward runtime of IDPs when using the forward solver is comparable with successful ADPs.
5.3 TRAINING PERFORMANCE
Setup. Beyond evaluating generalization to novel maps, we compare their training efficiency with learning curves. Each learning curve is aggregated over 5 seeds, which are from the models in the above section. The learning curves are for all planners on 15 x 15 maps (Figure left) and 49 x 49 maps (Figure 7 right, 30 layers for ADPs due to scalability issue and 80 iterations for IDPs).
Results. On 15 x 15 maps, we show Kaayer = 80 layers for ADPs and Kiwd = 80 iterations for IDPs. ID- DD-ConNGPPN performs the best and is much more stable than its ADP counterpart ConyGPPN. ID- VIN learns reliably, while VIN VIN fails to converge due to instability from 80 layers. VD-VIN and VIN comparable throughout training. On 49 49 maps, visualize Kinee 30 layers
8

---

Published as a conference paper at ICLR 2023
for ADPs (due to their limited scalability) and Kiwd 80 iterations for IDPs. ConvGPPN cannot run at all even for only 30 layers, while ID-ConvGPPN still reaches a near-perfect success rate. ID- SymVIN learns slightly better than Sym and reaches higher asymptotic performance. ID-VIN has a similar trend to VIN, but performs worse overall due to the complexity of the task.
5.4 PERFORMANCE ON MORE TASKS
Table I: Averaged test success rate (%) over 5 seeds using 10K/2K/2K dataset on rest types of tasks. We highlight entry with italic for runs with at least one diverged trial (any success rate < 20%).
Type
Methods
18 x 18 Mani.
36 x 36 Mani.
Workspace Mani.
Visual Nav.
VIN
89. 77.77
74.75
80.98 =3.84
66.11 18.991
Explicit
SImVIN
55. 44455
65.72:147.11
82. 24.777
96. 1:224
ConvGPPN
79.71:20.71
70.55:1336.1
70.23 199.44
81.76.131.0
Implicit
ID-VIN
80.53+6.08
56.27-120.92
77.17=7.24
62.53+15.9p
ID SymVIN
99. 19.633.m 20.08
08.53:11.44
87. 87.60=24.11
86.41:3300
(ours)
ED-COINGPPN
97.28 80.74
93.60 1.668
92.60=1..8
98.91 1..34
Setup. We run all planners on the other three challenging tasks. For visual navigation, we randomly generate 10K/2K/2K maps using the same strategy as 2D navigation and then render four egocentric panoramic views for each location from produced 3D environments with Gym- MiniWorld (Chevalier-Boisver) 2018). For configuration-saace manipulation and workspace manipulation, we randomly generate 10K/2K/2K tasks with to 5 obstacles workspace. In configuration-space manipulation, we manually convert each task into a 18 x 18 or 36 36 map (20% or 10 per bin). The workspace task additionally needs a mapper network to convert the 96 x 96 workspace (image of obstacles) to an 18 x 18 2-DOF configuration space (2D occupancy grid). We provide additional details in the Section D.
Results. In Table 1, due to space limitations, average over Kayer = 30, 50, 80 for ADPs and Kiwd = 30, 50, 80 for IDPs. For each task, we present the mean and standard deviation over 5 seeds times three hyperparameters and provide the separated results Section E. We italicize entries for runs with at least one diverged trial (any success rate < 20%).
Generally, IDPs perform much more stably. On 18 18 or x6x366 configuration-space manipulation, ID-SymVIN and DD-ConGGPPN reach almost perfect results, while ID-VIN has diverged runs on 36 (marked in italic). SyMVIN and ConvGPPN are more unstable, while VIN even outperforms them and is also better than ID- VIN. On 18 x 18 workspace manipulation, because of the difficulty of jointly learning maps and potentially planning on inaccurate maps, most numbers are worse than in configuration-sper space. 1D-CovvGPPS still performs the best, and other methods are comparable. For 15x 15 visual navigation, needs to learn a mapper from panoramic images and more challenging. ID-ConyGPPNN is still the best. ID-Sym exhibits some failed runs and gets underperformed by Sym in these seeds, and ID-VIN is comparable with VIN.
Across all tasks, the results confirm the superiority of scalability and convergence stability of IDPs and demonstrate the ability of jointly training mappers (with algorithmic differentiation for this layer) even when using implicit differentiation for planners.
6 CONCLUSION
This work studies how VIN-based differentiable planners can be improved from an implicit-function perspective: using implicit differentiation solve the equilibrium imposed by the Bellman equation. We develop a practical pipeline for implicit differentiable planning and propose implicit versions of VIN, SymVIN, and ConyGPPN, which is comparable to or outperforms their explicit counterparts. We find that implicit differentiable planners (IDPs) can scale up to longer planning-horize horizon tasks and larger iterations. In summary, IDPs are favorable for these cases to ADPs for several reasons: (1) better performance mainly due to stability, (2) can scale up while some ADPs fail due to memory limit, (3) less computation time. On the contrary, if using too few iterations, the equilibrium may be poorly solved, and ADPs should be used instead. While focus on value iteration, the idea of implicit differentiation is general and applicable beyond path planning, such as in continuous control where Neural ODEs can be deployed solving ODEs PDEs.

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENT
This work was supported by NSF Grant #2107256. We also thank Clement Gehring and Lingzhi Kong for helpful discussions and anonymous reviewers for useful feedback.
REPRODUCIBILITY STATEMENT
We provide an appendix with extended details of implementation in Section D, experiment details in Section D, and additional results in Section E. We plan to open-source our code next.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Brandon Amos and J. Zico Kolter. OptNet: Differentiable Optimization Layer in Neural Net- works. arXiv:/703 /003000433 [cs, math, stat], October 2019. URL httt::/exxxi.... /bs/ 1103.0044 43.
arXiv: 1703.00443.
Brandon Amos and Denis Yarats. The Differentiable Cross-Entropy Method. September 2019, doi: 10/g4 URL https: //wxxvvv/vvv////////////a///iiiv org/ /ags/////// /0909.99.... 11.9999.20 12830v4.
Pierre-Luc Bacon, Florian Schäfer, Clement Gehring, Animashree Anandkumar, and Emma Brun- skill. A Lagrangian Method for Inverse Problems in Reinforcement Learning. pp. 12, 2019.
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep Equilibrium Models, arXiv:1909. 01377 [cs, stat], October 2019. URL http: htttttpp//axxiiooootte http//axxivii...... hbtpg//bb/19900 01377. arXiv: 1909.01377.
Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Multiscale Deep Equilibrium Models.
Ntl::0006.08656 (cs, stat], November 2020. URL http://arxiv...ttt wwtpp/wwwwww..////////e/e///
08656. arXiv: 2006.08656.
Shaojie Bai, Vladlen Koltun, and Zico Kolter. Stabilizing Equilibrium Models by Jacobian Regu- larization. Technical Report arXiv:2106. 14342, arXiv, June 2021, URLhttp: /ttptt:://axxx.ooooto
abs/2106. 14342. arXiv:2106.143: 14342 [cs, stat] type: article.
Devendra Singh Chaplot, Deepak Pathak, and Jitendra Malik. Differentiable Spatial Planning using Transformers. arXiv:2112.01011 [cs], December 2021. URL http: /ttp:///aaivvvviiv///i/ org/ / 1112.01010 arXiv: 2112.01010.
Ricky Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural Ordinary Differential Equations. Technical Report arXiv: 180.0766,,,, arXiv, December 2019. URL
http://arxiii wttp://wor///b//////// 07366. arXiv:1806.07336 [es, stat] type: article.
Maxime Chevalier-Boisvert. Miniworld: Minimalistic 3d environment for rl & robotics research.
https://githul coommaxximecib haa.mmeee/gggmmmmmmmmemee ///ggygmmmii qym-miniworld, 2018.
Bruce Christianson. Reverse accumulation and attractive fixed points. Optimization Methods and Software, 3(4):311-326, January 1994. ISSN 1055-6788, 1029-4937. doi: 10/ethege. URL
http://www. htw.:.aaddfooe www.fnannnnnnneneee han//ooi/abaa abs 108010000000 11w..000000011188888888888000
Ignasi Clavera, Violet Fu, and Pieter Abbeel. Mogmee-ugmentedd Actor-Critic: Backpropagating through Paths. arXiv:2005. 08068 [cs, stat], May 2020. URL http:://rxiv..////////// 2005.00000 08068.
arXiv: 2005.08068.
Andreea Deac, Petar Veličković, Ognjen Milinković, Pierre-Luc Bacon, Jian Tang. and Mladen Nikolić. Neural Algorithmic Reasoners are Implicit Planners. October 2021. URL https:
//aaxiv.org/abb...............aa /2100 00..2.154.1111
Clement Gehring, Kenji Kawaguchi, Jiaoyang Huang, and Leslie Pack Kaelbling. Understanding End-to-End Model-Based Reinforcement Learning Methods Implicit Parameterization. May 2021. URL https:::: http::////eeeeeeeeeeee net fort/ffrum? d==x wwt.
-900e.
Laurent Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Y. Tsai. Implicit Deep Learning. Technical Report arXiv:1908.06:3 arXiv, August 2020. URL http:///rxxx
orgg/bss/990 0631.. arXiv:1908.066: 193119988.0061511111 [cs, math, stat] type: article.
Jean Charles Gilbert. Automatic differentiation and iterative processes. Optimization Meth-
ods and Software, 111):13-2,, January 1992. ISSN 1055-6788. doi: 10/dbgqw5. URL
/tts:///oo.
Publisher: Taylor & Francis
.eprint:
Andreas Griewank and Andrea Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second Edition. SIAM, November 2008. ISBN 978-0-89871-6599 Google-Books--e Soookk-IDDqMM..UusCCCCW// qMI.UlsCCwVUC.
11

---

Published as a conference paper at ICLR 2023
Christopher Grimm, André Barreto, Satinder Singh, and David Silver. The Value Equivalence Prin- ciple for Model-Based Reinforcement Learning. arXi::2011.03506 [cs], November 2020. URL http://arxiv org/ abs 22100011....0 03506.
arXiv: 2011.03506.
Christopher Grimm, André Barreto, Gregory Farquhar, David Silver, and Satinder Singh. Proper Value Equivalence. arXiv:2106. 10316 [cs], December 2021. URL
abs/2106 10316.
arXiv: 2106. 10316.
Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sébastien Racanière, Théophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, Greg Wayne, David Silver, and Timothy Lillicrap. An investigation of model-free planning. vrXiv:1901 0900093559 (cs, stat), May 2019. URL hwwp::tth/.... http://axvvvvo. www..oog//...ooooooooo...oooooo /aas///////// 901 03559. arXiv: 1901.03559,
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to Control: Learn ing Behaviors by Latent Imagination. arXiv: 1912.01603 [cs], March 2020. URL http: //arxiv.org abs/ 992. 01 603. arXiv: 1912.01603.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CoRR,
2015. URL http: //tp://///iiv/////a//////e/e org/ abs /1512 22122.4 03385.
Peter Karkus, David Hsu, and Wee Sun Lee. QMDP-Net: Deep Learning for Planning under Partial Observability. arXiv: 1e0e:7730009 06692 [cs, stat], November 2017. URL abs/1703 06692,
arXiv: 1703.06692.
Lingzhi Kong. Integrating implicit deep learning with Value Iteration Networks. Master's thesis, Northeastern University, 2022.
Steven M. LaValle. Planning Algorithms. Cambridge University Press, May 2006. ISBN 978-1- 139-45517-6.
Lisa Lee, Emilio Parisotto, Devendra Singh Chaplot, Eric Xing, and Ruslan Salakhutdinov. Gated Path Planning Networks. arXiv: 1806. 06408 [cs, stat], June 2018.
abs/1806 06408.
arXiv: 1806.06408.
Evgenii Nikishin, Romina Abachi, Rishabh Agarwal, and Pierre-Luc Bacon. Control- Oriented Model-Based Reinforcement Learning with Implicit Differentiation. Technical Re- port wrXiv:2106.03277: arXiv, June 2021. 11X.v:2106.03273 [es, stat] type: article.
Sufeng Niu, Siheng Chen, Hanyu Guo, Colin Targonski, Melissa C. Smith, and Jelena Kovačević. Generalized Value Iteration Networks: Life Beyond Lattices. arXiv: 02416 [cs], October 2017. URL http:h/t/// /ttt:://arxivv org/ abss/////////// 1706. 02416. arXiv: 1706.02416.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value Prediction Network. arXiv:1707.0s:: 1707.0347 [cs], November 2017. URL http:://rxixv wtw./////////.oo//////////. 03497. arXiv: 1707.03497.
Vitchyr Pong, Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal Difference Models: Model-Free Deep RL for Model-Based Control. 1802:v8802.09000 [cs/, February 2018. URL
http:://rxiv orggabbe 11022.1102..00 09081.
arXiv: 1802.09081.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomed- ical image segmentation. CoRR, abs/1505.04597, 2015. URL http://axxxi... wttpiiioorrr/aaooo org/abs/////oooooooo/....... a
1505. 04597.
Daniel Schleich, Tobias Klamt, and Sven Behnke. Value Iteration Networks on Multiple Levels of Abstraction. May 2019. doi: 10/g45m5v. 11068v2.
URL htttps://arxiv.org/ wtw.orgggrbb//oo/////e////
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lill- ierap, and David Silver. Mastering Atari, Go, Chess and Shogi by Planning with Leamned Model. arXiv: XXXiv:991.00266 [cs, stat], November 2019. URL http: attp://arxa /awxiv/.ivvv///////////.//////.l org/ a 1911 1911.8800 65.65. arXiv: 1911 1911608
12

---

Published as a conference paper at ICLR 2023
Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal Planning Networks. arXiv: 180.006444 [cs, stat), April 2018. URL.atpp://axxw...rr/////. http://w...rr//////////. 00645. arXiv: 1804.00645.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: introduction. Adaptive com- putation and machine learning series. The MIT Press, Cambridge, Massachusetts, second edition edition, 2018, ISBN 978-0-262-03924-6.
Aviv Tamar, YI WU, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value Iteration Net- works. In Advances in Neural Information Processing Systems, volume 29. Curran Asso- ciates, Inc., 2016. URL https: https::/prroeeedings nwwrips. http:ips..cppppeeeeeeeee http:///wwnaaaassespaa////////// 33w -bbtt63aabbbbbaaatttcec. .tml..
Tingwu Wang and Jimmy Ba. Exploring Model-based Planning with Policy Networks. June 2019. URL httpp:://axxi...tt /errg//bb/999// 1906. 08649v1.
Théophane Weber, Sébastien Racanière, David P. Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adria Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, Razvan Pascanu, Peter Battaglia, Demis Hassabis, David Silver, and Daan Wierstra. Imagination- Augmented Agents for Deep Reinforcement Learning. arXiv: 707006003333 [cs, stat], February 2018. URL http::ttp//. aawaiiivvvv..... www.wi.wwww.waa..aaaaoo/rerao.ae http:///ab//77...000 1707.06203,
arXiv:
Maurice Weiler and Gabriele Cesa. General SB(2)S Equiiaiau Steerable CNNs. arXiv: /9111082111 [cs, eess), April 2021. URL
08251. arXiv: 1911.08251.
Ezra Winston and J. Zico Kolter. Monotone operator equilibrium networks. arXiv:2006. 08591 [cs, stat], May 2021. URL http::/arxiv..ot
arXiv: 2006.08591.
Linfeng Zhao, Xupeng Zhu, Lingzhi Kong, Robin Walters, and Lawson Wong. Integrating Symmetry into Differentiable Planning. In ICLR 2023. ICLR, June 2022. doi: 10.48550/arXiv. 2206.03674. URL http:://axxiai wrg.iioorrrreeeeeeoo abs 2220 2206 03674. arXiv:2206003674 [cs] type: article.
13

---

Published as a conference paper at ICLR 2023
CONTENTS
A Outline
14
B Extended Discussion
14
B.1 Computational Similarity
14
B.2 more discussions
15
C Implementation Details
16
C.I Implementation ID-SPT
16
C.2 Optimization of Implicit Differentiable Planners
16
D Experiment Details
16
D.1 Building Mapper Networks
16
D.2 Training Setup
17
E Additional Results
17
E.1 2D Navigation Training on 75 75 Maps
17
E.2 Generalization to Larger Maps
18
E,3 Runtime of Implicit Differentiable Planners
19
E,4 Performance More Tasks: Complete Results
20
E,5 Jacobian Regularization.
20
A OUTLINE
We provide additional discussion, extended details of implementation and experiments, and addi- tional results in the appendix. The table of content is available above.
B EXTENDED DISCUSSION
B.1 COMPUTATIONAL SIMILARITY
In value iteration, iteratively apply until convergence: f(ve, r,0) Ut+1, then the outer loop optimizes one step on updating the model 0. We can generalize to time-varying optimization problem with equality constraint (Bacon et al., 2019): fe(vi, r, 0.). U++1, and assume mapping & gives the inner optimization VI: Φi = f ....o fo, dr Pn. + v.- We
de
ae 0Φr Ol AT
00, Our 00, Our
de 0fr-1 (VT-1, 0r-1) 0Φr - (1)-1)
(8)
Ovr
00,
ae 0fr-1 0fr-2
Obh (0.)
Our Øor-1 0vr-2
00,
The recursion is then given by
Bir (0r)
0f.- XT
J
XT
(10)
00,
00%
14

---

Published as a conference paper at ICLR 2023
The vector X, is the adjoint vector, costate, in control theory. The recursive update is the adjoint equation. The computation exactly the vector-Jacobian product used in automatic differentiation (Griewank & Walther, 2008).
This shows close connection between Equation 6 on the fixed-point solving for backward pass of implicit differentiation and 10 the recursive computation for algorithmic differentiation.
B.2 MORE DISCUSSIONS
Divergence of fixed-point iteration. The term "divergence" can be confusing, so we'll clarify its meaning. In value iteration, the goal of the forward pass is to find fixed point by iteratively applying the Bellman optimality operator. For an MDP with a given dynamics model, Bellman operators induced from the model and arbitrary policy guaranteed to be contraction mapping, so iterative methods will converge to a unique fixed point.
However, when the entire network is learned end-to-end, and the transition weights also learned, the property of Bellman operators is not guaranteed. When the planning horizon increases, this issue becomes more severe since it can cause the iteration move farther from the fixed point.
When we talk about divergence, we mainly refer to the fxeedpooint iteration in the forward pass. This iterative process does involve gradient computation, but is purely property of VIN and its variants.
It's worth noting that implicit differentiable planners introduce fixed-point iteration for the back- ward pass, but empirically, they do not have divergence issue.
Performance of implicit vs. algorithmic differentiation. For implicit differentiable planners, implicit differentiation itself does not guarantee result in better performance. Implicit differenti- ation and algorithmic differentiation have equivalent asymptotic performance and are not expected perform differently if run for long enough time. However, the advantage of implicit differen- tiable planners that they scale up better and can run with fewer resources, while the algorithmic differentiation ones cannot keep up with the scale.
Relationship with DEQ (Bai et al., 2019). The focus of paper is address the specific prob- lem of scaling up and stabilizing differentiable planning algorithms, particularly for value iteration- based fixed-point solving methods, such as VIN and its variants. Our approach is problem-driven. rather than method-driven like DEQ. While our work does draw on some prior techniques and mod- els, introduce new insights and methods that are specific our problem domain.
Technical contributions: Although our paper does build on some prior work, we make several sig- nificant technical contributions that are specific VIN and variants. For example, we introduce the use of implicit differentiaaionn, which has direct correspondence to the differentiable planning algo- rithm and allows for more scalable and interpretable solutions. We also explore specific tuning and techniques that are needed to address the unique challenges of value iteration- based methods, such as the need for precise value function calculations and the limitations of using fixed-point iteration in the planning process.
While DEQ has inspired some of our ideas and approaches, we also highlight some key differences between work and DEQ. For instance, DEQ is designed for supervised learning and does not require the same level of precision and stability as value iteration- based methods. Additionally, DEQ requires weight-tying tying and input injection, which are already present in vanilla VIN.
In conclusion, while our paper draws on some prior work and techniques, we introduce new insights and methods that are specific VIN and variants. We address the challenges of scaling up and stabilizing value iteration- based methods, and introduce the use of implicit differentiation, which offers more scalable and interpretable solutions for these types of algorithms.
15

---

Published as a conference paper at ICLR 2023
C IMPLEMENTATION DETAILS
C.I IMPLEMENTATION OF ID-SPT
Beyond VIN, VIN and ConvGPPN, we also tried implementing an implicit differentiation ver- sion of Spatial Planning Transformrrs (SPT) (Chaplot et al., 2021). However, we find the reimple- mentation of SPT and also the implicit version both do not work well enough. We first introduce how we implemented it and discuss our hypotheses on its failure.
Implementation. ID-SPT is based Transformer architecture, SPT. SPT is proposed to facilitate global value propagation using the global receptive field of self-attention layers in Transformers. Different from other variants, SPT uses heavier global self-attention layer and does not scale up the number of layers with map size, although the number of weights increases quadratically with size. We also implement an implicit version by using individual self-attention layer, where f(V) = SelfAtt (V; 9). Even SPT fits into our pipeline, we empirically find SPT behaves unlike other planners since does not inject reward R as input.
Discussion of performance. In our experiments, we find the modified ID-SPT cannot outperform SPT.
Since SPT uses multiple Transformer (self-attention) layers, it is computationally expensive. Thus, we use much smaller number iterations for ID-SPT: K = 3, 5, 10, 15, because the original paper uses K = 5 layers across all map sizes.
However, we plot the convergence curve for its forward and backward pass. We find that the forward pass can only convert around 10 I to 10 level (relative residual) and cannot further decrease, while other planners have their forward pass converged around at least 10-2, We find this may affect the backward pass, as the Jacobian the solved equilibrium is used in solving the backward fixed- point iteration.
Considering these, we think the reason might come from the fact that SPT uses Transformer layers, which is too expressive and tends to learn an arbitrary output as it needs.
C.2 OPTIMIZATION OF IMPLICIT DUFFERENTIALEY PLANNERS
To optimize the performance of IDPs, we also implemented other techniques. regularization from (Bai al., 2021), which estimates the Jacobian
We tried Jacobian at the equilibrium.
0fo(v" :x)
der
We experiment it on ID-VIN, since other methods have more memory use and Jacobian loss would cause out of memory. However, it does not perform we expected and rather decreases the success rate. We provide additional results on this in the later result section.
D EXPERIMENT DETAILS
D.1 BUILDING MAPPER NETWORKS
For visual navigation. For navigation, we follow the setting in GPPN (Lee et al., 2018). The input is m X m panoramic egocentric RGB images in 4 directions of resolution 32 x 32 x 3, which forms a tensor of m x m x 4 x 32 32 x 3. A mapper network converts every image into -i6-dimensional embedding and results in a tensor in shape m x m x x 256 and then predicts map layout yn x m x 1.
For the first image encoding part, we CNN with the first layer of 32 filters of size 8 x 8 and stride of 4 x 4, and the second layer with 64 filters of size 4 x 4 and stride of 2 x 2, with a final linear layer of size 256.
In the second obstacle prediction part, the first layer has 64 filters and the second layer has 1 filter, all with filter size x 3 and stride 1 1.
For workspace manipulation. For workspace manipulation, we use U-net (Ronneberger et al., 2015) with residtol-connection (He et al., 2015) a mapper, Figure 8. The input is 96 x
16

---

Published as a conference paper at ICLR 2023
St. juls gab. 200
iuuss Solees skg
1000 y0u
HD ludds git: Spiect
1000 VOU
2904
34000
DE: 1aRT 200 SONL PAd
nam comn
s1 Hulooo ps Spous s0g
inGo pC Spciu sag
eyuur Oh
at: Nuudo Dt Spares say
Shnure on
10:00 Spora
oone
Figure 8: The U-net architecture we used as manipulation mapper.
96 top-down occupancy grid of the workspace with obstacles, and the target is to output 18 x 18 configuration space as the maps for planning.
During training, we pre-train the mapper and the planner separately for 15 epochs. Where the mapper takes manipulator workspace and outputs configuration space. The mapper trained to minimize the binary cross entropy between output and ground truth configurations space. The plan- ner is trained in the same way as using given maps. After pre-training, we switch the input to the planner from ground truth configuration space the one from the mapper. During testing, we fol- low the pipeline in Chaplot et al. (2021) that the mapper-planne only have access to the manipulator workspace.
D.2 TRAINING SETUP
We try to mimic the setup in VIN and GPPN (Lee al., 2018).
For non-SymPlan related parameters, we use learning rate of 10-3, batch size of 32 if possible (GPPN variants need smaller), RMSprop optimizer.
For SymPlan parameters, we use 150 hidden channels (or 150 trivial representations for SymPlan methods) process the imput map. We use 100 hidden channels for Q-value for VIN (or 100 regular representations for Sym VIN), and use 40 hidden channels for Q-value for GPPN and ConvGPPN (or regular representations for SymGPPN on 15 15, and 20 for larger maps because of memory constraint).
E ADDITIONAL RESULTS
E. 2D NAVIGATION TRAINING ON 75 x 75 MAPS
We include comparison of differentiable planners with implicit differentiation algorithmic differ- entiation on even larger maps: 75 x 75. Every error bar contains 3 to 5 seeds.
Note that this has not been done in any of prior work along this line, including VIN, SPT, SymVIN and more. This shows better scalability of the implicit differentiable planners. Prior work GPPN uses only 28 x 28 and SPT uses x 50 (which mainly emphasizes long-term planning) for both training and evaluation. Note that Sym VIN also only uses 50 50 for training, while use up to 100 x 100 for generalization. We also did the same experiment, available in Section E.2.
Figure 9 shows the performance of all implicit and explicit differentiable planners on the 75 x 75 tasks. We train explicit differentiable planners with K Layer = 30, 50, 80, 120 layers, and our implicit differentiable planners with max Kiwd 30, 50, 80, 120 forward pass iterations and Kowd 15 backward pass iterations
For the explicit side, ConvGPPN totally fails as also in 49 x 49. The performance of SymVIN shows the need for more iteration: Kayer = 50 is better than Kaayer 30. However, although SymVIN successfully which shows its limitations on stability when scaling to larger iteration. VIN does not achieve meaningful results.
Kayer 80, the runs mostly fail to converge fixed point,
17

---

Published as a conference paper at ICLR 2023
Task
1.0
Task 7
1.0
0.8
Success Rate
Success Rate
0.6
model
0.6
model
ID-VIN
0.4
SymVIN ConvGPPN
ID-SymVIN
ID-ConvGPPN
0.2
0.2
0.0
30
50
80
120
50
80
120
#lterations/Layers Kayer
Forward
Iterations Kivd
Figure 9: Performance on 75 x 75 maps.
algorithm
VIN
0.8
ID-VIN
SymVIN
ID-SymVIN
0.6
ConvGPPN
ID-ConvGPPN
0.2
0.0
60
100
size
Figure 10: Generalization to larger maps.
As for implicit differentiable planners, noticeably, ID-ConvGPPN can successfully run with all for- ward iterations Kywd, which quite impressive considering its expensive recurrent network architec- ture. It can achieve almost perfect 100% successful rate when using Kiwd = 120. For ID-Sym VIN, it is less stable but can perform better with more forward iteration Kiwd. and the best performance Kiwd = 80 or 120 is higher than SymVIN. It also shows the potential to achieve even better number. ID-VIN seems struggling and does not give meaningful success rate.
E.2 GENERALIZATION TO LARGER MAPS
Setup. In other experiments, train the planners the map size with training case, while this experiment aims for generalization to larger maps to examine its potential. All methods are trained on 15 15 maps and tested larger maps. We chose ADPs with Kayer 50 (for stability concern) and IDPs with Kind = 80. All methods are tested on six sampled map sizes in 15 x 15 through 99 99, averaging over seeds (5 model checkpoints) for each method and 1000 unseen maps for each map size. At test time, we keep the same iteration numbers as training and do not increase them. The results are shown in Figure 10.
Results. VIN and ID-VIN both suffer from generalizing to larger maps and perform pretty sim- ilar. ID-Sym VIN much better than ID-VIN, and outperform the explicit counterpart Sym ID-ComvGPPN generalizes fine, but is worse than ConyGPPN. We find that although ConvGPPN suffers from training on large tasks (backward pass), since here we chose the best hyperparameter for ConvGPPN 15 x 15, its inference (only forward pass) is pretty reliable as long as it can suc- cessfully train. As expected, the success rate of all methods drops with increasing test map sizes. While in general, both IDPs and ADPs generalize similarly well. This is expected because implicit differentiation majorly improves scalability of the backward pass, while the main bottleneck for generalization is the forward pass, where they do not have major difference.
18

---

Published as a conference paper at ICLR 2023
solver /wd forward |sllver_bee bed forward
solver_fee _fwdd forward solver ber anderson
Tainavy backward time
anderson
solver
ID-N ID SymviN
25
Trainvv baskeard bire
ID ConVEPPN
20
15
10
deg bivd max wwn__bod__ax__iie Iter
bond bww__bddd_aaad_aooeeeeeee Iter
Figure 11: Backward pass iterations vs. backward runtime.
sclver fwi forward solver bwo forward
salver, Nwd forward solver Dwrd anderson
Trinsai D0C0esS
0.8
model
I0-SymVII
ID-ComVGPM
Trainavv succers
0.6
0.4
deq_bwdd_mxx___ jter
deeq [ro__wd_mmx__ie Lter
Figure 12: Success rate vs. different forward and backward solver and different backward pass iterations.
E.3 RUNTIME OF IMPLICIT DIFFERENTIABLE PLANNERS
Backward runtime. We visualize the runtime of backward pass of IDPs for using forward solver and Anderson solver in Figure 11. The experiment done on 15 x 15 maps.
As expected, using more backward pass iterations would increase the backward pass runtime. How- ever, we also find that the backward pass has already converged at around 10 iterations, so increasing the iteration will not help the training. Instead, the iterations of the forward pass are the main bot- tleneck for scalability on larger maps. We show the results in the next paragraph.
Choice of fixed-point solver. show the performance difference when using different solvers on all implicit differentiable planners in Figure 12. For backward passes, the Anderson solver is clearly better than the forward iteration solver. In terms of the forward passes, ID-SymVIN is not compatible with the original Anderson solver, since SymVIN needs to keep the equivariance of the intermediate variables by ordering them in a specific way. However, the Anderson solver has reshaping operations that would break it.
19

---

Published as a conference paper at ICLR 2023
Task 18x Manipulation
Task 36 36 Manipulation
Task = 18x 38 Worispace Manipulatin
5.6
Cenvorey
9.2
0.0
50
30
Itrrtioos
Monipuiation
Manipuaatoo
Manipulation
1.0
Figure 13: Manipulation complete results.
Visual (25 15)
1.0
Trainfong SUECeSS
0.8
model VIN
0.6
VIN
SymVIN
ConVGPPN
0.4
Co-ConGPPP
SymVIN
0.2
30
50 #lterations
30
50
deg, fwd, max_maxxee Iter
Figure 14: Visual navigation complete reuslts.
E.4 PERFORMANCE MORE TASKS: COMPLETE RESULTS
In the main paper, we average over 30/50/80 forward iterations/ layers. We here show the complete results for each forward iteration layer number for manipulation in Figure 13 and for visual nav- igation in Figure 14. The results still follow the trends in the paper, where IDPs tend to converge more stably for larger iterations.
E.5 JACOBIAN REGULARIZATION
We tune the Jacobian regularization from (Bai al., 2021). We focus on tuning the Jacobian regu- larization weight and frequency on 15 x 15 maps. The x-axis is a hyperparameter of the Anderson solver for backward pass.
The results are in Figure 15. Each column corresponds to the frequency = 0%, 20%, 40%. Each row is the weight 2, 4,4,8. However, the top left panel performs the best, which means zero regularization.
20

---

Published as a conference paper at ICLR 2023
2.0
2.0
0.2
weight - 2.01
4.0 froq
4.0 0.2
waight 4.01 freq
dea_bwdd_ www.bwewd_ddeesonunn
8.0) reg. froq 0.0
welght 8.0 froq 0.2
waight 8.0 0.4
farward
undetson
To murd
underron
fanward
andetion
Figure 15: Tuning Jacobian regularization.
21


Reviews:
[{"review_id": "LiTNQwoHpy", "reviewer": "Reviewer_D5nz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "The paper proposes to use implicit differentiation in value iteration networks, allowing for a deeper network structure/more iterations of planning. This is because the implicit gradient has a constant complexity with respect to the number of planning iterations.", "summary_of_the_review": "The paper proposes using implicit differentiation in value iteration networks (VINs). This allows using many more planning iterations than usual. The authors show that they can successfully train VINs with very high numbers of planning iterations, which is not possible using explicit gradients. I generally do not see a performance gap between implicit and explicit gradients in the experiments. The few cases where there is a benefit for implicit methods seem to also come with a very high runtime. The presentation does not make this very clear due to the reporting of averaged results. I find the idea of using implicit differentation in VINs very promising and interesting, but the experimental results and presentation currently do not convince me. The paper can be made a lot stronger by including experiments which show implicit methods clearly outperforming explicit ones and with reasonable runtimes. At the current stage, I see the paper as below the threshold of acceptance.", "strength_and_weaknesses": "**strengths**\n\n* The paper identifies and fixes an issue with an existing method. Value iteration networks do not scale to high numbers of planning iterations. Implicit differentiation reduces the cost of the gradient computation, which allows using many more planning steps.\n* Experiments show that implicit gradients allow using more planning iterations for the same cost of gradient computation. The authors also show that successful models can be trained with very high numbers of planning iterations using implicit gradients, while the same is not true of explicit ones.\n\n**weaknesses**\n\nI have some concerns about the results and the presentation. I will make an overview of the experiments and how I interpret the results below to make that clear.\n\n**overview of experiments**\n\nThe paper has 4 experiment setups: 1) 2D navigation 2) visual navigation 3) configuration-space manipulation 4) work-space manipulation.\n\n**2D navigation**\n\nThere are maps of size 15x15, 27x27 and 49x49. According to Figure 2, in both 15x15 and 27x27 there exist explicit planners which reach 100% success. In 49x49 maps, the best explicit planner (SymVIN with 30 iters) reaches about 85% success.\n\nAccording to Figure 4, the implicit planners match the performance of explicit ones in all scenarios, and even exceed that in 49x49 with 80 iterations using ConvGPPN. That being said, according to Figure 6 the runtimes of implicit planners in the 49x49 task seem impractical for all models (except VIN, which performs poorly).\n\nTo sum up, implicit vs explicit perform roughly on par. There are setups where implicit works better, but the runtime gets quite high.\n\n**visual navigation**\n\nAccording to table 1, implicit methods clearly outperform explicit ones. However, table 1 averages results across 30, 50 and 80 iterations. We can find individual runs in Figure 13. Here, the best explicit methods are SymVIN and ConvGPPN with 30 iterations, which reach ~100% success. The implicit ones also reach this performance. To sum up, implicit vs explicit perform on par.\n\n**configuration-space manipulation**\n\nThere are 18x18 and 36x36 setups. Again, table 1 shows implicit methods outperforming the others on averaged results. Figure 11 contains individual results for 30, 50 and 80 iterations. In both 18x18 and 36x36, the best explicit method (SymVIN with 30 iters) reaches ~100% success rate. Implicit methods also reach this performance. So again, the two are on par.\n\n**work-space manipulation**\n\nSimilar to configuration space, averaged results favor implicit methods. According to Figure 11, the best explicit methods are SymVIN and ConvGPPN with 30 iterations, and they reach between 85 and 90% success. The best implicit method seems to be SymVIN with 50 iterations. This performs similar to the explicit ones, but perhaps with a slight edge. Without exact numbers I'd have to say the best explicit and the best implicit perform on par.\n\n---\n\nLooking at these results, I have two main concerns:\n\n* Implicit and explicit methods appear to perform on par, if we compare the best explicit method for each setup with the best implicit method. The only setup where implicit has an edge is the 49x49 2D navigation task. However the runtimes of the implicit method here appear impractical. The backward pass of SymVIN takes 50 seconds according to Figure 6, which is quite long. That would mean over an hour for 100 gradient updates.\n* I find the presentation a bit misleading at times. In Table 1, it doesn't make sense to me to average across planning iterations. A fair comparison would be best-vs-best. Also, I find that there is not enough discussion of runtimes. I greatly appreciate Figure 6 but I still think more space should be dedicated to discussing runtimes. The results don't seem to be as simple as \"implicit gradient is faster\". There are some settings where the implicit gradient is slower than the explicit one (e.g. 49x49 SymVIN with 30 iterations) and settings where the fact that the implicit gradient is faster doesn't matter too much because it is still not fast enough (e.g. 49x49 ID-SymVIN backward pass takes close to a minute). A fair comparison would also include the runtime of the best implicit method against that of the best explicit one.\n\nPlease let me know if I'm misinterpreting the results here.\n\nMy recommendation would be to point out a setup where a) the implicit version is feasible, while the explicit is not b) the implicit version has an edge over the explicit one. By b) I mean that the longer planning horizon allows the method to reach a level of performance that an explicit gradient cannot reach with any number of iterations that is applicable or any choice of model. This would make it easier for the reader to understand when implicit gradients are helpful. I have searched for such a setup in the paper but couldn't find it (see my process above under \"overview of experiments\").\n\n**some minor points**\n\n* Can the authors define what they mean by divergence? Do you mean that the gradient vanishes or explodes?\n* One missing related work that I spotted: [1]. It has a similar goal as this paper: scaling up planning to larger environments.\n\n[1] Value Iteration Networks on Multiple Levels of Abstraction, http://www.roboticsproceedings.org/rss15/p14.pdf", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LcJStbgGW-", "reviewer": "Reviewer_Wf8g", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "This paper proposes to scale differentiable planning such as Value Iteration Networks (VINs) with implicit differentiation. Section 3 summarizes value iteration networks, symmetric VINs, and gated path planning networks and how the fixed point of the value iteration can be seen as an implicit function, i.e. Bellman optimality provides an implicit function. Section 4.1 goes on to review how to compute the implicit derivatives or approximations to them, and Section 4.2 instantiates the full pipeline for implicit planning.", "summary_of_the_review": "I recommend to accept this paper as it combines a reasonable core contribution of implicitly differentiating planners along with extensive experimental demonstrations of how it enables them to scale. ", "strength_and_weaknesses": "Strengths\n+ The idea of implicitly differentiating planners that compute a fixed point is appealing\n+ The implicit planners on the 2d navigation tasks in Figures 4, 6 and 7 and Table 1 convincingly improve upon the performance in contrast to the corresponding planners trained without implicit differentiation\n\nWeaknesses\n+ Sometimes the value iterations may take a long time to reach a fixed point. Is it hard in practice to ensure that a fixed-point is reaches so that the implicit derivatives remain stable?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "L2Z99i5pkn", "reviewer": "Reviewer_3dQr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper applied the implicit differentiation to the equilibrium state of the VIN-based path planning pipelines. Since the forward computation of VIN is effectively solving a fixed point of the Bellman equation, it is natural to treat this process as a deep equilibrium model (DEQ Bai et al. 2019), which can backpropagate the gradients without storing the entire forward computational graph. ", "summary_of_the_review": "In summary, this paper could be a good application of DEQ. However, the technical novelties are limited. Most of the components are from existing work. The experiments are on small scales and not compelling enough to back up the claimed scalability.", "strength_and_weaknesses": "Strengths\n\nDEQ is suitable with the VIN-based path planning framework. The forward iteration of VIN can be viewed as solving a fixed-point equation, which is exactly what DEQ should deal with. The back-propagation of DEQ only relies on the fixed point itself, so independent of the forward solving. As a result, we can have a longer forward iteration to solve for a better convergence in some larger-scale cases.\n\nWeaknesses\n\nAlthough this paper chooses an appropriate model to tackle the VIN-based path finding problems, the technical novelty itself is somehow limited. Both the forward network structures and backward implicit differentiation schemes are from existing models. \n\nMost importantly, the experiments cannot fully back up this paper’s main claim, that this method can scale up the path planning algorithms. The biggest map size is only 49x49, which is even less than the 100x100 examples used in the baseline SymVIN [1]. To validate the advantages of implicit differentiation, a bigger map size (with which previous baselines cannot deal) might be needed.\n\n[1] Integrating Symmetry into Differentiable Planning \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster