ReZero: Boosting MCTS-based Algorithms by Backward-view and Entire-buffer Reanalyze

## Abstract

Abstract Monte Carlo Tree Search (MCTS)-based algorithms, such as MuZero and its derivatives, have achieved widespread success in various decision-making domains.
These algorithms employ the reanalyze process to enhance sample efficiency from stale data, albeit at the expense of significant wall-clock time consumption.
To address this issue, we propose a general approach named ReZero to boost tree search operations for MCTS-based algorithms.
Specifically, drawing inspiration from the one-armed bandit model, we reanalyze training samples through a backward-view reuse technique which obtains the value estimation of a certain child node in advance.
To further adapt to this design, we periodically reanalyze the entire buffer instead of frequently reanalyzing the mini-batch.
The synergy of these two designs can significantly reduce the search cost and meanwhile guarantee or even improve performance, simplifying both data collecting and reanalyzing.
Experiments conducted on Atari environments and board games demonstrate that ReZero substantially improves training speed while maintaining high sample efficiency.
The code is available as part of the LightZero benchmark at https://github.com/opendilab/LightZero .

## 1 Introduction

As a pivotal subset of artificial intelligence, Reinforcement Learning (RL) [] has acquired achievements and applications across diverse fields, including interactive gaming [], autonomous vehicles [], and natural language processing [].
Despite its successes, a fundamental challenge plaguing traditional model-free RL algorithms is their low sample efficiency.
These algorithms typically require a large amount of data to learn effectively, making them often infeasible in the real-world scenarios.
In response to this problem, numerous model-based RL [, ] methods have emerged.
These methods involve learning an additional model of the environment from data and utilizing the model to assist the agent’s learning, thereby improving sample efficiency significantly.

Within this field, Monte Carlo Tree Search [] (MCTS) has been proven to be a efficient method for utilizing models for planning. It incorporates the UCB1 algorithm [] into the tree search process and has achieved promising results in in a wide range of scenarios.
Specifically, AlphaZero [] plays a big role in combining deep reinforcement learning with MCTS, achieving notable accomplishments that can beat top-level human players.
While it can only be applied to environments with perfect simulators, MuZero [] extended the algorithm to cases without known environment models, resulting in good performances in a wider range of tasks.
Following MuZero, many successor algorithms have emerged, enabling MuZero to be applied in continuous action spaces [], environments with stochastic dynamics [], offline RL training scenarios [], and etc. All these MCTS-based algorithms [, , ] made valuable contributions to the universal applicability of the MCTS+RL paradigm.

However, the extensive tree search computations incur additional time overhead for these algorithms:
During the data collection phase, the agent needs to execute MCTS to select an action every time it receives a new state.
Furthermore, due to the characteristics of tree search, it is challenging to parallelize it using commonly used vectorized environments [], further amplifying the speed disadvantage.
On the other hand, during the reanalyze [] process, in order to obtain higher-quality update targets, the latest model parameters are used to re-run MCTS on the training mini-batch.
The time required to process samples thus increases as a trade-off for high sample efficiency.
The excessive time cost has become a bottleneck hindering the further promotion of these algorithms.

Recently, a segment of research endeavors are directed toward mitigating the above wall-clock time overhead about MCTS-based algorithms.
On the one hand, SpeedyZero [] greatly diminishes algorithms’ time overheads by deploying a parallel execution training pipeline; however, it demands additional computational resources.
On the other hand, it remains imperative to identify methodologies that accelerate these algorithms without imposing extra demands.
PTSAZero [], for instance, compresses the search space via state abstraction, decreasing the time cost per search.
Nevertheless, it is widely acknowledged that MCTS-based algorithms necessitate search times (the number of simulations) to assure their performance.
From this perspective, our research try to discover strategies that preserve algorithmic performance while minimizing the search times as much as possible.

In this paper, we introduce ReZero, a new approach designed to boost the MCTS-based algorithms.
Firstly, inspired by the one-armed bandit model [], we propose a backward-view reanalyze technique that proceeds in the reverse direction of the trajectories, utilizing previously searched root values to bypass the exploration of specific child nodes, thereby saving time. We present several propositions to articulate our insights and analyzed the convergence of the algorithm based on the bandit model.
Secondly, to better adapt to our proposed backward-view reanalyze technique, we have devised a novel pipeline that concentrates MCTS calls within the reanalyze process and periodically reanalyzes the entire buffer after a fixed number of training iterations.
This entire-buffer reanalyze not only reduces the number of MCTS calls but also better leverages the speed advantages of parallelization.
Our approach can be easily applied to the MCTS-based algorithm family and synergistically implemented alongside existing acceleration methods.
In addition, it will not bring about any overhead in computation resources.
Empirical experiments (Section 5) show that our approach yields good results in both single-agent environment (Atari []) and two-player board games [], greatly improving the training speed while maintaining or even improving sample efficiency.
Ablation experiments explore the impact of different reanalyze frequencies and the acceleration effect of backward-view reuse on a single search.
The main contributions of this paper can be summarized as follows:

- •
We design a method to speed up a single search by the backward-view reanalyze technique. Theoretical support for the effectiveness of our proposed method is also provided.
- •
We propose a simplified framework with the entire-buffer reanalyze mechanims that further reduces the number of MCTS calls and enhance its parallelization, thus boosting MCTS-based algorithms.
- •
We conduct several experiments on diverse environments and investigate ReZero through ablations.

## 2 Related Work

### 2.1 MCTS-based Algorithms

AlphaGo [] and AlphaZero [] combined MCTS with deep RL, achieving significant results in board games, defeating world-champion players, and revealing their remarkable capabilities. Following these achievements, MuZero [] combines tree search with a learned
value equivalent model [], successfully promoting the algorithm’s application to scenarios without known models, such as Atari.
Subsequent to MuZero’s development, several new works based on the MuZero framework emerged. EfficientZero [] further improved MuZero’s sample efficiency, using very little data for training and still achieving outstanding performance. Another works [, ] extended the MuZero agent to environments with large action spaces and stochastic environments, further broadening the algorithm’s usage scenario. MuZero Unplugged [] applied MuZero’s reanalyze operation as a policy enhancement operator and extended it to offline settings. Gumbel MuZero [] changed the node selection method during tree search, so the policy obtained from the search shows a monotonic improvement, ensuring algorithm performance even with low simulation numbers. Despite the aforementioned excellent improvement techniques, the current time overhead of MCTS-based RL remains significant, which is the main problem this paper aims to address.

### 2.2 MCTS Acceleration

Recent research has focused on accelerating MCTS-based algorithms. The work [] reduces the algorithm’s time overhead by designing a parallel system; however, this method requires more computational resources and involves some adjustments for large batch training.
PTSAZero [] narrows the search space through state abstraction, which amalgamates redundant information, thereby reducing the time cost per search.
KataGo [] use a naive information reuse trick.
They save sub-trees of the search tree and serve as initialization for the next search.
However, our proposed backward-view reanalyze technique is fundamentally different from this naive forward-view reuse and can enhance search results while saving time.
To our knowledge, we are the first to enhance MCTS by reusing information in a backward-view.
Our proposed approach can seamlessly integrate with various MCTS-based algorithms, many of which [, , , ] are orthogonal to our contributions.

## 3 Preliminaries

### 3.1 MuZero

MuZero [] is a fundamental model-based RL algorithm that incorporates a value-equivalent model [] and leverages MCTS for planning within a learned latent space.
The model consists of three core components: a representation model $h_{\theta}$, a dynamics model $g_{\theta}$, and a prediction model $f_{\theta}$:

$$ $\begin{array}[]{lll}\text{Representation:}&&s_{t}=h_{\theta}(o_{t-l:t})\\ \text{Dynamics:}&&s_{t+1},r_{t}=g_{\theta}(s_{t},a_{t})\\ \text{Prediction: }&&v_{t},p_{t}=f_{\theta}(s_{t})\\ \end{array}$ (1) $$

The representation model transforms a last observation sequences $o_{t-l:t}$ into a corresponding latent state $s_{t}$. The dynamics model processes this latent state alongside an action $a_{t}$, yielding the subsequent latent state $s_{t+1}$ and an estimated reward $r_{t}$.
Finally, the prediction model accepts a latent state and produces both the predicted policy $p_{t}$ and the state’s value $v_{t}$. These outputs are instrumental in guiding the agent’s action selection throughout its MCTS.
Lastly the agent samples the best action $a_{t}$ following the searched visit count distribution.
MuZero Reanalyze is an advanced version of the original MuZero algorithm.
This variant enhances the model’s accuracy by conducting a fresh MCTS on sampled states with the most recent version of the model, subsequently utilizing the refined policy from this search to update the policy targets.
Such reanalysis yields targets of superior quality compared to those obtained during the initial data collection.
Traditional uses of the algorithm have intertwined reanalysis with training, while we suggests a novel paradigm, advocating for the decoupling of the reanalyze process from training iterations, thus providing a more flexible and efficient methodology.

