Generalized Weighted Path Consistency for Mastering Atari Games
Authors: Dengwei Zhao
Shikui Tu
Lei Xu
Venue: NeurIPS 2023 poster (2023)
Keywords: Monte Carlo Tree Search
Reinforcement learning
Path consistency.

Abstract: Reinforcement learning with the help of neural-guided search consumes huge computational resources to achieve remarkable performance. Path consistency (PC), i.e., $f$ values on one optimal path should be identical, was previously imposed on MCTS by PCZero to improve the learning efficiency of AlphaZero. Not only  PCZero still lacks a theoretical support but also considers  merely board games. In this paper,  PCZero is  generalized into GW-PCZero for  real applications with non-zero immediate reward. A weighting mechanism is introduced to reduce the variance caused by scouting's uncertainty on the $f$ value estimation. For the first time, it is theoretically proved that neural-guided MCTS is guaranteed to find the optimal solution under the constraint of PC. Experiments are conducted on the Atari $100$k benchmark with $26$ games and GW-PCZero achieves $198\%$ mean human performance, higher than the state-of-the-art EfficientZero's $194\\%$, while consuming only $25\\%$ of the computational resources consumed by EfficientZero.

Generalized Weighted Path Consistency for Mastering Atari Games
Dengwei Zhao Shanghai Jiao Tong University zdwoccosj tu. edu. cn
Shikui Tu
Shanghai Jiao Tong University tushikui@sjun edu. cn
Lei Xu
Shanghai Jiao Tong University Guangdong Institute of Intelligence Science and Technology leixu@sj Leixu@sjtu.edu.cm edu.cn
Abstract
Reinforcement learning with the help of neural-guided search consumes huge computational resources to achieve remarkable performance. Path consistency (PC), i.e., If values on one optimal path should be identical, was previously imposed MCTS by PCZero to improve the learning efficiency of AlphaZero. Not only PCZero still lacks theoretical support but also considers merely board games. In this paper, PCZero is generalized into GW-PCZero for real applications with non-zero immediate reward. A weighting mechanism is introduced to reduce the variance caused by scouting's 's uncertainty time, it is theoretically proved that neural- surrallguieed MCTS is guaranteed to find the optimal solution under the constraint of PC. Experiments are conducted on the Atari 100k benchmark with 26 games and GW-PCZero achieves 198% mean human performance, higher than the state-of-ther -frtt----tttttttt EfficientZero's 194%. while consuming only 25% the computational resources consumed by EfficientZero.
the f value estimation. For the first
Introduction
In recent years, combining neural networks with search algorithms has achieved remarkable success in Reinforcement Learning (RL) [22 24 23 The application scenarios include not only board games but also knowledge- ffege--reeete free real-wor world problems [19]. One critical challenge is that huge computational resources are required to collect interactive experiences order to obtain reliable policy and value networks with remarkable performance. For example, 1000 third-generation TPUs were used to generate selfplay games in MuZero [9], roughly 10 ~ 50 years of experience per Atari game, which unaffordable in regular situations. It is essential for algorithm to achieve high performance with limited computational cost. Otherwise, it difficult to generalize the algorithm to more applications.
For sequential decision problems, an interactive process between agent and the environment regarded as a playing path, which is collected to update the parameters the policy and value network. In turn, the learned policy and value provide guidance for Monte Carlo Tree Search (MCTS) in determining the next action. This iterative process generates a large number of playing paths in order to obtain reliable policy and value estimators. The evaluation function f at state is defined as the summation of g(s)), the accumulated reward from the initial state 8p to 8t, and (())), the expected return received after 8t, which is equivalent the state value u(s.). That is, have
f(x) = g(s:) + h(st))
To find the optimal path L that leads to the desired termination state, the A search algorithm 5 establishes an optimality condition for values, i.c., fs;) fso) for all 8; L*, where so
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the initial state that definitely belongs to the optimal path. In 1987, CNNEIM-A [30 relied on this optimality to improve A by estimating the f-values on L with the average of the f-values on the historical trajectory and on a lookahead scouting segment, plus revealing an implication that the f-values are regarded as i.i.d. samples from a same distribution. This idea has been adopted to equations. (aaiiiioonnnn((8))) (8)&())&(()))))))))))) (10) in (29] with regularization term added into the loss function of deep reinforcement learning such as AlphaZero [23]. The term aims at reducing the deviation of f()) from ones on L towards satisfying path consistency (fC)-"f values on one optimal path should be identical". Simplifying equation (10) in (29] by considering Le error and ignoring weighting, recently PCZero [3 realised the PC constraint for the first time by considering
[(0) = (0) + ALrc(O),
(2)
where LRI (0) is the loss function of AlphaZero, À is a hyperparameter, LPC is implemented as (v((t) )2, the squared La deviation of the state value v(s)) from the learning target 6(8)). which is the average state value along the estimated optimal path. Experiments on three board games have demonstrated that PCZero improves the learning efficiency of AlphaZero.
However, ignoring weighting by PCZero is oversimplified because deeper states along the search path have greater uncertainty due to the exploration randomness of self-play and policy reanalysis [19. Thus, it is essential to take into account of the uncertainty levels in L Also, PCZero has only been applied to board games, wherein the immediate reward is always zero until the game terminates. Thus, g(x)) = 0 holds for all states in PCZero, while PC has degenerated into the consistency of state values. It is unclear whether PC is effective generally as suggested by equation (8) in (2) to take ((x)) in consideration for applications with non-zero immediate rewards, such as Atari games. Moreover, there lacks a strong theoretical support for the effectiveness of PC, and the advantage conferred by the PC constraint has not been clearly explained.
This paper tackles the above problems by generalizing PCZero into GW-PCZero (short for Generalized Weighted PCZero), with the main contributions summarized as follows
The application of PC is extended scenarios where the environment emits immediate rewards, such as Atari games. Loss function in EfficientZero (32] is adopted as Lat (0) in Eq. (2). instead of using the loss function of AlphaZero like PCZero [33. (0) ensures the consistency of f values in Eq (I) across the search path, rather than only maintaining
the consistency of h value like PCZero. f(s)). the mean of the values of states along the path, is adopted as the learning target for LPC.
weighting mechanism is introduced for accurately estimating f(s)). States farther away from 8, are considered less reliable and given larger discounts to reduce noise in f(t)). Experiments are conducted on the Atari 100k benchmark with 26 games to evaluate GW-PCZero diverse environments. Under the same computing resource consumption, our GW-PCZero achieves 198% mean human normalized performance, sig- nificantly outperforms the state-of-the-e EfficientZero's 121%. Additionally, GW-PCZero surpasses the original version of EfficientZero, which achieved score of 194% 32 while utilizing only 25% of the computational resources required by EfficientZero.
An uncertainty-an
For the first time, it is theoretically proved that neural-guided MCTS is guaranteed to find the optimal solution under the constraint of PC, and that the optimal solution for minimizing (s:( is achieved by satisfying the multi-step temporal difference (TD) value estimation relationship between state s, and its neighboring states in the same path. Instead of estimating state value independently, PC leads to a more reliable value estimator.
2 Related work
The Arcade Learning Environment (ALE) is an evaluation platform that contains plenty of Atari games, which is used to evaluate the general competency of Al agents (2). Interaction steps are restricted to 100k, which is roughly two hours of experience for human [14]. to explore models' sample efficiency. SimPLe [ further selects 26 games from ALE on the basis of being solvable with existing state-of-the-art reinforcement leaming algorithms, which is adopted as the benchmark
by many following works 9 12 20 31
13 16].
So far, EfficientZero 32 is the only model that
'The source code is available at https: htt.://a.....eo//acC////////////

---

has achieved super-human performance on Atari 100k. Here, our generalized PC is applied to EfficientZero and improves its performance with theoretical support.
A search algorithm (5), the heuristic function (() is used to approximately estimate the optimal
cost (*) to guide the search process. If [(s) never over-estimated, A search will be guaranteed to find the optimal solution. Otherwise, A search may fail. MCTS [T)] [ is best-first search method, which is generally not guaranteed to converge to the optimal solution. UCT [TO] chose Upper Confidence Bounds (UCB) [T] MCTS's tree policy to do simulations, and it has been proved that UCT definitely finds the optimal solution for the infinite memory case [TT. UCT evaluates states by simulating the real outcomes by fast rollouts in Monte Carlo manner, which provides reliable information for making decisions. However, feedback value used in neural-guided MCTS in recent RL algorithms [23 19 is provided by the predictive value network. The decision's quality highly depends on the guidance network. The optimality of MCTS is only established for part of heuristic functions and neural-guided MCTS will hardly find the optimal solution if the value estimation is poor. Though originated from A search, PC was also promising on MCTS with deep RI. algorithms like AlphaZero [29 33). In this paper, we prove that when constraining value estimator with PC, neural- goural-guided MCTS used in those modern RL algorithms is guaranteed to find the optimal solution.
3 Preliminary
3.1 Path consistency
For a Markov decision process (MDP), the agent observes state 8, from state space S, chooses an action 0++1 from action space A, and receives reward r++1 according to the mapping S x A IR. Starting from 8o, a playing path L consisting of nt + 1 states is generated while the agent interacts with the environment for nı steps:
L { $1, $2,
11, $
If Sn, is the preferred termination state, i.e., the path L receives the most accumulated reward, then becomes the optimal path L In Eq. (1) g(s)) the accumulated reward from 80 to 8, and the f value can be reformulated as
f(s)) = g(s)) + u(s;;)) = Σ + v(s; Ase E L.
(4)
where v1 0) is the state value estimated by the policy-value neural network with parameter 0. The general PC is defined as the consistency of values.
Definition 3.1. Path consistency (PC for short) is that f values of states along any optimal path in a search graph should be identical, i.e.
f(00) = =[(1))
= .... (. L.
(5)
3.2 The neural-guided Monte Carlor Tree Search (MCTS)
In MCTS, for each possible action a E A in a given state set of statistics is used to record the situation, including visit count N ((s,, a), prior policy p(als), cumulative reward from multiple simulations W(s, a), and reward r(s, a). The action value Q(s, a) is calculated as W(s, a) a)/N(s, a). Starting from the current root state st, each simulation first traverses to leaf node s44e by maximizing over probabilistic upper confidence tree (PUCT) bound at each time-step, i.c.,
a(s,
+ p(a'ls) V VEEA N(s,a')
a arg max a'E.A
(6)
I+N(s,0')
The children states of 8t4e are expanded and v($r+e) is backed up to all edges (st, a-11) in the traversing path {(St, ((+1), (st+1,0t+2), ... (81+8-1, ((+e)) via
N(s,, 0:t1) + N(si, (4+1) +1,
(1
((s,0:41) + (88,0;111) +
Σ
o T + - (((4))))))
(7)
T=0
3

---

where y is the discount factor. If y is set to 1.0, the above equation is rewritten as:
(s; a:+1) +- (s,, as+1) + (s(+e) - ((;)..
(8)
After K time simulations, the action with the maximum visit count will be selected as the next move, and the selected child will become the new root of the search tree.
3.3 Reanalyze
To improve the sample efficiency, MuZero 19 proposes reanalyze technique to revisit its past time steps. MCTS is re-exccuted with the latest model parameters, potentially resulting in a better-quality policy cuurent than the original policy oold The (-step bootstrapped value target is estimated based on multi-step TD value relationships
Σ 1=1
rets + ((((0)))))))
(9)
The reanalyze technique updates 2 with the most recent value network parameters (curvent Effi- cientZero [32 employs an off-policy value correction method, which conducts an additional MCTS to estimate the value as MCTS ($t+1: and computes 2; by replacing 0($++1; 6) with MCTS (st+1 0) in Eq. (9). Enabling off- off-policy value correction for reanalysis requires running two MCTS for each sample, resulting a doubling the computational cost.
4 Methodology
The proposed GW-PCZero is built on EfficientZero with a generalized PC constraint. The PC constraint enables our GW-PCZero which has a significant contribution to the performance of EfficientZero, but also improve the performance surpass EfficientZero with theoretical guarantee the optimality. The loss function for learning the policy-value network is taken as the same form of Eq. (2). Different from PCZero, here CRL(0) is set to be the same EfficientZero's loss function, consisting of policy loss, value loss, value prefix loss, and self-supervised consistency loss (32), while CPc (f) is evaluated by the deviation of f value from its mean along the path. Specifically, on the state 8t, we can rewrite the squared L2 deviation [f(s) - f( by noticing v(s;; () = h(s;) in Eq. (1) as follows:
only remove the time-consuming off-policy value correction
(s 0) = {u(s; 0) - [f(()) g(s))))²
(10)
Built the basis of MuZero, EfficientZero has achieved superhuman performance Atari games [2] with limited 100k training data. EfficientZero has made three critical changes to MuZero. First, self-supervised consistency loss was proposed to help model the environment's state transi- tion dynamics. Second, one-step reward prediction was replaced by the estimation of value prefix E Σj=1 E rttj. Third, MCTS value target correction was executed by replacing the valicy-value network's output with root values estimated by MCTS. To take advantage of the merits of Effi- cientZero, we keep the first two changes and disable the third one, because the MCTS's root value target correction doubles the need of computing resources. Experimental results indicate that values estimated by the network trained under the PC constraint is more reliable than this time-consuming value correction method. With the help of the PC constraint, our method is able to improve the efficiency of the policy-value network parameter learning and save computing resources.
4.1
The optimality of the PC loss
is noted from Eq. 10p that (PC(st) is the square error loss and (Pc(st) 2 holds. We present the following theorem for the optimality of the PC loss.
Theorem 4.1. The PC loss of state 8t achieves the optimal value when the following equation holds:
v(st) = Σ T o(s), i>t,
j=t+1
(11)
v(si)
Σ j=i+1
ra + v(s)), ist

---

The above Eq. (TT) actually represents the multi-step TD value estimation relationships between St and all other states (sili in the same path.
The estimated values given by an effective value function predictor should satisfy the multi-step TD value relationships specified by the Bellman equation. Theorem [.1 indicates that Lrc will be minimized if multi-step TD value relationships are established for the estimated values, indicating that path consistency is nature that a well-learned value predictor should have. The term of PC loss guides the learning process towards it proactively, which gives an explanation about why the adoption of PC improves learning efficiency. State values learned by minimizing Lrc will establish the relationship among them, rather than learning the value predictions for different states independently, In particular, by setting discount factor y = in Eq. (9), the bootstrapping target for the state s; 's value learning in MuZero becomes the right formula of Eq. (TT), implying that PC is beneficial the learning of value estimation. It should be noted that Theorem 4.1 is also established for any Tp norm deviation loss with p 2 1, not limited to L2 norm used in this paper.
To prove Theorem 4.1 we define I (+)) = f(s)) - g(s)) as the learning target for the value network
in Eq. (10), and let ((t) be the mean over all states in the path L. Based on Eq. (3) & 4 Lpc(s is equivalently derived to be
1
Lrc(st; 0) = 1
Σ
v(sc:0)-
Σ Ty + ((ss))
(nz + 1)2
831
1=
1
u(si) -
Σ 1=++1
+ + 0(06:0)
(12)
ist
According to Eq. (12). the PC loss is a square error function with (sc e; 0) 2 0. When the multi-step TD value relationships by Eq. (IT) are satisfied, each term in the square brackets of Eq. (12) equal to zero. Then, Cpc(s;: 9; 0) is minimized at zero, and it implies that PC is established, which suggests that Theorem 4.1 holds. The derivation details of Eq.
are given in Appendix 1.
Previous research extensively employed TD error for training value function models in various algorithms. Minimizing TD error is commonly utilized learning objective among model-free RL algorithms, such as Q learning (28) and its variants [15] (2 6 (2). For model-based RL algorithms,, the TD error is employed as one of the auxiliary training objective during the learning process of the environment model. Dyna (55 updated the estimated values to be consistent with the environment model by minimizing the TD()) error, while TD(k) is adopted by value equivalent models, such as MuZero [9 and Muesli 7 SCZero 4 utilizes the TD(0) error to update the environment model and value function simultancously to encourage them to be jointly self-consistent, demonstrating that the TD constraint on value estimations is beneficial for both policy evaluation and environment model construction. Compared with those TD based algorithms, PC is global constraint for all states on the optimal path. As illustrated in Eq. (12). PC loss of is minimized if the TD errors for state s with all states on the same path are minimized to be O, while TD error itself represents a local constraint that pertains to the relationship between two states. The PC constraint on state 8, encompasses both consistency with subsequent states and consistency with preceding states. In contrast, the TD error only takes into account the consistency with subsequent states. Both SCZero and our GW-PCZero propose a consistency constraint to improve the learning efficiency. SCZero A is built model-based algorithms, encouraging the learned environment model and value function to be consistent by minimizing the TD(0) error. The concept of path consistency, explored in this paper, is conceptually different from the notion of self-consistenc discussed in SCZero. PC requires that estimated f values on the same optimal path are consistent, which is applicable to all value-based RL model- framework.
algorithms, regardless of their reliance
We further prove that the PC constraint on the estimated values guarantee the coural-guided MCTS to find the optimal solution, under an assumption below, which is made from the perspective of probability based on Definition 3.1 We use the notation N(u, a²) to denote normal distribution and use Pr(u o to denote an arbitrary distribution, where μ denotes mean and o² denotes variance.
Assumption 4.2. For the state s on the optimal path, suppose f(s) pb; For every state s' not on the optimal path, (f(')) are assumed to be sampled from an i.i.d. Pr(uf,of) of).
5

---

The M6 and uf are the expected total rewards for optimal and non-optimal solutions respectively according to the definition of f, and the inequality 1/ > nf holds.
Theorem 4.3. Under the PC condition, Pg. defined as the probability of finding the optimal path with the neural- neural-guided MCTS, satisfies the following inequality as the number of simulations K goes sufficiently large,
lim K+0
Pg
II t=1
RL
1 exp
(e m1)1 20//K² K*
1
m-1
(13)
where by is constant, and K' is the minimum simulation times for nodes in the search tree.
The proof of Theorem 4.3 is given in Appendix 2. Intuitively, K goes large (K -> +00), every child in the search tree will be visited enough times because of the exploration term in Eq. (6), leading to K" + +00. Then, the lower bound of Eq. (13) approaches one, which pushes the probability of finding the optimal path be one. Formally, we have the following result.
Theorem 4,4. For any Markov decision process, the neural- neural-guided MCTS with path consistency as the constraint of the estimated values is guaranteed to find the optimal solution, when the number of simulations K is sufficiently large,
lim Pg 11 K-+00
(14)
4.2 Empirical computation of PC on consistency
Considering that interaction sequences in practical applications like Atari games are quite long, the generated samples used to update parameters before reaching the termination. In practice, the state s, and its l following unrolled states are sampled from the replay buffer as a small training batch La {st, $141.''' St+e), } Reanalyzing is adopted to re-estimate the learning target with the latest policy-value network for all states Ly- States in La share part of the cumulative reward before st- The PC target Pe for the value network in Eq. (10) is calculated as
Σ tsc(s:) 1+1 1=0
T4i + v($++:00) Σ
(15)
Only 8t considered to constrained with PC loss in real implementation because the sampled batch Ly is too short to deal with the subsequent states in the same way. The reanalyze technique is used to prepare the learning targets for policy and value without enabling off- off-policy value correction. All target preparations are summarized in Algorithm
Algorithm 1: Sample Preparation for GW-PCZero
Input: Replay buffer R, Unrolled steps I, Batch size N. Output: (T, 2, (c)).
1: Sample N unrolled sequences from R and each sequence consists of ( + consecutive states.
2: for each sampled sequence L; = {st, s ... , do
iteration MCTS for each state in L;- 4: Recalculate value target by bootstrapping in Eq. (9) for each state in L,.
3: Reanalyze policy target by performing
5: Estimate PC target t (8t) according to Algorithm
6: end for
7: return Tuple (M, z, k,tr)).
4.3 Weighting the PC target
The estimation of (p((s:) in Eq. 15 takes the mean of all f values, treating all states equally. However, the states far away from 8, are less reliable than the ones near 8,, which is mainly caused by two operations, as shown in Figure One is the exploration uncertainty during the iteration process with the environment. As 81+1 sampled from the policy distribution injected with noise, it may not be the optimal choice. The other more important reason is policy reanalyzing. As illustrated in

---

the right of Figure 11 Sc+1 is the following state of St in the real iteration sequence collected with an older policy n but the optimal choice of the latest reanalyzed policy Tuurrent may be another state 81+1, According to Definition 3.1 PC requires that all states should be on the same optimal path, and it will be violated due the above two operations. Especially, the probability that 8t4- and S, are not in the same optimal path grows as increases.
m(( *
Si+1
Si+2
S2+1
(Stua)
tepes
S++
st+1
stt1
st+1
Sc+1
S1+1
n($t.1) = N(s 1 ~ (H,
State collected with x
Optimal state under x current
Figure 1: Left: exploration uncertainty when playing the game. Action is sampled from and is Gaussian noise. Right: difference between collected sequence {st-i} and current reanalyzed policy's optimal choice {+]+1)-
In order to mitigate the high variance brought by the above uncertainty, a weighting mechanism is devised to give larger discount to farther states. Specifically, (s,(s,) is calculated by a weighted summation and the weight w; decreases linearly with index i.e.,
Wi max Ca i, 0},
(16)
where ca and с are two constants, While there numerous algorithms available for weighting, the linear weighting method employed in this paper is simple and highly interpretable, which deserves further investigation in future research. The PC target LPC calculated as:
(pc(s:)
=
Σ W 2=0
Σ
T4i + o(st+i0))
(17)
where Wi -w// Ei Wi is the normalized weight. The details are summarized in Algorithm
Algorithm 2: Weighted PC target Pp estimation
Input: S {st, r++1, 8141,'' stt1,, value function v(s).
Output: Target (st).
1: Initialize the value summation T +- 0 and weight summation W + 0.
2: for each state s in S do
3: Calculate weight u for state stti according to Eq. (6)).
4: T X
Σ rets v(stte) W + W + wi
5: end for
6: return target (s:) T/W.
4.4 The coefficient for the PC loss
PC is incorporated into the policy-network learning as a regularization term in Eq. (2. and there non-negative coefficient À be determined. GW-PCZero degenerates back variant of EfficientZero (without MCTS value target correction) when À 0. In general, an appropriate À is required balance between maximizing the accumulated reward and satisfying the PC constraint. According to the empirical experience of PCZero on Hex game [33], it has been found that PC improves the generalization ability for testing while sacrificing the prediction accuracy for training. For games with low complexity, it is easy to generate all possible states for training and À should be small improve the training accuracy. For games with high complexity, the generalization ability should be paid more attention by giving larger X. See the details in Appendix 3.
7

---

Therefore, À is adjusted with the game complexity, which is evaluated by two criteria. One is the action space size AA,, which determines the number of brunch factors for search. The other is the difficulty for the computer program to master, which is approximately evaluated by Dm MuZero Score/ Human Score Atari games, where MuZero is trained without 100k limitation. In the experiment, if |A] < 18, À is set to be 0.2. For games with [A] 2 18, if Dm is larger than 100, indicating that this game easier to master, will be set to be 0.35. Otherwise, this game difficult to master, and À 0.4.
5 Experiments
Experiments are conducted on Atari 100k benchmark containing 26 games [8]. Only 100k interaction steps are allowed to collected, i.c., 400k frames based on a frameskip 4, which roughly the number of experiences played by human in two hours. The mean performance of human players was collected [7]. which is used to evaluate the model's performance against the baseline of the random player's s score. The human normalized score of learned agent is defined (Scoreagent random / [Scoremumnn Scorerandom)
Table Comparison of different algorithms. The computational cost is measured by the number of MCTS executions,
Value correction
Weighting
Adjustable c.
Frames
Train steps
Cost
Score
EfficientZero
N/A
N/A
100k
120k
61.54M
1.943
EfficientZero"
X
N/A
N/A
60k
15.46.M
1.218
G-PCZero
X
X
100%:
60k
15.46M
1.378
GW-PCZero
X
X
1004:
60A
15.46M
1.980
GW-PCZero(c.)
X
V
100k
60k
15.46.
2.066
Table 2: Scores the Atari 100k benchmark tested with 32 evaluation seeds. Benchmark methods include SimPLE (8), CURL(12), DrQ [31], and teRers [16). EfficientZerol [32 is retrained under the same computational resources GW-PCZero.
Game
Human
SimPLe
CURL.
DrQ
RfficientZemt SPR+resets
G-PCZero
GW-PC7ero
Alien
7127.7
616.9
558.2
771.2
911.2
850.6
761.3
699.7
Amidar
1719.5
88.0
142.1
102.8
201.7
60.6
91.6
97.0
Assault
742.0
527.2
600.6
452.4
953.0
994.8
1224.1
Asterix
8503.3
1128.3
734.5
603.5
1005.8
17734.4
15712.5
14771.9
BankHeist
753.1
34.2
131.6
168.9
547.0
276.9
280.9
207.2
BattleZone
37187.5
5184.4
14870.0
12954.0
8821.2
15875.0
13875.0
13500.0
Boxing
12.1
9.1
1.2
6.0
32,2
28.2
11.8
41.6
Breakout
30.5
16.4
4.9
16.1
23.4
366.7
402.7
450.0
ChopperCmd
7387.8
1246.9
1058.5
780.3
818.8
1221.9
1150.0
Crazy CrazyClinerr
35829.4
62583.6
12146.5
20516.5
28936.2 2
8059.4
8031.3
9734.4
DemonAttack
1971.0
208.1
817.6
1113.4
2778.0
7940.8
15163.4
24074.1
Freeway
29.6
20.3
26.7
9.8
18.0
0.0
0.0
0.0
Frostbite
4334.7
254.7
1181.3
331.1
1834.3
229.1
245.6
249.7
Gopher
2412.5
771.0
636.3
930.4
1325.6
1286.9
Hero
30826.4
2656.6
6279.3
3736.3
6735.6
7537.2
9958.1
8171.3
Jamesbond
302.8
125.3
471.0
236.0
415.7
300.0
298.
525.0
Kangaroo
3035.0
323.1
872.5
940.6
2190.6
525.0
1012.5
262.5
Krull
2665.5
4539.9
4229.6
4018.1
4772.4
3818.5
4233.0
7782.0
KungFuMaster
22736.3
17527.2
14307.8
911L0
14682.1
8956.3
10059.4
205-13.8
MsPacman
69516
1480.0
1465.5
960.5
13216
967.5
7S4.7
1594.1
Pong
14.6
12.8
16.5
-8.5
-9.0
15.6
19.8
19.8
PrivateEye
69671.3
58.3
218.4
13.6
82.2
0.0
100.0
96.9
Qbert
13455..0
1288.8
1042.4
854.4
3955.3
8120.3
8281.3
1365
RoadRunner
7845.0
5640.6
5661.0
8895.1
13088.2
3443.7
9262.5
16809.4
Seaquest
42054.7
683.3
384.5
301.2
655.6
478.1
768.1
UpNDown
11693.2
3350.3
2955.2
3180.8
30185.0
7592.5
6129.4
123444.7
Norned Mean
1.000
0.443
0.381
0.357
0.901
1.212
1.378
1,980
# > Human
2
2
7
11

---

Table 3: Scores on the Atari 100k benchmark with different in Eq. 16
0 means no weighting.
Ca 0.1 has been used Table 2
Ca
Seaquest
Asterix
Boxing
Alien
BattleZone
0.0
838.1
15712.5
11.8
761.3
13875.0
0.05
1215.6 6
22131.3
22.0
568.1
14281.3
0.1
768.1
14771.9
41.6
699.7
13500.0
0.2
776.9
14950.0
53.8
982.5
16812.5
Breakout
Qbert
KungFuMaster
Krull
Kangaroo
0.0
402.7
8281.3
10059.4
4233.0
1012.5
0.05
443.9
12568.8
12575.0
6874.9
787.5
0.1
450.0
13651.6
20543.8
7782.0
262.5
0.2
396.7
11269.5
10990.6
2182.5
206.3
In EfficientZero [32]. MCTS consumes the majority of computing resources, much more than network updating. The number MCTS is determined by two factors: data collection, which requires 100k: MCTS for 100k steps, and data reanalysis. 120k updating steps are performed with batch size of 256. A total of 30.72 million samples are reanalyzed, with each sample requiring two MCTS runs: one for policy re-estimation and the other for MCTS value correction. Thus. total of 61.44 million MCTS runs are used to prepare the training data, and the computational cost for data generation is relatively negligible. Therefore, the limit of 100k interaction steps does not fully constrain the computational resources used, and the total number of MCTS runs should be considered. Due to the reanalysis operation, EfficientZero requires total of 61.54 million MCTS runs, which accounts for the majority of the computational resources consumed.
In this paper, we evaluate our GW-PCZeno's learning efficiency under more difficult setting than the original EfficientZero 32). As summarized Table [] the updating steps are limited to 60k, and MCTS off-policy value correction is disabled. Models in our experiment only consume 25% computational resources of the original EfficientZero. G-PCZero included for comparisons by using the unweighted computation of the PC target in Eq. (5). EfficientZerof is retrained under identical conditions. Experiments are conducted on 4 NVIDIA Tesla A100 GPUs with 16 CPU cores. We с 1.0 and Ca 0.1 1 in Eq. (6).. Totally 32 of different random seeds used. Other hyperparameter settings are the same as EfficientZero, as summarized Appendix 5.
The mean testing results are reported in Table 2 GW-PCZero performs better than EfficientZerof 19 out of all 26 Atari games. The mean of the human normalized score of GW-PCZero achieves 198.0%, much higher than EfficientZeroo's 's 121.2%. Moreover, GW-PCZero slightly outperforms the original EfficientZero (32), which achieved a score 194.3%. should be noted that GW-PCZero only consumes 25% computational resources of the original EfficientZero, shown in Table [ Experiment results demonstrate the effectiveness of our GW-PCZero, and indicate that PC improves the learning efficiency remarkably in Atari games. Notice that GW-PCZero performs poorly in several games requiring great exploratory, such as Freeway, probably due to the quick convergence of PC. Moreover, examples of learning curves of GW-PCZero and EfficientZero" Atari games displayed in Appendix Analysis of test variances included in Appendix 4.
GW-PCZero outperforms G-PCZero in 15 games and achieves significantly higher mean normalized score. This ablation study indicates that the weighting mechanism important to provide a more accurate target for PC learning. The performance is greatly improved by considering different uncertainty levels in the states along the path while calculating the mean f values. It is critical to observe that G-PCZero outperforms EfficientZerol in 16 Atari games, and its mean score of 137.8% slightly higher than that EfficientZerol, indicating that PC improves the model's performance even without the weighting mechanism. We also employ the weighting mechanism in PCZero (33] and conduct experiments on board games. The game performance exhibits improvement as well. Details are included in Appendix 7.
Path consistency requires that / values on the optimal path should be identical. The selection of the optimal path from the collected interaction experiences is not only necessary but also presents significant challenge. Due the difficulty of definitively determining the optimality of particular path, one alternative approach is to strive for the collection of training paths that are near-optimal, thus

---

satisfying the requirement of PC. In on-policy reinforcement learning, game experiences collected through interactions between the updated policy and the environment improve gradually and approach near-optimal level throughout the training process. Alternatively, near-optimal paths obtained from human experts or other high-level computer players can also fulfill the requirement of PC, allowing the model to be trained in an off- manner. Both aforementioned training approaches have been demonstrated to be effective in PCZero [33]. The critical factor for the success of PC lies in the selection of the optimal path, and is relatively unaffected by whether the path is collected through on-policy or off-policy methods. However, in many scenarios, the availability of near-optimal paths provided by experts is limited, and on-policy learning methods demonstrate low sample efficiency, Therefore, in addition to the aforementioned methods, it is crucial to investigate the training of PC using suboptimal paths. For example, game frames in Atari 100k are collected using a poorly trained model in the early state, which are far from near-optimal. GW-PCZero implements a weighting mechanism address the limitation of suboptimal paths by excluding unreliable nodes along the collected path from consideration, and experimental results in Table demoosttrte the effectiveness of this node filtering approach.
We further investigate the weighting mechanism in more detail. As shown in Eq. (66), linear decay is adopted from the initial value с 1.0, with the decay rate controlled by ca. A larger ca gives less weight to the latter states, while Ca = 0 represents the situation without weighting. The effects of ca are illustrated in Table The optimal ca varies across different games, indicating that there is still room for improving the weighting strategy. On one hand, more reliable neighboring states should be considered to reduce the variance of the mean f value. On the other hand, unreliable neighbors increase uncertainty in the estimation of the mean f value. Ca is to achieve a trade-off between including more neighbors and reducing unreliability. Notice that when considering Asterix, Alien, BattleZone, and Kangaroo, GW-PCZero is inferior to EfficientZero in Table [ but becomes better than EfficientZero under appropriate values of ca. When c, is adjustable, GW-PCZero(c.) achieves a mean score of 2.066, with only 2 out of 26 games performing worse than EfficientZerol, These results suggest that there is potential for further improvement in the weighting strategy and that more effort should be devoted to exploring this area in future research.
Conclusion
In this paper, we have proposed GW-PCZero to consider path consistency (PC) in a general setting and provided theoretical analysis of the convergence property of MCTS with the PC constraint. GW-PCZero extends the previous PCZero from board games to more practical applications, for which the environment emits immediate rewards, such Atari games. An uncertainty- awwre weighting mechanism, which gives a larger discount to the farther states along the searching path, is devised to compute reliable learning target for PC. What's more, have theoretically proved that MCTS is guaranteed to find the optimal solution under the constraint of PC. Experiments demonstrate that PC is beneficial to obtain strong artificial intelligence programs but consumes fewer computational resources, Neural-guided MCTS has been extensively utilized to address optimization problems in various practical applications, such as de novo drug molecular generation [1]] organic molecule retrosynthesis [ and so on. There is potential for the development of PC to contribute to addressing these critical problems by providing more robust value estimators. This work is still in the nascent stages without further applications related to people's 's daily lives currently and thus there is no immediate ethical or harmful social impacts.
7
Acknowledgement
This work supported by the National Natural Science Foundation of China (62172273), and Shanghai Municipal Science and Technology Major Project (2011SHZDZX0102), Shikui Tu and Lei Xu are corresponding authors.
References
[1] Peter Auer, Nicolo Cesa- Bianchi, and Paul Fischer. Finite- time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-255 2002.
10

---

[2] Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling, The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
[3] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72 83. Springer, 2006.
[4] Greg Farquhar, Kate Baumli, Zita Marinho, Angelos Filos, Matteo Hessel, Hado Hasselt, and David Silver. Self-consistent models and values. Advances in Neural Information Processing Systems, 34:1111-1125, 2021.
[5] Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-100 107, 1968.
[6] Hado Hasselt. Double q-lcarning. Advances in neural information processing systems, 23, 2010.
[7] Mattco Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent Sifre, Theophane Weber. David Silver, and Hado Van Hasselt. Muesli: Combining improvements in policy optimization. In International conference machine learning, pages 4214 4226. PMLR, 2021.
[8] Lukasz Kaiser, Mohammad Babacizadch, Piotr Mitos, Blažej Osiński, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, al. Model based reinforcement learning for atari. International Conference on Learning Representations, 2019.
[9] Kacper Piotr Kielak. Do recent advancements model-based deep reinforcement learning really improve data efficiency? 2019.
[10] Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282-2822222 293. Springer, 2006.
[11] Levente Kocsis, Csaba Szcpesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 1, 2006.
[12] Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Curl: Contrastive unsupervised representations for reinforcement learning. In International Conference Machine Learning, pages 5639 5650. PMLR. 2020.
[13] Alexander Long, Alan Blair, and Herke van Hoof. Fast and data efficient reinforcement learning from pixels via non-parametrie value approximation. 2022.
[14] Marlos C Machado, Mare 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.
[15] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning. nature, 518(7540):529555 533, 2015.
[16] Evgenii Nikishin, Max Schwarzer, Pierluca D O'Oro, Pieme-- Bacon, and Aaron Courville. The primacy bias in deep reinforcement learning. In International Conference on Machine Learning, pages 16828- 16847. PMLR, 2022.
[17] Tobias Pohlen, Bilal Piot, Todd Hester, Mohammad Gheshlaghi Azar, Dan Horgan, David Budden, Gabriel Hado Van Hasselt, John Quan, Mel Večerík, et al. Observe and look further: Achieving consistent performance on atari. arXiv preprint arXiv: 1199,, 2018.
[18] Hao Qian, Cheng Lin. Dengwei Zhao, Shikui Tu, and Lei Xu. Alphadrug: protein target specific de novo molecular generation. PNAS nexus, 1(4):pgac227, 2022.
[19] Julian Schritwieserr, loannis Antonoglou, Thomas Hubert, Karen Simonyan. Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess shogi by planning with a learned model. Nature, 588(7839):604-60) 2020.
[20] Max Schwarzer, Ankesh Anand, Rishab Goel, R Devon Hjelm, Aaron Courville, and Philip Bachman. Data-efficient reinforcement learning with self-predictive representations. In International Conference on Learning Representations, 2020.
[21] Marwin HS Segler, Mike Preuss, and Mark P Waller. Planning chemical syntheses with deep neural networks and symbolic ai. Nature, 555(7698)6604 610, 2018

---

[22] David Silver. Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwisser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot. et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[23] David Silver, Thomas Hubert, Julian Schrittwieser, loannis 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, 362(6419):1144) 144,, 2018.
[24] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
[25] Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting. ACM Sigart Bullerin, 2(4):160-166) 163-163, 1991.
[26] Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In Proceedings of the AAAI conference on artificial intelligence. volume 30, 2016.
[27] Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Dueling network architectures for deep reinforeement learning. In International conference on machine learning, pages 1995-2003. PMLR, 2016.
[28] Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.
[29] Lei Xu. Deep bidirectional intelligence: Alphazero, deep ia-search, deep ia-infer, and tpe causal learning. In Applied Informatics, volume 5, pages 1-38. Springer, 2018.
[30] Lei Xu, Pingfan Yan, and Tong Chang. Algorithm enneim-a and its mean complexity. In Proc. of 2nd international conference computers and applications. IEEE Press, Beijing, pages 494-499, 1987.
[31] Denis Yarats, Ilya Kostrikov, and Rob Fergus. Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. In International Conference on Learning Reprexentations, 2020.
[32] Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34:25476-25488. 2021.
[33] Dengwei Zhao, Shikui Tu, and Lei Xu. Efficient learning for AlphaZero via path consistency. In Proceedings of the 39th International Conference Muchine Learning, volume 162 of P Proceedings of Machine Learning Research, pages 26971-26981. PMLR, 17-23 Jul 2022.
12


Reviews:
[{"review_id": "mhTMHTfWYv", "reviewer": "Reviewer_YYov", "summary": "This paper extends PCZero to more general games whre the environment emits non-zero immediate rewards and proposes Generalized Weighted PCZero (GW-PCZero). GW-PCZero is built on EfficientZero with a generalized PC constraint. Specifically, GW-PCZero add an additional value consistence loss alone the sampled path, i.e., $L_{PC}(\\theta) = \\left(v(s_t;\\theta)-\\frac{1}{l+1} \\sum_{i=0}^l\\left[\\sum_{j=1}^i r_{t+j}+v\\left(s_{t+i} ; \\theta\\right)\\right]\\right)^2$, the MSE loss between $v(s_t;\\theta)$ and the average value of {$0$-step td-target, $1$-step td-target, ..., $l$-step td-target}. To reduce the bias and variance of the PC targets when training with off-policy data, GW-PCZero devise a weighting mechanism to give larger discounts to farther states, which is very similar to the idea of `td-lambda`. So, this paper can be considered as adding an additional `td-lambda` style value loss to EfficientZero. Experiments on the Atari-100k benchmark validate the superiority of GW-PCZero over EfficientZero.", "questions": "* What's the performance of GW-PCZero if setting the updating steps to 120k?\n* What's the performance of EfficientZero if directly using Eq. (9) as the value target (do not replace $v(s_{t+l};\\theta)$ with $v^{MCTS}(s_{t+l};\\theta)$? \n* For $L_b=\\\\{s_t, s_{t+1}, \\cdots, s_{t+H}\\\\}$, only $s_t$ is considered to be constrained with PC loss in real implementation because the sampled batch $L_p$ is too short to deal with the subsequent states in the same way (line 220-221). Why not directly using Eq. (12) as the loss function (which can utilizing all states in $L_b$)?\n* What if removing the value loss (of EfficientZero) in GW-PCZero and only keeping the PC-constant loss shown in Eq. (12)?\n* What if removing the PC-constant loss of GW-PCZero and replacing the value loss (of EfficientZero) with a `td-lambda` style or a `v-trace` style value loss?", "limitations": "Please see the weaknesses and questions.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The paper is written clearly.\n* The proposed GW-PCZero becomes a new SOTA on the Atari-100k benchmark, which achieves a higher human normalized score than EfficientZero but with much less computational cost.", "weaknesses": "* 1. The path consistency exists not only on the `optimal` path but on any `on-policy` path.\n* 2. Although the paper has done a lot of theoretical analysis, the proposed method can be considered as  adding an additional `td-lambda` style value loss to EfficientZero. Therefore, the differences between the new proposed value loss functions in Eq. (15) and (17) with other typical value loss functions, e.g., td-lambda, v-trace, etc, should be discussed.\n* 3. For EfficientZero, the policy target reanalyze process and the value target reanalyze process are not necessarily separated into 2 independent passes. \n    * We can sample a slightly longer sub-trajectory $L_b=\\\\{s_t, s_{t+1}, \\cdots, s_{t+H}\\\\}$ for each item in a batch (but keep the total transition number in a batch the same), where $H>l$ and use a single batch of MCTS to get $\\pi^{MCTS}$ and $v^{MCTS}$ for all states in $L_b$. To compute $z_t, \\ldots, z_{t+H-l}$, we follow Eq. (9) in this paper but replacing $v$ with $v^{MCTS}$. For $z_{t+H-l-1}, \\ldots, z_{t+H}$, we set the $n$-step td targets with smaller $n \\in \\\\{l-1,\\ldots, 0\\\\}$, e.g., we set $z_{t+H}=v^{MCTS}(s_{t+H})$.\n    * Therefore, the computational cost (the number of MCTS runs) of EfficientZero is not necessarily much greater than GW-PCZero.\n* Minors:\n  * $v(s_{t+1};\\theta)$  (line 146) should be $v(s_{t+l};\\theta)$.\n  * $L_p$ (line 221) should be $L_b$.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable suggestions and would like to take this opportunity to address the raised issues.  \nQ1: What's the performance of GW-PCZero if setting the updating steps to 120k?  \nA1: The Path Consistency (PC) constraint is able to improve the model’s learning efficiency, and make it converge fast. The amount of game frames collected for training is 100k, regardless of whether the training steps are 60k or 120k. Increasing the number of training steps does not always lead to performance improvement. In practice, we observe certain performance improvement in several games. For example, the score is improved from 19.8 to 20.6 for Pong, and from 262.5 to 1793.8 for Kangaroo. Increasing the number of training steps 120k doubles the training time. The comparison results between GW-PCZero against the full-version EfficientZero with 120k training steps are shown as follows. GW-PCZero has converged in some games after 60k updates.The mean normalized score on those 10 games is 3.86 and 2.90 for GW-PCZero and EfficientZero accordingly.\nGame|GW-PCZero|EfficientZero|Game|GW-PCZero|EfficientZero\t\n-|-|-|-|-|-\nBreakout|450.0|406.5|DemonAttack|24074.1|13298.0\nJamesbond|525.0|459.4|Krull|7782.0|6047.0\nMsPacman |1594.1 |1387.0|Kangaroo|1793.8|962.0\nPong|20.6|20.6|Hero|10818.8 |8530.1\nAmidar|97.0|101.9|PrivateEye|96.9|100.0\n\nQ2: What's the performance of EfficientZero if directly using Eq. (9) as the value target?  \nA2: The comparison results with or without MCTS in Eq. (9) is shown in Table (9) in the appendix of EfficientZero. In this paper, the results of EfficientZero in Table 2 were obtained by adopting Eq (9) as the value target. We also add an experiment to implement EfficientZero to use MCTS root value correction. 5 games have performance improvement, while the other 5 are not. \nGame|With MCTS\t|Without MCTS|Game|With MCTS|Without MCTS\n-|-|-|-|-|-\nAlien|638.8|850.6|Amidar|80.1|60.6\nAssault|\t1352.5|994.8| Asterix|19356.3|17734.4\nBankHeist|293.8|276.9|BattleZone|13718.8|15875.0\nBoxing|43.3|28.2| Breakout\t|357.2|366.7\nChopperCmd|631.3|818.8|CrazyClimber|7115.6|8059.4\n\nQ3: Why not directly using Eq. (12) as the loss function?   \nA3: In practice, it is usually not a good choice to use Eq. (12) that require all nodes along the entire path to be available. First, the entire path may be long with a large number of nodes, and the computation for the PC target would be of high complexity. Secondly, obtaining complete and terminated paths might not be feasible in situations like Atari. Third, as mentioned in the paper, using the entire path to prepare the PC target may be unreliable. In practice, we suggest to select a certain number of the neighboring nodes through a weighting mechanism. This idea of local computation of Eq. (12) is left for future.  \nQ4: What if removing the value loss and only keeping the PC loss?  \nA5: The results of the PC-soly version are worse than the version where both loss functions are considered. Same as the PCZero paper, value loss and PC loss cannot be replaced withby each other, and the better performance will be achieved if both are adopted.\nGame|Random Player|PC-soly|PC + Value\n-|-|-|-\nQbert|163.9|2138.3|13651.6\nAssault|222.4|229.7|1224.1\nAsterix|210.0|2675.0|14771.9\nDemonAttack|152.1|3947.0|24074.1\nMsPacman|307.3|1186.3|1594.1  \n\nQ5: The differences between the PC loss with other typical value loss functions should be discussed. What if removing the PC loss and replacing the value loss with a td-lambda style or a v-trace style value loss?  \nA5: The path consistency loss and other typical value loss such as TD-lambda share many similarities. The PC target in Eq. (17) is to combine all i-step returns through a weighting mechanism, and it contains TD-lambda as a special case if we set the weights to $(1-\\lambda)\\lambda^{i-1}$. Other weighting methods can be considered for PC. PC loss and TD-lambda have some differences. In general, learning with the PC is more flexible than TD-lambda, because PC can be implemented in various mathematical forms. While preparing the learning target for PC, both states after $s_t$ and states before $s_t$ can be considered, and TD-lambda only considers the TD relationships with the states after $s_t$. If removing the PC loss of GW-PCZero and replacing the value loss with a td-lambda loss, we report the scores of several Atari games as and the performance is poor. If we keep the value loss and replace the PC loss with TD loss, the algorithm still works. TD-lambda is a special case of PC loss, and can be used as a substitute for PC loss. Both PC loss and TD-lambda cannot replace the role of the value loss.\nGame|Without value loss|With value loss|Game|Without value loss|With value loss\n-|-|-|-|-|-\nBreakout|3.22|415.4|Asterix |275.0| 18668.0\nMsPacman|606.9|883.1|Amidar|2.0|116.2\nKrull|1982.0|5147.9|Alien|577.8|916.9\n  \nQ6: The computational cost of EfficientZero is not necessarily much greater than GW-PCZero.  \nA6: Theoretically, the policy target reanalyze process and the value target reanalyze process can be done simultaneously if H is much larger than L, i.e., H >> L, and the reliability of most value function estimations is comparable to that by performing two MCTS runs. However, in practical situations, H is usually small, because a large H indicates long sub-trajectories and it tends to make the batch data violate the independence of training samples. For both MuZero and EfficientZero, H was 5. L was also 5 for MuZero. A dynamic L was adopted in EfficientZero, which is 4 or 5 in most cases. If H=L or H is slightly larger than L, a significant proportion of the value target is still determined by the last state, imposing higher requirements on the reliability of the value provided by MCTS. Therefore, EfficientZero need to employ two times of MCTS to ensure its performance. What’s more, PC can improve the learning efficiency greatly, reducing the computational resources consumption to half with 60k training steps. "}, {"review_id": "7AtLqMpMzN", "reviewer": "Reviewer_15wJ", "summary": "This paper proposes GW-PCZero, a reinforcement learning method, extending the technique of PCZero which is currently limited to board games and lacks theoretical backing. The GW-PCZero is designed for environments with non-zero immediate rewards, such as Atari games. It maintains path consistency by regularizing value estimation with the deviation from the mean value along the path, while a new weighting mechanism minimizes scouting variance. The paper provides the first theoretical proof that a neural-guided Monte Carlo Tree Search can guarantee finding an optimal solution under path consistency. And it reaches better performance on the Atari 100k benchmark with 26 games compared to the previous SoTA EfficientZero.", "questions": "1. As you mentioned in Definition 3.1 (L125), PC gives the constraint of the optimal path for the f values. For the optimal path, the f values keep the same in the path. But, I am wondering that \"when f values match in the path, is this path optimal? especially when neural nets estimate the f values.\"\n\n2. For tasks with much longer horizons, the computation cost of the path consistency can be much higher. How to reduce the corresponding cost in such cases?", "limitations": "1. The novelty of introducing a weighting mechanism without further clarification is limited. The authors claim that the weighting mechanism can mitigate the uncertainty/variance in L234, but no experiments or theorems are provided regarding the uncertainty/variance. \n\n2. The experiments and analysis of the weighting mechanism are not enough, which is the main contribution of the work. \n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clear and understandable, especially in the details in Preliminary Section.\n2. The paper provides a theoretical guarantee under the constraint of path consistency.\n3. The performance increase in the experiments shown is laudable.", "weaknesses": "1. The novelty seems limited. Compared to PCZero, it modifies the PC target through a linear weighting method, which is a little tricky and common. \n2. The authors claimed a theoretical guarantee for path consistency (PC) for the first time. But the PC is the main contribution of PCZero instead of GW-PCZero, which is confusing. However, there is no guarantee for the weighting method, concerning convergence rate or optimality.\n3. No ablation for different weighting methods. Only the tradeoff c is considered. For example, as illustrated in Figure 1(left), why the weights are not exponentially decayed?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable suggestions and would like to address the questions one by one as follows.  \nQ1: The novelty seems limited. The authors claimed a theoretical guarantee for path consistency (PC) for the first time. But the PC is the main contribution of PCZero instead of GW-PCZero, which is confusing.  \nA1: The primary contribution of this paper is to extend the concept of Path Consistency (PC) to a broader range of application scenarios with non-zero immediate reward, such as Atari games. In the literature, PC was considered by PCZero soly on board games, for which the immediate rewards are always zero. What’s more, PCZero only demonstrated the effectiveness of PC through experiments, and lacked theoretical guarantees. In this paper, we provide a theoretical foundation for PC for the first time that the neural-guided MCTS is guaranteed to find the optimal solution under the constraint of PC. Furthermore, we present a weighting mechanism into the calculation of the PC target to reduce the variance caused by scouting’s uncertainty and improve the performance.  \nQ2: As you mentioned in Definition 3.1 (L125), PC gives the constraint of the optimal path for the f values. For the optimal path, the f values keep the same in the path. But I am wondering that \"when f values match in the path, is this path optimal? especially when neural nets estimate the f values.\"  \nA2: If the f values are estimated quite accurately, the path with the same f-value is the optimal path. The reason is that the root node is definitely on the optimal path, and the f value of the root node is the global optimal solution with highest reward. Therefore, the nodes which have the same f value as the root node also have the highest reward, and they constitute the optimal path. However, if the quality of the estimated f-values cannot be guaranteed, the above statement may not hold true. For example, one may construct a specific function that outputs the same f values for a randomly picked path which is unlikely to be optimal. In practice, such case should be seldom encountered, because the parameters of the neural network to predict the f value are usually randomly initialized.  \nQ3: For tasks with much longer horizons, the computation cost of the path consistency can be much higher. How to reduce the corresponding cost in such cases?  \nA3: The computational complexity of PC mainly lies in preparing the learning target, which computes the mean f value for all states within a selected window. If the task has much longer horizons, we can still compute the PC target based on the predefined k nearest neighbor nodes. The number k is a given constant, and it is irrelevant to the length of the horizons. According to our empirical experience, k=5 is good enough.  \nQ4: The authors claim that the weighting mechanism can mitigate the uncertainty/variance in L234, but no experiments or theorems are provided regarding the uncertainty/variance.  \nA4: For a sampled batch ${s_0,s_1,s_2,s_3}$, the PC target is calculated as\n$$\\bar{f}=\\frac{f(s_0 )+w_1 f(s_1 )+w_2 f(s_2 )+w_3 f(s_3 )}{1+w_1+w_2+w_3}$$\nAs mentioned in the paper, PC requires that f values of states along any optimal path in a search graph should be identical with $s_0$, and the probability that $s_i$ and $s_0$ are not in the same optimal path grows as i increases. If we assume the f value follows a normal distribution,  $f(s_i)$ has the same mean value but the variance grows as i increases, because the probability of $f(s_i)$ being farther away from the mean grows. When a smaller weight $w_i$ is given to $f(s_i)$ with a larger index i, the variance of the estimated $\\bar{f}$ will be reduced. From this perspective, the weighting mechanism is a reasonable way to mitigate the variance.  \nQ5: More ablation study on the weighting mechanism.  \nA5: Thanks for your suggestion. We provide experimental results of the exponential weighting approach, for which the weight is calculated as $\\exp⁡\\\\{-i×0.1\\\\}$. Due to the limited time of the rebuttal period, we report the results on some Atari games as follows. Notice that the performance is improved on seven out of twelvegames if replacing the linear weighting with the exponential weighting method. It deserves more investigations on the weighting mechanism in the future.\n|Game\t|\tLinear\t|\tExp\t|\tGame\t|\tLinear\t|\tExp\t|\t\t\n| :-:   |   :-:             | :-:               |:-:   |   :-:             | :-:               |\n|Breakout\t|\t450.0|\t475.7\t|\tPong\t\t|19.8\t|\t20.2|\n|Qbert\t\t|13651.6|\t11737.5\t|\tAssault\t\t|1224.1\t|1224.9|\n|Asterix\t|\t14771.9|\t15750.0|\t\tCrazyClimber|\t9734.4|\t6718.8|\n|MsPacman\t|1594.1\t|1319.7\t\t|Amidar\t|\t97.0\t\t|186.2|\n|KungFuMaster|\t20543.8|\t24025.0|\tKrull\t|\t7782.0|\t6131.0|\n|Alien\t\t|699.7\t|627.8|\t\tFrostbite\t|\t249.7|\t258.1|"}, {"review_id": "beWeuOma6m", "reviewer": "Reviewer_s6tP", "summary": "This paper proposes a model-based RL method called GW-PCZero, which is built on EfficientZero and generalizes the path consistency (PC) constraint from board games with zero immediate rewards to environments with non-zero immediate rewards. The authors introduce a weighting average mechanism and use the mean f value of states along the path as the target for the PC constraint. \n\nAlthough the authors did comprehensive experiments to demonstrate that GW-PCZero slightly outperforms EfficientZero on the Atari 100k benchmarks with 26 games with less computation, they missed a published paper SCZero whose idea is essentially the same as the proposed GW-PCZero. This makes the novelty and comprehensiveness of GW-PCZero should be questioned. \n\nMeanwhile, since the author uses PC constraint on a off-policy RL algorithm EfficientZero, the off-policy issues may have significantly negative impacts on the effectiveness of PC loss. In the setting of off-policy RL, the author's claim on global constraint of PC loss should be questioned. The authors only make limited discussion and proposed a simple linear weighting trick, which causes PC loss to degenerate into the SC loss.", "questions": "1. Can you report the median human normalized score?\n2. Can you report the performance of GW-PCZero(c_\\alpha)? and also the performance of Dreamer and IRIS if possible.\n3. Can you report a performance with fixed coeff of PC loss? like \\lambda=0.2 or 0.4\n4. Can you report the performance of GW-PCZero with 120k training steps?\n5. Can you provide some experiment results that shows PC loss better than SC loss within Atari 100K setting?", "limitations": "The paper's novelty should be questioned, since its PC loss is basically a 'reward-sum' version of DeepMind's SC loss published in 'Self-Consistent Models and Values', Neurips 2021.\nThe coefficient of PC loss needs to be adjusted according to the task. Generally, this is not an common hyperparameter in most RL settings. And the performance should not be sensitive to the coefficient of PC loss.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "1. The paper extends the path-consistency to environments with non-zero immediate rewards.\n2. The paper uses significantly less computational resources.", "weaknesses": "The most critical issues of this paper:\n1. The proposed GW-PC loss is extremely similar to a published paper 'Self-Consistent Models and Values'(Neurips 2021). The PC loss can be converted to SC loss easily as\n$l^{SC-residual}=\\sum_{k=0}^K (\\hat{r}(s_k, a_k)+\\gamma \\hat{v}(s_{k+1})-\\hat{v}(s_k))=\\sum_{k=0}^K (g(s_{k+1})+\\hat{v}(s_{k+1})-g(s_k)-\\hat{v}(s_k))=l^{PC}$\nHowever, it seems that the author did not notice SCZero paper at all, no citing or taking SCZero as the most important baseline.\n2. Setting path consistency on a off-policy algorithm like EfficientZero is not reasonable. For tasks with nonzero immediate rewards like Atari Games, the old state transitions collected by the old policy brought significant off-policy issue, which makes the proposed PC loss  hardly be a global constraint as the authors claimed. Considering the off-policy issue and computational limitations, authors proposed a sliding window and a linear weighting trick to reduce the impact of the marginal states within the sliding window. This makes the proposed PC loss has little improvement compared to the previous SC loss, no matter in terms of fundamental ideas or mathematics.\n\nMinors:\n1. The paper didn't report the median human normalized score.\n2. The coefficient of PC loss is required to be adjusted according to the task. Generally, this is not an common hyperparameter in most RL settings. And the performance should not be sensitive to the coefficient of PC loss.\n3. The paper didn't compare it with other data-efficient RL algorithms like IRIS and Dreamer.\n4. The paper over-claims the contribution. GW-PCZero only slightly outperform the full-version EfficientZero(with 120k training steps).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable suggestions, and in the following we address the concerns you have raised.  \nQ1: Can you report the median human normalized score?  \nA1: The median human normalized scores are 0.399 and 0.388 for GW-PCZero and EfficientZero, respectively. The results are obtained under the same training conditions. The human normalized scores of GW-PCZero for each of the 26 games are given in decreasing order as follows. It is observed that GW-PCZero outperforms human on 11 games (with score > 1). The median is computed by the average between the $13^{th}$ (Gopher) and the $14^{th}$ (BattleZone).\n|Game\t|\tScore\t|\tGame\t|\tScore\t|\tGame\t|\tScore\t|\t\t\n| :-:   |   :-:             | :-:               |:-:   |   :-:             | :-:               |\n|Breakout\t|\t15.57\t\t|DemonAttack|\t13.15\t\t|Krull\t\t|5.79|\n|Boxing\t\t|3.46\t\t\t|RoadRunner\t|2.14\t\t\t|Assault\t\t|1.93|\n|Asterix\t|\t1.76\t\t|\tJamesbond\t|1.38\t\t|\tPong\t\t|1.15|\n|UpNDown\t|1.06\t\t\t|Qbert\t\t|1.01\t\t\t|KungFuMaster\t|0.90|\n|Gopher\t\t|0.48\t\t\t|BattleZone\t|0.32\t\t\t|BankHeist\t|0.26|\n|Hero\t\t|\t0.24\t\t|\tMsPacman\t|0.19\t\t|\tAlien\t\t|0.07|\n|Kangaroo\t|\t0.07\t\t|\tAmidar\t\t|0.05\t\t|\tChopperCmd\t|0.05|\n|Frostbite\t|\t0.04\t\t|\tSeaquest\t\t|0.02\t|\t\tPrivateEye|\t0.00|\n|Freeway\t|\t0.00\t\t|\tCrazyClimber\t|-0.04|\n\nQ2: Can you report the performance of GW-PCZero($c_\\alpha$)? and also the performance of Dreamer and IRIS if possible.  \nA2: The performance of GW-PCZero($c_\\alpha$) is reported as follows. Experiment results indicates that proper weighting mechanism is beneficial to improve the performance, and we will conduct a more detailed and rigorous study of the weighting mechanism in the future.\n|Game\t|\tScore\t|\tGame\t|\tScore\t|\tGame\t|\tScore\t|\t\t\n| :-:   |   :-:             | :-:               |:-:   |   :-:             | :-:               |\n|Alien\t|\t982.5\t\t|Amidar\t\t|97.0\t\t|\tAssault\t\t|1224.1|\n|Asterix|\t\t22131.3\t|\tBankHeist|\t207.2\t|\tBattleZone\t|16812.5|\n|Boxing\t|\t53.8\t\t|\tBreakout|\t\t450.0|\t\tChopperCmd\t|1150.0|\n|CrazyClimber|\t9734.4\t|\tDemonAttack\t|24074.1|\t\tFreeway\t\t|0.0|\n|Frostbite\t|\t249.7\t|\tGopher\t\t|1286.9\t|\tHero\t\t\t|8171.3|\n|Jamesbond\t|525.0\t\t|Kangaroo\t\t|262.5\t|\tKrull\t\t|7782.0|\n|KungFuMaster|\t20543.8\t|MsPacman\t|1594.1\t\t|Pong\t\t|19.8|\n|PrivateEye\t|96.9\t\t|\tQbert\t|\t13651.6|\t\tRoadRunner|\t16809.4|\n|Seaquest\t|\t1215.6|\t\tUpNDown\t|12344.7|\t|   |   \n\nAccording to the original paper of IRIS, when the training data size is limited to 100k frames, the average score of IRIS is 1.046, which is lower than that of EfficientZero and GW-PCZero. We will add the results of IRIS to our paper in the revised version. The Dreamer in the original paper was trained with 200M frames, which is a very different setting from our paper. We will make every effort to report the result of the Dreamers under 100k training frames in the future.  \nQ3: Can you report a performance with fixed coeff of PC loss?   \nA3: We report the results below by fixing the coefficient at 0.35. The normalized mean score is 1.421, which is higher than EfficientZero’s 1.212 under the same training conditions. The value of 0.35 is a moderate setting for the coefficient of PC loss. In practice, we suggest to use a small coefficient for simple games, a large one for complex games. That is, the coefficient can be further adjusted for improved performance. \n|Game\t|\tScore\t|\tGame\t|\tScore\t|\tGame\t|\tScore\t|\t\t\n| :-:   |   :-:             | :-:               |:-:   |   :-:             | :-:               |\n|Alien\t\t|699.7\t\t|Amidar\t\t|160.1\t\t|Assault\t\t|1350.2|\n|Asterix\t|\t9000.0\t|\tBankHeist\t|155.6\t|\tBattleZone\t|9968.8|\n|Boxing\t\t|27.4\t\t|\tBreakout\t|\t384.1|\t\tChopperCmd|\t1150.0|\n|CrazyClimber|\t6665.6\t|\tDemonAttack\t|12116.6|\t\tFreeway\t\t|0.0|\n|Frostbite\t|\t249.7\t|\tGopher\t|\t1769.4\t|\tHero\t\t\t|12646.4|\n|Jamesbond\t|357.8\t\t|Kangaroo\t|\t325.0\t|\tKrull\t\t|7782.0|\n|KungFuMaster|\t10400.0\t|MsPacman\t|805.0\t\t|Pong\t|6.7|\n|PrivateEye\t|100.0\t\t|Qbert\t\t|7439.1\t\t|RoadRunner|\t5693.8|\n|Seaquest\t|\t1006.3\t|\tUpNDown\t|3932.5\t    |||\n\nQ4: Can you report the performance of GW-PCZero with 120k training steps?  \nA4: The Path Consistency (PC) constraint is able to improve the model’s learning efficiency, and make it converge fast when the sample size is limited. It should be noted in this paper that the amount of game frames collected for training is fixed at 100k, regardless of whether the training steps are 60k or 120k. Therefore, increasing the number of training steps does not always lead to performance improvement, as GW-PCZero may converge early before the 120k step. In practice, we observe certain performance improvement in several games. For example, the score is improved from 19.8 to 20.6 for Pong, and the score is improved from 262.5 to 1793.8 for Kangaroo. The performances on most of the games remain the same roughly. Moreover, increasing the number of training steps from 60k to 120k, the training time is would be doubled. Also, we need to pay attention to appropriately adjusting  the decay rate of the learning rate in EfficientZero, because it is related to the number of training steps.  The comparison results between GW-PCZero against the full-version EfficientZero with 120k training steps on some of the Atari games are shown as follows. GW-PCZero has already converged in some games when training steps are 60k.The mean normalized score on those 10 games is 3.86 and 2.90 for GW-PCZero and EfficientZero accordingly. We will finish the computation on 26 Atari games in the revised version of the paper.  \n|Game|GW-PCZero|EfficientZero|Game|GW-PCZero|EfficientZero|  \t\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|Breakout|450.0|406.5|DemonAttack|24074.1|13298.0|\n|Jamesbond|525.0|459.4|Krull|7782.0|6047.0|\n|MsPacman |1594.1 |1387.0|Kangaroo|1793.8|962.0|\n|Pong|20.6|20.6|Hero|10818.8 |8530.1|\n|Amidar|97.0|101.9|PrivateEye|96.9|100.0|"}, {"review_id": "Kp6qaGB2TC", "reviewer": "Reviewer_hxZc", "summary": "This paper proposes GW-PCZero,  an RL algorithm based on neural-guided Monte Carlo Tree Search (MCTS). GW-PCZero adopts the idea of Path Consistency (PC) from prior work, i.e., a regularizer that encourages evaluation function to be consistent throughout an optimal path, to improve sample efficiency. Beyond this, GW-PCZero generalizes to the environment with reward given before the end of the episode, and appends a weight in the regularizer that decreases with the number of steps of the episode to account for increasing uncertainty later in the episode. The paper proves that the probability of finding the optimal path is lower-bounded, and achieves comparable / marginally better performance than the state-of-the-art (EfficientZero) with much less computational cost on many Atari environments.", "questions": "I have four questions for this paper:\n\n1. The experiment results only show the effect of How sensitive the $\\lambda$ is on the board games, which is a special case. How sensitive would $\\lambda$ on the Atari environment be?\n\n2. In section 4.4, the $\\lambda$ is chosen according to the ratio between prior work performance and expert (human) performance. However,  the evaluation of expert (human) performance might not be available in real-life applications. Have the author considered to use a adaptable $\\lambda$ that dynamically changes during the training process? (I noticed that the authors mention \"systematic investigation on automatic weighting methods in the future\", but this is about a different hyperparameter.)\n\n3. The author claims that they can do marginally better than EfficientZero with a quarter of MCTS runs. While this is exciting, a constant factor improvement in the time complexity might be cancelled out by implementation and more values to calculate (e.g. the extra regularizer term). Is it possible for the authors to provide actual wall clock time for each method, or to explain that your method do not have a significant overhead compared to EfficientZero for each MCTS run? \n\n4. It is a little surprising that in the Appendix section 7.2, MuZero without Path Consistency (PC) cannot deal with environments as simple as cartpole, either with or without reanalyzation. Also, there are two interesting phenomenon about this figure, which are 1) for all curves, the rewards first increase quickly, then decrease to a relatively low level, and 2) with no reanalization, MuZERO without PC even seems to work better. Could the authors explain the figure more carefully?\n\nThere are also three suggestions besides addressing the questions above and in the weakness section: \n\n1. Limitation section are missing in the paper. While there are some places that implicitly mentions the limitation (e.g. line 327, \"it deserves a systematic investigation on better automatic weighting ... in the future\"), I suggest the author to think of more possible limitations (see limitation section) and summarize them in a separate paragraph.\n\n2. I suggest the authors to append a pseudocode in the appendix to more clearly shows how GW-PCZero works; it is even better if the authors could highlight the difference in the pseudocode with prior work such as PCZero. \n\n3. The authors claim that there is no immediate ethical or social impact of this work. While this is true, there are still broader impacts of the paper that still needs to be considered, such as potential misuse of the automated technology and potential job loss that needs to be considered. ", "limitations": "The authors implicitly mentioned limitations (line 327, \"it deserves a systematic investigation on better automatic weighting ... in the future\"). However, I suggest the authors to think more about limitations, such as hyperparameter sensitivity, manual selection of hyperparameters, possible limitation on future application by the nature of neural-guided MCTS, etc., and summarize them into a separate paragraph. As for potential negative societal impact, the author claims that there are no immediate negative societal impact. While this is true, I encourage the authors to be aware of the broader impact of their work on automated decision making.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**1. The writing is easy to follow and the idea is clearly conveyed.** There are many designs of the prior work that needs to be introduced, such as neural MCTS, path consistency, and re-analyzation of both MuZero and EfficientZero; moreoever, the motivations of PCZero and EfficientZero have to be clearly stated for the readers to understand the line of work. This paper does a good job in the first three section where the concepts are well-explained to the readers. The theorems and assumptions are also clearly stated in the methodology section.\n\n**2. The experiment results are solid and convincing.** The superior performance of GW-PCZero has been evaluated on Hex and many Atari environments, and the ablation on the most important hyperparameters, which are the PC weight factor and $\\lambda$, are provided in detail. Furthermore, the authors have submitted the code, which makes the result more convincing.\n\n\n**3. The algorithm has theoretically proved performance, which is a valuable contribution.** The paper has proved that GW-PCZero has a bound for probability of finding the optimal path, which is the first theoretical result in this line of work. I am convinced that the proving technique utilized in the paper would be beneficial for further theoretical research into neural MCTS.", "weaknesses": "**1. It seems that the result is somewhat sensitive to the choice of weighting hyperparameters.** In table 3, the scores are quite different with adjacent choice of $c_a$, and different environment seems to have very different optimal $c_a$. This is also the case in the selection of $\\lambda$ in table 1 of the appendix, and there is no monotonicity exhibited on either side of the optimal hyperparameter (e.g. 8*8 and 9*9 MCTS player).\n\n**2. Other minor problems:**\n\na) The second part of Table 3 in the main paper should also have a horizontal line between the first row and the rest of the table. \n\nb) Should Eq. 16 be clipped with 0 from below? by line 281 we know that when $i>10$ the weight will be negative, but it does not make sense to discourage path consistency at any time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your valuable suggestions. We will incorporate more discussions about algorithm’s limitations in the paper. For example, similar to many existing algorithms, the performance of the current implementation of GW-PCZero relies on the selection of hyperparameters. In the long term, efficient reinforcement learning algorithms may be applied in many real-world scenarios, such as factory robots, which may lead to worker displacement. The complete pseudocode will be provided in the appendix. In the following, we provide a detailed explanation of the raised concerns.  \nQ1: The experiment results only show the effect of How sensitive the λ is on the board games, which is a special case. How sensitive would $\\lambda$ on the Atari environment be?  \nA1: The conclusion drawsn from board games also hold on Atari games. We add an experiment of  fixing $\\lambda$ at 0.2 or 0.35, and the results are reported below. We observe that out of the 11 simple games, 9 achieved better results with smaller $\\lambda$. This is consistent to the practical experience given in this paper, i.e., it is better to set a small $\\lambda$ for the relatively simple games whose the action space is less than 18.  \n|Game\t|\t$\\lambda$=0.2\t|\t$\\lambda$=0.35\t|\tGame\t|\t$\\lambda$=0.2\t|\t$\\lambda$=0.35\t|\t\t\n| :-:   |   :-:             | :-:               |:-:   |   :-:             | :-:               |\n|Breakout\t|\t450.0\t\t|384.1|Pong\t\t|19.8\t\t\t|6.7|\n|Qbert\t\t|13651.6\t\t|7439.1\t|\t\tAssault\t|\t1224.1\t\t|1350.2|\n|UpNDown\t|12344.7\t\t|3932.5\t|\t\tAsterix\t|\t14771.9\t\t|9000.0|\n|CrazyClimber|\t9734.4\t\t|6665.6\t|\t\tDemonAttack|\t24074.1\t\t|12116.6|\n|MsPacman\t|1594.1\t\t|805.0|\t\t\tAmidar\t\t|97.0\t|\t160.1|\n|KungFuMaster|\t20543.8\t|10400.0| \n\nQ2: In section 4.4, the $\\lambda$ is chosen according to the ratio between prior work performance and expert (human) performance. However, the evaluation of expert (human) performance might not be available in real-life applications. Has the author considered to use an adaptable $\\lambda$ that dynamically changes during the training process?  \nA2: Thanks for your valuable suggestions. Making the coefficient $\\lambda$ dynamically adapted during the training process is under our consideration. We have been trying to reduce $\\lambda$ gradually as the training proceeds. In the current version of the paper, we suggest to use a small $\\lambda$ for the relatively simple games and a large $\\lambda$ for the complex games according to our practical experience. We agree that it is challenging to assess the difficulty of each Atari game,  and the ratio given in the paper is an approximate measure. In practical applications, other factors can also be adopted to evaluate the difficulty of the game, such as its state-space complexity, game-tree complexity, and so on. It deserves further investigations in the future.   \nQ3: The author claims that they can do marginally better than EfficientZero with a quarter of MCTS runs. While this is exciting, a constant factor improvement in the time complexity might be cancelled out by implementation and more values to calculate (e.g. the extra regularize term). Is it possible for the authors to provide actual wall clock time for each method, or to explain that your method do not have a significant overhead compared to EfficientZero for each MCTS run?  \nA3: The regularization term induced by Path Consistency (PC) for the loss function increases some extra computation in the training phase but not much. We report the wall clock times by taking the game of Breakout as an example due to the time limitation in the rebuttal period. GW-PCZero with 60k training steps spends 254 minutes on the training process. If we remove the PC term, the training time of GW-PCZero reduces to 230 minutes. That is, the extra training computation due to the PC term costs 24 minutes, which is a 10.4% (24/230) increment in the wall clock time. Moreover, since the PC term does not affect the MCTS runs, the computational cost of GW-PCZero for each MCTS run is the same as that of EfficientZero. Therefore, the extra computational time due to the PC term is relatively a very small proportion of the overall cost. We will report the actual wall clock time for all the methods on all Atari games in the revised version of the paper.  \nQ4: It is a little surprising that in the Appendix section 7.2, MuZero without Path Consistency (PC) cannot deal with environments as simple as cartpole, either with or without reanalyzation. Also, there are two interesting phenomenon about this figure, which are 1) for all curves, the rewards first increase quickly, then decrease to a relatively low level, and 2) with no reanalyzation, MuZERO without PC even seems to work better. Could the authors explain the figure more carefully?  \nA4: As discussed in the paper, PC can enhance learning efficiency. Therefore, as shown by the learning curves in the Appendix Section 7.2, MuZero with PC learns to increase the score or reward faster than the version without PC in the early steps. Although the score curve of the PC version drops down later, it climbs back and stays at the top robustly, whereas the non-PC version drops down and stays at a low score level. What’s more, reanalyzation is one of the sources of uncertainty, and it is more helpful for the weighting mechanism in PC to take effect. The first phenomenon of the fluctuation in the score curves may be attributed to the implementation of MuZero. For the second phenomenon, the PC version of MuZero achieves a much higher score than the non-PC version as learning proceeds to be stable.  \nQ5: Should Eq. 16 be clipped with 0 from below?  \nA5: Thank you for pointing out this issue. We will revise it accordingly.  "}, {"review_id": "HgId6z4USj", "reviewer": "Reviewer_Dd1j", "summary": "This paper proposed Generalized Weighted PCZero (GW-PCZero), which builds on EfficientZero and PCZero. The goal is to generalize the implementation of PCZero from board games to Atari games, which is achieved by adding the theorem “path consistency” to EfficientZero, extending the previous idea from PCZero. This paper further applies a weighting mechanism to path consistency, which calculates more accurate targets for agents to learn. Furthermore, this paper proves that neural-guided MCTS is guaranteed to find the optimal solution under PC constraint, providing a theoretical foundation for PC. The experiments show that under Atari 100k benchmark, GW-PCZero achieves 198% mean human normalized performance, slightly higher than the SOTA EfficientZero (194%). More importantly, GW-PCZero only consumes 25% computational resources of EfficientZero.", "questions": "1. In Appendix 7.1, regarding the board game Hex, you mentioned that \"Weighted PCZero beats the original PCZero with a score of 175:163.\" However, based on the score of 175:163, it seems that the two are relatively close in performance, and it is not evident from this result alone the advantage of the Weighted mechanism. Probably, you want to show some confidence error. \n2. In Appendix 7.2, the experiments for the Classic control problem only include Cartpole, which is a relatively simple environment. Are there any other experiments that demonstrate the applicability of GW-PCZero to more complex control problems? For example, EfficientZero applied their work to Deepmind Control 100k, and it would be beneficial if you could apply your method to Deepmind Control 100k and compare it with their results.\n", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. GW-PCZero achieves slightly higher performance under Atari 100k benchmark than the SOTA EfficientZero while consuming only 25% computational resources of EfficientZero.\n2. GW-PCZero generalizes the implementation of path consistency from board game to the case where the environment emits immediate reward, such as Atari game.\n3. This paper proves that neural-guided MCTS is guaranteed to find the optimal solution under PC constraint.\n4. The paper provides rich experimental data. In addition to the Atari 100k benchmark, the authors conducted experimental analyses on board games (Hex) by combining PCZero with the weighting mechanism. Furthermore, experiments were conducted on the Classic control problem - Cartpole. The diverse range of experimental environments shows the generality of this method.\n", "weaknesses": "It appears that the proposed method is primarily a combination of two previous works, PCZero and EfficientZero, without introducing significantly novel ideas or concepts in the algorithm itself. However, overall, I would still think it is valuable to obtain the state-of-the-art with the combination. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive comments and suggestions, and we will carefully revise the paper accordingly. We provide a detailed response to each question below.  \nQ1: In Appendix 7.1, regarding the board game Hex, you mentioned that \"Weighted PCZero beats the original PCZero with a score of 175:163.\" However, based on the score of 175:163, it seems that the two are relatively close in performance, and it is not evident from this result alone the advantage of the weighting mechanism  \nA1: The effectiveness of the weighting mechanism becomes more evident when the game trajectories are of low-quality. Here, we demonstrate the effect by training the model gradually on the self-generated games during the reinforcement learning process. In the early stages of training, the model's playing ability is relatively weak, and the quality of the generated game playing trajectories is poor. When trained on the 50k games, GW-PCZero beats PCZero with a score of 199:139. When trained on the first 250k games, GW-PCZero beats PCZero with a score of 216:122. It is noted that the performance gap between these two models becomes more evident, i.e., the advantage of the weighting mechanism becomes more obvious.  \nQ2: In Appendix 7.2, the experiments for the Classic control problem only include Cartpole, which is a relatively simple environment. Are there any other experiments that demonstrate the applicability of GW-PCZero to more complex control problems?  \nA2: Thank you for your valuable suggestion. We are working on applying our GW-PCZero to the DeepMind Control (DMC) 100k tasks. Currently, our GW-PCZero is built on EfficientZero, but the source code of EfficientZero for the DMC task is not available from the original authors. We have not yet reproduced the results of EfficientZero on the DMC tasks. In the future, we will make every effort to successfully perform our GW-PCZero on the DMC tasks or find another way to demonstrate that the idea of Path Consistency (PC) also works on the DMC tasks."}]

Author rebuttal:

Meta-review: Based on the provided reviews, I recommend accepting the paper for NeurIPS. The proposed Generalized Weighted PCZero (GW-PCZero) demonstrates strong contributions by extending path consistency to Atari games, introducing a weighting mechanism to enhance learning targets, and providing theoretical grounding for neural-guided Monte Carlo Tree Search under path consistency. The experiments showcase competitive performance gains over state-of-the-art methods while utilizing significantly fewer computational resources. Although the method draws from prior works, it still represents a valuable combination leading to improved results. The reviews reflect positive evaluations and strong contributions.
Decision: Accept (poster)