Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a novel width-based algorithm, RIW+CPV, for playing Atari 2600 games. RIW+CPV is based on RIW, an algorithm that performs a depth-first search while pruning nodes according to IW's novelty metric and it guides the search with a base policy (later works showed how to learn such a base policy). In addition to the base policy, RIW+CPV learns a value function that is used to evaluate the leaf nodes of the lookahead tree RIW expands before deciding on the action that will be applied in the environment. Empirical results show that RIW+CPV achieves higher scores on a larger number of games than other IW-based methods for Atari 2600 games. 
main_review: The paper lists the following contributions (see last paragraph of Section 1):

(1) analysis of previous IW algorithms for Atari games;
(2) new IW-based algorithm
(3) learning schedule
(4) identifying characteristics of Atari 2600 games that influence the performance of IW-based planners

Contributions (2) and (3) are in fact a single contribution. The new search algorithm uses a learning schedule for updating the weights of the neural models responsible for encoding the policy and value functions. In my opinion (2)+(3) is the main contribution of the work. The new algorithm, RIW+CPV, learns a value function that is used to evaluate the leaf nodes of the lookahead tree the algorithm expands before deciding on the next action the agent will take. 

The original RIW algorithm used V-values of zero for all leaf nodes (i.e., RIW assumes that the agent won't receive any reward from a leaf state onwards). This is a reasonable assumption to make as long as the lookahead tree is able to "look far enough" into the future. The problem is that in (almost) real-time search one is unable to look far enough into the future. The present work replaced the V-value of zero by a value function that estimates the expected reward value from the leaf node. 

The CPV in RIW+CPV stands for Critical Path Value Function. The critical path is formed by the set of actions the algorithm chooses after completing its search in each "decision point." The paper explains that the value function is learned for the critical path and not for the base policy that is used to bias the lookahead tree. I believe there is a better way of describing the value function RIW+CPV learns. The value function returns a value that estimates the expected reward if a given policy is used from a given state onwards. The paper correctly explains that the base policy isn't the value function's policy. The lookahead search can be seen as a policy improvement operator, similar to how PUCT is to AlphaZero. The value function RIW+CPV is in fact for the policy induced by this  operator. I would define this policy (perhaps \pi_{IW}?) and explain that the value function learned is for \pi_{IW}.

RIW+CPV is indeed stronger than previous IW methods as shown in the experiments. However, I missed in the experiments a baseline that doesn't use novelty. RIW+CPV is similar to AlphaZero in the sense that it employs both a policy and value function to guide its search. One then wonders how much of the results are explained by IW's clever pruning or by the learned policy and value functions. It would be nice if the authors could include results of a version of RIW+CPV in which the IW part is turned off.  

Another suggestion is to use the learned value function to refine the novelty function. The paper considers two novelty definitions: classic and depth-based. However, it misses a definition that uses ideas from the classical planning literature where a heuristic function is combined with novelty. For example, [1] uses novelty to break ties of nodes with the same h-value. The novelty values in the context of Atari 2600 games could be refined with the V-values by considering a node n novel according to feature f even if another node n' had already satisfied the novelty condition with respect to f as long as V(n) is different than V(n').

Still under the umbrella of the contribution (2)+(3), I enjoyed the fact that the novelty is computed in terms pixels in this work. It is a pity that the paper doesn't present ablation studies to help us understand whether to good performance comes from the novelty representation or from the learned value function. 

The contribution (1) is fair. I enjoyed reading the related work section of the paper. I was already somewhat familiar with the literature though. I wonder if someone new to the field will also appreciate the analysis of previous algorithms. The analysis would be better if it had explained how the hierarchical \pi-HIW(n, 1) relates to the current work. For example, can one apply the ideas introduced in this work to the hierarchical algorithm? 

I was somewhat confused with the experiments of contribution (4). This is mainly because the tables of results do not report a normalized average win rate, but only the total number of wins. It is very hard to compare across tables without a normalized value. 

OTHER SUGGESTIONS

In the conclusion it reads "We hope that by having addressed some of the discrepancies in the experimental settings of previous width-based algorithms, such as the size of the action set and the planning budget used, [...]" I disagree that this paper addresses the discrepancies. This paper acknowledges the discrepancies and chooses one of the options that had been used in the past. The paper doesn't explain why the chosen option is superior and should be the standard option for future works. 

"without loss of generality, we consider only discrete action sets and deterministic action transitions." I disagree that this is without loss of generality. It isn't clear how RIW works with continuous action and state spaces and how it deals with stochastic transitions. 

Reference:

