The Transition You Never Saw Still Matters

TL;DR for operators

A controller can repeatedly complete its assigned task in simulation without providing a mathematical guarantee that it will eventually succeed. For an unknown decision system, increasing the simulation budget does not always close that gap.

S Akshay, Suguman Bansal, and Gaurav Mahla¹ prove that learning or verifying an almost-sure reachability certificate has no uniform sample-complexity guarantee when unknown transition probabilities are unrestricted. An arbitrarily rare transition can remain invisible under any sample budget determined only by model size and confidence.

The authors also establish a conditional solution: assume a known positive lower bound on every nonzero transition probability, estimate the transition model accurately enough, and construct a mathematical certificate whose validity transfers to the true system.

The resulting sampling requirement can grow exponentially with target distance. Moreover, the sufficient certification test can be conservative: all seven constructed benchmark certificates remain valid, but three fail the theoretical transfer condition.

For assurance teams, this changes the certification decision. Simulation volume is not enough; the defensibility of transition assumptions, model-error estimates, and certificate margins determines what can actually be guaranteed.

Why successful simulations cannot establish eventual success

Consider an autonomous controller that completes its assigned task in every simulation presented for evaluation. An operator considering its use in a safety-sensitive workflow wants a stronger statement: will the controller eventually reach its target with probability exactly one?

This property is called almost-sure reachability. It allows individual executions to take arbitrarily long, but requires the probability of never reaching the target to be zero.

The difficulty is that finite observations cannot reliably expose arbitrarily rare transitions.

In Section 3, the authors construct finite Markov decision processes (MDPs) whose relevant behavior cannot be distinguished reliably before a rare progress transition is observed. As that transition’s probability approaches zero, the number of samples needed to reveal it can grow without bound.

The resulting impossibility theorem rules out an algorithm whose required sample count depends only on the numbers of states and actions and a chosen confidence level, without restrictions on the unknown probabilities.

The result extends to verification of an existing certificate. Supplying a candidate mathematical proof does not eliminate the need to know whether its conditions hold under the actual transition dynamics.

This is a limitation of the information available from samples, rather than a claim that particular unknown systems can never be certified.

A certificate must demonstrate expected progress from every state

The authors study ranking supermartingales (RSMs), mathematical functions assigning a nonnegative value $V(s)$ to each state.

Outside the target set, a valid certificate must decrease by at least some strictly positive amount $\varepsilon$ in conditional expectation:

Here, $P$ describes the true transition probabilities under the fixed policy $\pi$.

The requirement applies to every non-target state, not merely states visited during testing. In a finite MDP, such a certificate establishes almost-sure reachability. The authors also prove completeness: under their setting, an RSM exists whenever the target is reached almost surely from every state (Section 2, Theorem 2 and Corollary 1).

This explains why the hidden transition probabilities matter. The inequality concerns expected behavior under the true dynamics, which cannot be calculated reliably from observations that omit consequential transitions.

The central certification problem is therefore to construct a function whose expected decrease remains positive despite uncertainty about those dynamics.

A known probability floor makes certificate learning possible

The positive result introduces $p_{\min}$, a known positive lower bound on every nonzero transition probability.

This assumption rules out transitions that are possible but arbitrarily unlikely. It does not require every state transition to have positive probability; impossible transitions can still have probability zero.

Under this assumption and almost-sure reachability from every state, progress-making transitions become observable with high probability using finitely many samples.

The authors then construct a certificate using expected hitting time:

where $H_T$ is the first time the trajectory reaches the target.

Outside the target, the Bellman recursion gives:

Thus, expected remaining time decreases by exactly one per step. This supplies a canonical RSM on the true model, provided the required reachability assumption holds.

For an unknown MDP, the certificate must instead be computed on an estimated transition model. The authors establish when that learned-model certificate transfers to the true dynamics.

Let $\eta$ be the aggregate absolute difference between the true and learned transition kernels, $B$ the maximum certificate value, and $\varepsilon’$ the certificate’s expected-decrease margin on the learned model.

The guaranteed margin on the true model is:

