⚡ electrical engineering

Robust Verification of Concurrent Stochastic Games

This paper introduces robust concurrent stochastic games (specifically interval CSGs) to handle epistemic uncertainty in transition probabilities, providing a theoretical framework and efficient algorithms for worst-case robust verification of both zero-sum and nonzero-sum objectives, which are implemented in the PRISM-games model checker and validated on large benchmarks.

Original authors: Angel Y. He, David Parker

Published 2026-01-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Angel Y. He, David Parker

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

The Big Picture: Planning in a Foggy World

Imagine you are the captain of a drone fleet. You need to coordinate your drones to deliver packages safely. In a perfect world, you would know exactly how the wind blows, how the batteries drain, and exactly what the other drones will do. You could calculate a perfect plan.

But in the real world, things are messy. You don't know the exact wind speed (it's a guess), your sensors have noise, and you don't know if the other drones are following your plan or trying to jam your signals. This is uncertainty.

The paper addresses a problem: How do you prove your system is safe when you don't know the exact rules of the game?

The Old Way: The "Perfect Map" Problem

Previously, computer scientists used a model called a Concurrent Stochastic Game (CSG) to check if these systems work. Think of a CSG as a board game where multiple players move at the same time.

The Problem: To play this board game, you need a map that tells you the exact probability of landing on every square.
The Flaw: In real life, we rarely have exact probabilities. We have estimates. If you build your safety plan on a map that is slightly wrong, your plan might fail when the real world (the "fog") hits.

The New Solution: The "Worst-Case" Map

The authors introduce a new model called Robust Concurrent Stochastic Games (RCSGs), specifically a type called Interval CSGs (ICSGs).

The Analogy: The Interval Map
Instead of saying, "There is a 50% chance of rain," the new model says, "There is a 40% to 60% chance of rain."

This creates a "cloud" of possibilities rather than a single point.
The system doesn't just check if the plan works for the average weather. It checks if the plan works even if the weather turns out to be the absolute worst within that 40-60% range.

This is called Robust Verification. It asks: "Can we guarantee safety even if nature (the environment) tries its hardest to mess us up?"

The Players: Agents, Opponents, and "Nature"

In these games, there are usually two types of players:

The Agents: The drones or robots trying to achieve a goal.
Nature: The environment (wind, noise, data errors).

In the old models, "Nature" was just a random coin flip. In this new model, Nature is an adversary.

Zero-Sum Games (Team vs. Team): Imagine a game of chess. One player wants to win; the other wants to stop them. Here, "Nature" teams up with the opponent to make the game as hard as possible for the first player.
Non-Zero-Sum Games (Cooperation vs. Chaos): Imagine two drones trying to deliver packages together. They want to maximize their combined success. Here, "Nature" acts like a mischievous gremlin trying to minimize their total success, even if it hurts both of them.

How They Solved It: The "Shadow Game"

The authors faced a huge mathematical challenge: How do you calculate the "worst-case" outcome when players move simultaneously and the environment is unpredictable?

The Trick: The Shadow Game
They invented a clever way to turn this messy, uncertain problem into a standard, solvable board game.

They added a third player to the game board: Nature.
In this "Shadow Game," Nature gets to move after the agents pick their actions. Nature looks at all the possible outcomes and picks the one that hurts the agents the most.
By doing this, they transformed a complex "uncertain" problem into a standard "multi-player game" that existing computer tools (like the PRISM-games checker) could already solve.

The Result:

For competitive games (Zero-Sum): They turned the problem into a 2-player game (Agent vs. Team of Opponent + Nature). It runs almost as fast as the old method.
For cooperative games (Non-Zero-Sum): It becomes a 3-player game. This is harder and takes more computer time, but they developed a filtering system to find the best "Robust Nash Equilibrium" (a state where no one wants to change their strategy, even knowing the worst might happen).

What They Tested

They built this into a software tool and tested it on large, complex scenarios like:

Robot coordination: Getting robots to move without crashing.
Network traffic: Managing data flow in a busy network.
Radio jamming: Protecting signals from interference.

The Findings:

It works: The software successfully calculated safe strategies even with uncertain data.
Speed: For competitive scenarios, it was only about twice as slow as the old method (which is very fast for computers). For cooperative scenarios, it was slower but still handled large systems.
The "Fog" Factor: They found that having a little bit of uncertainty (a small "fog") sometimes makes the calculation faster because the system converges on a solution quicker. However, too much uncertainty makes the "worst-case" scenarios very conservative (very safe, but maybe too cautious).

Summary

This paper gives us a new way to check if autonomous systems (like self-driving cars or drones) are safe when we don't have perfect information. Instead of guessing the exact odds, they assume the environment will be as tricky as possible within a known range. They turned this difficult math problem into a standard game that computers can solve, ensuring that our future robots won't crash just because the wind blew a little differently than expected.

Technical Summary: Robust Verification of Concurrent Stochastic Games

1. Problem Statement

Autonomous systems operating in multi-agent environments (e.g., drone coordination, robotic exploration) often require simultaneous strategic decisions under uncertainty. While Concurrent Stochastic Games (CSGs) provide a powerful framework for modeling such systems, standard verification techniques assume that transition probabilities are precisely known. In reality, these probabilities are often subject to epistemic uncertainty due to modeling inaccuracies, noise, abstraction, or limited data (common in reinforcement learning).

Standard CSG verification yields guarantees that may be unreliable if the underlying model is slightly incorrect. While Robust Markov Decision Processes (RMDPs) address this for single-agent systems by considering sets of possible transition probabilities, analogous frameworks for multi-agent concurrent settings have been underdeveloped. The challenge lies in extending robustness to concurrent games where players act simultaneously, and the "nature" player (resolving uncertainty) interacts with multiple strategic agents.

