Active Exploration for Learning Symbolic Representations

Garrett Andersen, George Konidaris

Introduction

In artificial intelligence and robotics, planning is significantly more efficient when executed using high-level "symbols" (e.g., "I am in front of the door") rather than raw, high-dimensional sensor data like pixel grids. Traditionally, these symbolic abstractions are hand-coded by humans, a brittle approach that struggles to scale.

While recent research demonstrates that agents can learn these symbols by observing the effects of their high-level skills (known as "options"), relying on random exploration to do so is incredibly slow. In complex environments, an agent might spend an eternity bumping into walls without ever discovering the "key" needed to unlock a "door." This paper tackles this data-efficiency gap, introducing an online algorithm that allows an agent to autonomously and rapidly learn a complete symbolic model of its environment through "active exploration."

Online Active Symbol Acquisition

The authors propose a two-part framework that combines fast model-building with targeted exploration:

1. Fast Bayesian Model Construction

As the agent navigates its environment, it collects transition data. The algorithm first identifies "factors"—groups of variables that change together, such as $x$ and $y$ coordinates. It then clusters these observations to create discrete symbols. Finally, it employs Bayesian Hierarchical Clustering to group states where a specific action yields similar effects. This generates a probabilistic "map" detailing what actions do and the specific preconditions required to perform them.

Illustration of symbolic transitions, showing how the preconditions and effects of options map between different state space regions.

2. Optimal Exploration via MCTS

Rather than acting randomly, the agent leverages its current, uncertain model to plan its next moves. It uses Monte-Carlo Tree Search (MCTS) to simulate potential future paths. Crucially, the "reward" in this search is not a standard game score, but the expected reduction in model uncertainty, measured using KL divergence. If the agent encounters a previously unseen transition, it receives a "novelty bonus," actively encouraging it to push into unknown regions of the state space.

Experimental Setup

The algorithm was evaluated on two simulated domains designed to test different dimensions of complexity:

  • The Asteroids Domain: A physics-based environment with complex continuous dynamics but a relatively simple logical structure (35 symbols representing asteroid faces).
  • The Treasure Game: A 2D video game environment with simpler dynamics but a highly complex logical structure involving keys, locks, handles, and treasure. Success requires a highly specific sequence of actions, rendering random exploration highly ineffective.

Key Insights and Results

By treating the symbolic model as a Bayesian distribution, the authors mathematically define "what the agent doesn't know." Using the standard deviation of this distribution as a target for MCTS allows for highly purposeful discovery.

When compared against random and greedy (visiting the least-executed option) policies, the active exploration approach demonstrated significant advantages:

  • Proportional Exploration: In the Asteroids domain, the active agent distributed its time proportionally across all asteroids, whereas baseline agents frequently got "stuck" near their starting locations.
  • Faster Discovery: In the Treasure Game, the active agent successfully obtained the key and treasure significantly more often. Baseline policies often failed to find the treasure even after 2,000 option executions.
  • 2-3x Efficiency Gain: Across both domains, greedy and random policies required 2 to 3 times as many actions to achieve the same level of model completeness (measured by unobserved symbolic transitions) as the active exploration algorithm.

Limitations and Future Work

While highly effective, the current framework has notable limitations. First, the agent is provided with pre-defined high-level skills (options) at the start; a truly autonomous agent would need to learn these skills and symbols simultaneously. Second, running MCTS and updating Bayesian models after every action introduces significant computational overhead compared to simpler reinforcement learning methods.

Finally, the method relies on a "subgoal assumption"—the idea that an action's outcome is mostly independent of its starting state. While this reflects many high-level human skills, more complex partitioning of options will be necessary for environments where this assumption does not hold. Future work may also explore injecting "common sense" into the agent via informative Bayesian priors to further accelerate performance.

Summary updated

Abstract

We introduce an online active exploration algorithm for data-efficiently learning an abstract symbolic model of an environment. Our algorithm is divided into two parts: the first part quickly generates an intermediate Bayesian symbolic model from the data that the agent has collected so far, which the agent can then use along with the second part to guide its future exploration towards regions of the state space that the model is uncertain about. We show that our algorithm outperforms random and greedy exploration policies on two different computer game domains. The first domain is an Asteroids-inspired game with complex dynamics but basic logical structure. The second is the Treasure Game, with simpler dynamics but more complex logical structure.
BibTeX
@inproceedings{andersen2017active,
  author = {Garrett Andersen and George Konidaris},
  title = {{Active Exploration for Learning Symbolic Representations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=SJ-EQwWdZr},
}
Figure