cs.LGFeb 24, 2026

Regret-Guided Search Control for Efficient Learning in AlphaZero

Authors: Yun-Jui Tsai, Wei-Yu Chen, Yan-Ru Ju, Yu-Hung Chang, Ti-Rong Wu

Organizations: Department of Computer Science, National Yang Ming Chiao Tung University, Taiwan · Institute of Information Science, Academia Sinica, Taiwan · College of Computing, Georgia Institute of Technology

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Reinforcement learning (RL) agents achieve remarkable performance but remain far less learning-efficient than humans. While RL agents require extensive self-play games to extract useful signals, humans often need only a few games, improving rapidly by repeatedly revisiting states where mistakes occurred. This idea, known as search control, aims to restart from valuable states rather than always from the initial state. In AlphaZero, prior work Go-Exploit applies this idea by sampling past states from self-play or search trees, but it treats all states equally, regardless of their learning potential. We propose Regret-Guided Search Control (RGSC), which extends AlphaZero with a regret network that learns to identify high-regret states, where the agent's evaluation diverges most from the actual outcome. These states are collected from both self-play trajectories and MCTS nodes, stored in a prioritized regret buffer, and reused as new starting positions. Across 9x9 Go, 10x10 Othello, and 11x11 Hex, RGSC outperforms AlphaZero and Go-Exploit by an average of 77 and 89 Elo, respectively. When training on a well-trained 9x9 Go model, RGSC further improves the win rate against KataGo from 69.3% to 78.2%, while both baselines show no improvement. These results demonstrate that RGSC provides an effective mechanism for search control, improving both efficiency and robustness of AlphaZero training. Our code is available at https://rlg.iis.sinica.edu.tw/papers/rgsc.

Figures & tables

Figure 1: Humans focus on correcting mistakes, whereas RL always starts from the initial state.
Figure 2: Overview of RGSC. The regret network selects high-regret states (red circles) from both self-play ( A ) or MTCS search node ( B ), which serve as restart points for further self-play. The newly generated trajectories can further branch out, e.g., state D originates from a restart at state C .
Figure 3: A toy example on nn -level binary tree. (a) and (c) show the average rewards during the training, while (b) and (d) show the mean squared error (MSE) of the optimal Q-values during the training. The shaded area is a 95% confidence interval for the mean.
Figure 4: Playing performance of AlphaZero, Go-Exploit, and RGSC on three different board games. The shaded area is a 95% confidence interval for the mean.
 AlphaZeroGo-ExploitRGSC
9x9 Go45.5% ±\pm 1.5%49.5% ±\pm 2.0%53.6% ±\pm 2.4%
10x10 Othello51.7% ±\pm 2.5%52.9% ±\pm 3.3%57.8% ±\pm 3.2%
11x11 Hex83.6% ±\pm 1.6%89.2% ±\pm 1.8%91.1% ±\pm 2.0%
Table 1: Win rate against established open-source programs on three board games.
Figure 5: Playing performance of AlphaZero, Go-Exploit, and RGSC when continued from well-trained models. The shaded area is a 95% confidence interval for the mean.
Figure 6: Playing performance of RGSC using regret value network and regret ranking network. The shaded area is a 95% confidence interval for the mean.
Figure 7: The regret values for nodes selected by Go-Exploit, regret value and ranking network. The shaded area is a 95% confidence interval for the mean.
Figure 8: Regret distributions of states in the prioritized regret buffer at entry and before removal.
Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

 from scratchfrom well-trained
ParameterGoHexOthelloGo
Board size911109
OptimizerSGDSGDSGDSGD
Optimizer: learning rate0.020.020.020.001
Optimizer: momentum0.90.90.90.9
Optimizer: weight decay0.00010.00010.00010.0001
Appendix
Table 2: Hyperparameters for training from scratch ( subsection 4.2 ) and from well-trained model ( subsection 4.3 ).
# blocks36912151820
RGSC139.5%109.1%105.4%103.5%102.7%101.8%101.9%
AlphaZero100.0%100.0%100.0%100.0%100.0%100.0%100.0%
Appendix
Table 3: Forwarding time across different blocks of the network.
IDVersion# blocksElo ratings
1kata1-b6c96-s152505856-d2315263669833.3 ±\pm 16.1
2kata1-b6c96-s165180416-d2513043469900.6 ±\pm 16.2
3kata1-b6c96-s175395328-d2678873269958.6 ±\pm 16.9
4kata1-b10c128-s41138688-d273968551010138.6 ±\pm 18.3
5kata1-b15c192-s86740736-d722598361511180.1 ±\pm 16.1
Appendix
Table 4: The versions of the selected KataGo models for 9x9 Go.
Figure 9: Playing performance of different sampling probabilities ( λ\lambda ) across three games. The orange curve is the final RGSC setting.
Figure 10: Playing performance of different buffer sampling temperatures ( τ\tau ) across three games. The orange curve is the final RGSC setting.
Figure 11: Playing performance of different buffer sizes ( κ\kappa ) across three games. The orange curve is the final RGSC setting.
Figure 12: Playing performance of different EMA coefficients ( α\alpha ) across three games. The orange curve is the final RGSC setting.
Figure 13: High-regret state examples. Blue triangles indicate the last moves.
Figure 14: Win rates of high-regret states during RGSC training.
Figure 15: Relationship between game outcomes and regrets during training.
Figure 16: Change in the proportion of openings with different lengths across training in 9×9 Go.
Figure 17: Change in the proportion of openings with different lengths across training in 10×10 Othello.
Figure 18: Change in the proportion of openings with different lengths across training in 11×11 Hex.
Figure 19: Changes in the values of openings from their first appearance to the final update during training.
Figure 20: Playing performance of MuZero, and RGSC on Ms. Pac-Man. The shaded area is a 95% confidence interval for the mean.
More in this topic

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,704 papers

Explore similar work

CardsList

  1. AlphaZero in Sparsely Rewarded Games: Limits and Auxiliary Supervision

    Jul 9, 2026Brent Kong, Tejas Ram, Tony Yue YuGame-Playing AgentsSelf-Play RL

    Department of Mathematics · California Institute of Technology · Department of Computer Science

  2. Belief-Guided Decision Making with Uncertainty Gating in the Game of Go

    Jul 29, 2026Mehrad Yaghoubi, Azam Bastanfard, Abbas Jalilvand +1Game-Playing AgentsDecision-Making under Uncertainty

    Department of Computer Engineering, Ka.C, Islamic Azad University, Karaj, Iran

  3. MAPLE: Multi-State Aggregated Policy Evaluation for AlphaZero in Imperfect-Information Games

    May 22, 2026Qian-Rong Li, Hung Guei, I-Chen Wu +1Game-Playing AgentsImperfect-Information Games

    Department of Computer Science, National Yang Ming Chiao Tung University, Taiwan · Institute of Information Science, Academia Sinica, Taiwan