Structure Learning for Safe Policy Improvement

Thiago D. Simão, Matthijs T. J. Spaan

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.

Structure error reduction as a function of dataset size |D| across different domains.

Experimental Evaluation

The researchers evaluated the framework across three simulated benchmarks:

  1. Taxi Domain: A 4-variable task involving passenger pickup and delivery.
  2. SysAdmin Domain: A 9-computer network where machine failures affect neighbors, representing a well-factorized environment.
  3. 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).

Mean performance of various SPI algorithms. Factored methods with structure learning significantly outperform flat SPI and approach oracle performance.

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

Abstract

We investigate how Safe Policy Improvement (SPI) algorithms can exploit the structure of factored Markov decision processes when such structure is unknown a priori. To facilitate the application of reinforcement learning in the real world, SPI provides probabilistic guarantees that policy changes in a running process will improve the performance of this process. However, current SPI algorithms have requirements that might be impractical, such as: (i) availability of a large amount of historical data, or (ii) prior knowledge of the underlying structure. To overcome these limitations we enhance a Factored SPI (FSPI) algorithm with different structure learning methods. The resulting algorithms need fewer samples to improve the policy and require weaker prior knowledge assumptions. In well-factorized domains, the proposed algorithms improve performance significantly compared to a flat SPI algorithm, demonstrating a sample complexity closer to an FSPI algorithm that knows the structure. This indicates that the combination of FSPI and structure learning algorithms is a promising solution to real-world problems involving many variables.
BibTeX
@inproceedings{simao2019structure,
  author = {Thiago D. Simão and Matthijs T. J. Spaan},
  title = {{Structure Learning for Safe Policy Improvement}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/479},
}
Figure