[1] Nir Lipovetzky and Hector Geffner. Best-first width search: Exploration and exploitation in classical planning. In AAAI Conference on Artificial Intelligence, pages 3590–3596, 2017.
limitations_and_societal_impact: Yes, the authors have addressed the limitations of their study and proposed algorithm, such as the lack of ablation studies.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary:   The paper proposes a new state of the art in planning-based approach
  to Atari game.  The paper carefully analyses existing work, including
  $pi$-IW+ which uses both value and policy functions, and fixes several
  incorrect decisions that qualitatively does not make sense, such as
  mixing up the estimate for the base and the critical path policy.

  Perhaps what I would ask the authors is the way the paper is written:
  The current text is not written in the style of "They do X which has
  this issue; therefore we do Y" --- issue-focused description, but in
  the style of "We do Y; X does this; X is problematic".  For example,
  Sec 4.2 could be titled as "Addressing the complex novelty definition
  in RIW", or "Simplifying the novelty; depth-based novelty is not
  necessary".

  The algorithm also has a mechanism inspired by AlphaZero, which
  resembles active-learning (section 4.5), which compares the old and
  the updated parameters.  Following up work should more carefully
  evaluate this mechanism as an active-learning scheme.

  Its second contribution is the proposal of a standard evaluation
  scheme, which is now an adequate proposal due to the recent
  improvement in the field.

  The proposed algorithm is carefully evaluated empirically,
  characterizing the sparseness and the branching factor.

  This is a solid paper that I recommend for acceptance.

main_review:   Throughout the paper, "base policy" could be replaced with "uniform
  random policy" to make the meaning immediately obvious.  In the
  current text, readers should trace the meaning back to line 120-121,
  and it may still be a bit ambiguous.

  l.134, and are hard to distinguish, consider alternative punctuations.
  Well, shouldnt you just use V if and V are same?


  There are quite a lot of variations of the algorithms.  I suggest
  adding a feature comparison table between them.

  The table row / column ordering in Table 1,2 could be reconsidered to
  emphasize your proposed approach --- RIWD+CPB at the top.

  There are inconsistencies in the references (conference names, etc.)

  Regarding the full vs minimal action sets, [1] [2] are worth cited.



  [1] Jinnai, Yuu, and Alex Fukunaga. "Learning to prune dominated
  action sequences in online black-box planning." Proceedings of the
  AAAI Conference on Artificial Intelligence. Vol. 31. No. 1. 2017.

  [2] Mark J. Nelson (2021). "Estimates for the branching factors of
  Atari games." In Proceedings of the IEEE Conference on Games.

limitations_and_societal_impact: The paper deals is categorized as basic research rather than applied research. It is not likely to cause large societal issue.
The evaluation is also performed with much less compute than what is typically used in RL papers, and is likely to have less environmental impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper builds upon existing width-based methods for solving Atari games environment, in particular Rollout-IW, and enhances them with Critical Path Value Functions to achieve better results. 
main_review: Novelty:
Although the novelty based rollouts and the critical paths are not novel themselves, the application of critical paths to enhance width-based search as presented in the paper is novel.

Clarity:
The paper is written in a somewhat confusing manner. My main issue is that the RIW+CPV (algorithm constituting the main contribution of the paper) is presented in a very informal way, thus it is hard for the reader to comprehend how exactly does it function. Also, some sentences are structured in a very confusing way and some decisions are left unexplained.

Scholarship:
The literature review is sufficient. 
It should be noted, however, that you omitted the work of Dittadi et al. from section 4.2, where you discuss the novelty features. Their representation of the features was shown to perform better than B-PROST, and you mention them in the introduction, so it is unclear why this work uses B-PROST.

Reproducibility:
I was not able to launch the code by following the instructions in the readme file. However, this might be due to my system’s limitations.

Notes:
Line 34: “... we consider planners which use novelty measures directly over the values of screen pixels” - no justification is given for this decision.

Line 61: “... we consider [...] deterministic action transitions” - Atari screen setting is not deterministic as far as I’m aware (as opposed to Atari RAM setting)

Line 65: It doesn’t make sense to me to draw from T if you assume deterministic action transitions.

Line 66: Why introduce \gamma just to say that it's 1?

Def. 1 (lines 75-77): What do you mean by “nodes/states”? Does it mean that there are 2 definitions here, one for lookahead tree with states and the other one for lookahead tree with nodes? Or do you declare that here states and nodes are two different names for the same type of objects? What is the connection between these and the MDP described above?

Lines 78-79: In section 2.1 the rewards are defined on pairs (a, s), where s is a state but here you mention “rewards for each node”, please clarify.

Line 90: Again, it doesn’t make sense to me to draw from T if you assume deterministic action transitions

Lines 155-156: This sentence confused me. Do RIW(1) and RIW_{D} refer to the same algorithm? If so, why give it a different name?

Lines 190-201: The description of the algorithm is very informal. I would suggest formalizing it, or at least attach a graphics to help the reader understand the process

In the result tables - it's not clear whether the number in row $i$ column $j$ represents how many times $i$ beats $j$ or $j$ beats $i$.

Lines 359-360: Is the taxonomy that you refer to just the binary quality of a game being SMRF or not?

Summary: 
The main idea of the paper looks promising, but sadly the clarity of this paper is subpar.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The reviewers have written careful reviews and are generally in agreement that the paper is making a nice contribution. The authors are strongly encouraged to revise the final paper in accordance with the substantial feedback from the reviewers. 
Decision: Accept (Spotlight)