🤖 machine learning

Value Functions as Supermartingale Certificates

This paper establishes a theoretical connection showing that value functions for policies satisfying $\omega$ -regular properties encode Streett supermartingale certificates, thereby bridging formal verification and reinforcement learning to enable principled certificate synthesis across finite, countably infinite, and continuous state spaces.

Original authors: Alessandro Abate, Daniel Contro, Mirco Giacobbe, Agustín Martínez-Suñé, Diptarko Roy

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro Abate, Daniel Contro, Mirco Giacobbe, Agustín Martínez-Suñé, Diptarko Roy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a maze. You want the robot to follow a complex set of rules, like "Keep going until you find the treasure, then stay in the safe zone forever, and never step in the lava." In the world of computer science, this is called satisfying an "omega-regular" property (a fancy way of saying a rule that applies to an infinite journey).

For a long time, there have been two separate ways to handle this:

The "Math Proof" Way (Verification): Mathematicians use something called a Supermartingale Certificate. Think of this as a "safety scorecard." If you can draw a map where the score always goes down (or stays the same) as the robot moves, and it hits zero only when the robot is safe, you have a mathematical proof that the robot will never fail, no matter how the dice roll (stochasticity). The problem is, drawing this map by hand for complex mazes is incredibly hard and doesn't scale well.
The "Trial and Error" Way (Reinforcement Learning): This is where the robot learns by doing. It tries actions, gets rewards for good moves, and learns a Value Function. Think of the Value Function as a "happiness map" that tells the robot how much future reward it can expect from any given spot. While this works great for finding a good path, it usually lacks a formal guarantee that the robot will succeed, especially in complex, infinite, or continuous worlds.

The Big Breakthrough
This paper bridges the gap between these two worlds. The authors discovered a surprising secret: If a robot's "happiness map" (Value Function) is built using a very specific type of reward system, that map is the "safety scorecard" (Supermartingale Certificate).

Here is how they did it, using simple analogies:

The Two Reward Recipes

The authors propose two different ways to give the robot rewards so that its resulting "happiness map" automatically becomes a valid safety proof.

Recipe 1: The "Safe Zone" Reward

How it works: You tell the robot: "You get a point every time you step into the 'Safe Zone' (or a zone where you are guaranteed to stay safe forever)."
The Magic: If the robot is actually following the rules, its "happiness map" will naturally start high outside the safe zone and drop lower as it gets closer to safety. Once it's in the safe zone, the map stays flat.
The Catch: To use this, you need to know exactly which areas are "Safe Zones" where the robot gets stuck forever. This is hard to know in advance for complex systems.

Recipe 2: The "Penalty and Prize" Reward

How it works: You tell the robot: "You get a small penalty (negative points) every time you are in the 'Danger Zone' (waiting for the goal), and a big prize when you finally reach the 'Goal'."
The Magic: As the robot moves through the danger zone, the "happiness map" increases because it is getting closer to the big prize and escaping the penalties. Once it hits the goal, the map stabilizes.
The Catch: This doesn't require knowing the "Safe Zones" in advance; it only needs to know the rules (the specification). However, it requires a slightly more complex math setup (a special discount factor) to make the numbers work out.

What They Proved

The authors proved mathematically that if you use either of these reward recipes, and the robot actually succeeds in following the rules, the resulting "happiness map" is a valid Supermartingale Certificate.

This means:

You don't need to manually draw the safety map.
You can use standard Reinforcement Learning tools to train the robot.
Once trained, you can look at the robot's "happiness map," flip it upside down (mathematically), and instantly have a formal, mathematical proof that the robot will succeed almost 100% of the time.

The Experiment

They tested this on a computer simulation of a "slippery maze" (where the robot might slide the wrong way by accident).

They trained robots to follow various complex rules (like "Find 'b' and never hit 'h'").
They calculated the "happiness map" for the successful robots.
They checked the map against the safety rules.
Result: The maps passed the test perfectly. The successful robots had valid certificates; the failing robots did not.

Why This Matters (According to the Paper)

This creates a new, principled path to Certified Reinforcement Learning. Instead of just hoping a learned policy works, or struggling to write complex proofs by hand, we can now:

Train a policy using standard AI methods.
Evaluate its Value Function.
Check if that function satisfies the "safety scorecard" rules.

If it does, we have a formal guarantee that the policy works, even in complex, continuous, or infinite environments. The paper suggests this could eventually allow us to use data-driven methods (like neural networks) to build these safety proofs for systems that are too big for humans to analyze manually.

Technical Summary: Value Functions as Supermartingale Certificates

Problem Statement

The verification of stochastic systems against $\omega$ -regular properties (including Linear Temporal Logic, LTL) over general state spaces (finite, countably infinite, and continuous) typically relies on supermartingale certificates. These are real-valued functions that satisfy specific proof rules, serving as mathematical guarantees for the almost-sure satisfaction of a specification. However, synthesizing these certificates is challenging; existing methods often rely on constrained optimization, which does not scale well to large or continuous state spaces.

