Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new sampling schedule for the experience replay buffer often used by reinforcement learning algorithms. The proposed approach is to perform value backups via bread-first search, starting from the set of terminal states and then moving backwards. The paper proposes a way to building such graph from sampled transitions and it shows, empirically, that the proposed approach (TER) performs better than other methods in a specific class of problems. 
main_review: This paper clearly tackles an important problem to a currently relevant class of algorithms in the community. However, the proposed solution is completely tailored to a particular type of reinforcement learning problem: episodic, goal reaching problems, where the observed reward signal is zero in every transition but the final one. This drastically reduces the applicability of the proposed method. Some important components/assumptions of the overall approach are also not properly discussed/evaluated. Moreover, this is a paper that touches on one of the most fundamental aspects of deep RL solutions, but it justifies itself only on a small set of domains that are not necessarily the domains in which deep RL algorithms (and their replay buffers) were originally proposed and evaluated. This raises more questions about the real feasibility of the propose approach. The text could also be improved for precision.

First and foremost, it seems to me that TER is only effective in RL problems in which the agent observes a reward signal of value zero until success. This seems fairly limiting to me. How can one use TER when the RL agent is tackling problems in which the reward function doesn’t have this structure? Robotics, for example, often uses a dense reward function which is a function of the distance between the robot and the goal. This is reflected in reward functions such as those used in simulators such as MuJoCo, for example. Other simulators have different patterns, but even Atari games that became notorious for their sparsity of rewards (e.g., Montezuma’s Revenge) are not problems in which only one non-zero reward signal is observed. How much TER is a general approach and how much is it a method to leverage very specific features of a subclass of problems?

Some of the assumptions apparently being made also seem quite limiting. Specifically, experience replay buffers are often used for deep RL, when the state space is so large that function approximation is necessary. In that case, it is not clear how often one observes common states in different trajectories. Again, this is a fairly limiting assumption, not to mention that things such as distractors and randomness may even make two equivalent states look differently. The discussion at the end tries to dismiss this suggesting “quick fixes”, but these are never evaluated. The same applies to the distinction between stochastic/deterministic environment. I don’t think the single experiment n Figure F.9 is enough to justify this is not an issue.

Related to this, I also have questions about the proposed method itself. For example, how important is the hashing component of TER? For distinct states it would obviously not lead to quick retrieval, but leaving this aside, how are collisions dealt with? Doesn’t the hash function itself matters? Also, the main justification for using an experience replay buffer in DQN was to decorrelate samples. Now, samples are not decor related, but the backups are heavily tied to the trajectory itself. I imagine this can have a horrible interaction with modern neural network training schemes, generating a lot of instability in non-toy domains.

The text has several issues in terms of precision or correctness. For example:

- “Off-policy algorithms are more data efficient than their on-policy counterparts by learning from the experience replay (Lin, 1992).” This doesn’t seem to be an obvious fact. What off-policy methods? What on-policy methods? What is the role things such as eligibility traces and importance sampling can have in this analysis? What about n-step methods? They are quite effective for whole trajectories.
- “The key ingredient in off-policy methods is Q-learning (Watkins & Dayan, 1992) that learns a Q-function to predict the expected future sum of rewards (i.e., return) at a state.” I’m not sure what this sentence means. Is Q-learning a key ingredient? Isn’t it a method? Learning Q-functions is ominous to most RL algorithms, off-policy and on-policy.
- “Let the agent receive a reward when it reaches the goal state (labeled as G), but not at any other state.” By definition, the agent receives a reward at every time step in an MDP.
- “We ran each experiment with 5 different random seeds and reported the mean and 95%-confidence interval on the learning curves.” How was the confidence interval computed with only 5 samples?

