A Review for Deep Reinforcement Learning in Atari:
Benchmarks, Challenges, and Solutions

As we mentioned above, recent reinforcement learning advances (Badia et al. 2020a, b; Kapturowski et al. 2018; Ecoffet et al. 2019; Schrittwieser et al. 2020; Hessel et al. 2021, 2017) are seeking agents that can achieve superhuman performance. Thus, we need a metric to intuitively reflect the level of the algorithms compared to human performance. Since being proposed by (Bellemare et al. 2013), the Human Normalized Score (HNS) is widely used in the RL research(Machado et al. 2018). HNS can be calculated as follows:

wherein g donates the gth game of Atari, i represents the algorithm i, $G_{g,\text{human average}}$ represents the human average score baseline (Toromanoff, Wirbel, and Moutarde 2019), and $G_{g,\text{random}}$ represents the performance of a random policy. Adopting HNS as an evaluation metric has the following advantages:

1. 1.

   Intuitive comparison with human performance. $\text{HNS}_{g,i}\geq 100\%$ means algorithm i have surpassed the human average performance in game g. Therefore, we can directly use HNS to reflect which games the RL agents have surpassed the average human performance.

2. 2.

   Performance across algorithms become comparable. Like Max-Min Scaling, the human normalized score can also make two different algorithms comparable. The value of $\text{HNS}_{g,i}$ represents the degree to which algorithm i surpasses the average level of humans in game g.

Mean HNS represents the mean performance of the algorithms across the 57 Atari games based on the human average score. However, it is susceptible to interference from individual high-scoring games like the hard-exploration problems in Atari (Ecoffet et al. 2019). While taking it as the only evaluation metric, Go-Explore(Ecoffet et al. 2019) has achieved SOTA compared to Agent57(Badia et al. 2020a), NGU(Badia et al. 2020b), R2D2(Kapturowski et al. 2018). However, Go-Explore fails to handle many other games in Atari like demon attack, breakout, boxing, phoenix (Fan, Xiao, and Huang 2021). Additionally, Go-Explore fails to balance the trade-off between exploration and exploitation, which makes it suffer from the low sample efficiency problem, which will be discussed later.

Median HNS represents the median performance of the algorithms across the 57 Atari games based on the human average score. Massive researchers (Schrittwieser et al. 2020; Hessel et al. 2021) have adopted it as a more reasonable metric for comparing performance between different algorithms. The median HNS has overcome the interference from individual high-scoring games. However, As far as we can see, there are at least two problems while only referring to it as the evaluation metrics. First of all, the median HNS only represents the mediocre performance of an algorithm. How about the top performance? One algorithm (Hessel et al. 2021) can easily achieve high median HNS, but at the same time obtain a poor mean HNS by adjusting the hyperparameters of algorithms for games near the median score. It shows that these metrics can show the generality of the algorithms but fail to reflect the algorithm’s potential. Moreover, adopting these metrics will urge us to pursue rather mediocre methods.

In practice, we often use mean HNS or median HNS to show the final performance or generality of an algorithm. Dispute upon whether the mean value or the median value is more representative to show the generality and performance of the algorithms lasts for several years (Mnih et al. 2015; Hessel et al. 2017; Hafner et al. 2020; Hessel et al. 2021; Bellemare et al. 2013; Machado et al. 2018). To avoid any issues that aggregated metrics may have, we advocate calculating both of them in the final results because they serve different purposes, and we could not evaluate any algorithm via a single one of them.

Capped Normalized Score is also widely used in many reinforcement learning advances (Toromanoff, Wirbel, and Moutarde 2019; Badia et al. 2020a). Among them, Agent57 (Badia et al. 2020a) adopts the capped human normalized score (CHNS) as a better descriptor for evaluating general performance, which can be calculated as $\mathrm{CHNS}=\max\{\min\{\mathrm{HNS},1\},0\}$. Agent57 claimed CHNS emphasizes the games that are below the average human performance benchmark and used CHNS to judge whether an algorithm has surpassed the human performance via $\mathrm{CHNS}\geq 100\%$. The mean/median CHNS represents the mean/median completeness of surpassing human performance. However, there are several problems while adopting these metrics:

1. 1.

   CHNS fails to reflect the real performance in specific games. For example, $\mathrm{CHNS}\geq 100\%$ represents the algorithms surpassed the human performance but failed to reveal how good the algorithm is in this game. From the view of CHNS, Agent57 (Badia et al. 2020a) has achieved SOTA performance across 57 Atari games, but while referring to the mean HNS or median HNS, Agent57 lost to MuZero (Fan, Xiao, and Huang 2021).

2. 2.

   It is still controversial that using $\mathrm{CHNS}\geq 100\%$ to represent the superhuman performance because it underestimates the human performance (Toromanoff, Wirbel, and Moutarde 2019).