### 3.2 Bandit-view Tree Search

A stochastic bandit has $K$ arms, and playing each arm means sampling a reward from the corresponding distribution.
For a search tree in MCTS, the root node can be seen as a bandit, with each child node as an arm.
The left side of Figure 1 illustrates this idea.
However, as the policy is continuously improved during the search process, the reward distribution for the arms should change over time.
Therefore, UCT [] modeled the root node as a non-stationary stochastic bandit with a drift condition:

$$ $\mathbb{P}(\overline{X}_{is}-\mu_{i}\geq\varepsilon)\leq\exp(-\frac{ \varepsilon^{2}s}{C^{2}})\>\text{and}\>\mathbb{P}(\overline{X}_{is}-\mu_{i} \leq-\varepsilon)\leq\exp(-\frac{\varepsilon^{2}s}{C^{2}})$ (2) $$

Where $\overline{X}_{is}$ is the average reward of the first $s$ samples of arm $i$. $\mu_{i}$ is the limit of $\mathbb{E}[\overline{X}_{is}]$ as $s$ approaches infinity, which indicates that the expectation of the node value converges. $C$ is an appropriate constant characterizes the rate of concentration.

Based on this modeling, UCT uses the bandit algorithm UCB1 [] to select child nodes. AlphaZero [] inherits this concept and employs a variant formula:

$$ $UCB_{score}(s,a)=Q(s,a)+cP(s,a)\frac{\sqrt{{\sum}_{b}N(s,b)}}{1+N(s,a)}$ (3) $$

where $s$ is the state corresponding to the current node, $a$ is the action corresponding to a child node. $Q(s,a)$ is the mean return of choosing action $a$, $P(s,a)$ is the prior score of action $a$, $N(s,a)$ is the total time that $a$ has been chosen, ${\sum}_{b}N(s,b)$ is the total time that $s$ has been visited.

## 4 Method

### 4.1 Backward-view Reanalyze

Our algorithm design stems from a simple inspiration: if we could know the true state-value of a child node in advance, we could save the search for it, thus conserving search time.
As shown on the right side of Figure 1, we directly use the true expected value $\mu_{A}$ to evaluate the quality of Arm A, thereby eliminating the need for the back-propagated value to calculate the score in 3.
This results in the process occurring within the gray box being omitted.
Indeed, this situation can be well modeled as an one-armed bandit[], which also facilitates our subsequent theoretical analysis.

Figure: Figure 1: The connection between MCTS and bandits. Left shows the tree search in a bandit-view. When action $A$ is selected, a reward $r_{A}$ will be returned, where $r_{A}=\sum_{t=1}^{3}\gamma^{t-1}r_{t}^{a}+\gamma^{3}v_{a}$. For the root node, the traversal, evaluation and back-propagation occurring in the sub-tree can be approximated as sampling from an non-stationary distribution. Thus the root node can be seen as a non-stationary bandit. Right shows the one-armed bandit case. Once the reward $\mu_{A}$ is known, we can evaluate arm A using $\mu_{A}$, thereby eliminating the need to rely on subsequent tree search processes.
Refer to caption: x1.png

Driven by the aforementioned motivation, we aspire to obtain the reward expectation of a child node in advance.
However, the true expectation is always unknown.
Consequently, we resort to using the root value obtained from MCTS as an approximate substitute.
Specifically, for two adjacent time steps $S_{0}^{1}$ and $S_{0}^{0}$ (^1^11The subscript denotes the trajectory, the superscript denotes the time step in the trajectory.) in Figure 2, when searching for state $S_{0}^{1}$, the root node corresponds to a child node of $S_{0}^{0}$. Therefore, the root value obtained can be utilized to assist the search for $S_{0}^{0}$.
However, there is a temporal contradiction. $S_{0}^{1}$ is the successor state of $S_{0}^{0}$, yet we need to complete the search for $S_{0}^{1}$ first.
Fortunately, this is possible during the reanalyze process.

Algorithm 1 shows the specific design with Python-like code.
During reanalyze, since the trajectories was already collected in the replay buffer, we can perform tree search in a backward-view, which searches the trajectory in a reverse order.
Figure 2 illustrates a batch containing $n+1$ trajectories, each of length $k+1$, and $S_{l}^{t}$ is the $t$-th state in the $l$-th trajectory.
We first conduct a search for all $S^{k}$s, followed by a search for all $S^{k-1}$s, and so on.
After we search on state $S_{l}^{t+1}$ (^2^22To facilitate the explanation, we have omitted details such as the latent space and do not make a deliberate distinction between states and nodes.), the root value $m_{l}^{t+1}$ is obtained.
When engaging in search on $S_{l}^{t}$, we assign the value of $S_{l}^{t+1}$ to the fixed value $m_{l}^{t+1}$.
During traverse in the tree, we select the action $a_{root}$ for root node $S_{l}^{t}$ with the following equation:

$$ $a_{root}=\arg\max_{a}I_{l}^{t}(a)$ (4) $$

$$ $I_{t}(a)=\begin{cases}UCB_{score}(S^{t}_{l},a),&a\neq a_{l}^{t}\\ r_{l}^{t}+\gamma m_{l}^{t+1},&a=a_{l}^{t}\end{cases}$ (5) $$

where $a$ refers to the action associated with a child node, $a_{l}^{t}$ is the action corresponding to $S_{l}^{t+1}$, and $r_{l}^{t}$ signifies the reward predicted by the dynamic model.
If an action distinct from $a_{l}^{t}$ is selected, the simulation continues its traversal in accordance with the original setting []. If action $a_{l}^{t}$ is selected, this simulation is terminated immediately.
Since the time used to search for node $S^{t+1}_{l}$ is saved, this enhanced search process is faster than the original version.

Figure: Figure 2: An illustration about the backward-view reanalyze in both node and batch view. We sample $n+1$ trajectories of length $k+1$ to form a batch and conduct the search in the reverse direction of trajectories. From the node view, we would first search $S_{0}^{1}$ and then pass root value $m_{0}^{1}$ to $S_{0}^{0}$ to evaluate the value of a child node. $T_{0}^{1}$ and $T_{0}^{0}$ are the corresponding search trees. From the batch view, we would group all $S^{1}$s into a sub batch to search together and pass the root values to the $S^{0}$s.
Refer to caption: x2.png

Figure: Algorithm 1 Python-like code for information reuse

### 4.2 Theoretical Analysis

AlphaZero selects child nodes using Equation 3 and takes the final action based on the visit counts.
In the previous section, we replace Equation 3 with Equation 5, which undoubtedly impacts the visit distribution of child nodes.
Additionally, since we use the root value as an approximation to true expectation, the error between the two may also affect the search results.
To demonstrate the reliability of our algorithm, in this section, we model the root node as an non-stationary bandit and prove that, as the number of total visit increases, the visit distribution gradually concentrates on the optimal arm.
Specifically, we have the following theorem:

#### Theorem 1

For a non-stationary bandit that conforms to the assumptions of Equation 2, denote the total number of rounds as $n$, and the times a sub-optimal arm $i$ is selected in $n$ rounds as $T_{i}(n)$, then selecting actions according to Equation 5 can ensure that $\frac{{\mathbb{E}[T_{i}(n)]}}{n}\to 0$ as $n\to\infty$.
Specifically, if we know the $n$ times sample mean $\hat{\mu}^{*}_{n}$ of the optimal arm in advance, then $\mathbb{E}[T_{i}(n)]$ for all sub-optimal arm $i$ satisfies

$$ $\mathbb{E}[T_{i}(n)]\leq 2+\frac{2P_{i}\sqrt{n-1}}{\Delta_{i}-\varepsilon}+ \frac{C^{2}}{(\Delta_{i}-\varepsilon)^{2}}+n\exp{(-\frac{n\varepsilon^{2}}{C^{ 2}})}$ (6) $$

Otherwise, if we have the $n$ times sample mean $\hat{\mu}_{ln}$ of a sub-optimal arm $l$, then for arm $l$,

$$ $\mathbb{E}[T_{l}(n)]\leq 1+\frac{4C^{4}}{\varepsilon^{4}P_{1}^{2}}+n\exp{(- \frac{n(\Delta_{l}-\varepsilon)^{2}}{C^{2}})}$ (7) $$

and for other sub-optimal arms,

$$ $\mathbb{E}[T_{i}(n)]\leq 3+\frac{2P_{i}\sqrt{n-1}}{\Delta_{i}-\varepsilon}+ \frac{C^{2}}{(\Delta_{i}-\varepsilon)^{2}}+\frac{4C^{4}}{\varepsilon^{4}P_{1}^ {2}}$ (8) $$