summary_of_the_review: This paper clearly tackles an important problem to a currently relevant class of algorithms in the community. However, the proposed solution is completely tailored to a particular type of reinforcement learning problem: episodic, goal reaching problems, where the observed reward signal is zero in every transition but the final one. This drastically reduces the applicability of the proposed method. Some important components/assumptions of the overall approach are also not properly discussed/evaluated. Moreover, this is a paper that touches on one of the most fundamental aspects of deep RL solutions, but it justifies itself only on a small set of domains that are not necessarily the domains in which deep RL algorithms (and their replay buffers) were originally proposed and evaluated. This raises more questions about the real feasibility of the propose approach. The text could also be improved for precision.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new sampling strategy to improve the sample efficiency of Q-learning based methods. Bootstrapping being a fundamental characteristic of TD methods, the accuracy of the next state's value is critical in updating the current state. Previous work preform a similar observation, leading to methods such as backward value iteration. However, performing reverse sweeps is challenging in high dimensional tasks. As such, the authors propose to iteratively construct a graph representing the underlying MDP on which reverse sampling is executed. The authors report considerable improvement on grid-like tasks when compared to baselines that propose sampling schemes. The authors also provide numerous additional experiments attempting to elucidate the merits and limitations of the approach.
main_review: Strengths
-------------
-Finding more sampling efficient ways to sample from a replay buffer is an important avenue of research. 

-The authors are clear and open about the details of the implementation.

-There are extensive experiments that shine light on why the method works compared to previous approaches. It also showcases limitations. 

Weaknesses
-------------
-The experiments are somewhat limited to goal oriented tasks.

-The number of random seeds is a bit low.


Details
----------
Given the fact that replay buffers can be used with off-policy learning to accelerate model free reinforcement learning methods, it is surprising there is so little research around this topic. Reverse sweeping is intuitive and compelling, yet it is not straightforward to extend it to high dimensional data. Although the authors more or less limit the scope of applicability of their method to grid-like environments, it stills shows that such inductive bias can be useful for complex environments. This is somewhat acknowledged in the "Assumptions" section, however the assumption on being able to revisit the same state twice is left to the conclusion, which is questionable. I think it would be better for the setting to be clear from the beginning, as we can better evaluate the generality, limitations and future work throughout reading the paper. 

The details about graph construction are definitely appreciated. The "Overview" itself seems a bit lengthy and prehaps confusing by going sometimes into too much details. Regarding BFS, how many predecessors are sampled? If I understand correctly, there are multiple transition for each edge, but only one state for each node? Or is it possible that \phi maps two states to the same low dimensional space? Regarding hashing and random projections, it is almost un-intuitive for me that this would work. Could the authors elaborate on why this works in this setting, as well as elaborate on what setting would we see this choice be a bottleneck? Did the authors consider using neural networks to project the state, perhaps in a pre-trained manner?

Regarding the difference between EBU and TER, the authors mention that it is likely due to tracjectory stitching. Although I can probably guess what this means, it is never clearly mentioned in the paper what this refers to precisely. In TER(single pred, $\eta=0$), when a single predecessor is designated, does this still leave open the possibility to having multiple trajectories in the edge in-between?
The experiments in Figure 3 are pretty good. I would suggest clearly mentioning the values of $\eta$. I would also suggest augmenting the number of random seeds to 10. In the same spirit of reproducibility, I think it would be great to present the kind of hyper parameter search that was done for TER.

Regarding related work, the authors do cite (Lin, 1992), however they do not mention that within this work the author suggests and uses backward replay (i.e. a sequence is replayed in a backward order for updates), which highlights that the idea of reverse sweep is common itself. As the paper itself considers building a graph, references to recent work are somewhat limited. For example Jiang et al. 2021 and  Klissarov et al. 2020 very different method for creating the graph. The latter work is perhaps more related to this work in the sense that it seeks better sample efficiency within a single task. In general, the construction of the graph is a bottleneck for RL methods, and citing relevant literature in this space is important as it can accelerate future research.


