Uncertainty-Guided Exploration for Efficient AlphaZero Training
Authors: Scott Cheng
Meng-Yu Tsai
Ding-Yong Hong
Mahmut Kandemir
Venue: NeurIPS 2025 poster ()
Keywords: AlphaZero
uncertainty
exploration
Primary area: reinforcement_learning

Abstract: AlphaZero has achieved remarkable success in complex decision-making problems through self-play and neural network training. However, its self-play process remains inefficient due to limited exploration of high-uncertainty positions, the overlooked runner-up decisions in Monte Carlo Tree Search (MCTS), and high variance in value labels. To address these challenges, we propose and evaluate uncertainty-guided exploration by branching from high-uncertainty positions using our proposed Label Change Rate (LCR) metric, which is further refined by a Bayesian inference framework. Our proposed approach leverages runner-up MCTS decisions to create multiple variations, and ensembles value labels across these variations to reduce variance. We investigate three key design parameters for our branching strategy: where to branch, how many variations to branch, and which move to play in the new branch. Our empirical findings indicate that branching with 10 variations per game provides the best performance-exploration balance. Overall, our end-to-end results show an improved sample efficiency over the baseline by 58.5\% on 9x9 Go in the early stage of training and by 47.3\% on 19x19 Go in the late stage of training.

Uncertainty-Guided Exploration for Efficient AlphaZero Training
Scott Cheng!
Meng-Ya Yu Tsai
Bing-Yong Hong
Mahmut Taylan Kandemir'
'The Pennsylvania State University, USA
IIndependent
Institute of Information Science, Academia Sinica, Taiwan
-yypc5394,mttett mps2) edu
2 adamatuno@gmai1 com
ddyhongeiss. www.iiisssiiiiiiiice.ei edu. tw
Abstract
AlphaZero has achieved remarkable success in complex decision-making problems through self-play and neural network training. However, its self self-play process remains inefficient due to limited exploration of high-uncertainty positions, the overlooked runner-up decisions in Monte Carlo Tree Search (MCTS), and high variance in value labels. To address these challenges, we propose and evaluate uncertainty-guider exploration by branching from high-uncertainty positions using our proposed Label Change Rate (LCR) metric, which is further refined by a Bayesian inference framework. Our proposed approach leverages runner-up MCTS decisions to create multiple variations, and ensembles value labels across these variations reduce variance. We investigate three key design parameters for our branching strategy: where to branch, how many variations to branch, and which move to play in the new branch. Our empirical findings indicate that branching with 10 variations per game provides the best our end-to-end results show an improved sample efficiency over the baseline by 58.5% on 9x9 Go in the early stage of training and by 47.3% on 19x19 Go in the late stage of training.
balance. Overall,
Introduction
main sequence
branched sequence
Which move to play?
high- uncertainty position
possible move
unplayed position
How many to branch?
Where to branch?
time step
Figure 1: Our proposed method enhances exploration in self- eelf-play by branching at highhuncertainty positions to explore additional runner-up MCTS decisions, and reduces the variance of the value label by ensembling multiple game results, thus improving training efficiency.
AlphaZero [1] has demonstrated remarkable capabilities by combining Monte Carlo Tree Search (MCTS) [2, 3] and deep neural networks, achieving superhuman performance in games such as Go
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Chess, and Shogi. It learns through self-play, where a neural network guides MCTS to generate games, and the game results are used to train the network. This process is repeated in an alternating fashion, gradually improving the playing strength. As the size and capability of the neural network increase, the cost of evaluating it during MCTS increases substantially, making self-play the dominant component of overall training time.
Despite its success, AlphaZero's self-play process remains inefficient for several reasons. First, only 40% of the positions change decisions after the tree search [4, 5], so only a few positions benefit from the search for improvement. Those high- uigh-uncertainty positions are unfortunately not reused for exploration. Second, only one MCTS decision is used per move during self-play, while other non-best decisions, especially the runner-up decisions, are discarded without exploration. Those runner-up up moves can potentially be stronger than the best decision, but due to an insufficient number of simulations, they fail to overtake the current best one, even a better move was found during the latter phase of tree search. Third, the value label in self-play training is provided by a single game result and thus exhibits high variance, especially during the opening phase of game. Previous works [6. 7] on reusing positions to improve AlphaZero training efficiency focus mainly game exploration, thus failing to capture high-uncertaantyy positions, particularly in the mid-to-late game. Furthermore, most of the work [8-11] on efficient training of AlphaZero and its variants focuses on improving the learning target for neural network training. In contrast, this work focuses on exploring high-uncertainty positions during self-play, and thus complements these prior approaches.
early
To this end, we propose uncertainty-guided self-play, which revisits figh-uncertainty but under- explored positions, as illustrated in Figure 1. This branching process is analogous to how humans learn after game plays, where people identify the last major mistake, typically not in the opening, and revisit that position to explore highly considered but initially overlooked decisions to change the game result. In particular, we aim to address the following questions in the context of branching: i) Where to branch?, ii) Нow many variations' to branch?, and iii) Which move to play in each new variation? ? For the first question, we branch from high-uncertainty positions by our proposed Label Change Rate, which quantifies uncertainty by estimating how likely the game result would differ when repeatedly replaying from a given position. We further refine this estimate using a Bayesian inference framework to robustly integrate both prior knowledge from search values and empirical game results. For the second question, we control the number of branches via a variation budget, balancing the degree of exploration within single game and across multiple games. Finally, for the third question, we reuse the runner-up decisions from the original search result to play the new variation without performing additional simulations observe that, when a deeper search changes the best move, the new best decision has a high chance coming from the runner-up decisions in the initial search. Moreover, since obtaining an MCTS planning result typically requires hundreds of neural network inferences, we can reuse the runner-up decisions during self- eelf-play, unlike the original method, which discards all decisions but the best result.
relying on other larger models, since
In summary, this paper makes the following main contributions:
We introduce an uncertainty-guided exploration for AlphaZero, which enhances exploration by revisiting high-uncertainty positions and reduces the variance of the value label by ensembling multiple game results. Furthermore, we conduct a detailed analysis of the three design dimensions for uncertainty branching and experimentally show their contributions to training efficiency.
We propose the Label Change Rate (LCR) metric based on our analysis on the Bernoulli distri- bution, along with a Bayesian refinement scheme, to robustly identify high-uncertainty positions. We experimentally show that the proposed uncertainty estimator closely matches the empirical results, with an average RMSE (root mean square error) of 0.02. This metric enables us to discover high- uighhuncertainty positions at later game stage via an analytical form.
Our evaluation indicates that using 10 variations per game achieves the best balance for exploration within and between games. Moreover, branching at positions selected uniformly at random leads to significant decrease in strength, with only 25.5% win rate against our proposed method, highlighting the critical role of branch point selection and the insufficiency of relying solely on the value ensemble. Finally, our end-to-end results show that our method improves sample efficiency over the baseline in both the early and late stages of training, achieving an improvement of up to 58.5% in 9x9 Go and 47.3% in 19x19 Go.
We use "branches" and "variations" interchangeably; "variation" follows the terminology used in GTP [12].

---

2
Background
self-play
100%
acting
80%
MCTS policy
policy label value label
Probability
policy label value label
MCTS value
40%
planning
learning
20%
Doubled simulations
Stonger network
NN policy NN value
0%
3
NN training
TopK of initial search result
Interaction of policy and value among the stages of acting, planning, and learning in AlphaZero. Our method further employs policy and value labels early during acting, as indicated by the red arrow.
Figure 2:
Figure 3: Probability that when doubling sim- ulations using stronger network, the new best move appears within the initial top k search results, conditioned cases where the original top-1 move changes.
2.1 AlphaZero
AlphaZero combines MCTS with a deep neural network (NN) to address complex decision-making problems. As shown in Figure its training process alternates between two phases: (1) self-play and (2) neural network training. In the self-play phase, AlphaZero generates games by acting, with each move determined through MCTS planning. In the training phase, the neural network is updated by learning from the collected self-play games. Specifically, the neural network learning target contains (i) a policy label, corresponding to the root visit count distribution MCTS, and (ii) a value label, representing the final game result. Moreover, during planning, the MCTS search tree is guided by the neural network policy and value to obtain the search result, typically requiring hundreds thousands of neural network predictions to obtain a search result. Once decision is made by MCTS planning, the resulting MCTS policy and value are used to select the next action or decide resign. Through the cycle of acting, planning, and learning, AlphaZero continuously refines its decision-making capabilities. Furthermore, unlike the original approach, our method augments the self-play process by incorporating not only the MCTS planning results but also the neural network learning targets (the red arrow in Figure 2) to guide acting. This additional label information enables us to explore more high-uncertainty positions during acting, as we will discuss later in Section 4.2.
2.2 Motivation
In this section, we study the relationship between stronger decisions and their rank in the search result. Previous studies [4, 5] have shown that, for more than 60% of positions, the best move remains unchanged after MCTS. Thus, we focus on the remaining 40% of important positions where the best search result changes. Specifically, we examine whether the new best decision emerges from novel, out-of-distribution (OOD) decisions or from a runner-up decision already present in the initial search.
To analyze this, we generate improved decisions by increasing simulation counts or using stronger network, and then compare the new best move the ranking in the initial search results. Figure shows that when search results change due to an increase in simulation count or a stronger network, the improved decision falls within the top of the initial search results in more than 80% of the cases. In contrast, OOD decisions account for only 10%. These observations motivate us to reuse the initial search results when exploring potentially stronger decisions. Since most improved decisions come from runners-up of the initial search, this approach avoids the cost of additional simulations or larger networks, while still providing high chance of improving the decision.
3 Related Work
Most prior works on improving AlphaZero's training efficiency and its variant, MuZero [13], focus on refining the training objective, such as introducing path consistency [9, 14], using contrastive
3

---

