Information-based learning by agents in unbounded state spaces

Shariq A. Mobin, James A. Arnemann, Fritz SommerNeurIPS 2014

Introduction

In traditional reinforcement learning (RL), agents typically operate within a "bounded" box—a grid or a game where every possible state is known from the start. However, real-world biological agents and future autonomous robots face "unbounded" environments. They do not know how many rooms are in a building or how many configurations a forest might have until they actively explore them.

This presents a two-fold challenge:

  1. Model Representation: How do you build a mathematical model of a world when you don't know its dimensions?
  2. Exploration Strategy: How do you decide where to go when "the unknown" is everywhere?

Previous information-driven models worked well for small, finite spaces but broke down when the state space was infinite or its size was unknown. Researchers have developed a new framework for autonomous agents to explore and learn models of these unbounded environments. By combining the Chinese Restaurant Process (CRP) with Predicted Information Gain (PIG), their "Empirical Bayes" agent can efficiently map out complex worlds and harvest rewards without needing any prior knowledge about the size or boundaries of its environment.

Methods

The authors introduce a framework based on Controlled Markov Chains (CMC)—essentially a world model where the agent’s goal isn't just to get a "reward," but to learn the transition probabilities of the environment as accurately as possible.

Key components include:

  • The Chinese Restaurant Process (CRP): A non-parametric Bayesian model used to handle state discovery. In this analogy, a "customer" (an observation) either sits at an existing "table" (revisits a known state) or starts a new one (discovers a new state). This allows the model to grow dynamically as the agent explores.
  • Empirical Bayes (EB-CRP): Instead of manually tuning the "discovery rate" parameter, the agent uses Maximum Likelihood Estimation to learn how likely it is to find new states based on its history.
  • Padding Procedure: To compare a small internal model (few states) with a larger true world (many states), the authors developed a "padding" method. It treats undiscovered states as a uniform "probability mass," allowing the use of KL-Divergence to measure how much the agent still needs to learn.
Padding Procedure
  • Value Iteration for Planning: The agent doesn't just move greedily toward the nearest unknown. It uses Bellman equations to plan paths toward areas with the highest Predicted Information Gain (PIG) over a long time horizon.

Experimental Setup

The model was evaluated on three simulated benchmarks:

  1. Bounded Maze: A 36-room grid with "transporters" that trap the agent in an absorbing state, testing its ability to avoid pitfalls while learning.
  2. The "Chain" Environment: A classic 5-state benchmark used to measure how quickly an exploration strategy leads to optimal reward harvesting.
  3. Unbounded Maze: A newly defined infinite grid with multiple absorbing states, specifically designed to test exploration in a world with no boundaries.

Key Insights and Results

  • Information as Reward: The paper reinforces the idea that "learning progress" (information gain) is a powerful intrinsic reward. An agent that seeks to minimize its own "Missing Information" naturally discovers the most efficient way to navigate a world.
  • Non-Greedy Exploration is Essential: In environments with "gravity wells" or traps, a greedy agent gets stuck. By using value iteration to look 10 steps ahead, the PIG agent learns to navigate around dangers to reach high-information areas.
  • Parameter-Free Discovery: The Empirical Bayes approach (EB-CRP) is a "set it and forget it" solution. It performs better than models with fixed discovery rates because it adapts to the actual complexity of the environment it encounters.
Missing Information over Time
  • Matching the "Oracle": In bounded environments, the EB-CRP agent performed almost as well as agents that were told the exact size of the state space beforehand.
  • Outperforming Baselines: On the "Chain" benchmark, the EB-CRP-PIG-R agent achieved a cumulative reward of 3182 ± 25, significantly outperforming established algorithms like BOSS (3003) and nearly reaching the theoretical optimal (3658).
  • Superior Coverage: In the unbounded maze, the EB-CRP agent explored a much larger area and gathered more reward than the "Least Taken Action" (LTA) heuristic, which tended to get stuck in local loops near its starting point.

Limitations and Future Work

  • Computational Complexity: While the CRP model is simple, the Value Iteration step becomes computationally expensive as the number of discovered states grows. Future versions might only calculate values for states reachable within a specific time horizon.
  • Discrete vs. Continuous: This model currently only works for discrete state spaces (e.g., distinct rooms or grid cells). Real-world robotics often requires continuous state spaces.
  • Partial Observability: The paper assumes the agent always knows exactly which state it is in. Extending this to Partially Observable MDPs (POMDPs)—where the agent might be uncertain of its location—is a cited next step for neuroscience applications.

Summary updated

BibTeX
@inproceedings{mobin2014information,
  author = {Shariq A. Mobin and James A. Arnemann and Fritz Sommer},
  title = {{Information-based learning by agents in unbounded state spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure