Abstract
This paper introduces a method for agents to learn deterministic action models online by remembering past experiences and applying them to new situations through analogical reasoning. By representing the world via relationships between objects rather than specific coordinates or identities, the agent can generalize from a single experience to predict outcomes in entirely unseen states. This approach significantly accelerates reinforcement learning by enabling "zero-shot" generalization in structurally similar environments.
Introduction
In traditional reinforcement learning (RL), agents often learn about the world one state-action pair at a time. This lack of generalization means a robot might learn that driving off one specific table is dangerous but fail to apply that knowledge to a different table. The authors address this by creating an agent that is online, incremental, and relational. By focusing on object relationships (e.g., on(BlockA, BlockB)), the agent can predict action outcomes in new states by comparing them to similar past experiences.
Methodology
The proposed algorithm is implemented within the Soar cognitive architecture, leveraging its episodic and procedural memory modules. When an agent needs to predict the outcome of an action in a "target" state, it follows a four-step process:
- Retrieval: The agent searches episodic memory for a similar past "source" transition using a proximity heuristic that focuses on relations connected to the action parameters.
- Finding Changes: It identifies the differences between the "before" and "after" states of the retrieved memory.
- Feature Mapping: Based on Structure Mapping Theory, the agent maps objects from the past memory to the current situation based on their relational roles.
- Mapping Changes: The mapped changes are applied to the current state to generate a prediction.
Experimental Evaluation
The approach was evaluated in two simulated environments:
- Breaking Blocks World: A high-stakes environment where picking a block from the middle of a stack causes others to break. This tests the ability to learn complex, transitive consequences.
- Taxi Domain: A standard benchmark where navigation rules change based on whether a passenger is inside or outside the vehicle.
Key Results
The instance-based approach demonstrated a significant advantage over non-generalizing methods. In the Breaking Blocks World, the agent achieved 88% prediction accuracy after only 32 experiences. Furthermore, when integrated with a Dyna-Q reinforcement learning agent, the model allowed the agent to converge to an optimal policy an order of magnitude faster than Real-Time Dynamic Programming (RTDP).
Conclusion and Future Work
By using specific instances as templates for analogy, the agent achieves robust generalization without the need for large batches of data or rigid pre-defined rules. While the current model relies on a proximity heuristic—assuming action effects are local—future work aims to allow agents to learn which features are relevant through experimentation and to integrate background knowledge to further refine the reasoning process.
Summary updated