Safe Policy Improvement for POMDPs via Finite-State Controllers

Thiago D. Simão, Marnix Suilen, Nils Jansen

Introduction

In offline reinforcement learning (RL), the goal is to derive an improved policy from a fixed dataset of historical interactions. A significant challenge in this domain is "policy collapse," where a newly learned policy performs worse than the original behavior policy due to insufficient data coverage. Safe Policy Improvement (SPI) algorithms address this by providing probabilistic guarantees that the new policy will at least match the performance of the baseline.

While SPI is well-studied for Markov Decision Processes (MDPs), real-world applications often involve Partially Observable MDPs (POMDPs), where agents lack full state visibility. This paper extends SPI to POMDPs by utilizing Finite-State Controllers (FSCs) to provide the necessary memory for effective decision-making in partially observable environments.

Methodology: From POMDPs to History MDPs

The authors propose a framework that transforms a POMDP into a tractable "History MDP." This transformation is achieved through two key components:

  1. Finite-State Controllers (FSCs): Unlike reactive policies, FSCs maintain an internal memory state (nodes) that updates based on incoming observations. This allows the agent to base decisions on a sequence of past events.
  2. History MDP Mapping: By assuming that a finite history window is sufficient for near-optimal behavior, the POMDP's history is mapped into the states of a new MDP. Each state in this History MDP is defined by the current FSC memory node and the most recent observation.
Overview of the offline RL framework for POMDPs.

Safe Policy Improvement with Baseline Bootstrapping (SPIBB)

Once the History MDP is established, the authors apply the SPIBB algorithm. SPIBB is a pessimistic approach: it identifies state-action pairs with insufficient data in the buffer and "bootstraps" them by defaulting to the behavior policy. This prevents the agent from taking unverified risks in poorly explored regions of the state space. The authors provide a theoretical performance bound ($\zeta$) ensuring that the improved policy will outperform the behavior policy with high probability ($1-\delta$).

Experimental Evaluation

The framework was evaluated on three standard POMDP benchmarks: CheeseMaze, Tiger, and Voicemail. These environments test various aspects of partial observability, from spatial navigation with limited visibility to inferring intent from noisy signals.

Performance comparison of SPIBB against Basic RL and PO-UCT.

Key Results

  • Reliability: In all benchmarks, "Basic RL" (which solves the estimated model without safety constraints) frequently performed worse than the behavior policy when data was scarce. In contrast, SPIBB consistently met or exceeded the baseline performance.
  • Data Efficiency: As the dataset size ($|\mathcal{D}|$) increased, SPIBB-derived policies converged toward the performance of PO-UCT, a powerful online solver. This indicates that the safety constraints do not hinder the discovery of near-optimal policies given sufficient data.
  • Memory and Safety: A critical insight is that increasing the memory size ($k$) of the FSC not only improves potential performance but also enhances the reliability of the SPI guarantees.

Conclusion and Future Work

This research successfully bridges the gap between theoretical SPI guarantees and the practical complexities of POMDPs. By leveraging FSCs and History MDPs, the authors provide a robust method for offline policy improvement in partially observable settings. Future work may explore approximate bisimilarity to improve data efficiency and the integration of deep learning architectures to handle high-dimensional observation spaces.

Summary updated

Abstract

We study safe policy improvement (SPI) for partially observable Markov decision processes (POMDPs). SPI is an offline reinforcement learning (RL) problem that assumes access to (1) historical data about an environment, and (2) the so-called behavior policy that previously generated this data by interacting with the environment. SPI methods neither require access to a model nor the environment itself, and aim to reliably improve upon the behavior policy in an offline manner. Existing methods make the strong assumption that the environment is fully observable. In our novel approach to the SPI problem for POMDPs, we assume that a finite-state controller (FSC) represents the behavior policy and that finite memory is sufficient to derive optimal policies. This assumption allows us to map the POMDP to a finite-state fully observable MDP, the history MDP. We estimate this MDP by combining the historical data and the memory of the FSC, and compute an improved policy using an off-the-shelf SPI algorithm. The underlying SPI method constrains the policy space according to the available data, such that the newly computed policy only differs from the behavior policy when sufficient data is available. We show that this new policy, converted into a new FSC for the (unknown) POMDP, outperforms the behavior policy with high probability. Experimental results on several well-established benchmarks show the applicability of the approach, even in cases where finite memory is not sufficient.
BibTeX
@inproceedings{simao2023safe,
  author = {Thiago D. Simão and Marnix Suilen and Nils Jansen},
  title = {{Safe Policy Improvement for POMDPs via Finite-State Controllers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i12.26763},
}
Figure