PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents

Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, Michael Bowling

arXiv:1709.06009v2cs.LG

TL;DR

The paper addresses fragmented and potentially misleading evaluation practices for agents tested in the ALE. It reviews protocols, proposes best practices and platform extensions, and reports benchmarks that support clearer comparison while identifying persistent challenges and open problems.

  • Problem

    Diverse ALE evaluation methodologies are often conflated, making agent comparisons difficult or misleading and motivating standardized protocols.

  • Method

    The article surveys ALE evaluation practices, proposes methodological best practices, introduces sticky actions and multiple game modes, and provides benchmark results under the proposed practices.

  • Results

    In 22 out of 60 games, Sarsa(λ) + Blob-PROST showed statistically significant improvement from 100 million to 200 million frames, while most games showed diminishing improvements.

  • Takeaways & Limitations

    The proposed practices and new ALE are intended to distinguish evaluation protocols, improve reproducibility, and support comparison and analysis of sample efficiency.

  • Takeaways & Limitations

    Learned generative models have not yet demonstrated successful planning in the ALE, with rollout accuracy typically degrading after a few dozen time steps.

Abstract

from arXiv · show

The Arcade Learning Environment (ALE) is an evaluation platform that poses the challenge of building AI agents with general competency across dozens of Atari 2600 games. It supports a variety of different problem settings and it has been receiving increasing attention from the scientific community, leading to some high-profile success stories such as the much publicized Deep Q-Networks (DQN). In this article we take a big picture look at how the ALE is being used by the research community. We show how diverse the evaluation methodologies in the ALE have become with time, and highlight some key concerns when evaluating agents in the ALE. We use this discussion to present some methodological best practices and provide new benchmark results using these best practices. To further the progress in the field, we introduce a new version of the ALE that supports multiple game modes and provides a form of stochasticity we call sticky actions. We conclude this big picture look by revisiting challenges posed when the ALE was introduced, summarizing the state-of-the-art in various problems and highlighting problems that remain open.

1. Introduction

The ALE evaluates general AI competency across dozens of Atari 2600 games and has become an influential testbed. This article reviews its use, identifies methodological concerns, and proposes practices and platform changes to improve future evaluation.

  • 1. Introduction: The ALE is a challenge problem and evaluation platform for agents seeking competency across many Atari 2600 games without game-specific information.Agents generally perceive the environment through video, while the games provide varied tasks and are independent of experimenter-designed environments.
  • 1. Introduction: The platform has attracted extensive research attention, including the high-profile DQN result of human-level control in a large fraction of Atari games.
  • 1. Introduction: The article examines how researchers use the ALE, highlights overlooked issues, and proposes course corrections intended to maximize its scientific value.
  • 1. Introduction: Its contributions include reviewing evaluation methods, identifying reinforcement-learning best practices, and introducing sticky-action stochasticity to address deterministic dynamics.
  • 1. Introduction: The article also provides reproducible benchmark results, supports multiple game modes and difficulty levels, and reviews state-of-the-art and open problems.

2. Background

The ALE instantiates reinforcement learning as sequential interaction with Atari environments, where agents learn policies or approximate action-value functions from observations and rewards. Common approaches include linear feature-based control and neural-network methods such as DQN.

  • 2. Background: Reinforcement learning models the agent–environment interaction as an MDP in which actions produce subsequent states and rewards.
  • 2. Background: In the ALE, an agent selects joystick actions, receives rewards and observations, and may observe a 210 × 160 image, 1024-bit RAM state, or both.RAM represents the emulator state more directly, while a single image may not satisfy the Markov property.
  • 2. Background: ALE agents interact episodically, and performance is primarily measured by the undiscounted sum of rewards earned during an episode.The paper cautions that score alone is not necessarily an indicator of AI progress.
  • 2. Background: The typical RL objective is to learn a policy or action-value function that captures expected long-range reward, often using function approximation because the state space is too large for tabular values.
  • 2. Background: Linear control methods represent state–action observations with features and estimate action values as θ⊤φ(s, a); Sarsa(λ) updates this approximation as rewards are observed.Blob-PROST features enabled Sarsa(λ) to achieve performance comparable to DQN in several Atari games.
  • 2. Background: DQN replaces handcrafted feature design with a neural network that estimates action values, using convolutional layers, a target network, reward clipping, and experience replay.

3. Divergent Evaluation Methodologies in the ALE

ALE studies use diverse evaluation protocols, and failing to distinguish them can make direct comparisons difficult or misleading. The paper therefore advocates standardized procedures covering hyperparameters, training data, performance summaries, and environmental stochasticity.

  • 3. Divergent Evaluation Methodologies in the ALE: Hundreds of ALE papers use distinct protocols, but inadequate distinctions between them make direct comparisons difficult or misleading.
  • 3. Divergent Evaluation Methodologies in the ALE: Because evaluating ALE algorithms is computationally expensive, the paper proposes a standard methodology and benchmarks to reduce the cost of principled comparison.
  • 3. Divergent Evaluation Methodologies in the ALE: Protocol differences can be individually benign yet undermine direct comparisons when researchers ignore them.
  • 3.1 Methodological Differences: Hyperparameters should be selected on training games and evaluated once on held-out test games to assess generality without game-specific tuning.
  • 3.1 Methodological Differences: Training data should be measured in frames rather than episodes because episode lengths vary and successful policies may receive more experience under episode-based limits.
  • 3.1 Methodological Differences: Researchers should report performance at multiple learning intervals because diverse summary statistics make results across 60 games difficult to compare.
  • 3.1 Methodological Differences: The deterministic ALE permits high scores from memorized open-loop action sequences, motivating stochasticity injection in evaluation.

4. Summarizing Learning Performance

ALE studies commonly compress learning across many games into summary statistics, but different protocols expose different aspects of progress, stability, and sample efficiency. The authors recommend reporting average performance over the last k episodes during training, supplemented by measurements at selected training points and publicly released learning curves.

  • Common Performance Measures: Learning curves are difficult to display and compare across the ALE’s 60 games, motivating numerical summaries of performance for each game.The paper frames these summaries as responses to the practical challenge of comparing many learning processes.
  • Evaluation after learning: Evaluating only after training hides sample efficiency and can reward agents that explore poorly before switching to exploitation.This protocol also overlooks continual improvement during the training period.
  • Evaluation of the best policy: Evaluating the best policy fails to capture unstable learning, performance collapse, or the greater stability of a lower-scoring agent.In Centipede, Sarsa(λ) + Blob-PROST scores highly early but later collapses, whereas DQN is lower-scoring but more stable.
  • Area under the learning curve: Area under the learning curve rewards sustained average performance and penalizes spikes, but it can miss plummeting behavior and cannot distinguish instability from steady progress.For the Centipede example, Sarsa(λ) + Blob-PROST appears better than DQN under this metric despite its later collapse.
  • Proposal: Performance During Training: The proposed standard reports average performance over the last k episodes, requiring agents to perform well during learning rather than during a separate evaluation phase.Spiking or plummeting methods score poorly compared with methods that improve continually and stably.
  • Proposal: Performance During Training: Reporting this statistic at multiple training points provides a compact view of sample efficiency, while full learning curves enable post-hoc analysis of learning rate and stability.The benchmark reports averages over the last 100 episodes before 10, 50, 100, and 200 million frames and releases the full learning-curve data.

5. Determinism and Stochasticity in the Arcade Learning Environment

Earlier ALE versions were deterministic, allowing open-loop agents to memorize action sequences and achieve strong scores without using observations. The paper examines alternative stochasticity protocols and proposes sticky actions as a reproducible way to test robustness while limiting disruption to learning.

  • Determinism: Deterministic ALE dynamics let agents memorize effective action sequences while ignoring perceived state, producing solutions unlikely to generalize beyond ALE.The agent starts from the same initial state, and each action sequence has the same outcome.
  • Evaluation protocols: Researchers introduced diverse protocols—including injected stochasticity, no-ops, human starts, and random frame skips—but their results are difficult to compare directly.The paper argues for a single standard protocol that distinguishes brittle open-loop from robust closed-loop solutions.
  • The Brute: The Brute exploits determinism through trajectory-based state representations and can estimate deterministic state-action outcomes from a single sample.Its implementation uses maximum-likelihood transition and reward estimates for stochastic environments.
  • The Brute: The Brute achieved competitive performance in several games, but its performance critically depended on deterministic dynamics and failed under small random perturbations.Bellemare et al. reported that it outperformed the best learning method on 45 of 55 games under a different evaluation protocol.
  • Sticky actions: Sticky actions execute the agent’s previous action with probability ς instead of its newly selected action, adding stochasticity without modifying the Stella emulator.The design aims to be minimally non-Markovian, preserve task difficulty, and require changes only to the ALE framework.
  • Sticky actions: Sticky actions differ from random delays because agents can change their intended action before the repeated action carries through, which matters in timing-sensitive games such as Q*bert.With ς = 0.25, the environment has a 25% chance of not executing the desired action immediately.
  • Evaluation results: Under ς = 0.25, the Brute was substantially impacted while DQN and Sarsa(λ) + Blob-PROST were comparatively robust, supporting sticky actions as a robustness evaluation.The paper concludes that sticky actions discourage memorization while preserving reproducibility and interacting naturally with frame skipping and discounting.
  • Alternative protocols: Alternative start-state methods preserve action control but do not prevent deterministic exploitation, whereas stochastic methods affect control throughout an episode.The authors argue that sticky actions minimize the impact of stochasticity while retaining its diagnostic value.