where $\Delta_{i}$ is the optimal gap for arm $i$, $\varepsilon$ is a constant in $(0,\Delta_{i})$, and $C$ is the constant in Equation 2.

We provide the complete proof and draw similar conclusions for AlphaZero in Appendix A. Additionally, our method has a lower upper bound for $\mathbb{E}[T_{i}(n)]$. This implies that our algorithm may yield visit distribution more concentrated on the optimal arm. This is a potential worth exploring in future work, especially in offline scenarios [] where reanalyze becomes the sole method for policy improvement.

### 4.3 The ReZero Framework

The technique introduced in Section 4.1 will bring a new problem in practice.
The experiments in the Appendix C.3 demonstrate that batching MCTS allows for parallel model inference and data processing, thereby accelerating the average search speed. However, as shown in the Figure 2, to conduct the backward-view reanalyze, we need to divide the batch into $\frac{1}{k+1}$ of its original size. This diminishes the benefits of parallelized search and, on the contrary, makes the algorithm slower.

Figure: Figure 3: Execution workflow and runtime cycle graph about MuZero and ReZero in both single and multiple worker cases. The number inside the modules represent the number of iterations, and the number under the modules represent the time required for module execution. The model is updated $n$ iterations between two collections. MuZero reanalyzes the mini-batch before each model update. ReZero reanalyzes the entire buffer after certain iterations($\frac{n}{3}$ for example), which not only reduces the total number of MCTS calls, but also takes advantage of the processing speed of large batches.
Refer to caption: x3.png

We propose a new pipeline that is more compatible with the method introduced in Section 4.1.
In particular, during the collect phase, we have transitioned from using MCTS to select actions to directly sampling actions based on the policy network’s output.
This shift can be interpreted as an alternative method to augment exploration in the collect phase, akin to the noise injection at the root node in MCTS-based algorithms.
Figure 10 in Appendix C.3 indicates that this modification does not significantly compromise performance during evaluation.
For the reanalyze process, we introduce the periodical entire-buffer reanalyze mechanism. As shown in Figure 3, we reanalyze the whole buffer after a fixed number of training iterations.
For each training iteration, we don’t need to run MCTS to reanalyze the mini-batch, only need to sample the mini-batch and execute the gradient descent.

Overall, this design offers two significant advantages:
1 The entire buffer reanalyze is akin to the fixed target net mechanism in DQN [], maintaining a constant policy target for a certain number of training iterations. Reducing the frequency of policy target updates correspondingly decreases the number of MCTS calls. Concurrently, this does not result in a decrease in performance.
2 Since we no longer invoke MCTS during the collect phase, all MCTS calls are concentrated in the reanalyze process. And during the entire-buffer reanalyze, we are no longer constrained by the size of the mini-batch, allowing us to freely adjust the batch size to leverage the advantages of large batches. Figure 11 shows both excessively large and excessively small batch sizes can lead to a decrease in search speed. We choose the batch size of $2000$ according to the experiment in Appendix C.3.

Experiments show that our algorithm maintains high sample efficiency and greatly save the running time of the algorithm. Our pipeline also has the following potential improvement directions:

- •
When directly using policy for data collection, action selection is no longer bound by tree search. Thus, previous vectorized environments like [] can be seamlessly integrated. Besides, this design makes MCTS-based algorithms compatible to existing RL exploration methods like [].
- •
Our method no longer needs to reanalyze the mini-batch for each iteration, thus decoupling the process of reanalyze and training. This provides greater scope for parallelization. In the case of multiple workers, we can design efficient parallelization paradigms as shown in Figure 3.
- •
We can use a more reasonable way, such as weighted sampling to preferentially reanalyze a part of the samples in the buffer, instead of simply reanalyzing all samples in the entire buffer. This is helpful to further reduce the computational overhead.

## 5 Experiment

Figure: Figure 4: Time-efficiency of ReZero-M vs. MuZero on six representative Atari games and two board games (Connect4, Gomoku). The horizontal axis represents Wall-clock Time (hours), while the vertical axis indicates the Episode Return over 5 episodes. ReZero-M achieves higher time-efficiency than the baseline on most Atari games and Gomoku, and achieve similar time-efficiency on some simpler game like Connect4. Mean of 5 runs, shaded areas are 95% confidence intervals.
Refer to caption: x4.png

Efficiency in RL usually refers to two aspects:
sample efficiency, the agent’s ability to learn effectively from a limited number of environmental interactions, gauged by the samples needed to reach a successful policy using equal compute resources;
time efficiency, which is how swiftly an algorithm learns to make optimal decisions, indicated by the wall-clock time taken to achieve a successful policy.
Our primary goal is to improve time efficiency without compromising sample efficiency.
To empirically validate the efficiency of our introduced two boosting techniques for MCTS-based algorithms, we have incorporated the ReZero with two prominent algorithms detailed in []: MuZero with a Self-Supervised Learning loss (SSL) and EfficientZero, yielding the enhanced variants ReZero-M and ReZero-E respectively.
For brevity, when the context is unambiguous, we simply refer to them as ReZero, omitting the symbol representing the baseline algorithm.

In order to validate the applicability of our method across multiple types of decision-making environments, we opted for six representative Atari environments characterized by classic image-input observation and discrete action spaces, in addition to the strategic board games Connect4 and Gomoku with special state spaces.
For a baseline comparison, we employed the original implementations of MuZero and EfficientZero as delineated in the LightZero benchmark [].
The full implementation details available in Appendix B.
Besides, we emphasize that to ensure an fair comparison of wall-clock time, all experimental trials were executed on a fixed single worker hardware settings.
In the next subsections, we sequentially explore and try to answer the following three questions:

- •
How much can ReZero-M/ReZero-E improve time efficiency compared to MuZero/EfficientZero, while maintaining equivalent levels of high sample efficiency?
- •
What is the effect and hyper-parameter sensitivity of the Entire-buffer Reanalyze technique?
- •
How much search budgets can be saved in practice by the Backward-view Reanalyze technique?

**Table 1: Average wall-time of ReZero-M vs. MuZero on various tasks. (left) Six Atari games, (right) two board games. The time represents the average total wall-time to 100k environment steps for each algorithm. Mean and standard deviation over 5 runs.**
|  | Atari | Board Games |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| avg. wall time (h) to 100k env. steps $\downarrow$ | Pong | Breakout | MsPacman | Qbert | Seaquest | UpNDown | Connet4 | Gomoku |
| ReZero-M (ours) | $\mathbf{1}\scriptstyle{\pm 0.6}$ | $\mathbf{7.7}\scriptstyle{\pm 0.3}$ | $\mathbf{3.8}\scriptstyle{\pm 0.2}$ | $\mathbf{5.1\scriptstyle{\pm 0.3}}$ | $\mathbf{6.1}\scriptstyle{\pm 0.5}$ | $\mathbf{6.9}\scriptstyle{\pm 0.5}$ | $\mathbf{10}\scriptstyle{\pm 0.8}$ | $\mathbf{9\scriptstyle{\pm 0.8}}$ |
| MuZero [] | $4.1\scriptstyle{\pm 0.2}$ | $12.4\scriptstyle{\pm 0.8}$ | $12.0\scriptstyle{\pm 0.9}$ | $10.2\scriptstyle{\pm 0.5}$ | $11.75\scriptstyle{\pm 0.9}$ | $12.4\scriptstyle{\pm 0.9}$ | $11\scriptstyle{\pm 0.9}$ | $23\scriptstyle{\pm 2}$ |

### 5.1 Time Efficiency

Setup In this section, we aim to evaluate the performance of ReZero against classical MCTS-based algorithms MuZero and EfficientZero, focusing on the wall-clock time reduction required to achieve the comparable performance level.
In order to facilitate a fair comparison in terms of wall-time, for each run, we not only utilize identical computational resources but also maintain consistent hyper-parameter settings across the algorithms (unless otherwise specified cases). Key parameters are aligned with those from original papers.
Specifically, we set the replay ratio (the ratio between environment steps and training steps) [, ] to 0.25, and the reanalyze ratio (the ratio between targets computed from interactions with the environment and by reanalysing existing data) [] is set to 1.
For detailed hyper-paramater configurations, please refer to the Appendix B.

Results Figure 4 illustrates the performance comparison in terms of wall-clock time between ReZero-M and the original MuZero across a variety of RL environments. It is apparent that ReZero-M achieves a significant improvement in time efficiency, reaching a near-optimal policy in substantially less time for the games Pong, Breakout and Seaquest, and obtained a better policy than MuZero on the remaining tasks.
Additional results about ReZero-E and EfficientZero are detailed in Appendix C.2, specifically in Figure 7 and 8.
For a more comprehensive understanding of our findings, we provide an in-depth comparison of the wall-clock training time up to 100k environment steps for ReZero-M against MuZero in Table 1. The data reveals that, on most games, ReZero require between two to four times less wall-clock time per 100k steps compared to the baseline methods.

Figure: Figure 5: The effect of Reanalyze Frequency in ReZero-M on the MsPacman game. The proper reanalyze frequency can improve time and sample efficiency while obtaining the comparable return with MuZero (reanalyze ratio=1).
Refer to caption: x12.png

### 5.2 Effect of Reanalyze Frequency

In next two sub-sectons, we will delve into details to explain how ReZero works.
Firstly, we will analyze how the entire-buffer reanalyze technique manages to simplify the original iterative mini-batch reanalyze scheme to the periodical updated version while maintaining high sample efficiency.
Here we adjust the periodical reanalyze frequency(reanalyze the buffer 1 time every $n$ training iterations) in ReZero to a lower or higher value on the MsPacman environment, specifically reanalyze frequency=$\{2,1,1/3,0\}$, where $1$ denotes the setting $n=1000$.
The original MuZero variants with the reanalyze ratio of 1 is also included in this ablation experiment as a baseline.
Figure 5 shows entire training curves in terms of Wall-time or Env Steps and validates that appropriate reanalyze frequency can save the time overhead without causing any obvious performance loss.

### 5.3 Effect of Backward-view Reanalyze

Figure: Table 2: Comparisons about detailed time indicators between MuZero and ReZero-M inside the tree search.

To further validate and understand the advantages and significance of the backward-view reanalyze technique proposed in ReZero, we meticulously document a suite of statistical indicators of the tree search process in Table 2. The number of function calls is the cumulative value of 100 training iterations on Pong. Avg. time is the average time of a MCTS across all calls.
Comparative analysis between ReZero-M and MuZero reveals that the backward-view reanalyze technique reduces the invocation frequency of the dynamics model, the search tree, and other operations like data process transformations.
Consequently, this advanced technique in leveraging subsequent time step data contributes to save the tree search time in various MCTS-based algorithms, further leading to overall wall-clock time gains.
Additionally, Theorem 1 demonstrates that the backward-view reanalyze can reduce the regret upper bound, which indicates a better search result. Figure 9 in Appendix C.3 shows a comparison of sample efficiency between using backward-view reanalyze and origin reanalyze process in MsPacman. The experimental results reveal that our method not only enhances the speed of individual searches but also improves sample efficiency. This aligns with the theoretical analysis.

## 6 Conclusion and Limitation

In this paper, we have delved into the efficiency and scalability of MCTS-based algorithms.
Unlike most existing works, we incorporates information reuse and periodic reanalyze techniques to reduces wall-clock time costs while preserving sample efficiency.
Our theoretical analysis and experimental results confirm that ReZero efficiently reduces the time cost and maintains or even improves performance across different decision-making domains.
However, our current experiments are mainly conducted on the single worker setting, there exists considerable optimization scope to apply our approach into distributed RL training, and our design harbors the potential of better parallel acceleration and more stable convergence in large-scale training tasks.
Also, the combination between ReZero and frameworks akin to AlphaZero, or its integration with some recent offline datasets such as RT-X [], constitutes a fertile avenue for future research.
These explorations could broadening the application horizons of MCTS-based algorithms.

## Appendix A Proof Materials

In this section, we will present the complete supplementary proofs.

###### Lemma A.1 .

Let$\hat{\mu_{t}}$ be a random variable that satisfies the concentration condition in Equation 2 with zero expectation,
$\varepsilon>0$, $a>0$ and

$$ $\kappa=\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{t}+\sqrt{\frac{a}{t^{2}}}\geq\varepsilon\}$ (9) $$

, then it holds that $E[\kappa]\leq 1+\frac{2\sqrt{a}}{\varepsilon}+\frac{C^{2}}{\varepsilon^{2}}$.

###### Proof.

Take $u$ as $\frac{2\sqrt{a}}{\varepsilon}$, then

$$ $\displaystyle E[\kappa]$ $\displaystyle\leq u+\sum_{t=\lceil u\rceil}^{n}\mathbb{P}(\hat{\mu}_{t}+\sqrt{ \frac{a}{t^{2}}}\geq\varepsilon)$ (10) $\displaystyle\leq u+\sum_{t=\lceil u\rceil}^{n}\exp(-\frac{t(\varepsilon-\sqrt {\frac{a}{t^{2}}})^{2}}{C^{2}})$ (11) $\displaystyle\leq 1+u+\int_{u}^{\infty}\exp(-\frac{t(\varepsilon-\sqrt{\frac{a }{t^{2}}})^{2}}{C^{2}})dt$ (12) $\displaystyle\leq 1+u+e^{\frac{\sqrt{a}\varepsilon}{C^{2}}}\int_{u}^{\infty}e^ {-\frac{t\varepsilon^{2}}{C^{2}}}dt$ (13) $\displaystyle=1+u+\frac{C^{2}}{\varepsilon^{2}}=1+\frac{2\sqrt{a}}{\varepsilon }+\frac{C^{2}}{\varepsilon^{2}}$ (14) $$

∎

Proof for Theorem 1:

###### Proof.

We first present the upper bound of $\mathbb{E}[T_{i}(n)]$ for using the Equation 3 in AlphaZero. A slight adjustment to this proof yields the conclusion of Theorem 1.
Denote $T_{i}(k)$ as the times that arm $i$ has been chosen until time $k$, $\hat{\mu}_{is}$ as the average of the first $s$ samples of arm $i$, which satisfies the concentration assumption in Equation 2, and $\hat{\mu}_{i}(k)=\hat{\mu}_{iT_{i}(k)}$. Then we have:

$$ $\displaystyle T_{i}(n)=\sum_{t=1}^{n}\mathbb{I}\{A_{t}=i\}$ (15) $\displaystyle\leq\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{1}(t-1)+P_{1}\frac{\sqrt {t-1}}{1+T_{1}(t-1)}\leq\mu_{1}-\varepsilon\}$ (16) $\displaystyle+\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{i}(t-1)+P_{i}\frac{\sqrt{t- 1}}{1+T_{i}(t-1)}\geq\mu_{1}-\varepsilon\ \text{and}\ A_{t}=i\}$ (17) $$

for 16, we have

$$ $\displaystyle E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{1}(t-1)+P_{1}\frac{\sqrt{ t-1}}{1+T_{1}(t-1)}\leq\mu_{1}-\varepsilon\}]$ (18) $\displaystyle\leq 1+\sum_{t=2}^{n}\sum_{s=0}^{t-1}\mathbb{P}(\hat{\mu}_{1s}+P_ {1}\frac{\sqrt{t-1}}{1+s}\leq\mu_{1}-\varepsilon)$ (19) $\displaystyle=1+\sum_{t=2}^{n}\sum_{s=1}^{t-1}\mathbb{P}(\hat{\mu}_{1s}+P_{1} \frac{\sqrt{t-1}}{1+s}\leq\mu_{1}-\varepsilon)$ (20) $\displaystyle\leq 1+\sum_{t=2}^{n}\sum_{s=1}^{t-1}\exp(-\frac{s(\varepsilon+P_ {1}\frac{\sqrt{t-1}}{1+s})^{2}}{C^{2}})$ (21) $\displaystyle\leq 1+\sum_{t=2}^{n}\exp(-\frac{1}{C^{2}}\varepsilon P_{1}\sqrt{ t-1})\sum_{s=1}^{t-1}\exp(-\frac{s\varepsilon^{2}}{C^{2}})$ (22) $\displaystyle\leq 1+\sum_{t=2}^{n}\exp(-\frac{1}{C^{2}}\varepsilon P_{1}\sqrt{ t-1})\frac{C^{2}}{\varepsilon^{2}}$ (23) $\displaystyle\leq 1+\frac{4C^{4}}{\varepsilon^{4}P_{1}^{2}}$ (24) $$

Notes: In 19, since we assume $P_{1}\geq\mu_{1}$, the probability of the term $s=0$ would be 0 0. Thus, we can discard it. If this assumption doesn’t hold, we can choose to accumulate $t$ starting from a larger $t_{0}$(which satisfies $P_{1}\sqrt{t_{0}-1}>\mu_{1}$ as mentioned in the article). Starting the summation from such a $t_{0}$ ensures all terms of $s=0$ can still be discarded, and all add terms that $t\leq t_{0}$ can be bounded to $1$. This only changes the constant term and won’t affect the growth rate of regret.
From 21 to 22, we just need to expand the quadratic term and do some simple inequality scaling.
From 22 to 23, we need to notice that $\sum_{s=1}^{t-1}\exp(-\frac{s\varepsilon^{2}}{C^{2}})$ is a geometric sequence and scale it to $\frac{C^{2}}{\varepsilon^{2}}$.
From 23 to 24, we use the inequality $\sum_{t=2}^{n}\frac{1}{e^{a\sqrt{t-1}}}\leq\int_{1}^{\infty}\frac{1}{e^{a\sqrt
{t-1}}}$.

