Topological Experience Replay
Authors: Zhang-Wei Hong
Tao Chen
Yen-Chen Lin
Joni Pajarinen
Pulkit Agrawal
Venue: ICLR 2022 Poster (2022)
Keywords: Deep reinforcement learning
experience replay

Abstract: State-of-the-art deep Q-learning methods update Q-values using state transition tuples sampled from the experience replay buffer. This strategy often randomly samples or prioritizes data sampling based on measures such as the temporal difference (TD) error. Such sampling strategies can be inefficient at learning Q-function since a state's correct Q-value preconditions on the accurate successor states' Q-value. Disregarding such a successor's value dependency leads to useless updates and even learning wrong values.
To expedite Q-learning, we maintain states' dependency by organizing the agent's experience into a graph. Each edge in the graph represents a transition between two connected states. We perform value backups via a breadth-first search that expands vertices in the graph starting from the set of terminal states successively moving backward. We empirically show that our method is substantially more data-efficient than several baselines on a diverse range of goal-reaching tasks. Notably, the proposed method also outperforms baselines that consume more batches of training experience. 

Published as a conference paper at ICLR 2022
TOPOLOGICAL EXPERIENCE REPLAY
Zhang-Wes Wei Hong', Tao Chen', Yen-Chen Lin', Joni Pajarinen', & Pulkit Agrawal Improbable AI Lab, Massachusetts Institute of Technology Aalto University?
ABSTRACT
State-of-the-art deep Q-learning methods update Q-values using state transition tuples sampled from the experience replay buffer. This strategy often uniformly and randomly samples prioritizes data sampling based on measures such as the temporal difference (TD) error. Such sampling strategies can be inefficient at learning Q-function because state's Q-value depends on the Q-value of succes- sor states. If the data sampling strategy ignores the precision of Q-value estimate of the next state, it can lead to useless and often incorrect updates the Q-values. To mitigate this issue, we organize the agent's experience into a graph that explic- itly tracks the dependency between Q-values of states. Each edge in the graph represents a transition between two states by executing a single action. We per- form value backups via breadth-first search starting from the set of terminal states and successively moving backwards. We empirically show that our method is substantially more data-efficient than several baselines on diverse range of goal-reaching tasks. Notably, the proposed method also outperforms baselines that consume more batches of training experience and operates from high-dimensional observational data such as images.
INTRODUCTION
A significant challenge in reinforcement learning (RL) is overcome the need for large amounts of data. Off-policy algorithms have received great attention because of its ability to reuse data by experience replay (Lin, 1992) for learning the policy. The key ingredient in off-policy methods is learning Q-function (Watkins & Dayan, 1992) which estimates the expected sum of future rewards (i.e., return) at a state. State-of-the-art deep RI. algorithms train the Q-function by bootstrapping Q-values from state transitions sampled from the experience replay buffer (Mnih et al., 2015). In bootstrapping, the sum of the immediate reward and the succeeding state's Q-value are used as the target (or "labels") for the current state's Q-value. Because of the dependency states' Q-value, the order in which states are sampled to update the Q-value substantially influences the convergence speed of Q-value. An improper update order results in slow convergence.
the successor
As a motivating example, consider the Markov Decision Process (MDP) shown in Figure 1. Let the agent receive a positive reward when it reaches the goal state (labeled G), but zero other stated. (note that our method does not need rewards to be 0 or 1). Starting from state C, the agent can obtain the reward by visiting states in the sequence C + D + G. Now if the Q-value of taking action at state D, Q(D, a). is inaccurate, then using it to update Q(C, a) will lead to an incorrect estimate of Q(C, a). It therefore natural to start at the terminal state G and first bootstrap Q-values of preceding states (D, E), and then for states (A, B, C). Using such a reverse order for bootstrapping ensures that for each state, the Q-values of successor states are updated before an update is made to the current state's value. In fact, it has been proven that for acyclic MDPs such reverse sweep is the optimal order for bootstrapping (Bertsekas et al., 2000). Other works (Grzeš & Hoey, 2013; Dai & Hansen, 2007; Dai et al., 2011) have further empirically demonstrated the effectiveness of reverse sweep in cyclical MDPs.
However, it is challenging to perform Q-learning with reverse sweep in high-dimensional state spaces since the predecessors each state are often unknown. State-of-thh-arr Q-learning meth- ods (Mnih et al., 2015; Lillicrap et al., 2015; Haarnoja al., 2018; Fujimoto al., 2018) resort to random sampling of data from the replay buffer. Their speed convergence can be slow as these methods do not account for the structure in state transitions when selecting the order of states for

---

