Bayesian Learning of Recursively Factored Environments

Marc G. Bellemare, Joel Veness, Michael BowlingICML 2013 · OpenReview

Overview

Scaling model-based reinforcement learning (RL) to high-dimensional observation spaces, such as the pixel outputs of Atari 2600 games, has historically been a significant challenge. This paper introduces a novel method to tackle this by using a class of recursively decomposable factorizations combined with an efficient Bayesian model averaging algorithm. The result is a "meta-algorithm" that automatically discovers the optimal way to represent complex environments without the need for manual structural tuning.

The Curse of Dimensionality in Model-Based RL

Model-based RL is highly effective because it enables agents to "plan" by simulating future states. However, it frequently falls victim to the "curse of dimensionality." In environments with large observation spaces—such as a 160x210 pixel game screen—learning a full joint probability distribution of all pixels is computationally intractable.

A common workaround is to "factor" the environment, breaking the massive observation space into smaller, independent sub-problems. The primary challenge here is that there are countless ways to factor a space, and the "best" factorization is highly environment-dependent. Choosing an incorrect factorization leads to poor predictions. This paper addresses the critical need for an automated, efficient method to select or combine these factorizations dynamically.

Core Methodology

The authors propose a framework built on four main components:

  1. Recursively Decomposable Factorizations: The observation space (e.g., an image) is recursively split into smaller pieces. For instance, a screen can be divided into four quadrants, and each quadrant can be subdivided again, forming a hierarchical tree structure.
  2. Bayesian Model Averaging (BMA): Rather than selecting a single "best" split, the algorithm maintains a mixture of all possible recursive factorizations. It assigns a prior probability to each structure, naturally favoring simpler ones to prevent overfitting.
  3. The Efficiency Identity: The mathematical breakthrough of the paper is an identity that allows the exact Bayesian average over a super-exponential number of possible factorizations to be computed in linear time. This dynamic programming approach is conceptually similar to the Context Tree Weighting (CTW) algorithm used in data compression.
  4. Quad-Tree Factorization (QTF): The theory is instantiated for 2D images by recursively splitting the Atari screen into quadrants.
Quad-Tree Factorization on Space Invaders

To predict pixel colors based on surrounding context and previous frames, the authors use Context Tree Switching (CTS) as the base model for each individual patch.

Experimental Setup

The researchers evaluated their approach using the Arcade Learning Environment (ALE), a standard benchmark of Atari 2600 games.

  • Training Set: 5 games were used for hyperparameter optimization.
  • Testing Set: 15 games served as a hold-out set for final evaluation.
  • Input: 160x210 pixel screens with 128 possible colors.

Key Insights

  • Scaffolding for Complexity: The authors argue that many high-dimensional environments possess "fundamentally simple dynamics." The objective is not to invent a completely new learning algorithm, but to provide the "algorithmic scaffolding" that allows existing algorithms to scale effectively.
  • No Manual Tuning Required: By averaging over many factorizations, the algorithm seamlessly adapts to different games. In a game with large moving objects (like Space Invaders), it can rely on larger factors; in games with intricate details, it can focus on smaller, localized factors.
  • Asymptotic Guarantees: The mixture model is mathematically proven to be "asymptotically competitive" with the single best factorization in its class, meaning there is little penalty for maintaining a broad mixture initially.

Results and Performance

The authors compared their QTF model against models with fixed patch sizes (e.g., strictly using 4x4 or 32x32 blocks).

  • Predictive Accuracy: QTF achieved performance that was close to or better than the best-tuned fixed-size model in 13 out of 20 games.
  • Logarithmic Loss: Measured in "bits per frame" (indicating how surprised the model is by new data), QTF significantly outperformed all fixed-size models across the board. For example, in Pong and Freeway, QTF saved about 3 bits per frame compared to the best fixed-size alternative.
Logarithmic Loss Comparison
  • Efficiency: Crucially, the model processed frames and made predictions in real-time (60 frames per second), proving that exact Bayesian inference is practically viable for large-scale RL tasks.

Limitations and Future Directions

While highly effective, the approach has limitations. The base model (CTS) treats pixel values as atomic symbols. Consequently, if a single pixel changes due to noise or a minor graphical glitch, the model interprets it as a completely new "symbol," which can hinder generalization in noisy environments.

Future work could replace the simple CTS base models with more sophisticated alternatives, such as locally linear models or neural networks, to further enhance performance. Additionally, while this paper focuses on learning the model, the natural next step is integrating these factored models into search algorithms (like Monte Carlo Tree Search) to develop superior game-playing agents.

Summary updated

Abstract

Model-based reinforcement learning techniques have historically encountered a number of difficulties scaling up to large observation spaces. One promising approach has been to decompose the model l...
BibTeX
@inproceedings{bellemare2013bayesian,
  author = {Marc G. Bellemare and Joel Veness and Michael Bowling},
  title = {{Bayesian Learning of Recursively Factored Environments}},
  booktitle = {International Conference on Machine Learning},
  year = {2013},
  url = {https://openreview.net/forum?id=SJ-Ucsb_ZS},
}
Figure