3. 3.

   CHNS ignores the low sample efficiency problem as other metrics using normalized scores.

In practice, CHNS can serve as an indicator to reflect whether RL agents can surpass the average human performance. The mean/median CHNS can be used to reflect the generality of the algorithms.

As (Toromanoff, Wirbel, and Moutarde 2019) put it, the Human Average Score Baseline potentially underestimates human performance relative to what is possible. To better reflect the performance of the algorithm compared to the human world record, we introduced a complete human world record baseline extended from (Hafner et al. 2020; Toromanoff, Wirbel, and Moutarde 2019) to normalize the raw score, which is called the Human World Records Normalized Score (HWRNS), which can be calculated as follows:

wherein g donates the gth game of Atari, i represents the RL algorithm, $G_{i,human}$ represents the human world records, and $G_{g,random}$ represents means the performance of a random policy. Adopting HWRNS as an evaluation metric of algorithm performance has the following advantages:

1. 1.

   Intuitive comparison with human world records. As $\text{HNS}_{g,i}\geq 100\%$ means algorithm i have surpassed the human world records performance in game g. We can directly use HWRNS to reflect which games the RL agents have surpassed the human world records, which can be used to calculate the human world records breakthrough in Atari benchmarks.

2. 2.

   Performance across algorithms become comparable. Like the Max-Min Scaling, the HWRNS can also make two different algorithms comparable. The value of $\text{HWRNS}_{g,i}$ represents the degree to which algorithm i has surpassed the human world records in game g.

Mean HWRNS represents the mean performance of the algorithms across the 57 Atari games. Compared to mean HNS, mean HWRNS put forward higher requirements on the algorithm. Poor performance algorithms like SimPLe (Kaiser et al. 2019) will can be directly distinguished from other algorithms. It requires the algorithms to pursue a better performance across all the games rather than concentrate on one or two of them because breaking through any human world record is a huge milestone, which puts forward significant challenges to the performance and generality of the algorithm. For example, current model-free SOTA algorithms on HNS is Agent57 (Badia et al. 2020a), which only acquires 125.92% mean HWRNS, while GDI-H³ obtained 154.27% mean HWRNS and thus became the new state-of-the-art.

Median HWRNS represents the median performance of the algorithms across the 57 Atari games. Compared to Median HNS, median HWRNS also puts forward higher requirements for the algorithm. For example, current SOTA RL algorithms like Muzero (Schrittwieser et al. 2020) obtain much higher median HNS over GDI-H³ (Fan, Xiao, and Huang 2021) but relatively lower median HWRNS.

Capped HWRNS Capped HWRNS (also called SABER) is firstly proposed and used by (Toromanoff, Wirbel, and Moutarde 2019), which is calculated by $\mathrm{SABER}=\max\{\min\{\mathrm{HWRNS},2\},0\}$. SABER also has the same problems as CHNS, and we will not repeat them here. For more details on SABER, we recommend referring (Toromanoff, Wirbel, and Moutarde 2019).

As one of the commonly used metrics to reveal the learning efficiency for machine learning algorithms, training scale can also serve the purpose in RL problems. In ALE, the training scale means the scale of video frames used for training. Training frames for world modeling or planning via real-world models also need to be counted in model-based settings.

Game time is a unique metric of Atari, which means the real-time gameplay (Machado et al. 2018; Fan, Xiao, and Huang 2021). We can use the following formula to calculate this metric:

For example, 200M training frames equal to 38.5 days real-time gameplay (Fan, Xiao, and Huang 2021), and 100B training frames equal to 19250 days (52.7 years) real-time gameplay (Badia et al. 2020a). As far as we know, no Atari human world record was achieved by playing a game continuously for more than 52.7 years because it is less than 52.7 years since the birth of the Atari games.

As we mentioned several times while discussing the drawbacks of the normalized score, learning efficiency has been ignored in massive SOTA algorithms. Many SOTA algorithms achieved SOTA through training with vast amounts of data, which may equal 52.7 years continuously playing for a human. In this paper, we argue it is unreasonable to rely on the increase of data to improve the algorithm’s performance. Thus, we proposed the following metric to evaluate the learning efficiency of an algorithm:

For example, the learning efficiency of an algorithm over means HNS is $\frac{\text{mean HNS}}{\text{Num.Frames}}$, which means the algorithms obtaining higher mean HNS via lower training frames are better than those acquiring more training data methods.

In the origin benchmark of ALE (Bellemare et al. 2013), episodes terminate when all the lives of the player are lost. Nevertheless, some articles (Mnih et al. 2015; Hessel et al. 2017) will end a training episode after every loss of life for training while ending an episode after losing all lives for testing. It helps the agent to value their lives more and learn to avoid death. We argue that is a kind of game-specific knowledge, which should not be concluded in the benchmark for ALE. As (Machado et al. 2018) put it, we also advocate to use the game over signal be used for termination.

Several related work (Toromanoff, Wirbel, and Moutarde 2019) also noticed that this setting of ALE would affect the results of the algorithms. Maximum Episode Length means the maximum number of frames allowed per episode. This parameter ends the episode after a fixed number of time steps even if the game is not over. In most advance in RL (Badia et al. 2020a; Fan, Xiao, and Huang 2021; Kapturowski et al. 2018; Badia et al. 2020b), this parameter has been set to 30min (equal to 1E+5 frames), while that in (Machado et al. 2018) is set to 5min. To put forward higher requirements on learning efficiency of methods, we advocate to use 30min as the maximum episode length, which not only require the agents to find an optimal solution of the game but also require it to acquire the optimal score as soon as possible. We argue that the proposal of no maximum episode length (Toromanoff, Wirbel, and Moutarde 2019) is unreasonable because some games like Kangaroo will never stop being tracked in a circle.

In the ALE, there are two sets of actions for each game, namely the useful set and the full set. Instead of using the useful set consisting of 4 actions that have been used in massive works (Mnih et al. 2015; Hessel et al. 2017), we advocate to use the full set of actions which consists of 18 actions.

As we mentioned above, in the training phase, we advocate to use at most 200M frames and end an episode when all the lives are lost or the episode exceeds 30min. Inside an episode, the agent should select a proper action from the full action set.

Except for the same setting as training, in evaluation procedures, we advocate to record the training score by averaging k consecutive episodes across the whole training.

As recommended by (Machado et al. 2018), we also advocate reporting the training score calculated by averaging k consecutive episodes across the whole training. It gives more information about the stability of the training and removes the statistical bias induced when reporting the score of the best policy, which is today a common practice (Hessel et al. 2017; Mnih et al. 2015; Badia et al. 2020a, b). Except for the HNS, we advocate that use evaluation metrics based on human world records like HWRB, HWRNS, SABER should be included in the final performance, and at the same time, the learning efficiency should also be considered while evaluating whether the RL agents have achieved superhuman performance.

Rainbow (Hessel et al. 2017) is a classic value-based RL algorithm among the DQN algorithm family, which has fruitfully combined six extensions of the DQN algorithm family. It is recognized to achieve state-of-the-art performance on the ALE benchmark. Thus, we select it as one of the representative algorithms of the SOTA DQN algorithms.

IMPALA, namely the Importance Weighted Actor Learner Architecture (Espeholt et al. 2018), is a classic distributed off-policy actor-critic framework, which decouples acting from learning and learning from experience trajectories using V-trace. IMPALA actors communicate trajectories of experience (sequences of states, actions, and rewards) to a centralized learner, which boosts distributed large-scale training. Thus, we select it as one of the representative algorithms of the traditional distributed RL algorithm.

LASER (Schmitt, Hessel, and Simonyan 2020) is a classic Actor-Critic algorithm, which investigated the combination of Actor-Critic algorithms with a uniform large-scale experience replay. It trained populations of actors with shared experiences and claimed to achieve SOTA in Atari. Thus, we select it as one of the SOTA RL algorithms within 200M training frames.

(Kapturowski et al. 2018) Like IMPALA, R2D2 (Kapturowski et al. 2018) is also a classic distributed RL algorithms. It trained RNN-based RL agents from distributed prioritized experience replay, which achieved SOTA in Atari. Thus, we select it as one of the representative value-based distributed RL algorithms.

One of the classical problems in ALE for RL agents is the hard exploration problems (Ecoffet et al. 2019; Bellemare et al. 2013; Badia et al. 2020a) like Private Eye, Montezuma’s Revenge, Pitfall!. NGU (Badia et al. 2020b), or Never Give Up, try to ease this problem by augmenting the reward signal with an internally generated intrinsic reward that is sensitive to novelty at two levels: short-term novelty within an episode and long-term novelty across episodes. It then learns a family of policies for exploring and exploiting (sharing the same parameters) to obtain the highest score under the exploitative policy. NGU has achieved SOTA in Atari, and thus we selected it as one of the representative population-based model-free RL algorithms.

Agent57 (Badia et al. 2020a) is the SOTA model-free RL algorithms on CHNS or Median HNS of Atari Benchmark. Built on the NGU agents, Agent57 proposed a novel state-action value function parameterization method and adopted an adaptive exploration over a family of policies, which overcome the drawback of NGU (Badia et al. 2020a). We select it as one of the SOTA model-free RL algorithms.

