acceptodds
Under review as a conference paper at ICLR 2027

The Surprising Effectiveness of Approximate Value Iteration in Self-Play

Abstract

Combining search with function approximation has driven major advances in game-playing programs, making self-play algorithms more competitive than ever. Still, the computational overhead of the most popular methods, based on Monte Carlo Tree Search (MCTS), can be substantial. In this work, we investigate whether simpler methods remain competitive in non-trivial, moderately sized games such as Connect Four, Hex(7x7) and synthetic games. We train a minimal self-play implementation of Approximate Value Iteration (AVI) and use ground-truth oracles for exact evaluation. Contrary to expectations, our results demonstrate the surprising effectiveness of AVI: it learns more accurate value functions than those learned by AlphaZero, while its one-step-lookahead greedy policies remain competitive with MCTS-based policies at substantially lower training and inference costs. Preliminary experiments on Othello and Go(9x9) show that AVI trains stably on larger games and learns effective value functions. These findings suggest that the success of MCTS-based methods may have eclipsed simpler approaches that have become increasingly practical with modern deep-learning tools.

Primary area:
reinforcement learning
Keywords:
game, tree search, reinforcement learning, alphazero, minimax, value iteration, deep reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_gvP9OpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

Value Iteration is one of the basic exact methods of tabular reinforcemnet learning. This paper assess the effectiveness of approximate VI. It does so by comparing against MCTS/AlphaZero based self-play methods, using medium complexity games (for quick experimentation) Connect 4 and Hex 7x7, as well as synthetic games. Surprisingly, AVI is much more effective than the state of the art AlphaZero MCTS based approaches. On larger games, Go 9x9, it remains competitive.

Critical strengths
  • interesting to see how Approximate VI performs so well against AlphaZero-like approaches.
  • provides insight: In section 6, the paper answers the biggest question as to why AVI may perform so well: " In MDPs, maximizing over noisy value estimates can introduce a systematic overestimation bias (Hasselt, 2010). In a negamax backup, however, successor values are instead expressed from the opponent’s perspective and enter with the opposite sign, so an overestimate for one player becomes an underestimate one ply earlier. Approximation errors may therefore alternate in sign rather than accumulate in the same direction. This bias-cancellation argument remains a hypothesis, but it suggests that error propagation in alternating games may behave better than in the usual MDP setting." This is an important and highly useful hypothesis, that makes the paper transcend the: "just another unexpected result" category.
  • Limitations, the need for Oracle-type games, are clearly expressed.
  • All reproducibility data (code, hyperparameters are available). Five random seeds; 95% confidence.
Critical weaknesses
  • Small network: Appendix C: four resblocks, 2 MLP layers. 256 hidden units.
  • as per the limitations: how does it perform on larger games?
  • no full ablation of MCTS/AZ. Silver et al show in their 2017 Science paper that MCTS-free pure neural network achieves reasonable play, around half the Elo score on AlphaZero. So the fact that pure neural network evaluation plays decent is not new. MCTS planning is just needed for even better play, but comes at a computational cost. No full ablation of deep learning with different amounts of planning/MCTS. This is more a future work item than a critical weakness. The authors show an interesting and unexpected result, which requires follow up work.
Questions for authors

I do not fully understand the last sentence of the Abstract, using the world eclipsed. Do you mean that MCTS/AZ is better than simpler approaches? The rest of the paper seems to suggest that simpler approaches, such as AVI, have become stronger (= eclipse emans overshadow) than MCTS/AZ. Maybe rewrite. or add the word been eclipsed by. This is an interesting and surprising result, that deserves deeper exploration. Why does it work?

Silver et al show in their 2017 Science paper that MCTS-free pure neural network achieves reasonable play, around half the Elo score on AlphaZero. So the fact that pure neural network evaluation plays decent is not new. MCTS planning is just needed for even better play, but comes at a computational cost.

The use of AI tools is described in detail, in a convincing way. The paper even contains typo's: Additionally. We have reviewed all...

