Atari-5: Distilling the Arcade Learning Environment down to Five Games

Ideally a subset summary score would be strictly order preserving, in that if $a>b$ then $\Phi(a)>\Phi(b)$. Unfortunately this is not possible.

Proposition 1: No subset score can be strictly increasing.

Proof. Let $M^{\prime}$ be the strict subset of environments used by $\Phi_{M}$, then select $z\in[1..n]$ where $\mu_{z}\in M\setminus M^{\prime}$. Now consider two algorithms $a,b$, where $a_{i}=b_{i}\;\forall\,i\neq z$, and $a_{z}>b_{z}$. Hence we have that $a>b$, but not $\Phi(a)>\Phi(b)$. Therefore, the next best thing we can do is to require that our subset score be at least weakly order preserving, that is, if $a>b$ we can not have $\Phi_{M}(a)<\Phi_{M}(b)$.

Proposition 2: Any summary score of the form

with $c_{i}\in\mathbb{R}\geq 0$, is weakly increasing.

Proof. See Appendix C.

We therefore find that linear combination of scores, if constrained to non-negative weights, is weakly order preserving. We note that this is not the case for more sophisticated non-linear models, such as deep neural networks, which might reverse the order of algorithms. We also note that any monotonically increasing function $\phi:\mathbb{R}\rightarrow\mathbb{R}$ can be applied to the individual game scores, which we will take advantage of by using a log transform. We can therefore guarantee that if algorithm $a$ is strictly better than algorithm $b$, it can be no worse when measured using a weighted subset score, which is, as shown, the best we can do.

As shown, a weighted subset produces a monotonic measure of an algorithm’s performance. However, the question of which subset to use and how to weigh the scores remains. A trivial solution would be to weigh each score by $0$, which would be fast to generate and weakly order-preserving but completely uninformative. Therefore, we propose that individual scores should be weighted such that the summary score provides meaningful information about the performance of the algorithm. For established benchmarks, meaningful summary performance measures have often already been established. For example, with ALE, the most common summary score is median score performance. Therefore, we suggest that the prediction of an established summary score (target score) provides a sensible strategy for selecting and weighting the environments within the suite. That is, to find the subset of environments that best predicts the target score and weigh them according to their linear regression coefficients.

We therefore propose that using linear regression models to predicate a meaningful target summary score provides a good solution to the desiderta outlined above, and formalize the procedure. Given $m$ algorithms $a^{k}:k=1...m$ together with their individual evaluations $s^{k}_{i}\in\mathbb{R}$ on environments $i\in\{1:n\}$ and total/aggregate score $t^{k}\in\mathbb{R}$, e.g. $t^{k}=s_{1}^{k}+...+s_{d}^{k}$ or the average or the median. The “training” data set is hence $D=\{(s_{1}^{k},...,s_{n}^{k};t^{k}):k=1...m\}$. Let $I\subseteq\{1:n\}$ be a subset of games and $s^{I}:=(s^{i}:i\in I)$ be a corresponding score sub-vector. We want to find a mapping $f^{*}_{I}:\mathbb{R}^{I}\to\mathbb{R}$ that best predicts $t$ from $s^{I}$, i.e. formally $f^{*}_{I}=\arg\min_{f}\sum_{k=1}^{m}(t^{k}-f(s_{I}^{k}))^{2}$. Since for $I=\{1:d\}$, the best $f$ is perfect and linear, it is natural to consider linear $f$, which leads to an efficiently solvable linear regression problem. We further want to find small $I$ with small error. We hence further minimize over all $I\subseteq\{1:n\}$ of some fixed size $|I|=C$. The optimal set of games $I^{*}$ with best linear evaluation function $f^{*}$ based on games in $I^{*}$ hence are

We used the website paperswithcode⁴⁴4https://paperswithcode.com/dataset/arcade-learning-environment as the primary source of data for our experiments. This website contains scores for algorithms with published results on various benchmarks, including ALE. The dataset was then supplemented with additional results from papers not included on the website. Additions included various algorithms, such as evolutionary algorithms and shallow neural networks. A full list of algorithms and their sources contained within the dataset can be found in Appendix D.

We removed any algorithms that had results for fewer than 40 of the 57 games in the standard ALE dataset on the grounds that a reasonable median estimate could not be obtained. This reduced our dataset of 116 algorithms down to 62. When fitting models for subsets, any algorithm missing a score for a required game was excluded for that subset. We also excluded any games with results for fewer than 40 of the remaining 62 algorithms. The only game meeting this criteria was Surround. All scores were normalized using the standard approach from [5]

where $r_{i}$ and $h_{i}$ are the human and random scores for environment $i$ respectively, which we include in Appendix 12. We found that, even after normalization, scores differed across games by many orders of magnitude and produced non-normal residuals. We, therefore, applied the following transform

to the normalized scores, producing log normalised scores. Clipping was required as algorithms occasionally produce scores slightly worse than random, generating a negative normalized score. Both input and target variables were transformed using $\phi$, and all loss measures were calculated in transformed space. This transformation also has the effect that larger scoring games would not dominate the loss.

To better understand the games within ALE, we produced single-game linear models where the score from a single environment was used to predict the median Atari-57 score. We then ranked games according to their predictive ability as measured by their R². Due to a small parameter count (n=2), cross-validation was not used.

To assess the best selection of games for each subset, we evaluated all subsets of the ALE games of size five three or one that met our criteria as defined in Section 4.1.⁵⁵5We found diminishing returns after five games, however, we do also provide models for a larger ten-game set if additional precision is required. Subsets were evaluated by fitting linear regression models to the data using the log normalized scores of games within the subset to predict the median overall, selecting the model with the lowest 10-fold cross-validated mean-squared-error. For these models, we disabled intercepts as we wanted a random policy to produce a score of 0.

To make the best use of the 57 games available, we carefully ordered the subset searches to maximize the performance of the most common subset size while maintaining the property that smaller subsets are true subsets of their larger counterparts. All subsets of five games were evaluated, with the best subset selected as Atari-5. The Atari-3 subset was then selected as the best triple game subset of the Atari-5 subset and Atari-1 as the best single-game subset of Atari-3. Doing this ensures that only five games are included in the test set and also that evaluations on Atari-1 or Atari-3 can more easily be upgraded to Atari-5 if required. For the validation subsets, we selected the best three games, excluding the games used in Atari-5, as the validation set. We then extended this set to 5 games by choosing the best two additional games. Finally, the ten-game Atari-10 set was generated by selecting the best five additional games, not in Atari-5 nor Atari-5-Val.

Searching over all subsets took approximately 1-hour on a 12-core machine. No GPU resources were used. Source code to reproduce the results are provided in the supplementary material.

To better understand how much information our subsets capture about the 57 game dataset, we trained 57 linear regression models for the best five-game and ten-game subsets, predicting log-normalized scores for each game within the 57-game set. We then evaluated each of the 57 models according to their R², allowing us to identify well or poorly captured environments by the subset. These models also enable score predictions for any game within the 57-game set.

We found a significant difference in the ability of games within the ALE benchmark suite to predict median score estimates (Figure 2). For single-game subsets, Zaxxon performed best with $\text{R}^{2}=0.903$, and Surround the worst with $\text{R}^{2}=0.002$. The environment Name this Game was found to have the interesting property that its intercept was close to 0 (-0.03) and its scale close to 1 (1.01). As a result, normalized scores from Name This Game provide relatively good estimates for the median performance of an algorithm, by themselves, without modification.

We also note that several games have close to no predictive power when used by themselves. In the case of Pong, Surround, and Tennis, this is most likely due to a low score cap, which most algorithms easily achieve. Games within the hard exploration subset also performed poorly at predicting the median score due to many algorithms achieving no better than random performance.

As a baseline reference, we include results for the 7-game set used in the DQN paper [22]. The result demonstrates the importance of game selection in that our single-game model outperforms the 7-game baseline set used by the DQN paper. Table 2 gives the results for the top-performing regression model for each subset size. Coefficients are provided in Appendix E.

We also approximated the expected relative error of the median score, using $\log_{e}(10)$ times the mean absolute error in log space, which, for small residuals, is a good approximation of the relative error.⁶⁶6The authors were unable to find a reference for this, and so have provided a proof in Appendix G. We found that Atari-5 is generally within 10% of the true median score. In Table 3, we give the performance of popular algorithms on the Atari-5 benchmark.

To assess the impact of significantly different environmental settings, we used Atari-5 to evaluate the algorithm Go-Explore [11], which was not included in our training set. Go-Explore uses 400,000 frame time limits for each game, rather than the 108,000 used by the algorithms in our dataset. For many games, this difference fundamentally changes the skills the game requires and, importantly, the maximum possible score. For example, in the Space Invaders-like game Demon Attack, a shorter time limit requires an agent to take risks to score points more quickly. In contrast, an extended time limit emphasises staying alive instead. Given the differences, we were surprised to find that Atari-5 produced an overestimate of only 12.2% (an estimate of 1,620 compared to 1,446). While this result supports the robustness of Atari-5 to provide useful performance information, even when environmental settings have been changed, we still recommend that it not be used in these cases.

To assess the fairness of Atari-5, we split the algorithms with scores for all five games in the Atari-5 dataset into tertiles, ordered by their true median score performance. We looked for differences in accuracy between the groups by comparing the average absolute relative error and looked for bias by comparing the average relative error. No statistically significant difference was found between any pairs using the standard p=0.05 threshold and Wilson’s two-sided T-test.

We found that Atari-5 was able to produce surprisingly accurate score estimates for many of the other games in the ALE benchmark, as shown in Figure 4. There were 17 games which showed a high degree of correlation, with R² greater than 0.8, and together, the models explain 71.5% of the variance in log-scores within the dataset.

Inspired by this result, we tested the ‘vital few, trivial many’ principle [15],⁷⁷7Sometimes referred to as the 80/20 rule, or the Pareto Principle. by repeating the experiment with the Atari-10 dataset (17.5% of the environments) and found that those games could explain 80.0% of the variance of the full 57-game set. Because of this, in many cases, other performance measures (for example, the number of games with human-level performance) could potentially be approximated using the Atari-10 game set. Model parameters for predicting scores for these games is given in Appendix E. We also note that while the Atari-5 games predict many of the games well, they perform poorly in Bellemare’s hard exploration games [4].

Algorithms included in our training dataset are very diverse and include neural network and non-neural network approaches. Because of this, Atari-5 generates results robust to algorithmic and training choices, such as how many frames an algorithm was trained for. However, any changes made to the environment, importantly the maximum number of frames, could affect the result, as they modify the optimal policy and potentially the maximum score. We also note that stochasticity in the form of the probability of repeating actions is an environmental change but that our dataset contains both stochastic and deterministic variants. This does not seem to make a significant difference to the prediction accuracy.

We also note that Atari-5 does not do well at incorporating hard-exploration games (see Figure 4). We, therefore, recommend, for algorithms where this matters, to run individual tests for these games. Researchers could then establish their algorithm’s general performance via Atari-5, while also demonstrating a specific ability on hard-exploration problems by giving individual results on those games.

We believe that Atari-5 plays a vital role in increasing access and diversity in RL research, thus increasing reproducibility. Our work aims to address several issues that currently affect RL researchers. One of the barriers to working in RL research is the high level of computation required to produce results on common benchmarks. Researchers who do not have access to tens of thousands of dollars of compute capacity cannot evaluate their algorithms on established benchmarks, inhibiting their ability to publish their work. This has led to a lack of diversity in the literature, evidenced by the fact that only two companies have been able to produce results on the full dataset in six years. We believe Atari-5 is an important step in the right direction, as it brings Atari games inside the sphere of computationally accessible benchmarks.