Interval POMDP Shielding for Imperfect-Perception Agents

1. Problem Statement

Autonomous systems increasingly rely on learned perception components (e.g., Deep Neural Networks) to interpret sensor data. However, these components suffer from imperfect perception, where sensor readings are misclassified, leading to unsafe decisions.

• The Challenge: Traditional shielding methods often assume perfect state observation or rely on point-estimate models of perception uncertainty. When perception is imperfect, the agent operates under a Partially Observable Markov Decision Process (POMDP).
• The Gap: Existing approaches face two main limitations:
  1. Point Estimates: Using a single estimated probability for perception errors can be dangerously optimistic, especially when trained on finite data.
  2. Support-Based Abstraction: Methods that only track which states are possible (support-based shields) discard probabilistic information, often becoming too coarse to admit any safe actions in complex, aliased environments.
• Distributional Shift: The paper addresses the critical issue that perception models trained on finite data may not match deployment realities (deployment shift). The goal is to build a shield robust to this shift while maintaining formal safety guarantees.

2. Methodology

The authors propose a framework that models the system as an Interval Partially Observable Markov Decision Process (IPOMDP) and constructs a runtime shield using belief envelopes.

A. System Modeling: IPOMDP

Instead of fixed emission probabilities $Z(o|s)$, the system uses intervals $[Z^-(o|s), Z^+(o|s)]$ derived from finite labeled data.

• Interval Construction: Using the Clopper-Pearson method, confidence intervals are calculated for every state-observation pair. This ensures that with high probability ($\lambda$), the true perception model lies within these bounds, providing a Probably Approximately Correct (PAC) guarantee against deployment shift.
• Admissible Set: The system considers the set of all valid perception models $\mathcal{Z}$ that satisfy these interval bounds.

B. Shielding Mechanism: Belief Envelopes

The core innovation is lifting a "perfect-perception" shield (which knows the true state) to the imperfect-perception setting without computing the exact reachable belief set (which is intractable due to non-convexity).

1. Perfect-Perception Base: Start with a shield $\Omega$ defined on the true state space (e.g., derived from Probabilistically Controlled Invariant Sets - PCIS).
2. Belief Propagation: Instead of tracking a single belief, the algorithm propagates a conservative belief envelope (a set of possible beliefs) consistent with the history and interval uncertainty.
3. Linear Programming (LP) Formulation:
   • The belief update involves bilinear terms (probability $\times$ belief) and normalization (division by total evidence).
   • To make this tractable, the authors use McCormick envelopes to linearize the bilinear products and the Charnes-Cooper transformation to handle the fractional normalization.
   • The reachable belief set is over-approximated by a template polytope (e.g., a hypercube of coordinate-wise bounds).
4. Action Admissibility: An action is permitted only if its worst-case safety score (minimum probability of safety across all beliefs in the envelope) exceeds a threshold $\beta$.

C. Safety Guarantees

The method provides a finite-horizon double-probability guarantee:

• With probability $\ge \lambda$ (over the training dataset), the true perception model is within the learned intervals.
• Conditioned on this, the shield guarantees that the system remains in a safe set with probability $\ge (\beta \gamma)^H$ over horizon $H$, where $\gamma$ is the invariance probability of the underlying perfect-perception shield.

3. Key Contributions

1. IPOMDP Formulation: A formal model for imperfect-perception systems using finite-data observation uncertainty and interval bounds.
2. Runtime Shield Construction: A novel method to lift perfect-perception shields to imperfect settings by propagating conservative belief envelopes.
3. LP-Based Over-Approximation: A sound linear programming and linear-fractional programming method to compute reachable belief sets under interval uncertainty, avoiding the "vertex explosion" of exact convex-hull propagation.
4. Empirical Validation: Comprehensive evaluation on four benchmarks (TaxiNet, Obstacle, CartPole, Refuel) comparing the proposed method against state-of-the-art baselines.
5. Theoretical Guarantees: Proof of abstraction soundness and finite-sample PAC correctness for the learned intervals.

4. Experimental Results

The authors evaluated five shielding strategies: Observation (memoryless), Single-Belief (point-estimate history), Fwd-Sampling (sampling-based under-approximation), Envelope (proposed LP-based over-approximation), and Carr (support-based).

• Safety vs. Usability Trade-off:
  • CartPole (High Observability): All methods performed similarly; the interval envelope was unnecessary as observations localized the state well.
  • TaxiNet & Obstacle (Aliased/Noisy): The Envelope shield significantly outperformed others. It reduced failure rates compared to Single-Belief (which was too optimistic) and prevented the "stuck" behavior (blocking all actions) seen in Support-based shields (which were too coarse).
  • Refuel (Latent Variables): The Envelope method was computationally infeasible due to state space size, highlighting a scalability limit. Fwd-Sampling served as a scalable, though slightly less safe, alternative.
• Adversarial Regime: Under worst-case observation realizations, the Envelope shield maintained the lowest failure rates, demonstrating robustness to deployment shift.
• Computational Cost:
  • Observation/Single-Belief: Microsecond inference time.
  • Fwd-Sampling: Millisecond to sub-second.
  • Envelope: Milliseconds to hundreds of milliseconds (2–5 orders of magnitude slower), making it suitable for low-frequency safety checks or smaller models.

5. Significance and Impact

• Bridging the Gap: This work occupies a critical middle ground between overly optimistic point-estimate methods and overly conservative support-based methods. It is particularly vital for safety-critical systems where perception is noisy and data is finite.
• Robustness to Shift: By using confidence intervals derived from finite data, the shield explicitly guards against the mismatch between training and deployment distributions (deployment shift), a common failure mode in learned autonomy.
• Modularity: The approach separates the dynamics-level safety logic (the perfect-perception shield) from the perception uncertainty reasoning, allowing it to integrate with various existing shield synthesis techniques (e.g., PCIS, barrier certificates).
• Practical Engineering: The paper provides a clear hierarchy of methods: use lightweight point-estimates when observations are clear, use the LP-envelope for high-stakes, aliased scenarios where it is computationally feasible, and use sampling-based approximations when the state space is too large for exact envelope propagation.

In summary, the paper presents a rigorous, mathematically grounded approach to making autonomous agents safer in the face of imperfect perception and data uncertainty, offering formal guarantees that are practically verifiable.