Classical Planning with Simulators: Results on the Atari Video Games

Nir Lipovetzky, Miquel Ramírez, Hector GeffnerIJCAI 2015

Abstract

This paper demonstrates that Iterated Width (IW), a simple "blind" search algorithm from classical planning, can perform as well as or better than state-of-the-art methods like UCT (Monte Carlo Tree Search) on Atari 2600 games. By utilizing a novelty-based pruning mechanism applied to the game's RAM state, the authors show that effective exploration in complex, deterministic environments can be achieved without complex heuristics or deep reinforcement learning.

Introduction

The Arcade Learning Environment (ALE) serves as a rigorous benchmark for AI, featuring hundreds of Atari 2600 games. While these games are deterministic, they present a significant challenge for classical planning because they function as "black boxes." Simulators return new states and rewards based on actions, but lack explicit goal descriptions or compact models (e.g., PDDL). Standard search algorithms like Breadth-First Search (BFS) are typically overwhelmed by the astronomical state space. This work explores whether domain-independent planning techniques can navigate these environments effectively without prior knowledge of game logic.

Methods

The authors adapt Iterated Width (IW) for online planning. IW consists of a sequence of breadth-first searches, $IW(1), IW(2), \dots, IW(k)$, governed by a novelty test. A state is deemed "novel" if it is the first in the current search to make a specific tuple of atoms true.

  • State Representation: The 128-byte RAM of the Atari console is used as the state representation. Each byte acts as a variable with 256 possible values.
  • Novelty Pruning: In $IW(1)$, a state is preserved only if it is the first to assign a specific value to a specific RAM byte. This aggressively prunes the search tree.
  • 2BFS (Best-First Search with Two Queues): A variant designed to balance exploration and exploitation by maintaining two priority queues: one ordered by novelty and the other by accumulated reward.
  • Online Planning: The algorithms perform a lookahead search from the current state to select the immediate next action, repeating this process throughout the game.

Results

The performance of IW was evaluated across 54 Atari 2600 games within the ALE, comparing it against Breadth-First Search (BrFS) and UCT.

Performance comparison of IW(1), 2BFS, BrFS, and UCT across 54 Atari games.

As shown in the table above, IW(1) outscored UCT in 31 out of 54 games. Furthermore, IW(1) was identified as the best-performing algorithm in 26 games, compared to 19 for UCT and 13 for 2BFS.

Key Insights

  • Novelty as a Proxy for Progress: Tracking changes in RAM bytes effectively prevents the agent from becoming trapped in redundant state cycles, forcing exploration of new configurations.
  • Computational Efficiency: Due to its aggressive pruning, $IW(1)$ often operated 10 times faster per lookahead than 2BFS or UCT, frequently concluding its search before exhausting its frame budget.
  • Robustness to Sparse Rewards: Unlike UCT, which relies on reward signals, IW's novelty-driven approach allows it to navigate "reward deserts." For instance, in Freeway, IW successfully crosses the road while UCT fails to find the initial reward.

Discussion and Limitations

While $IW(1)$ is highly efficient, scaling to $IW(2)$ is currently computationally prohibitive for real-time play due to the quadratic growth of the state space for byte pairs. Additionally, the planners do not inherently account for "lives" unless they impact the score; the authors found that manually penalizing life loss improved performance in games like Breakout.

Future research may involve integrating novelty-based exploration with learning components (e.g., neural networks) or extracting features directly from screen pixels to remove the dependency on RAM state.

Summary updated

BibTeX
@inproceedings{lipovetzky2015classical,
  author = {Nir Lipovetzky and Miquel Ramírez and Hector Geffner},
  title = {{Classical Planning with Simulators: Results on the Atari Video Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure