Abstract
This paper introduces a novel Reinforcement Learning (RL) algorithm designed to automatically discover hidden, time-delayed causal relationships in partially observable environments. By incrementally adding "memory units" that track pertinent past events—validated through the principle of independence between cause and mechanism—the approach significantly improves data efficiency and model interpretability compared to standard black-box recurrent networks like LSTMs.
Introduction
Most Reinforcement Learning algorithms struggle with Partial Observability, where an action performed now (such as unlocking a door) may only manifest its effect much later. Standard Markovian models fail in these scenarios because they rely solely on the immediate previous state. While researchers often employ Recurrent Neural Networks (RNNs) like LSTMs or GRUs to provide agents with memory, these models are notoriously data-hungry and function as "black boxes," making it difficult to discern what the agent is remembering or why. This paper proposes a middle ground: a method for learning accurate, interpretable predictive models that link causes to effects across arbitrary time delays without requiring massive training datasets.
Methods
The authors propose a Greedy Causal Graph Construction algorithm. Instead of starting with a complex memory structure, the agent begins with a simple Markov assumption. When it encounters outcomes it cannot predict reliably (high entropy), it follows a structured process to expand its model:
- Identify Uncertainty: Flag variables with high unpredictability.
- Search for Past Causes: Search history for a variable $Y$ at a previous time $t+\tau$ that provides the highest Information Gain for the current unpredictable variable $X$.
- Create Memory Units: Once a cause is identified, the algorithm creates a "timer" variable ($M$) to track how long it has been since that specific causal event occurred.
- Causality Testing: To ensure the link is not a spurious correlation, the Principle of Independence of Cause and Mechanism is applied. This statistical test verifies if the cause and the process producing the effect are truly independent.
- Planning: These discovered hidden variables are fed into a neural network for future reward and state prediction, which a Monte Carlo Tree Search (MCTS) uses to plan actions.
Experiments and Key Results
The approach was evaluated on three distinct environments: Robotic Painting, Tire Removal, and VizDoom. In the robotic tasks, the proposed method reached a nearly 100% success rate, while standard RL baselines like PPO and A2C with LSTMs struggled to learn the long-term dependencies.
In the VizDoom experiment, the algorithm successfully identified that shooting effectiveness was tied to a specific 18-step cooldown, effectively "discovering" the game's internal mechanics from raw observation. As shown in the performance metrics, the proposed method significantly outperforms standard recurrent baselines in terms of average score and learning speed.
Key Insights
- Timers as Memory: Representing memory as "time since event $Y$" is highly effective for physical tasks, converting temporal problems into state-based ones.
- Pruning Confounders: Using causal inference principles prevents the agent from being misled by coincidental correlations.
- Incremental Complexity: Starting simple and adding hidden variables only when necessary ensures higher data efficiency than deep recurrent models that attempt to learn all dependencies simultaneously.
Limitations and Future Work
The current model assumes the environment can be decomposed into objects with attributes, which may limit its use in unstructured environments. Additionally, while the algorithm discovered the temporal cooldown in Doom, it failed to explicitly discover the "ammunition" variable, suggesting that the search for hidden variables may still miss certain non-temporal causal factors. Future work will also need to address the computational cost of searching through all possible time shifts and spatial partitions as environment complexity increases.
Summary updated