6. Benchmark Results in the Arcade Learning Environment

The benchmark evaluates Sarsa(λ) + Blob-PROST and DQN across 60 Atari games using sticky actions and performance measurements throughout learning. Sarsa(λ) + Blob-PROST generally improves steadily, while DQN shows greater variability, limited benefit from additional data, and algorithm-dependent performance drops.

  • Benchmark methodology: The benchmark evaluates Sarsa(λ) + Blob-PROST and DQN in 60 Atari 2600 games using sticky actions.Performance is measured at 10, 50, 100, and 200 million frames, with averages over 24 trials for Sarsa(λ) + Blob-PROST and 5 trials for DQN.
  • Sarsa(λ) + Blob-PROST: Sarsa(λ) + Blob-PROST’s performance steadily increases in most games throughout learning.Scores at 200 million frames are lower than at 100 million in only 10% of games, with statistically significant decreases in Carnival, Centipede, and Wizard of Wor.
  • Sarsa(λ) + Blob-PROST: Only 22 out of 60 games show statistically significant Sarsa(λ) + Blob-PROST improvements from 100 million to 200 million frames.The observed stagnation in games such as Montezuma’s Revenge is attributed to exploration issues that prevent discovery of additional rewards.
  • DQN: DQN reaches its highest score at 200 million frames in only 35 out of 60 games and benefits significantly over 100 million frames in only 18 games.The authors report greater learning variability for DQN and caution that the five-trial sample may have insufficient statistical power to detect decreases.
  • Cross-algorithm trends: Performance drops appear algorithm dependent, whereas Asteroids, Pitfall, and Tennis remain difficult for both algorithms.The shared difficulties are associated with hard exploration tasks or complex dynamics requiring better value-function representations.
  • Cross-algorithm trends: Sticky actions do not appear to favor either benchmarked algorithm: Sarsa(λ) + Blob-PROST and DQN retain comparable performance and each is better in an equal number of games.The benchmark is intended to support direct comparison and reproducibility under a common experimental methodology.

7. Open Problems and the Current State-of-the-Art in the ALE

The ALE community has made substantial progress across several research directions, but representation learning, planning and model-learning, exploration, transfer learning, and off-policy learning remain open problems.

  • Representation learning: Representation-learning methods can jointly learn representations and control policies, but DQN-like approaches require high sample complexity and additional tuning.DQN outperforms Sarsa(λ) + Blob-PROST in fewer than 20% of games at 10 million frames and is comparable at 100 million frames.
  • Planning and model-learning: Planning remains rare in the ALE because general heuristics must handle large branching factors and goals sometimes thousands of steps ahead.Most successful planning systems use Stella’s exact generative model; successful planning with a learned model has not been clearly demonstrated.
  • Planning and model-learning: Learned ALE models can support exploration, but compounding errors and slower-than-emulator execution keep fast, accurate model-learning open.Oh et al.’s models appear accurate for up to one hundred time steps, yet algorithms still frequently restore the model to the real game state.
  • Exploration: Exploration is difficult because the ALE has potentially 2^1024 states, sparse delayed rewards, and games where random behavior is more likely to produce negative than positive rewards.In some games, thousands of actions precede the first positive reward, making random exploration unlikely within typical sample constraints.
  • Transfer learning: Transfer-learning attempts remain limited to similar subsets of games, can suffer negative transfer, and generally conflate representation transfer with policy transfer.The newer ALE’s game modes and difficulty settings create many related environments where negative transfer may be less likely.
  • Off-policy learning: Off-policy learning algorithms can be brittle in the ALE, with reported divergence for methods including GQ(λ) without projection and Q-learning.The article identifies off-policy learning as one of five important research directions that remains open.

8. Conclusion

The article reviews ALE evaluation practices, proposes methodological best practices, introduces an ALE version with stochasticity and multiple game modes, and reports benchmark results for future comparison.

  • Conclusion: The article distinguishes evaluation methodologies that have frequently been conflated in ALE research.Its stated goal is to help clearly distinguish different evaluation protocols.
  • Conclusion: The authors provide benchmark results using methodological best practices as a comparison point for future ALE work.The benchmarks evaluate reinforcement-learning algorithms with linear and nonlinear function approximation.
  • Conclusion: The article highlights five open problems: representation learning, planning and model-learning, exploration, transfer learning, and off-policy learning.These problems are presented after revisiting the challenges posed in the ALE’s original article.
  • Conclusion: The Brute exploits deterministic, episodic ALE dynamics and high-level purpose to achieve competitive performance in several games.Its assumptions include a unique starting state and the idea that purpose matters more than individual actions in most Atari 2600 games.

