Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a planning method called PALMER that creates a feedback loop between reinforcement learning, representation learning, sampling-based motion planning and a non-parametric memory. The method tackles a specific variant of a planning problem where observations from a prior exploration of the environment are available and the goal is to find optimal paths between any two states in the  same environment. The authors conduct experiments in the ViZDoom and Habitat environments which show some improvements over prior methods.
strengths_and_weaknesses: Strengths:
- The method is well motivated. The idea of using sampling-based motion planning for this task makes sense. The use neural networks for learning the graph structure required for motion planning from pixel-based observations is clever.
- The results on ViZDoom environment show a significant performance improvement especially for distant goals. 

Weaknesses:
- The scope of the method is low in my opinion as the method requires access to an exploration of the environment. 
- Since the authors are tackling embodied tasks, there are alternative methods which build a map of the environment and use differentiable planning, for example Gated Path Planning Networks (Lee et al. ICML 2018), Path Planning using Neural A* Search (Yonetani et al. ICML 2021), Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees (Chen et al. ICLR 2020). It is difficult to understand the significance of the proposed approach as compared to this line of work as it is missing in the paper both in related work and as baselines.
- The results on Habitat environment are only qualitative and are not compared against baselines. More comprehensive experiments in realistic environments would make the submission stronger.
- The writing clarity can be improved significantly. 
  - Many important experimental details are missing which makes it difficult to assess the significance of the results. It is unclear how the exploration trajectories are obtained in different environments. How many trajectories do you use per environment? How are the trajectories sample, is it a random policy, a trained policy or human trajectories? How are the target images sampled? Are target images always observed in exploration trajectories or can they be novel images?
  - The text contains several terms which are not clearly defined. For example, what do you mean by "approximate-overlap criteria (L37, L50), what are "actually observed transitions" in L48? Which transitions are observed but not actually observed? The text also contains very long sentences which are difficult to follow (for example L39-42, L42-45). 
questions: See questions in weaknesses above.
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this work, the authors introduce PALMER that combines reinforcement learning and classical planning (particularly sampling-based methods) to achieve robust navigation in visual domains. PALMER maintains a memory buffer. During rollout, given a state-goal pair, the lowest cost trajectory on the graph (w.r.t state-goal query) is found by solving an optimization problem minimizing a similarity metric based on perceptual representations (processed referred to as perceptual memory retrieval, or PMR). A probabilistic roadmap is incrementally constructed with transitions added to the buffer. This is done by following the classical sampling-based motion planning routines but replacing the Euclidean distance metric with one that's based on PMR. Doing so allows for effective use of the memory buffer as a trajectory bank for high-level guidance of long horizon navigation tasks. Simulation results show that PALMER is able to effectively generate goal-reaching trajectories from visual input and exhibit decent generalization capability in the VizDoom and Habitat environments
strengths_and_weaknesses: Strengths
1. The paper is well written, and the visualizations are very helpful in explaining the core ideas. 
2. I appreciate the detailed explanations of the key concepts provided in the paper and appendices, again incredibly helpful for understanding the paper.  

Weaknesses
1. lacks comparison with other planning and RL methods in visual navigation
2. evaluation in support of the claims would strengthen the paper
questions: 1. The claims in the paper are that PALMER is more robust to false predictions and it learns abstractions that can extend from goal-reaching to general RL problems. However, it is not clear how these two claims are supported by the experiment results. In order to support these two claims, the authors need to show (a) how the number of false predictions correlate to the task success rate in PALMER and comparison methods and (b) how PALMER performs on tasks more complex than visual navigation. 

2. The idea of restitching transitions in the memory buffer is relevant to offline RL (A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems ), can the authors comment on the similarities and differences?

3. Out of all the components in PALMER, which is the most time consuming and how does it scale with the dimension of its inputs?

4. The effectiveness of PMR and the constructed roadmap depends on coverage of the transitions in the memory buffer over the task space. Will this hinder exploration at the start of training when the coverage is low?
limitations: requiring a graph-based roadmap inherits some of its limitations, including the inefficiency caused by high dimensional state space and closely situated obstacles a cluttered environment. And it's not clear to me how a sampling-based planner can be extended to non-navigation RL tasks with arbitrary reward.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a method similar to anytime-sampling methods in planning (e.g. RRT*) but in the RL context, to stitch together trajectories from an experience buffer to solve goal reaching tasks. 

The core idea is to learn representations using general neural function approximators by leveraging the idea that the functional distance between two interactions should be small if they can be achieved through similar actions and attain similar reward/cost values. This is formalized using state value function and L2 function over learn feature embeddings. 

The representation is learn by fitting several sub-modules including an encoder, a trandition dynamics model, action proposal network and a function to retrieve a distribution over timesteps necessary to achieve an interaction. Effectively this gives rise to a policy improvement algorithm that follows a virtuous loop of improve the system to achieve goal by iterating over: 1) learn an accurate Q function, 2) Use this Q function learn better function appx, 3) Use this to better estimate expected reward given start and goal query, 4) this is turns lead to better exploration, repeat. This is the core algorithm and there are parallels drawn to RRT* algorithms which behave in similar ways but by using hand-crafted sub-functions. This reformulation of planning algorithms as a memory retrieval mechanism is interesting and is the core conceptual contribution of this paper. This is then validated on navigation tasks in VizDoom and Habitat. 
strengths_and_weaknesses: Strengths:

In long horizon tasks like navigation under sparse rewards, exploration and policy improvement is challenging. Assuming that the agent explores the state space well enough, the experience stitching approach proposed in this paper is a principled solution to tackle this problem in case of non-linear function approximation based RL and planning. 

The key empirical result is shown in Figure 4 where the success ratio degrades more gracefully than baselines in the long horizon planning setting.

