Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
**Summary**
This paper proposes graph-structured reinforcement learning (GSRL), which consists of two key components: (1) goal generation, to choose what goals a goal-conditioned agent should follow during an exploration episode, and (2) value estimation, to prioritize experience from highly related trajectories according to local graph structure during value/policy updates. 

For (1), the algorithm maintains a “state-transition graph”, essentially a graph of the observed state transitions in the MDP. At a high level, the goal generation should pick goals in the “boundary” of the current state-transition graph for exploration. This “optimal goal” that should be generated can be trained in hindsight by looking at the best trajectory in the next episode (where the best trajectory terminates at a state that is estimated to be the closest to the goal) and finding in it the reachable state from the current episode. During inference, an attention mechanism is used to identify this optimal goal in the current episode. 

For (2), GSRL selects trajectories that have states that are in the immediate neighborhood of the current state to train on, rather than sampling transitions uniformly. 

Experiments were conducted in several (discretized) robotics environments ranging from maze navigation to robotic arm block manipulation, demonstrating improvement to HER and MAP baseline. 

**Positives**:
- I like the idea of using hindsight to assign the target for choosing behavior goals for exploration. Usually, as in HER, hindsight is applied only for the optimization phase to update the value/policy by augmenting the experience data. This approach can directly affect the data collection process itself. 
- The paper presents several theoretical results: (1) to motivate the need for directed exploration, (2) showing that the exploration goals should come from the boundary.

**Negatives**:
- There are several works that investigate letting the agent choose its own goals during exploration: GoalGAN [1], DDL [2], MEGA [3], Skew-Fit [4]. Rather than constructing a graph to determine the boundaries/frontier, they use either a discriminator or a density estimator. It would be worth discussing these works in relation to GSRL, and perhaps even including some of them as baselines. 
- For prioritizing experience during value estimation, there is also MEP which tries to group trajectories that achieve diverse goals during the update. This should be compared to $\mathcal{D}_{related}$ in line 13 in Algorithm 1. 
- There are several ablations that can be included to further gain intuition about GSRL (see questions below)
- Some parts of the paper were confusing to read. In Section 3, the goal-oriented RL framework was introduced, with both discrete and continuous action space. I was confused then later in section 4 as the dynamic graph construction appears to rely on discrete actions in order to have a notion of degree of node $s$. 

**Recommendation**:
 
Overall, I vote for marginally below the acceptance threshold. The motivation and proposed ideas are promising, but I have several concerns about relevant related literature and ablation experiments which would make the paper much stronger and convincing. 

**Question**:
1. Ablations:
  1. How does the method perform without using the attention strategy on the groups to pick $C_{ATT}$ first, then obtain the optimal goal within $C_{ATT}$? Claimed in 4.2 *Goal Learning Strategy* that supervising for the group instead of the goal can eliminate instability brought from inaccurate value estimation. The “Impact of Group Selection” shows a curve with “no group selection”, how exactly was this done?
  2. Ablation for the value learning strategy: compare updating from transitions drawn uniformly from the replay buffer, without using $\mathcal{D}_{related}$. Along with the above, would allow you to show that the various components of GSRL are necessary
2. Can you clarify/explain more about the self-attention mechanism used in Eq 2? Is this similar to self-attention used in Transformer layers? 

**After rebuttal responses**:

The authors have tried to address my concerns about the baselines and clarifications on some of the details of their implementation during the rebuttal period. After the revision, the additional ablations and GoalGAN/CHER baselines added to the empirical evidence for their algorithm. I updated my score to a weak acceptance.

**References**

[1]. Florensa et al.. Automatic goal generation for reinforcement learning agents. ICML, 2018

[2]. Hartikainen et al. Dynamical distance learning for semi-supervised and unsupervised skill discovery. In ICLR, 2020.

[3]. Pitis et al. Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning. ICML, 2020

[4]. Pong et al. Skew-Fit: State-Covering Self-Supervised Reinforcement Learning. ICML, 2020

[5]. Zhao et al.  Maximum entropy regularized multi-goal reinforcement learning. ICML, 2019

