Width-based Lookaheads with Learnt Base Policies and Heuristics Over the Atari-2600 Benchmark
Authors: Stefan O'Toole
Nir Lipovetzky
Miquel Ramirez
Adrian Pearce
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: width based planning
planning and learning
online planning
atari
planning over simulators

Abstract: We propose new width-based planning and learning algorithms inspired from a careful analysis of the design decisions made by previous width-based planners. The algorithms are applied over the Atari-2600 games and our best performing algorithm, Novelty guided Critical Path Learning (N-CPL), outperforms the previously introduced width-based planning and learning algorithms $\pi$-IW(1), $\pi$-IW(1)+ and $\pi$-HIW(n, 1). Furthermore, we present a taxonomy of the Atari-2600 games according to some of their defining characteristics. This analysis of the games provides further insight into the behaviour and performance of the algorithms introduced. Namely, for games with large branching factors, and games with sparse meaningful rewards, N-CPL outperforms $\pi$-IW, $\pi$-IW(1)+ and $\pi$-HIW(n, 1).

Width-based Lookaheads with Learnt Base Policies and Heuristics Over the Atari-2600 Benchmark
Stefan O'Toole
Nir Lipovetzky Computing and Information Systems University of Melbourne, Australia nir. Lipovetzky@uninen edu. au
Computing and Information Systems University of Melbourne, Australia stefan@student unimelb. edu. au
Miquel Ramirez
Adrian R. Pearce Computing and Information Systems University of Melbourne, Australia adrianrp@umimell edu. au
Electrical and Electronic Engineering University of Melbourne, Australia miquel. rwwirez@uuimeeleeeeleeee edu. au
Abstract
We propose new width-based planning and learning algorithms inspired from a careful analysis of the design decisions made by previous width-based planners.
The algorithms are applied over the Atari-2600 games and our best performing algorithm, Novelty guided Critical Path Learning (N-CPL), outperforms the previously introduced width-based planning and learning algorithms x1I,(I), present taxonomy of the Atari-2600
x-IW(1]+ and (n,, 1). Furthermore, games according to some of their defining characteristics. This analysis of the games provides further insight into the behaviour and performance of the algorithms introduced. Namely, for games with large branching factors, and games with sparse meaningful rewards, N-CPL outperforms I-IW, I-IW(I)+ and T-HIW(n, 1).
Introduction
The Atari-2600 games provide useful environments for benchmarking autonomous agents due to the diversity of behaviour required across the different games. The Atari-2600 games be accessed through the Arcade Learning Environment (ALE) [1] which provides a typical Reinforcement Learning (RL) environment interface where given state, the agent selects action and receives resulting state and reward. The two main approaches that have been used by autonomous agents applied to the Atari-2600 games have been RI methods 22 3 and Planning methods [5. The RL approaches have had great success surpassing the performance of human players for many of the Atari-2600 games. However, RI. approaches require long training times in order train the Neural Networks (NN) used for policy and value functions. Planning agents do not require training time and instead use a bounded, fixed computational budget decide which action take at each time step of the game. The budget allowed for planning for each action is set as part of the experimental setting and can be set in such a way that the agent can play a game in real-time. Through the ALE interface, the agent not provided a description of the transition or reward functions as is the case of models described through languages such as the Planning Domain Description Language (PDDL) 7 Instead, planning agents applied to the Atari-2600 games are required to work with simulator, treating the environment's s transition and reward functions as black-box
Width-based planning agents have been shown to be particularly successful on the Atari-2600 games when compared other planning agents 6). Width-based planners prioritise search effort on states deemed to be novel. The novelty of a state can be defined in a number of ways. Previously, novelty tests have been obtained from the RAM of the game [ handcrafted features computed from screen
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

pixels [6] and learnt features extracted from the screen pixels through NN 8 9 L0. In this paper we consider planners with novelty measure that does not require extensive feature engineering, or the internal state of the simulator, but is instead defined directly over the values of screen pixels.
Recent approaches have combined the RL and planning methods into single agents that are applied to the Atari-2600 games [ Junyent et al. [8] combined a width-based planner with a learnt policy defined over a NN in order to guide the planner to promising areas of the search space. The learnt NN was also used to extract features from which the novelty of states were defined over. In this paper we introduce new width-based planning and learning methods that learn both policy and value networks using methodical learning schedule.
Through analysing previous width- based methods we construct and benchmark new width-based approaches for the Atari-2600 games. We also classify the Atari-2600 games according to their particular characteristics. The resulting game taxonomy helps us gain insight into the performance of the al algorithms we propose and benchmark. The paper contributions are: (1) an analysis of the previous width-based planning methods that have been applied the Atari-2600 games, (2) introducing new width-based planning and learning approaches for playing the Atari-2600 games, (3) defining a methodical learning schedule for planning and learning methods, and (4) identifying characteristics of the Atari-2600 games that influence the performance of different planning approaches.
2 Background
2.1 MDPs
We model the Atari games as Markov Decision Processes (MDPs), We formalise MDPs, as described by Geffner and Bonet [2]. as the tuple of M = (S, so. A. R), where S g Rd. so E S is the initial state, A provides the sets of applicable actions such that A(s) is a set of actions applicable in s E S, T a set of distributions such that T(s, a, s') gives the probability of the transition from state E S to state s' E S given action As). and R is the reward function such that R(s, a) returns the reward for performing action A(s) from state x S. In this work we will be considering a special case, finite-horizon MDPs, where accumulated rewards need to be maximised over a given number of stages k- = I..... H. starting at a fixed initial state, so. Terminal states in finite-horizon MDPs are absorbing states. That is, if is terminal state and are at time step k, every action will map (s. k) into (s, + 1) and will be reward-free i.e. R(s,a) O. Our goal is to produce a policy, æ, that maps any given state into action, such that it maximises the expected accumulated reward received for an episode of the MDP,
argmax, JT E
R(sk, 7
(I)
where the expectation is over 5k+1 T(5 T (SK),, SK+1).
We assume that we have access to a simulator of the environment that given any state-action pair (s, a). where following the probability distribution T(s, a.s') and whether s' is a terminal state. In line with previous work 66 & [0] we consider only discrete action sets and states that represent the internal state of the Atari environment such that action transitions are deterministic, that is T(s, a, s') can only equal 1 for one state s' and 0 for any other state s", ",,"',"" s" S, s' # s" and a E A A()). Note that while the agent can use the internal Atari game state to set the state of the simulator, it can only directly observe the Atari screen's pixel value for any given state.
S and E A(s), the simulator returns the reward R(s,a), resulting state s'
2.2 Online Planning over simulators
In this paper we explore online planning over simulators by considering width-based lookahead algorithms for the Atari-2600 games. Lookaheads use simulator of the environment to consider rewards from different action trajectories from the current state into the future. An example of this is shown in Figure where lookahead is illustrated. We define the notion of lookahead as,
Definition 1 (Lookahead). A lookahead is defined as I. (N, C, sy) where N is a set of nodes defined as state-action paths starting at the root state of the lookahead sy, and C is a function that given a node E N and an action a A(s) returns the children of n, that is ne C(n, a) and ne N.

---

So
so
so
so (ott- ((
Rp
(ig.a-)- 0
(eggag) =1
Ap
(elgggg) -
Ro
(Degar) -
S1
$3
$1
$3
S1
$3 Vitul 10
Viss)
=1440)=
0SHA))=
Ols,a))= 10
S4
V((g)==
Vi(g)=
V(
Figure 1:
Example lookahead showing the action selection process for the root node sn following Definition 2 On the left, we have fully built lookahead. From left to right, we show the recursive process to determine what is the action be executed. The transition with action aj from so shown in green in the last diagram
the right is the transition added to the lookahead's critical path (Definition 3). The V. Q, and VT functions are as defined in Definition 2
Through backing up the rewards for each node in the lookahead, as shown Figure an expected value be found for each action applicable at the current state. That is, where n² the last state along the state-action path of node n1 the operation of backing up the rewards and selecting which action execute is,
Definition 2 (Action selection of lookahead). Given lookahead L= (N, C. S,) (Definition) D the action to execute is selected at the root ny, where nz. = Sy, by argmax AEA(E) (Q a)), where Q(n, a) Rnn a) + EmeC(mn,.a) T a, (n),, and (n) = (2)n), with V (n) being a termination cost, when UaEA(H)) C(n, a) otherwise V(n) max, RR(n,, a) En' T(n", a, a.n" Vnn"))
Once an action is selected for execution, the lookahead updated to have its root at the selected action's resulting node and the lookahead continues being constructed from the new root node. We define the action selected by the agent as part of its critical path. That is,
Definition (Critical Path). Given the action selected a, at each time step f = 0, I....,m following Definition 2 the critical path p is the sequence of states and actions p (so, ag, $1, dl. al..... am 11 5m). such that 5/+1 T(s,, (,, :) for = O, O....,Ph m
Related Work
3.1 MuZero
Schrittwieser et al. [1] followed up on the AlphaGo [13 and AlphaZero [14] algorithms with MuZero. AlphaZero is planning and learning agent that achieved state-of-the-an performance on the games of Go, Chess and Shogi [1]. AlphaZero learns a policy and value network that are used within Monte Carlo Tree Search (MCTS) lookahead through sampling actions according to the policy network and evaluating the states within the lookahead with the value function. Unlike AlphaZero, MuZero does not require simulator model of the game environment but instead learns a model of the environment through interaction. MuZero achieved Mate-offthe-ea performance in the Atari-2600 games when compared to existing model-free RL algorithm performances. We also explore using learnt value and policy networks within a lookahead but consider width-based methods as opposed MCTS. MuZero's experimental setting different the one considered in this paper as we require access to a simulator in the planning phase and use significantly less computing power.
3.2 Width-based Planners on Atari
Here will provide an overview of the different width-based planners which have been applied to the Atari-2600 problems. the next Section we go into the design and implementation details that each of the following planners use.
Width-basel planners [66] prioritise adding states to the lookahead with novel valuations of features that are defined over the states. IW(I) is bisth breadth- first search that is guaranteed to run in

---

linear time and space as it only expands novel states. /W(Z) considers state in the lookahead as novel if is the first state within the lookahead make a particular feature within the feature set true.
Width-based planners were first applied to the Atari-2600 games by Lipovetzky et al. (S), where they applied IW(1) over the RAM values of the game state as features. Lipovetzky et al., and subsequent
works that use IW(1) 17 18] show that it outperforms breadth-first search and UCT [19] planners.
Algorithm 1: Overview of the RIW(I) Algorithm
Input :A lookahead L = (N, C, and a base policy πb Output Updated lookahead I.
while - haa__solee__aabee (ordd_label(sss))) do
5' // complete depth-first rollout from the root node's state while is_ is_novel(s) A- is_ is_terminal(s) do
s'.a sample www.uoooooocclllleeeee
L - updatee_lookaeedd(L s, s'), 5t 5
end
podate_solvvd__abelss/
end
Bandres et al. 6 introduced depth-first version of the IW(1) planner, named Rollout- (W(t (RIW). RIW(1) aims to contain the same nodes that are expanded by the IW(1) planner. As RIW(1) performs depth-first search was argued by Bandres al. that it has better any-time performance than IW(1). The hypothesis for the better any-time performance of RIW(1) is that its search visits states that are further away from the initial state earlier in the search than its breadth-firs search counter-part IW(I). Algorithm[]] provides defined to use a random uniform base policy Th. however any given policy can be used instead. The function sample e_ unsolved_chhile
overview of RIW(I) using the base policy πь. RIW(1) was originally
(s)s) and transition s' ~ T(s, a) provided that s' has not been marked as solved. If the selected transition does not already exist in the lookahead update lookahead adds it. The update_ teddate_solvee solved labelll function adds solved label to the given state and back- propaaatss the solved label to its parents the parent's children have all been marked as solved. Bandres et al. results showed that RIW(I) outperformed IW(1) greatly when almost real-time budgets for planning were applied.
samples
action
Junyent et al. [8 follow up on Bandres et al.'s 6 use of a random policy for the base policy (x²) of RIW with x- III, an algorithm that replaces Ta with a trained policy defined over a NN. The intended effect is to orient the lookahead to promising areas of the state space. The NN from the trained policy is also used to extract features from the screen pixels for the computation of state novelty. Recently Junyent et al. [10) introduced x-IW(I)+ and H--I 1) as follow ups of I-). I-IW(1)+ modifies x1l's random breaking of ties for the action selection (Definition 2 to select the action with the branch of the lookahead that contains the most nodes. x-IW(1)+ also adds learnt value function, V, which is used in the action selection (Definition 2h by modifying V(s) to be max (s), (*))),, where V*()) is V(s) as described in Definition 2 (n,, 1) is hierarchical algorithm that has a high-level planner which uses a coarse down-sampling of the screen pixels as feature set and low-level planner which uses x-IW(() }+ with the feature set defined through the policy network as previously described. The high-level planner uses a modified stochastic exploration policy, that selects actions with probability inversely proportional state visitation counts.
4 Width-based Planning and Learning for the Atari Games
In this Section we step through different design considerations when constructing a width-based planning and learning algorithm. We compare the design decisions made by previous works and propose new algorithms to test over the Atari-2600 games.
4.1 Novelty Definitions: Classic and Depth-based
The novelty definition of width-based lookahead dictates which states to prune. In Algorithm | the novelty definition determines the output of the is_novel function. We refer to IW(1)'s novelty definition as the "Classic" definition and define it as,

---

Definition 4 ("Classic" Novelty). Given a feature set F = (ff......f.............. fi....,, s.t. fi SS - (T, and lookahead L= (V, C. sy), node n novel, if n contains the first state generated s.t. f(n') =T for some f F, that is, Vn' E N, f(nn*) = + and n' * n.
The "Depth" novelty definition introduced for RIW(1) by Bandres et al. 6 is,
Definition 5 ("Depth" Novelty). Given a lookahead L= (N, C, sy), newly generated node, n $ N, reached after doing d(n)) actions from Sy, is novel, if f(n") = T for some f E F, and Vn' E N, such that d(n') s d(n), (n" =1.
Later we show that in width-based planning and learning algorithm based upon the RIW(I) algorithm the original "Classic" novelty is competitive and can sometimes outperform the depth-based one over the Atari-2600 games. In what follows, refer to Bandres et al. 's original configuration of RIW(I) as RIW D and refer to RIW(I) where one replaces the "Depth" novelty definition with the "Classic" one as RIWC.
4.2 Features for Novelty from Graphical Game Outputs
Width-based methods require a feature set F to be defined over the observable state-space S. There two types of observations that can be used for the Atari-2600 games, the internal states of the Atari-2600 machine (the RAM), and the colours of screen pixels. Either of these enable features to be defined, as arbitrary Boolean functions over the observable variables. For the internal state observables we have b XX X variables, where b is the size of the Atari memory word (8 bits) and x is the size of the physical RAM given by the number of distinct memory addresses (128 addresses). There are с X w x h screen observable variables, where is 128, w is 160, and h is 210, corresponding to the colour depth, and the number of screen pixels along the horizontal and vertical directions.
When RIW(I) was introduced 66. Bandres et al. stated that features capturing mmeaningful structure" would yield better results than using raw features. Hence, Bandres et al. mapped the observable screen variables into the feature set B-PROST, first proposed by Liang et al. [3] The B-PROST feature set attempts to capture temporal and spatial relationships between the past and present screen pixel values. In order to compute the set of B-PROST features there are number of steps required. First a set of basic features needs to be computed through dividing the screen into 16 x 14 tiles comprised of 10 x 15 pixels. For each tile, (w, h). where w E (1...., 16) and h E (1...., 14), there are K features where K is equal to the colour depth of the Atari-2600 pixels (128). The basic feature in the B-PROST set is fw.h.c where c E {I.....K K} is true if the tile (w, h) contains at least one pixel with the colour value c. second tier of features, the Basic Pairwise Relative Officets in Space (B-PROS) set, is computed from the basic ones. A B-PROS feature fc,.o...jj. is true if fw.h.e, A fwtik++j.ez for any w, h. Finally, a third tier of features, the Basic Pairwise Relative Offsets Time (B-PRÖT) set, are computed. A B-PROT feature considers the current screen's 's tiles (w, h) and the previous game screen's tile (w', h') so that a feature fa f21. is true if fw. fw.b.q A fw'ti,ut+..c for any w, h where w' = w and h = h. The B-PROST set is the union of basic, B-PROS, and B-PROT feature sets.
The feature set can also be defined dynamically through NN 8. --IW, x-IW(I)+ and the lower level planner of x (n, 1) use a feature set that is defined as the output values of the rectified linear units from the last hidden layer of the policy NN treating zero values as 1 and positive as
T. The policy NN input are the last four screens, processed to map colours to a suitably defined grayscale, and down sampled to size of 84 x 84. While the policy network is being trained the features extracted through it will also change. This similar to Dittadi et al. (,, who use Variational Autoencoders ( (VAE) to learn set of features from the Atari game screen using a training set of game screens created from a RIW(1) execution using B-PROST. RIW(L) using the VAE features was shown to outperform RIW(L) using the B-PROST features.
While width-based planning methods using both the BPROST and NN extracted feature sets have been shown to perform well over the Atari games, previous width-based methods have not tested simpler feature sets defined directly over the screen pixel values. With the motivation of presenting a simpler width-based algorithm. we define our feature set directly over the values of the current down sampled 84 x 84, 8-bit grayscaled, observable screen variables. Each feature defined as fi.j.c and is true if the downsampled pixel (i. has the grayscaled colour c, where i E (1..... 84) and e E (I...., 256). Despite using a simpler feature set than previous work, in the next Section we show that our algorithm outperforms the methods that use dynamically defined NN based features.
5

---

Algorithm 2: Novelty guided Critical Path Learning (N-CPL)
// Perform K training iterations
for == ...... K do
T - 0, E 0 // Iteration's critical path transitions and episode rewards while train ittiinniinerral_exauuueeee
do
s - so. - 0, L - htt.-iiniiallisllloaaheeddde
while is_ (ttrmmiaatrmma((ss do
6
L-RIW(L, // Algorithm
a,r,s', L - select next_ teteeeeneee_ttnntiioollllo T - U (s.a,,,s,,)
// Selected using Def.2
R R+r
end
10
E - F RURUR Episode rewards from current iteration
11
end
// Train and update network parameters according to learning schedule
12
Tb, V' <
end
4.3
Learning Base Policies and Termination Costs
AlphaGo [13 and Æ-IW (8) showed the power of using learnt base policy defined through a NN in order to guide lookahead search. Similarly, AlphaGo and x-IW(1)+ [IO] also use learnt value function defined through a NN. x-IW(I)+ used its learnt value function modify the definition of ((n) (Definition 2 allowing the rewards received from the transitions in the lookahead to sometimes be ignored in preference of the value network's 's valuation.
We propose a new algorithm based on Algorithm 1, Novelty guided Critical Path Learning or N-CPL for short, that incorporates both learnt policy and value function network. An outline of N-CPL is shown in Algorithm 2. Like x-IW does, N-CPL. defines the base policy used by Algorithm to be a policy network. Besides that, N-CPL NN as a value function, which is evaluated at the non-terminal leaf nodes of the lookahead. Using cest-g--aprrximmttion has been shown significantly improve the performance of width-based lookaheads over stochastic shortest paths (20). but rather than using simulations to obtain the cost-to-go estimates, we rely on a learnt heuristic function. That instead of assigning termination costs, V", of 0 as done by previous midth-based methods, if the state is not terminal the valuation of the learnt value function network used. We note that unlike r-II(11)+ we do not use the learnt value function to modify the Vss) definition as defined in Definition
a cost-to-go approximation which
implement with
4.4 Learning from Critical Paths
The policy network of N-CPL uses the state action pairs, (sy.ay) o.....
of previous episodes performed by N-CPL with NN parameters, <0,². 0. >, in order to train new NN parameters 0x This is similar to how I-I trains its policy function, except for the fact that x-IW(I) uses the Q values within the lookahead tree. multiple actions in --W''s lookahead have the same value for given state, instead of the training vector assigning probability of one to the executed action, --IW uniformly distributes the probability across the actions with the same Q values. We have taken the simpler approach of just using 1-hot encodings for the single selected action along the critical path (Definition 3) of the N-CPL algorithm. Curating the training dataset in this way also means N-CPL does not need access to the internal data structures of the planning agent itself but instead can externally observe any agent interacting with the environment in order to acquire the training data.
Influential deep RL algorithms such DQN 2 which have been applied to the Atari-2600 games rely on evaluating an e-greedy policy defined over the parameters of its network in order to sample transitions and use Q-learning updates on the parameters of the network. We follow this strategy and perform Temporal Differential (TD) 21 learning to train the value network. The selection of the transitions that are used for the TD learning determines what the value function is estimating. That is, TD's task is to estimate the expected accumulated rewards from the given state following the policy which underlies the transitions that it is trained on. In N-CPL the transitions within the

---

Episodes executed with N-CPL< 0,,0% >
Episodes executed with N-CPL.<< Bf 1: >
E
N
E+t1
2
If te_t Bij <.11: 0.1:
-0-11 0ir1 2m 0f 0f-10-=1
0 0 >=< 00 57
Figure 2: Illustration of the schedule for the network parameter updates, <0 0²>, N-CCLL The E arrays contain episodes executed by N-CPL and each episode in the array is represented by a square in the diagram. The t_ test function returns the p-value for Welch's t-test [22] of the episode rewards executed with the old i - parameters being better than the new ones. S and oV are real vectors of the same dimensions as 6 and 6/ respectively. 07 and oy are functions over Ej.
lookahead follow the base policy, uy which is being learnt by aiming to mimic the policy induced from the N-CPL lookahead, TN-CPL. The N-CPL lookahead through selecting actions according to Definition can be seen as a policy improvement operator over тμ and hence the execution of TN-CPL is not necessarily equivalent to the лg. Therefore it does not make sense approximate the expected accumulated reward of the lookahead with the expected accumulated reward of T&. Instead, as shown in Line 8 of Algorithm 2, N-CPL. trains only the transitions on the critical path of the lookahead (Definition 3) that is, the transitions selected by an CPL. This results in the value function approximating the expected accumulated reward of executing TN CPL from given state.
4.5 Adding Learning schedule
The previous basth-based planning and learning methods continuously learn and update their policy and value networks, while a key mechanism of the Alpha-Zero algorithm [14] is the of learning schedule. Alpha-Zero evaluates each new set of network parameters 6' that are trained against the current set of network parameters 0 to ensure 6' improves A AlphaZero's performance. Here introduce general learning schedule mechanism that is applicable to sequentially executed and trained planning and learning methods applied single-player domains, that N-CPL uses for updating its network parameters for its policy network, 6x and value function network, ØV. As illustrated in Figure 2 the learning schedule determines whether network parameter updates <0," 0 > can be accepted or if the <BT 00 <, within N-CPL. This test is implemented in the peeddte_networ__poee Batooookpppamtttrreeeee function shown in Algorithm 2. For the test N-CPL performs a Welch's t-test [22] on its performance with the new i parameters vs. the old i- parameters. The update is rejected if the t-test suggests, with p-value of less than 0.1, that performance could deteriorate if the new parameters were accepted. This training and parameter update schedule allows learning steps to be completed each time step like done by --IW R except that the updated parameters are not used for data generation by N-CPL until they have been accepted by the proposed learning schedule.
parameters are kept, by evaluating their performance when used
5 Experimental Study
We benchmark width-based planning and learning methods with variations of the design decisions explained the previous section. Here we explain our experimental methodology and provide results across the different algorithms over the Atari-2600 games.
5.1 Methodology
Given vast compute resources it would be preferable to conduct full ablation study over the Atari-2600 benchmark on each element of a width-based planning and learning algorithm discussed in the previous Section. However, due to computational constraints we instead select five planners which will provide the most insight. Two of the planners we evaluate are based on RIW(1) without learnt policy or value function networks. One of the planners uses "Depth" definition of novelty (Definition 5) and the other uses the "Classic" definition (Definition 4 name these version RIW D
7

---

and RIWc respectively. Note that RIWp is as described in Bandres et al. except that the features are defined directly over the screen's 's pixel values as discussed in the previous Section. The other 2 width-based planners we benchmark are two versions of N-CPI., as previously described. Again we test both the "Classic" and "Depth" novelty definitions (Definitions) 4 5), and refer to them as N-CPL, and N-CPL-D respectively. For the policy networks of N-CPL and N-CPL.D we use the same architecture used by Mnih et al. [2]. The value network uses the same architecture as the policy network except that instead of the output layer being dense softmax layer with output for each action, the output layer of the value network is a dense linear layer with a single output value. Additionally we test version of N-CPL that does not prune for novelty, we refer as CPL, i.e. for CPL the is _s_novel function in Algorithm 1 always returns true.
We compare RIW D. RIWc. C, CPL, N-CPL, and N-CPLp to the x-IW, x-I+ and x-HIW I) planners with the results as given by Junyent et al. [TO]. We do not directly compare our results to those given in the original RIW(1) planner as Bandres et al. [6] use different experimental design. That is, Bandres et al. and previous works such as Lipovetzky et al. [5] benchmarked their width-based planners over the Atari-2600 games all using the full action set of 18 actions per state. We found in the code provided for the xII work that it was benchmarked against the games using the minimal action set for each game. Using the minimal action set results in many games having much smaller branching factors, for example, instead of Breakout having a branching factor of 18, it has branching factor of just 4. Additionally it is worth noting that the true average branching factor of each game is often much smaller than the minimal action set (33 and learning the minimal action set can help avoid unnecessary simulator interactions [18]. Due to computational constraints could not benchmark our algorithms over the games with full, minimal and learnt minimal actions sets. Instead, we decided to benchmark using the minimal action set as Junyent et al. [10] do.
The results are also not directly compared with those from MuZero due to discrepancies in the evaluation protocols and computing resource requirements. For example, MuZero uses smaller frameskip for the environment time steps and uses a longer allowed episode length of 108,000 frames compared to the I 18,00 frame maximum episode length we impose. While our experiments run on a single vCPU for each trial for both training and evaluation, MuZero required 40 third generation Google Cloud TPUs for each run, 8 for training and 32 for its self-play. Furthermore the results for MuZero on each domain were only made available for a 20 billion frame training budget. We do however provide comparisons with the RL algorithms DQN (2) and Rainbow (4, along with all the necessary caveats about differences in evaluation protocols, in the Supplementary Material.
For the evaluation of each algorithm on each game we run 5 independent trials. Once training has completed we evaluate each trial over 10 episodes. Following previous width-based planning papers 6 8 [0] we use a frameskip of 15. We keep our experimental settings the same as Junyent et al. [0] including a training budget of 2 x 10? simulator interactions and allowing 100 simulator interactions at each planning time step, which allows almost real-time planning. Note that previous width- algorithms have varied in how they apply planning budgets, Lipovetzky et al. enforce budget of 30,000 simulator interactions with frameskip of 5, while Bandres et al. enforce time budgets of 0.5 and 32 seconds with a frameskip of 15. We ran 80 independent trials at once over 80 Intel Xeon 2. 10 processors with 720GB of shared RAM,, limiting each trial to run on a single vCPU. The average vCPU run-time per time step needed across both the planning and learning steps were 1.28 and 1.11 seconds for N-CPL, and N-CPLp respectively, resulting in each trial taking just under 3 days to complete. For RIW and RIW p. which do not require any learning steps or evaluation of NNs, the average run-times per step were 0.55 and 0.54 seconds respectively. Note that given Atari operates at 60 frames per second and we use a frameskip of 15 real-time planner would be required to execute with run- run-time of 0.25 seconds per time step.
The transitions within the lookahead are cached inline with previous width- basth- planners 5 6
That is, when the search revisits transition between two nodes of the lookahead within the same episode, the simulator does not need to be recalled and hence does not affect the simulator budget. Also following previous work, transitions that are cached from previous time steps are not considered by the novelty Definitions 4 and 5 and hence will never be pruned.
5.2 Results
Table T summarises the results of N-CPL., N-CPL.p, CPI., RIWc, RIW,, IWI()), I-IW(I)+ and π (n, 1). Using the pairwise comparison of the different algorithms across the 53 games it is
8

---

Table 1: A pairwise comparison of the width-based planning algorithms over the full benchmark set made up of 53 Atari Games. Numbers represent the number of games an algorithm had a higher average evaluation score over the 5 learning trials than the algorithm it is being compared to.
Number of games with higher average than
N-CPL
N-CPLD
CPL
RIWc
RIW
sr-IW
x-IW++
JT ---HI
Total (ave, win %6
N-CPL
26
35
49
32
39
32
260 (70.1%)
N-CPLD
26
29
48
46
32
38
30
249 (67.1%) 1%)
CPL
18
24
43
45
31
39
27
227 (61.2%)
RIWe
3
4
10
23
19
18
17
94 (25,3%)
RIWD
18
17
103 (27.8%)
x-IW
20
20
22
33
32
30
25
182 (49,1%) 1%)
x--
14
15
14
35
35
23
23
1.59 (42.9%
--HIW
23
30
200 (53.9%)
Table 2: Same as Table [ [uut for games with a Branching Factor 10 (33 Games).
Number of games with higher average seore than
N-CPL
N-CPLD
CPL
RIWc
RIW
---W
w-IW+
--HIW
Total (ave. win %%
N-CPL
14
22
30
29
23
28
22
168 (72.%%)
N-CPLD
18
18
31
29
23
27
21
167 (72.3%
CPL
11
15
26
28
23
28
21
152 (65.8%)
RIWC
2
1
7
16
15
16
13
70 (30.3%)
RIWD
3
3
5
16
16
16
13
72 (31.2%)
19
94 (40.7%)
X-IW+
6
17
17
14
11
75 (32.5%)
--IIW
12
12
20
20
19
22
(50.20))%
clear that N-CPLd and N-CPL are the most performant. Comparing the "Depth" vs. "Classic" novelty definition methods as RIW W vs. RIW the former performs better than the latter. The superiority of the "Depth" over the "Classie" definition of novelty does not follow when using our CPL method. The "Classic" method of N-CPL slightly outperforms the "Depth" method N-CPL with Table I iindedd showing that N-CPL is the best performing algorithm overall. Interestingly our CPL method that does not use novelty pruning, still outperforms all previous methods which shows the large contribution learning and using the policy and value function networks, as described in the previous Section, has on performance.
To better understand the performance of the algorithms we segment the benchmark set according to couple of different characteristics. The game characteristics we examine are the branching factor, and the sparseness of meaningful reward feedback (SMRF). We consider rewards as meaningful when they provide information to player about how to maximise the accumulated reward of an episode. For a given game, SMRF is determined by executing a random policy and a Real-Time Dynamic Planner (RTDP) [24] over each of the games. RTDP is an online planner that uses a one step lookahead (Definition and an approximation for the termination cost V at each of the Icaf nodes. For the approximation of V (s') we use the accumulated reward from a random policy executed from s' for 10 time steps. We run both the random policy and RTDP for 50 time steps (750 frames). If the results from the RTDP planner are not better than the random policy according to Welch's t-test (2) with p < 0.1, the game is classified as having SMRFs. The results of the random policy vs. RTDP can be found in the Supplementary Material. For example, in the game of Pong, RTDP will be able to discover states through its 10 step approximation of Vt v'(s') where either player has scored. Using information from V' (s') about which players have scored, RTDP will be able to have better informed policy than the random policy, so Pong would not be considered a SMRF game. In game like Skiing, where a skier is required to ski down a mountain and pass through gates on its path down, RTDP will not discover any meaningful rewards in its 10 step rollouts. This is because in Skiing, despite a constant negative reward at each time step, there is meaningful reward feedback until the skier reaches the bottom of the mountain where a negative reward is applicd for each gate the skier missed.
Table T groups the games according to their branching factor. Comparing Table and 1 we can see that for games with larger branching factors, the relative performance gap between our N-CPLD and N-CPL planners and Junyent et al. 's II), I-IW(1)+ and x- (n, 1) increases as the branching factor increases. For example N-CPL and N-CPLp perform better than I-I+(1)+ in 28/33 (84.8%) games and 27/33 (81.87 (1.8%) games respectively for the games with a branching factor greater or equal to 10. However, for games with a branching factor less than 10, N-CPL. and N-CPI.p only perform better than -II+ in 1 11/20 (55%) and 1 11/21 (55%) games respectively.

---

Table 3: Same as Table but for SMRF games (12 Games).
Number of games with higher average than
N-CPL
N-CPLp
CPL
RIWc
RIWp
x--W
x-IW+
n --HIW
Total (ave. win %6
N-CPL
55 (65,5%)
N-CPLD
7
9
47 (56%)
CPL
7
9
11
11
8
9
7
62 (73.8%)
RIWC
2
6
3
23 (27.4%)
RIWD
22. (26.2%)
x-IW
4
4
5
8 4
3
29 (34.5%)
x-I
3
3
9
40 (47.6%)
7
48 (57.1%)
Table 3 compares the pairwise performance for games classified as SMRF games. Table clearly shows that the dominant method for the SMRF games is CPL, that is, the algorithm without novelty pruning. Table 3 also shows that the "Classic" novelty (Definition 4 methods outperform "Depth" novelty (Definition 5). These observations, that contradict previous claims in the literature, required careful analysis. We observed that the "Classic" method prunes states more aggressively, meaning it is more likely to reach states that are further away from the root node compared with the "Depth" definition. Similarly, the CPL method does not prune any states due to novelty, CPL's depth- first lookahead trajectories will always reach the lookahead search horizon of 100 time steps at least once, given that the lookahead simulator budget is 100 time steps. This results in CPI. on average searching for states that are further away from the root node than any of the novelty pruning methods. By definition, high rewards for SMRF games have a higher probability of being further away than games with dense rewards. Therefore, CPL and the "Classic" " novelty methods are more likely to discover the meaningful rewards by searching deeper in the lookahead. Interestingly CPL and N-CPL still outperform, yet are close to x-IW(II+ and (nHI I) on the SMRF games, despite x-- and π (n, 1) being motivated by such domains.
6 Discussion
We have found significant discrepancies in the experimental settings used in the previous width-based planning papers for evaluating their algorithms over the Atari-2600 games. We believe clear and consistent evaluation protocol should be set out for planning based algorithms applied to the Atari-2600 games to facilitate the direct comparison of their results. This could be similar to the evaluation protocol for the Atari-2600 games set out by Machado et al. (25), which was mainly focused towards RL agents and included recommendations episode termination, setting of hyper-parameteee measuring training data, summarising learning performance and injecting stochasticity. However Machado et al. do not discuss evaluation settings that are vital to the deterministic planning setting we have explored in this paper, such as planning budgets, and caching of transitions within lookaheads. We hope that by having identified 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, future research in planning agents for the Atari-2600 games can be more easily assessed. We were able to observe interesting patterns in the relative performance of algorithms through segmenting the Atari-2600 games by their different game characteristics. We are not aware of other works that analyse the performance of agents in regards to the characteristics of specific Atari-2600 games. We believe this taxonomy will provide useful insights into the behaviour of agents on the Atari-2600 games.
In this paper we have focused on width-based planning methods that have been applied over the Atari-2600 games. It is important to note though that these algorithms are defined in general way to operate over MDPs. We proposed new width-based planning and learning algorithms through the examination of different design decisions made by previous implementations of width-baser planners. These new algorithms, particularly N-CPL, are simpler implementations than the previously introduced width-based planning and learning algorithms III( and (n, 1). N-CPL defines its features directly over the grayscaled pixel colours of the game screen and uses a simplified novelty definition. Furthermore, N-CPL learns value function which is only used for cost-to-go approximations the leafs of the lookahead search tree. N-CPL also uses methodical learning schedule we introduced for training both its policy and value networks. We found N-CPL to outperform I-I,(I), -II+())+ and (n, 1) not only across the Atari-2600 benchmark, but also over subsets of games with large branching factors and games with sparse meaningful rewards. These results show that N-CPL's integration of planning and learning pays off for almost real-time planning over hard problems.
10

---

7 Acknowledgements and Funding Disclosure
Funding in direct support of this work: Australian Government Research Training Program Scholarship provided by the Australian Commonwealth Government and the University of Melbourne; the Defence Science Institute, an initiative of the State Government of Victoria; and computing resources provided by the University of Melbourne through the Melbourne Research Cloud.
References
[1] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
[2] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518:529, 2015.
[3] Yitao Liang, Marlos C. Machado, Erik Talvitie, and Michael H. Bowling. State of the art control of atari games using shallow reinforcement learning. In Proc. of Int'l Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pages 485-493. ACM, 2016.
[4] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski. Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proc. of the National Conference on Artificial Intelligence 2018.
(AAAI), pages
[5] Nir Lipovetzky, Miquel Ramirez, and Hector Geffner. Classical planning with simulators: results on the atari video games. Proc. of Int'l Joint Conf. in Artificial Intelligence (IJCAI), pages 1610-1616, 2015.
[6] Wilmer Bandres, Blai Bonet, and Hector Geffner. Planning with pixels in (almost) real time. In Proc. of the National Conference on Artificial Intelligence (AAAI), volume 32, pages 6102-6100 AAAI Press, 2018
[7] Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, and Christian Muise. An introduction to the planning domain definition language. Synthesis Lectures on Artificial Intelligence and Machine Learning, 1-(2) 2019.
[8] Miquel Junyent, Anders Jonsson, and Vicene Gomez. Deep policies for width-based planning. In Proc. of the Int'l Conf. in Automated Planning and Scheduling (ICAPS), volume 29, pages 646 654, 2019.
[9] Andrea Dittadi, Frederik K Drachmann, and Thomas Bolander, Planning from pixels in atari with learned symbolic representations. Proc. of the National Conference on Artificial Intelligence (AAAT), volume 35, pages 4941-4949, 2021.
[10] Miquel Junyent, Vicenç Gómez, and Anders Jonsson. Hierarchical width-based planning and learning. In Proc, of the Int'l Conf. in Automated Planning and Scheduling (ICAPS), volume 31, pages 519-527, 2021.
[11] Julian Schrittwieser, 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):604-60)) 609, 2020.
[12] Hector Geffner and Blai Bonet. concise introduction to models and methods for automated planning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 8(1):1-141, 2013.
[13] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, and others. Mastering the game of go with deep neural networks and tree search. Nature, 529:484-488 2016.

---

[14] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, and others. Mastering the game of Go without human knowledge. Nature, 550(7676):354, 2017.
[15] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 110064499)1140-11144 144, 2018.
[16] Nir Lipovetzky and Héctor Geffner. Width and serialization of classical planning problems. In Proc. of European Conference Artificial Intelligence (ECAI), pages 540-545, 2012.
[17] Alexander Shleyfman, Alexander Tuisov, and Carmel Domshlak. Blind search for atari-like online planning revisited. In Proc. of Int'l Joint Conf. in Artificial Intelligence (IJCAI), pages 3251-3251 2016.
[18] Yuu Jinnai and Alex Fukunaga. Learning to prune dominated action sequences in online black-box planning. In Proc. of the National Conference Artificial Intelligence (AAAI), volume 31, pages 839-845, 2017.
[19] Levente Kocsis and Csaba Szepevari. Bandit based monte carlo planning. In Proc. of European Conference in Machine Learning (ECML), pages 282-293, 2006.
[20] Stefan O'Toole, Miquel Ramirez, Nir Lipovetzky, and Adrian Pearce. Width-based lookaheads augmented with base policies for stochastic shortest paths. In ICAPS Workshop on Heuristics and Domain Independent Planning (HSDIP), pages 37-45, 2019.
[21] Richard S Sutton, Learning to predict by the methods of temporal differences. Machine learning. 3(1):9-44, 1988.
[22] B. L. Welch. The generalization of 'student's' problem when several different population variances are involved. Biometrika, 34(1/2):28-35, 1947.
[23] Mark J Nelson. Estimates for the branching factors of atari games. In Proc. of the IEEE Conference Games., 2021.
[24] Andy G. Barto, Bradtke, and S. P. Singh. Real-time learning and control using asynchronous dynamic programming. Artificial Intelligence Journal, 72:8 1-:81-138, 1995.
[25] Marlos C Machado, Mare G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018.
12


Reviews:
[{"review_id": "KBI68plvpUv", "reviewer": "Reviewer_Ae7H", "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. ", "questions": "", "limitations": "", "rating": 6, "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": "Novelty:\nAlthough 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.\n\nClarity:\nThe 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.\n\nScholarship:\nThe literature review is sufficient. \nIt 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.\n\nReproducibility:\nI 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.\n\nNotes:\nLine 34: “... we consider planners which use novelty measures directly over the values of screen pixels” - no justification is given for this decision.\n\nLine 61: “... we consider [...] deterministic action transitions” - Atari screen setting is not deterministic as far as I’m aware (as opposed to Atari RAM setting)\n\nLine 65: It doesn’t make sense to me to draw from T if you assume deterministic action transitions.\n\nLine 66: Why introduce \\gamma just to say that it's 1?\n\nDef. 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?\n\nLines 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.\n\nLine 90: Again, it doesn’t make sense to me to draw from T if you assume deterministic action transitions\n\nLines 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?\n\nLines 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\n\nIn 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$.\n\nLines 359-360: Is the taxonomy that you refer to just the binary quality of a game being SMRF or not?\n\nSummary: \nThe main idea of the paper looks promising, but sadly the clarity of this paper is subpar.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "GYkRaJZVWzJ", "reviewer": "Reviewer_XEoW", "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. ", "questions": "", "limitations": "", "rating": 7, "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": "The paper lists the following contributions (see last paragraph of Section 1):\n\n(1) analysis of previous IW algorithms for Atari games;\n(2) new IW-based algorithm\n(3) learning schedule\n(4) identifying characteristics of Atari 2600 games that influence the performance of IW-based planners\n\nContributions (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. \n\nThe 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. \n\nThe 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}.\n\nRIW+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.  \n\nAnother 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').\n\nStill 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. \n\nThe 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? \n\nI 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. \n\nOTHER SUGGESTIONS\n\nIn 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. \n\n\"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. \n\nReference:\n\n[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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "1QaBVDtbs0P", "reviewer": "Reviewer_RtGM", "summary": "  The paper proposes a new state of the art in planning-based approach\n  to Atari game.  The paper carefully analyses existing work, including\n  $pi$-IW+ which uses both value and policy functions, and fixes several\n  incorrect decisions that qualitatively does not make sense, such as\n  mixing up the estimate for the base and the critical path policy.\n\n  Perhaps what I would ask the authors is the way the paper is written:\n  The current text is not written in the style of \"They do X which has\n  this issue; therefore we do Y\" --- issue-focused description, but in\n  the style of \"We do Y; X does this; X is problematic\".  For example,\n  Sec 4.2 could be titled as \"Addressing the complex novelty definition\n  in RIW\", or \"Simplifying the novelty; depth-based novelty is not\n  necessary\".\n\n  The algorithm also has a mechanism inspired by AlphaZero, which\n  resembles active-learning (section 4.5), which compares the old and\n  the updated parameters.  Following up work should more carefully\n  evaluate this mechanism as an active-learning scheme.\n\n  Its second contribution is the proposal of a standard evaluation\n  scheme, which is now an adequate proposal due to the recent\n  improvement in the field.\n\n  The proposed algorithm is carefully evaluated empirically,\n  characterizing the sparseness and the branching factor.\n\n  This is a solid paper that I recommend for acceptance.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "  Throughout the paper, \"base policy\" could be replaced with \"uniform\n  random policy\" to make the meaning immediately obvious.  In the\n  current text, readers should trace the meaning back to line 120-121,\n  and it may still be a bit ambiguous.\n\n  l.134, and are hard to distinguish, consider alternative punctuations.\n  Well, shouldnt you just use V if and V are same?\n\n\n  There are quite a lot of variations of the algorithms.  I suggest\n  adding a feature comparison table between them.\n\n  The table row / column ordering in Table 1,2 could be reconsidered to\n  emphasize your proposed approach --- RIWD+CPB at the top.\n\n  There are inconsistencies in the references (conference names, etc.)\n\n  Regarding the full vs minimal action sets, [1] [2] are worth cited.\n\n\n\n  [1] Jinnai, Yuu, and Alex Fukunaga. \"Learning to prune dominated\n  action sequences in online black-box planning.\" Proceedings of the\n  AAAI Conference on Artificial Intelligence. Vol. 31. No. 1. 2017.\n\n  [2] Mark J. Nelson (2021). \"Estimates for the branching factors of\n  Atari games.\" In Proceedings of the IEEE Conference on Games.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\nThe 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

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)