Learning without search can perform surprisingly well. Reason why are explained, limitations are clearly described, reproducibility is done well, results are surprising and open new direction for entire field of combinatorial games. Accept.

2 comments

We warmly thank the reviewer for their positive assessment and thoughtful comments. We are particularly pleased that the discussion of possible bias cancellation in negamax backups was found useful. We agree that understanding this phenomenon more deeply would be an interesting direction for future research.

as per the limitations: how does it perform on larger games?

We have not yet experimented with games larger than Go(9x9), and we agree that understanding how AVI scales is an important open question.

As discussed in Section 6, one potential limitation is that AVI evaluates every legal successors, effectively distributing its computation uniformly across actions rather than focusing on more promising, deeper branches. This becomes increasingly expensive as the branching factor increases, and may explain why its one-step greedy policy is less competitive on larger games.

Nevertheless, our experiments on Othello and Go(9x9) are encouraging: AVI trains stably, and the learned values improve MiniZero's playing strength when substituted into its MCTS procedure. This suggests that even when one-step greedy inference becomes insufficient, AVI may remain an effective way to learn value functions that can subsequently guide more sophisticated search.

We believe that improving the allocation of computation across actions, for instance through action sampling or a learned policy prior, is a promising direction for scaling AVI further: we see AVI as a good building block for more advanced algorithms.

no full ablation of MCTS/AZ. Silver et al show in their 2017 Science paper that MCTS-free pure neural network achieves reasonable play, around half the Elo score on AlphaZero. So the fact that pure neural network evaluation plays decent is not new. MCTS planning is just needed for even better play, but comes at a computational cost.

If we are not mistaken we think you refer to Figure 6b of the 2017 Science paper where the performance of the "Raw Network" is compared to that of variants of AlphaGo/AlphaZero. This "Raw Network" corresponds to what we call policy-only inference in our paper. Importantly, it is the policy network obtained through standard AlphaGo Zero training, which relies on MCTS to generate improved policy targets. The distinction is only at inference time, where the raw network directly selects actions without further search. In our paper, we also evaluate such a policy-only baseline, notably in the new head-to-head figure (Figure 2) or cross-inference experiments (Figure 3).

However, our main question is different: is MCTS necessary during training to learn effective value functions? This is where most of the computational cost of AlphaZero is payed. Our results suggest that a simple AVI algorithm can learn highly effective values without search-based policy improvement during training. We fully agree that MCTS can remain extremely useful at inference time, particularly in larger games, as our cross-inference experiments illustrate.

Small network: Appendix C: four resblocks, 2 MLP layers. 256 hidden units.

We agree that investigating larger architectures would be valuable. Our goal in the main experiments was to compare the two learning procedures under the exact same network capacity, optimization settings, and training-data budget. The additional Othello and Go(9x9) experiments use larger convolutional-based architectures matched to MiniZero and provide preliminary evidence that the observations extend beyond our smaller benchmarks. Nevertheless, we agree with you that a more systematic study of network capacity would be a natural continuation of this work.

I do not fully understand the last sentence of the Abstract, using the world eclipsed. Do you mean that MCTS/AZ is better than simpler approaches? The rest of the paper seems to suggest that simpler approaches, such as AVI, have become stronger (= eclipse emans overshadow) than MCTS/AZ. Maybe rewrite. or add the word been eclipsed by.

What we intended to convey is that the remarkable success of AlphaZero and related MCTS-based algorithms may have drawn attention away from simpler approaches to value learning, such as AVI. We updated the sentence in the abstract with the hope it makes it clearer.

Reviewer_gvP9OpenReview ↗

Thank you

Thank you for these insights. Nothing surprising, but your replies are useful and insightful, please use them in your revised version, if the paper gets accepted. Your replies strengthen my conviction that this is a worthwhile result, that deserves acceptance at this highly competitive venue, so my positive score remains.