review_title: Promising direction, needs more comparison with existing literature and careful ablations

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper introduces Graph Structured Reinforcement Learning (GSRL) framework, able to balance exploration and exploitation in RL. Actually, GSRL builds a dynamic graph based on historical trajectories. Then in order to learn from sparse or delayed rewards and  be able to reach a distant goal, it decomposes the main task into a sequence of easier and shorter tasks. An attention strategy has also been proposed that is able to select an appropriate goal for each one of the easiest tasks. Experiments have been conducted on various robotics manipulation tasks showing that GSRL performs better compared to HER and MAP algorithms. 

The idea of constructing a dynamic graph on top of the state-space is really interesting. In this case, the agent is able to explore efficiently all the state-space as the graph is expanded at each time-step. Despite the possible merits of this approach on  various robotics manipulation tasks, the applicability of GSRL on other sensitive tasks is not guaranteed. For instance, could GSRL be applied to the task of helicopter controlling where  the safety of the agent is critical? Another point that should be clarified by the authors is the modelling of the self-attention function. It is not clear how does it defined (Eq. 2)? It is not also obvious  for the reader how do you update the attention mechanism (see Eq. 4). I recommend to the authors to give more details about the definition and update of attention strategy and not treat it as blackbox. Moreover, at Eq. 3 the state with the highest value among the states of C_ATT is selected as goal. How do you learn the value function that is not goal-oriented as the Q-function (learned by minimising the objective function of Eq. 6)? Another point that should be discussed is if there is any connection between GSRL and Hierarchical RL. Finally, despite the fact that the paper is well-written, the notation is cluttered in some cases. For instance, $E$ is used both for the episode length and the number of episodes.

review_title: Official Blind Review #1

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a new framework, GSRL, to handle the sparse reward challenge and better leverage past experiences. Specifically, it formulates trajectories as a dynamic graph, and generates hindsight-like goals based on sub-group division and attention mechanism. The authors provide theoretical analysis to show the efficiency and converge property of their method. The experimental result shows the proposed method significantly outperforms the baselines. 

Strengths:
+ The general idea is reasonable. 
+ Appropriate theoretical analysis is attached. 
+ The experimental result is good.

Weaknesses:
+ Is it true that the boundary of a graph consists of all observed states, as defined in Section 4.1? The example in Fig. 4 is misunderstanding. 
+ It is unclear about how the groups are represented during computing the attention values. Are they embedded as representations (e.g., averaging all state representations within one group) or just identified as one-hot group ids?
+ Can the paper visualize the groups, their assigned attention values, and the selected goal? If a group is selected, is it true that the goal is sampled randomly from this group, or with some priors. If the boundary of a graph consists of too many states, I wonder whether the groups divided from it are still too large, as there are only three groups. 
+ It is better to clarify which episode the s_{last} comes from. According to Fig. 4, the last visited state comes from the "next" episode. However, according to the "Attention Strategy" in Section 4.1, s_{last} is appended to each group since the beginning of each episode. So is s_{last} here not from the "future" episode? Please correct me if I misunderstood your illustration. 
+ Regarding Appendix E.4, is a method regarded as more sample efficient if it can explore more unique nodes and form a larger group given a fixed number of episodes?
+ Not sure experiments are enough. For example, just comparing to HER. There are some recent works [1, 2] addressing similar problems and tasks. It is better to compare to them or at least mention the difference.

[1] Curriculum-guided Hindsight Experience Replay, NeurIPS-2019

[2] Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning, ICML-2020

review_title: Idea is interesting. Some parts are unclear. Experiments are not enough.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work presents a strategy for improving exploration and efficiency of RL by leveraging the graph structure of an episodic experience buffer. This strategy combines goal-oriented RL with structured exploration. The authors compare their proposed technique to two popular benchmarks for goal-reaching tasks. In addition, the authors provide some theoretical justification for their algorithmic choices.