Weakness:

This method assumes that the exploration problem is "solved". One of the advantages of RRT* like algorithms is that they quickly explore large unstructured spaces. However, a trajectory stitching based approach will only work well assuming the space is well explored. Please discuss limitations. 

The paper would also be much more powerful and the parallels to RRT* like algorithms much more grounded if larger environments were considered. I suspect some form of intrinsic motivation or curiosity would be needed to solve this but it is important to know where the current proposed method breaks (e.g. what maze or level complexity would this break on compared to RRT*, assuming knowledge of state space?).


questions: -  It looks like the state action value function has not been trained in the Habitat environment fully correctly. There are a lot of glitches that happen in the policy rollout. Why is this? 

- "We say two states approximately overlap if dϕ(st, sg) ≤ dp holds, where dp is a hyper-parameter". How is the hyper param selected? It seems like this would greatly depend on the topology of the environment. The variable would be vastly different for navigation, manipulation or gaming tasks. This also makes me wonder if the algorithm easily generalizes to environments beyond navigation tasks. In principle it should but the exploration and this assumption can make it highly trivial to get good empirical results. Have the authors ran experiments on other tasks like the Mujoco continuous control suite or Atari? Even experiments in these synthetic domains would prove out the empirical generality of this framework and make it a very strong paper. 

- Section 2.3 is not clear at all. How is the search done?  "Given any interaction proposal (sc, sg) as a query, we use the components from Sec.2.2 to retrieve the highest scoring trajectory from M whose first-last states overlap with the query pair according to our approximate-overlap criterion from Sec.2.1.". More details would be good. 

- If the environment is dynamic, how would this approach still work?
limitations: - RRT* style of algorithms come with anytime sampling convergence guarantees. What does and dosen't hold in this setting? 

- Are there any situations under which the bellman optimality is broken under this policy improvement scheme?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper’s main contribution is a method for stitching observed trajectories together to create a graph of the state space on which classical planning can be done to reach a given goal from a given starting point. This method then forms the core of an iterative system that can collect experience given such a graph and then improve the graph (and other learned components) given the new experience. Experiments in VizDoom validate some of the underlying assumptions and choices of the method and demonstrate its benefits over existing work.
strengths_and_weaknesses: **Originality:** The presented work is a natural extension of existing ideas in the literature of goal-conditioned planning but is comprehensive and clearly adds novelty to the existing literature by introducing an alternative state embedding function, supporting arbitrary rewards, and enabling the use of classic planning algorithms on in-memory observations.

**Quality and clarity:** The presentation is of high quality, well-written, and clear, albeit quite dense. My main complaint in this regard is that the authors seem to be quite constrained by the page limit, and this is impacting the readability of parts of the text and definitely of the figure captions. I’d encourage moving an additional paragraph from somewhere into the supplement and clarifying the figure captions (e.g., Fig 3 needs the supplement to be understood at all, which should not be the case).

**Significance:** The contribution appears significant and the evaluation is reasonable but a bit limited in scope (mainly focused on ViZDoom) so it’s unclear what the longer term significance of this work will be.

Overall, the paper is well-written and fairly enjoyable to read (aside from the density and need to refer to the supplement to understand certain sections and figures). The exposition, explanations, and clear connections to existing work are much appreciated. This is a large and somewhat complicated method and I felt each component was explained and justified and connected to the other components. 

questions: 1. How does the proposed method fare as a function of dataset/memory-buffer size? Does performance fall off more quickly or slowly than other methods as the memory buffer shrinks?
2. How strong and how necessary is the assumption of additive reward over trajectories?
3. If I understand correctly, d_\phi[(sc1, sg1), (sc2, sg2)] (from line 74) computes the L2 over concatenated feature vectors, which requires computing a square root over the sum of squared entries. Wouldn’t it be better to compute separate L2 distances over sc1,sc2 and sg1,sg2 respectively and then add those values?
4. Further, the bold text in lines 76-78 says that d_\phi cares about similar actions and costs but d_Q appears to measure the max cost of moving in either direction from sc1<->sc2 or from sg1<->sg2, which says nothing about the actions and costs of the trajectories from sc1->sg1 and sc2->sg2. So, this bolded text seems wrong?
5. How well do SoRB and your method do when using the improvements mentioned in footnote 3? Since it’s possible those improvements would eat into some of the benefits from your method.
6. Please define what an “update” is in figure 7.
7. How well does your method perform in more stochastic domains? I don’t see anything in the method to deal with noisy transitions.

limitations: Yes, the authors have done a sufficient job addressing limitations and potential negative societal impacts of their work.
review_title: null

Meta-review: metareview: The paper presents a method for goal-directed trajectory planning for offline RL on experience replay buffers.  The work builds on classic ideas of sample based planning in robotics (PRM and RRT), but the proposed method is purely experiential and can operate directly with high-dimensional observations instead of a given low-dimensional state space.  The work reduces the presence of false graph connections as compared to earlier techniques.  The method also learns a reachability preserving embedding function that maps observations to a low-dimensional state space.  The experiments show the technique is effective for navigation tasks, and outperforms simpler baselines.

The reviewers found the paper's arguments well motivated (PChv, BFRQ, BnRU), and well written (BFRQ, t3oP), with significant improvements over baselines (PChv, BnRU, t3oP).  The reviewers also had a long list of questions on the limitations of the approach, and how well it connected to the question of planning in a general RL problem.  The author response addressed the reviewers' questions, and described both the strengths and limitations of the proposal.  The reviewers indicated their satisfaction with the response, and their core concerns were addressed.

Four reviewers indicate to accept this paper for its contribution of a new method for a memory-based planning method.  The paper is therefore accepted.

confidence: Certain
Decision: Accept