Reviewer_aHw7OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper compares a minimal self-play Approximate Value Iteration (AVI) agent with an AlphaZero baseline. The AVI agent learns to predict state values with epsilon-greedy self-play, one-step negamax targets, and a replay buffer. It uses the same environments, neural backbone, optimizer, and amount of training data as the AlphaZero baseline.

Instead of only measuring playing strength, the authors use games for which optimal game-theoretic values and optimal actions are known, and can therefore measure value error (MAE), one-step regret, and error rate when playing against a perfect solver. AVI reaches lower value error, and its greedy one-step policy is close to AlphaZero's strength on Connect Four and better on Hex, while being much cheaper during training and inference. In the larger games Othello and Go (9x9), AVI's greedy one-step policy loses against MiniZero at 200 MCTS simulations; but replacing MiniZero's value head with AVI's values inside MCTS improves on vanilla MiniZero.

Critical strengths
  • The evaluation on solved games is much more in-depth than the usual playing strength evaluation against a fixed set of opponents. It is also good that the authors controlled for several factors by keeping the implementation, backbone, and amount of data fixed.
  • It is impressive that in Hex, the AVI agent costs about as much as AlphaZero at 32 MCTS simulations, and is clearly better in every metric (Figure 1). In Connect 4, the AVI agent is at least comparable to AlphaZero at 512 simulations, while only costing 1/28 as much for training and 1/73 as much during inference.
Critical weaknesses
  • The main claim of the paper is that AVI learns more accurate value functions. This comparison is muddled for two reasons: 1) AlphaZero's value estimate uses as training target the outcome of games that are played with Dirichlet noise, i.e. with an exploratory policy. AVI, on the other hand, uses backups whose fixed point is the optimal value function. Therefore it's expected that AVI estimates more accurate values (also see https://dl.acm.org/doi/abs/10.1007/s00521-021-05928-5 on other AlphaZero value targets). 2) The authors compute MAE and regret on uniformly sampled states (and epsilon-optimally sampled states in Connect-4). This is not quite fair towards AlphaZero as AlphaZero's value head is trained on a very different state distribution, and its policy head also helps it stay close to that distribution (where its value estimates are more accurate) during play. Therefore, the main claim can't be taken to mean "AVI works better than search".
  • The paper also claims that AVI's success is "contrary to expectations". There is some related work here; for example, Young, K., Vasan, G., and Hayward, R. (2016): "NeuroHex: A Deep Q-learning Hex Agent" train a Hex agent with deep Q-learning and self-play, without search, and with a very similar negamax one-step backup. This is probably the closest related work, but not mentioned here. There are some differences to AVI, but this shows that the contribution of this paper is more empirical than algorithmic.
  • The result for Connect 4 shown in Table 2 is that greedy AVI is significantly weaker - maybe not by much, but the phrase "performs similarly or better" in the text is not quite correct.
  • AVI is stronger than AZ in Hex according to Table 2, but according to Table 1, AlphaZero barely improves in Hex after the first 100K steps or so. There could be an issue with this baseline.
Questions for authors
  • In Figure 1, is AlphaZero using the same number of simulations during gameplay against the oracle as it used during training? Is the policy regret computed from the policy head or from the visit distribution at the root after search?
  • Was gamma = 1 in your experiments? Both for AVI and for AlphaZero training?
  • Do you have evidence that the Hex AZ baseline was reasonably tuned, e.g. results against other agents? Do you have any idea why there seems to be no improvement with 32 simulations?
4 comments

We thank the reviewer for their careful reading, constructive comments, and positive assessment of our work.

The main claim of the paper is that AVI learns more accurate value functions. This comparison is muddled for two reasons: 1) AlphaZero's value estimate uses as training target the outcome of games that are played with Dirichlet noise, i.e. with an exploratory policy. AVI, on the other hand, uses backups whose fixed point is the optimal value function. Therefore it's expected that AVI estimates more accurate values (also see https://dl.acm.org/doi/abs/10.1007/s00521-021-05928-5 on other AlphaZero value targets).

Technically, AlphaZero's exploration policy, the one that is used to generate the self-play episodes, which define the value targets, does not use directly Dirichlet noise. Dirichlet noise is used indirectly as an exploration device within the local tree search, the outside policy is defined as a temperature-scaled distribution over the visits counts of that local search. Whether this policy is an improved policy compared to the static policy network is somewhat the promise of PUCT, and is guaranteed for a large enough number of MCTS simulations. AlphaZero is often viewed as an implementation of Policy Iteration, in this regard, as the policy tends to an optimal policy, the value should tend to an optimal value as well. Thus, we do not believe there is an intrinsic misalignment in what the value networks try to approximate in AlphaZero and AVI: both should converge to the same thing.

2) The authors compute MAE and regret on uniformly sampled states (and epsilon-optimally sampled states in Connect-4). This is not quite fair towards AlphaZero as AlphaZero's value head is trained on a very different state distribution, and its policy head also helps it stay close to that distribution (where its value estimates are more accurate) during play. Therefore, the main claim can't be taken to mean "AVI works better than search".

