Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPs

Summary

This partial ingest is based on the extracted full PDF text. Hashimoto et al. study how to compute Probabilistic Controlled Invariant Sets for safe RL when the transition kernel is unknown but has a linear-MDP representation. The paper constructs a conservative approximation of an N-step safety predecessor operator from transition data, certifies candidate safe sets with high confidence using sample splitting, and uses the resulting set-valued safe action map as an external Shielding layer around arbitrary RL learners.

Key Claims

• Safe exploration can be enforced through an explicit probabilistic invariant-set object rather than only through recovery controllers, constrained policy updates, or cumulative violation bounds.
• For unknown linear MDPs, regularized least squares plus self-normalized confidence bounds can give an eta-conservative lower approximation of the N-step safety predecessor operator.
• A conservative fixed point is only a candidate PCIS when selected using the same data; a separate hold-out certification step is needed to claim the set is an (N, epsilon)-PCIS with confidence.
• In continuous state spaces, a lattice abstraction plus a Lipschitz discretization error term gives a tractable conservative approximation, at the cost of state-explosion-style scaling.
• The PCIS safe action map can wrap DQN, SARSA, or another learner as a runtime shield that filters proposed actions without modifying the learner’s update rule.

Methods / Formalism

• The MDP is M=(X,U,P,X_S) with finite actions, safe set X_S, and unknown transition kernel. The linear-MDP assumption gives a known feature map phi:X x U -> R^d and unknown signed measures nu_l such that P(A|x,u)=<phi(x,u),nu(A)>.
• An (N, epsilon)-PCIS is a set X_PCIS subseteq X_S such that every x in X_PCIS has a deterministic Markov policy keeping the trajectory inside X_PCIS for N transitions with probability at least 1-epsilon.
• The exact operator is:

$$Q_{ϵ}^N(\Omega )=\{x\in \Omega :\exists {\Pi }_N\text{s.t.}{p}_{{\Pi }_N}^{\Omega }(x)\ge 1-ϵ\}.$$

• The paper estimates the dynamic-programming safety recursion with lower confidence bounds, producing an approximate operator \tilde Q^N_\epsilon.
• The data are split into grow data, used to find a tentative fixed point, and certification data, used only to test the fixed reference set. PCIS Safety Predecessor records the formal recursion and grow/certify wrapper.

Evidence / Experiments

• The empirical section is a proof-of-concept on an unclipped modified MountainCar benchmark with continuous state, three discrete actions, Fourier state-action features, and a rectangular safe set.
• Shielded DQN improves fully safe runs from 9/30 to 30/30 and goal-reaching seeds from 23/30 to 28/30 in the reported setup.
• Shielded SARSA also improves fully safe runs from 9/30 to 30/30, but goal-reaching seeds drop from 23/30 to 20/30, consistent with a conservative safety-priority shield restricting momentum-building trajectories.
• The authors emphasize that the trajectory and return plots are qualitative proof-of-concept evidence, not a fine-grained statistical efficiency comparison.

Connections

• Extends Shielding beyond temporal-logic or given-model shields by synthesizing an external safety filter directly from transition data.
• Connects Safe Reinforcement Learning to Control Theory through controlled invariance and safe set maintenance.
• Relates to Probabilistic Model Checking because the safety object is an N-step probability guarantee over an MDP, but the operational target is runtime filtering rather than offline property checking.
• Relates to Invariant Synthesis as a probabilistic and data-driven invariant-set construction for controlled stochastic systems.
• Complements Brorholt2025 - Compositional Shielding and Reinforcement Learning for Multi-Agent Systems: both produce shield layers, but this paper focuses on single-agent unknown linear MDPs and data-driven PCIS certification rather than compositional multi-agent assume-guarantee shields.

Open Questions

• How can the lattice abstraction scale beyond low-dimensional continuous state spaces?
• Can local or adaptive Lipschitz estimates reduce the conservatism introduced by global discretization bounds?
• What uniform-certification or multiple-testing arguments are needed when shield updates are repeated many times online?
• Can the PCIS recursion be combined with compositional or subsystem abstractions so that certificates can be assembled in higher-dimensional systems?

Citation

Hashimoto, Kazumune, Shunki Kimura, Kazunobu Serizawa, Junya Ikemoto, Yulong Gao, and Kai Cai. 2026. “Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPs.” arXiv:2604.02727.