Introduction
A fundamental challenge in robotics and artificial intelligence is the transition from high-dimensional sensory input (pixels) to high-level symbolic understanding. For an agent to plan complex tasks, such as navigating a house or solving a puzzle, it must operate on abstractions like "at home" or "door open" rather than raw motor commands. Traditionally, these symbolic representations were hand-coded by engineers. This paper, presented at NIPS 2017, proposes an autonomous framework for Online Active Symbol Acquisition, where an agent learns these abstractions by intelligently exploring its environment to reduce model uncertainty.
Methodology
The authors introduce a two-part framework that combines Bayesian model learning with active exploration strategies.
1. Fast Bayesian Model Construction
As the agent interacts with the world, it clusters observations into "factors" (variables that change together) and "symbols" (abstract states). Using Bayesian Hierarchical Clustering, the agent groups high-level skills, or "options," that produce similar effects.
As shown in the figure above, symbols are defined geometrically by their preconditions ($Pre(o)$) and the resulting state distributions ($Im(o, Z)$). This creates a probabilistic model that quantifies what the agent understands about its environment and where its knowledge is lacking.
2. Optimal Exploration via MCTS
Instead of wandering aimlessly, the agent treats "reducing model uncertainty" as its primary objective. It measures uncertainty using the Kullback-Leibler (KL) divergence between its current model and potential future models. To navigate toward informative states, the agent employs Monte-Carlo Tree Search (MCTS) to simulate action sequences, selecting paths that maximize expected information gain.
A key component is the "R-max style" bonus: when the agent's internal simulations encounter a transition it has never seen, it assigns a massive reward, incentivizing the agent to explore the "edges" of its current map.
Experimental Evaluation
The algorithm was tested in two simulated environments:
- Asteroids Domain: A physics-heavy environment requiring precise movement between asteroid faces.
- Treasure Game: A logical puzzle involving keys and locked doors that must be navigated in a specific sequence.
Key Results
The active exploration strategy (MCTS) was compared against random and greedy baselines.
- Superior Coverage: In the Asteroids domain, the active agent consistently reached distant targets that required complex flight sequences.
- Puzzle Solving: In the Treasure Game, the active agent successfully obtained keys and treasures far more frequently than baselines, which often became trapped in early regions of the map.
- Data Efficiency: Quantitatively, the active algorithm reached target levels of model certainty using 2 to 3 times fewer actions than random or greedy policies.
Discussion and Future Work
The research demonstrates that intermediate, even imperfect, symbolic models are powerful tools for guiding exploration. By identifying factors—variables that change together—the agent effectively reduces the dimensionality of the learning problem.
However, limitations remain. The current method assumes "subgoal options" (actions with outcomes relatively independent of the starting state) and requires pre-defined low-level variables like coordinates. Future work aims to scale this approach to raw, unstructured sensory data like video frames and to reduce the computational overhead associated with frequent MCTS updates.
Summary updated