We agree that the state distribution matters when interpreting value-function accuracy. Our motivation for evaluating on fixed dataset of states (random uniform or espilon-optimal) is precisely to assess the accuracy and generalization of the learned value functions beyond the states encountered during the self-play collection of a specific algorithm. We believe this is a meaningful property to study, particularly for value functions intended to support planning.

Importantly, our conclusions do not rely exclusively on these evaluations. We also measure playing strength against perfect oracles, starting from common openings, which evaluates the actual policies of both algorithms, including AlphaZero's policy-guided MCTS. Furthermore, our cross-inference experiments evaluate the learned values within the same MCTS procedure, keeping AlphaZero's policy prior fixed. Even with the corrected AlphaZero baseline, replacing its value function with AVI's generally improves the resulting search performance, although the improvements are now smaller.

We agree that these results should not be interpreted as showing that AVI is universally better than search, and this is not our intended claim. Rather, our main finding is that expensive tree search is not necessarily required during training to learn effective value functions. AVI provides a particularly simple and computationally inexpensive alternative that achieves surprisingly competitive performance (at least on the games we tested), while its learned values can also benefit from more sophisticated search procedures at inference time.

The paper also claims that AVI's success is "contrary to expectations". There is some related work here; for example, Young, K., Vasan, G., and Hayward, R. (2016): "NeuroHex: A Deep Q-learning Hex Agent" train a Hex agent with deep Q-learning and self-play, without search, and with a very similar negamax one-step backup. This is probably the closest related work, but not mentioned here. There are some differences to AVI, but this shows that the contribution of this paper is more empirical than algorithmic.

We thank the reviewer for pointing us to NeuroHex (Young et al., 2016). This is indeed a highly relevant reference that we had overlooked. A few differences are the use of supervised-learning for network initialization, the use of q-learning instead of approximate value iteration and the extent of the empirical evaluation. We have added it and discussed it in the related work section.

We agree that our contribution is primarily empirical rather than algorithmic. Our objective is not to introduce a fundamentally new value iteration algorithm, but to investigate the effectiveness of a minimal AVI self-play procedure using modern deep-learning tools.

AVI is stronger than AZ in Hex according to Table 2, but according to Table 1, AlphaZero barely improves in Hex after the first 100K steps or so. There could be an issue with this baseline.

You were right to question the performance of the AlphaZero baseline. As discussed in our response to reviewer Kg6R, we discovered an unintended implementation error in the AlphaZero loss: the policy cross-entropy term was averaged over actions instead of summed, effectively reducing its weight relative to the value loss.

We corrected this error and retrained all AlphaZero configurations. The corrected results show that the bug did negatively affect AlphaZero's performance, including on Hex. AlphaZero now achieves better results across the tested simulation budgets, and its strongest configuration (512 simulations) has become much closer with AVI.

