Graph Backup: Data Efficient Backup Exploiting Markovian Transitions
Authors: zhengyao jiang
Tianjun Zhang
Robert Kirk
Tim Rocktäschel
Edward Grefenstette
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
graph structure
neuro-symbolic methods
data efficient reinforcement learning

Abstract: The successes of deep Reinforcement Learning (RL) are limited to settings where we have a large stream of online experiences, but applying RL in the data-efficient setting with limited access to online interactions is still challenging. A key to data-efficient RL is good value estimation, but current methods in this space fail to fully utilise the structure of the trajectory data gathered from the environment. In this paper, we treat the transition data of the MDP as a graph, and define a novel backup operator, Graph Backup, which exploits this graph structure for better value estimation. Compared to multi-step backup methods such as $n$-step $Q$-Learning and TD($\lambda$), Graph Backup can perform counterfactual credit assignment and gives stable value estimates for a state regardless of which trajectory the state is sampled from. Our method, when combined with popular off-policy value-based methods, provides improved performance over one-step and multi-step methods on a suite of data-efficient RL benchmarks including MiniGrid, Minatar and Atari100K. We further analyse the reasons for this performance boost through a novel visualisation of the transition graphs of Atari games.

Under review as a conference paper at ICLR 2023
GRAPH BACKUP: DATA EFFICIENT BACKUP EXPLOIT- ING MARKOVIAN TRANSITIONS
Anonymous authors Paper under double-blind review
ABSTRACT
The successes of deep Reinforcement Learning (RL) are limited to settings where we have a large stream of online experiences, but applying RL in the data-efficient setting with limited access to online interactions is still challenging. A key to data-efficient RI. good value estimation, but current methods in this space fail to fully utilise the structure of the trajectory data gathered from the environment. In this paper, we treat the transition data of the MDP as a graph, and define a novel backup operator, Graph Backup, which exploits this graph structure for better value estimation. Compared to multi-step backup methods such as n-step Q Q-Laarning and TD(A), Graph Backup can perform counterfactual credit assignment and gives stable value estimates for a state regardless of which trajectory the state is sampled from. Our method, when combined with popular off-policy value-based methods, provides improved performance over one-step and multi-step methods on a suite of data-efficient RL benchmarks including MiniGrid, Minatar and Atari 100K. We further analyse the reasons for this performance boost through a novel visualisation of the transition graphs of Atari games.
INTRODUCTION
Deep Reinforcement Learning (DRL) methods have achieved super-human performance in a varied range of games (Mnih et al. 2013: Silver et al.) (2016; Berner et al.] [219;) Vinyals et al.) 2019). All of these present a proof of existence for DRL: with large amount of online interaction, trainrd policies can learn to solve problems that have similar properties to real-world
secision-making tasks. However, most real-world tasks such as autonomous driving or financial trading are hard to simulate, and generating new interaction data can be expensive. This makes it crucial to develop data-efficient RL approaches that solve sequential decisionnmaaingg problems with limited online environment interactions.
As many existing DRL algorithms assume access to simulator they don't focus on efficiently using the available data it's always cheaper to simply generate fresh data from the simulator. Data is normally stored in a buffer and only used several times for learning before being discarded. However, there is lots of additional structure in the transition data, and a key insight of our work is to organise the trajectories stored in the buffer as graph (For example see Figure T(a)) which shows a visualisation of the transition graph of the Atari game Frostbite). Our method, Graph Backup, then exploits this transition graph to provide a novel backup operator for bootstrapped value estimation. When estimating the value of state, will combine information from a subgraph rooted the target state, including rewards and value estimates for future states.
When the environment has Markovian transitions and crossovers between trajectories, the construction of this data graph provides several benefits. As discussed in Section 4.2, our method exploits intersecting trajectories to correctly propagate reward to more states, effectively by propagating reward along an imagined trajectory. Further, while existing improvements to one-step backup (as used by Mnih et al. (2015) such as multi-step backup (Moriarty & Mikkuulanen [995] Hessel et al. 2018 Suttonn& & Barto 2018) address the problem of slow reward information propagation (Hernandez Garcia & Sutton 2019). they add variance to the state value estimates as different states have different values estimates depending the trajectory they were sampled from. Our method addresses this issue by grouping states in the transition graph and averaging over outgoing transitions at the value estimation stage.

---

Under review as a conference paper at ICLR 2023
Sokop Backap
Gright Eedlup braathed depttid
(a) Transition Graph
(b) Backup Diagrams
(a) shows the transition graph Frostbite, an Atari game, extracted from a replace buffer of a Graph Backup agent after 100k steps. (b) shows backup diagrams for different backup targets. The circles are states, the blue squares represent the actions that have been observed for the given state node, and orange squares are actions where target net evaluation happened
Figure I:
We propose a specific implementation of Graph Backup, extending Tree Backup (Precup et al. 2000) (Section 4 see Figure ) Our method improves data efficiency and final performance on
MiniGrid Chevalier-Boisvert et al. 2018), Minatar YYong & Tian (019) and Atari100K when using Graph Backup combined with DQN (Mnih et al., 2015) and Data- Efficieff Rainbow (van Hasselt et al. 2019) compared to other backup methods, showing that utilising the graph structure of the trajectory data leads to improved performance in the data-efficient setting (Section 5p. To more fully understand where this gain in performance comes from, we further investigate the graph sparsity of
different environments in relation to the performance of Graph Backup, in part using a novel method to visualise the full set of seen transitions and their graph structure (Section
2 RELATED WORK
The idea of multi-step backup algorithms (e.g. TD(A), n-step TD) dates back to early work in tabular reinforcement learning (Sutton 1988 Sutton & Barto 2018). Two approaches to multi- step targets are n-step methods and eligibility trace methods. The n-step method is natural extension of using one-step target that takes the rewards and value estimations of steps into future into consideration. For example, the n-step SARSA (Rummery Niranjan 1994 (Suttnn & Barto 2018) target for step t is simply the of n-step rewards and the value at timestep + Ri+1 + Re+2 +... + R 1 + V(S++n). Graph Backup is an extension of an n-step backup target, Tree Backup, which will be described in Section
Eligibility trace (Sutton 1988) methods instead estimate the X-return, which is an infinite weighted sum of n-step returns. The advantage of the eligibility trace method is it can be computed in online manner without explicit storage of all the past experiences, while still computing accurate target value estimates. However, in the context of off-policy RI., eligibility traces applied because the use of replay buffer means all past experiences are already stored. In addition, cligibility traces are designed for the case with a linear function approximator, and it's nontrivial to apply them to neural networks. van Hasselt et al. (202I) proposed an extension of the eligibility trace method called expected eligibility traces. Similar to Graph Backup, this allows information propagation across different episodes and thus enables counterfactual credit assignment. However, similar to the original eligibility traces methods, it is better fit for the linear and on-policy case, whereas Graph Backup is designed for the non-linear and off-policy cases.
widely
Since learned model can be treated as distilled replay buffer (van Hasselt et al. 2019), we view model- based reinforcement learning as related to work. Recent examples include Schrittwieser et al. (2020); |essel et al. (2021); Farquhar et al. (2018); Hafner et al. (202 Kaiser (2020bb) Ha & Schmidhuber 20188. These HICTS-based algorithms also share some similaritis with Graph Backup as they also utilise tree-structured search algorithms. However, our work is aimed model-free RL, and so is separate from these works.
Several recent works have also utilised the graph structure of MDP transition data. Zhu et al. 2020)
propose the MDP graph associative memory improve Episodic Reinforcement Learning
2

---

Under review as a conference paper at ICLR 2023
(ERL) methods. This allows counterfactual reward propagation and can improve data efficiency. However, the usage of a data graph in this work is different from the usage in Graph Backup: the graph is used for control and as auxiliary loss, rather than for target value estimation. Their associative memory graph also doesn't t handle stochastic transitions and the return for each trajectory is only based observed return (no bootstraping is used), unlike our work. Topological Experience Replay (Hong et al., [2022] TER) uses the graph structure of the data in RL for better replay buffer sampling. TER uses the graph structure decide which states should be sampled from the replay buffer during learning, by implementing a sampling mechanism that samples transitions closer to the goal first. This work is orthogonal (and possibly complementary) to ours, as TER is a replacement for uniform or prioritized sampling from replay buffer while Graph Backup is replacement for one-step or multistep backup for value estimation.
3 PRELIMINARIES: ONE-STEP AND MULTI-STEP BACKUP
Given an MDP M we denote A as the action space; S to be state space; R C IR to be reward space: and 0 E A. 8, 8 are used to denote the specific actions and states respectively observed at step t. We denote trajectory of states, actions and rewards as T = ($1, 01 1 $2, 02 r2,...).
For transition (st; (ee Tt; 81+-1) 1) the loss function of DQN methods is defined the mean square erro between the predicted g-value and the backup target GeT for (#c: aq):
L(O st az)
(go(s), ar) G
where qo represents the online network parameterized by O. The backup target G is estimation of the optimal Q-value q (s,, at). Vanilla DQN uses one-step bootstrapped backup, which makes gradient descent an analogue to the update of tabular Q-learning:
def G G1411 T++1 +- max go a')
where 8' are the parameters of the target network, which is standard in DQN.
The one-step target makes the propagation of the reward information to previous states slow, which is amplified by the use of a separate frozen target network. This motivates the use of more sample- efficient multi-step targets in DQN (Hessel et al. 2018 Herrandez-Carcia & Sutton 2019).
A widely used multi-step backup algorithm is n-step Q-Learning (n-step-Q) Q) (Hessel et al. 2018 Silver al. 2017). This method sums the rewards in next n steps, together with the maximum g value at step y::
def M1+1 + TT+42 +... + 7" max gor (St+n, d').
a'
n-step-Q exploits the chain structure of the trajectories with little computational cost but cost of biased target estimation. The distribution of the sum of the rewards r=+1 + YT++2 + ... + --"'1rt Titn conditioned the behaviour policy μ which generates the data. This means that in off-policy setting the estimated target value can be biased towards the value of the behaviour policy.
Another off-policy multi-step target is Tree Backup (Precup al., 2000). Tree Backup is designed for general-purpose off-policy evaluation, meaning it aims to estimate the value of any target policy ı by observing the behaviour policy p. When the target policy is the optimal policy given by go. Tree Backup recursively applies one-step-( backup to the trajectory, bootstrapping with the target value network when the input action a isn't 't that taken the trajectory (at):
def [r41 + maxa Gu' G(41:44
ift n2 a=aa otherwise.
G Guttn
(4)
gg
Despite what its name suggests, Tree Backup does not expand tree of states and transitions, and so still only leverages the chain structure of trajectories. The name is because the trajectory has leaves corresponding to the actions that the backup diagram of the 3-step Tree Backup, where yellow squares are these leaf actions.
selected in the current trajectory. In Figure (7c) we show
Or sometimes the Huber Loss Huher 1992)
3

---

Under review as a conference paper at ICLR 2023
4
GRAPH BACKUP
In this section we introduce a new graph-structured backup operator, Graph Backup, extending the multi-step method Tree Backup. Graph Backup allows counterfactual reward propagation and variance reduction while also having the benefits of multi-step backup.
4.1 INTRODUCING GRAPH BACKUP
We propose the Graph Backup operator that propagates temporal differences across the whole data graph rather than single trajectory. The differences between one-step, multi-step, tree and Graph backup are illustrated in Figure [(c) We want backup method that can work with stochastic transitions, which means single state-action pair can lead to different states. This means it's obvious how to perform recursive backups to the next state, as there could be multiple next states. We estimate the transition probability to each next state using visitation counts, and use the estimated transition probabilities to compute the empirical mean over all possible state value estimates weighted by the likelihood of transitioning to that state. This easy to calculate efficiently and provides strong results as seen in Section
Denoting the set of all seen transitions be SSXAXRxS counter function f T + N+ maps each transition T = (s, a, 8') to its frequency S(T). Notabely, this counter function also plays 2 roles 1) the adjacency list the graph; 2) to weight transitions when the same action leads to different future states. The Graph Backup target for a state-action pair (s, a) is then the average of recursive one-step backup of all outgoing transitions. Similar to Tree Backup, if the (s, a) has not been seen,
the target is estimated directly by the target network. Define Txaa def {(8, â, 8,8') ) the set of all (&, â. i; 8) tuples starting with Extending Tree Backup, we can then define the Graph Backup (GB) value estimate as
T 8, a},
G. def a(*.a) ΣTET... S(T) ( T(d|3))7) (s0 a)otherwise.
if a) >
(5)
where a(s,a) = Erer., S(T) is the normaliser, π is the target policy and go is the tar- get network. In the case where target policy always chooses the action with optimal Q value (alss) = [(argmax, Ga¹ = a), the formula can be simplified into:
G def c(s.a) ETET,,. S(T) ( yaxx C%y) qo (0, a) otherwise.
if >0
(6)
This is often the case since our implementations are based on DQN and we are interested in the optimal Q-value. In this paper Graph Backup refers to the simplified version in Equation (6). On high level, Graph Backup does dynamics programming Q evaluations on a Empirical MDP, where all the Q values for untried state-action pairs are initialized by Q network.
Our Graph Backup implementation extends Tree Backup. However, there could be other imple- mentations which extend other multi-step methods, such as n-step-Q backup the n-step ver- sion (Hernandez- Caraanddez--ariiaaaa & Sutton 2019) of Retrace (Munos et al.) 2016). Appendix we present variation of Graph Backup that extends ne-tep-( backup.
Note that in Equations 66, and (8), the graph structure does not appear explicitly. This is because it's easier to mathematically formalise these backup operators using transition counts; from an implementation perspective building and maintaining the data graph is the most efficient way of calculating these target value estimates. To better provide intuition for Graph Backup, in Appendix C we explicitly describe the data graph generated from an MDP and link that to Equation
(6). The data graph contains the information for calculating and sampling from Te. Te.as c(s, a), c(s) and f(T).
4.2 ADVANTAGES OF GRAPH BACKUP
In Figure 2 explain conceptually how Graph Backup brings benefits value estimation and thus the learning the agent. We also present a more empirical analysis in Appendix Figure 7 Assuming the value estimates of all the states are initialised 0, the one-step backup update
4

---

Under review as a conference paper at ICLR 2023
the value of only state. The multi-step backup methods can further propagate the reward to the whole trajectory that leads to the reaching of the goal However, Graph Backup goes beyond that and propagates rewards to the states of another trajectory (the dashed line). This feature of counterfactual reward propagation can significantly benefit the credit assignment of sparse reward tasks: During the exploration of sparse-reward environment, policies usually generate large number of trajectories that do not reach the goal, and while multi-step methods cannot efficiently leverage those transitions, Graph Backup can reuse them by propagating rewards from the crossovers with other successful trajectories.
The second row of Figure 2 shows another advantage of Graph Backup: reducing the variance of the value estimate. suep backup in this case will assign different value estimates for the same state depending on the trajectory the state is sampled from (as it will appear multiple times in the replay buffer). This brings extra noise to the value estimate which can be harmful to learning In Figure [ we showed a simple case in MiniGrid where this target value noise can constantly disturb the convergence of DQN. Graph Backup removes this source of variance by ensuring that the same state always has the same value estimate regardless of which trajectory it's sampled from by calculating the value estimate from the underlying data graph. In addition, in stochastic environments Graph Backup reduces variance by averaging over different next states from the same state-action pair.
Counsoriactual Reward Propacation
One-step Beck.p
Mudi stop Sackup
Craph Deckup
Vorianoe
Cne sap Backsp
Mutritep
Graph Backup
Trijccories es
Tenwiratt sooes
Postive este
estttieestinatt
Rerent submatoi for the simestate
Avarued mate
Figure 2: Benefits of Graph Backup
4.3 LIMITING EXPANSION OF THE GRAPHI
naive implementation of Graph Backup would follow the definition exactly and do an exhaustive recursive expansion of the graph. However, the computational cost of doing can quickly blow up with the size of the replay data Therefore, similar to the n-step backup methods, we need to limit recursive calls. For Graph Backup, this means expanding smaller local graph from the source state, using the target network for value estimation when reaching expansion limits. In our work, the expansion of the local data graph has both a breadth limit b and a depth limit d. When the breadth limit is hit ((T opposed to expanding all transitions. the depth limit is hit < n) the expansion of the graph will be terminated (so the second case in Equations (6) and 7 is taken).
b). we will sample b transitions from T,a according to their frequency f. as
The pseudocode for local graph expansion is shown in Algorithm 2 Figure 7(c) also illustrates examples of limited expansion for Graph Backup, where faded nodes are clipped away due to hitting the limit.
"In this case, both Tree Backup and re-seep- backup produce the estimation shown in the example tasks.
II the Figure 2 the noise comes from different rewards at the end of the trajectories.
"In fact, if there loops the graph, the situation can be even worse as the algorithm may never converge.
5

---

Under review as a conference paper at ICLR 2023
In our work, make sure the expansion will reach d steps in order to better align with multi-step methods. This makes sure the algorithm will reduce to Tree Backup gracefully when there are no crossovers between the trajectories. It also allows more principled comparison between Tree Backup and Graph Backup. For b = Graph Backup will do a similar job as d-step Tree Backup, and increasing b will gradually make the Graph Backup leverage more structure from the transition graph.
4.4 INTEGRATION OF OTHER RAINBOW COMPONENTS
To demonstrate that Graph Backup improves data efficiency in a realistic state-of-the-art algorithm, we integrate Graph Backup inside Rainbow (Hessel et al. 2018). As a replacement for n-step-Q backup, Graph Backup is orthogonal to all other ingredients. While some components such as prioritized experience replay(PER) (Schaul al. 20166, noisy networks (Fortunato et al. (2018) and duelling network architectures (Wang et al. 2016) can be plugged in seamlessly, others require more care, which we describe here.
Combining double DQN (van Hasselt et al. 2016) with Tree Backup and Graph Backup is quite straightforward. Double DQN uses an online network instead of target network specify the optimal policy in the bellman update, so that max, qor(s (8, a) = Qø (s, argmax, l (8, a)) becomes qe (s, argmax, go go(s, a)) in one-step or n-Step-Q backup. For Tree Backup and Graph Backup, can take the same approach for every expanded state.
Distributional RL (Bellemare al. 2017), specifically C51, attempts to model the whole distribution of the state-action value rather than the expectation, using a distributional version of the bellman update (namely, one-step backup) when applied in the DQN setting. C51 divides the support of the value into discrete bins, called atoms, and the network then outputs categorical probabilities over the atoms. In the distributional bellman update, the vanilla bellman update applied to each atom, and the probability of the atom is distributed to the immediate neighbours of the target value. The loss the KI. divergence between the target and predicted value distribution rather than the mean squared error. In order to combine C51 and Tree Backup or Graph Backup, we apply the distributional bellman update in every state node.
Algorithm Double Distributional Graph Backup
Input: source state Sspurce: source action Asouree frequency mapping f : T - N+, list of states in the subgraph L, atoms 20, 21, -.. 2 1, online network p(::- and target network - (0")
1: Set Sexpandod be the set containing all the states in list L
2: Initialize the target values G3 G (8, a), Vs E Sexpamied, a E A
3: for a) in 4max, 4max-l,..... /1 do
4: a" argmax, 2, (s,
5: m,(s. a) =0, i E 10,1.... 1,...,
6: for j E 0, 1,.,, N
do
7:
for / = (s, ú, r, E T do
2/ + [r + 725 Vaex
8:
9:
bj + (z) V/
10:
+ [by], 0 + [b,]
my(s, a) t- mi(s,a) a) + ((...n)))
6(s.0) Py (z (Ie+1, )u b,)
12:
my (s, - as + [(s.a.r,s))
cls,a) pj (Ix+1, a" ab) -
13:
end for
14: end for
15:
end for
16: return mS Asource)
( Agourez)
In Algorithm I we combine double and distributional RL with Graph Backup given the subgraph state list calculated by Algorithm Blue lines show the changes introduced by Graph Backup.

---

Under review as a conference paper at ICLR 2023
MiniGind
MinAtar
AtarTT
Atar1Boo
stada
(PS))
2002
50.00
00:.00
190000
200
0.000
11:00
2000
00.000
00000
1800
2.003
19:00
18:00
st0p
x0ep
stap
stap
Figure 3: Summary of training curve for Minigrid, Minatar and Atari100K. For Atari 100K, show both the mean and IQM of the human- scores.
Table 1: Numeric summary of the performance. IQM stands for interquartile mean 202T.
Agarwal et al.
ane-4top
10-top-Q
Tice
Grapph
MinGGrd-QQM
0.74
MiniGrid-mman
MiniGrit-mmdian
0.0
0.0
MinAAtrl00K-10 IQM
1.90
1.72
3.20
8.46
MisAnel00K 100K-menn
3.07
3.76
6.76
11.83
MinAtar L0O median
2,07
1.56
3.33
4,95
Amai NIK-IQM
18.85
16.55
26.76
34.25
Atuil O0K
32.8
28.72
43.62
50.49
Ama median
30.07
4.5 ASSUMPTIONS
The effectiveness of Graph Backup relies on two assumptions about the environment: (1) the transition function of the environment Markovian, and (2) there are crossovers between state trajectories. We show in Section 5 that-perhapps high dimensional environments (Atari100 from pixel input) for Graph Backup differentiate itself from Tree Backup in statistically significant manner. As such, these restrictions not strict as may appear, and we further discuss how they can be relaxed Section 7
connter-inuitively--the these assumptions hold frequently enough in
EXPERIMENTS
In order to test whether Graph Backup can bring benefits to the data efficiency of DRL agent, we conduct experiments on singleton-MiniGrid, MinAtar and Atari100K. These tasks have an increasingly sparse transition graph so that we can see how many crossovers are needed for Graph Backup to bring significant performance improvements. The baseline agent for MiniGrid and MinAtar is DQN (Mnih et al.] 2015) and for Atari is
Rainbow (van Hasselt et al. 2019). The average training curves of the different backup methods are shown in Figure 3 where each algorithm for random seeds. The performance metric for Atari in the plot is the mean and median of human-normalised scores (%). The final performance for each task and method can be found in Table [ where we also include both mean and median metrics. The full results of each individual task are shown in Table 3 in Appendix.
MiniGrid We first compare the methods in 5 singleton MiniGrid tasks: Empty8x8, DoorKey6x6. KeyCoriidoS3RI. SimpleCrosingS9N22 and LavaCrossingS9N2. Every single run (out 5) has different but fixed random seed within the whole training process. We set the environment to be fully observable so that the transitions are Markovian. The overall number of possible states is small and the data graph is thus quite dense. The reward of MiniGrid is only given at the end of the episode, which makes credit assignment a critical problem. Among the tasks, one-step backup and Tree Backup only managed to converge within 1e5 steps for the easiest empty room task. For other tasks with more complex navigation (SimpleCrossing and LavaCrossing) and interaction with objects (DoorKey and KeyCorridor), only the Graph Backup converged this low data regime.
7

---

Under review as a conference paper at ICLR 2023
Table 2: Minatar results after 1M steps of training. standard error.
Values for each individual tasks are mean
one-step
n--tep--
Tree
Graph
Minatar-seaquest
5.98+0.97
6.93+0.72
6.57=0.43
5.87+0.86
Minatar-breakoul
10.60+1.02
9.28+1.48
7.05+1.33
14.38+ 1.38
Minatar-asterie
14.90+3..6
11.25=1.84
7.68#1.81
8.02+1.93
Minntar-freeway
39.93+ 1.77
6.00+2.88
18.85 10
40.95+
Mlintta-space_inaadeer
37.53+5.26
26.07+1.94
33.85+2.29
44.40+4.83
IQM
15.50
9.83
8.72
16.12
mcan
21.79
11.91
14.80
22.72
median
14.90
9.28
7.68
14.38
Minatar 100K steps. We perform experiments on Minatar. Minatar is a collection of miniature Atari games with symbolic representation of the objects. The game state is fully specified by the observation of a 10 by 10 image, where each pixel corresponds to an object. We set the overall number of interactions to be 100,000, inspired by the Atari benchmark (Kaiser et al.] (020b). We can see in Figure that Graph Backup outperforms Tree Backup, n-step-Q backup and one-step backup in terms of mean scores and interquartile mean (IQM), in the data-efficient setting.
Atari100K In order to test if Graph Backup be applied tasks with pixel observations, test it in Atari100K, As suggested by its name, Atari100K limits the number of interactions of Atari games 100,000, which is equivalent 2 hours of game-play in Atari. Since the human performance scores reported by Mnih et al. (2013) are also from human experts after 2 hours of game-play, Atari 100K is considered as test-bed for human-level data-efficient learning. We follow the standard frame processing protocol used by Rainbow Hessel et al. (2018) without any other downsampling. The frame is processed into an by 84 greyscale image and the observation is a stack of 4 previous frames, which leads to very sparse transition graphs The baseline we chose for Atari100K: is data-efficient Rainbow yan Hasselt et al. (2019), which is a variation Rainbow that is optimized particularly for Atari100K, Consistent with the results in MiniGrid and MinAtar, Graph Backup performs better than one-step and multi-step methods. The results here show: 1) Graph Backup is robust in terms of bringing orthogonal improvements over other DQN improvements. 2) Graph Backup works for nigh-dimensional, pixel- based tasks that have sparse transition graphs.
Minatar 1M steps In order to see the asymptotic performance of Graph Backup, in Table we also show the results for million steps of training with hyper-parameters still kept the data-efficient setting. Interestingly, while Graph Backup still preserves strong advantage over n-step-Q and Tree Backup in terms of aggregated metrics, one-step backup shows comparable performance against Graph Backup with more training. Looking at individual tasks, we find out Tree Backup shows inferior performance compared one-step backup on Breakout, Asterix and Freeway. From practical perspective, Minatar 1M results show Graph Backup achieves consistent performance in multiple scenarios while the baselines (one-step backup and Tree Backup) only show their advantage in settings with specific data availability.
ANALYSIS
Atari Transition Graphs. Here we study why Graph Backup can bring benefits to Atari games. Atari games have pixel-based observations, which have 255(210+180+3) combinations if each pixel can take any value independently from other pixels. The first question is then: are there crossovers in just 100K transitions? To analyse the graph density quantitatively, we propose to measure the novel state ratio. The novel state ratio is the ratio between the amount of non-duplicated (i.e. unique) states and the amount of all states that the agent has seen. The novel state ratio will be if there are no overlapping states in the transition graph, in which case Graph Backup reduces to Tree Backup. The average novel state ratio of Atari is 0.927, which means the graphs are usually quite sparse (The 0.006/0.298 respectively). However, if assume
average novel state ratios of MiniGrid/Minntar
SSince the agent interacts with the environment every 4 frames, such preprocessing still assumes the transition be Markovian.
8

---

Under review as a conference paper at ICLR 2023
(a) Alien
(b) Freeway
(c) Asterix
(d) RoadRunner
Figure 4: Transition graphs of selected Atari100K games, with data collected by one-step DQN agent. As there are too many state nodes, we did not paint nodes directly but rather preserve edges (transitions), where circles represent self-loop transitions.
that duplicated states happen independently, this means that in 53% of the backup updates, there will be a crossover on the next steps, which means the Graph Backup will give a different value estimate to multi-step methods more than half the time.
However, the crossovers are not distributed uniformly on the transitions graph. In order to investigate the topology of the graph, visualize the exact graph structure of the whole transition graph. In Figure 4 we show four representative transition graphs and leave the others to Figure S in the Appendix. We apply radial layouts proposed by Wills 1999). which scales well with the number of nodes and aligns well with the transition structure of most of the games, where the central point corresponds to the start of the game. Many transition graphs of Atari100k games show interesting crossover structures that can be leveraged by Graph Backup. For example, the transition graph of Freeway forms a windmill-like pattern, where each blade corresponds a group of trajectories that have connections within the group but between groups. There are also some tasks (e.g. Alien) where crossovers mostly happen the starting stage of the game.
Explaining Crossovers. By comparing the transition graphs and the pixel observations, we can provide two explanations for the existence of the trajectory crossovers Atari games. The first factor that there is low number of degrees of freedom for the objects and especially for the agent avatar in many of these games. For most of the Atari games, the agent can only move on a 2D plane, which partially alleviates the curse of dimensionality since we only need two dimensions to specify the position of the agent. A second important factor is that Atari games always have a fixed initial state. Although follow prior work (Hessel et al., 2018) to add random number of no-ops after the start of the game, the initial observations the agent sees will still be quite similar, and this creates crossovers at the beginning of the episode (the centre of the plot, for example for Alien in Figure
In light of these characteristics, we recommend practitioners apply Graph Backup with exact state matching tasks that either (1) have few degrees of freedom, (2) have discrete state space, or (3) are highly repetitive with minimal noise. There are many real-world tasks that have similar properties, such as any 2D navigation (e.g. household cleaning robots), power management and manufacturing in assembly lines.
7 LIMITATIONS AND FUTURE EXTENSIONS
The high-level insight of Graph Backup is to treat all the transition data as a collective entity rather than independent trajectories, and exploit its (graphical) structure for sake of efficient learning. This work shows simple implementation of this idea, by building the graph with exact state matching. While there are already a large class of tasks that have crossovers, we expect in future to extend Graph Backup to cover even more challenging tasks. For example. with learned human-craftee discrete representation of the true state (van den Oord et al.] 2017: Hu et al., 2017] Hafner et al.
2021a| Kaiser et al. 2020a) with a similarity kernel measuring distance between states, Graph Backup might be able to tackle continuous control or tasks with partial observability.

---

Under review as a conference paper at ICLR 2023
8 REPRODUCIBILITY STATEMENT
The code to reproduce all the experiment results are available in the supplementary materials. README includes guides to setup and environment and commands (with hyperparameters) to run the experiments. Experiments for all environments can be on CPUs but (a single) GPU can speed up for Atari tasks. Besides codes. pseudo-code in Algorithmm2 and Algorithm| and hyperparameters described in Appendix D can also be helpful reproduce the results if readers are interested in implementing by themselves.
REFERENCES
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C. Courville, and Mare G. Belle- mare. Deep reinforcement learning at the edge of the statistical precipice. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Perey Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34; Annuul Conference Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 29304 29320, 2021. URL wttpttpppppppppeeepeeeteeeeeeeee E544ccccccc1145501111 742 Aastee--bsstttccc .tml
www.inuuripp.. cttccc//ppaa/ pc/pappr///e//ee//pe/peeeeeeaeee 2021/hasllss
Mare G. Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforce- ment learning. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th Interna- tional Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 449 458. PMLR, 2017. URL h.mmm
htttp://proceedlnng www.diiinnsm........mmmmm.ee.eee mlr. wwwp:/pppssseeeeeeeeeeeee
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman. Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota with large scale deep reinforcement learning. CoRR, abs/1912.066800 2019. URL.ttp:: /ttt:::///axxivv/ org/ abs 9912 06680
Maxime Chevalier- Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https:
com/ max wwtp//aximmmiiiimmmm/mmmmmm ht///yymmmmi minigiin 2018.
Gregory Farquhar, Tim Rocktäschel, Maximilian Igl, and Shimon Whiteson. Treeqn and atreec: Differentiable tree-structured models for deep reinforcement learning. In 6th International Confer- ence on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April May 2018, Conference Track Proceedings. OpenReview.net, 2018. URL Eorum?i --d-iid-i H1 61d
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Osband, Alex Graves, Volodymyr Mnih, Rémi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htttp:://ppenreviiieeeee/ net/ forum?id ΣYWИCPКAW
David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In Samy Ben- gio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò DisacBianchi, and Roman Gar- nett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 2018. URL httpttttt//ppceeeeeeeeeeee hww.diiinnnnnnnunnnoooooe.muu CC wwtpccpppppppeeceeccccccc /20//2111 8/ /hahh/ Abst oat. html
22e aaba
Danijar Hafner, Timothy P. Lillicrap. Mohammad Norouzi, and Jimmy Ba. Mastering atari with
discrete world models. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021a.
net/forum http://oowwmmmmooooooooaawwwyaa/
10

---

Under review as a conference paper at ICLR 2023
Danijar Hafner, Timothy P. Lillicrap. Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021b. URL [RLLittpp:////eeeeevies
net/ d= 0 d
J. Fernando Herrandez-Garciia and Richard S. Sutton. Understanding multi-step deep reinforcement learning: A systematic study of the DQN target. CoRR, 0bs//100..0550,, 2019. URL http:
//a //a.xi..rg/aabs.......... wwt.o///g/bbbs/1...11
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.). Proceedings of the Thirty-Secondl AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA,
February 2-7, 2018, pp. 3215-3222. AAAI Press, 2018. URL https:/ /wwww www.a.aiar.........a............
ocss/nnees php BAAIIAAAIAAA CAAAI/AAAII htt.A/AAAAAA/aaa//veraeee http:/ppppppp//e/eppppppp 17204
Mattco Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent Sifre, Theo- phane Weber, David Silver, and Hado van Hasselt. Muesli: Combining improvements in policy optimization. arXiv preprint arXiv: (oXiv:2/04006/59) 2021.
Zhang-Wei Hong, Tao Chen, Yen-Chen Lin, Joni Pajarinen, and Pulkit Agrawal. Topological experience replay. CoRR, abs/2203. 2022. doi: 10.48500aXXi2223..55544 URL https //doi.org///0 18550//aaX0
Weihua Hu, Takeru Miyato, Seiya Tokui, Eicchi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. In Doina Pre- cup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1558-1567. PMLR, 2017, URL htttp://proceedings mlr aress/v70/hin 7b. htm.
Peter J Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pp. 492-518. Springer, 1992.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learning for atari. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a. URL https: htttps::/openreview..ee.
Forum Parummid-Shle -wt::iiisxxx--- S1xcp JHEDB
Lukasz Kaiser, Mohammad Bahaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learning for atari. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26 30-30, 2020. OpenReview.net, 2020b. URL https: httt:s://openreveew..ee.
Forum? 1d= 1 DE
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep re- doi: 10.1038/nature142
inforcement learning. Nat., 518(7540):529 533, 2015.
URL
https://doi.ors http///..110///ttreeeee..
David E. Moriarty and Risto Miikkulainen. Efficient learning from delayed rewards through symbiotic evolution. In Armand Prieditis and Stuart Russell (eds.), Machine Learning. Proceedings of the Tweifth International Conference Machine Learning, Tahoe City, California, USA, July 9-12, 1995, pp. 396 404. Morgan Kaufmann, 1995. doi: 11..1111/197.1.11111111111111 18877788---5888 577-556007777-5000 https: //do:
URL

---

Under review as a conference paper at ICLR 2023
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare G. Bellemare. Safe and efficient off- policy reinforcement learning. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Anmual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 1046- 1054, 2016. A
www.aeediinnnnuunnnne..eeee wwtpc//pppee/.1////// Abstract html
Doina Precup, Richard S. Sutton, and Satinder P. Singh. Eligibility traces for off-policy policy evaluation. In Pat Langley (ed.), Proceedings of the Seventeenth International Conference Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29 - July 2, 2000, pp. 759-766. Morgan Kaufmann, 2000.
Gavin A Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems, vol- ume 37. Citeseer, 1994.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL org/ htsp//bssl11111 Tttp:///arvv..rrr//////........ 05952
Julian Schrittweserr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):044-699 2020.
Max Schwarzer, Ankesh Anand, Rishab Goel, R. Devon Hjelm, Aaron C. Courville, and Philip Bachman. Data-efficient reinforcement learning with self- ceff-predictive representations. In 9th Interna- tional Conference on Learning Represennaations ICLR 2021. Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
www.:/ttfoommmmmo furum? www.:rrrmmmmmuuuuuguuooEe.. dFuCgf
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panncershelvam,, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nat. 529(7587):484 489, 2016. doi: 10.1/ur/a 1661. URL httpps://dos http:/..rrgr...0 w0t.///t/neeeee 6961
David Silver, Thomas Hubert, Julian Schrittwieser, Toannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.018/1 2017.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Ahmed Touati, Pierre-Luc Bacon, Doina Precup, and Pascal Vincent. Convergent TREE BACKUP and RETRACE with function approximation. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmäässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 4962 4971. PMLR, 2018. URL htt.tttt:///// httt::::pppoccecc
ngs ml www.prresssv... saress/v80/touat
html
Aäron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems
30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6306 6315, 2017.
www.:eewwweeeee..n..s.ee...... /c/ /201 9 252pr/7007775s7134111aaaaaa22262
.htll
12

---

Under review as a conference paper at ICLR 2023
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Dale Schuurmans and Michael Wellman (eds.), Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. February 12-17. 2016. Phoenix, Arizona, USA, Pp. 2094-2100. AAAI Press, 2016. htttht//t///w.. aaai org/oca//// ocs index. p AAAT (AAT16/paper// httppperr/iew///2//2
Hado van Hasselt, Matteo Hessel, and John Aslanides. When to use parametric models in reinforcement learning? In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Buc, Emily Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference
Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 14322-14333, 2019, URL
neurips.. wttperrppssccpppppe/////. wttpppppee/l.///eeeeepeeeeeeeeee 20a20099hhh///// html
Hado van Hasselt, Sephora Madjiheurem, Matteo Hessel, David Silver, André Barreto, and Diana
Borsa. Expected eligibility traces. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI
2021, Thirty- Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 9997-10005, AAAI Press, 2021. URL https:://jss.... aaai
www.://...a.ttt....eeeaaaeeaeeee org/index.ro http://www...aaaaaaaaaaaaa/aaa//
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom Le Paine, Çaglar Gülçehre, Ziyu Wang. Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nat. 575(7782): 350-354, 2019. doi: 10. 10.1038//41186-019-111 641586-019-1724--
URL https: http:///oooooo///..1/1////
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Mare Lanctot, and Nando de Freitas. Ducling network architectures for deep reinforcement learning. In Maria-Florina Balcan and Kilian Q Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning. ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1995-2003. 20L.............m JMLR.org, 2016. URL httt:::/prrceedinng w wtwppp/s////wwwann........
Graham J, Wills. Nicheworks-iittractivv visualization of very large graphs. Journal of Compu- tational and Graphical Statistics, 8(2): 1999. doi: 10. 1080/106 18888660.999 19...19999.44888 URL
1tw.111101111111 1999. 00399.10440 10474810
Kenny Young and Tian Tian. Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint arXiv:1903.033 03106, 2019.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https //openreiew. net/ fest/forum220 JXXBYD
13

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Local Graph Expansion
Input: source state Scurce, source action Asouree depth limit d. breath limit b, frequency mapping
f: T:T+M N+
1: Initialize the set containing states the boundary of expansion Snew <- {Soouce)
2: Initialize the list of expanded state-action pairs L. denoting the last element in the list to be mmax
3: for = 0 to d do
4: Find all transitions on boundary Trew <- {tlvt= (s, a, r, 8') E TT&EE Snew)
5: Sample b transitions from Tnew with p(t) x f(t), getting T Tpramed {1i, 12,,....i 1bb
6: Append state-action pairs to list L, {mmax+), 2 ..... = {(s, ( E T
7: Update boundary states Snew { (s)), a,s,,,,, r,), Tpmand)
8: end for
9: return L
A OTHER EMPIRICAL FINDINGS
In general, the experiments in three different settings shows Graph Backup consistently brings improvements over multi-step methods. Besides that, also find that the improvements of n-step-Q backup over one-step backup are actually quite limited in the data-efficient setting, whereas Tree Backup performs significantly better than n-step-( backup. This can be explained by the off-policy nature of Tree Backup, as it can bring the benefits of multi-step reward propagation without biasing the value estimation. In data-efficient setting, the flaw of n-step-Q is amplified as the learning relies more on historical rather than freshly sampled data. Interestingly. Tree Backup has not received lot of attention DRL community. [Hernanezz-Gariia mountain car experiment which shows n-step-Q performs best among multiple multi-step methods, including Tree Backup. (Touati et al. 2018) points out the instability Tree Backup when combined with functional approximation, both with theoretical analysis and empirically evaluation some constructed counter-example MDPs. However, our experiments on a larger scale and more diverse set of tasks show Tree Backup has superior sample efficiency when combined with modern DRL method.
Sutton (209)) tested Tree Backup in a toy
B STABLE VALUE ESTIMATE
Graph backup can integrate information from a subgraph, yielding a more accurate and stable value estimation. On the other hand, the nested max operators might lead overestimation of the value. Here we try to analyse the value estimation given by different backup operators.
We collect 5000 transitions with random walks in MiniGrid 5x5 Empty Room environment, and have the agents to learn the q" from this static dataset. In Figure 5 we show the mean and standard deviation of latest 10 estimates of the same state-action pairs. Both mean and standard deviation are averaged over different state-action pairs. The value estimate of Graph Backup quickly stabilize after few hundred optimization iterations as the mean value converged and the standard deviation reduce to near O. However, all other backup methods keep giving varied estimate for the exact same states leading to a higher standard deviation and fluctuating mean. terms of ever-estimation, the graph backup does give a slightly higher estimate at first (the little bump in the curve), however, it quickly recovers to a stable value.
C DATA GRAPH DEFINITION
An MDP data graph a bipartite multigraph (Seeen N, Eout, Ein), where Swen S is the set of seen state nodes, N C Sween x A is the set of (state conditioned) action nodes, Enu is a multiset of edges pointing from state nodes to action nodes and &n is a multiset of weight-weighted edges pointing from action nodes to state nodes. A state node can point multiple action nodes because multiple actions might be tried, and the action nodes can point to multiple state nodes because of the stochastic dynamics. When
transition (s, a, r, s') is observed, edge (s, (s, a)) will be added to En and ((s, a). r, ss) will be added to Emm- A visual example of this data graph can be seen in the Graph Backup diagram in Figure 7cc) with tried (blue) action nodes only.
14

---

Under review as a conference paper at ICLR 2023
Mean
Standard Deviation
1.0
0.40
une steg
n-step-Q
value estimate mean
value estimate std
0.35
tree
0.8
0.30
graph
0.25
0.6
0.20
0.4
0.15
one-step tree
0.2
0.05
graph
500
1000
1500
2000
500
1000
2000 1500
step
step
Figure 5: Mean and standard deviation of the value estimate for the same state-action pairs for fixed dataset collected in MiniGrid Empty Room. The x-axis is the number of optimization steps.
Relating this data graph to Equation 6 we can see c(s. a) is the number of (s, (s, a)) edges in en and f((s, a, r, s')) is the number of ((s,a), s') edges Eost.
D DETAILS ABOUT EXPERIMENT SETUP
The Graph Backup and multi-step backup both use a depth limit of 5 for MiniGrid and MinAtar, and 10 for Atari100K. The breath limit for GB-limited is 50 for MiniGrid, 20 for Minatar and 10 for Atari100K,
For MiniGrid and MinAtar, all backup methods based the vanilla DQN. The q network has 2 convolutions layers and dense layers, and we follow the papaaeerraeseers of Rainbow (Hessll al. 2018) with target network update frequency 8000. e-greedy exploration with e 0.02. The learning rate is 0.001 for MiniGrid, 0,000065 for Minatar. The discounting factor is 0.95 for MiniGrid and 0.99 for Minatar. The replay frequency for MiniGrid, and for Minatar. Since we tested the algorithm in data-efficient setting, the size of the replay buffer is set to be equal to the overall training steps.
As for Atari 100K, our baselines and Graph Backup agents are based on Data-Efficient Rainbow (van Hasselt et al. 2019) with the same hyper-parameters of [Schwarzer al. (021).
E GRAPH SPARSITY
Across different tasks, we can see a correlation between the density of the transition graph and the improvement of Graph Backup. For MiniGrid tasks where the possible number of states is limited, the Graph Backup brings much larger improvements, whereas, for MinAtar and Atari, the graph is sparse as there are multiple other objects besides the agent that can move the game world. To analyse the graph density qualitatively, we propose the metric of the novel state ratio. The novel state ratio is the ratio between the number of non-duplicated states and the number of all states that the agent has seen. The novel state ratio will be if there are no overlapping states in the transition graph, in which case Graph Backup reduces to Tree Backup. The average novel state ratio of MiniGrid/Minntarr// Atar are 2.006/0.2980..99 298/0.927 respectively. The relative average improvements of Graph Backup compared to Tree Backup are 190%/89%/179 on these three group tasks. The graph density alone, however, is not reliable indicator to (linearly) predict how much improvement the Graph Backup bring to a specific task. Although we know the Graph Backup will the same as Tree Backup the graph has crossovers, more crossovers do not always guarantee larger performance improvement.
15

---

Under review as a conference paper at ICLR 2023
When investigate the normalised performance gain and the novel state ratio for each individual task we tested, the correlation is -0.29. Other factors like the structure of the graph and reward density or simply the performance upper bound can also affect the performance gain. As mentioned in Section 4.2, Graph Backup seems to bring more benefits in sparse reward tasks, which can be explained by its counterfactual reward propagation. And the structure pattern of the graph, given the same amount of crossovers, can also play a role.
F GRAPH STRUCTURE VISUALISATION
In order to investigate the topology of the graph, we visualize the exact graph structure of the whole transition graph. In Figure we show four representative transition graphs and leave the others to Figure in the Appendix. We apply radial layouts proposed by Wills (199),, which scales well with the number of nodes and aligms well with the transition structure of most of the games. Since the common protocol for evaluating DRL agents in Atari games involves a random number of no-ops before the agent takes over the game, the initial states can vary for different episodes. To adjust for this, create a hypothetical meta-initial state pointing to all initial states of a game. The meta- iettill state is then treated as the root of the whole graph, displayed in the centre of each plot.
lot of transition graphs of Atari At0K show interesting crossover structures that be leveraged by Graph Backup. For example, the transition graph of Freeway forms a windmill-like pattern, where each blade corresponds to a group of trajectories that have connections within the group but between groups. There are also some tasks (e.g. Alien) where crossovers only happen at the start of the game. In such case, the Graph Backup will not helpful for most of the source states.
We also find some MinAtar and Atari games have self-loop states (e.g. Asterix), represented as circles in the graph. After further investigations, we found the existence of self-loops is because some the state transitions in MinAtar and Atari will not make observation changes (such as periodically moving objects). This actually violates the underlining assumptions of Graph Backup that the transitions must be Markovian, which can explain why Graph Backup is inferior to Tree Backup in some of the Tasks. On the other hand, the fact Graph Backup still outperforms multi-step methods on average suggests that Graph Backup is robust against minor violations of Markovian Assumption.
G FULL EXPERIMENT RESULTS
In Table 3 we show the results of each individual task and the mean/median of the average perfor- mance in each group of tasks.
H ALL TRANSITION GRAPHS
In Table 3
we visualise all the transition graphs of Atari ttai100KK 100K.
MIXED GRAPH BACKUP
By extending the N-Step-Q backup with the graph structure. mixed Graph Backup (GB-mixed). GB-mixed only applies the max operator on the boundary nodes
get another backup target, named
of the transition graph. Define T. def {($, f, T s} and c(s) ErET, f(T) similarly to before. The GB-mixed target for the state value is then:
क(ी) Erer, ((T) G c() > max, 9o (8,
G,
otherwise
6The scores of MiniGrid are treated as normalised as it is. The scores of MinAtar normalised by step 5-million-steps DQN performance reported hy Young Tian (2019)
16

---

Under review as a conference paper at ICLR 2023
Table 3: Full Results of all the Tasks. The agent for MiniGrid and MinAtar is based on DQN, and the agent for Atari100K is based Data-Efficient Rainbow. The default backup operator for rainbow is n-step-Q. The values in the table for MiniGrid and Minatar are raw game scores and those for Atari1008 are numan-normalised scores.
one-step
n-step-
tree
graph
MiniGrid- LantGrid=LaaaCnosssgggN--000
0.00=0.00
0.00+0.00
0.00+0.00
0.3840.21
MiniGrid- MiniGrid-Empty- Empty-8x8-v0
0.69=0.07
0.11#0.03
0.96+t0.00
0.96+0.00
MiniGrid-Sinnn SinaeaddiiiipcCosssssggg//-
0.00+0.00
0.00+0.00
0.00+0.00
0.21+0.1
MiniGrri- MiniGind-KeyCCrrdoorSSSR KeyCorridorS3R1-v0
0.00#0.00
0.00+0.00
0.00+0.00
0.76+t. 17
MamiGrddDDorKey-6xx6f
0.00+0.00
0.00+0.00
0.0440.04
0.58+0.21
IQM
0.0
0.0
0.0
0.74
mean
0.14
0.02
0.2
0.58
median
0.0
0.0
0.0
0.58
Minatar- seaquest
0.53#0.11
1.12+0.18
2.68+0.17
1.77=0.29
Minatur-
2.42+0.35
1.56+0.13
4.58:10.1 14
4.95+0.45
Minatar-asterix
2.07+0.59
2.05+1.40
3.33+1.57
2.2110.53
Minatar-freeway
0.9940.56
0.29+0.17
0,46+0.18
30.28++4.32
Minatar-space inndade
9.32+0.57
13.78+1.90
20.23
19.93
IQM
1.90
1.72
3.20
8.46
mean
3.07
3.76
6.26
11.83
median
2.07
1.56
3.33
4.95
alien
5.58+0.12
9.49+1.31
7.88+0.23
6.01
amidar
6.4940.37
8.46+1.10
5.0640.00
5.77+0.93
assault
83.90+1.88
42.7945.25
98.2744.19
102.50+4.28
asterix
4.74+0.
3.24+0.59
7.11#1.61
3.50+0.38
bank_heist
2.72+0.64
8.26+1.04
63.31
38.13+20.
battle_zone
9.31+2.53
21.83+1.09
22.6443.80
29.51+4.62
boxing
98.42440.41
-16.63+4.91
77.1943..70
53.14445.08
breakout
48.73+10.02
30.53+1.23
57.3014.30
65.30+7.05
chopper_commen command
8.52+1.15
9.50+1.25
6.3642.13
11.08
crazy eizy_cclimbr
101.27+27.40
34.85+4.54
110.68+8.89
113.45#17.38
demon_attack
24.65+6.86
3.40+0.68
24.84+4.00
23.83+5.59
freeway
53.29+17.20
61,25+22.38
35.81+22.65
64.16420.67
frostbite
3.84
4.56+0.14
4.3140.07
4.40+0.12
gopher
18.48+5.57
7.40+1.14
19.48+4.91
16.5415.34
hero
17.08+6.95
22.54+1.18
31.2543.28
30.63+1.23
jamesbond
75.72425.42
53.47+6.90
92.52+7.21
78.80410.82
kangaroo
29.61+4.05
143.46:44.42
76.86+27.87
141.14:37.87
krull
154.52+19.33
112.99+16.28
159.09*6.34
174.77+17.05
kung fu..uuu.m...... master
93.31=19.35
28.0744.81
62.3744.70
92.06+10.15
ms-pacman
9.71
12.94+1.31
9.11+1.06
14.60#1.11
pong
1.15+0.35
70.69+14.10
11.10+6.90
27.00#2.43
private eye
0.1
0.11+0.00
0.1140.00
-0.05+0.00
qbert
3.97+0.59
8.75+2.97
13.41+2.85
19.27+3.69
road_runner
167.53+63.55 .50
42.90+9.81
116. 16.12251.72
164.74+58.55
seaquest
1.51+0.12
0.96+0.11
1. 1.14+0.18
1.06+0.
up-n down
25.33+1.72
20.8440.73
20.7642.95
31.45+1.32
IQM
18.85
16.55
26.76
34,25
mean
32.8
28.72
43.62
50.49
median
13.39
16.89
23.74
30.07
17

---

Under review as a conference paper at ICLR 2023
Table 4: The unnormalised scores for Atari Note that taking average of these scores will lead to evaluation metric highly weighted by games with higher range.
one-step
n-step-Q
tree
graph
alien amidar
612.9348.14
714.60+88.06
771.30#15.97
642.70#38.61
117.01=6.37
179.38+3.76
92.51=0.00
104.65#16.04
assault
658.3249.51
422.47+16.66
733.00+21.74
754.98+22.23
asterix
603.33+25.95
497.25 16
199.67=133.22
500.67+31..8
bank_heist
34.27=4.74
79,50+1 1.24
482.00#141.66
295.97=150.20
battle_zone
5603.334880.01
11800
11800.00+0.00 00+0.00
00243.33+13225
12636.6741608.85
boxing
-11.71+4.85
0.00#0.00
9,36+4.28
6,48+5.41
breakout
15.7342.88
10.60=0.00
18.20#1.24
20.51+2.03
chopper command
1371.67475.49
1103.00#0.00
$539.6749.66
crazy_climen rrazy_llimber
36148.
11148.1746622 17#6862.90
22990.00#0.
38503 67722226.05
39198.67 6744444.44
demon_attack
600.42+124.. 124.86
182.00#11.81
603 90472.76
585,48+101.56
freeway
15.78+5.09
14.96#6.69
10.60=6.70
18.9946.12 12
frostbite
229.07+13.21
246. 1566.46
249.37+3.01
252.9345.05
gopher
655.77+120.05
341.50#11.22
677.40+105.88
613.93+115.14
hero
6116.5842072.96
7414.70#0.00
10340.43+978.
10154.154365.49
jamesbond
236.33+69.60
140.75+7.06
282.33+19.74
244.75+29.6
kangaroo
935.33+ 1 20.86
1907.00407.00
2344.674831.44
4262.33+1 129.61
krull
3247.534206.2
3004.35+13.30
2296.30467.66
2463.70+182.
kung fu master
21233.33+4348.22
9761.504794.99
14277.67 1055
20952. 0.55281.75
ms pacman
952.40+25.32
1015.65+6.69
912.40+70.82
1277 307.33377.99
pong
-20.29+0.13 13
0.00#0.00
-16.7842.44
-11.1740.86
private_eye
100.00+0.00
0.00+0.00
100.00+0.00
-10.3440.00
qbert
692.00+78.34
1176.75+0.00
145.674379.41
2724.75+489.88
road_runner
13134.67#4973.1
188.0000..0
9108.00 400454444
12916.6744588.43
seaquest
703.13250.67
529.20+0.00
596.27469.83
514.53+78.49
up down
3360.67#191.43
3303.50#0.00
2849.734329.4
4043.07#147.85
mean
3744.07
2731.61
3863.86
4527.08
18

---

Under review as a conference paper at ICLR 2023
The GB- GB-mixed target for the state-action value is then frequency weeihted average of the next state target:
aoaa c(s,a) EreT... f(T) + +G²)) if c(ss > qo (8
G
(8)
otherwise
Similar to N-Step-Q backup, GB-mixed is not a strictly off-policy backup operator. The value of boundary states is estimated in off-policg manner while the rewards of interior paths are on-policy, hence the name mixed Graph Backup. GB-mixed is biased backup operator when evaluating the target policy. However, it can also be less noisy than GB-nested since there the nested max operators can propagate over-optimistic value estimation error from every step to the source state.
J GRAPH DENSITY OF ATARI10OK
We also explore the role of graph density in the same set of tasks. In Figure we show the correlation between relative performance and novel state ratio, where each point represents a task Atari I O0K. The relative performance is the human normalised score of GB-nested divided by that of Tree Backup. indicates how many benefits the agent can get from leveraging the graph structure. There is negative correlation of -0.22 between the novel states ratio and relative performance. Although the correlation is weaker than in the case of cross- group comparison, the graph density can still affect the effectiveness of Graph Backup.
Figure 6: Relative performance and novel state ratio
gong
2.25
2.75
command
perfo
4 JACTIO
3.50
gfort
sooutt "ARgesaeeenn atta
1.00
alles
dcolng
Jant heret
0.525
0.800
0,000
0.22
0920 9935 1000
novel states r9tl
K. MINATAR 1M
Table 2 shows the performance of different methods after 1M steps of training. Both one-step and Graph Backup achieves the means scores close to the DQN asymptotic performance reported by Young & Tian Tian (2019). This shows that even with more training data, Graph Backup is able to converge to the same level of performance one-step backup. Surprisingly, though, the n-step-Q backup and Tree Backup both perform worse than one-step backup with more data. This can be explained by the innate problems of n-step-() and nested max operators. Strietly speaking, n-step- is not an off-policy backup operator because it always uses online reward sequences for the estimation of its value, which counter its advantages in longer reward propagation. This can be especially true for Minatar because its framerate is much lower than vanilla Atari and longer reward propagation may not be as important. For Tree Backup and Graph Backup, the nested max operator may cause an overestimation of values. We leave methods that address this problem for future work. With the over-estimation dealt with properly, Graph Backup may show even stronger performance in an asymptotic setting.
L COMPUTATIONAL OVERHEAD
19

---

Under review as a conference paper at ICLR 2023
In contrast to model-based planning methods, Graph Backup does not bring computational overhead at action selection. Therefore, during deployment, decision latency and the computational cost will be the same for previous methods, which we believe is important in Data-Efficien setting, where it's both important and required to leverage additional computing at training time to make up for the limited number of samples from the environment. On the other hand, the computational overhead of Graph Backup during training is nuanced and is heavily dependent on the implementation, the base algorithm, hyperparameters and the network architecture. In our implementation, the subgraph is constructed from the adjacency list (python dictionary), and the value for expanded state nodes can be computed in a batched way. This is quite different from model-based planning methods like MCTS where the tree expansion is conditioned on the policy and value estimation of parent nodes. Due to the easy parallelization of the neural network inference, the main bottleneck becomes the sub-graph expansion itself. Our implementation did the graph expansion and backup with python code and the different samples in a batch are processed sequentially, which makes the training 2-5 times slower than one-step backup. However, this is just simple proof of the algorithm's 's performance, and the implementation could easily be sped up drastically by JIT compilation or multi mutti-threading (or multi multi-processing).
M VALUE ESTIMATION VISUALIZATIONS
In Figure 7
we visualize the value estimates for all positions in an empty room environment. An agent starts at the bottom left corner and tries to reach the top right goal position. We fix the value of the goal position to be 1, and all other value estimations come from the Q network when the agent is in such position and facing right. The discount factor y = 0.95 is the same as in our empirical evaluations so the ground truth value for the initial position is 0.57. We fixed the random seeds of the agents and all of them will find the first reward in step 1957 and the training starts at step 2000. We can see graph backup quickly converge to the ground truth value estimation for half of the states at step 3000, whereas other backup methods only failed to correctly estimate the value of the initial state even after 30000 steps of training.
An interesting observation is the value is not overestimated for Graph Backup even though it has a lot of nested max operators. On the other hand, values of some states are over-estimated by Tree Backup agent and one-step backup agents at step 30000. This can be explained by the combination of counterfactual credit assignments and online interactions. If the value of a state is overestimated, such excess value will quickly propagate to a lot of the interconnected states. Therefore, the agent will then actively try reach the over-estimated states and such overestimation will then be corrected. Another interpretation is the overestimation comes from the extra noise of one-step and Tree Backup. In Figure even training the value from the logged data, Tree Backup and one-step backup will sometimes give higher value estimation than Graph Backup.
3.B
8.99
3.50
6:44
52
3.03
are xxe
<D4 1536
3200
(a) One-step Backup
(b) n-step-Q Backup
3.34 (524 043 3:47
0.55 0.03 6:5
B.77 0/5
C47 833 334
0.00 odd
035
3.35
OUT 0.37 333 0.06
0.7 0.5
3.71
0.75
3as 0:0
0:0 c50
0.9
0.99
8
Beo 3006
EMC 13006
190 3006
1930 3008
092 22006
1990 3009
(c) Tree Backup
(d) Graph Backup
Figure 7: Value Map of Empty Room
20

---

Under review as a conference paper at ICLR 2023
(a) Alien
(b) Amidar
(c) Assault
(d) Asterix
(c) Bank Heist
(f) Battle Zone
21

---

Under review as a conference paper at ICLR 2023
(g) Boxing
(h) Breakout
(i) Chopper Command
(j) Crazy Climber
Demon Attack
(1) Freeway
22

---

Under review as a conference paper at ICLR 2023
(m) Frostbite
(n) Gopher
(o) Hero
(p) Jamesbond
(g) Kangaroo
(r) Krull
23

---

Under review as a conference paper at ICLR 2023
(s) Kung Fu Master
(1) Ms Pacman
(u) Pong
(v) Private Eye
(w) Qbert
(x) Road Runner
24

---

Under review as a conference paper at ICLR 2023
(y) Seaquest
(2) Up Down
Figure 8: All Transition Graphs of Atari100K
100K
25


Reviews:
[{"review_id": "zdpyh8FdOq", "reviewer": "Reviewer_iGcV", "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": "", "summary_of_the_paper": "This paper proposes a new backup operator that exploits potential graph\nstructure in the observed transitions. The purpose of this backup\noperator is to increase data efficiency by allowing information to be\nbacked-up further along state transitions and providing better value\nestimates. Their results demonstrate, rather conclusively in the\naggregated score, that backup operators can improve data-efficiency. In\nparticular, a rainbow DQN agent augmented with graph backup tends to\noutperform one-step, n-step and tree-backup targets on MinAtar and Atari\n100k.\n", "summary_of_the_review": "\nI am somewhat torn on this submission. On the one hand, the contribution\nis clear and the experiments are in favor of the proposed method (graph\nbackup). It is also well connected to previous literature as an\nextension of tree-backup. This suggests that graph-backup does improve\ndata-efficiency, and the main explanation is that this improvement is\ndue to exploiting the graph structure of some fixed breadth. Some\nstatements in the manuscript are still unclear, and the overall\nmotivation for why graph backup would benefit in environments like Atari\nis still non-obvious. In light of the large improvements that graph\nbackup can make, I think this finding needs to be better explained,\neither from further intuition or results on a simple problem (but with\nfunction approximation). I am currently rating this paper at a weak\nreject. However, I am very open to increasing my score up to an accept.\n", "strength_and_weaknesses": "# Strengths\n\n-   The empirical results presented seem strongly in favour of graph\n    backup. This is especially interesting because a priori I would not\n    expect that the results would be strong on Atari due to low expected\n    crossover.\n\n-   Overall easy to follow with a clear contribution. Graph backup is\n    well-connected to the literature, as a generalization in breadth\n    from tree-backup. Experiments also leverage an already strong\n    baseline, and tweak a single component making the contribution of\n    graph backup clear as well.\n\n# Weaknesses\n\n-   Despite the paper being overall clear and easy-to-follow, there are\n    some statements in the paper that are unclear. While I understand\n    the method, its motivation and its use in Rainbow DQN, I am not able\n    to follow the reasons for the large improvement. The difference\n    between tree backup and graph backup, in particular, is\n    significantly larger than I would expect. Little intuition, or\n    empirical insight, is given to explain this effectiveness. Although\n    the crossover rate for Atari is reported, I am still left wondering\n    why the method is as performant as reported.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eck9yb0yDb", "reviewer": "Reviewer_zkNq", "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": "", "summary_of_the_paper": "The paper studies the value function back-up estimation problem in data efficient reinforcement learning. The key idea is to the Graph Backup, with uses creates a tree-structured update of the value function based on multiple trajectories which have overlapping states. Because of the overlapping trajectories, it has advantages such as the counterfactual credit assignment and smaller variance. The empirical results show that the proposed Graph Backup method, when integrated into DQN or Rainbow, outperforms existing backup methods in data efficient settings.  ", "summary_of_the_review": "Main reasons of accepting the paper are points (1)(2)(3) of strengths. \nMain reasons of rejecting the paper are points (1)(2)(5) of weaknesses. ", "strength_and_weaknesses": "Strengths:\n1) The problem being studied is well-motivated: data efficient RL is a practical and important topic in many real-world RL tasks.\n2) The idea of using crossover trajectories in updating the value function is interesting and novel. I am a bit surprised that this has not been studies in previous works (from what I saw in the discussion of related works).\n3) The empirical results look promising. \n4) The analysis in Section 6 is an addition. Though there might be some limitations there. \n\nWeaknesses:\n1) The settings with overlapped (crossover) trajectories are often quite restricted. In the Atari game, the ratio of crossover trajectories is relatively high because the initial state is always the same. This is a strong assumption for the majority of the RL tasks/MDPs. Therefore, this has strongly limited the applicability of the proposed Graph Backup method. \n2) It is not clear why a data graph is necessary for the proposed backup in Equation (6), and it looks like that this critical information is only included in the Appendix. Therefore it is very hard to evaluate the motivation of the proposed data graph.\n3) In computing the new backup, there is a computational overhead since it requires more computations with the iterative update and multiple crossover trajectories. It would be good to add some discussions/evaluations of the computational overhead.\n4) Section 4.2: This is more like a discussion. While it is good to have such kind of discussions, the paper would be stronger if it includes some formal results for the described advantages.\n5) The writing of the paper needs significant work. While this is normally not the reason to reject a paper, it is making it really challenging to evaluate the paper itself when clarify is a serious issue. Examples:\n- Figure 2 is far from where it is first referred to. It does not really help understand why multi-step backup adds variance to the state value estimates.\n- The visualization of Figure 1(a) is good, but it would be better if there is explanation as to what the shape of the graph indicates, e.g., is it a subgraph that shares the same target state? It will be more informative if such kind of discussion/description is provided.\n- In Figure 1, \"The blue squares represent the state-action pairs\" -> they should just be the actions from what I understand\n- Equations (7) and (8) are in the appendix, but they are referred to in the main text.\n- Some typos and grammar issues. E.g., 2nd last line of Page 2: \"as they are also utilise\" -> remove \"are\"; 1st line of Page 3: \"Zhu et al. (2020) propose the using the MDP graph\" -> \"propose to use\"; 3rd line after Equation (3): \"in a off-policy\" -> \"an\"; 4th last line of Page 3, \"Despite what it’s name suggests\"->\"its\". There are a few more which I did not list but strongly suggest the authors check them out. \n- Notations: \n1st line after Equation (1): $G^{a_T}$ should be $G^{a_t}$; Equation (2): \n$\\theta'$ is not explained? You did not mention anything about a separate network. Also, the superscript of G is not explained, and is inconsistent with Equations (3) (4); \nEquation (4): why do we compare t with n in the condition  of Equation (4)? by t<n do you mean the last time step in n-step return? In this case you should use a t' as the generic step, and the condition should be $t'<t+n$. \n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "EOlTSkJL1G3", "reviewer": "Reviewer_8RrV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new target value estimate approach, Graph backup, based on tree-backup. The main idea is to leverage the crossover on state space to accelerate value propagation using a graph. In graph backup, a state-transition graph is built and the target value for each value backup is estimated by looking at the Q-values a few steps ahead on the graph. The empirical results show that graph backup can be a drop-in replacement to Rainbow (a DQN variant) and attains visible performance improvements, particularly in MiniGrid ( challenging sparse reward tasks).", "summary_of_the_review": "Overall, I enjoy reading the paper and the analysis section in particular. The writing can be improved to make it easier to follow (especially the pseudocode). The algorithm has some novelty, but more work needs to be done in order to apply such a method to continuous state space. ", "strength_and_weaknesses": "**Strength**\n\n* The method is well-motivated and novel and can be combined with many existing off-policy algorithms.\n* The empirical results are convincing and comprehensive (experiments on MiniGrid, MiniAtar, Atari100K).\n\n**Weakness**:\n\n* Some of the pseudocode is hard to follow (See my questions).\n* The implementation of the graph is complicated.\n* The applicability to continuous state space or more complex games with a high novel state ratio is unclear.\n* Computation costs might be big to build and loop over the graph?\n\nQuestions:\n* In Line 2, Algorithm 1, what does “the largest element” mean?\n* Algorithm 2 in the Appendix is confusing. Where is $\\bar{G}^{a}_s$ used in the update?\n* Since graph backup performs recursive max-operation while looking ahead from a node, would graph backup aggravate over-estimation?\n* I wonder when the novel state ratio is low (i.e., many crossover states), would a discrete graph planning achieve competitive performance with deep RL?\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "D2OHSXBkSy", "reviewer": "Reviewer_uNoE", "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": "", "summary_of_the_paper": "The paper suggests that an important way to improve sample efficiency in reinforcement learning comes from bootstrapping from accurate target estimates. Although multistep methods such as TD(lambda) offer a bias-variance trade-off, the authors argue that such algorithms fail to exploit the underlying graph structure of the MDP. They therefore propose to explicitly build a graph structure out of the experience of the agent allowing for bootstrapping targets to be composed of various trajectories starting from the current state. The authors claim that this method leads to counterfactual credit assignment and reduced variance. They evaluate their method on variety of environments, from smaller grid-like worlds to the  Atari domain.", "summary_of_the_review": "The proposed method tackles an important challenge in RL, but the claims are sometimes hardly justified. Importantly, the paper proposes an inherently non-scalable method, and it is not clear how it can avoid the curse of dimensionality. On some environments the propose method provides significant gain, but on larger ones it doesnt. More important, those results on only 5 seeds and the CIs are sometimes not even presented.", "strength_and_weaknesses": "# Strengths\n- The paper tackles an important problem\n- Trying to construct graph to better perform credit assignment can be an promising path in RL\n- Evaluation on a variety of environments\n\n# Weaknesses\n- The graph construction method seems inherently not scalable\n- The results are not really statistically significant in larger environments\n- Some claims should be more nuanced or supported by evidence", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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:

Decision: Reject