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.
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