Abstract
Safe Policy Improvement (SPI) aims to derive a new policy that is guaranteed to perform at least as well as a known behavior policy ($\pi_b$). While traditional SPI methods suffer from high sample complexity in large state spaces, this paper proposes a novel framework that integrates structure learning with Factored Reinforcement Learning. By automatically identifying variable dependencies through a Dynamic Bayesian Network (DBN) approach and utilizing the "Knows What It Knows" (KWIK) framework, the proposed algorithm achieves orders-of-magnitude improvements in sample efficiency while maintaining rigorous safety guarantees.
Introduction
In many real-world applications, deploying a raw Reinforcement Learning (RL) agent is risky due to potential performance degradation compared to an existing behavior policy. SPI provides a mathematical safety net, but current approaches face a dilemma: "Flat" SPI methods require impractical amounts of data in complex systems, while "Factored" SPI methods typically require human experts to manually define the system's structure. This research introduces Structure Learning $\Pi_b$-SPIBB, a framework that learns the underlying problem structure on the fly, enabling efficient generalization without prior expert knowledge.
Methodology
The core of the proposed approach is the integration of Structure Learning (SL) subalgorithms into the "Safe Policy Improvement by Baseline Bootstrapping" (SPIBB) framework. The system dynamics are estimated as a Dynamic Bayesian Network, where the agent identifies which variables influence one another based on observed data.
The KWIK Framework and Safety
To ensure safety, the algorithm employs KWIK-admissible subalgorithms (such as $k$-meteorologists). When the agent lacks sufficient data to be certain about a specific relationship or transition, it returns a "don't know" symbol ($\perp$). In these uncertain regions, the SPIBB framework marks the state-action pair as "unsafe," forcing the agent to mimic the reliable behavior policy. This mechanism turns statistical uncertainty into a proactive safety feature.
Experimental Evaluation
The researchers evaluated the framework across three simulated benchmarks:
- Taxi Domain: A 4-variable task involving passenger pickup and delivery.
- SysAdmin Domain: A 9-computer network where machine failures affect neighbors, representing a well-factorized environment.
- Stock-Trading Domain: A high-dimensional task involving 6 stocks across 3 sectors, testing the ability to handle complex dependencies.
Key Results
The experiments demonstrated that learning the problem structure provides a massive boost in sample efficiency while strictly avoiding "negative transfer" (performing worse than the baseline).
Sample Efficiency and Generalization
In the Stock-Trading domain, the Factored SPI with structure learning identified an improved policy using approximately 200 trajectories. In contrast, the standard "flat" SPI algorithm required nearly 10,000 trajectories to achieve comparable performance. This improvement stems from the agent's ability to generalize; by identifying that an action's effect on a specific variable only depends on a subset of other variables, the agent can learn from every relevant instance regardless of the state of the rest of the system.
Performance vs. Oracle
The proposed algorithms performed nearly as well as an "oracle" version that was provided with the true environment structure. As shown in the performance plots, the factored models quickly converge to optimal performance as the structure error drops toward zero.
Conclusion and Future Work
By combining structure learning with safe bootstrapping, this framework bridges the gap between the data efficiency of factored models and the autonomy of model-free RL. While currently limited to DBN structures and discrete dynamics, future work may extend these principles to more complex function approximations and continuous environments. The results confirm that identifying variable independence is not just an optimization—it is a fundamental requirement for achieving safety in data-constrained environments.
Summary updated