Published as a conference paper at ICLR 2022
Random pampling
Reverse Seveep
Num. bacoupa
Selected
(6.0)
max Q a)
mAX Q(a, >
Figure I: The ordering of states used for updating Q-values directly effects the convergence speed. (a) Consider the graphical representation of the MDP with the goal state (G). Each node the graph is state, The arrows denote possible transitions a,, s') and the numbers on the arrows are the rewards r associated with the transition.
(b) Random sampling wastes many backups at states with zero values (gray) while each backup of reverse sweep propagates values (orange) one step back.
updating the Q-values. The speed of convergence matters because data collection is interleaved with Q-value updates. If the Q-values are incorrect, the agent may take actions that result in low rewards. Such data is useless for improving the Q-values of states in the high-return trajectories. Therefore, the slower convergence of Q-values is directly linked to the data inefficiency. One way reduce dependence on data is artificially increase the speed of convergence by increasing the ratio between the Q-learning update steps and the data collection steps. However, when function approximators are used to estimate the Q-value, excessive updates on fixed set of interaction data can lead to over-fitting and overestimation of the Q-values, resulting in worse overall performance. Our experiments in Section 5.4 empirically confirm this hypothesis.
To speed up Q-function convergence in high-dimensional state spaces, approximate the reverse sweep update scheme via stitching the trajectories stored in the replay buffer to construct graph. The graph is built directly from high-dimensional observations (c.g.. images). Each state is vertex, and two vertices are connected with an edge if the agent transitions between them during training time. As result, trajectories are joined when common state appears in different rollouts. In our framework, graph building and exploration proceed iteratively. The resulting graph provides information about the predecessor of each state, which is used determine the update order of the Q-function based on the reverse sweep principle. The reverse sweep is initiated from a set of terminal states because bootstrapping is not required to determine the correct Q-value for these states. We call this method Topological Experience Replay (TER) because the update order of Q- values based on the topology of the state space.
2 RELATED WORKS
Experience replay Devising experience replay strategy to improve Q-learning is an active field in deep RL. Prioritized Experience Replay (PER) (Schaul et al., 2015) prioritize states by the bootstrapping errors (also called temporal difference (TD) error) (Schaul al., 2015). Since during training the TD error depends on a (possibly) erroneous estimate the Q-values, PER can lead slow convergence speed. Episodic Backward Update (EBU) (Lee al., 2019) and Lin (1992) replays interactions trajectories in the reverse order of state visitations in every episode. However, for instance, Figure 1, moving backward in a trajectory (A, E, E, D. misses the other predecessors of D (i.e.. C) while the Q-value of D affects that of C. DisCor (Kumar et al., 2020) re-weights the error of state transitions to approximate the optimal bootstrapping order while the conservative weighting scheme of DisCor impedes learning progress. Different from the above works, we reorder states for updates based on the states' Q-value dependency.
Reverse sweep Similar ideas of reverse sweep were studied different scenarios. Assuming the access to the simulators, Florensa et al. (2017) trained RL agents from initial states that are closer to the goal and are gradually chosen to be farther away. Moore & Atkeson (1993) fitted an enviroument dynamics model for generating the predecessors of the states of high bootstrapping errors successively backward to update the Q-values. Goyal et al. (2019) extended this algorithm by learned generative model to perform backward rollouts from high-value states. Schroecker
2

---

Published as a conference paper at ICLR 2022
et al. (2019) trained an imitation learning model to match the expert's predecessor state distribution generated by a backtracking model. Instead of augmenting the training dataset by manipulating simulators or generating synthetic data, our method rearranges the existing dataset to aid training.
Graph for RL Prior works organizing experience into graph focused on temporally abstracted planning. Savinov et al. (2018) learn to build graph for navigation from images. Eysenbach et al. (2019); Zhang et al. (2021); Emmons et al. (2020) provide RL agents with sub-goals by planning over graph. Zhu et al. (2020) regularizes the Q-learning training via an additional graph Q-function defined over graph. Instead of taking advantages of temporal abstraction from graph, use graph to maintain states' dependency for improving Q- Q-function learning.
Model-based RL Graph is similar with the world model used in model-based RL, but TER uses it for different purpose. The classic work (Sutton, 1991) maintains the state transition probabili- ties of each state and sample states by these transition probabilities to update the Q-values. Recent model-based methods (Hafner et al., 2019; Nagabandi et al., 2018 8; Deisenroth & Rasmussen, 2011) typically learn world model (e.g., neural network or Gaussian process) for generating "imaginary" data for training the RL agent or planning. Imaginary data augments the replay buffer, improving the agent's 's performance by training it with data absent in the replay buffer. Instead generating synthetic state transitions, TER employs the graph to find better update order of each state tran- sition in the existing replay buffer for training the value function. In other words, model-based RL. augments the dataset while TER sorts the dataset.
PRELIMINARIES
We consider reinforcement learning (RL) (Sutton & Barto, 2018) in episodic discrete-time Markov decision process (MDP). The objective of RL is to find the optimal policy, H², that max- imizes expected return E { rr Barto, 2018), the S represents the set of all states in the MDP, and t denotes the time step. At a time step the agent takes the action a, =(5)), receives reward r, = (8,, ur 87+1), and transitions to the next state 4,+1, where R is the reward function. At the time r of task completion (c.g., reaching goal states) the episode termination indicator {s,) 1, otherwise E(s,) 0.
s] Vs E S, where is discount factor (Sutton &
Q-learning a popular algorithm for finding the optimal policy. It learns the Q function Q(s, a) = E [[ET] yT "r-rr = s,a, = a] using bootstrapping operations: Q(s, a) + R(s, a, s') + max Q(s', a') where s' is the state encountered on executing action a in the state s. The pol- icy (s) can be easily derived as: <(s) =- arg max, Q(s, a). When S is high-dimensional. the Q function is usually represented by a deep neural network (Mnih et al., 2015). The interaction data collected by the agent is stored in an experience replay buffer (Lin, 1992) in the form of state tran- sitions (St. ae, Tt. $1+1). The Q function is updated using stochastic gradient descent on batches of data randomly sampled from the replay buffer.
4 METHOD
Our method, topological experience replay (TER), is central at performing reverse sweep to update the Q-function in high-dimensional state spaces. Reverse sweep is known to accelerate Q-function convergence yet requires the knowledge of predecessors of a state, which is often unknown in high- dimensional state spaces. We overcome this limitation by building a graph from the replay buffer and guide the Q-function update with a reverse sweep over the graph. Section 4.1 presents the overview of our proposed algorithm. In Section 4.2, we describe the procedure for building the graph from high-ddmmesiionl states. Next, in Section 4.3, we describe how the graph is used to determine the update order for Q-learning. Finally, we present a batch mixing technique Section 4.4 that guarantees TER to converge.
4.1 TOPOLOGICAL EXPERIENCE REPLAY
Assumption Similar to prior works of reverse sweep in tabular domains (Dai & Hansen, 2007), assume that the objective of the MDPs is to reach terminal states (i.e., goal states). When an
3

---

Published as a conference paper at ICLR 2022
agent successfully completes the task, the agent must be at some terminal states. This assumption is required, otherwise reverse sweep will not help the agent learn optimal Q-value faster. Another assumption is that agent must be able to visit the same state twice that can find the joint state between two episodes for building the graph. This is an admissible assumption since Zhu al. (2020) shows that an agent can visit repeated states even in high-dimensional image state spaces Bellemare et al. (2013).
Overview TER iteratively interleaves between graph building and reverse sweep online during training. The agent collects experience at each step and periodically updates the Q-function. Each new transition (s, a, r, r') ) is mapped to an edge on the graph. When updating the Q-function, TER performs a few steps of reverse sweep for making batch of training samples. The reverse sweep starts from the vertices associated with terminal states. Each step in the sweep gathers transitions stored at an edge for training the Q-function. The batch mixing technique mixes the transitions that are fetched during reverse sweep and randomly sampled from the replay buffer, ensuring those transitions disconnected from terminal states to be updated. The pseudo-code Algorithm details the whole procedure.
4.2 GRAPH BUILDING
Data structure We organize the replay buffer unweighted graph of state transitions. The graph keeps track of the predecessors of states and stores the transitions. Let an unweighted graph be = (V. }., where V. denote the set of vertices and edges, respectively. As the graph will be queried frequently for replaying experience, we desire a query-efficien data structure. Thus, we implement G as nested hash table, where the outer (v') and inner (v) keys correspond to a pair of vertices in an edge e(v, r') E E where v, v' E V. We associate a transition (s, a, r, s') with an edge by a hash function db Each edge e(v, v') stores a list of transitions (s, a, 8') where o = ((s) and o' ((5'). We then can retrieve the predecessor transitions of state in (()) time.
Hashing Since high-dimensional states cannot directly serve the hash-tables keys for fast query, we require a encoding function Φ : S + Id that transforms states to low-dimensional representa- tions (keys in the graph 9). The minimal requirements of this encoding function is being able to distinguish two different states. We thus make use of random projection as the encoding function ((s) := Ms where s E S. M is matrix with elements randomly sampled from a normal distri- bution No roam (0, 1/d). where d denotes the dimension of projected vectors', as prior work has empirically found that random projections can distinguish individual visual observations (Burda et al., 2019; Zhu et al., 2020). Though an encoding function that aggregates states with similar task-relevant features would be helpful for determining better update orders, we simply use random projection, since our focus is not representation learning for hashing.
Update scheme The graph is iteratively updated online at each time step by the incoming transi- tion and each transition (st, ae, Tt, st) is stored into the hash table G. We add ((s)) and @(s++1) 1) to the vertex set V and append the transition (st, Tt, $1+1) to the list of transitions stored in the edge (()())) ((++1))) We can retrieve the predecessor transitions of by querying e(v, o(>')) Ve E V for a reverse sweep. The predecessor transitions of a state is aggregated from multiple trajecto- rics. Let (SA. a, A. T'A.'' ) and (sg, aB. TB, s'g) be two transitions from different trajectories. Both transitions can be retrieved by e(v, Ve E V if o' ((5'x)) = @(s')) (i.c., outer keys of G).
UB,
4.3 REVERSE SWEEP
Algorithm Once the graph is built, the next step is determine the ordering of states for updating the Q-values. Same as common experience replay methods, Q-function is periodically updated online with mini-batches of data sampled using a fixed replay ratio (Fedus et al., 2020). Each batch of training data is collected via a reverse sweep. More specifically, we maintain record of vertices that correspond terminal states, and this set is denoted by Ve. Each terminal vertex Ve acts as the root node. We perform reverse breadth-firs search (BFS) on the graph starting from subset of v, sampled from Ve separately. The Ue serves as the initial frontier vertex v'. For a frontier vertex o'
IIf is image, we flatten s into an one dimensional vector before the transformation.
4

---

Published as a conference paper at ICLR 2022
in the search tree, we first sample its predecessors and append the corresponding state- teaeetrtanitinnss sampled from e(v, v²) to a batch.queue. Then we set the predecessors to be the new frontier vertices and fetch transitions. Once there are B transitions in the batch queue, mtatetrrnssiionss for updating the Q-function. We resume the tree search next time starting from the frontier e' update the Q-function. Note that BFS only expands each vertex once, and thus infinite loop on cyclic (i.c., bi-directional) edges will not happen. When there is no vertex to expand, reverse sweep is restarted from a of root vertices sampled from VE again.
pop out B
Complexity Compared with uniform experience replay (UER) (Lin, 1992: Mnih al., 2015), the extra memory needed is at most |E| low-dimensional vectors in the hash-table's keys. Instead of growing endlessly, the graph g pruned once the number of transitions (s, a, r, s') on the graph greater than user-specified replay buffer capacity. For pruning details and the hyperparameter settings, see the Section A. The time complexity of making a batch of training transitions is O we fetch data from B vertices. We show that the wallclock computation time is close typical methods in Section A.7.
4.4 BATCH MIXING
One potential drawback of starting the reverse sweep from only terminal states is that the states that are unreachable from the terminal states will never be updated. Consequently, the Q-values of such states are not updated, which impedes the convergence of Q-learning Prior work (Dai & Hansen, 2007) has shown that interleaving value updates at randomly sampled transitions and at transitions selected by any prioritization mechanism ensure the convergence. Thus, we mix experience from TER and PER Schaul et al. (2016) to form training batches using mixing ratio rJ E (0, 1]. For each batch, 17 fraction of the data is from PER, and 1 7) is from TER. Additional details of batch mixing are provided in the supplementary material Section
Algorithm Topological Experience Replay for Q-Learning
Input: A hash function é, warm up period Twam. batch size B
1: Set empty graph G (V 0, E 0} and terminal vertices set Ve 0
2: Set search_queue and bat cquque as empty queues and visited.vertex + 0 for BFS
3: for t 0, 0,...... do
> online training loop
4:
Take action o and receive experience (st, at St41)
5:
Add ((s;) and (($++1) to V, and c()(s;), 6(5441) to
6:
Augment the terminal vertices set V/8 + Ve U (0(St=1)) if ((441) =1
7:
while > Twarmpp and len (batch_quee search.queue empty then
< do
8:
9:
Add sampled vertices from Ve to search-queue, visited.veree
10:
end
11:
Pop of from search queue until v' visited vertex
12:
Sample a subset the predecessors edges Er(w') (e(u, E F. = v/} of
13:
Push {o e(u, o') Ep(r')) to search_queus
14:
Push (s, a, r,),,) s') stored at each predecessor edge e(t,e') Ep((') to bat batch.queue
Mark of as expanded: visited + visited.vertex (v')
16:
end while
if
Twarmup then
Pop a minibatch of experience b ((8;, a, Fi # from batch batch.queue Update Q function with b
19:
end if
21: end for
EXPERIMENTS
We aim to answer the following primary questions: (1) Does TER accelerate the speed of conver- gence of Q-learning? (2) Does TER improve sample efficiency in high-dimensional state spaces?
5

---

Published as a conference paper at ICLR 2022
(3) Does baselines with higher replay ratios match TER's efficiency? In addition, Section 5.5 ana- lyzes the effect of batch mixing in TER, and Section 5.6 investigates why TER improves the sample efficiency.
5.1 SETUP
Environments We evaluate TER in Minigrid (Chevalier-Boiswi) et al., 2018) and Sokoban (Schrader, 2018) as the tasks' objectives are to reach terminal states (i.c., goal states) and both domains have challenging tasks for Q-learning. In Minigrid and Sokoban, the agent observes the top-down image view of a grid map and moves around in the grid map to complete the task. For each task, the map randomly generated at each episode, so the policy needs to generalize across different map configurations. In Sokoban, the task is to push all the boxes on the map to the target positions where the map sizes and the number of boxes can be varied. We denote a configuration in the format <size>x<si> ze> <num. boxes>. All of the environment details be found in the Section C.
Baselines. We compare TER with uniform experience replay (UER) (Lin, 1992; Mnih et al., 2015), prioritized experience replay (PER) (Schaul et al., 2016), episodic backward update (EBU) (Lee et al., 2019), and DisCor (Kumar et al., 2020). UER uniformly samples state-transition tuples from the replay buffer. PER prioritizes experience with high temporal difference (TD) (Sutton, 1988) errors defined as Irt + max.' Q(s', a') Q(s, a)]. EBU uniformly samples an episode from the replay buffer, and updates the Q-values of the state-action pairs in the sampled episode reversely. For example, given an episode ($1, 01, 1,, 82, 02 r2, 83, ....... ST -1. Pr-1, sT), EBU updates in a sequence (Q(T-1,,r--1) Q(ST-2 (0r-2.ar-21 ar))) ..... ((51, a1)]. DisCor re- re-weights each Q-function update inversely proportional to the estimated bootstrapping error [Q'(s', (s', a') - Q(s', ; a')l of a state- action pair (s, a), where Q" denotes the optimal Q-function.
Implementation. We test each experience replay method along with double deep Q-learning (DQN) (Van Hasselt et al., 2016) with the same architecture used by (Mnih et al., 2015). In DQN, the Q function is updated once per four environment steps (i.e., replay ratio = 0.25) unless spec- ified otherwise. We e-greedy method for exploration. We have reused implementations of the baseline methods and DQN from pfrl codebase (Fujita et al., 2021). For EBU, we adapted the publicly released code in the framework of pfrl. We re-implemented DisCor and verified that our implementation reproduces the results reported in the paper (Kumar et al., 2020). For TER, we use 7 0.5 for Minigrid and 17 0.2 for Sokoban. Additional implementation details and our reproduction of DisCor results are available in Section A.
Evaluation Metric. We ran each experiment with 5 different random seeds and reported the mean (solid or dashed line) and 95%%-coffidence interval (computed by bootstrapping method DiCiccio et al. (1996)) on the learning curves. The learning curves indicate the average normalized return over 100 testing episodes in varying number of environment steps. More details are provided in Section B.
5.2 AN ILLUSTRATIVE EXAMPLE
We experimented with NChain environment, as shown in Figure 2a, to illustrate that TER gives rise to a more efficient updating order. The only positive reward in NChain emits at the rightmost terminal state (i.e., node N). As the only reward is distant from the starting state, it is easy to observe the impact of a misspecified update order. In order to rule out the influence of exploration, collected fixed number of rollout episodes where the agent took random actions and then used these pre-collected experiences to train TER and all the basclines. Figure 2b shows the normalized return and the average Q-value error the training progresses. The value error calculated by the absolute difference between the agent's ' Q-function and the ground truth optimal Q-function. We see that the TER agent obtains the highest score after only 30 value backups, while UER, PER, and DisCor fail to solve the task in 100 updates, which shows the importance of update order. Even the best baseline method (EBU) takes twice the number of backups on average. As TER differs

---

Published as a conference paper at ICLR 2022
NChain (N=20)
NChain (N=20)
Nornalized return
NChain
Start
End
UEA
2
3
N-1
0.4
0.
0.2
[oum]]
0.0
0.0
20
100
80
updates
(a)
(h)
Figure 2: (a) The illustration NChain environment. Each node denotes state, and the arrow represents valid transition between nodes. (b) TER achieves higher performance with fewer updates and reduces the value error of the Q-function faster than the baselines.
from EBU in that EBU only backtracks from the instantaneous trajectories, this shows the benefits of backtracking from the episodes stitched by the graph. Also, show that the value error of TER reduces faster than the baselines, which suggests that TER converges to the ground truth optimal Q-function faster.
5.3 How DOES TER PERFORM IN A HIGH-DIMENSIONAL STATE SPACE?
We investigated TER is effective in environments with -igh-nmmensioall state space such as im- ages in Minigrid and Sokoban (see Section 5.1). Overall, TER outperforms the baselines in Minigrid and Sokoban, as shown Figure 3a and Figure 3b. In Sokoban, such improvement is even more significant when the environment map is bigger, and there are more boxes than the others. Surpris- ingly, we can see from Figure 3b that EBU and DisCor perform worse than UER. We find that the average Q-value of EBU is much bigger than the maximum possible return in the environment (Sec- tion D), suggesting that EBU suffers from the overestimation problem (Hasselt, 2010) that hinders the Q-leaming. Also, find that the exploding value error estimates in DisCor impede the learning progress, where the updates are down-won weighted exceedingly due to huge estimates on value error. In addition, we present the analysis the influence of random projection dimension d in Section J, showing that TER is insensitive to the choice of d.
5.4 HOW DOES TER COMPARE TO THE BASELINES WITH HIGHER REPLAY RATIO?
As we mentioned in Section 1, the convergence speed of Q-learning can affect sample efficiency. Even though TER demonstrates superior learning efficiency the previous section, critical unan- swered question is whether baselines can achieve similar sample efficiency with more frequent Q- function updates compared TER. Thus, for all baselines, we increase the replay ratio defined as the number of gradient updates per environment transition (Fedus et al., 2020). Figure 4 shows the learning curves the baselines with different replay ratios of 0.25, 1.0, 2.0 and TER. For instance, 0.25 means 1 gradient update for every 4 environment steps. Overall, increasing the replay ratio does not consistently improve the performance of the basclines, except for Lavaarossing--Hore found that a possible reason could be Q-value overestimation (Hasselt, 2010). Figure 4b shows that the average Q values of the baselines with larger replay ratios are much higher than Rmax (i.e., the maximum return in the task), implying significant Q-value over-estimation. We compute the nor- malized difference between the learned Q values and Rmax: E.alQ(e.a)) and [Q,,a a)] is the average Q values during training. Therefore, even though we increase the replay ratio, does not close the performance gap between the baselines and TER.
We
Hmav
5.5 HOw DOES BATCH MIXING AFFECT TER?
Figure shows the learning curves of TER with different batch mixing ratios, where the number in the legend denotes the batch mixing ratio r defined in Section 4.4. The results of Sokoban show that high ratio can fail TER and a low ratio leads premature convergence. It can be best best-performing variants are TER with 0.1 and 0.2 mixing ratios. On the contrary, TER is insensitive to the mixing ratio in Minigrid, where each variant exhibits similar performance. The reason for
that the

---

Published as a conference paper at ICLR 2022
Sey
1.00
6.00
5.80
2.43
0.3M
1:M
2,3M
0.3M
1.5
SimpleCrawnng-ttrd
LaveCrawwingettrrd
UER
0.00
PER
2.43
0.23
DisCor
2.00
TER(ours)
2.54
3.5M
2.3M
0.3M
1:M
25N
0.5M
3,50
2.5M
(a)
3.05
3.80
0.80
5.43
0.23
0.4H 2,04
0.NN
2.0N
6.ON
Socobann5xx-22
Soloban-6xi-2
5olemban-7u7-2
1.02
UER
PER
DisCor
TER(ours)
32H 0.4H 7.5M 0
3.3M
3.2H
5.5H
3.2H
3.0M
S.NM
(b)
Figure 3: TER outperforms the baselines (a) Minigrid and (b) Sokoban, demonstrating that TER work with high-dimensional state spaces. In (b), the plots ordered by task difficulty (i.e., reward sparsity) from left to right. The performance gain of TER is more salient when rewards are more sparse. The x-axis the environment steps. y-axis is the normalized mean return.
2.00
Unlock
LavaCrossingetard
Unlock
LawaCnssirg-aar
tMr martaddd Ovakue
3.00
2.0
0.00
2.0
0.20
0.0
UER
-3.0
PER
3.00
0.5M
Stkkobnn- -xx-3
3.5M
2.5M
0.5M
So Solcbbn--ba 8xob22
3.5M
-2.0
5.0
3.5M
Soboban-6x--
1.50
2.5M
0.5M
Seloban-tx6-2
3.5M
2.5M
DisCor
EBU
TERfours)
5.000
Mormalzed O Dift
4.0
implay_rati
3.0
0.25
2.0
1.0
2.0
0.20
3.00
2.08
6.M
10.
3.0M
5.0M
6.0M Timestep
10 10.0M
3.CM
Timestep
Timestep
Timesteep
(a)
(b)
Figure 4: (a) Increasing the replay ratio does not consistently improve the performance of the base-
lines. (b) Increasing replay ratios leads to Q-value overestimation in baselines.
this result could be that the successful experience is easier to get in Minigrid than that in Sokoban. As the states in a successful episode must be connected to a terminal state, more transitions will be replayed in the reverse sweep. Hence the issues about the non non-updtted states can be minor. Overall, though the choice of mixing ratio can be environment dependent, we empirically found that TER with mixing ratio 0.1 and 0.2 perform well in both Minigrid and Sokoban.
8

---

Published as a conference paper at ICLR 2022
Unlack
LavaCrossing Hard
Sakaban 6x6-3
Sokoban 6x6
1.0
0.8
0.6
0.6
0.4
0.4
02
0.0
0.0
0.0
1.0
3.CM
1,0M
3.0M
2.0M
6.0M
20.0M
1.0M
3,0M
5.0M
Timestep
Timestep
Timestep
Timestep
TER(D.5)
TER(0.2)
TER(O.1)
TER(0.0)
Figure 5: The learning curves of TER with different batch mixing ratios. In Sokoban the choice of mixing ratio is more sensitive than that in Minigrid. TER with mixing ratio 0.1 and 0.2 perform well in both Minigrid and Sokoban.
5.6 WHY DOES TER OUTPERFORM EBU?
Since EBU and TER share the idea of reverse replay, natural question what explains the significant performance gap between the al- gorithms reported in Section 5.3. To inves- tigate if the benefit originates from stitching episodes, we made a variant of TER that dis- ables batch mixing (i.e., 17 0) and uses only one search tree and sample one predecessor during BFS, called TER single pred, 1) 0). Also, to rule out the influence of Q-value mixing hyperparameter 8 (Lee al., 2019) and timeout-states in EBU, we set 3 =
Unlock
LavaCrossing: Hard
0.53
Nenotted
0:31
0.00
0.00
0.03
3.00
0.5M
1.5M Timedlep
7.5M
2.50
1.5M
2.5M
T Timettep
EBU(7-0)
TER(eingle pred, n 0)
Figure The only difference between TiRgsingle pred, 0) and EBU (3 = 0) is trajectory stitch- ing while TER(single pred, r 0) still outperforms EBU (3 0). This shows that trajectory stitching results is critical for TER's performance gain.
for EBU and only replay backward from the terminal states in this experiment'. As such, the only difference between TER(ssingl pred, B = 0) and EBU is the ability to replay back- ward from a new path through the joint state between different trajectories. Figure shows that TER single pred, 7) 0) outperforms EBU, suggesting that the performance gap between TER and EBU likely results from trajectory stitching. In addition to this primary finding, we also show that applying batch mixing and filtering out timeout-states for EBU do not improve EBU's performance in Section and Section I.
CONCLUSION
In conclusion, we showcased that replaying experience in a backward topological order expedites Q-learning in goal-reaching tasks. Moreover, our experiments demonstrated that TER works in cyclical MDPs even though the strict topological orders are unclear where the rationale is presented in Section M. We present more discussion in Section O.
ACKNOWLEDGEMENT
We thank members of Improbable Lab for the helpful discussion and feedback. We are grateful to MIT Supercloud and the Lincoln Laboratory Supercomputing Center for providing HPC resources. supported by the MIT-IBM Watson AI Lab and it part by the Anmy The research was
The research in this paper Research Office and was accomplished under Grant Number W91 --N--2-----02- also supported by the Army Research Office and was accomplished under Grant Number W91 21-1-0328. The views and conclusions contained in this document are those the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the United States Air Force or the U.S. Government. The U.S. Government authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
Timeout-state does not indicate the task completion but triggers resets due running out of time. EBU also replays backward from these states.

---

Published as a conference paper at ICLR 2022
7
CODE OF ETHICS
Not applicable.
REPRODUCIBILITY STATEMENT
Please refer Section
REFERENCES
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013. 4, 14
Dimitri P Bertsekas et al. Dynamic programming and optimal control: Vol. 1. Athena scientific Belmont, 2000. 1, 23
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. 23
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network
distillation. In International Conference on Learning Representations, 2019. URL https: / //openrevieww.oo//////r/r net inteerrrriew..etttoooritettet-t dow.mmmmmm.11110oo511 4
Maxime Chevalier-Boisvert Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https: / / thub. com/ //ax/mxxiiii wwwp:mmebb//// bereeb/gymmmtt crym-mmniggrae 2018. 6,
Peng Dai and Eric A Hansen. Prioritizing bellman backups without priority queue. In ICAPS, pp- 113-119, 2007. 3,5,
Peng Dai, Daniel S Weld, Judy Goldsmith, al. Topological value iteration algorithms. Journal of Artificial Intelligence Research, 42:181 12:181-209, 201 1.11.
Mare Deisenroth and Carl Rasmussen. Pilco: A model--ased and data-efficient approach to policy search. In Proceedings of the 28th International Conference on machine learning (ICML-I1), pp- 465-472. Citeseer, 2011. 3
Thomas DiCiccio, Bradley Efron, et al. Bootstrap confidence intervals. Statistical science, 11(3):
189-228, 1996. 6, 15
Scott Emmons, Ajay Jain, Misha Laskin, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5251-5262. Curran Associates, Inc., 2020. URL https: httppp:://prooeeee http///oocceddeeecoccooo ngg neurips.e.... cce pdE.
Ben Eysenbach, Russ Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL https: httt:::/pproceeeiiiee
neurips cc/ 3
William Fedus, Prajit Ramachandran. Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In International Con- ference on Machine Learning, pp. 3061-3071. PMLR, 2020. 4,7
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse riculum generation for reinforcement learning. In Conference on robot learning, pp. 482-495. PMLR, 2017. 2
10

---

Published as a conference paper at ICLR 2022
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596. PMLR, 2018.
Yasuhiro Fujita, Prabhat Nagarajan, Toshiki Kataoka, and Takahiro Ishikawa. Chainerrl: A deep reinforcement learning library. Journal of Machine Learning Research, 22(77):1-14, 2021. URL
http://jml www.r.orggpppee wwaggpapersss 2222220- 376. htm..ttmmm..............mmm..w 6, 13
Anirudh Goyal, Philemon Brakel, William Fedus, Soumye Singhal, Timothy Lillicrap, Sergey Levine, Hugo Larochelle, and Yoshua Bengio. Recall traces: Backtracking models for efficient reinforcement learning. In International Conference on Learning Representations, 2019. URL
net/ forum? d- fnR9mm
Marek Grzeš and Jesse Hoey. On the convergence of techniques that improve value iteration. In The 2013 International Joinl Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2013. 1
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, pp. 1861-1870. PMLR, 2018.
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. arXiv preprint arXiv: 2019. 3, 21
Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with dis- crete world models. arXiv preprint arXiv:2010.02193, 2020. 21
Hado Hasselt. Double q-learming. Advances in neural information processing systems, 23:2613- 2621, 2010.
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp- 18560-18572. Curran Associates, Inc., 2020. URL https: http::: http::ppp//pproeeeeeeeeeeee neur ps cc/paper..
Papere pdf. 2, 6, 14
Su Young Lee, Choi Sungik, and Young Chung. Sample-efficient deep reinforcement learn- ing via episodic backward update. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL https bttps::/proceeee /ttp://ecccceeecccceeeccccccc.se neurips.co. pdf. 2, 9,
13, 18
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:/509.0297/ 2015.
Long-Ji Lin. Self-improving reactive agents based reinforcement learning, planning and teaching. Machine learning, 8(3-4):293-322 -2,1 1992. 1, 2, 5,
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 5 518(7540):529 -333, 2015. 1, 3, 5, 6, 13
Andrew W Moore and Christopher G Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine learning, 13(1):103-130, 1993. 2
Anusha Nagabandi, Gregory Kahn, Ronald S Fearing. and Sergey Levine. Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning, In 2018 IEEE Interna- tional Conference on Robotics and Automation (ICRA), pp. 7559-7566. IEEF, 2018. 3
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametri topological memory for navigation. In International Conference on Learning Representations, 2018. URL https: / //oppneeviii ew. net. feee/fooo http//orrmm?//m wtw.rrmmmd.sSyyyggg......

---

Published as a conference paper at ICLR 2022
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05992, 2015. 2
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In ICLR (Poster), 2016. URL http::/arxxv..rrg /ttp:o////////11.55922... 5, 6, 13
Max-Philipp B. Schrader. gym-sokoban, 2018. 6, 18
gym-sokoban.
Yannick Schroecker, Mel Vecerik, and Jon Scholz. Generative predecessor models for sample- efficient imitation learning. International Conference on Learning Representations, 2019. URL htttps://openrevll net forum? id=skeVs AcYm.
Richard $ Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting, ACM Sigart Bulletin, 264):160-163, 1991.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016. 6, 13
Hado van Hasselt, Matteo Hessel, and John Aslanides. When to use parametric models in rein- forcement learning? In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL https: http://////.....cc.//..../////ss neurips cccpaperr/219//ilee 11742ae215adf1 8b www.aaff885444444 45377449666222269222
Paper.pdl 21
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-992, 1992.
Lunjun Zhang, Ge Yang, and Bradly Stadie. World model as graph: Learning latent landmarks for planning. In International Conference on Machine Learning, pp.
PMLR, 2021.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In International Conference on Learning Representations, 2020. URL https:/ http:::s///pppeevieeee net forum? d= H 3.4
12