for 17, we have

$$ $\displaystyle E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{i}(t-1)+P_{i}\frac{\sqrt{ t-1}}{1+T_{i}(t-1)}\geq\mu_{1}-\varepsilon\ \text{and}\ A_{t}=i\}]$ (25) $\displaystyle\leq E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{i}(t-1)+P_{i}\sqrt{ \frac{n-1}{(1+T_{i}(t-1))^{2}}}\geq\mu_{1}-\varepsilon\ \text{and}\ A_{t}=i\}]$ (26) $\displaystyle\leq 1+E[\sum_{s=1}^{n-1}\mathbb{I}\{\hat{\mu}_{is}+P_{i}\sqrt{ \frac{n-1}{(1+s)^{2}}}\geq\mu_{1}-\varepsilon\}]$ (27) $\displaystyle\leq 1+E[\sum_{s=1}^{n}\mathbb{I}\{\hat{\mu}_{is}-\mu_{i}+P_{i} \sqrt{\frac{n-1}{s^{2}}}\geq\Delta_{i}-\varepsilon\}]$ (28) $$

with Lemma A.1, we can have

$$ $\displaystyle\ref{T21}\leq 2+\frac{2P_{i}\sqrt{n-1}}{\Delta_{i}-\varepsilon}+ \frac{C^{2}}{(\Delta_{i}-\varepsilon)^{2}}$ (29) $$

so

$$ $\displaystyle E[T_{i}(n)]\leq 3+\frac{2P_{i}\sqrt{n-1}}{\Delta_{i}-\varepsilon }+\frac{C^{2}}{(\Delta_{i}-\varepsilon)^{2}}+\frac{4C^{4}}{\varepsilon^{4}P_{1 }^{2}}$ (30) $$

The proof of theorem 1 can be obtained by making slight modifications. In case we have $\hat{\mu}^{*}_{n}=\frac{1}{n}\sum_{t=1}^{n}\hat{\mu}_{t}$ where $\hat{\mu}_{t}$ is sampled from the optimal arm in advance,

$$ $\displaystyle E[T_{i}(n)]=E[\sum_{t=1}^{n}\mathbb{I}\{A_{t}=i\}]$ (31) $\displaystyle\leq E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{1n}\leq\mu_{1}- \varepsilon\}]$ (32) $\displaystyle+E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{i}(t-1)+P_{i}\frac{\sqrt{ t-1}}{1+T_{i}(t-1)}\geq\mu_{1}-\varepsilon\ \text{and}\ A_{t}=i\}]$ (33) $\displaystyle\leq n\exp{(-\frac{n\varepsilon^{2}}{C^{2}})}+E[\sum_{t=1}^{n} \mathbb{I}\{\hat{\mu}_{i}(t-1)+P_{i}\frac{\sqrt{t-1}}{1+T_{i}(t-1)}\geq\mu_{1} -\varepsilon\ \text{and}\ A_{t}=i\}]$ (34) $\displaystyle\leq 2+\frac{2P_{i}\sqrt{n-1}}{\Delta_{i}-\varepsilon}+\frac{C^{2 }}{(\Delta_{i}-\varepsilon)^{2}}+n\exp{(-\frac{n\varepsilon^{2}}{C^{2}})}$ (35) $$

In case we have $\hat{\mu}_{ln}=\frac{1}{n}\sum_{t=1}^{n}\hat{\mu}_{t}$ where $\hat{\mu}_{t}$ is sampled from the same reward distribution of arm $l$,

$$ $\displaystyle E[T_{l}(n)]=E[\sum_{t=1}^{n}\mathbb{I}\{A_{t}=l\}]$ (36) $\displaystyle\leq E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{1}(t-1)+P_{1}\frac{ \sqrt{t-1}}{1+T_{1}(t-1)}\leq\mu_{1}-\varepsilon\}]$ (37) $\displaystyle+E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{ln}\geq\mu_{1}- \varepsilon\ \text{and}\ A_{t}=i\}]$ (38) $\displaystyle\leq E[\sum_{t=1}^{n}\mathbb{I}\{\hat{\mu}_{1}(t-1)+P_{1}\frac{ \sqrt{t-1}}{1+T_{1}(t-1)}\leq\mu_{1}-\varepsilon\}]+n\exp{(-\frac{n(\Delta_{l} -\varepsilon)^{2}}{C^{2}})}$ (39) $\displaystyle\leq 1+\frac{4C^{4}}{\varepsilon^{4}P_{1}^{2}}+n\exp{(-\frac{n( \Delta_{l}-\varepsilon)^{2}}{C^{2}})}$ (40) $$

and the bound of $E[T_{i}(n)]$ for $i\neq l$ keeps unchanged.
∎

###### Lemma A.1 .

###### Proof.

###### Proof.

## Appendix B Implementation Details

### B.1 Environments

In this section, we first introduce various types of reinforcement learning environments evaluated in the main paper and their respective characteristics, including different observation/action/reward space and transition functions.

Atari: This category includes sub-environments like Pong, Qbert, Ms.Pacman, Breakout, UpNDown, and Seaquest. In these environments, agents control game characters and perform tasks based on pixel input, such as hitting bricks in Breakout. With their high-dimensional visual input and discrete action space features, Atari environments are widely used to evaluate the capability of reinforcement learning algorithms in handling visual inputs and discrete control problems.

Board Games: This types of environment includes Connect4, Gomoku, where uniquely marked boards and explicitly defined rules for placement, movement, positioning, and attacking are employed to achieve the game’s ultimate objective. These environments feature a variable discrete action space, allowing only one player’s piece per board position. In practice, algorithms utilize action mask to indicate reasonable actions.

### B.2 Algorithm Implementation Details

Our algorithm’s implementation is based on the open-source code of LightZero []. Given that our proposed theoretical improvements are applicable to any MCTS-based RL method, we have chosen MuZero and EfficientZero as case studies to investigate the practical improvements in time efficiency achieved by integrating the ReZero boosting techniques: just-in-time reanalyze and speedy reanalyze (temporal information reuse).

To ensure an equitable comparison of wall-clock time, all experimental trials were executed on a fixed single worker hardware setting consisting of a single NVIDIA A100 GPU with 30 CPU cores and 120 GiB memory.
Besides, we emphasize that to ensure a fair comparison of time efficiency and sample efficiency, the model architecture and hyper-parameters used in the experiments of Section 5 are essentially consistent with the settings in LightZero [].
For specific hyper-parameters of ReZero-M and MuZero on Atari, please refer to the Table 3.
The main different hyper-parameters for the ReZero-M algorithm in the Connect4 and Gomoku environment are set out in Tables 4.
In addition to employing an LSTM network with a hidden state dimension of 512 to predict the value prefix [], all hyperparameters of ReZero-E are essentially identical to those of ReZero-M in Table 3.

Wall-time statistics Note that all our current tests are conducted in the single-worker case. Therefore, the wall-time reported in Table 1 and Table 5 for reaching 100k env steps includes:

- •
collect time: The total time spent by an agent interacting with the environment to gather experience data.[] can be integrated to speed up. Besides, this design also makes MCTS-based algorithms compatible to existing RL exploration methods like [].
- •
reanalyze time: The time used to reanalyze collected data with the current policy or value function for more accurate learning targets [].
- •
train time: The duration for performing updates to the agent’s policy, value functions and model based on collected data.
- •
evaluation time: The period during which the agent’s policy is tested against the environment, separate from training, to assess performance.

Currently, we have set collect_max_episode_steps to 10,000 and eval_max_episode_steps to 20,000 to mitigate the impact of anomalously long evaluation episodes on time. In the future, we will consider conducting offline evaluations to avoid the influence of evaluation time on our measurement of time efficiency.
Furthermore, the ReZero methodology represents a pure algorithmic enhancement, eliminating the need for supplementary computational resources or additional overhead. This approach is versatile, enabling seamless integration with single-worker serial execution environments as well as multi-worker asynchronous frameworks. The exploration of ReZero’s extensions and its evaluations in a multi-worker [] paradigm are earmarked for future investigation.

Board games settings Given that our primary objective is to test the proposed techniques for improvements in time efficiency, we consider a simplified version of single-player mode in all the board games. This involves setting up a fixed but powerful expert bot and treating this opponent as an integral part of the environment. Exploration of our proposed techniques in the context of learning through self-play training pipeline is reserved for our future work.