The result for Connect 4 shown in Table 2 is that greedy AVI is significantly weaker - maybe not by much, but the phrase "performs similarly or better" in the text is not quite correct.

We agree that our previous wording was insufficiently precise. The original results already showed a modest but statistically meaningful disadvantage for AVI in direct matches against AlphaZero on Connect Four.

Following the correction of the AlphaZero implementation discussed above, we replaced the table with Figure 2, which compares greedy AVI against AlphaZero across training and inference budgets. On Connect Four, the stronger AlphaZero agents achieve positive scores against AVI as their inference budget increases. On Hex(7x7), AVI retains a positive score against all tested configurations, although the strongest AlphaZero agent is much closer. Overall, this supports the conclusion that AVI is competitive up to the extent of how much more training/inference budget we allocate to AlphaZero.

In Figure 1, is AlphaZero using the same number of simulations during gameplay against the oracle as it used during training? Is the policy regret computed from the policy head or from the visit distribution at the root after search?

In our experiments AlphaZero always uses the same number of simulations during training and inference, unless explicit mention, like in the cross-inference experiments. Policy regret also uses the action of the post-search AlphaZero policy.

Was gamma = 1 in your experiments? Both for AVI and for AlphaZero training.

Yes, we always use gamma=1, we added this omitted detail in the paper.

Do you have evidence that the Hex AZ baseline was reasonably tuned, e.g. results against other agents? Do you have any idea why there seems to be no improvement with 32 simulations?

Regarding tuning, we used the same architecture, optimization procedure, and training-data budget for both algorithms, and performed a search over the PUCT exploration constant (c=1,2,3), selecting the best-performing configuration. Nevertheless, we acknowledge that this does not constitute an exhaustive tuning study.

For the 32-simulation configuration specifically, we suspect that the limited search budget relative to Hex's large branching factor may limit policy improvement.

Thank you for the revised draft. The corrected figures confirm AVI's lower value error on uniformly sampled states and its advantage with matched compute. Sections 5.1 and 5.2 describe the new results accurately (fixed baseline).

One question: Figure 8 looks like it hasn't changed. Were the F-Games AlphaZero baselines affected by the bug, and were they retrained as well? (The caption also swaps the two rows)

I am keeping my rating at 3 because the corrected results show a smaller advantage for AVI than the original submission, and because the contribution is primarily empirical. I will raise my soundness score to 3 if you can confirm that the F-Games AlphaZero baselines were unaffected by the bug or have been retrained.

Thank you for catching this. Yes, the original F-Games AlphaZero baselines were affected by the same action-averaging issue. We have retrained AlphaZero on all three F-Game structures, with simulation budgets S={32,64,128,256}, using the corrected policy loss. The AVI results are unchanged.

We have replaced Figure 8 with the corrected AlphaZero results and fixed the caption: the top row shows policy regret, and the bottom row shows value error.

The qualitative conclusion on value accuracy does not change much: AVI has lower mean value error across the three structures shown. The policy results are a slightly updated: on the deep and narrow tree, AlphaZero reaches lower mean regret, and on the balanced tree the largest AlphaZero budget also achieves slightly lower mean regret.

Reviewer_Kg6ROpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper revisits a AVI method using one-step negamax backups. It compares AVI with AlphaZero on Connect Four, Hex(7×7), and synthetic games. AVI learns more accurate values and achieves competitive play at lower reported cost. Experiments on Othello and Go(9×9) further show that replacing MiniZero’s value estimates with AVI’s can improve its search-based play.

Critical strengths
  1. The evaluation is a strong. Exact values and policy regret reveal differences that only head-to-head matches would miss. The additional Connect Four evaluation on approximately optimal trajectories also makes the results more convincing than an evaluation restricted to random positions.

  2. The value-substitution experiments are useful. Keeping the policy prior and MCTS simulation budget fixed while replacing the value function shows that AVI’s lower prediction error can translate into stronger play.