---

Published as a conference paper at ICLR 2022
A APPENDIX
A IMPLEMENTATION DETAIL
We implement all the methods based on (Fujita et al., 2021).
A. DEEP Q-NETWORK IMPLEMENTATION DETAIL
We use double DQN (Van Hasselt et al., 2016) for all the methods.
Network architecture Our networks consist of types of layers: 2-D convolutional layer Conv2D and fully connected layer Linear. We denote a Conv2D layer with parameters (imput.channel.dii and Linear with (input.channel..n
Output.channel.diin kernelsiiz, stride)
output.channel.di
For Minigrid, the DQN architecture is the sequential combination of [Conv2D (40+40+3, 32, 8, 4), Conv2D (32, 64, 4, 2). , Conv2D (64, 64, 3, 1), Linear (64, 512), Linear (512, num actions) with ReLU activation units followed by each layer.
For Sokoban and Atari, the DQN architecture is [Conv2D 32, 8, 4), Conv2D (32, 64, 4, 2), Conv2D (64, 64, 3, 1), Linear (3136, 512), Linear (512, num.actions) ] with ReLU activation units.
Target network For all environments, we use hard-reset that copies the current Q-function network to the target network periodically. The target network update interval is 1000 for Minigrid and 10, 000 for Sokoban and Atari.
Batch size, Optimizer, and Learning rate For all environments, we set batch sí zizz664 64 for Minigrid, batch_si 2ettchssiz==2 for Sokoban and Atari. The optimizers are Adam with 3e-4 for Minigrid and Sokoban. For Atari, we follow the configuration in (Mnih al., 2015) and RMSProp optimizer with learning.zate-2 5e alpha=0, 95, eps=le 2, and um=0n
<-greedy exploration We use c-greedy exploration for our method and the baselines. The value of is linearly decayed from 1.0 to 0.01 in 1M environment steps.
Experience Replay buffer We warm-up the replay buffer with the trajectories where the agent takes random actions. The warm-up periods are 50, 000 for all environments. The capacity (i.e., maximum number of elements) of the buffer is 1M for each environment. We draw batch of experience from the replay buffer to update the Q-function every environment steps, except for the experiments in Section 5.4.
A.2 PRIORITIZED EXPERIENCE REPLAY (PER) (SCHAUL ET AL., 2016) IMPLEMENTATION DETAILS
We use the implementation provided in pfrl. There are two poree--prrameers in PER: a and 8. Following the original paper (Schaul et al., 2016), set 0.6 and 0.4. The linearly transitions to 1.0 within 7 of the total training environment steps in the environment.
A.3 EPISODIC BACKWARD UPDATE (EBU) (LEE ET AL., 2019) IMPLEMENTATION DETAILS
We adapted the code from the official code- base to pfrl and set diffusion factor (Lee et al., 2019) as 0.5. Note that we also double DQN for EBU, though the original paper (Lee et al., 2019) uses the vanilla DQN (Mnih et al., 2015). As a sanity check for the correctness of implementation, we EBU in some of the Atari environments reported in the original paper (Lee al., 2019). The results shown in Figure L.15 show that the performances of our reproduced results are higher than
13

---

Published as a conference paper at ICLR 2022
Mean (sec.)
Median (sec.)
Min (sec.)
Max (sec.)
UER
0.002
3c-5
lc-5
0.086
PER
0.003
0.0001
4e-5
0.28
EBU 0.002
3e-5
le-5
0.083
DisCor
0.003
4e-5
le-5
0.11
TER
0.002
0.0002
0.0001
0.256
Table A.I: Computation time of making a batch of training transitions over the training time.
or match the original results in Pong, Kangaroo, and Venture, but lower than the original ones in Freeway.
A.4 DISCOR (KUMAR ET AL., 2020) IMPLEMENTATION DETAILS
We re- re-implemented DisCor based the implementation details provided in the original paper (Ku- mar et al., 2020). The initial temperature 7 is set as 10.0 and the t is updated to the batch mean of error network A prediction over the last target update interval when the target network is updated. As the original paper suggests, the architecture of the error network A is the DQN architecture for each task with an additional fully connected layer the end.
We verified the correctness of our implementation by testing DisCor in Atari Bellemare et al. (2013) Pong that is reported in the original paper (Kumar et al., 2020). Figure L.15 shows our result of Pong matches the original result in (Kumar et al., 2020).
A.5 TER IMPLEMENTATION DETAILS
Reverse Breadth-first Search (BFS) Since the number of terminal states in the environment can be large, we sample the vertices of some terminal states the roots of BFS search trees. For all environments, we sample 8 terminal vertices as the roots. For each vertex, we sample at most 3 predecessors to expand instead of enumeration. Enumerating all the predecessors can have too many predecessors
Vertex Encoding
We set the dimension d of the encoded states 3 for all the environments.
Batch Mixing
We set the batch mixing ratio as 0.5 for Minigrid and 0.1 for Sokoban.
Graph Pruning We prune the graph when the number of transitions stored at the edges in the graph exceeds the replay buffer capacity. The pruning is carried out according to the "age" each transition. The age of transition is current_env_sted t transiti wwwassiiioneenssteeeeeeeeeeeeeee current.env.step is the current environment steps and transiticn.env.ster the envi- ronment step when it added the buffer. When sampling batch of experience from the batch queue in Algorithm 1, we remove the transition which age exceeds the replay buffer capacity from the current batch and from the corresponding edge and pop more transitions from batch-quee to replace the removed transitions. Once an edge has no transitions remaining, we remove the edge from the graph.
where
A.6 CODE
Code is included in the zip file.
A.7
COMPARISON OF COMPUTATION TIME
As TER requires performing graph search over the training time, is worth knowing how much extra computation time is required by TER. Table A.I shows that TER's running time is similar to canonical experience replay methods on average. Also, the maximum running time over the training process is not greater than that of PER.
14

---

Published as a conference paper at ICLR 2022
B EVALUATION DETAIL
We ran each experiment with 5 different random seeds and report the mean (solid dashed line) and bootstrapped confidence interval (shaded part) (DiCiccio al., 1996) on the learning curves. The learning curves show how the averaged normalized return over 100 testing episodes change over the number environment interaction steps.
For each testing episode, fix the neural network weights of Q-function and run the agent with the greedy action (i.c., arg max, (s,, a)). Since the greedy action will not change if the state remains the same, let the agent take random actions with probability 0.05 prevent the agent from being stuck at the same state.
C ENVIRONMENT DETAIL.
We illustrate the example maps of each environment in Figure C.I.
Start
NChain
End
(a)
(c)
Figure C.1: (a) NChain. Each circle denotes state and arrow represents valid transition between two circles. (b) Minigrid. This figure shows one example environment in Minigrid. The agent takes the top-down image view of the two dimensional grid states. The red arrow denotes the agent, the green cell is the goal, the yellow square is a door, and the yellow key is used for opening the door. The black and the gray cells walk-able areas and walls respectively. The task is pickup the key, open the door, and then to the goal. (c) Sokoban. A randomly sampled environment in Sokoban domain. The yellow block denotes box, the red square represents target position, and the green object is the agent. The outer brown bricks denote walls and the black cells are walk-able ares. The goal to push all the boxes to the target positions.
C.I CHAIN
For NChain shown in Figure C.la, there are N states, .N...8N in the state space S and (forward, backward] actions in the action space A. At each state the agent can move to next state 8:41 by forward and the last state 8;-1 by backward. If the agent at 81, action backward will not effect. The agent gets +1 reward when transitioning from SN-1 to and otherwise. An episode terminates when the agent at sN.
C.2 MINIGRID
The official Minigrid implementation is referred to -Chivvlier-Boisvert et al., 2018). Fig- ure C.I shows an example top-down view image of the map. For each environment, each state is an RGB top-down view image resized to to 40 x 40 and the action space is (turn-left, turn.right, forward, pickup, drop, toggle). An episode terminates when the timestep exceeds the maximum time steps MAXSTEPS dependent on the task the agent receives +MAXSTEPS reward. Note that we modify the reward function defined (Chevalier- Boisvert al., 2018) since the default reward function is history dependent function. A history- dependent reward function is not valid for fully observable MDPs since history data un-obeervable in the state.
15