2. Methodology

The paper introduces Robust Concurrent Stochastic Games (RCSGs) and focuses on a tractable subclass called Interval CSGs (ICSGs), where transition probabilities are bounded within intervals. The methodology involves theoretical foundations, game-theoretic reductions, and algorithmic implementations.

2.1 Theoretical Framework

The authors define robust solution concepts for both zero-sum and nonzero-sum settings under worst-case assumptions about transition uncertainty:

Zero-Sum: The framework adapts minimax concepts. A game is robustly determined if the value remains consistent regardless of the order in which players and "nature" (the adversary resolving uncertainty) act. The paper proves that player-first and nature-first semantics yield the same robust value for finitely-branching ICSGs.
Nonzero-Sum: The paper introduces Robust Nash Equilibria (RNE) and Robust Social-Welfare Optimal NE (RSWNE). An RNE is a strategy profile that remains a Nash equilibrium under any uncertainty resolution. The authors focus on subgame-perfect $\epsilon$ -RNE to ensure existence.

2.2 Reduction to Standard Games

A core contribution is the reduction of robust verification problems to standard (non-robust) CSGs via an Adversarial Expansion:

Zero-Sum Reduction: An ICSG is reduced to a 2-player CSG ( $G_A$ ) by adding a third "nature" player who acts adversarially against Player 1. Since Player 2 and Nature share the objective of minimizing Player 1's payoff, they form a coalition. The robust value of the original ICSG equals the value of this expanded 2-player CSG.
Nonzero-Sum Reduction: The reduction creates a 3-player CSG ( $G_A$ $G_{A}$ ) where Player 3 (Nature) acts adversarially against both Player 1 and Player 2 by minimizing their social welfare (sum of utilities).
- Challenge: A Nash Equilibrium in the expanded 3-player game does not automatically imply a Robust NE in the original game, as Nature's minimization of the sum of utilities does not necessarily minimize individual utilities.
- Solution: The authors propose a filtering step. After computing equilibria in $G_A$ , they filter profiles by checking if they satisfy the RNE condition using deviation IMDPs (Interval MDPs). This ensures the profile is robust against nature's worst-case choices for each individual player.

2.3 Algorithms

The paper develops efficient algorithms for solving these reduced games:

Infinite-Horizon: Uses Robust Value Iteration (RVI). For each state and joint action, an inner optimization problem (finding the worst-case transition distribution within the interval) is solved, followed by a linear programming (LP) or bimatrix game solution.
Finite-Horizon: Uses Robust Backward Induction (RBI).
Implementation: The algorithms are implemented in the PRISM-games model checker. The approach avoids explicit construction of the full expanded state space by solving inner problems and normal form games (NFGs) on-the-fly.

3. Key Contributions

Model Definition: Introduction of RCSGs and ICSGs to model multi-agent systems with interval-bounded transition uncertainty.
Theoretical Foundations:
- Proof of value equivalence between player-first and nature-first semantics in zero-sum ICSGs.
- Establishment of Robust Nash Equilibria and RSWNE concepts.
- Demonstration that robust verification can be reduced to solving standard CSGs (2-player for zero-sum, 3-player with filtering for nonzero-sum).
Algorithmic Implementation: Development of tractable algorithms for finite and infinite horizons, integrating robust dynamic programming with standard CSG solution techniques (value iteration, Lemke-Howson).
Empirical Evaluation: Implementation in PRISM-games and evaluation on large benchmarks (Robot coordination, Aloha, Jamming radio systems).

4. Experimental Results

The authors evaluated the approach against standard (non-robust) CSGs using benchmarks with perturbed transition probabilities ( $\pm \epsilon$ ).

Zero-Sum Performance: Verification times for ICSGs were comparable to standard CSGs, typically within a factor of two. The method successfully handled models with over 2 million states and 10 million transitions. In some cases (e.g., Aloha), ICSG verification was faster due to fewer iterations required for convergence.
Nonzero-Sum Performance: Verification times were higher due to the complexity of the 3-player reduction and the filtering step. The approach scaled effectively to models with up to 0.4 million states and 1.3 million transitions.
Impact of Uncertainty ( $\epsilon$ ):
- Verification time was non-monotonic with respect to $\epsilon$ ; intermediate values were often slower than very small or very large values due to the trade-off between per-iteration cost and convergence speed.
- Increasing $\epsilon$ yielded more conservative (lower) values, effectively providing confidence intervals for verification results.

5. Significance and Claims

The paper claims to fill a critical gap in formal verification by providing a principled framework for reasoning about epistemic uncertainty in multi-agent concurrent systems.

Practicality: The authors demonstrate that robust verification is feasible for large-scale systems, not just theoretical constructs. The zero-sum case scales comparably to standard verification, making it immediately applicable to safety-critical adversarial scenarios.
Insight: The nonzero-sum results highlight the intrinsic complexity of robust multi-agent reasoning, particularly the distinction between minimizing social welfare and individual robustness, which necessitates the proposed filtering mechanism.
Foundation: By reducing RCSGs to standard CSGs, the work leverages existing tool support (PRISM-games) and theoretical results, offering a scalable path forward for robust analysis of autonomous systems.

The authors conclude that while the nonzero-sum case introduces higher computational demands, the framework successfully enables the synthesis of strategies that are robust against model inaccuracies, a crucial requirement for deploying autonomous systems in uncertain real-world environments.