PaperlayerView exact revision on arXiv

Source-linked AI summary

State of the Art Control of Atari Games Using Shallow Reinforcement Learning

Yitao Liang, Marlos C. Machado, Erik Talvitie, Michael Bowling

arXiv:1512.01563v2cs.LG

TL;DR

DQN’s ALE success raises questions about which learned representations matter and how reliably its results can be interpreted. This paper builds simple linear representations around DQN-inspired biases and finds that Blob-PROST is competitive with DQN while offering a practical benchmark and alternative when representation learning is not the focus.

  • Problem

    The paper asks which representational biases underlie DQN’s ALE performance and addresses methodological concerns that make its results difficult to interpret.

  • Method

    The authors progressively augment simple linear features with relative spatial relationships, non-Markov information, and improved object detection.

  • Results

    Blob-PROST is competitive with DQN in the ALE, while progressive additions produce dramatic improvements over simpler representations.

  • Takeaways & Limitations

    The results suggest that general representation properties may matter more than DQN’s specific learned features and support Blob-PROST as a practical ALE benchmark.

  • Takeaways & Limitations

    A principled Blob-PROST–DQN comparison is essentially impossible because DQN has only one reported trial per game and is prohibitively expensive to reevaluate.

Abstract

from arXiv · show

The recently introduced Deep Q-Networks (DQN) algorithm has gained attention as one of the first successful combinations of deep neural networks and reinforcement learning. Its promise was demonstrated in the Arcade Learning Environment (ALE), a challenging framework composed of dozens of Atari 2600 games used to evaluate general competency in AI. It achieved dramatically better results than earlier approaches, showing that its ability to learn good representations is quite robust and general. This paper attempts to understand the principles that underlie DQN's impressive performance and to better contextualize its success. We systematically evaluate the importance of key representational biases encoded by DQN's network by proposing simple linear representations that make use of these concepts. Incorporating these characteristics, we obtain a computationally practical feature set that achieves competitive performance to DQN in the ALE. Besides offering insight into the strengths and weaknesses of DQN, we provide a generic representation for the ALE, significantly reducing the burden of learning a representation for each game. Moreover, we also provide a simple, reproducible benchmark for the sake of comparison to future work in the ALE.

1. INTRODUCTION

The paper investigates why DQN succeeds in the diverse ALE and whether its key representational biases can be captured by simple linear features. It progressively incorporates these biases to produce a generic, practical representation competitive with DQN.

  • 1. INTRODUCTION: The ALE contains diverse Atari games and therefore tests robustness and generality across visually varied decision-making problems.Its human-designed games also encode biases relevant to navigating visual environments.
  • 1. INTRODUCTION: DQN’s reported ALE results are difficult to interpret because they use game-specific prior information, one trial per game, and unequal training-data baselines.These choices impair reproducibility and principled cost-benefit comparisons.
  • 1. INTRODUCTION: The paper targets uncertainty about which DQN properties drive its ALE success, beyond game-specific tailored representations.It focuses on spatial invariance, short-range temporal information, and detection of small pixel patterns.
  • 1. INTRODUCTION: The study progressively augments a simple linear representation with DQN-inspired biases to isolate their contributions.The resulting feature set is fixed, generic, and computationally practical.
  • 1. INTRODUCTION: The resulting representation achieves performance competitive to DQN while reducing the need to learn a separate representation for each game.It is also intended as a simpler benchmark and platform for future ALE research.

2. BACKGROUND

The background formalizes reinforcement learning and value-function approximation, then situates ALE research from generic linear features to DQN’s convolutional representation. DQN processes recent image frames to capture spatial patterns and movement.

  • 2. BACKGROUND: In reinforcement learning, an agent interacts with an environment and learns a policy that maximizes reward under an MDP.The MDP specifies states, actions, rewards, transitions, and a discount factor.
  • 2. BACKGROUND: Approximate value functions replace infeasible state-action tables, using either linear features or nonlinear function approximators such as neural networks.Linear approximation represents Qπ(s, a; θ) as θ⊤φ(s, a).
  • 2. BACKGROUND: Sarsa(λ) updates an approximate action-value function with eligibility traces while improving the policy, and is described as more stable than off-policy alternatives in linear ALE settings.The cited practice specifically reports lower divergence risk than Q-learning and other off-policy methods.
  • 2. BACKGROUND: ALE agents receive 160×210 pixel screens and 18 joystick actions, while recent screens are needed because one screen usually is not Markovian.Atari games are deterministic, so the full interaction history determines future screens.
  • 2. BACKGROUND: Earlier ALE work developed generic linear representations such as Basic, BASS, DISCO, LSH, and contingency-awareness features.These methods respectively encode tiled colors, feature combinations, object information, hashing, or controllable screen regions.
  • 2. BACKGROUND: DQN uses a deep convolutional network for Q and four recent images, enabling learned spatial filters and temporal relationships such as movement.These properties motivate the paper’s temporal features and improved object detection.

3. SPATIAL INVARIANCE

This section introduces B-PROS, which removes dependence on absolute object positions by encoding pairwise relative offsets. Across ALE comparisons, B-PROS substantially improves on earlier linear representations, including with less training data than CAF.

  • 3. SPATIAL INVARIANCE: B-PROS encodes whether two colors occur at a specified relative tile offset, making pairwise spatial relationships invariant to absolute position.Its complete feature set contains 6,885,440 features after removing redundancies.
  • 3.1 Empirical Evaluation: B-PROS surpasses the original linear benchmarks by a large margin and exceeds CAF in all but one game despite being simpler and trained with half as much data.In Pong, it wins 20-15 on average, whereas previous methods rarely scored more than a few points.
  • 3.1 Empirical Evaluation: 77% (41/53) of games show higher average B-PROS performance than Basic, BASS, DISCO, and LSH, while 77% (38/49) exceed CAF with less training data.The experiments used 24 independent trials, 5000 training episodes, and frozen-policy evaluation over 499 episodes; CAF used 10,000 episodes.
  • 3.1 Empirical Evaluation: The results indicate that emphasizing relative spatial relationships rather than absolute positions is important for ALE performance.B-PROS’s advantage is attributed to the nonlinearity applied to pairwise spatial information.

4. NON-MARKOVIAN FEATURES

The paper extends relative-offset features with temporal information to capture movement, then finds that non-Markovian features substantially improve performance across Atari games.

  • 4. NON-MARKOVIAN FEATURES: B-PROS cannot encode movement, whereas B-PROST addresses this limitation by using information from multiple recent screens.Movement can determine whether objects such as a Pong ball are approaching or receding from the paddle.
  • 4. NON-MARKOVIAN FEATURES: B-PROST adds temporal pairwise offsets between features from the current screen and a screen five frames earlier, complementing spatial relative-position features.It contains Basic, B-PROS, and B-PROT features, totaling 20,598,848 sparse binary features.
  • 4.1 Empirical Evaluation: The evaluation trains each agent for 200,000,000 frames across 24 independent trials and averages performance over 499 no-learning episodes.Episodes begin with randomized no-op actions, and agents use only actions with unique effects in each game.
  • 4.1 Empirical Evaluation: B-PROST outperforms B-PROS in 40 of 49 games, with especially large gains in Pong and robustness to randomized initial conditions in Enduro.The average score using B-PROST is higher in 82% of evaluated games.

5. OBJECT DETECTION

The paper replaces pixel-based primitives with color-contiguous blobs to improve object detection, producing Blob-PROST and measuring its benefits and trade-offs.

  • 5. OBJECT DETECTION: The blob-contiguity tolerance s trades off fewer, easier-to-compute blobs against the risk of grouping separate objects, and the experiments fix s=6 after an informal search.The authors state that more systematic selection of s could produce better results.
  • 5. OBJECT DETECTION: Blob features detect contiguous same-color regions and represent their coarse screen positions instead of encoding individual pixel positions.Blob positions are defined by the centroids of their smallest bounding boxes, using 4×7-pixel tiles and 128 colors.
  • 5. OBJECT DETECTION: Blob-PROST contains 114,702,400 possible features, but blob sparsity means most are never generated.The representation includes 153,600 Blob features, 38,182,976 Blob-PROS features, and 76,365,824 Blob-PROT features.
  • 5.1 Empirical Evaluation: Blob-PROST outperforms both B-PROS and B-PROST in all but one training game, with significant gains over B-PROST in 6 of 9 games.Across 49 games, Blob-PROST exceeds B-PROST significantly in 23 games and has higher average performance than both baselines in 29 games.
  • 5.1 Empirical Evaluation: Blob detection improves the meaningfulness of feature inputs, but grouping pixels by contiguity can incorrectly merge distinct objects.Asterix is reported as a failure case where harmful grouping may explain poor performance.

6. COMPARISON WITH DQN

The comparison argues that Blob-PROST’s structural representation approaches DQN-level performance while exposing weaknesses in DQN’s evaluation methodology and offering substantially lower computational cost.

  • 6.1 DQN Evaluation Methodology: DQN’s evaluation selected the best weights from one training run, used 30 evaluation episodes, and incorporated game-specific action and termination choices.The authors adopted some comparable procedures but omitted DQN’s life-counter termination mechanism.
  • 6.2.1 Computational Cost: Blob-PROST ran at 56–300 decisions per second with game-dependent memory use, whereas DQN ran at approximately 5 decisions per second and required approximately 9.8GB of memory.The reported DQN speed was about 20 frames per second, while Blob-PROST ranged from 280–1500 frames per second.
  • 6.1 DQN Evaluation Methodology: The authors argue that DQN comparisons are not statistically principled because each game has only one DQN trial and independently reevaluating DQN is prohibitively expensive.They therefore use ad hoc comparisons to form an intuitive picture of relative capabilities.
  • 6.2.2 ALE Performance: Blob-PROST reached at least 75% of human performance in 34/49 games in its best trial, compared with DQN’s 29/49.Its middle trial reached the threshold in 20/49 games.

7. ALE BENCHMARK

The paper proposes a more reproducible ALE benchmark that uses multiple trials, final learned weights, no game-specific prior knowledge, and the full action set for future comparisons.

  • 7. ALE Benchmark: The benchmark is designed to avoid DQN’s methodological flaws by reporting more than one trial, evaluating final weights, and eschewing game-specific prior knowledge.The authors present this benchmark to support principled comparison in the ALE.
  • 7. ALE Benchmark: Using the full action set, Blob-PROST’s average performance after 24 trials is reported as the recommended benchmark for future comparisons.The authors unexpectedly found slightly better comparisons with DQN using the full action set than using the minimal action set.

8. CONCLUSIONS AND FUTURE WORK

Blob-PROST achieves ALE performance competitive with DQN, while exposing representational principles behind that result and offering a lighter-weight alternative for benchmarking and future agents.

  • Blob-PROST is competitive with DQN in the ALE, although it is likely slightly worse overall.
  • Progressively adding relative distances, non-Markov features, and sophisticated object detection produced dramatic performance improvements.
  • The results suggest DQN’s general representational properties may matter more in the ALE than the specific features learned for each game.
  • Blob-PROST is proposed as a strong alternative ALE benchmark and platform when representation learning is not the research focus.
  • DQN and Blob-PROST show complementary strengths across game types, motivating further study of velocity encoding, holistic screen views, sparse rewards, and life-loss handling.
  • Adaptive representation methods could use these biases to learn useful features quickly before focusing on exceptions.

APPENDIX

The appendix collects complete comparisons for the proposed linear feature sets, prior linear representations, and Blob-PROST versus DQN, with stated evaluation protocols and statistical conventions.

  • Table 3 reports linear-function-approximation control performance, with first-five-column results using all 18 actions after 5,000 training and 500 evaluation episodes.
  • B-PROS outperforms CAF in the majority of games despite using half as many samples, although the reported results are not directly comparable.
  • Table 4 compares B-PROS, B-PROST, Blob-PROST, and full-action Blob-PROST across 24 independent learning trials.
  • Table 5 reports Blob-PROST’s comparison with DQN using 24 trials, evaluation variability, and Welch’s tests with p<0.025.
Loading 1512.01563v2…