Approximate Value Iteration for self-play

The Surprising Effectiveness of Approximate Value Iteration in Self-Play

Raphaël Boige, Amine Boumaza, and Bruno Scherrer

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

How much search does a strong self-play agent really need? We revisit Approximate Value Iteration (AVI), a particularly simple alternative that learns through 1-step negamax updates without using MCTS during training. Across several games, this approach proves more competitive than its simplicity might suggest: where exact evaluation is available, it learns more accurate values than our AlphaZero baseline, while requiring substantially less computation. On larger games, the method remains stable, and its values can also strengthen existing AlphaZero agents when incorporated into their search.

Paper summary

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. We investigate whether simpler methods remain competitive in non-trivial, moderately sized games such as Connect Four, Hex(7×7), 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, AVI learns more accurate value functions than 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(9×9) 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.

The method

Approximate Value Iteration in self-play

Approximate Value Iteration extends Value Iteration to state spaces that cannot be represented exactly. In an alternating two-player game, its update takes the form of a one-step negamax backup.

y(s) = max_a [ R(s, a) − γV(s′) ]

Here, s′ is the state reached after action a. Its value is subtracted because the next state is evaluated from the opponent’s perspective.

Our implementation combines this update with a neural value function, epsilon-greedy self-play, and a replay buffer. It uses neither a policy network nor MCTS during training. At inference time, the learned value function can guide either one-step greedy play or deeper search.

In practical terms, AVI keeps the learning loop deliberately small, making it straightforward to inspect and reproduce. Its empirical stability is nevertheless not guaranteed: the algorithm combines function approximation, bootstrapping, and off-policy learning—the three ingredients commonly known as the “deadly triad” of reinforcement learning.

1
ExploreGenerate positions through epsilon-greedy self-play.
2
Back upCompute one-step negamax value targets and store them in the replay buffer.
3
LearnFit the value network to sampled targets by minimizing squared error.

How it differs from AlphaZero

AVI and AlphaZero share several components, including neural function approximation, self-play, and replay. They differ primarily in how they construct their training targets. AVI applies a one-step maximization over bootstrapped value estimates. This update is comparatively inexpensive when the action space is manageable, but it can propagate approximation errors and introduce instability. AlphaZero instead trains its policy from MCTS visit counts and its value function strictly from final game outcomes. Its value targets avoid bootstrapping and are generally more stable, though they have higher variance. Producing its policy targets may also require hundreds of MCTS simulations per move.

Main result

More accurate values under exact evaluation

Perfect oracles for Connect Four and Hex(7×7) provide ground-truth values and optimal actions. This makes it possible to measure value error, policy regret, and errors against perfect play (which are better metrics than win-rate against an arbitrary baseline).

AVI and AlphaZero compared on value error, policy regret, oracle error rate, and compute budget for Connect Four and Hex — **AVI reaches lower value error across the tested settings.** Its greedy policy is competitive with the stronger AlphaZero configurations while using fewer network evaluations. Lines show means and shaded areas show 95% confidence intervals.

Value quality

Better values provide better search guidance

What if we scale the inference budget of AVI? Can AVI values’ be used to guide deeper search? We place the learned values inside AlphaZero’s MCTS inference to isolate their contribution.

Cross-inference and minimax experiments comparing search guided by AVI values with search guided by AlphaZero values — Holding AlphaZero’s policy and MCTS procedure fixed, replacing its value estimate with AVI’s reduces the error rate in both games. AVI also remains stronger in value-only minimax search.

Larger games

Stable learning on Othello and Go(9×9)

Oracle-available games are limited in size, how does AVI scale to larger games? We train AVI on games without practical exact oracles and compare it with published MiniZero agents. Greedy AVI improves steadily but remains weaker than search-based MiniZero. Interestingly, its learned values nevertheless make MiniZero’s search stronger.

Head-to-head scores against MiniZero during AVI training on Othello and Go 9 by 9 — Solid lines show greedy AVI. Dashed lines use MiniZero’s policy and MCTS with AVI’s value under the same 200-simulation search budget. Scores are measured against native MiniZero.

Pretrained weights

Model Checkpoints

Trained model checkpoints ready for evaluation, cross-inference, and benchmark replication. The weights are provided in JAX (Equinox) format.

Game	Algorithm	Download
Connect Four	AlphaZero (512 sims)	Weights (.zip)
Connect Four	AVI	Weights (.zip)
Hex 7×7	AlphaZero (512 sims)	Weights (.zip)
Hex 7×7	AVI	Weights (.zip)
Othello	AVI	Weights (.zip)
Go 9×9	AVI	Weights (.zip)

Reference

Citation

@misc{boige2026surprisingeffectivenessapproximatevalue,
      title={The Surprising Effectiveness of Approximate Value Iteration in Self-Play}, 
      author={Raphael Boige and Amine Boumaza and Bruno Scherrer},
      year={2026},
      eprint={2609.09094},
      archivePrefix={arXiv},
      primaryClass={cs.AI},
      url={https://arxiv.org/abs/2609.09094}, 
}