Blind Search for Atari-Like Online Planning Revisited

Alexander Shleyfman, Alexander Tuisov, Carmel DomshlakIJCAI 2016

Abstract

This paper presents significant enhancements to the Iterated Width (IW) algorithm, a "blind" search technique for online planning in the Arcade Learning Environment (ALE). By introducing reward-based prioritization (p-IW) and a "racing" mechanism, the authors address the "tunnel vision" limitations of standard IW(1). Experimental results across 53 Atari games demonstrate that p-IW(1) significantly outperforms standard IW(1) and established baselines like UCT, particularly in scenarios with limited computational budgets and sparse rewards.

Introduction

The Arcade Learning Environment (ALE) provides a challenging testbed for online planning. While Atari 2600 games are deterministic, their internal logic is hidden within a "black box" simulator, necessitating "blind" search strategies that do not rely on domain-specific heuristics. Traditional Breadth-First Search (BrFS) is often computationally infeasible due to the vast state space. The Iterated Width algorithm, specifically IW(1), mitigates this by pruning states that do not introduce novel features (e.g., specific RAM byte values). However, IW(1) often suffers from a "tunnel vision" effect, where it aggressively pursues a single narrow path of novelty while ignoring high-reward alternatives.

Methods

The authors propose two primary modifications to the IW algorithm:

  1. Prioritized Iterated Width (p-IW): This approach introduces reward-based tie-breaking and state reopening. In p-IW, if multiple states share the same depth in the search queue, the one with the highest accumulated reward is expanded first. Furthermore, a state is only considered "seen" (and thus pruned) if it was reached with a reward equal to or greater than the current path. This allows the search to "reopen" and improve upon known feature sets if a higher-scoring path is discovered.
  2. Racing Blind Search: This mechanism treats action selection as a multi-armed bandit problem. Instead of a single search tree, the computational budget is distributed across available actions in a round-robin "race." This ensures a more balanced exploration of the immediate action space and prevents the planner from wasting its entire budget on a single deep, but potentially suboptimal, sub-tree.

Key Results

The proposed p-IW(1) algorithm was evaluated against standard IW(1), UCT (a Monte-Carlo Tree Search variant), and 2BFS across 53 Atari games. As shown in Figure 2, p-IW(1) achieved the best performance in 37 out of 53 games, significantly outperforming UCT and standard IW(1).

Comparison of p-IW(1) against standard IW(1), 2BFS, UCT, and BrFS across 53 Atari games.

Further analysis of computational budgets reveals that p-IW(1) is remarkably robust. Even with a reduced budget of 10,000 frames, p-IW(1) maintained superior performance in 38 games compared to standard IW(1). Interestingly, standard IW(1) often regressed when given more time (150,000 frames) in 13 games, likely due to getting lost in deeper, non-rewarding branches. Notably, the racing variant (R. p-IW) proved effective in challenging environments, being the only algorithm to score points in the notoriously difficult Montezuma’s Revenge.

Performance comparison of p-IW(1), IW(1), and Racing p-IW(1) under different computational budgets (150K and 10K frames).

Conclusion

By integrating reward signals into the novelty-based pruning of IW, p-IW(1) effectively balances exploration and exploitation in blind search. The racing mechanism further stabilizes performance by ensuring a fair allocation of search resources across immediate actions. Future work will explore local versus global pruning strategies and more sophisticated bandit algorithms to further refine budget allocation in reward-dense environments.

Summary updated

BibTeX
@inproceedings{shleyfman2016blind,
  author = {Alexander Shleyfman and Alexander Tuisov and Carmel Domshlak},
  title = {{Blind Search for Atari-Like Online Planning Revisited}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure