PCIS Safety Predecessor

Context

Hashimoto2026 - Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPs builds a Shielding layer by estimating a conservative safety predecessor for unknown linear MDPs. The annex collects the reusable formal core: the exact N-step predecessor, the lower-confidence approximation, the grow/certify split, and the induced safe action map.

Formal Statement

For a reference set Omega subseteq X_S, define the dynamic-programming recursion:

$$p_N^{\Omega }(x)=1_{\Omega }(x),$$ $$p_j^{\Omega }(x)=1_{\Omega }(x)\underset{u\in U}{\max }E[p_{j+1}^{\Omega }(x^{\prime })\mid x,u],j=N-1,\dots ,0.$$

Then the exact N-step safety predecessor is:

$$Q_{ϵ}^N(\Omega )=\{x\in \Omega :p_0^{\Omega }(x)\ge 1-ϵ\}.$$

Under the linear-MDP assumption, for any bounded continuation value p, there is a parameter vector theta_p satisfying:

$$E[p(x^{\prime })\mid x,u]=⟨{\theta }_p,\varphi (x,u)⟩.$$

Given independent stage datasets, regularized least squares estimates a lower confidence bound

$${\ell }_j(x,u)={\hat{\theta }}_j^{\top }\varphi (x,u)-{\beta }_j{\sigma }_j(x,u),$$

and the conservative recursion is:

$${\tilde{p}}_N(x)=1_{\Omega }(x),$$ $${\tilde{p}}_j(x)=1_{\Omega }(x)\underset{u\in U}{\max }\min \{1,[{\ell }_j(x,u){]}_{+}\}.$$

The induced approximate operator is:

$${\tilde{Q}}_{ϵ}^N(\Omega )=\{x\in \Omega :{\tilde{p}}_0(x)\ge 1-ϵ\}.$$

With appropriate confidence allocation, the paper proves conservative inclusion:

$$\mathrm{Pr}({\tilde{Q}}_{ϵ}^N(\Omega )\subseteq Q_{ϵ}^N(\Omega ))\ge \eta .$$

Derivation / Construction

The lower-confidence bound makes the estimated continuation probability pessimistic. Backward induction then ensures \tilde p_j(x) <= p^\Omega_j(x) on the confidence event, so any state meeting the threshold under the conservative recursion also meets it under the exact recursion.

Because a fixed point found from data is adaptively selected, the paper separates construction from certification:

• Grow phase: use D_grow to repeatedly apply the conservative operator until a tentative fixed point Omega_tent is found.
• Certification phase: use independent D_cert to evaluate the conservative operator once on the fixed set Omega_tent.
• Accept the tentative shield only if Omega_tent subseteq \tilde Q^{N,cert}_\epsilon(Omega_tent).

For continuous state spaces, the operator is evaluated on a lattice over X_S; a Lipschitz discretization bound is subtracted so the approximation remains conservative after quantization.

The safe action map for a fixed reference set is:

$${\mu }_j^S(x;\Omega )=\{u\in U:{\ell }_j(x,u)\ge 1-ϵ\}.$$

For N>1, this is stage-dependent and should be used on the augmented state (j,x) or in a receding-horizon scheme.

Implications

• PCIS shielding turns data into an explicit runtime safety filter instead of only a policy penalty.
• The certification split is essential: finding a conservative fixed point and certifying it are different statistical tasks.
• Lattice abstraction makes the continuous-state method tractable only in low-dimensional settings unless combined with adaptive or compositional abstractions.
• The safe action map is set-valued, so backup action selection still matters for learning performance.

Links

• Hashimoto2026 - Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPs
• Probabilistic Controlled Invariant Sets
• Shielding
• Safe Reinforcement Learning