The Surprising Effectiveness of Approximate Value Iteration in Self-Play
Raphael Boige, Amine Boumaza, Bruno Scherrer
cs.AI
Quick verdict
AVI self-play learns more accurate values than AlphaZero and plays competitively at far lower cost; solid oracle-based work, but baseline strength is open.
Summary
The paper revisits Approximate Value Iteration (AVI) — ε-greedy self-play, one-step negamax backups into a value network, and no tree search during training — and asks whether it can rival AlphaZero on moderately sized games. Using exact oracles (a strong Connect Four solver with distance-to-outcome, the MoHex solver for Hex(7x7), and synthetic F-Games with known minimax values), the authors compare against an in-house AlphaZero sharing the same JAX backbone, data budget, and optimization. AVI learns more accurate value functions at every tested MCTS budget (32–512 simulations), and its greedy one-step policy is competitive at far lower inference cost (at most 7 network calls on Connect Four, 49 on Hex, versus 512 MCTS simulations). Head-to-head, greedy AVI scores −0.09±0.04 against the strongest AZ on Connect Four but +0.38±0.09 on Hex(7x7). Substituting AVI's value into MCTS (cross-inference) improves both the in-house AZ and the external MiniZero agent on Othello and Go(9x9), where greedy AVI alone remains weaker than MiniZero. Limitations: the strongest claims are confined to solved games; the in-house baseline uses an MLP rather than a CNN backbone, with external calibration only on Connect Four; and the proposed bias-cancellation explanation for stability remains a hypothesis.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- AVI with one-step negamax backups and ε-greedy self-play trains stably (no divergence across seeds) on Connect Four, Hex(7x7), F-Games, Othello and Go(9x9), with 20 seeds on the solved games.
- AVI learns more accurate value functions (lower oracle MAE) than the in-house AlphaZero baseline at every tested MCTS budget (32–512 simulations) on Connect Four and Hex(7x7).
- Greedy one-step AVI is competitive with MCTS-based policies at far lower inference cost (≤7 network calls on Connect Four, ≤49 on Hex, vs 512 simulations), scoring −0.09±0.04 against AZ S=512 on Connect Four and +0.38±0.09 on Hex(7x7).
- AVI's value function improves MCTS-based agents — both the in-house AZ and the external MiniZero on Othello and Go(9x9) — when substituted as leaf evaluator under the same search budget (cross-inference).
- The post-AlphaZero dominance of search-based self-play may have eclipsed simpler direct value-learning approaches that modern deep-learning tooling has made practical.
Strengths
Oracle-based exact evaluation design
Value MAE (Eq. 6), policy regret (Eq. 7), oracle error and blunder rates on Connect Four/Hex(7x7)/F-Games give absolute quality measures that Elo-style or head-to-head evaluation cannot; the authors plausibly claim this is the first systematic oracle-based comparison of neural AVI and MCTS self-play across multiple games (§1, §4.2).
Controlled, compute-transparent comparison
One JAX codebase shares environments, replay buffer, optimizer, batch size, gradient-update counts and network backbone, with AZ adding only a policy head (§4.5); the N_forward+3·N_backward proxy is defined with an explicit disclaimer, and the inference asymmetry is concrete: ≤7 (Connect Four) / ≤49 (Hex) network calls vs 512 MCTS simulations (§5.1).
Multi-seed stability evidence
External calibration against weak-baseline artifacts
Honest scoping of claims
Weaknesses
Possibly handicapped baseline
Headline outruns one key number
Stability claim contains a silent mitigation
Reproducibility gaps
Narrow baseline coverage
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Preliminary Review: The Surprising Effectiveness of Approximate Value Iteration in Self-Play
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Does this paper prove that AlphaZero and MCTS are unnecessary?
No. AVI's greedy policy remains weaker than MiniZero's MCTS agent on Othello and Go(9x9) (§5.3). The paper's own conclusion is that MCTS stays valuable for turning values into decisions at inference time, while accurate values can apparently be learned without search during training; a hybrid (AVI value inside MCTS) is the strongest configuration shown.
Which games were used, and why these?
Connect Four (a strong solver giving exact outcomes and distance-to-outcome), Hex(7x7) (the MoHex solver, win/loss only), and synthetic F-Games with minimax values known by construction — all allow exact measurement of value error and policy regret. Othello and Go(9x9) add larger-scale tests against the publicly released MiniZero agents.
How much cheaper is AVI than AlphaZero?
At inference, greedy AVI needs at most 7 network evaluations per move on Connect Four and 49 on Hex(7x7), versus 512 MCTS simulations for the strongest AlphaZero configuration tested. For training, the paper uses a forward-equivalent proxy (one backward pass counted as three forwards); wall-clock, AVI took about 2 hours on Connect Four versus up to 2 days for AZ S=512 on comparable consumer GPUs (Appendix C).
Is the code available?
Yes. The authors state the code is publicly available (github.com/Egiob/avi), implemented in JAX on top of the PGX game-simulator suite and DeepMind's mctx MCTS library; the Connect Four oracle is the public Pons solver.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Quantitative curves (exact MAE/regret values and CI widths) exist only inside Figures 1–3 and 5–7; the extracted text provides captions and prose but not the plotted numbers, so effect magnitudes could not be independently checked. No truncation detected: the full reference list and Appendices A–F through Figure 7's caption are present.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.