# Value Functions as Supermartingale Certificates Source: [Value Functions as Supermartingale Certificates]() Collection index: [llms.txt]() Data updated: 2026-06-02T05:00:12.522Z Authors: Alessandro Abate, Daniel Contro, Mirco Giacobbe, Agust\\'in Mart\\'inez-Su\\~n\\'e, Diptarko Roy Published: 2026-05-29T16:39:02.000Z ## Abstract Certification methods for stochastic systems provide sufficient proof rules, based on real-valued supermartingale certificates, to determine the almost-sure satisfaction of $\\omega$-regular properties (and therefore of linear temporal logic) over general state spaces, encompassing both countably infinite and continuous state spaces. Conversely, reinforcement learning (RL) methods for $\\omega$-regular tasks have received considerable attention, but they typically lack formal guarantees that the learned policy satisfies the specification, except possibly for finite state and action spaces. We bridge these two lines of research by establishing a novel theoretical connection: under an appropriate reward, the value function associated to a policy that almost surely satisfies an $\\omega$-regular property encodes a Streett supermartingale certificate for that specification. Our results, validated experimentally on finite Markov decision processes, hold for finite, countably infinite, and continuous state spaces, suggesting a principled route to certificate synthesis via RL. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [LTL Property Verification on Grid-world environment](): LTL Property Verification; Grid-world environment; PRISM Satisfaction Probability: 100. ## Original sources and implementation [Original paper]() [PDF]()