Critical weaknesses
  1. The AlphaZero loss in the code does not match Eq. (10). Averaging over actions gives the policy term less weight relative to the value term, which could affect how well the baseline learns. Was this intentional? I would like to see whether the main results still hold with the loss stated in the paper.

  2. It is not clear what drives AVI’s better value estimates. AVI and AlphaZero use different training targets and also learn from different states. Changing one of these at a time would help show how much of the improvement actually comes from the one-step backup.

Questions for authors
  1. Did the AlphaZero experiments use the loss in the released code? If so, do the main results still hold when you use the loss written in Eq. (10)?

  2. Have you tried comparing the two types of value targets on the same training states? Does AVI still have an advantage, or does the difference mainly come from the states each method learns from?

1 comment

The AlphaZero loss in the code does not match Eq. (10). Averaging over actions gives the policy term less weight relative to the value term, which could affect how well the baseline learns. Was this intentional?

Thank you for identifying this issue. This was indeed an unintended implementation error: we intended to implement the standard cross-entropy loss described in the paper, but the code averaged over the action dimension instead of summing, effectively reducing the weight of the policy loss relative to the value loss.

This changes the relative contribution of the two objectives and may therefore affect training. We have corrected the implementation and retrained all our AlphaZero baselines to ensure a fair comparison. Note that the Go9x9 and Othello experiments were not affected, because the networks were independently trained by MiniZero authors.

We sincerely appreciate the reviewer bringing this issue to our attention and allowing us to improve the paper correctness and robustness.

I would like to see whether the main results still hold with the loss stated in the paper.

The bug did harm the performance of AlphaZero, and the previous version of the paper underestimates its strength, but not to an extent where it significantly alters the conclusions of the paper. On Connect Four, the main change is that AVI's one-step greedy policy is now approximately on par with AlphaZero using 128 simulations, rather than 512, in the play-against-oracle metrics. On Hex(7x7), AlphaZero improves across all simulation budgets, with the largest improvement at 512 simulations, where it now achieves results competitive with AVI. Head-to-head results also changed. Figure 2 now shows AVI against all tested AZ training and inference budgets, with the score reported from AZ's perspective. We updated the text in section 5.1 accordingly.

The new cross-inference results also show a narrower difference between using AVI's value and AZ(512)'s value. But using AVI's value still provides at least as good performances, with lower variance. We updated Section 5.2 accordingly.

Importantly, the revised results still support our central finding: a remarkably simple AVI algorithm, combining epsilon-greedy self-play with one-step negamax backups, can learn effective value functions and achieve competitive performance against substantially more computationally expensive MCTS-based approaches. We believe this remains a surprising and valuable result, especially given the simplicity of AVI and its stability despite combining function approximation, bootstrapping, and off-policy learning.

Have you tried comparing the two types of value targets on the same training states? Does AVI still have an advantage, or does the difference mainly come from the states each method learns from?

We thought about it, but we believe that disentangling the respective contributions of the training targets and the data distribution is less straightforward than it might initially appear. An experiment we thought about: what if we setup a standard AlphaZero training, but we also collect AVI-style targets, and we use them to train a standalone, passive value-network with those AVI targets? Then there is a problem: this would break an important feedback mechanism in AVI. If at a given state, the passive AVI value overestimates an action, nothing will drive the self-play data towards this action, so there is no opportunity to improve the estimate and recover a better value. We therefore believe that the targets and the training distributions are intrinsically coupled in these algorithms, and that such an experiment would not fully isolate their respective contributions.

Our main contribution is instead to demonstrate that a particularly simple self-play algorithm, combining epsilon-greedy exploration with one-step negamax backups, can learn highly effective value functions and remain competitive with substantially more computationally expensive AlphaZero baselines.

Comments on the paper

1 comment

Dear reviewers we just uploaded the rebuttal. We know it is close to the end of the discussion period and we apologize for that, but we had to re-run some experiments presented in the paper. We uploaded a revised pdf with main changes highlighted in blue.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.