### Clarity
The biggest issue with this paper is clarity. Grammar is a minor part of this issue, but the major clarity issue is that it's simply quite hard to understand what exactly the authors are proposing/doing in this work. It's very unfortunate, because it seems like there might be some interesting ideas here, but it is very hard to say because so many details are not clear. The best resource for understanding what the authors' proposed technique is the algorithm box and accompanying text in Appendix B, but this is still not enough.
The lack of clarity is perhaps worst, and most crucial, when it comes to describing how the graph is constructed. How do you go from a set of trajectories to a useful graph representation? In addition, it is difficult to form an intuition around the logic of the algorithm -- for instance, how is the generated goal related to the task goal; or, does the multi-episode graph assume that the task goal is the same across episodes? The result of this confusion is that I would **not** be able to implement their algorithm based on the understanding I gain from the paper.
To the authors' credit, they do attempt to provide some high-level descriptions and include several high-quality illustrations of their proposed strategy, but the lack of clarity remains a decisive problem. It's entirely possible that fixing the clarity issues would result in a strong paper, but, unfortunately, it does not currently seem suitable for publication.


### Quality and Originality
This work fits into a recent trend of work using graph-based representations of the environment for structured exploration and planning. In particular, this work is focused more on graph-based exploration. Overall, the paper's clarity issues prevent a detailed assessment of its broader quality, but the high-level idea seems reasonably original. Certainly, this is not the first paper to recognize that trajectories of experience can reveal the environment's structure and that this structure is conveniently represented as a graph. But I am not aware of another paper that leverages this insight in order to learn to generate a curriculum of goals for good exploration. In addition, the author's technique seems agnostic to the composition of the environment, avoiding some shortcomings of prior work.


### Significance
Again, clarity issues make it difficult to assess the significance of the work. This should be expected to reduce the significance, though, since I doubt most readers will get a good sense of how to actually implement the paper's core idea. Since the work does not present many broader insights about RL, learning from goals, or structured exploration, its significance is linked to its practical value, which is currently limited by clarity issues.


**Pros**
- New algorithm for improving exploration in goal-oriented RL
- Experimental validation in complex, continuous domains

**Cons**
- Very difficult to understand the details
- Comparison to prior work is mostly unclear
- Would be difficult to implement based on current description

### Suggestions for improvement
If the authors can present a clear plan for how they will improve the clarity of the paper, I will be happy to consider raising my score. I recommend that the authors make use of more concrete examples. This would help to make the great illustrations (like Figures 2 and 7) more useful. Also, it may help to put the Related Work at the end of the paper. The comparison to previous work might be clearer if it is presented after the proposed technique is fully described.
review_title: Potentially interesting but major issues with clarity

Meta-review: This work presents an algorithm - graph-structured reinforcement learning (GSRL)- to address the problem of exploration in sparse reward settings. The core elements of this work are 1) to build a state-transition graph from experienced trajectories in the replay buffer; 2) learn an attention module that chooses a goal from a subset of nodes in the graph and 3) policy learning via DDPG using "related trajectories", where trajectories that are related to the generated goal are sampled from the replay buffer.

Pros:
- all reviewers agree that the idea/work is interesting and valuable to the community
- reviewers appreciate the theoretical graph-based foundation/motivations

Cons:
- clarity: the manuscript still remains hard to follow. Many critical components for understanding are in the appendix. 
-- One of the key steps in this work is the discretization of the state/action space for graph construction. However, this is not mentioned very clearly, which creates a lot of confusion given that you're considering continuous control domains. 
-- Furthermore, the group selection part and training the attention module is expressed in an overly complex manner. Without the reviewers inquiries it would have been impossible to decode the technical details of this key contribution, and unfortunately it remains hard to read/follow. 
-- while the ablation experiments (impact of discretization, group selection ..) are appreciated, but it is not clear on which environment they were generated (average across all? or only one of them?).
-- do you use DQN and DDPG? There are some conflicting statements in your paper, namely first you say "We use off-policy algorithms named DQN (Mnih et al., 2013) for discrete action space and DDPG (Lillicrap et al., 2015) for continuous action space", then in the experiments you say "to demonstrate the real performance gain of our GSRL we set the policy network with DDPG for GSRL and all baselines".  
- I agree with the reviewers that it's not clear why the chosen baselines are very relevant - there seem to be other more relevant baselines. 
- the significance of the attention module is not very clear, and is not analysed properly. What does it really learn? some form of deeper analysis would be useful here. How would a version that simply picks the most uncertain state in the graph? The ablation graph presented is not very convincing.


Overall, I believe that this work will make a valuable contribution in the future, with an iteration to improve clarity and better show-case the significance of the attention module.
Decision: Reject