---

Published as a conference paper at ICLR 2022
DoorKey
The example levels are illustrated in Figure C.2. The task is pickup the key (yellow key icon), open the door (yellow square icon), and navigate to the goal (green block). The reward defined as
+MXXTTEPS the goal is reached otherwise
R(s, a')
1
Figure C.2: The images of randomly generated levels of DoorKey
Unlock The example levels are illustrated in Figure C.3. The task is to pickup the key (key icon) and open the door (yellow square icon). The reward is defined
+MAXSTEPS, the door is opened otherwise
R(s,a,
-1
Figure C.3: The images of randomly generated levels of Unlock
RedBlueDoors
The example levels are illustrated in Figure C.4. he task to open the red door (red square) and open the blue door (blue door). The reward is defined
MAXSTEESS the red door and the blue door are opened sequentially otherwise
R(s,,,88)
1,
Figure C.4: The images of randomly generated levels of RedBlueDoor
The example levels illustrated in Figure C.5a and Figure C.5b. The task is to navigate through the rooms to reach the goal (green block). There are more rooms in the hard
MAXSTEESS
the goal is reached otherwise
R(s,a,8))
The example levels are illustrated in Figure C.6a and Figure C.6b.The task to navigate toward the goal (green block) while avoiding the lava (orange block).
LavaCrossing- BaaCCrooinng-EsyHHaadd
+MAXSTEPS, the goal is reached MAXSTEPS, lava hit otherwise
R(s, (())), =
1,
16

---

Published as a conference paper at ICLR 2022
(a) The images of randomly generated levels of SissieCrossing Easy
(b) The images of randomly generated levels of SimpleCrossing-tarrt
Figure C.5
(a) The images of randomly generated levels of LavaCrossing Easy
(b) The images of randomly generated levels of LavaCrossing
Figure C.6
17

---

Published as a conference paper at ICLR 2022
C.3 SOKOBAN
The implementation can be found in (Schrader, 2018). We resize each RGB image state observation 84 x 84.
D AVERAGE Q-VALUES IN Sokoban
We compute the normalized difference between the learned Q values and the maximum return value in the environment: B. [Q(a.a]] - Rmax where Rmax is the maximum return the agent can get in the task, and (9,s a)] is the average Q values during training. Figure D.7 shows the average
Hanax
Q-values in Sokoban.
Sokoban 5x5-1
Sokoban 6x6-
Sokoban-7x7
Sokoban-6x6-
10.0
16.0
10.0
10.0
8.0
8.0
8.0
Qualls Dif,
max
4.0
4.0
4.5
2.0
2.0
2,0
2.0
-2.0
0.GH
2.00
0.0M
0.0M
-2.0
0.5M
1.5M
2.5M
-2.0
2.0M
6.0M
10.0H
5okoban-5x5-2
Sokoban-6x6-2
Sokoban-7x7-2
8.0
PER
vavav Dif,
6.0
6.0
EBU
DisCor
2.0
2.0
2.5
TER
0.0
0.0
0.0
0.6M
3.0M Timestep
Timeesop
Figure D.7: EBU tends to over-estimate the Q-values in Sokoban. UER, PER, and DisCor tend to under-estimate.
E HYPERPARAMETER SEARCH FOR EBU
As the original paper of EBU (Lee et al., 2019) did not have the best-fit ,3 for the benchmarks we considered in Section 5.3. Figure E.8 shows that the influence of is not significant. Thus, we follow the best-fit parameter reported in (Lee et al., 2019) and select B 0.5 for all of our experiments.
LavaCrussing-Had
Sokcoban-6x6-2
Sokoban-6xé-3
1.01
0.29
0.10
0.34
2.01
0.08
5.00
6.19
0:55
0.04
1.00
0.02
0.06
0.5M
1.5M Timsstop
2.5M
0.5H
3.5M Timestip
1.39
3.0M
2.0M
6.3M
CH
Timestop
Timsstop
EBUjO.0)
FBUJO.1)
EBUIO.5)
EBU(O.7)
Figure E.8: Performance of EBU with different 3
F STOCHASTIC ENVIRONMENTS EXPERIMENTS
We examine the performance of TER under stochastic transition dynamics in LavaCrossing- Hard. The stochasticity is realized by replacing the agent's action with a random action in 10% of steps in an episode. Figure F.9 shows that this stochasticity does not overshadow the advantage of TER.
18

---

Published as a conference paper at ICLR 2022
wwwaGresing--forr (stochasiic)
6.73
6.60
0.50
Nomatel Saturn
0.40
UER
0.50
PER
TER
Timestep
Figure F:9: Performance in stochastic environments
G PSEUDO TERMINAL STATE EXPERIMENTS
We further demonstrate an extension of TER to environments without terminal states. We test TER in the modified SimpleCrossing -oossing-Hardd and LavaCrossing -orrdssinn--aadd where the episode does not terminate when the agent reaches the goal. An episode terminates only when the time is up or entering lava. The agent gets +MAXSTEPS reward when entering the goal, -MAXSTEPS reward when exiting the goal or entering lava, O reward when staying at the goal, -1 reward otherwise. For TER, we construct "pseudo terminal states" for reverse sweeping. We keep track of the moving average of the accumulated rewards at a vertex, sample vertices proportionally to their accumulated rewards, and start reverse sweeping from the sampled vertices. The sampled vertices are regarded "pseudo terminal states". The accumulated rewards of, for example, a vertex v is defined as
((v) = E)jes(o) G(s))
[S(b)]
where st denotes the state at timestep t in episode G(s{) corresponds to the accumulated rewards from the beginning of episode to timestep f, S(u) == {(s) E Ω == o(s{)} } is the set of states mapped to vertex v, and Ω is the replay buffer. The probability of choosing vertex is defined as
exp(U(v)/x)
P(u) Evev (xp((UU))))))) (U))/)))
where denotes the temperature (we shows that the pseudo terminal state scheme enables TER to outperform the baselines, suggesting that pseudo terminal states approach could be promising alternative of terminal states. We also find that the baselines' performance drop in the non-terminal version of SimpleCrossing-Iiee LavaCrossing-Haare We hypothesize that it is because in the non-terminal version, the agent could accidentally exit the goal after reaching, the learning is harder than the original environment. Moreover, this fact makes learning more challenging in LavaCrossing-Hrr Hard since the goal is near lava and the agent could accidentally hit lava and end up with a large negative reward.
0.01) of a Boltzmann distribution. Figure G.10
and
H DOES BATCH MIXING AID EBU?
To investigate if the performance gap between EBU and TER results from batch mixing, we incor- porate batch mixing with EBU and compare it with TER. We set the batch mixing ratio same as that used TER for every environment. Figure H.11 shows that batch mixing does not improve EBU's performance, which suggests that batch mixing is not critical reason for TER to outperform EBU.
I DOES FILTERING OUT TIMEOUT STATES IMPROVES EBU?
One possibility that TER outperforms EBU the difference in the starting states of reverse replay- ing. TER only starts from the terminal states, while EBU initiates backtracking from both terminal
19

---

Published as a conference paper at ICLR 2022
SimpleCrossing-Hard (nonterminal)
LavaCrossing-Hard (nonterminal)
1.00
0.60
Normalized Return
0.80
0.50
0.60
0,40
0.40
0.30
0.20
0.20
0.00
1.00M
2.00M
1.00M
2.00M
Timestep
Timestep
UER
PER
EBU
TER (pseudo terminal)
Figure G. G.10: Performance in environments without terminal states
LavaCrossing Hard
Sokoban- 6x-622
1.00
Nornalized Return
0.80
0.60
0.60
0.40
0.40
EBU+PER
0.20
0.00
0.00
Timestep
Timestep
Figure H.l.: Incorporating batch mixing with EBU does not aid EBU.
states and timeout states (i.e., the states that trigger resets because of running out of a specified time limit). We then let EBU starts only from the terminal states and compares it again with TER. Fig- 1.12 shows that EBU(no timeout) EBU(no-iimouut) did not mitigate the performance gap, which suggesting the choices of starting states of reverse replaying is not crucial.
Unlock
LavaCrossing Hard
Soloban
Sokoban 6x6
3:80
0.00
3.60
0.50
3.60
3.40
3.40
1.30
3:20
3.20
120
3.30
1.00
2.00
2.H
limsstop
limesteg
linsslop
limsstpp
TER
:BUino_bmmoutt bimeuut)
Figure 1.12: Filtering out timeout states does not help EBU match TER's performance.
J HOW DOES DIMENSION OF AFFECT TER?
Since we rely on random projection to compress the states and stitch common states in different trajectories, it is interesting to see if the choice of dimension affects the performance. Let 2 = Id. Figure J.13 surprisingly shows that TER is insensitive to the dimension of the vectors after the random projection. We found that even small variations in images lead to huge difference after random projection. This might explain why even TER(|Z] = 1) can distinguish each state. Note that do not rely the distances in the space Z to determine the neighbor vertices, it is acceptable that a pair of state and successor state (s, s') are distant in the space Z after random projection.
20

---

Published as a conference paper at ICLR 2022
Unrock
LaveGrossing-Hord
Soloban-6xtB 6xbt22
0.70
Soloban 3xcb-
3.00
3.90
1.30
1.60
3.90
2.40
2.40
1.0
1.0
3.00
Timsstop
Timestop
Timestop
Timestop
TER(
TER ()-)
TERIZ|-16)
Figure J.13: TER insensitive to the choice of dimension of Z.
K COMPARISON WITH STATE-OF-THE-ART MODEL-BASED RL
As van Hasselt et al. (2019) shows that model-free RL using experience replay can be competitive with model-based RL using imaginary data, we are interested whether TER can match or surpass such model-based RL methods. We compare TER with state-of-the-art model-based RI,, Dream- crV2 (Hafner al., 2020). We implemented TER with double DQN as we mentioned in Section 5. I. Figure K.14 shows that TER can match DreamerV2's performance at convergence in out of 4 tasks, albeit DreamerV2 has the luxury of access to imaginary data and more sophisticated models. DreamerV2 learns large environment dynamics model and policy with the latent representations of the learned dynamics model. The policy is trained by imaginary data generated by the dynamics model. Generating imaginary data entails expensive computations and lots of wallclock time. Also, if the environment dynamics model is discontinuous or contact-rich in nature, it is difficult to fit good neural network model for generating imaginary data. In such case, model-free methods can be preferable to model-basee methods.
Additionally, the architecture of DreamerV2 is more complex and harder to tune than TER. TER consists of the following components:
Q-network: Q(s, a) = (o(s.a)
Random projection matrix: (s)) Ms,
where & denotes the weight of the Q-network, while Dreamer comprises the following modules:
Recurrent model: h = f0 4=-1)
Representation model: 4s (0 (2, vx.)
Transition predictor: 2, ~ po (er
Image predictor: 2, p P (ir//e 21)
Reward predictor: Pr ~ ps (Fellhe 21)
Discount predictor: for p hielhe zx)
Actor: â ~ Py (ar (2))
Critic: (&() Ep..ps
"p
For the explanations of each notation, please refer Hafner al. (2019). Each component in dreamer is a neural network and requires tuning the network architecture. As such, we highlight that TER attains similar performance in the selected domains shown in Figure K. 14 with less hyperpa- rameters.
L ADDITIONAL ATARI EXPERIMENTS
further evaluate TER in four games selected from Atari benchmark where these tasks' objectives not to reach terminal states. Figure L.15 shows that TER performs similarly with the baselines in these four games, which suggests that violating the terminal state reaching assumption in the task's 's objective does not impede TER's performance though the agent cannot benefit from TER. Exciting future work is to discover promising states other than terminal states to start to reverse sweeping for general RI. tasks.
21

---

Published as a conference paper at ICLR 2022
Unlock
LaveCrossing--tan flar
Soloban- 6xd-2
Soloban-6x 6xb-3
7.30
1.00
5.60
0.00
1.00
2.00
1.0
1.4
5.90
2.20
1.00
Timestep
Tireettpp
Tinestep
Timestop
DreamerV2
TER
Figure K.14: Comparison between TER and dreamer.
Pong
Kangaroo
Freeway
Venture
20.0
100.0
10.0
6000.0
25.0
80.0
Return
20.0
4000.0
15.0
40.0
-10.0
2000.0
20.0
-20.0
0.0
0.0
0.0
2.0M
6.0M Timestep
10.0M
2.0M
6.0M
10.0M
2.0M
6.0M
10.0M
2.0M
6.0M
10.0M
Timestep
Timestep
Timestep
PER
EBU
DisCor
TER(ours)
Figure L.15: Learning curves in Atari games.
M DISCUSSION OF TER IN CYCLICAL MDPs
We discuss the rationale that TER can work in cyclical MDPs. TER improves the Q-learning update efficiency because we update the Q-values at dependent successors states before the current state's Q-values. However, in cyclical MDPs, some states are inter-dependent (i.e., being predecessor and successor mutually), which renders the correct update order unclear. We argue that under some assumptions, the optimal backup order exists even in cyclical MDPs.
M.1 OPTIMAL UPDATE ORDER OF Q-LEARNING EXISTS IN EPISODIC CYCLICAL MDPS
In cyclical MDPs, there could be inverse action the successor state that moves the agent back to the current state which causes inter-dependency. For example, for a state-action pair (s, a) and corresponding successor state s', there could be an inverse action a' that transitions from s' to s.
Fortunately, the Q-value ((s,a) a) of state-action pair (s, a) is not dependent on the Q-values of all actions the successor state s'. Let us recall the Q-value update equation
Q(s,a) R(s, a, s') max Q(s',
Instead, Q(s, a) depends only on the m Q('', a') of the successor state s'. Let the optimal successor action a" = arg max Q(s', a'). All Q(s, a'), a' * a" does not affect the Q(s, a) update. We just need to ensure that Q(s', a²") is updated before ((s, a). Moreover, for any state s, we care only about the optimal action a* arg max, ((s a), if we are only interested in finding the optimal policy.
As the Q-value at each state-action pair depends only on the max Q-value of the successor state, we are able to define optimal path from any state. Let rollout path w starting from the state be [(s1, a1) ... ($==-,,0=1) #n- 81 = s). where H the path length. The rollout path w given by the optimal policy are then [[s1, at),... (s--1,07-11) where denotes the tth state in the path and af the optimal action at state 8;.
Under the assumption that the objective is to reach some terminal states, each w is acyclic, and merging all w given by the optimal policy forms directed acyclic graph (DAG). This assumption is valid; otherwise, the optimal policy would be trivial policy endlessly going back and forth between two states since there must be a terminal state in episodic RL settings. Besides, the merged graph must be DAG; otherwise, it indicates there is optimal action a" state is inverse action.
22

---

Published as a conference paper at ICLR 2022
For instance, suppose we have two states $ and sg and their corresponding optimal actions d² and a-. Let the transition function be P S x A S. If sB = P(sA. (A), and & = P(sg. ag), then the optimal policy will lead the agent move back and forth between s and A- Given that DAG, the optimal update order is established according to (Bertsekas et al., 2000).
M.2 OPTIMAL UPDATE ORDER HARD TO ORTAIN
Though the optimal backup order for the optimal policy for cyclical MDPs exists, we need the optimal actions at each state for deriving this order. However, the optimal policy unknown before we finish the training. Fortunately, under an admissible assumption that rewards at non-terminal transitions are non-positive, we can exploit the ending state of the optimal policy.
If rewards are non- non-positive at transitions other than terminal ones, the MDP can be viewed as an unweighted graph. Under the assumption that the task's ' objective is to reach some terminal goal states, all the paths given by the optimal policy must end terminal state. Performing reverse BFS from the terminal states gives rise to the shortest path (i.e., the optimal policy) from terminal states all other states, thus recovering the optimal backup order. Note that even though we can infer the optimal paths by the terminal states in these environments, training Q-function by the experience associated with these paths is still preferable. We can only infer the optimal paths from the existing experience, but training Q-function based on these paths can generalize to other unseen states.
Nevertheless, there more than one terminal state in the environment in practice, and we do not know which one is the terminal state that the optimal policy will end at. One approximation is to perform reverse sweep from all the terminal states, as TER does. Though the backup order sequences from these reverse sweeps are not necessarily optimal, we reduce the search space for the optimal backup order to the permutations of the terminal states. Otherwise, the search space for the update order is the permutations of all the possible state-action pairs in the environment.
Note that even though the state-action pairs with non-optimal actions are not needed to be updated (as long their Q-values are initialized small enough), we still perform value backups because their Q-values could become higher than that of the optimal actions due to function approximation. Performing value backups on these state-action pairs makes sure that these Q-values are not over- estimated.
N DISCUSSION OF TER IN NON-GRID LIKE TASKS
TER not restricted grid-like environments. For instance, consider a LunarLander task in Ope- nAI gym (Brockman et al., 2016). The goal is to control the aircraft to land on the planet. Though is not grid-like environment, we still can build graph maintain predecessors of each state in Lunarl for TER.
O DISCUSSION
What if an agent is unlikely to visit the same state twice? TER is likely to degenerate to EBU in this case the graph will end up with multiple independent paths. A quick fix is to aggregate vertices (i.e., Φ(s) from random projection) by their Fuclidean distances. However, the Euclidean distances in the space spanned by randomly projected vectors might not reflect the state similarity with respect to a task. A viable way is to aggregate states based on their features extracted by the value function. For example, suppose we have transitions (51, a1, 82) and (33, 03 S3)s4) and let (ss)) Vi E {1, 2, 3, 4} be the states' features in the value function. When we update ((52, a) for any action a, we need update Q(s1, 01) as well as Q(53, 0s) if ($22) ()()).. Unfortunately, the graph has to be rebuilt over again whenever the Q-function is updated, which leads to expensive computation during online training. An interesting follow-up is to develop a faster online graph update rule that keeps tracking the value function's 's feature space & changes.
How does TER tackle stochastic transition function? each vertex in the graph, can main- tain the visitation counts from each predecessor during exploration in the environment and calculate the visitation probabilities from each predecessor by the visitation counts. Given that probabilities,
23

---

Published as a conference paper at ICLR 2022
sample the predecessors according to their visitation probabilities during reverse BFS. On the other hand, we tested TER in an environment with a stochastic transition function. The results shown in Figure F.9 suggest that stochasticity does not overshadow the advantage of TER.
24


Reviews:
[{"review_id": "zfI_INi1x--", "reviewer": "Reviewer_JmAq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nFirst 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?\n\nSome 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.\n\nRelated 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.\n\nThe text has several issues in terms of precision or correctness. For example:\n\n- “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.\n- “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.\n- “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.\n- “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?\n", "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. ", "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.\n\n", "strength_and_weaknesses": "", "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": {}}, {"review_id": "ZavkspE_Xv", "reviewer": "Reviewer_ANXD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n- The paper's presentation is clear and easy to read\n- The paper's main idea is simple to understand, and seems to improve performance robustly\n- Stating the assumptions of the method is good.\n- Rigorous ablations and analysis are carried out to understand how the method improves on prior work\n\n## Weaknesses\n- 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\n- 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.\n\n## Questions\n- 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?\n- 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.\n", "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.", "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.\n\nEDIT: 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.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Tc0MyHzaU_K", "reviewer": "Reviewer_mMYf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n-------------\n-Finding more sampling efficient ways to sample from a replay buffer is an important avenue of research. \n\n-The authors are clear and open about the details of the implementation.\n\n-There are extensive experiments that shine light on why the method works compared to previous approaches. It also showcases limitations. \n\nWeaknesses\n-------------\n-The experiments are somewhat limited to goal oriented tasks.\n\n-The number of random seeds is a bit low.\n\n\nDetails\n----------\nGiven 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. \n\nThe 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?\n\nRegarding 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?\nThe 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.\n\nRegarding 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.\n\n", "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.", "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.", "strength_and_weaknesses": "", "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": "K5fxk6uC75k", "reviewer": "Reviewer_t7F3", "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": "However, I have the following concerns:\n\nQ1. 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. \n\nQ2. 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.\n\nQ3. 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.\n\nQ4. The authors only consider the construction of undirected graphs, which makes their method not applicable to MDPs where states form directed graphs.\n", "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. ", "summary_of_the_review": "Although the paper is well written, the current version does not convince me to recommend acceptance.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)