AVI vs AlphaZero: 7 Evals vs 512, Same Strength

Nine years of orthodoxy says you can't train strong game agents without tree search. AlphaZero's MCTS-in-the-loop is the template every successor copied — MuZero, Gumbel AZ, MiniZero, your local Kaggle poker bot. A paper posted yesterday from Université de Lorraine (Boige, Boumaza, Scherrer) runs the control experiment the field skipped: plain Approximate Value Iteration (AVI) — ε-greedy self-play, one-step negamax backups, no search at all during training — learns better value functions than AlphaZero and plays it roughly even, using 7 network evaluations per move where AlphaZero-512 uses 512.

The problem: nobody measures values, only wins

Self-play algorithms are almost always evaluated by Elo or head-to-head matches. Those measure relative strength against whatever opponents you happened to have. They say nothing about whether the learned value function is actually right — which is the thing you'd want to know if you plan to bolt search onto it at inference. The authors sidestep this by working on games with exact oracles: Connect Four (~10¹² positions, solvable in <0.1s per state) and Hex(7×7), plus synthetic F-Games. With ground truth available, value error and policy regret become measurable, not vibes. This is — as far as they know — the first systematic oracle-based comparison of neural AVI against MCTS self-play across multiple non-trivial games.

The method: the deadly triad, deliberately

AVI here is almost aggressively simple. Fixed network θ generates negamax targets y(s) = max_a [R(s,a) − γV̄(f(s,a))] over states sampled from ε-greedy self-play, stored in a circular replay buffer; then the network regresses onto those targets with MSE. Repeat. Function approximation + bootstrapping + off-policy learning — the "deadly triad" that RL textbooks warn causes divergence. The expected failure never materializes: across 20 seeds on both games, zero divergences, smooth learning curves. AlphaZero baseline: standard PUCT MCTS, S ∈ {32…512} simulations, same 2.4M gradient updates and shared data/optimization protocol.

mindmap
  root((Self-play targets))
    AlphaZero
      MCTS per state: 32-512 NN evals
      Value target: one terminal outcome z per episode
      Policy distillation from visit counts
    AVI
      No tree search in training
      Target: 1-step negamax backup, dense per state
      Inference: greedy over legal actions (7 evals in Connect Four)

The results: values win, headlines don't quite

• Value error: AVI is lower than every AlphaZero budget in both games, and the gap widens with training — even AZ at S=512 never catches up.
• Cross-inference: hold the AlphaZero policy fixed, swap its value head for AVI's — error rate drops across the whole MCTS-budget range, in both games. AVI's values are better raw material for search.
• Head-to-head vs AZ-512: Hex(7×7) +0.38 ± 0.09 in AVI's favor; Connect Four −0.09 ± 0.04 — a statistical tie with 73× fewer evals per move (7 vs 512) and a fraction of the training compute.
• Bigger games: greedy AVI trains stably on Othello and Go(9×9) but loses head-to-head to MiniZero — greedy inference can't concentrate compute on promising lines. Yet feeding AVI's values into MiniZero's own MCTS improves the independently trained baseline at equal budget.

Here's the mechanism the abstract doesn't spell out: AlphaZero's value head trains on terminal outcomes only — one scalar z per episode, broadcast to every state in the trajectory, mostly credit assignment noise for early moves. AVI trains on a fresh, dense negamax target at every visited state, bootstrapped but immediately corrected each iteration. On solved games you can see the consequence directly: the outcome-only target is high-variance, the backup target is low-variance given a decent successor estimate. That, not cleverness, is why AVI's value head wins. The authors' own hypothesis for why the deadly triad doesn't bite: in negamax backups, the opponent's value enters with opposite sign, so approximation errors alternate in sign across plies instead of compounding — overestimation bias self-cancels. They flag it as unproven; it's the paper's most testable idea.

Limitations, including one they bury

Three they admit: exact evaluation restricts the strong claims to Connect Four / Hex(7×7) / F-Games; nothing tested at Go(19×19) or Chess scale; the compute proxy ignores wall-clock overhead of MCTS tree construction (which flatters AVI, if anything). What they bury: the AlphaZero baseline is in-house, not the DeepMind reference implementation — the external calibration with AlphaZero.jl is Connect Four only, and it's a different architecture and budget, so it calibrates the oracle metrics but not the head-to-head. Also, AVI's greedy policy on Connect Four is actually slightly behind AZ-512; the parity story is carried by Hex. And the ε-greedy exploration means sparse strategic lines may simply never enter the replay buffer — a sampling weakness they defer to future work rather than quantify.

Why builders should care

The paper's real reframe: training and inference are separable design decisions. You don't need search to learn good values; you may need search to turn values into moves in wide-branching domains. That's an architecture hint for anything with adversarial structure — game solvers, adversarial planning, agentic environments where an opponent (or an environment counterfactual) is in the loop. If you're burning 512 simulations per decision to compensate for a mushy value head, the cheap experiment is: train a dense-backup value head on the side, swap it in at inference, measure. The cross-inference result says the swap is often a free win. And for RL practitioners generally: the "deadly triad" is a caution, not a law — alternating-sign error propagation may be a free stabilizer hiding in adversarial formulations.