Consequently, transfer is certified whenever:

This is the paper’s principal bridge between learning dynamics from samples and establishing mathematical correctness.

For expected hitting-time certificates, the authors derive the explicit sufficient accuracy requirement:

where $D$ is the maximum shortest-path distance from any state to the target.

The corresponding probabilistic learning guarantee has sample complexity polynomial in:

Here, $\delta$ is the permitted failure probability.

Although expressed as a polynomial bound, the dependence on $(p_{\min}/2)^{-D}$ can be exponential in $D$. A certification procedure may therefore be mathematically possible but require a prohibitive sampling budget.

Three certificates fail the sufficient test but remain valid

Section 5 examines seven constructed finite MDPs using deterministic transition-kernel calculations. These evaluations test the conservativeness of the transfer theorem, not the practical sampling cost of learning the models.

The authors compute certificates on nominal models, perturb the transition kernels, and calculate their actual minimum expected decrease under the resulting true dynamics.

Source: Section 5, Table 1. Positive minimum drift establishes certificate validity in these constructed instances. The sufficient margin is a conservative theoretical lower bound, not the measured drift.

All seven certificates retain positive true-model drift. Only four satisfy the sufficient theoretical condition.

The largest discrepancy occurs in the 100-state example. Its maximum certificate value is $B=10{,}666.7$, making the global approximation-error penalty large. The theoretical margin falls to $-105.667$, even though the actual minimum drift remains $0.958$.

The negative margin means that the theorem cannot establish validity through this particular bound. It does not establish certificate invalidity.

Appendix B’s state-level calculations reinforce this interpretation. In the rare-transition examples, large expected hitting times make the global worst-case bound loose, while actual one-step expected decreases remain positive.

These are exact calculations on selected constructed systems, not randomized experimental results or estimates of field performance.

What changes for controller assurance

For a team evaluating an existing autonomous controller representable as a finite MDP, the paper suggests separating three decisions.

First, establish whether the environment supports certification assumptions. A known and defensible $p_{\min}$ is a substantive prerequisite, not a parameter that can safely be inferred from a finite set of successful trajectories.

Second, evaluate the achievable model accuracy and sampling budget. The team needs to determine whether estimated transition probabilities can satisfy the required error tolerance. Rare progress and long distances to the target can make that requirement demanding even for finite systems.

Third, distinguish failure of a sufficient bound from failure of a certificate. A negative global transfer margin should be recorded as an inconclusive result under that criterion. More precise state-sensitive verification may be worth investigating, although this paper does not establish its cost or effectiveness in deployment.

These are Cognaptus interpretations for assurance-workflow design, not benefits demonstrated in a production controller.

The guarantee has a narrow but consequential boundary

The positive theory concerns finite MDPs, fixed deterministic memoryless policies, and almost-sure reachability from every state. That last assumption is stronger than requiring success only from an operationally designated initial state.

The probability floor must be known, and the sample-complexity dependence on maximum target distance may be exponential. When the true support-based distance is unknown, the learner can substitute the conservative bound $|S|-1$.

The authors do not establish corresponding guarantees for continuous-state systems, unrestricted adaptive policies, reach-avoid objectives, or general temporal-logic specifications. Nor do the deterministic benchmarks measure the simulator interactions required to achieve the theoretical model accuracy.

Whether substantially tighter general certification bounds can eliminate the exponential dependence on distance remains unresolved.

Certification requires information that simulation success cannot supply

The paper identifies both an information limit and a conditional route around it. Without restrictions on hidden transition probabilities, uniformly guaranteed sample-based certificate learning and verification are impossible. With a known probability floor and sufficiently accurate transition estimates, mathematical reachability certificates can be constructed and transferred.

The remaining engineering challenge is substantial: the sampling requirements may be severe, while conservative global tests may fail to certify functions that are actually valid.

For teams making deployment-assurance decisions, the relevant outcome is not simply how frequently a controller succeeds in testing. It is whether the assumptions and available evidence support a proof about the controller’s behavior under the true dynamics.

Cognaptus: Automate the Present, Incubate the Future.