summary_of_the_review: The authors provide a clear explanation of their method, code and implementation details. Although the experimental setup is a bit limited,  the results look good and the proposed approach has the potential to improve future work in this space. Moreover, many additional experiments are proposed to shine light upon the proposed method.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a topological experience replay (TER) method to perform Q value updates in a reverse sweep style. A variety of empirical results demonstrate that TER improves the Q-learning convergence speed significantly. The paper is well-written and well-organized, and the motivation is clear. 
main_review: However, I have the following concerns:

Q1. I believe the current version of TER is applied only to goal-reaching tasks where the learning objective is to reach goal states. The authors should clarify it in the abstract and introduction sections, and discuss how to extend TER to general RL tasks. 

Q2. I suspect that the hashing method may lead to an intractably large graph $\mathcal{G}$ especially for environments with large state spaces. I think it may be necessary to partition the state space into multiple state clusters to obtain a tractable graph.

Q3. I suspect that inaccurate graphs may lower the Q-learning convergence speed. Does it take a large number of samples to construct an accurate state graph? If so, the TER algorithm requires some warming-up time-steps to collect samples to construct a comparatively accurate state graph, which should be discussed in the main text.

Q4. The authors only consider the construction of undirected graphs, which makes their method not applicable to MDPs where states form directed graphs.

summary_of_the_review: Although the paper is well written, the current version does not convince me to recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a novel experience replay technique motivated by the topology of the collected data. The technique changes the order in which states are sampled for a minibatch Q-function update, sampling states backwards in a breadth-first way through a trajectory graph constructed from the replay buffer. This means that terminal states, which are more likely (by assumption) to receive reward, and don't require bootstrapping for value estimation, are updated first allowing reward from these states to propagate backwards to earlier states quicker. This method shows improved performance on several MiniGrid and Sokoban tasks, outperforming other baseline experience replay methods (PER, EBU, DisCor). They perform extensive ablations on the difference between TER (their method) and EBU, showing why TER outperforms EBU.
main_review: ## Strengths
- The paper's presentation is clear and easy to read
- The paper's main idea is simple to understand, and seems to improve performance robustly
- Stating the assumptions of the method is good.
- Rigorous ablations and analysis are carried out to understand how the method improves on prior work

## Weaknesses
- I wouldn't describe MiniGrid as an image-based environment, and while sokoban may be, the number of different images is still quite low. This makes the state-matching for trajectory stitching possible, which it wouldn't be (naively) in higher dimensional spaces. The hashing could address this, but I think it's worth adding that the hashing being good (or having another way of matching states between trajectories) is effectively an assumption of your method
- Due to the assumptions of terminal states being rewarding, the method is limited, unless a proposed way of improving it to apply to more general reward structures was presented.

## Questions
- What view of minigrid are you using? For example is the veiw ego-centric, or does it include the entire map. And is it the RGB rendering of the map, or the tensor representation?
- It would be good to see results on how often state matches occur in general. Especially for these environments with randomly generated levels, it seems unlikely that states would match unless they're from the same generated level.

summary_of_the_review: Overall I believe the paper is good enough to be accepted. While a few additional experiments would be beneficial to the understanding of the method's performance, the main blocker towards me giving a higher score is the limitation of the method to environments where the terminal state holds most of the reward. I think the method is still interesting, but showing it can be applied in environments without rewarding terminal states and that it still improve performance in these environments would be beneficial.

EDIT: Having seen the additional experiments and clarifications the authors have added, showing that TER could be used in situations where reward is concentrated in states rather than just in terminal states, I raised my score from 6 to 8.
review_title: null

Meta-review: A new sampling strategy for experience is proposed and compared with alternative sampling strategies. The main weakness of the paper is the limited applicability of the strategy as it only works well goal-oriented tasks, and stochasticity reduces the effectiveness. And within this setting, only good performance is shown on two gridworld-like: MiniGrid and Sokoban. In the rebuttal phase, the authors have added additional experiments that suggest applicability of the approach beyond just goal-oriented tasks, which have let several reviewers to raise their score. While general applicability of the approach is still somewhat of a concern, the authors have done enough to show the potential of their approach. Hence, I recommend acceptance.
Decision: Accept (Poster)