Conversely, Reinforcement Learning (RL) has been widely applied to synthesize policies for $\omega$ -regular tasks. While RL methods can maximize the probability of satisfaction, they typically lack formal guarantees that a trained (non-optimal) policy satisfies the specification with a specific probability, particularly outside finite state and action spaces. There is a disconnect between the theoretical machinery of supermartingale verification and the practical machinery of RL policy evaluation.

Methodology

This paper establishes a novel theoretical connection between the value function of a policy in a discounted RL setting and Streett supermartingale certificates. The core hypothesis is that under specific reward designs, the value function $V^\pi$ of a policy $\pi$ that almost-surely satisfies an LTL specification encodes a valid Streett supermartingale.

The authors propose two distinct reward designs to achieve this:

Reward Design 1 (Absorbing Set Knowledge):
- Requirement: Knowledge of the absorbing sets induced by the policy (specifically, the largest absorbing subset of the complement of the union of the Streett pair sets).
- Mechanism: The reward is set to 1 when the process enters the target set $B$ or an absorbing set from which neither $A$ nor $B$ can be visited again.
- Theoretical Basis: The value function $V^\pi$ represents the expected discounted sum of these rewards. By defining the certificate $W(s) = C - V^\pi(s)$ (where $C$ is a constant related to the discount factor), the authors prove that $W$ satisfies the Streett supermartingale conditions: it decreases strictly in expectation when in $A \setminus B$ (due to uniform bounds on hitting times) and remains non-increasing elsewhere.
Reward Design 2 (Specification Knowledge Only):
- Requirement: Only knowledge of the specification (the Streett pair $(A, B)$ ), without requiring knowledge of the policy's specific absorbing sets.
- Mechanism: This design employs a state-dependent discount factor $\Gamma(s)$ and a reward function that assigns positive rewards for visiting $B$ and negative rewards for visiting $A \setminus B$ .
- Theoretical Basis: The discount factor is set to $\gamma < 1$ when rewards are non-zero and $1$ otherwise. Under a "positive recurrence bound" assumption (limiting the expected number of steps in $A$ before hitting $B$ ), the value function again encodes a supermartingale. The ratio of positive to negative rewards is tuned to ensure the certificate remains non-negative and strictly decreasing where required.

Both approaches are proven to hold for finite, countably infinite, and continuous state spaces. The proofs rely on lemmas relating value functions to first hitting times and expected one-step changes in value.

Key Contributions

Theoretical Bridge: The paper proves that the value function of a policy satisfying an LTL specification is a valid Streett supermartingale certificate under appropriate reward designs (Theorems 1 and 2).
Two Reward Schemes: The authors provide two distinct methods for constructing these rewards: one leveraging policy-specific absorbing sets (Theorem 1) and one relying solely on specification structure with state-dependent discounting (Theorem 2).
Generality: The results are not limited to finite MDPs; they apply to general state spaces, addressing a gap in existing RL-based verification which often lacks formal guarantees for infinite or continuous spaces.
Experimental Validation: The authors validate the theory on finite Markov Decision Processes (MDPs) using a grid-world environment. They synthesize certificates for various LTL specifications spanning the Manna-Pnueli hierarchy, verify the supermartingale proof rules, and cross-check satisfaction probabilities using the PRISM model checker.

Results

Experimental Verification: In the grid-world experiments, the proposed reward designs successfully synthesized valid certificates for policies that satisfied the specifications (probability of satisfaction = 1.0). For policies that did not satisfy the specifications, the proof rules failed (invalid certificates), and PRISM confirmed satisfaction probabilities strictly less than 1.
Consistency: The experimental results align perfectly with the theoretical guarantees, demonstrating that the value function approach correctly identifies both satisfying and non-satisfying policies.
Limitations in Experiments: The current experiments are restricted to finite MDPs where value functions are computed exactly via linear systems. The paper notes that extending this to infinite/continuous spaces using parametric approximations (e.g., neural networks) is left for future work.

Significance and Claims

The paper claims to open a "principled route to certificate synthesis via RL." By reframing the problem of finding supermartingale certificates (traditionally a constrained optimization problem) as a problem of policy evaluation followed by a certificate check, the authors suggest a pathway to scale verification to large and continuous state spaces using data-driven RL methods.

The authors emphasize that while the theorems provide sufficient conditions for the value function to be a certificate, the certificate itself is valid if the proof rules hold, regardless of whether the theorem's assumptions (like uniform hitting time bounds) are independently verified. This allows for a practical workflow: train a policy, estimate its value function, and verify the supermartingale conditions directly.

The paper positions this work as a foundational step toward certified reinforcement learning, where trained policies can be formally verified for $\omega$ -regular properties beyond finite state spaces, bridging the gap between the scalability of RL and the rigor of formal verification.