A.1 Determinism and starting configurations

The appendix formalizes histories and reproducibility in ALE environments, then uses a partial history tree to estimate action values and update them efficiently from episodes.

  • Determinism and starting configurations: A history is a sequence of actions and observations, and histories induce a Markov decision process represented as an infinite history tree.This formulation is useful when the environment is partially observable.
  • Determinism and starting configurations: The Stella emulator is deterministic and episodic, with resets represented as the empty history ϵ.The ALE defines reproducible environments as deterministic, episodic, and having a unique starting configuration.
  • Determinism and starting configurations: Determinism makes one sample per state-action pair sufficient for learning a transition model, while reproducibility enables exact action-sequence experiments from the history-tree root.Reset configurations can otherwise vary because of timer, register, and memory contents, although ALE code avoids these effects.
  • Determinism and starting configurations: For a finite history tree, bottom-up dynamic programming estimates history-action values, and assigning −∞ to unknown pairs defines a lower bound on q∗(h, a).The lower bound is updated by following the most recent episode backward from its terminal node.
  • Determinism and starting configurations: Updating the lower bound along one episode takes O(T) time, while the Brute stores visited histories and maximum-likelihood transition and reward estimates.The lower-bound guarantee is exact only when the subtree rooted at h is fully deterministic.
  • Determinism and starting configurations: The Brute uses an ϵ-greedy policy over the lower-bound action values, decreasing ϵ as a history-tree node receives more visits.This focuses exploration on promising trajectories while retaining random exploration.

Appendix B. Experimental Setup

The experiments use a common evaluation protocol and parameters across the article’s experiments, covering the Brute, Sarsa(λ) + Blob-PROST, and DQN.

  • Experimental Setup: All experiments discussed in the article use the same evaluation protocol and parameters.The setup specifies parameters for the ALE task and for the Brute, Sarsa(λ) + Blob-PROST, and DQN.

B.1 Evaluation Protocol and Arcade Learning Environment Parameters

The evaluation protocol measures robustness across repeated trials under specified stochasticity, episode limits, and algorithm-specific settings. DQN uses original-paper parameters with modified frame skip and exploration, while the Brute uses only γ and ϵ.

  • Evaluation protocol: 24 trials evaluate the Brute and Sarsa(λ) + Blob-PROST, whereas DQN uses 5 trials because GPU-based validation is more expensive.Each trial averages the last 100 episodes that led the agent to termination.
  • ALE parameters: ς is set to 0.0 in Section 5.1.1 and 0.25 elsewhere, with episodes ending after 5 minutes or loss of all lives.Agents receive all 18 primitive ALE actions without game-specific information.
  • Algorithm settings: The Brute uses γ = 1.0 and ϵ = 0.005/log(ni + 2), where ni counts visits to history hi.Spooky Hash8 is used for hashing, and current and previous ALE screens are not averaged.
  • Algorithm settings: DQN retains its original parameters except for frame skip 5 and ϵ = 0.01, and is evaluated continually without game-specific information.The frame-skip setting follows preliminary experiments, while the exploration value reflects the absence of an evaluation phase.

B.4 Parameters used by Sarsa(λ) + Blob-PROST

The Sarsa(λ) + Blob-PROST experiments use fixed learning parameters and a visual feature pipeline with color averaging, spatial grids, blob detection, and NTSC color encoding. Preliminary checks motivate frame skip 5 and color averaging.

  • Parameters: Eligibility traces set any vector value below 0.01 to zero.
  • Representation: Blob-PROST stands for Blob Pairwise Relative Offsets in Space and Time.The representation was originally introduced by Liang et al. (2016).
  • Representation: The screen representation divides rows into 40 tiles of width 4 pixels and columns into 30 tiles of height 7 pixels.Blob detection uses neighborhood size 6, and screens use 128 NTSC colors.
  • Preliminary checks: Color averaging significantly improves results for most games, while frame-skip effects vary across games; the experiments therefore use both color averaging and frame skip 5.These choices were based on preliminary experiments.

Appendix C. Complete Benchmark Results

The appendix reports Sarsa(λ) + Blob-PROST and DQN performance across 60 ALE games under the Appendix B evaluation protocol, alongside game-mode and difficulty coverage. Training games are marked separately in the Sarsa results.

  • Complete benchmark results: Sarsa(λ) + Blob-PROST results are summarized across 60 games under the Appendix B evaluation protocol.Games originally used for training are highlighted with the † symbol.
  • Complete benchmark results: DQN results are summarized across the same 60-game benchmark under the Appendix B evaluation protocol.
  • Game coverage: Table 10 lists each supported Atari 2600 game together with its available modes and difficulties, excluding modes playable only by two players.
Loading 1709.06009v2…