- 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
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.
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.
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.
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.
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.
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.