AlphaZero Neural Scaling and Zipf’s Law: a Tale of Board Games and Power Laws

Oren Neumann, Claudius Gros · 2024

Read AlphaZero Neural Scaling and Zipf’s Law: a Tale of Board Games and Power Laws by Oren Neumann, Claudius Gros (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11979.txt.

Introduction

Oren Neumann and Claudius Gros study why the game playing system AlphaZero improves as a power law in a 2024 paper. Power law gains with scale appear across AI, with no agreed cause. In language, one theory ties them to Zipf's law, where a few items are very common and most are rare. The authors test whether board game states follow the same pattern, and whether learning order matches that theory.

Game states in training and play data do follow Zipf's law, which they trace to the tree shape of games. Agents improved first on the most frequent states, even though those are not the simplest to model. That order matches the theory. They also find a failure mode: when end game states rank among the most frequent, larger models can get worse. Bigger models shift focus to those common but minor states and lose ground on key early states.

Catalog record

CREATOROren Neumann, Claudius Gros
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11979

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

AlphaZero Neural Scaling and Zipf’s Law: a Tale of Board Games and Power Laws Oren Neumann, Claudius Gros Abstract Neural scaling laws are observed in a range of domains, to date with no universal understanding of why they occur. Recent theories suggest that loss power laws arise from Zipf’s law, a power law observed in domains like natural language. One theory suggests that language scaling laws emerge when Zipf-distributed task quanta are learned in descending order of frequency. In this paper we examine power-law scaling in AlphaZero, a reinforcement learning algorithm, using a model of language-model scaling. We find that game states in training and inference data scale with Zipf’s law, which is known to arise from the tree structure of the environment, and examine the correlation between scaling-law and Zipf’s-law exponents. In agreement with the quanta scaling model, we find that agents optimize state loss in descending order of frequency, even though this order scales inversely with modelling complexity. We also find that inverse scaling, the failure of models to improve with size, is correlated with unusual Zipf curves where end-game states are among the most frequent states. We show evidence that larger models shift their focus to these less-important states, sacrificing their understanding of important early-game states. 1 Introduction Neural scaling laws, describing the scaling of model performance with training resources, have been documented across many architectures and use cases [ 1 , 2 , 3 , 4 , 5 ] . The performance of these models, typically measured by test loss, follows a power law in either compute, model size or training data. The robustness of these power laws and their usefulness in training large models, especially large language models (LLMs) [ 6 ] , prompted a range of attempts to find a model explaining the mechanism behind neural power-law scaling [ 7 , 8 , 9 , 10 , 11 ] . Several models connect performance power laws to Zipf’s law, a universal power law appearing in natural language [ 12 , 9 , 13 , 14 , 15 , 16 ] . Scaling laws in reinforcement learning (RL) are so far relatively rare compared to supervised learning [ 17 , 18 , 19 ] . AlphaZero, a multi-agent RL algorithm that beat human champions in games like chess and Go [ 20 ] , exhibits power laws of Elo score with training resources, as well as a power law relation between compute and optimal model size [ 5 , 21 , 22 ] . In this paper, we explore the mechanism behind known RL scaling laws, comparing this mechanism to the quantization model of LLM scaling [ 12 ] . Our main findings are: 1. We find that AlphaZero agents that exhibit scaling laws, such as those trained in Neumann & Gros (2022) [ 5 ] , produce train and test data that follows Zipf’s law, suggesting that learned tasks also scale with Zipf’s law. 2. We show how these smooth Zipf laws form when agent policies are combined with the tree-structure of board games, which is known to create a Zipf-like state distribution [ 23 ] . We find a correlation between the Zipf curve and scaling exponents, exposed by modulating policy temperature at inference. 3. In agreement with the quanta scaling model, we show that agents minimize loss on game states in descending order of frequency, counter-intuitively achieving better performance on harder tasks. 4. Inverse scaling, the abrupt failure of scaling laws at large sizes, coincides with an unusual state-frequency distribution. We show that large models scale negatively on games with an unusual tree structure that increases the frequency of strategically-unimportant late-game states. Larger agents achieve better loss on these late-game states, sacrificing performance on more important early-game states. We propose an explanation of inverse scaling in AlphaZero using a combination of the quantization model and the selective non-stationarity of training targets. All code and data required to reproduce our results is publicly available 1 1 1 Code and data available at github.com/OrenNeumann/alphazero_zipfs_law . . 2 Background Figure 1: Zipf’s law in AlphaZero games. Board-state frequency follows a power law in state rank, here for Connect Four and Pentago. Similar exponents \alpha appear for agents of various sizes trained on different games, see appendix C.1 . A short description of the AlphaZero algorithm and AlphaZero scaling laws is given in appendix A . Zipf’s law Zipf’s law is an empirical law describing the distribution of values when sorted in decreasing order, typically with respect to frequency [ 24 ] . When sorting elements in decreasing order of frequency, e.g. words in natural language texts, one regularly finds that the frequency distribution S(n) follows a power law in element rank n : S(n)\propto\frac{1}{n^{\alpha}}\,, (1) often with \alpha\approx 1 for natural language datasets [ 25 , 26 ] . Quantization model of LLM scaling Michaud et al. (2023) [ 12 ] proposed that a ‘quantization model’ may explain the origin of power-law scaling in LLMs, connecting neural-network training to language Zipf’s laws. The model assumes that LLMs learn discrete task quanta and that the frequency of these tasks follows Zipf’s law. The quantization model suggests that language models learn tasks in descending order of frequency , which leads to power-law scaling laws. If the loss on each task is reduced by a fixed amount \Delta L after it is learned, then a model that learned the first n tasks will have an expected loss of L=\frac{\Delta L}{\alpha\zeta(\alpha+1)}\cdot n^{1-\alpha}+L_{\infty}\,\implies\,(L-L_{\infty})\propto n^{1-\alpha}\,, (2) where \zeta is the Riemann zeta function. It is assumed that a fixed neural capacity c is needed to fit each of the independent task quanta. At the limit of infinite compute and data, the number of learned task quanta n=\frac{N}{c} is determined by the number of parameters N . Eq. 2 then becomes a power-law scaling law: (L(N)-L_{\infty})\propto\frac{1}{N^{\alpha-1}}\,, (3) and the Zipf exponent \alpha determines the size-scaling exponent \alpha_{N}=\alpha-1 . Similar reasoning relates compute- and data-scaling laws to Zipf’s law. Other supervised learning scaling models A large body of work exists on models of neural scaling laws on static datasets, several of which making the connection between Zipf’s law and scaling laws. Hutter (2021) [ 9 ] argues that data scaling laws emerge when training on Zipf-distributed data under the assumption of infinite memory. Bordelon et al. (2020) [ 13 ] develop a model of data scaling laws for kernels, which applies to neural nets at the infinite width limit. Other works expand this line of work on kernel models, including results on real datasets [ 14 , 27 ] . Maloney et al. (2022) [ 15 ] develop a model that explains joint scaling of model size and dataset size. Cabannes et al. (2023) [ 16 ] assume Zipf-distributed data and develop a model for scaling of attention models. Schaeffer et al. (2025) [ 28 ] propose that exponential scaling on individual tasks can aggregate to a power law when the distribution of success probabilities is heavy tailed, in the case of multiple attempts per task. Dohmatob et al. (2024) [ 29 ] explore model collapse through the effect of synthetic data on heavy-tailed data distributions. We frequently compare our results to Michaud

Read the complete text