**Table 3: Key hyperparameters of ReZero-M on Atari environments.**
| Hyperparameter | Value |
| --- | --- |
| Replay Ratio [] | 0.25 |
| Reanalyze ratio [] | 1 |
| Num of frames stacked | 4 |
| Num of frames skip | 4 |
| Reward clipping [] | True |
| Optimizer type | Adam [] |
| Learning rate | $3\times 10^{-3}$ |
| Discount factor | 0.997 |
| Weight of policy loss | 1 |
| Weight of value loss | 0.25 |
| Weight of reward loss | 1 |
| Weight of policy entropy loss | 0 |
| Weight of SSL (self-supervised learning) loss [] | 2 |
| Batch size | 256 |
| Model update ratio | 0.25 |
| Frequency of target network update | 100 |
| Weight decay | $10^{-4}$ |
| Max gradient norm | 10 |
| Length of game segment | 400 |
| Replay buffer size (in transitions) | 1e6 |
| TD steps | 5 |
| Number of unroll steps | 5 |
| Use augmentation | True |
| Discrete action encoding type | One Hot |
| Normalization type | Batch Normalization [] |
| Priority exponent coefficient [] | 0.6 |
| Priority correction coefficient | 0.4 |
| Dirichlet noise alpha | 0.3 |
| Dirichlet noise weight | 0.25 |
| Number of simulations in MCTS (sim) | 50 |
| Categorical distribution in value and reward modeling | True |
| The scale of supports used in categorical distribution [] | 300 |

**Table 4: Key hyperparameters of ReZero-M on Connect4 and Gomoku environments. If the parameter settings of these two environments are different, they are separated by a semicolon.**
| Hyperparameter | Value |
| --- | --- |
| Replay Ratio [] | 0.25 |
| Reanalyze ratio [] | 1 |
| Board size | 6x7; 6x6 |
| Num of frames stacked | 1 |
| Discount factor | 1 |
| Weight of SSL (self-supervised learning) loss | 0 |
| Length of game segment | 18 |
| TD steps | 21; 18 |
| Use augmentation | False |
| Number of simulations in MCTS (sim) | 50 |
| The scale of supports used in categorical distribution | 10 |

## Appendix C Additional Experiments

### C.1 Sample-efficiency of ReZero-M

Except for the results reported in main paper for time efficiency, we also shows the detailed sample efficiency results in this section.
Figure 6 displays the performance over environment interaction steps of the ReZero-M algorithm compared with the original MuZero algorithm across six representative Atari environments and two board games.
We can find that ReZero-M obtained similar sample efficiency than MuZero on the most tasks.

Figure: Figure 6: Sample-efficiency of ReZero-M vs. MuZero on six representative Atari games and two board games. The horizontal axis represents Env Steps, while the vertical axis indicates the Episode Return over 5 assessed episodes. ReZero achieves similar sample-efficiency than the baseline method. Mean of 5 runs; shaded areas are 95% confidence intervals.
Refer to caption: x14.png

### C.2 ReZero-E

The enhancements of ReZero we have proposed are universally applicable to any MCTS-based reinforcement learning approach theoretically.
In this section, we integrate ReZero with EfficientZero to obtain the enhanced ReZero-E algorithm. We present the empirical results comparing ReZero-E with the standard EfficientZero across four Atari environments.

Figure 7 shows that ReZero-E is better than EfficientZero in terms of time efficiency.
Figure 8 indicates that ReZero-E matches EfficientZero’s sample efficiency across most tasks.
Additionally, Table 5 details training times to 100k environment steps, revealing that ReZero-E is significantly faster than baseline methods on most games.

Figure: Figure 7: Time-efficiency of ReZero-E vs. EfficientZero on four representative Atari games. The horizontal axis represents Wall-time (hours), while the vertical axis indicates the Episode Return over 5 assessed episodes. ReZero-E achieves higher time-efficiency than the baseline method. Mean of 3 runs; shaded areas are 95% confidence intervals.
Refer to caption: x22.png

Figure: Figure 8: Sample-efficiency of ReZero-E vs. EfficientZero on four representative Atari games. The horizontal axis represents Env Steps, while the vertical axis indicates the Episode Return over 5 assessed episodes. ReZero-E achieves similar sample-efficiency than the baseline method. Mean of 3 runs; shaded areas are 95% confidence intervals.
Refer to caption: x26.png

**Table 5: Average wall-time of ReZero-E vs. EfficientZero on four Atari games.The time represents the average total wall-time to 100k environment steps for each algorithm. Mean and standard deviation over 5 runs.**
| avg. wall time (h) to 100k env. steps $\downarrow$ | Pong | MsPacman | Seaquest | UpNDown |
| --- | --- | --- | --- | --- |
| ReZero-E (ours) | $\mathbf{2.3}\scriptstyle{\pm 1.4}$ | $\mathbf{3}\scriptstyle{\pm 0.3}$ | $\mathbf{3.1}\scriptstyle{\pm 0.1}$ | $\mathbf{3.6}\scriptstyle{\pm 0.2}$ |
| EfficientZero [] | $10\scriptstyle{\pm 0.2}$ | $12\scriptstyle{\pm 1.3}$ | $15\scriptstyle{\pm 2.3}$ | $15\scriptstyle{\pm 0.7}$ |

### C.3 Ablations

Figure: Figure 9: The results of the ablation study comparing the use of backward-view reanalyze versus its absence. Mean of 3 runs; shaded areas are 95% confidence intervals.
Refer to caption: x30.png

Figure: Figure 10: The comparison of the outcomes of sampling actions based on the policy network’s output against selecting actions using MCTS. Mean of 3 runs; shaded areas are 95% confidence intervals.
Refer to caption: x31.png

Figure: Figure 11: The depiction of the variation in the average search speed of MCTS as the batch size increases. Mean of 3 runs; shaded areas are 95% confidence intervals.
Refer to caption: x32.png

This section presents the results of three supplementary ablation experiments. Figure 9 illustrates the impact of using backward-view reanalyze within the ReZero framework on sample efficiency. The results indicate that backward-view reanalyze, by introducing root value as auxiliary information, achieves higher sample efficiency, aligning with the theoretical analysis regarding regret upper bound. Figure 10 demonstrates the effects of different action selection methods during the collect phase. The findings reveal that sampling actions directly from the distribution output by the policy network does not significantly degrade the experimental results compared to using MCTS for action selection. Figure 11 depicts the relationship between the average MCTS search duration and the batch size. We set a baseline batch size of 256 and experimented with search sizes ranging from 1 to 20 times the baseline, calculating the average time required to search 256 samples by dividing the total search time by the multiplier. The results suggest that larger batch sizes can better leverage the advantages of parallelized model inference and data processing. However, when the batch size becomes excessively large, constrained by the limits of hardware resources (memory, CPU), the search speed cannot increase further and may even slightly decrease. We ultimately set the batch size to 2000, which yields the fastest average search speed on our device.

## Peer Reviews

confidence: 2
contribution: 1
initial_rating: 3
presentation: 1
questions: See weaknesses.
soundness: 2
strengths: ReZero demonstrates a reduction in wall-clock time needed to achieve comparable performance levels compared to baseline MCTS-based algorithms.
summary: In MuZero, the "reanalyze" mechanism enhances sample efficiency by revisiting and updating past experiences stored in the replay buffer. In this paper, the authors propose a method to use information from future time steps during the reanalyze phase to reduce the search space and accelerate individual MCTS runs.
weaknesses: - The writing is not clear enough for the reader to understand exactly what the algorithm is doing. I had a hard time understanding Section 4.1, and Figure 2, so I am not able to evaluate this paper too well.
- To my best guess, the authors are proposing to use previous MCTS runs to approximate the value of nodes in future MCTS runs. This is based on the 
- I don't think Theorem 1, which seems to be based on existing work, is properly grounded in the current setting. This is because MCTS is not a typical bandit: I recommend the authors take a look at the Shah et al. paper "Non-asymptotic analysis of monte carlo tree search".

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: - Why MuZero is the only baseline authors compare with?
soundness: 3
strengths: - The paper is well-written and authors include easy-to-understand figures
- The authors propose a theoretical justification of their framework
- Presented experimental results clearly show the proposed method is faster (in term of wall-clock time) than MuZero
summary: The paper proposes an improvement to the MuZero algorithm. Instead of trying the child node selection as a multi-armed bandit problem, the method treats it as one-armed bandit problem, that is a problem of selecting between one stochastic arm or a sure pay-off with a known value. Since this true value is unknown, of course, authors propose a backward search technique that produces an estimate of it.
weaknesses: - There only baseline authors compare against is the MuZero algorithm. However, in the related work section authors mention many improvements proposed to the MuZero baseline to make it faster.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: I have stated numerous questions in context in the weaknesses section. I would appreciate if the authors address them during the rebuttal phase.
soundness: 1
strengths: - The subject that the paper addresses is very important. Indeed, improving the sample efficiency of MCTS methods such as MuZero, along with the wall-clock time they incur during tree search could dramatically improve the current MCTS methods.
- Explaining MCTS methods can be a difficult task, thus using illustrations such as Figure 2 helps a lot in explaining the approach.
- There is an attempt at providing finite-time theoretical analysis, in the form of a bound on the expected number of visits to suboptimal actions. Such attempts are common within the Multi-Armed Bandits literature but are less frequent in MDP contexts. It is therefore appreciated that the authors made this theoretical effort.
- The experiments, if they are reproducible with a publicly available code, seem to support the authors claims. However, I am not confident enough to assess the experimental setup accurately.
- The contribution is orthogonal to previously proposed solutions. This implies that ReZero is readily applicable with the other proposed methods from the literature.
summary: Algorithms like MuZero extend the use of MCTS to environments without known models. However, its extensive tree search incurs a substantial time overhead. This pressing matter has motivated many research papers to propose mechanisms mitigating this wall-clock time problem. The authors in this paper propose a new algorithm of this sort, called ReZero, which is orthogonal to the previous contributions, thus making it readily deployable with many of the previous works. ReZero leverages a backward-view reanalyse technique that prunes the exploration of certain specific nodes by using previously searched root values. ReZero also reanalyses the whole buffer periodically after a fixed number of training iterations. In tandem with this reanalyse technique, ReZero employs a search strategy that is akin to a one-armed bandit algorithm. The authors then analyse ReZero from a theoretical point of view. In Theorem 1, a bound on the expected number of suboptimal action visits is proposed. Moreover, this bound implies that this expected number of suboptimal action visits is sublinear, i.e. $\lim_{n \rightarrow \infty}\frac{\mathbb{E}\left[ T_i(n)\right]}{n} = 0$. In the Appendix, the authors also claim to provide such bound for AlphaZero. Empirical results seem to indicate that ReZero-M, which is ReZero employed with MuZero with SSL, can significantly decrease the wall-clock time compared to MuZero. Similar empirical results are stated in the Appendix comparing ReZero-E with EfficientZero.
weaknesses: I see two significant weaknesses with this paper. Lack of clarity and mistakes in the theoretical result.

## Lack of Clarity:

- In Algorithm 1 there are many undefined functions: prepare, origin\_MCTS, select\_root\_child, traverse . I did not find these defined in the Appendix either. It is hard for the reader to understand the algorithmic steps from the provided code. I suggest that the authors rather provide an abstract pseudocode or thorough explanations of each step in an iteration, accompanied by some simple illustration. I struggle to deeply understand ReZero, even now I am unsure that I grasp it sufficiently.
- From Figure 2, the considered MDPs seem to have deterministic transition dynamics. This is also implied by Eq. (5). Is ReZero specific to deterministic transition dynamics? If that is the case, then it should be mentioned while introducing the method. Otherwise, Eq. (5) should account for the stochasticity of transitioning to a certain state through a (state, action) pair.
- Section 4.1 is hard to follow. Does ReZero follow the standard MCTS steps: Selection, Expansion, Simulation and Backpropagation? How is the data collected in the replay buffer? In Section 4.3, a policy network will be briefly mentioned, which implies the use of DeepRL. It makes hard for the reader to follow the explanation with scattered information like this. I only realised that there is a DeepRL approach later on, which confused me. What is the network approximating? Is it just the policy or the value function as well? How are the targets constructed in this case? And how are the values updated? There are too many questions here related to the algorithmic machinery itself that I think the authors should spend time explaining. As a suggestion, I think that the authors should delete section 3.1, which I did not find helpful, and spend more space and effort on clearly stating and explaining the algorithmic steps. Figures like Figure 1 and 2 could also be very helpful here, even if put in an illustrative appendix. Figure 3 to me does not seem standalone, it could be useful but only accompanied by this large section just defining the algorithm fully.
- It is unclear how the mini batches come to existence. Do they stem from filling the replay buffer by following the Tree and Simulation policies (as per the standard MCTS terminology)? If so, how are all the trajectories in Figure 2 of the same length? Is this just for illustrative purposes or are they indeed of the same length?
- Could you provide a more thorough explanation of traverse in Line 240? Is it following the Tree and Simulation policies? When does traverse happen compared to reanalyse? I thought it happened at the end of reanalyse but Algorithm 1 suggests otherwise.
- What if during reanalyse, two actions (or more) $a_1, a_2$ have been taken at state $S_l^t$ (in different trajectories)? Would we have $I_l^t\left( a_1\right) = r_1 + \gamma m_1, I_l^t\left( a_2\right) = r_2 + \gamma m_2$? in which case, the policy in (4) and (5) will not taken into consideration the UCB scores of these actions but rather their estimates directly. If many actions of this sort are explored, then how would exploration occur? I think I am missing a crucial detail about the algorithm here, hence why I suggest that the authors restructure the paper in a way that prioritises much more a clear explanation of ReZero.
- In (5), $I_t\left( a\right)$ should be denoted $I_t^l\left( a\right)$ for consistency of the notation with (4).
- This is not a clarity issue per se, nevertheless it should be mentioned. Regarding the non-stationary bandit in (2), the concentration assumption should be around $\mu_{is} = \mathbb{E}\left[ \overline{X_{is}} \right]$ rather than $\mu_i$ for a meaningful analysis. It is true that the text in the paper "Bandit-based Monte Carlo Planning" is unclear about this. In page 5, the authors just "assume the tail inequalities (3), (4)" and we it is unclear whether they mean $\mu_{is}$ or $\mu_i$. However, in a follow-up journal publication by the same authors "Improved Monte Carlo Methods" where they thoroughly rewrite the previous paper and correct some of its theoretical claims, the authors clarify this misunderstanding in Assumption 1. They indeed consider the concentration to be around $\mu_{is}$. If $\delta_{is} = \mu_{is} - \mu_i = \mathcal{o}\left( \sqrt{\frac{1}{s}}\right)$ the Assumption 1 would indeed imply (2) in the reviewed paper for an appropriate constant $C$. However, I believe that no such assumption was made.

To recapitulate this section. I believe that most of the confusion comes from a lack of investment in clearly explaining the algorithm ReZero. I suggest that the authors take this into consideration when revising the paper. Some of the ways to make this improvement is through illustrations, pseudocode and accompanying text. Some sections like 3.1 could be deleted in favour of this restructuring.

## Theoretical mistakes:

I love the fact that the authors committed time to theoretically analyse their algorithm, I encourage such endeavour. I would like to draw the attention of the authors to a number of mistakes in their proofs that unfortunately end up not supporting their claims. At the end of this section, I will provide references that I hope will be helpful to the authors in rethinking their proof approach in the future.
- First, the statement of Theorem 1 is not rigorous. The terms $P_i$ are nowhere defined. I understood from context and the proof that they are the prior terms $P\left( s, a\right)$ introduced in $3$, nevertheless, they should be properly defined in the theorem statement. The same remark applies to other terms like $\widehat{\mu}_{ln}$. Moreover, and even more importantly, What does it mean precisely to choose actions according to $(5)$? A first understanding would lead the reader to believe that once an arm $i$ is played, its index $I_i^t$ will always be equal to its reward, thus removing the UCB exploration bonus, but it seems to me unlikely that this is what is meant by the authors as it would imply full exploitation algorithm. Please provide the precise statement of how actions are chosen.
- General advice that the authors could incorporate straightforwardly. Please start using \left( , \right) , \Bigg\{ , \Bigg\} ... for clearer mathematical notation.

### Lemma 1:
- Minor: Line 706, put a space between "Let" and "$\widehat{\mu}_t$".
- Minor: I think the term $\exp\left( \frac{\sqrt{a}\epsilon}{C^2}\right)$ should rather be $\exp\left( 2\frac{\sqrt{a}\epsilon}{C^2}\right)$ in (13). This is a minor detail as it does not change the result, but could you please verify this?

