TL;DR
This paper explores how to make reinforcement learning (RL) agents more efficient in complex environments like video games by using relational representations and hierarchical actions. By encoding game states as objects and their relationships, rather than just raw pixels, the agent can learn faster and leverage background knowledge, demonstrating improved performance in the Infinite Mario domain.
What Problem Does This Paper Address?
Traditional reinforcement learning agents often struggle with environments that have enormous state and action spaces, such as video games. These environments are characterized by complex interactions between numerous objects. Directly applying RL to such domains can be computationally infeasible due to the sheer scale of possibilities. The authors aim to bridge this gap by developing methods that allow symbolic agents, like those built with the Soar architecture, to learn effectively by incorporating structural information and hierarchical task decomposition. This approach seeks to make learning tractable by abstracting away from low-level details and focusing on meaningful relationships and actions.
Methods
The core of the paper's approach lies in two key innovations:
- Relational State Representation: Instead of processing the game's visual input as a raw grid of tiles, the agent's state is represented as a collection of objects and their relationships. For instance, a "pit" is not just a tile at a specific coordinate but is described as "a pit at a distance of three tiles in the horizontal direction." This relational encoding allows the agent to leverage background knowledge and more easily reason about the environment.
- Hierarchical Reinforcement Learning (HRL): The authors adopt a hierarchical operator structure inspired by GOMS (Goals, Operators, Methods, Selection rules) analysis. This hierarchy separates high-level "Functional Level Operators" (FLOs) like "tackle monster" or "grab coin" from low-level "Key-stroke Level Operators" (KLOs) like "move right" or "jump." The agent learns to select appropriate FLOs based on the current state and then learns the sequence of KLOs needed to execute that FLO. This decomposition constrains the problem space and speeds up learning.
The agent uses Soar-RL, which integrates reinforcement learning into the Soar cognitive architecture. SARSA is employed for learning value functions and operator preferences.
Datasets
The paper evaluates its approach on the Infinite Mario domain from the RL Competition 2009. This domain is described as having a 16x22 character array representing the visual scene, along with monster locations and velocities. The reward structure varies. The authors compare their agent's performance against a hand-coded sample agent provided with the Mario environment.
Key Insights and Ideas
- Abstraction is Crucial for Complex Domains: Directly learning from raw sensory input in games like Mario is impractical. Relational representations and hierarchical actions provide necessary abstractions that make learning feasible.
- Background Knowledge Enhances Learning: By encoding states as objects and relationships, the agent can easily incorporate domain-specific background knowledge (e.g., "if there is a pit ahead, then jump while moving right"), which significantly aids in planning and decision-making.
- Hierarchies Decompose Complexity: Breaking down tasks into functional and primitive actions allows the agent to learn at different levels of abstraction, leading to faster convergence and more efficient exploration.
- Learned Preferences vs. Hand-Coded Heuristics: The paper highlights that while previous GOMS analyses relied on hand-coded preferences, their RL approach allows the agent to learn these preferences through experience, making it more adaptable.
Key Results
The paper presents a performance graph (Figure 2) showing the Soar-RL agent's reward over episodes compared to a hand-coded sample agent. While specific quantitative metrics like final accuracy or speedup percentages are not explicitly stated in the text, the graph visually suggests that the Soar-RL agent's performance improves significantly over episodes and eventually surpasses the hand-coded agent. The authors note that the agent learns to prioritize actions based on immediate importance, such as dealing with a nearby monster before grabbing a coin.
Limitations and Future Work
- Independent Object Interaction Assumption: The current agent design assumes that interactions with different objects can be handled independently. This breaks down when multiple objects of similar importance are present (e.g., two nearby monsters), and the agent fails to learn effective strategies in such cases.
- Learning New Operators: The authors plan to extend their work by enabling the agent to learn new operators and rules as novel situations arise, rather than relying solely on pre-defined ones. This would allow for more robust adaptation to unforeseen game mechanics or challenges.
Summary updated