Abstract
Reinforcement learning (RL) agents often struggle with the trade-off between sample efficiency and computational complexity. Furthermore, traditional navigation algorithms lack the flexibility to handle dynamic environmental changes without exhaustive recalculation. This paper introduces Q-Cogni, a framework that integrates autonomous causal structure discovery with model-free Q-learning. By learning a causal model of the environment offline, Q-Cogni guides exploration and adjusts rewards, leading to improved convergence rates and interpretability. Evaluated on both the OpenAI Gym Taxi-v3 environment and real-world New York City taxi data, Q-Cogni demonstrates superior scalability and adaptability in solving complex Vehicle Routing Problems (VRP).
Introduction
Standard RL approaches typically fall into two camps: model-free methods, which are computationally efficient but sample-hungry, and model-based methods, which are sample-efficient but computationally demanding. In the context of navigation and vehicle routing, traditional algorithms like Dijkstra’s or A* provide optimal paths but require complete prior knowledge of the map and fail to adapt dynamically to real-time events like traffic congestion.
While causal inference offers a path toward more efficient and interpretable RL, most existing methods rely on human experts to provide pre-defined causal graphs. Q-Cogni addresses this limitation by autonomously discovering the environment's causal structure and embedding this reasoning directly into the learning process.
Methodology
The Q-Cogni framework is composed of three integrated modules that facilitate a hybrid model-based/model-free learning approach.
- Autonomous Offline Causal Structure Discovery: The agent initially performs a random walk to gather state-action-reward data. It then utilizes the NOTEARS algorithm to learn a Directed Acyclic Graph (DAG) representing causal relationships, which is subsequently modeled as a Bayesian Belief Network (BBN).
- Causal Inference: During training, the agent queries the BBN to determine the conditional probability of achieving a sub-goal (e.g., $P(goal=True | state, action)$).
- Modified Q-Learning: Instead of purely random $\epsilon$-greedy exploration, Q-Cogni uses the causal model as a heuristic. If an action has a high probability of success according to the BBN, the agent prioritizes it and scales the environmental reward accordingly, mitigating the sparse reward problem.
Experimental Results
The framework was tested on the Taxi-v3 baseline and a large-scale real-world dataset from the NYC Taxi & Limousine Commission.
- Efficiency and Convergence: In the
Taxi-v3environment, Q-Cogni achieved rewards comparable to Deep Q-Networks (DDQN) and Proximal Policy Optimization (PPO) but reached convergence significantly faster due to its causal exploration shortcuts. - Scalability: Q-Cogni exhibited near-linear time complexity when scaled to grid sizes as large as 512x512, significantly outperforming Dijkstra’s and A* in terms of computation time for large-scale routing.
- Real-World Performance: On 531 real taxi trips in NYC, Q-Cogni produced shorter routes than standard Q-learning in 66% of cases. It matched the optimal distance provided by Dijkstra’s algorithm in 76% of the trips, while maintaining the ability to reroute dynamically in response to simulated traffic events.
Explainability and Adaptability
A key advantage of Q-Cogni is its inherent interpretability. Because the agent relies on a Bayesian Belief Network, it can provide transparent reasoning for its actions by outputting the underlying probabilities.
Furthermore, the agent is agnostic to global maps. It learns the causal rules of navigation rather than a static path, allowing it to generalize to new map configurations and handle unexpected road closures without retraining or full-path recalculation.
Conclusion and Future Work
Q-Cogni represents a significant step toward autonomous, interpretable, and efficient reinforcement learning. By bridging causal discovery and model-free RL, it provides a robust solution for dynamic combinatorial optimization problems. Future research will focus on extending the framework to continuous state-action spaces for applications in robotics and integrating deep learning for high-dimensional feature extraction from sensory data.
Summary updated