### Theorem 1:
- $\widehat{\mu_{is}}$ is the average of the first $s$ samples of arm $i$, thus I think that the notation $\widehat{\mu}_{ln}$, in the theorem statement, is inadequate as it implies that arm $l$ has been chosen $n$ times. It should rather be replaced by $\widehat{\mu}_l\left( n\right)$.
- $T_i\left( n\right) = \sum_{t=1}^n \mathbb{I}\\{ A_t = i \\}$, thus $A_t$ denotes the chosen arm at time $t$. This definition should be stated during the proof.
-  I believe there is a mistake in (24). For the passage from (23) to (24), the authors employ $\sum_{t=2}^{n}\exp\left( -a\sqrt{t-1}\right) \le \int_{t=1}^\infty \exp\left( -a\sqrt{t-1}\right)dt$ but they do not make the calculation explicitly. I do it below via change of variable $u = \sqrt{t-1}$:
\begin{align*}
\int_{t=1}^\infty \exp\left( -a\sqrt{t-1}\right)dt &= \int_{u=0}^\infty 2u\exp\left( -au\right)du\\\\
&= \left[ -\frac{2u}{a}\exp\left( -au\right)\right]_{0}^\infty + \int_0^\infty \frac{2}{a}\exp\left( -au\right)du\\\\
&= \frac{2}{a}\left[ -\frac{1}{a}\exp\left( -au\right)\right]_0^\infty = \frac{2}{a^2}\\\\
\implies \sum_2^n\exp\left( -\frac{1}{C^2}\epsilon P_1 \sqrt\{t-1}\right) &\le \frac{2C^4}{\epsilon^2 P_1^2}
\end{align*}
This in turn implies that the term in (24) should be replaced with $1 + \frac{2C^6}{\epsilon^4 P_1^2}$.
- The passage from (26) to (27) is wrong, and this is what will unfortunately go against your claim. I invite the authors to discuss this important specific point with me during the rebuttal. There is an omitted sum here. When upper bounding the term in (26), you should proceed as follows:
$$
\mathbb{E}\left[ \sum_{t=1}^n\sum_{s=1}^{t-1} \mathbb{I}\Bigg\\{ \widehat{\mu}_{is} + P_i\sqrt{\frac{n-1}{\left( 1 + s\right)^2}} \ge \mu_1 - \epsilon\Bigg\\}, T_i\left( t-1\right) = s\right]
$$
Then this term will be further upper bounded by omitting the event $T_i\left( t-1\right) = s$. For a similar illustrative example of this sum, please refer to the paper "Finite-time Analysis of the Multiarmed Bandit Problem", especially the proof of Theorem 1, check (6). Now this double sum will lead to the following:
$$
(25) \le n + \frac{2\left( n-1\right)\sqrt{P_i^2 \left( n-1\right)}}{\Delta_i - \epsilon} + \frac{\left( n-1\right)C^2}{\left( \Delta_i - \epsilon\right)^2}\exp\left( \frac{2\left( \Delta_i -  \epsilon\right)\sqrt{P_i^2 \left( n-1\right)}}{C^2}\right)
$$
Thus leading to:
$$
\mathbb{E}\left[ T_i\left( n\right)\right] \le 1 + \frac{2C^6}{\epsilon^4 P_1^2} + n + \frac{2\left( n-1\right)\sqrt{P_i^2 \left( n-1\right)}}{\Delta_i - \epsilon} + \frac{\left( n-1\right)C^2}{\left( \Delta_i - \epsilon\right)^2}
$$
Now unfortunately the term $n + \frac{2\left( n-1\right)\sqrt{P_i^2 \left( n-1\right)}}{\Delta_i - \epsilon} + \frac{\left( n-1\right)C^2}{\left( \Delta_i - \epsilon\right)^2}$ is not sublinear and as such you can no longer deduce that $\mathbb{E}\left[ T_i\left( n\right)\right]$ is sublinear. In fact that is the reason why UCB, in the Multi-Armed Bandit (MAB) setting, employs a logarithmic term in the index $\widehat{\mu}_i\left( t-1\right) + C\sqrt{\frac{\log t}{1 + T_i\left( t-1\right)}}$ as opposed to a polynomial term. $\log t$ slows down exploration thus leading to the concentration of visits to the optimal arm. With a polynomial term in $t$, this is no longer guaranteed because the index grows quickly leading to too much exploration even for the suboptimal arms. Now the reason AlphaZero employs a polynomial term instead of a logarithmic term is because there is a need for a lot more exploration in MDPs than it is for MABs. You need a lot more samples to estimate the value of a node in an MDP than you need to estimate the value of an arm in a MAB.
- Suggestions to solve this issue. I think there might be a need to change the way you define the index of your UCB. For finite-sample analyses of UCT-like algorithms, please check the following paper "Nonasymptotic Analysis of Monte Carlo Tree Search".

## Experiments:

I do not know how to accurately assess the experimental setup as I feel like I'm not fully grasping the algorithm itself to pinpoint the merits of its contributions in the experiments. Nevertheless, if ReZero-M is just ReZero applied to MuZero, then it does hint at some substancial speedups. My concerne is with variance. From my understanding of your reanalyse strategy, you can stop searching a node prematurely, and with less samples to estimate its values, the variance of this estimate could be important. I think the authors should spend some space discussing this issue. Figure 7, SeaquestNoFrameskip-v4, Gomoku do hint at this phenomenon, while we see that MuZero's variance is stable in these cases.

## Misspelling:

There are a multitude of misspellings in the paper. Although this is a minor issue, the authors should take the time to revise their paper accordingly.
- Line 308: "in in".
- Line 059: "we aims".
- Line 084: "a efficient"
- Line 127: "a last observation sequences"
- Line 137: "we suggests"
- Line 181: "reward $r_A$", shouldn't it be "return $r_A$"?
- Line 201: Remind the reader that the grey box refers to Figure 1.
- Line 212: "Trajectories was"
- Line 744: "$T_i\left( k\right)$ as the times that" should be "$T_i\left( k\right)$ as the number of times that".
- Line 810: $\widehat{\mu}_n = \frac{1}{n}\sum_1^n \widehat{\mu}_t$, what does this mean? Does it mean that you have $n$ samples from the optimal arm?
- Line 311: "we don't need" should be "we do not need".
- Line 349: "compatible to" should be "compatible with".
- Line 399: "an fair" should be "a fair".
- Line 423: "nexe" should be "next".
- Line 527: "we incorporates" should be "we incorporate".
- Line 535: "could broadening".
- Line 539: "for build".


I believe that the subject and the approach of the paper could be very interesting to investigate rigorously. Unfortunately, mainly due to the lack of clarity and the unsoundness of the theoretical results I have decided to reject the paper. Nevertheless, I invite the authors to take a look at my suggestions during the rebuttal period and maybe we can have an instructive discussion about a revised version of the paper.

---

confidence: 5
contribution: 1
initial_rating: 5
presentation: 2
questions: Main Questions:
1) Previous studies such as "Information capture and reuse strategies in Monte Carlo Tree Search, with applications to games of hidden information" and "Learning policies from self-play with policy gradients and MCTS value estimates" have also proposed methods similar to reuse in MCTS. What are the differences between the methods in this work and those in the previous studies? This requires detailed discussion.
2) The paper presents some theoretical analyses and proofs, but I fail to understand the specific connection between this proof and the method proposed in the article, and a detailed explanation is needed.
3) How the proposed method performs in terms of improvement on Sampled MuZero and EfficientZero requires further experimental illustration.

Some minor issues:
1) It is recommended that the algorithm not use the pseudo-code of Python in Algorithm 1.
2) Line 235: what does $S^{0}s$ refer to?
3) The font size of the text in Figure 3 is too small.
4) Is it understandable that the experimental effect of Figure 6 is not obvious and there is only a small amount of influence?
5) Why is the decision made to periodically reanalyze the entire buffer instead of frequently reanalyzing small batches of data? How does this approach impact search efficiency?
soundness: 2
strengths: This work proposes the backward-view reuse technique, which reutilizes previously collected data to boost search efficiency. Additionally, the entire-buffer reanalyze mechanism represents a creative adaptation of traditional reanalyze processes, allowing for more effective data utilization. This originality is further underscored by the application of these techniques across diverse environments.The paper is well-structured and clearly written.
summary: This research presents an innovative approach to enhance the efficiency of Monte Carlo Tree Search (MCTS) algorithms, like MuZero, by introducing a method called ReZero. By leveraging a backward-view reuse technique and periodically reanalyzing the entire buffer, the authors aim to reduce search costs while maintaining or even improving performance. This work promises to simplify data collection and reanalysis in various decision-making domains.
weaknesses: The main weakness of the paper lie in the lack of innovation in the method and the scarcity of baseline comparisons in the experiment. The reuse method has some other approaches in previous MCTS works, but this paper fails to conduct a sufficient disscusion. Additionally, the experiments in the article only compare with the MuZero algorithm. Whether the EfficientZero or Sampled MuZero would show improvements when using this method requires further experimental illustration.

Meta-review: Th paper tackles the problem of improving the sample efficiency of MCTS, with some finite time guarantees.
The reviewers found several weaknesses with the current paper. 
In particular, they the writing seems to be poor, as highlighted by two reviewers. There also seems to be some mistakes in the proof. Finally, the empirical evaluation may not be very thorough because it is not comprehensive in terms of baselines.

Decision: Reject