Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: # Strengths
- The paper tackles an important problem
- Trying to construct graph to better perform credit assignment can be an promising path in RL
- Evaluation on a variety of environments

# Weaknesses
- The graph construction method seems inherently not scalable
- The results are not really statistically significant in larger environments
- Some claims should be more nuanced or supported by evidence
clarity,_quality,_novelty_and_reproducibility: Obtaining accurate bootstrapping targets is indeed essential in RL as most methods rely on this mechanism, either through value based methods or policy-based ones. Multistep TD methods generally only consider the sampled trajectory to perform updates, as a way to achieve scalability. My understanding is that the method the authors propose tries to construct the underlying graph of the MDP directly on observations, which inherently seems not scalable to large environments. By constructing this underlying graph, the method the authors propose to bootstrap from targets belonging to different possible trajectories, weighted by their probability of taking place. I am having a hard time understanding how this motivation differs from standard dynamic programming updates, yet there is no mention of it in the paper. Arguably, the authors do not try to bootstrap from all possible futures, only from the subset which has previously been observed. However, this strategy, based on modelling each observation as a node of the graph, faces the same curse of dimensionality. This is illustrated by the empirical results on Atari, which do not provide significant gain as the confidence intervals overlap, as well by how sparse the resulting graph is (.927 novel state ratio). I would really appreciated more discussion on this in the paper, in particular if the authors considered working in a (possibly discrete) latent space. For example, the authors mention that the transition matrix is estimate through counts. Are they also using counts for Atari, or instead are they using pseudo-counts? Moreover, how long does it take for the algorithm to perform updates, compared to other methods?

The authors claim that performing the Graph Backup update will lead to reduced variance. Although this is intuitive as expected updates usually do so (Expected SARSA or Expected Policy Gradients, which are not cited), I would have liked to see some experiments to support this. 

Throughout the paper, there are some fundamental concepts that seem wrong. For example in section 3 "n-step-Q exploits the chain structure of the trajectories with little computational cost, but at a cost of biased target estimation". It is not clear what is meant by this. Q-Learning add bias by boostrapping, as do all TD methods when lambda is not set to 1.


Regarding experiments, the results on MinAtar and MiniGrid are good, however they are done with only 5 seeds which is very little considering how fast they can be performed. Moreover, the variance of the plots is very high, which brings into question the robustness of the method.

The paper adequately cites recent work such as Expected Eligibility Traces, however they do not provide a comparison to it in the experiments. There is in fact no comparison to any other method trying to performing credit assignment more efficiently, such as [1] or [2]. Recent work on leveraging the underlying structure of the graph for better information propagation would be a particularly good baseline [3]. In general I there isn't enough relevant baselines or other recent work on unifying multi step methods [4].


[1] Counterfactual Credit Assignment in Model-Free Reinforcement Learning.  Mesnard et al. 2020
[2] Hindsight Credit Assignment, Harutyunyan et al. 2019
[3] Reward propagation using graph convolutional networks, Klissarov et al. 2020
[4] Multi-step reinforcement learning: A unifying algorithm, De Asis et al., 2018   
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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).
strength_and_weaknesses: **Strength**

* The method is well-motivated and novel and can be combined with many existing off-policy algorithms.
* The empirical results are convincing and comprehensive (experiments on MiniGrid, MiniAtar, Atari100K).

**Weakness**:

* Some of the pseudocode is hard to follow (See my questions).
* The implementation of the graph is complicated.
* The applicability to continuous state space or more complex games with a high novel state ratio is unclear.
* Computation costs might be big to build and loop over the graph?

Questions:
* In Line 2, Algorithm 1, what does “the largest element” mean?
* Algorithm 2 in the Appendix is confusing. Where is $\bar{G}^{a}_s$ used in the update?
* Since graph backup performs recursive max-operation while looking ahead from a node, would graph backup aggravate over-estimation?
* 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?

clarity,_quality,_novelty_and_reproducibility: The paper presents a novel graph backup algorithm and show consistent improvements on the experiments.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.  
strength_and_weaknesses: Strengths:
1) The problem being studied is well-motivated: data efficient RL is a practical and important topic in many real-world RL tasks.
2) 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).
3) The empirical results look promising. 
4) The analysis in Section 6 is an addition. Though there might be some limitations there. 