GDI (Fan, Xiao, and Huang 2021), or Generalized Data Distribution Iteration, claimed to have achieved SOTA on mean/median HWRNS, mean HNS, HWRB, median SABER of Atari Benchmark. GDI is one of the novel Reinforcement Learning paradigms, which combined a data distribution optimization operator into the traditional generalized policy iteration (GPI) (Sutton and Barto 2018) and thus achieved human-level learning efficiency. Thus, we select them as one of the SOTA model-free RL algorithms.

As one of the classic model-based RL algorithms on Atari, SimPLe, or Simulated Policy Learning (Kaiser et al. 2019), adopted a video prediction model to enable RL agents to solve Atari problems with higher sample efficiency. It claimed to outperform the SOTA model-free algorithms in most games, so we selected it as representative model-based RL algorithms.

Dreamer-V2 (Hafner et al. 2020) built world models to facilitate generalization across the experience and allow learning behaviors from imagined outcomes in the compact latent space of the world model to increase sample efficiency. Dreamer-V2 is claimed to achieve SOTA in Atari, and thus we select it as one of the SOTA model-based RL algorithms within the 200M training scale.

Muzero (Schrittwieser et al. 2020) combined a tree-based search with a learned model and has achieved superhuman performance on Atari. We thus selected it as one of the SOTA model-based RL algorithms.

As mentioned in NGU, a grand challenge in reinforcement learning is intelligent exploration, which is called the hard-exploration problem (Machado et al. 2018). Go-Explore (Ecoffet et al. 2019) adopted three principles to solve this problem. Firstly, agents remember previously visited states. Secondly, agents first return to a promising state and then explore it. Finally, solve simulated environment through any available means, and then robustify via imitation learning. Go-Explore has achieved SOTA in Atari, so we select it as one of the SOTA algorithms of the hard exploration problem.

Musile (Hessel et al. 2021) proposed a novel policy update that combines regularized policy optimization with model learning as an auxiliary loss. It acts directly with a policy network and has a computation speed comparable to model-free baselines. As it claimed to achieve SOTA in Atari within 200M training frames, we select it as one of the SOTA RL algorithms within 200M training frames.

From Figs. 4, we see there are at least 35 human world records that have not been broken through by current SOTA RL algorithms. Therefore, it is too early to say we have achieved superhuman performance.

From Tabs 7, 8, and 10 in the Appendix, we see current SOTA algorithms are fragile facing the hard exploration problems, and others like Agent57 or Go-Explore that have overcome those problems failed to balance the trade-off between exploration and exploitation leading to lower learning efficiency.

Learning from sparse rewards is extremely difficult for model-free RL algorithms, especially those without intrinsic rewards that struggle to learn from weak gradient signals. Model-based methods can ease those problems by adopting a world model to planning (Schrittwieser et al. 2020) or replay (Hafner et al. 2020), which both enhanced the gradient signals. However, being utterly dependent on planning is unrealistic and will lose generality in some Atari Games like Tennis.

From Figs. 4, current SOTA algorithms like Agent57 may require more than 52.7 years of game-play to achieve SOTA performance, which revealed its low learning efficiency. As recommended in (Hafner et al. 2020), we also argue for high learning efficiency algorithms, and we advocate that 200M training frames (equal to 38 days) are enough for achieving a superhuman agent.

The trade-off between exploration-exploitation is a classic difficult problem in RL algorithms (Sutton and Barto 2018). Algorithms designed for hard exploration problems may fail to trade-off the balance leading to low sample efficiency. Others may suffer from hard exploration problems. Thus how to trade off balance becomes more important. NGU, Agent57 tried to ease this problem by training a family of policies from extremely explorative to highly exploitative. Based on that, GDI (Fan, Xiao, and Huang 2021) proposed the data distribution iterator to formulate this procedure and revealed its superiority to the origin process without the data distribution iterator. It may be a promising way to solve this problem.

Planning algorithms like Muzero (Schrittwieser et al. 2020) fail when the outcome signals of the planning algorithms become misleading or indistinguishable. The former may come from the accumulation of model approximation errors, and the latter may come from a relatively sparse rewards environment like Montezuma Revenge. The former problem may need more assistance from more advanced deep learning methods, but the latter can be solved by a long time of planning. More precisely, we need a big picture that guides agents towards a better decision. GDI (Fan, Xiao, and Huang 2021) showed a promising way to combine techniques from Go-Explore and Muzero into the data distribution iteration operator and guide the policy inside an episode, which may solve the low learning efficiency and hard exploration problems. Musile (Hessel et al. 2021) also offers another interesting combination of policy-based methods with model-based RL.

As Hessel et al. (2017) put it, the DRL community has made several independent improvements those years, but it is unclear whether there are unified frameworks that can fruitfully combine those improvements and make each component compatible. CASA (Xiao et al. 2021b) provided promising frameworks, and based on CASA, GDI further proposed a more general paradigm. We believe a unified framework may help to obtain the superhuman agents.