learning [15], and modifying the value target [16, 17]. Additional improvements involve enhancing prioritized experience replay [11, 18] and adopting an alternative training optimizer [8]. In contrast, our proposed method focuses on enhancing exploration during self-play, thus complementing these existing approaches toward efficient AlphaZero training. Furthermore, previous studies [19, 20] on uncertainty in deep reinforcement learning typically rely neural networks, such as predicting uncertainty using neural networks [5, 21-24), planning to explore with world models [25-27], or representing uncertainty as the discrepancy or variance between neural networks [28-30]. In contrast, we propose an analytical uncertainty metric that can be directly estimated from the results of the MCTS search. We also discuss the distribution assumptions for our work compared the previous works in Section 6.
On the other hand, previous work has also explored the option of solving hard exploration problems by revisiting unfamiliar states [31], or replaying trajectories starting from states of interest [6, 32] by sampling from an archive of positions. Similarly, KataGio [7] includes an option to fork from random position to play, especially in the opening phase of a game. However, these approaches primarily focus on early game exploration, as opening positions are often, naturally, of high uncertainty. As we show later in Section 5.2, these works fail to effectively target high-uncertainty positions the mid and late stages of a game. In contrast, our proposed uncertainty metric can identify such challenging positions across the entire game.
4
Methodology
We first establish the foundations of uncertainty estimation in Section 4.1. Then, we introduce uncertainty- guided branching for self-play to enhance training efficiency in Section 4.2.
4.1 Uncertainty Estimation
In this subsection, we quantify the reduction in training variance, introduce our uncertainty metric to guide exploration, and present a Bayesian framework for refining uncertainty estimation with empirical observations. Detailed proofs and derivations can be found in the appendix A.2.
Variance Reduction. First, to reduce variance in the training target, we ensemble multiple game results. To formalize this, let w be the win rate at a given position in game, and let Bernouli(w)) be the random variable representing the result of single game (winning not). Consider independent and identically distributed (i.i.d.) samples Zi,...; Zn Z. Then, the variance of the sample mean Z = >i= Zi/n is given by:
Var [ = w(1 101-w)) ww)/n.
(1)
In AlphaZero, the average game result Z over games played from a given position serves as the value label during training. Hence, by increasing the degree exploration from a given position, we can reduce the variance of the value label with more game results.
Uncertainty Estimator. Next, to quantify the uncertainty of the game results from given position s, we introduce the Label Change Rate (LCR), denoted by 0 = ICR(ss, defined as the probability that two independently sampled game results, Z, and Zj for i * j. are different as follows:
LCR(s) Pr(Zi + Zj) 2w (1 (1-
(2)
This metric also matches our intuition, since the uncertainty is highest when the win rate is 50% and approaches zero when the result is nearly determined; that is, when the win rate is close to 0 or 1. In practice, this metric enables an online uncertainty estimation during self-play by using the search value e to estimate 0.2 Moreover, we will show later in Section 5.2 that this analytical approach to uncertainty estimation aligns closely with the empirical results. In general, collecting more states with greater epistemic uncertainty can increase the degree of exploration and lead to more efficient training [19, 30, 33].
Bayesian Inference. When multiple game results are available for a given position, Bayesian inference can provide more robust estimate of the LCR since simply employing the search value
If the search value E [0, 1), we obtain an estimate 0 2e(1 v); otherwise, we rescale interpret win rate before computing 8.

---

to estimate w in Equation 2 ignores the uncertainty about itself. To address this, we model the LCR by treating the underlying label change probability 0 as a random variable. Thus, each observed label change is represented as X; ~ Bernoulli()), where X; 1 indicates that two independently sampled outcomes from the same position differ, and X; = otherwise. Given a sequence of i..dd observations D= {X1, Xz..... ), we perform Bayesian inference over 0, and define the LCR as the posterior expectation B[0 DJ. In practice, we can construct the observations as X; o2 using paired game outcomes for i E [1, m] and m Ln/2]. Alternative empirical choices are discussed in the appendix A.2.4. Let = Ei X; denote the number of observed label changes. Since the conjugate prior for the Bernoulli likelihood is the Beta distribution, we assume the prior 0 ~ Beta(a, 3), and thus the posterior distribution becomes 0 ~ Beta(a + s, B m s). Consequently, the corresponding Bayesian estimate of the posterior LCR is as follows:
m
a +
E DJ =
(3)
+ 3 + m
where the prior LCR- [0]
As an illustrative example, suppose that the MCTS search value for a position is v 0.6 [0, 1]. Then, the prior LCR is 2- 0.6 (1 0.6) = 0.48, according to Equation 2. If we perform four empirical trials (m = 4) and observe one label change (s 1). the posterior estimate becomes LCR
a+ 1.++1 ~ 0.414, where (a, 3) = (4.8, 5.2) and o+33 = 0.48. As expected, the 10-1
ats
posterior I.R decreases slightly, as the observed change rate (1 in 4) is lower than the prior estimate. The scale of a, 3 can be adjusted reflect the confidence the prior probability. In the next section, we will discuss how to integrate this estimation and its update into self-play to guide exploration.
4.2 Uncertainty-Guine Branching
Algorithm 1: Uncertainty-Guide Branching
(2)
m-
Input: G number of states to collect
Output: 9 =(state, policy label, value label))
21 2x
(3)
2113
(3)
2
(2)
inle
S
9 + 0
while | < G do
3
(s,a) + initial state and action
for i + 1 to V do
c-1
(3)
S3
label
5
((s,,((s)..) 2.) s E S,}+ +
play episode from (s.a)
IXC
7
Compute LCR and sampling weights
(defined in Equation 4)
Figure 4: An example of an uncertainty-guie
8
8~ YY())) (defined in Equation 5)
self-play game, where S; is the set of positions in variation i, with S₁ as the main sequence. 10
a~ <~<T(11 (
while (s, a) has been played do
s(1) is the position at time t, π (s{") is the pol- icy label obtained from MCTS, and 2; is the 12 game result. The value label at each position is computed as the average of all subsequent game results from that position, as indicated by the blue arrows.
preceding state of
a~ a~
S = UK S g gu ((s) (s', ((s), Enves, #t 1 }
13
14
((ENES))
15 return g
To improve training efficiency, this subsection integrates the previously discussed strategies for reducing variance in value labels and increasing exploration at high-uncertainty positions into our method. Figure illustrates an example game obtained by Algorithm 1, which contains a main branch
S₁ and two variations, S2 and Sy, where branching occurs at positions (1) and (1) respectively. In particular, for the first branching points, two different moves are sampled from π =(>?²)). resulting
in two variations starting from positions (1) and (?) which in turn lead game results 21 and 22, respectively. With more variations branched, we obtain more game results, allowing the value
label of & to be computed as the average of 2 and z2, rather than only relying single result. This reduces label variance and likewise reduces variance for all earlier positions that lead to these variations.
5

---

Algorithm I shows uncertainty guideed branching during pelf-play to produce policy and value labels for the training target. It begins by playing the main sequence from an initial state and obtains the training target for the first game variations Sj. We use "play episode from(s, a)" to denote playing a complete game from the state 8 starting with the action a, and the game playing process remains the same as in the original AlphaZero algorithm. After each completed episode, we calculate the posterior LCR for each position based on Equation and 3. Then, we select a high-uncertainty position based on sampling, and the weight assigned to each position is defined as follows:
- 4, if (s))) N LCRo
-
(4)
0o, otherwise.
where LCR, represents the uncertainty threshold. This hyperparameter is typically determined based on the initial win rate Wp so that we can discard positions whose win rates fluctuate around or remain weighted by their time step because want to capture the win rate turning point in the later game phase. We then sample the position to branch using a categorical distribution over the set of all positions S:
close to the initial win rate. In addition, positions
u(())
Y Categorical(p), where p(s) Eves u(6')
(5)
After selecting a position Y to branch from, sample action from the current position and play from there. If the sampled action has already been explored, especially in cases where only one legal move is available, we backtrack to an earlier position and repeat the sampling process. Once an unexplored action is found, we proceed with the play. If no such action can be found, we terminate the loop and return all collected variations early, which is unlikely, and hence we omit this case from Algorithm 1 for simplicity.
Moreover, discussed in Section 2.2, the runner-up decisions often have high likelihood of being the best moves. Thus, we select the branching move by resampling from the same policy distribution æ, which also aligns with the i.i.d. assumption introduced in the previous section. Overall, we employ the value label in the Bayesian inference and the policy label for action selection, as illustrated earlier in Figure 2. This branching process continues until predefined variation limit V is reached. In particular, when V = 1, our method reduces to the original AlphaZero algorithm without branching. Finally, the self-play process finishes when G states are collected, where G is the same hyperparameter as in the original algorithm.
5 Evaluation
We first provide our experimental setting Section 5.1. Then, we evaluate and compare empirical and analytical label change rates in Section 5.2. Following that, we evaluate the design space of our proposed approach in Section 5.3. Finally, we conclude by evaluating the end-to-end training efficiency in Section 5.4.
5.1 Experimental Setting
We evaluated our proposed method on 9x9 and 19x19 Go. To demonstrate that our approach improves efficiency for both early and late stages of training, we train the 9x9 Go model from scratch, while for 19x19 Go, we use a model pretrained with 100M samples. Our evaluations employ Elo rating [34] against the ttate-of-the-ar KataGo program [7], and the Elo rating is converted to the win rate to reflect relative playing strength. Detailed hyperparameters for self-play and training are provided in the appendix A.3.
Our experiments are mainly conducted on 2 NVIDIA A100 GPUs with 768 GB system memory. For the empirical analysis in Section 5.2, we collected 20,000 self-play game positions, requiring 10 A A100-hours. In Section 5.3, each evaluation on 19x19 Go requires 100 A100-hours, whereas the evaluations on 9x9 Go require 16 A100-hours each. Our end-to-end training experiments in Section 5.4 are conducted on a cluster of 5 nodes, each consisting of NVIDIA V100 GPUs and 768GB system memory. Each training run requires 800 V100-hours with additional 135 V100- hours for each evaluation. Both our method and the original one require about 23 GB of runtime memory, primarily due to the size of the replay buffer.

---

5.2 Label Change Rate
In this section, we show that our proposed uncertainty estimator, defined by Equation 2, closely aligns with the uncertainty observed in the empirical label changes. To compute the empirical LCR for a given position, we perform two independent game plays from the same position and compare whether their results differ. Then, the empirical I.R X for position is the ratio of games with changed results, averaged over 20,000 positions. As shown Figure 5, the empirical mean closely in agreement with the mean of the analytical estimators, with an RMSE (root mean square error) of 0.023. This suggests that our uncertainty metric provides reliable analytical estimate of uncertainty without requiring repeated empirical experiments at each position. Moreover, unlike empirical sampling, which yields only binary results per trial, we can now estimate the uncertainty for each position, denoted 0. Therefore, we adopt our analytical LCR estimator as a practical substitute for empirical uncertainty measurements in the following evaluations. In addition, we perform similar evaluations across different simulations in the appendix A.1.5.
In addition, Figure 5 shows that the LCR re- mains as high as 50% during the early stages of game, especially before move 60, leaving limited opportunities to capture additional high- uncertainty positions at this stage. In particular,
Empirical Mean 8
Est. Meun E(O]
Est. 0
50%
the original method is equivalent to branching at the first positions of game. In contrast, emphasize that uncertain positions continue to appear in game's mid-to-late stages. The fig-
40%
Label change
30%
ure shows the distribution of uncertain positions in the self-play games, represented by orange scatter points. Although the average LCR de- creases gets closer the end-game, we still observe that several games have an LCR above 40% the mid-to-late game, even if most po- sitions have nearly determined results and thus have a low LCR due less uncertainty. Hence, our method focuses on capturing those high- uncertainty positions, which are often buried by massive amount of uwweuretttintt positions. As a result, we use LCR not only as an uncer- tainty indicator but also how effectively different strategies explore high- uncertainty positions in game.
10%
0%
100
150
200
250
300
Move
Figure 5: Label change rate (LCR) across moves in 19x19 Go. The empirical mean X (blue line) is the average of observed label changes across positions, with a 95% confidence interval shown as the shaded blue region. Analytical estimates E(O] (orange line) are averaged from individual LCR estimators shown as orange seatter points.
metric evaluate
5.3 Design Space Exploration
80%
40%
50%
38%
Label change rate
Label change rate
60%
Win rate
336%
40%
40%
34%
30%
20%
32%
Variations (V)
5
10
15
20%
0%
30%
10
15
20
60
Variations (V)
Move
Figure 6: Win rate and label change rate under different variation limits V when training on the same number of samples 9x9 Go. The V= setting serves as the win rate comparison baseline, without incertainty-guider branching. Reported results have standard deviation of %..
7

---

80%
40%
50%
38%
Label change rate
Label chunge rule
40%
60%-
Win rate
36%
30%
40%
20%
34%
20%
32%
Random
0%
Ours 30%
100
150
200
250
Buseline
Random
Move
(a)
(b)
Figure 7: Win rate and label change rate under different branching methods when training under the same number of samples in 19x19 Go. Baseline denotes the original algorithm without branching and serves as the win rate comparison baseline; Random applics branching at positions selected uniformly random; Ours refers the proposed uncertainty -ggided branching method. Reported results have a standard deviation 1%.
To determine the degree exploration, we evaluate the efficiency of training across different variation limits V after training in 12M positions. Figure 6a shows that V = 10 produces the highest strength and outperforms the = 1 bascline by a 69% win rate under the same number of training samples, thus achieving the best training efficiency among different variations. Comparing V = 5 with the baseline, we find that the average LCR increases slightly and the strengths are close because there only limited amount of additional exploration. Furthermore, Figure 6b reveals that, with more variations explored, self-play, in general, contains more high-uncertainty positions. However, as V increases further, the degree of exploration begins saturate. In particular, we observe that the LCRs for V = 10 and V 15 are close. Since we collect a fixed number of positions per self-play iteration, increasing the number of variations per game can reduce the diversity of opening variations across games. As a result, while V = 10 and V = 15 both saturate the LCR within a game, V = 10 can achieve higher win rate since it can explore more diverse opening positions. Based on these observations, we adopt V = 10 in the following evaluations.
On the other hand, demonstrate that the label change rate is effective metric for branching, compared three methods: the baseline (no branching), uniformly random branching, and our proposed uncertainty-guider method, shown in Figure 7. For uniform branching, branching positions selected uniformly at random with total variations V = 10, and the new variation is played by resampling from the MCTS policy, similarly our method.
Figure 7a shows that our method achieves 62% win rate against the baseline after training on 12M positions in 19x19 Go. In contrast, random branching results in 35% win rate against the baseline and 25.5% win rate against our method, along with the lowest average LCR among all approaches. As shown in Figure 7b, compared to the baseline, the LCR of random branching is lower during the mid-game, while significantly higher in the end-game. This trend reflects the inherent complexity and uncertainty of mid-game positions, where uniformly branching is unable to distinguish between low and high uncertainty positions. Conversely, typically there are fewer choices moves during the end-game, high- uubbuunnnetttty positions have chance to be sampled with uniformly random exploration. Overall, uniform random branching explores more lower-uncertainty positions due to the lack of metric identify high-uncertainty positions, thus resulting in lower performance. This highlights the limitations of naive branching strategies and the insufficiency of relying solely on the value ensemble over multiple game results. In contrast, our uncertainty-guil -ggided branching consistently explores higher uncertainty positions throughout the game, as shown in Figure 7b, leading to more effective exploration and, eventually, to greater training efficiency.
5.4 End-to-End Training Efficiency
In this section, we evaluate the sample efficiency of our method compared to the baseline without branching the 9x9 and 19x19 Go games with the same amount of compute resources. shown in Figure 8, method consistently outperforms the baseline in both settings, indicating improved

---

300
1400
1200
250
Blo rating
1000
Elo rating
200
800
150
600
100
Ours
Ours
200
Baseline
Baselino
0-
20
40
60
15
25
Training samples (Million)
Training samples (Million)
(a) 9x9 Go.
(b) 19x19 Go.
Figure 8: End-to-end evaluation of sample efficiency. In 9x9 Go, models are trained from scratch, while in 19x19 Go, the performance is relative the pretrained model. Our method consistently achieves higher strength than the baseline with fewer samples.
training efficiency under the same training samples, and the standard deviation is about 2. %. In 9x9 Go, our method reaches the same performance as the baseline 40M and 80M samples using only 29.6M and 50.5M training samples, corresponding to 34.9% and 58.5% improved sample efficiency, respectively. On average, our method requires only 59.6% of training samples to reach the same strength as in the baseline. In particular, the gap between our method and the baseline becomes evident early and persists throughout, with our approach leading by an average 99.3 Elo rating under the same number of samples. In addition, we visualize the LCR distribution for self-play games in the appendix A.I.I.
Similarly, in 19x19 Go, our method matches the baseline's performance at 5M and 10M samples with only 3.9M and 6.8M samples, yielding 29.0% and 47.3% improvements in sample efficiency. This shows that, even in the later phases of training, our proposed method maintains a high sample efficiency. On average, our method achieves the same strength using only 66.4% the samples required by the baseline, and our approach maintains a consistent lead to the baseline by 75 Elo rating under the same number of samples. Overall, our end-to-end evaluations highlight better sample efficiency when adopting our proposed uncertainty-guidee exploration during self-play.
Discussion
Our L.R analysis requires the game result be binary discrete since we assume the Bernoulli distribution for the result. This sets our approach apart from many prior works [20, 23, 28] on uncertainty deep reinforcement learning, which typically assume more general continuous distributions such as Gaussian. Our Bernoulli setting allows us to derive a closed-fome LCR metric and significantly simplifies uncertainty analysis. Interestingly, in this case, there coincidence for the Bernoulli distribution that the value variance in Equation and the LCR in Equation 2, share similar form, and this relationship does not hold for general distributions. Moreover, extend the Bernoulli setting to continuous outcomes, one can define Bernoulli random variable X based == [(>>)) where is a threshold score. This
on whether the outcome exceeds a threshold: formulation may also be useful in hard-exploration tasks since completing sub-goal can be modeled as Bernoulli event. Alternatively, the LCR can be generalized by defining it as Pr([X; - -x, t), where >> is the threshold of measuring significant differences between outcomes.
Concluding Remarks
In this work, we proposed an uncertainty- -uided exploration framework that addresses key inefficien- cies in AlphaZero training. By branching out from sigh-uncertainty positions and exploring multiple variations, our method achieves two complementary goals: (1) reducing the variance of the value label by ensembling multiple game results in a tree-structured self-play setting, and (2) exploring previously overlooked yet promising decisions that may contain potential improvements. In general, our method is applicable to episodic reinforcement learning environments that allow the algorithm to return to specific state during acting. In our work, AlphaZero inherently assumes access perfect

---

simulator. However, such simulator is not strictly required, previous work [31] has already shown that returning to earlier states can also be accomplished by restoring memory states. Our future work includes extending the I.R analysis to continuous outcomes or generalized form, as discussed in the previous section, or applying LCR to multiple value heads [35] to guide exploration and improve interpretability for uncertainty. We believe that our analytical formulation for LCR opens up a promising direction for future research on uncertainty exploration in reinforcement learning.
Acknowledgments and Disclosure of Funding
This research is supported in part by DOE grant DE-SC0023186, NSF grants 2453653 and 221 2211018. and National Science and Technology Council of Taiwan project number BSTCC144-221-B-0001-
MY3. The opinions expressed in this paper those of the authors and not necessarily the views of the NSF or the DOE. We thank the Taiwan National Center for High-performance Computing (NCHC) for providing computational and storage resources. The authors would also like thank Cyan Subhra Mishra for helpful discussions and the anonymous reviewers for their valuable comments.
10

---

References
[1] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al., "A general reinforcement learning algorithm that masters chess, shogi, and go through self-play," Science, vol. 362, no. 6419, pp. 1140-1144 144, 2018.
[2] R. Coulom, "Efficient selectivity and backup operators in monte-carlo tree search," in Computers and Games: 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers 5, pp. 72-83, Springer, 2007.
[3] L. Koesis and C. Szepesvári, "Bandit based monte-carlo planning." in Machine Learning: ECML 2006: 17th European Conference Machine Learning Berlin, Germany, September 18-22, 2006 Proceedings 17, pp. 282-293, Springer, 2006.
[4] S. Cheng, M. T. Kandemir, and D.-Y. Hong, "Specullaivee monte-carlo tree search," Advances in Neural Information Processing Systems, vol. 37, pp.
2024.
[5] L.-C. Lan, T.-R. Wu, I.C. Wu, and C.-J. Hsich, "Learning to stop: Dynamic simulation monte- carlo tree search," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 267, 2021.
[6] A. Trudeau and M. Bowling, "Targeted search control alphazero for effective policy improve- ment," in Adaptive Agents and Multi-Agent Systems, 2023.
[7] D. J. Wu, "Accelerating self-play learning in go," arXiv preprint arXiv: 2019.
[8] Y. Mei, J. Gao, W. Ye, S. Liu, Y. Gao, and Y. Wu, "Speedyzero: Mastering atari with limited data and time," in The Eleventh International Conference on Learning Representations, 2023.
[9] D. Zhao, S. Tu, and L. Xu, "Efficient learning for alphazero via path consistency," in Interna- tional Conference on Machine Learning, pp. 26971 1 1-9981, PMLR, 2022.
[10] D. Willemsen, H. Baier, and M. Kaisers, "Value targets in off-policy alphazero: a new greedy backup." " Neural Computing and Applications, vol. 34, pp. 1801 1814, 2021.
[11] D. J. Soemers, E. Piette, M. Stephenson, and C. Browne, "Manipulating the distributions of experience used for self-play learning expert iteration," in 2020 IEEE Conference on Games (CoG), pp. 245-252, IEEE, 2020.
[12] G. Farnebäck, "GTP Go Text " "https://www.lyae"" 2002.
liu. sewu.eee/eeee wet.l//eeggunarree gunnar/gtp/",
[13] J. Schritwieser,, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D. Hassabis, T. Graepel, et al., "Mastering atari, go, chess and shogi by planning with learned model," Nature, vol. 588, no. 7839, pp. 604-609, 2020.
[14] D. Zhao, S. Tu, and Xu, "Generalized weighted path consistency for mastering atari games," Advances in Neural Information Processing Systems, vol. 36, pp. 50346-50357, 2023.
[15] W. Ye, S. Liu, T. Kurutach, P. Abbeel, and Gao, "Mastering atari games with limited data," Advances in neural information processing systems, vol. 34, pp. 25476-25488, 2021.
[16] Wang, S. Liu, W. Ye, J. You, and Y. Gao, "Efficientzero v2: Mastering discrete and continuous control with limited data," in International Conference Machine Learning, 2024.
[17] A. Borges and A. Oliveira, "Combining off and on on-policy training in model-based reinforcement learning," arXiv preprint 11X::2102.11194 2021.
[18] Y. Oh, J. Shin, E. Yang, and S. J. Hwang, "Model-augmented prioritized experience replay," in International Conference Learning Representations, 2022.
[19] Y. Jiang, Z. Kolter, and R. Raileanu, "Uncertainty-driven exploration for generalization in reinforcement learning." in Deep Reinforcement Learning Workshop NeurIPS 2022, 2022.

---

[20] S. Lahlou, M. Jain, H. Nekoei, V. I. Butoi, P. Bertin, J. BrotorrBrooos, M. Korablyov, and Bengio, "DEUP: Direct epistemic uncertainty prediction," Transactions on Machine Learning Research, 2023.
[21] V. Mai, K. Mani, and L. Paull, "Sample efficient deep reinforcement learning via uncertainty estimation," in International Conference on Learning Representations, 2022.
[22] S. Aravindan and W. S. Lee, "State-aware variational thompson sampling for deep q-nerworks," in Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '21, p. 124-132, International Foundation for Autonomous Agents and Multiagent Systems, 2021.
[23] W. R. Clements, B. Van Delft, B.-M. Robaglia, R. B. Slaoui, and S. Toth, "Estimating risk and uncertainty in deep reinforcement learning," arXiv preprint prrXiv:9955.00 2019.
[24] M. Fortunato, M. G. Azar, B. Piot, J. Menick, M. Hessel, I. Oshand, A. Graves, V. Mnih, R. Munos, D. Hassabis, O. Pietquin, C. Blundell, and S. Legg. "Noisy networks for exploration," in International Conference on Learning Representations, 2018.
[25] Y. Sun, F. Gomez, and J. Schmidhuber, "Planning to be surprised: Optimal bayesian exploration in dynamic environments," in International conference on artificial general intelligence, pp. 41- 51, Springer, 2011.
[26] R. Sckar, O. Rybkin, K. Daniilidis, P. Abbeel, D. Hafner, and D. Pathak, "Planning to explore via self-supervised world models," in International conference on machine learning, pp. 4583-8592, PMLR, 2020.
[27] P. Shyam, W. Jaškowski, and F. Gomez, "Model-based active exploration," in International conference on machine learning, pp. 5779-5788, PMLR, 2019.
[28] Osband, Aslanides, and A. Cassirer, "Randomized prior functions for deep reinforcement learning," Advances in neural information processing systems, vol. 31, 2018.
[29] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy, "Deep exploration via bootstrapped dqn," Advances in neural information processing systems, vol. 29, 2016.
[30] R. Y. Chen, S. Sidor, P. Abbeel, and J. Schulman, "Ucb exploration via q-ensembles," arXiv preprint arxivv11066 01 502, 2017.
[31] A. Ecoffet, J. Huizinga. J. Lehman, K. O. Stanley, and J. Clune, "First return, then explore," Nature, vol. 590, no. 7847, pp. 580-586, 2021.
[32] A. Tavakoli, V. Levdik, R. Islam, C. M. Smith, and P. Kormushev, "Exploring restart distribu- tions," arXiv preprint
2018
[33] C. Luis, A. G. Bottero, Vinogradska, Berkenkamp. and J. Peters, "Model- -Model-based uncer- tainty in value functions," in International Conference on Artificial Intelligence and Statistics, pp. 8029-8052, PMIR, 2023.
[34] R. Coulom, "Computing "elo ratings" of move patterns in the game of go." ICGA journal, vol. 30, no. 4, pp. 198-208, 2007.
[35] T.R. Wu, I.-C. Wu, G.-W. Chen, T.-H. Wei, H.-C. Wu, T.-Y. Lai, and L.-C. Lan, "Multilabeled value networks for computer go." IEEE Transactions on Games, vol. 10, no. 4, pp. 378-389, 2018.
[36] L. v. d. Maaten and G. Hinton, "Visualizing data using t-sne," Journal of machine learning research, vol. 9, no. Nov, pp. 2579-2605, 2008
[37] K. Hc, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition." in Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 770-778, 2016.
[38] I. Danihelka, A. Guez, J. Schrittwieser, and D. Silver, "Policy improvement by planning with gumbel," in International Conference on Learning Representations, 2022.
[39] J. Wu, "Networks for katal." ". "https:/ http://gaaattttiiinggggggo org/networks/", 20000
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction are aligned with the paper's method and evaluation results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation and the scope of the work in Section 6 and 7.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Theory proof' and analysis are provided in Section 4.1 and appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Detailed experimental settings are provided Section 5.1 and appendix, and all experiments results of multiple evaluations.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: The model checkpoints are provided in https://hugginggaacccom chengscott/ugb. zero.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https: //iips.cocc httpp/cccppulllc//geeeee http://giieeee/oeeeeeeeeee
ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Detailed experimental settings are provided Section 5.1 and appendix. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Experiment statistical significance are provided in Section 5.1 and in each evaluation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Experiment compute resources are provided in Section 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttpp:::///uurss.... tttp:://earrpp..cpp/bbl//
ines?
Answer: [Yes]
Justification:
All authors conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper focuses on improving training efficiency.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper focuses on improving training efficiency.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets properly credited and cited in the paper.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https httpp:://neurigee cc///oofeeeenccc//22///.... for what should or should not be described.
19

---

A Appendix Supplemental Material
A.1 Additional Evaluation
A.1.1 Visualization
(a) Baseline.
(b) Ours.
Figure 9: Visualization of the LCR distribution among self-play games. The heatmap color indicates the LCR, with red representing higher values. Each line connects adjacent moves within the same game variation.
Figure 9 shows the visualization of the LCR distribution for both the bascline (without branching) and our proposed method with V 10 on 9x9 Go after training on 60M samples. We project self-play game positions into two dimensions using t-SNE [36], connect successive positions from the same game variation with lines, and color them according to their LCR values.
Figure 9a shows the LCR distribution of the baseline method, which consists of unbranched lines, each representing game. Note that some lines may overlap due the projection from a high- dimensional space. This visualization matches the earlier result shown in Figure 5, where for most of the games, the L.R is high during the game's early stage and gradually decreases toward the end-game; i.e., one end of the line is red and the other end is blue. Interestingly, some lines remain entirely blue, indicating persistently low uncertainty throughout those games. These positions likely correspond to early losses in games, resulting from exploring obviously losing positions. On the other hand, Figure 9b presents the LCR distribution our proposed method, where most games form spike- cluster due branching. Overall, observe that self-play games contain more positions. In particular, we
red lines than the baseline, indicating a higher number of do not branch from positions that are entirely blue (i.e., low uncertainty).
A.1.2 LCR Threshold Sensitivity
(v
80%
LCR, -u.30
Distribution
LCR, 0,420 (v-70)0
60%
LCR, 0.487
40%
LCR, 0.480 0.50)
LCRR, 0..977 0.54)
20%
0.089
0%
50
100
150
200
250
300
Move
Figure 10: Percentage of positions whose LCR exceeds LCR threshold (LCRg) for each move. Each curve corresponds to different threshold with its corresponding value in parentheses. particular, 0.6 is the initial value for an empty position.
To demonstrate the robustness of various LCR thresholds, Figure 10 shows the distribution of positions whose LCR exceeds given threshold. As the threshold decreases, the percentage of
20

---

selected positions gradually increases at each move, which aligns with our intuition: highly uncertain positions often occur near other uncertain positions, whether preceding or following. Additionally, since 0.58 is close to the initial win rate (0.6), the I.CR of early-game positions often lie near the LCR threshold, leading to a greater variability in the distribution. These results suggest that the LCR threshold is a robust hyperparameter, as slight changes in the threshold often result in only small number neighboring uncertain positions and do not cause abrupt changes the selection volume.
A.1.3 High-Uncertainty Position Distribution
1.00%
distribution
0.80%
Sample distr ibution
Distribution
0.60%
0.40%
0.20%
Move
Figure 11: Distribution over move numbers for positions where the LCR exceeds the threshold (0.48). The red bars represent the data distribution (original distribution over all positions), while the blue bars show the sampling distribution, obtained by drawing from the data distribution with weights proportional to the move number.
To gain additional insights into our proposed branching strategy, Figure shows the distribution of high-uncertainty positions across different move numbers. The red bars represent the data distribution, corresponding to positions exceeding the LCR threshold, while the blue bars show the sampling distribution obtained by weighting the data distribution according to move number, as defined in Algorithm 1. We observe that the data distribution decreases steadily as the game progresses, reflecting the sparser orange scatter points above the LCR threshold in Figure 5 during later stages, In contrast, the sampling distribution is concave, starting low in the early moves, rising to peak around move 1 110, and then gradually declining.
Based on these observations, without branching, exploration of high- uighhunnertainty moves during self- play would implicitly follow the red distribution. With our LCR-guided branching, we explicitly identify high-uncertainty positions and increase the probability of exploring them, especially in the mid-to-late game, as evidenced by the region enclosed by the data and sample distribution. In general, this analysis can be applied to various uncertainty metrics.
A.1.4
Alternative Uncertainty Metries
4.00%
4.00%
Distribution
3.00%
Distribution
3.00%
2.00%
2.00%
1.00%
1.00%
0.00%
0.00%
100
202
250
50
200
250
Move
Move
(a) MinV: positions in the lowest 10% of 0.5, where v(8) is the MCTS value.
(b) MinMaxP: positions in the lowest 10% of max(m(-) s)), where < | s) is the MCTS policy.
Figure 12:
Distribution over move numbers for positions identified as high-uncertainty by the alternative uncertainty metrics, MinV and MinMaxP.
21

---

type
type 2
type
type 4
type
type 2
type
type 4
100%
80%
80%
Distribution
Distribution
60%
60%
40%
40%
20%
20%
0%
0%
100
150
200
250
150
250
Move
Move
(a) (LCR, MinMaxP)
(b) (MinV, MinMaxP)
Distribution of positions across four uncertainty categories, defined by combinations of value and policy uncertainty shown in each subfigure. The four types are defined as follows: type has high value uncertainty and high policy uncertainty: type 2 has high value uncertainty and low policy uncertainty; type has value uncertainty and high policy uncertainty; and type 4 has low value uncertainty and low policy uncertainty.
Figure 13:
1400
300
1200
Elo rating
1000
Elo rating
800
200
100
Baselino MinV
200
Baseline
0
0-
20 40
60
80
0
10
20
40
50
Training samples (Million)
Training samples (Million)
(a) 9x9 Go with MinV.
(b) 19x19 Go with additional training samples.
Figure 14: End-to-end evaluation of sample efficiency.
In addition to proposed LCR metric, define two alternative uncertainty metrics, MinV and MinMaxP, based on MCTS value and policy, respectively. Figure 12 presents the distribution of nigh-uncertaintyy positions under each metric, similar to Figure 11. The MinV distribution shows a similar distribution to LCR, as both are value-based metrics. In contrast, MinMaxP exhibits an opposite trend: its mass concentrates in the endgame, where game results nearly determined. This is because multiple moves in the endgame often lead to the same game result, corresponding to high policy uncertainty. As expected, MinMaxP also identifies some sarly-game positions with high policy uncertainty, but these are much fewer compared to the endgame.
Moreover, Figure 13 shows the distribution each move of uncertainty categorized into four types. Similar to our earlier observations, value-hased metrics identify high-uncertainty positions primarily in the early game, whereas policy-based metrics detect them mainly in the endgame. As result, when only using the MinMaxP metric, the end-to-end training fails. Figure 14a shows the end-to-end training sample efficiency with MinV metric. We observe that the MinV shows similar efficiency to ours during the early stage of training, but later slows down and approaches the baseline. This is because simply using fixed percentage of the lowest value alone can only capture certain amount of high-uncertainty positions, which lacks the flexibility to identify uncertainty per position, as in our proposed LCR metric. On the other hand, we provide more training samples to Figure 8b in Figure 14b. Our method still outperforms the baseline at later phase of training.
A.1.5 Scaling of the Label Change Rate
In addition Figure 5, Figure 15 shows the evaluations of empirical and analytical LCR estimation for simulations ranging from 5 to 800. Among all simulations, all curves show similar trend, and the
22

---

Trrpiical
Englikel Moen.X
50%
50%
Libe chandhnnnn rate
80%
60%
40%
change
20%
20%
20%
Libe
10%
10%
100
1.00 Move
2001
250
700
100
150 Move
200
250
700
50
100
150 Move
203
250
500
(a) simulations.
(b) 10 simulations.
(c) 25 simulations.
Imporical Mon
Est, Meas ER
Bst
Iirpicial Mean X
Est. Meas E(i)
Bat
Immpncaal Mear.
Est. Meat E Ba.
50%
50%
30%
Label change
10%
30%
10%
20%
20%
20%
0%
0%
0%
150 Move
(d) 50 simulations.
(c) 100 simulations.
(f) 200 simulations.
Impiriall Mon
De. Morn Ei
Drpriiaa
Txt E
Label change sste
40%
Label change aske
40%
Label diange moto
30%
30%
30%
100
20%-
20%
10%
10%
10%
0%
0%
100
150
100
200
250
(g) 400 simulations.
(h) simulations.
(i) Comparison of E((] curves from panels (a-h).
Figure 15: Label change rate (LCR) with different simulation counts. The empirical mean X (blue line) is the average observed label changes across positions, with a 95% confidence interval shown as the shaded blue region. Analytical estimates E[ő] (orange line) are averaged from individual LCR estimators 0, shown as orange scatter points.
empirical and estimated means are closely aligned. On the other hand, in Section 5.2, we computed the RMSE by comparing the empirical mean (blue line) with the estimated mean LCR (orange line) in Figure 5. Another way to compute the RMSE based on per-position comparisons. Specifically, position obtain empirical change rate, and then
simulate 10 game results from the compare this to the estimated L.C.. The RMSE computed by comparing the mean for 5, 10, 25, 50, 100, 200, 400, 800 simulations is 0.07, 0.08, 0.05, 0.04, 0.03, 0.02, 0.02, 0.02, respectively; the RMSE computed by per-position comparison is 0.14, 0.13, 0.12, 0.11, 0.12, 0.11, 0.18, 0.14, respectively. The RMSE for the per-position comparison is higher, as each position requires more simulations for accurate estimation.
Furthermore, Figure 15i shows the comparison of the estimated mean among different simulations. When the simulation count smaller, the LCR is lower, meaning the game is likely to lose earlier and faster. In contrast, when doubling the simulations, the LCR at the linearly, and thus the game result less determined compared to a smaller simulation. This evaluation only demonstrates that proposed LCR scales well across simulations but also suggests that it a potential metric for detecting the strength of a position.
move is increased almost
23

---

Suppose Z Bernouli(ww). meaning that Z is random variable that takes the value with iid A.2 Proofs
In this section, we provide the proofs and derivations for Section 4.1, corresponding to appen- dices A.2.1, A.2.2 and A.2.3. In addition to the Bayesian inference presented carlier, also present an alternative formulation of Bayesian inference appendix A.2.4.
A.2.1 Variance Reduction
probability w and O with probability - w. Let Zı..... Zn ~ Z, and define the sample mean as Z Di=1 Zi/n. Then,
VarlZ]
Var
Zi
Var [2c]
1 n
Σ
w(1 w) w(1-w) w)
(6)
71
n
This result follows from the fact that the variance of a Bernoulli(w) random variable is w(1 w). and that Z; are independent and identically distributed.
A.2.2 Uncertainty Estimator
According to the definition of the label change rate (LCR) in Section 4.1, we compute the LCR for two saaeeenndnnn--ssamppee variables Z, and Zj. where + j. follows:
Pr(Z: # Zz) = Pr(Z: = 0, 2 = 1) + Pr(Z: = 1, Z, = 0)
(7)
(1 - w + w(1 - w)
(8)
= 2w((1 - w)
(9)
Similarly, we can compute label unchanged rate as:
Pr(7: Zz) Pr(Za 0, Z, 0) + Pr(Z 1,
(10)
w) 2 w
(11)
Thus, we can define random variable that equals I if Z, * Zy, and 0 otherwise:
1 for some + j. This an indicator variable
1 if 2z,
X
(12)
0 if = Zy.
Moreover, we can write the probability mass function of X as:
p = w) = [2w - w)
if 1
(13)
w2 + (1 w)²
if x = 0
and the expectation of X is
E X Pr(Z; + 2z) = 2wo - w).
(14)
It is important to note that these results hold for any i j. In the following, we explore how different choices of i and lead different Bayesian formulations.
A.2.3 Bayesian Inference
Suppose that we observe a sequence of label change rates, denoted as dataset D (X1, X2...., X,), where X, iid. Bernoulli()) and 0 represents the random variable for la- bel change. In particular, we choose X, 2a using paired game outcomes for i E [1,m],
24

---

where m = In/2]. Since the X; are i.i.d., the joint likelihood of the data is:
p(D 0) = p(X1, X2,.... Xm ()
(15)
m
II p(X; 10)
(16)
II 0x (1 0) (1-x) 1=1
(17)
(b Xi (1 8 1
(18)
0 (1 0)m m-
(19)
(20)
where E X; is the number of observed label changes. On the other hand, according to Bayes' theorem, the posterior distribution given by:
p(0)p(D)
p(0 D)
(21)
/ p(0)p(D (0) d0
where p(0) is the conjugate prior for the Bernoulli likelihood, which is the Beta distribution. Thus, we express the prior probability distribution as 0 ~ Beta(a, (3). Namely,
p(0)
B(a,3) 0t -1 (1 038 x 00-1(11- 038-1
1
(22)
where B(a, (3) is the Beta function. We also have
E[O]
(23)
B B
= Pr(Zzs # (2x-1) = 2w(1 - w),
(24)
where Equation 23 is the expectation of Beta(a, 33 and Equation 24 is derived from Equation 14 by definition. By applying Bayes' theorem, the posterior distribution is proportional to the product of the prior and the likelihood:
p(0 D) x p(D ()) p(0) x 08 - 0)m .00=1 - 018-1 = pouto-1(1 - 0) --mm---- (25)
Thus, the posterior distribution is:
D ~ Beta(a + s, mm s)
(26)
The posterior mean, which serves as the Bayesian estimate of namely the posterior label change rate (LCR), is given by:
a +
E
D
(27)
a +
A.2.4 Alternative Bayesian Inference
Previously, we only used m = n1/ of the n observed label changes for the Bayesian update. In this section, study the option of using update, which breaks the independent assumption. In particular, we choose X, = 12,42_,, using the previous outcome to calculate the label change rate for [2. In this case, X;s are still identically distributed to Bernoull(()) but not independent. Before we dive into the caleulation of p(D] 0), we first define as the xor operation, namely, the addition under mod 2. Hence, have X, = Z, + Z = Z₁ + Z and thus,
1 observed label changes for Bayesian
2, = Z $ X;
(28)
Zi ② (X2 ① ... X³).
(29)
25

---

Then, we have the following probability:
Pr Z1 = 21) = 8 (1 - -0) 0)
(30)
Pr(Z* = 2/ X1 z1) = Pr = 21 B
X1 = x1) = =0 (0----
0) 1- 0s. 0000
(31)
where 8; = 22 L ... + 2/ and 2, = 21 θ 84-
Then, the joint probability of the dataset is
Pr(X2 T2..... X2 = =xn)= =
Pr(Zi = 21) 22 .,,,,,,, In 21 = =1)
(32)
=1=0
Σ
Pr(Zi Pr(X2 = 21 21 82,
X₂ = 21 8n
21 21)
(33)
Pr(Zi = =11)
II
Pr(X, = x1 0sk 21 = =1)
(34)
=1=0
k=2
Σ
0 (1 00 1-
0 (1 0) 1 1-21 158
(35)
=1=0
k=2
(1 0) 0% (1 0) 10 0 0 5k (1 0)*h
(36)
since we have 21 @ 8k 8% when 21 0, and 21 ① 8k =1 8k when 21 1.
Let my = Σx sy be the number of ones in { ( 8p and mg = n n-m m- Then, we can rewrite the joint probability as:
P(X = 2) = 0mh (1 0) + 0 (1 0)m
(37)
Suppose that we still assume Beta prior, that is, 0 Beta(a, 3). By applying Bayes' theorem, the posterior distribution can be expressed as:
p(0 D) p(D) 0) p(0) (0 - (1- + 0 (1 m) 0a-1 0))8-1 x 0ma (1 00 1 + (1 - 0)
(38)
(39)
Thus, the posterior distribution becomes
0 D Beta(m, + a, my + 3) + Beta(mo + +a, m2 + B).
(40)
And the corresponding posterior LCR is:
(a + m: mm) + +a+ mo + B) + (a + mo) + + m1 + +B)
E DJ
(41)
(a (+))(B(mm + a, mo B) + B Bmm + az m. + B)
26

---

A.3 Hyperparameters
Table shows the hyperparameters for self-play and training. In 9x9 Go, the model consists ResNet residual blocks [37] with 96 channels each, while in 19x19 Go, the model consists of Nested Bottleneck blocks [38] with 192 channels each, following the model architecture in the latest KataGo models [39]. Our pretrained model follows previous work [7] to train on the first 100M samples from the public repository [39] and set baseline of an Elo rating 9958. Moreover, the LCR threshold for Equation 4 is LCRRo = 0.48 for both games.
Table I: Hyperparameters for self-play and training.
9x9 Go
19x19 Go
19x19 Go Pre-training
Training
Training
MCTS simulation
400
MCTS Cpuct
1.25
Self-play
Dirichlet noise ratio è
0.25
Dirichlet parameter a
0.12
0.03
G states per iteration
0.3M
1.2M
Optimizer
SGD
Batch size
512
Training
Optimizer: momentum
0.9
Optimizer: weight decay Optimizer: learning rate
le-4
0.01
Sample factor
2
1
2
27


Reviews:
[{"review_id": "sGE95BJI8e", "reviewer": "Reviewer_GEKg", "summary": "The paper tackles a long-standing inefficiency in AlphaZero-style self-play: most positions are visited only once and the single game result used as a training target is noisy.\n\nThe authors propose **Uncertainty-Guided Branching (UGB)**:\n\n- Label Change Rate – an analytic, closed-form estimate of how likely the game outcome would flip if the same position were replayed. A Bayesian update refines LCR when repeated roll-outs are available.\n- Where / how / what to branch – positions whose posterior LCR exceeds a threshold are selected; 10 runner-up MCTS moves are replayed from each such position; their outcomes are ensembled to reduce value-label variance.\n- Extensive experiments on 9 × 9 and 19 × 19 Go shows an improved sample efficiency over the baseline by 58.5% on 9x9 Go in the early stage of training and by 47.3% on 19x19 Go in the late stage of training.", "questions": "1. Could the authors provide wall-clock training time and per-move latency overhead relative to the baseline?\n2. How robust is performance to the LCR threshold or to choosing 5 vs 10 branches when total compute is fixed?\n3. An ablation without the Bayesian update would clarify its added value?\n4. The Elo ratings for both baseline and Ours are still small on Figure 8 (b). Could the authors provide a figure with more training samples?", "limitations": "See questions.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The paper is well structured with core ideas explained.\n\n- Tackles an important inefficiency problem in Go self-play.\n\n## Weaknesses\n\n- GPU-hour counts are given, but end-to-end wall-time and memory impact of branching are not reported.\n\n- Branching change the visited distribution; effect on final policy optimality vs exploration bias is not analized.", "was_revised": true, "final_justification": "I appreciate the commitment to include detailed wall-clock time, latency overhead, and memory usage analysis in the final revision. For Bayesian Update Ablation, the rebuttal only promises an additional discussion.", "rebuttal": "We thank the reviewer for the feedback. We have conducted additional experiments for the rebuttal, and we will include them in the final revision, as this year's rebuttal phase doesn't allow authors to upload a PDF or any images. We address each comment as follows:\n\n> GPU-hour counts are given, but end-to-end wall-time and memory impact of branching are not reported.\n\nAs noted in Section 5.1, the wall‑time for each experiment can be computed by dividing the reported GPU‑hours by the number of GPUs used. Moreover, we'll also include the Slurm job scheduling logs as part of our final data artifact. Regarding memory usage, our proposed method requires storing only an additional LCR variable per game step, which corresponds to about a 2.5% increase in memory usage (calculated by sizeof(float) / sizeof(Record)). We'll include detailed runtime and memory usage information in the revision.\n\n> Branching change the visited distribution; effect on final policy optimality vs exploration bias is not analized.\n\nOur proposed method preserves the training targets unbiased, as in standard AlphaZero: policy labels come from the MCTS visit counts, and value labels remain the unbiased average of game returns. Moreover, the AlphaZero algorithm doesn't promise global optimality but instead relies on iterative policy improvement via self‑play MCTS [1]. Because our method does not modify the PUCT formula and the MCTS policy‑improvement operator, each iteration under the shifted visit distribution remains a valid policy‑improvement step, although the sequence of improved policies may differ from the original AlphaZero. As a result, we still retain AlphaZero's core policy improvement behavior. Overall, we acknowledge that a quantitative analysis on the final policy optimality of the AlphaZero algorithm and its variants remains an open problem for future investigation.\n\n[1]: Grill, J. B., Altché, F., Tang, Y., Hubert, T., Valko, M., Antonoglou, I., & Munos, R. (2020, November). Monte-Carlo tree search as regularized policy optimization. In International Conference on Machine Learning (pp. 3769-3778). PMLR.\n\n**Q**: Could the authors provide wall-clock training time and per-move latency overhead relative to the baseline?\n\n**A**: We'll include the runtime latency and memory usage in the revision.\n\n**Q**: How robust is performance to the LCR threshold or to choosing 5 vs 10 branches when total compute is fixed?\n\n**A**: In the revised version, we'll include a graph showing the distribution for positions whose LCR exceeds a LCR threshold. More specifically, the graph will show a gradual increase in percentage for each move as the LCR threshold is decreased. The result also aligns with our intuition, as a highly uncertain position is typically accompanied by a highly uncertain adjacent previous/next position. For instance, consider a sequence of LCR values: …, 0.47, 0.48, 0.49, 0.46, …\n\nAt threshold LCR_0 = 0.48, 2 positions are included in the candidate pool.\n\nAt LCR_0 = 0.47, 3 positions are included.\n\nAt LCR_0 = 0.46, 4 positions are included.\n\nAs a result, this suggests that the LCR threshold is a robust hyperparameter, since a slight change in the threshold often only admits a small portion of adjacent uncertain positions without causing abrupt changes in the selection volume. \n   \nOn the other hand, all experiments in the paper are compared under a fixed total compute resource, including the study of variation V in Section 5.3. The compute resource per iteration is determined by the hyperparameter G in Algorithm 1, which is fixed among all settings for each game.\n\n**Q**: An ablation without the Bayesian update would clarify its added value?\n\n**A**: Our method adopts a Bayesian perspective to model the MCTS value as a random variable, rather than a fixed estimate under the frequentist view. This modeling choice is particularly motivated by our branching strategy, which typically only has a small number of variations (V). To address this low-sample setting, the Bayesian approach can offer better sample efficiency by leveraging the assumed prior distributions. While we don't include an ablation study comparing the Bayesian update to a frequentist counterpart, we'll include a discussion in the revision to clarify the role of the Bayesian update in our approach.\n\n**Q**: The Elo ratings for both baseline and Ours are still small on Figure 8 (b). Could the authors provide a figure with more training samples?\n\n**A**: We'll include a figure with more training samples in the final revision. It is to be noted that Figure 8 (b) is based on a pre-trained model with an Elo rating of 9958, corresponding to a training sample of 0 in the figure, as our goal was to evaluate the model at a later phase of training. At this stage, smaller Elo gains are expected as the performance curve starts to plateau."}, {"review_id": "L0U7PHoOmn", "reviewer": "Reviewer_CiWs", "summary": "This paper proposes a novel uncertainty-guided exploration of positions in self-play for AlphaZero. Using a proposed Label Change Rate (LCR) metric, positions with high uncertainty are identified after self-play trajectories are generated.  The LCR values are used to sample an uncertain state, and a new action is sampled from the policy in that state, generating a new trajectory. This is repeated V times, and all the generated trajectories are used to estimate values of states and as training data for the Neural Network training phase of AlphaZero. Experimental results show the accuracy of the LCR metric, and the sample efficiency gains of the proposed method, in two variants of Go.", "questions": "1. I was a bit surprised that the experiment in section 5.2 only included two independent game plays from each position. Would the results change if more game plays were performed, getting a more accurate estimate of LCR for each position, but perhaps sacrificing the number of positions that could be averaged over?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper was generally clear and well-written.  \n- The proposed idea is simple, and to my knowledge original, but shows clear promise in the experimental results. \n- The evaluation experiments were well-designed and clear. I liked the methodology used to determine the best V value, as an example.\n\nWeaknesses: \n- Perhaps it was just me, but it took a second pass through the paper to grasp the overall idea of what was happening in the paper, what the main idea actually was.  I think a lot of this was due to a misunderstanding of how some of the terminology (ie \"variations\") was being used.  I think that could have been made a bit more clear. \n- It seems that a few more alternatives could have been included in the experimental results, beyond simply the baseline and random selection of branching points.  For example, uniformly sampling among branch points with LCR above threshold, instead of utilizing the time step of the move to bias towards later in the game. \n- It is unclear how some of the decisions made, like V=10, would translate to other domains beyond Go.", "was_revised": true, "final_justification": "For the reasons outline earlier, I think that this is an interesting approach and the obtained results are encouraging.  I like this paper and think that it should be shared.", "rebuttal": "We thank the reviewer for the feedback. We have conducted additional experiments for the rebuttal, and we will include them in the final revision, as this year's rebuttal phase doesn't allow authors to upload a PDF or any images. We address each comment as follows:\n\n> Perhaps it was just me, but it took a second pass through the paper to grasp the overall idea of what was happening in the paper, what the main idea actually was. I think a lot of this was due to a misunderstanding of how some of the terminology (ie \"variations\") was being used. I think that could have been made a bit more clear.\n\nWe use the terms branch and variation interchangeably in the paper. To improve clarity, we'll revise and move footnote 2 to an earlier section in the paper.\n\n> It seems that a few more alternatives could have been included in the experimental results, beyond simply the baseline and random selection of branching points. For example, uniformly sampling among branch points with LCR above threshold, instead of utilizing the time step of the move to bias towards later in the game.\n\nWe'll include a figure showing the distribution of high-uncertainty positions across moves in the final revision. This figure shows the data distribution and the sampling distribution, which is obtained by drawing from the data distribution with weights proportional to the number of moves. With this analysis, we can employ a different sampling strategy, such as uniform sampling, and compute its corresponding sample distribution to gain insights from the properties of the sample distribution, including the mean and quantiles.\n\n> It is unclear how some of the decisions made, like V=10, would translate to other domains beyond Go.\n\nThe variation V is a hyperparameter to our algorithm. Similar to Figure 6(b), we believe that studying the relationship between the variation V and LCR per move for a few training iterations can provide a projection for performance in other application domains.\n\n**Q**: I was a bit surprised that the experiment in section 5.2 only included two independent game plays from each position. Would the results change if more game plays were performed, getting a more accurate estimate of LCR for each position, but perhaps sacrificing the number of positions that could be averaged over?\n\n**A**: We have conducted an additional experiment using 10 independent game plays per position (compared to 2 previously), and will include a corresponding figure in the final revision. The results follow the same trend as in the original Figure 5. We'll also include results for 100, 200, and 400 simulations in the revision."}, {"review_id": "wZmSsWnB8J", "reviewer": "Reviewer_gKQg", "summary": "This paper addresses an important and practical problem: enhancing exploration efficiency in AlphaZero's training process. The authors correctly point out the inefficiency inherent in AlphaZero’s traditional approach of initiating self-play games from the starting position every time, leaving many high-uncertainty states under-explored.\n\nTo resolve this issue, the authors introduce a well-defined uncertainty estimation metric called \"Label Change Rate (LCR).\" LCR intuitively and effectively quantifies state uncertainty by calculating the variability of outcomes from the same position across multiple game plays. The authors further solidify this approach through a robust Bayesian inference framework. This method clearly identifies the core of the problem and serves as a strong baseline.\n\nThe experimental design is thorough: initially validating the effectiveness and accuracy of LCR, then analyzing the impact of different branching strategies and positions on exploration efficiency, and finally demonstrating the benefits through comprehensive end-to-end training evaluations. Overall, the experimental results are convincing, showing that the proposed uncertainty-guided exploration method significantly improves AlphaZero’s training efficiency and performance.", "questions": "Distribution of LCR-Uncertain States:\nCould the authors provide an analysis of how the LCR-uncertain states are distributed across different game stages (e.g., early, mid, late game)? Understanding this distribution could offer insights into which game phases most benefit from the proposed branching strategy.\n\nImpact of MCTS Simulation Counts on LCR Accuracy:\nIt would be valuable to investigate how the accuracy of the LCR metric varies with different MCTS simulation counts. Considering recent methods frequently utilize fewer simulations (e.g., 100-200), compared to traditional settings (e.g., 800), evaluating LCR across varying simulation counts could validate its robustness and practical applicability.\n\nClarification on RMSE Analysis Methodology:\nThe current RMSE evaluation approach is not entirely clear. A suitable method might involve first obtaining multiple simulation results (like geting n=1000 z values) for each of the 20,000 positions, calculating their average as the ground truth, and then comparing this ground truth with estimates obtained from varying numbers of simulations (from 1 up to V=10). Could the authors clarify or consider revising their RMSE analysis accordingly?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nMentioned in the summary. \n\nWeakness:\n- Using random selection as the baseline for branching is weak, as obviously certain positions should not be explored from.\n\n- There is no direct comparison with the MCTS value baseline. Theoretically, MCTS values themselves inherently capture uncertainty effectively.\n\n- The authors only consider uncertainty in terms of value estimation but neglect uncertainty related to policy decisions. For instance, methods such as those described in the \"Learning to Stop\" paper might be more appropriate, especially since agents can directly simulate outcomes. Furthermore, many states, such as the initial state, can remain persistently uncertain in value, regardless of the number of simulations performed.\n\n- The authors do not explore alternative uncertainty estimation methods sufficiently. For example, if MCTS value remains stable throughout the search of a state, it may indicate inherent certainty in the uncertainty itself rather than genuine uncertainty about the position. Conversely, fluctuating values might signify genuine uncertainty and an area needing further training.\n\n- The chosen threshold (lcr_0=0.48) appears arbitrary. A more principled approach, such as selecting the top 10% most uncertain positions, might yield better performance. Additionally, the optimal number of variations (V=10) was determined empirically without providing deeper insights or theoretical justifications for why this specific number is particularly effective.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We have conducted additional experiments for the rebuttal, and we will include them in the final revision, as this year's rebuttal phase doesn't allow authors to upload a PDF or any images. We address each comment as follows:\n\n> Using random selection as the baseline for branching is weak, as obviously certain positions should not be explored from.\n\nOur method is designed to achieve two complementary goals: (1) reducing variance through value ensembling from multiple games, and (2) exploring overlooked but potentially promising decisions. The random branching baseline highlights the limitations of relying solely on (1) and demonstrates the importance of branching position selection in our proposed strategy.\n\n> There is no direct comparison with the MCTS value baseline. Theoretically, MCTS values themselves inherently capture uncertainty effectively.\n\nWe agree that MCTS value inherently captures uncertainty. Typically, there are two ways to model this uncertainty: the frequentist and the Bayesian perspectives. Our method adopts a Bayesian interpretation, where the MCTS value is assumed to be a random variable, rather than a fixed estimate. This choice does not imply that the Bayesian approach is universally better for modeling uncertainty in MCTS values; instead, it reflects the specific interests of our setting. In particular, our proposed branching method typically only has a small number of variations (V), placing us in a low-sample regime. As a result, Bayesian methods can offer more sample efficiency than frequentist ones by incorporating the assumed prior distribution and explicitly modeling uncertainty, as analyzed in Section 4.1 for the Bernoulli distribution. We thank the reviewer for raising this point, and we will include a discussion in the revision.\n\n> The authors only consider uncertainty in terms of value estimation but neglect uncertainty related to policy decisions. For instance, methods such as those described in the \"Learning to Stop\" paper might be more appropriate, especially since agents can directly simulate outcomes. Furthermore, many states, such as the initial state, can remain persistently uncertain in value, regardless of the number of simulations performed.\n\nOur method focuses on identifying high-uncertainty positions that can alter the game result, as value labels exhibit high variance in the original AlphaZero self-play process. In particular, for positions with low value uncertainty but high policy uncertainty, even though there is significant variability in the move to play (high policy uncertainty), the game result is also highly determined (low value uncertainty). In general, in addition to exploring the uncertainty position, our work also aims to reduce the value label variance. Exploring positions with low value uncertainty but with high policy uncertainty is left as future work.\n\n> The authors do not explore alternative uncertainty estimation methods sufficiently. For example, if MCTS value remains stable throughout the search of a state, it may indicate inherent certainty in the uncertainty itself rather than genuine uncertainty about the position. Conversely, fluctuating values might signify genuine uncertainty and an area needing further training.\n\nIn addition to the previous discussion, our work focuses on analyzing the proposed LCR metric, and we include a discussion of alternative uncertainty estimation in Appendix A.2.4. We appreciate the reviewer's perspective, and future studies on incorporating uncertainty during search can complement our work.\n\n> The chosen threshold (lcr_0=0.48) appears arbitrary. A more principled approach, such as selecting the top 10% most uncertain positions, might yield better performance.\n\nThe choice of LCR_0 is based on the initial value (0.6) for an empty position. The threshold serves as an interpretable hyperparameter and can be adjusted accordingly with different value thresholds. On the other hand, we adopt a fixed threshold to ensure that branching occurs only at positions with sufficiently high variability. This is particularly important in cases where none of the positions in a game are suitable for branching due to the exploration noise introduced in the self-play. For instance, as discussed in the visualization in Appendix A.1, some games have few to no branching points (shown in entirely blue lines) due to exploring a clearly losing position. In such cases, enforcing a fixed-percentage strategy could lead to branching at low-variability positions, potentially reducing the overall quality of exploration. Conversely, there are games where more than 30% of the positions exhibit high LCR. Overall, we find that using a fixed threshold offers a flexible way to ensure efficient exploration across diverse game scenarios.\n\n> Additionally, the optimal number of variations (V=10) was determined empirically without providing deeper insights or theoretical justifications for why this specific number is particularly effective.\n\nThe variation V is a hyperparameter of our algorithm, and we connect the study of variation V to the LCR per move metric, as discussed in Section 5.3. Our observations show that increasing V allows for a broader exploration of uncertainty at the selected positions and leads to improved performance. However, the benefit of increasing V begins to saturate beyond a certain point, indicating diminishing returns. Our study provides an empirical insight into the hyperparameter, and we consider a more analytical study for future work.\n\n**Q**: Distribution of LCR-Uncertain States: Could the authors provide an analysis of how the LCR-uncertain states are distributed across different game stages (e.g., early, mid, late game)? Understanding this distribution could offer insights into which game phases most benefit from the proposed branching strategy.\n\n**A**: We will include a figure showing the LCR distribution across different game stages in the final revision. To summarize the figure, the data distribution shows a higher density of uncertain positions in the early stages of the game. Since our branching strategy aims to capture the turning point in the later game phase, the figure shows the sample distribution peak around move 110. We appreciate the reviewer's suggestion, as it helped us better illustrate how our proposed LCR metric quantifies uncertainty across various phases of the game.\n\n**Q**: Impact of MCTS Simulation Counts on LCR Accuracy: It would be valuable to investigate how the accuracy of the LCR metric varies with different MCTS simulation counts. Considering recent methods frequently utilize fewer simulations (e.g., 100-200), compared to traditional settings (e.g., 800), evaluating LCR across varying simulation counts could validate its robustness and practical applicability.\n\n**A**: We'll include three figures similar to Figure 5 in Section 5.2 showing the impact of fewer MCTS simulation counts. To summarize the figure, both empirical results and analytical estimators for 100, 200, and 400 simulations exhibit a similar trend to that observed with 800 simulations (as shown in Figure 5 of Section 5.2). Moreover, our LCR estimator remains close to the empirical results across these settings. In general, these observations suggest that our estimator is robust with various simulation counts. We also include their RMSE in the next response.\n\n**Q**: Clarification on RMSE Analysis Methodology: The current RMSE evaluation approach is not entirely clear. A suitable method might involve first obtaining multiple simulation results (like geting n=1000 z values) for each of the 20,000 positions, calculating their average as the ground truth, and then comparing this ground truth with estimates obtained from varying numbers of simulations (from 1 up to V=10). Could the authors clarify or consider revising their RMSE analysis accordingly?\n\n**A**: In Figure 5, the RMSE was computed by comparing the empirical mean (blue line) with the estimated mean LCR (orange line). The blue line represents the average of observed label changes across all positions at each move, while the orange line is the average of individual LCR estimates at the same moves. On the other hand, in response to the feedback, we will also include another RMSE result based on per-position comparisons. Specifically, we simulate a larger number of game results from the same position to obtain an empirical change rate, and then compare this to the estimated LCR. We'll provide additional graphs in the revision.\n\nThe following table summarizes the RMSE values computed using both approaches with various simulation counts: (1) the \"mean comparison\" method used in the paper, where * indicates the value reported in the paper, and (2) a new \"per-position comparison\" result, where we simulate 10 game results per position and compute RMSE relative to the estimated LCR. The RMSE for the per-position comparison is higher, as each position requires more simulations for accurate estimation. While we use 10 simulations per position due to available compute resources, the results still suggest a close match between the empirical estimates and our proposed analytical estimator.\n\n| Simulations | RMSE (Mean comparison) | RMSE (Per-Position comparison) |\n|---|---|---|\n| 100 | 0.05 | 0.12 |\n| 200 | 0.04 | 0.11 |\n| 400 | 0.03 | 0.18 |\n| 800 | 0.02* | 0.14 |"}, {"review_id": "eGZKYtHm9o", "reviewer": "Reviewer_DkvB", "summary": "The authors propose an uncertainty-guided MCTS exploration framework that improves upon standard AlphaZero. It branches out from high-uncertainty positions and explores multiple variations. This reduces the variance of the value label by ensembling multiple game outcomes. It also explores critical decision points that may yield improvements. This results in greater training efficiency.", "questions": "Generalization to the non-Bernoulli case: In the Discussion section, you allude to the possibility of using quantiles. Is there any obstruction to obtaining a similar closed form for common distributions, like Gaussian or Beta distributions?\n\nIs it possible to add uncertainty bands / error bars to some figures (such as Figures 6b, 7b, 8a, and 8b)? I assume that these can be obtained by running multiple trials and using a metric such as standard error, or a confidence interval.\n\nCan this approach be extended to n-player games, as in Multiplayer AlphaZero?", "limitations": "Yes (page 9)", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The experimental results look promising. I suggest adding error bars to some of the Figures (such as 6b, 7b, 8a, and 8b). These can be obtained by running multiple trials. Overall, the idea of uncertainty-guided exploration during MCTS makes a lot of sense.\n\nPage-by-page comments and suggestions:\n\nPage 1:\n\n\"It learns through self-play\" No need for italics and boldface here.\n\n\"alternative fashion\" → \"alternating fashion\"\n\n\"the strength\" → \"the agent's playing strength\"\n\nPage 2:\n\n\"change decisions after the tree search\" Unclear what this means. Change from the policy head's prediction? If so, state so.\n\n\"during self-play while\" Add comma before while.\n\nReduce the indentation of the contribution list.\n\n\"our analysis on Bernoulli distribution\" → \"our analysis of/on the Bernoulli distribution\"\n\n\"in an analytical form\" → \"in an analytical way\" / \"via an analytical form\" ?\n\nPage 3:\n\n\"policy and value to obtain the search result, typically requiring hundreds to thousands\nof neural network predictions to obtain a search result.\" Repetition of \"to obtain a/the search result\".\n\n\"red arrow in the figure\" → \"red arrow in Figure 2\"\n\nPage 4:\n\n\"In this section, we... in Section 4.1\" Redundant to say \"in section X\" twice.\n\n\"denoted by θ = LCR(s)\" Put LCR in upright font for consistency.\n\nLines 141-143 are a run-on sentence. Split into at least two sentences.\n\nPage 5:\n\nAlgorithm 1: \"has been played\" should not be italicized.\n\nAlgorithm 1: \"play_episode_from\" consider using normal text and font (as opposed to monospace with underscores) for consistency with the rest of the presentation of the algorithm.\n\n\"and thus can reduce the label variance\" doesn't grammatically fit with the rest of the sentence. Consider making it a new sentence: \"This reduces the label variance\".\n\nPage 6:\n\n\"where LCR0 represents\" Put LCR in upright font for consistency.\n\n\"so that we can discard positions whose win rates fluctuate around the initial win rate\" Unclear what this means. What precisely do you mean by \"fluctuate around\"? Consider rephrasing or elaborating.\n\n\"positions are weighted by their time step because we want to capture the turning point in the later game phase\" Unclear what \"capture the turning point\" means here. Consider clarifying.\n\n\"when G number of states are collected, and this hyperparameter is the same as...\" → \"when G states are collected, where G is the same hyperparameter as...\"\n\n\"In this section, ... in Section 5.1\" Redundant.\n\n\"Each training\" → \"Each training run\"\n\nPage 7:\n\n\"analytical estimators with\" Add comma before \"with\".\n\nPage 8:\n\n\"similar to our method\" → \"similarly to our method\"\n\nPage 9:\n\n\"our method achieves equivalent strength\" Equivalent to what? Standard AlphaZero? Clarify.\n\n\"allow the return to a specific state\" → \"allows the algorithm to return to a specific state\", if that's what you meant.", "was_revised": true, "final_justification": "My questions and requests for clarification have been answered satisfactorily by the authors. I believe the paper merits acceptance.", "rebuttal": "We thank the reviewer for the feedback. We have conducted additional experiments for the rebuttal, and we will include them in the final revision, as this year's rebuttal phase doesn't allow authors to upload a PDF or any images. We address each comment as follows:\n\n**Q**: Generalization to the non-Bernoulli case: In the Discussion section, you allude to the possibility of using quantiles. Is there any obstruction to obtaining a similar closed form for common distributions, like Gaussian or Beta distributions?\n\n**A**: The generalization to the non-Bernoulli case typically does not yield a closed form when computing Pr(|X-Y| > t), as the sum (or difference) of two independent random variables is the convolution of their distributions. However, in practice, the integration can be estimated using numerical techniques.\n\n**Q**: Is it possible to add uncertainty bands / error bars to some figures (such as Figures 6b, 7b, 8a, and 8b)? I assume that these can be obtained by running multiple trials and using a metric such as standard error, or a confidence interval.\n\n**A**: We'll include the standard deviation and confidence interval in the revision. The standard deviation for Figure 6 (b) and Figure 7(b) is about 1.0% and Figure 8 is about 2.1%.\n\n**Q**: Can this approach be extended to n-player games, as in Multiplayer AlphaZero?\n\n**A**: We believe our approach can be extended to n-player settings. Since our method leverages the MCTS value and LCR estimation to quantify uncertainty, it is, in general, compatible with Multiplayer AlphaZero and similar variants.\n\n> Page-by-page comments and suggestions:\n\nWe will incorporate the comments and suggestions into the final revision. We provide clarifications as follows:\n\n> Page 2:\n> \"change decisions after the tree search\"\n\nThis refers to the difference between the best action decided by the NN policy and the one selected after performing MCTS. This concept is further discussed in Section 2.2.\n\n> Page 6:\n> \"fluctuate around\"\n\nThis describes situations where win rate values remain close to the initial value across time steps. For example: …, 0.6, 0.62, 0.58, 0.59, … indicates fluctuation around 0.6.\n\n> \"capture the turning point\"\n\nThis refers to identifying positions where a significant change in win rate occurs, such as a sudden drop from 0.59 to 0.1, which might reflect a critical mistake or forced move. The LCR can be used to detect such turning points.\n\n> Page 9:\n> \"our method achieves equivalent strength\"\n\nThis refers to achieving the same playing strength when comparing ours to the baseline.\n\nWe again thank the reviewer for their feedback to improve the clarity of our work."}]

Author rebuttal:

Meta-review: All reviewers recommend acceptance and praise the clear writing and well designed experiments. I follow their recommendation and also recommend acceptance.

Reviewer gKQg made some valid observations about the type of uncertainty (e.g. from policy decisions, which the authors acknowledged) and asked for additional baselines that the authors promised to include. The authors are reminded to include these discussions and experiments in the final version of the paper. 

Upon reading the paper myself, I noted that the related work section is missing a related branch of literature about planning to explore (listed blow). The objective is not directly comparable to the method presented in this paper, but appear related enough to the core problem to be mentioned.

**Additional references on planning to explore**

Yi Sun, Faustino J. Gomez, and Jurgen Schmidhuber. Planning to be surprised: Optimal Bayesian exploration in dynamic environments. Artificial General Intelligence - 4th International Conference, 2011.

Pranav Shyam, Wojciech Jaskowski, and Faustino Gomez. Model-based active exploration. Proceedings of the 36th International Conference on Machine Learning, 2019.

Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervised world models. Proceedings of the 37th International Conference on Machine Learning, 2020.

Carlos E. Luis, Alessandro G. Bottero, Julia Vinogradska, Felix Berkenkamp, and Jan Peters. Model-based uncertainty in value functions. International Conference on Artificial Intelligence and Statistics, 2023.

Yaniv Oren, Viliam Vadocz, Matthijs T. J. Spaan, and Wendelin Bohmer. Epistemic Monte Carlo Tree Search. International Conference on Learning Representations, 2025.
Decision: Accept (poster)