Weaknesses:
1) 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. 
2) 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.
3) 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.
4) 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.
5) 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:
- 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.
- 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.
- In Figure 1, "The blue squares represent the state-action pairs" -> they should just be the actions from what I understand
- Equations (7) and (8) are in the appendix, but they are referred to in the main text.
- 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. 
- Notations: 
1st line after Equation (1): $G^{a_T}$ should be $G^{a_t}$; Equation (2): 
$\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); 
Equation (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$. 

clarity,_quality,_novelty_and_reproducibility: I use 4 levels of grades: strong, good, fair, poor

Clarity: poor. See point (5) of weaknesses.
Quality: fair. 
Novelty: good.
Reproducibility: good.
summary_of_the_review: Main reasons of accepting the paper are points (1)(2)(3) of strengths. 
Main reasons of rejecting the paper are points (1)(2)(5) of weaknesses.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new backup operator that exploits potential graph
structure in the observed transitions. The purpose of this backup
operator is to increase data efficiency by allowing information to be
backed-up further along state transitions and providing better value
estimates. Their results demonstrate, rather conclusively in the
aggregated score, that backup operators can improve data-efficiency. In
particular, a rainbow DQN agent augmented with graph backup tends to
outperform one-step, n-step and tree-backup targets on MinAtar and Atari
100k.

strength_and_weaknesses: # Strengths

-   The empirical results presented seem strongly in favour of graph
    backup. This is especially interesting because a priori I would not
    expect that the results would be strong on Atari due to low expected
    crossover.

-   Overall easy to follow with a clear contribution. Graph backup is
    well-connected to the literature, as a generalization in breadth
    from tree-backup. Experiments also leverage an already strong
    baseline, and tweak a single component making the contribution of
    graph backup clear as well.

# Weaknesses

-   Despite the paper being overall clear and easy-to-follow, there are
    some statements in the paper that are unclear. While I understand
    the method, its motivation and its use in Rainbow DQN, I am not able
    to follow the reasons for the large improvement. The difference
    between tree backup and graph backup, in particular, is
    significantly larger than I would expect. Little intuition, or
    empirical insight, is given to explain this effectiveness. Although
    the crossover rate for Atari is reported, I am still left wondering
    why the method is as performant as reported.


clarity,_quality,_novelty_and_reproducibility: # Detailed Comments (Clarity, Quality, Novetly, Reproducibility)

-   Section 1, (data-use): "Data is normally stored in a buffer and only
    used several times for learning before being discarded. This means
    these algorithms underutilise the data that is generated from the
    simulator"

    It is hard to argue that replay-buffer based training doesn't make
    use of data. As far as minimizing TD errors of the current policy,
    which is the goal of most value-based methods, the data has
    contributed all it can in some sense. While the environment may
    possess additional structure, this is not known apriori. Of course,
    it can also be argued that the right back-up operator can minimize
    these errors in fewer iterations.

-   Section 2, (Connection to Model-based RL): Paragraph 3 lists some
    model-based work and separates the proposed graph backup from MCTS
    methods that also utilise tree-structure search algorithms. It is
    would be good to discuss further what advantages graph backup
    provides over background planning methods, that use a learned model
    to provide samples. This would bring all problems - including those
    without a simulator - closer to "cheap data" regime.

-   Section 3, (Equation 1): It is not quite correct to refer to this as
    a loss function. This is because temporal difference methods which
    use a stop-gradient are not taking the gradient of any objective
    function. There are gradient TD methods, but they minimize the
    projected mean squared bellman error.

-   Section 4 (counter function) : This seems to be the key function in
    graph backup - but it is also the most problematic. Similar to
    count-based exploration methods, accurately learning to count
    visitation is a challenging problem.

-   Section 4.2 (counterfactual): A tabular update to the value function
    at one transition will not directly influence the value function at
    other states from other trajectories. With function approximation,
    however, there will be generalization which may allow for changes in
    nearby states in feature space.

-   Section 4.2 (spare reward settings): if there are truly no rewards
    from a lack of successful trajectories, then both graph backup and
    one-step backups will fail to learn anything meaningful. If there
    are some trajectories that are successful, then this information
    will still be propagated to other states from other trajectories
    through generalization, as long as they are in the replay buffer. It
    may take more iterations but this is not what you seem to argue in
    Section 4.2 Paragraph 1.

-   Section 4.3 (variance): this point about averaging over many
    trajectories is interesting and valid. It is, in my opinion however,
    lacking some nuance because it may not be the case that your counter
    functions is accurate.

-   Section 4.2 (bias): while you discuss how graph backup can reduce
    variance, you also mention that multi-step backups can be biased for
    Q-learning. I do not see a discussion of whether graph backup is
    similarly biased. This would help situate graph-backup in the space
    of backup operators described in section 3.

-   Section 4.3 (Limiting expansions in Figure 1b). Could you explain
    why the top node in figure 1b is faded? Its parent node only expands
    one child node, so the top most node should satisfy the breadth
    limit, unless the breadth is not at the expansion level but at the
    tree level.

-   Section 4.5 (crossover assumption): I think it would benefit more
    broadly to discuss (or demonstrate empirically) the importance of
    these assumptions. The Markov assumption is obviously tied to
    effectiveness of not only the method but RL algorithms as whole. It
    is not, however, obvious the degree that crossovers matter (for
    example, if 1\% vs 10\% of states have a crossover).
summary_of_the_review: 
I am somewhat torn on this submission. On the one hand, the contribution
is clear and the experiments are in favor of the proposed method (graph
backup). It is also well connected to previous literature as an
extension of tree-backup. This suggests that graph-backup does improve
data-efficiency, and the main explanation is that this improvement is
due to exploiting the graph structure of some fixed breadth. Some
statements in the manuscript are still unclear, and the overall
motivation for why graph backup would benefit in environments like Atari
is still non-obvious. In light of the large improvements that graph
backup can make, I think this finding needs to be better explained,
either from further intuition or results on a simple problem (but with
function approximation). I am currently rating this paper at a weak
reject. However, I am very open to increasing my score up to an accept.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: (a) Summary: This work proposes to improve sample efficiency in RL by constructing bootstrapping targets from multiple trajectories starting at the current state, in a manner akin to tree backup.

(b) Strengths:  All the reviewers agreed that the paper studies an important problem.  Exploiting graph structure in the environment's dynamics may be a promising direction.  The empirical results seem promising.

(c) Weaknesses: All reviewers had significant clarity concerns.  It was not clear to multiple reviewers where the empirical improvements came from.  All reviewers agreed that this approach is likely to have significant scalability issues.

justification_for_why_not_higher_score: Although the empirical results were promising, the reviewers did not understand how they came out of the paper's proposed approach.  (Additionally, one reviewer did not consider the empirical improvements significant).  None of the reviewers (including the one marginally positive reviewer) were willing to advocate for accepting the paper.

justification_for_why_not_lower_score: n/a
Decision: Reject