Abstract
This paper addresses the challenge of planning in stochastic games with complex requirements. While finding strategies for general probabilistic goals is typically undecidable when players have perfect recall, the authors prove that restricting goals to "co-safe" properties—requirements that can be satisfied in finite time—renders the problem decidable. We present the theoretical framework for this result, establishing memory bounds and finite-depth witnesses, and demonstrate that this decidability holds for both deterministic and randomized strategies.
Introduction
In artificial intelligence, systems are often modeled using Markov Decision Processes (MDPs) or stochastic games to account for both intentional choices and random chance. A primary goal is to find a "strategy" that ensures a specific objective is met with a certain probability. The standard language for these goals is Probabilistic Computation Tree Logic (PCTL), which can describe complex behaviors like "reach the exit with 90% certainty" or "never enter a fail state."
The Theoretical Wall
Despite its power, PCTL faces a major theoretical hurdle. If a player is allowed to remember the entire history of the game (perfect recall), deciding if a winning strategy exists for a general PCTL goal is undecidable. As shown in Figure 1, while memoryless strategies are decidable, the transition to perfect recall for general PCTL objectives makes the problem unsolvable by any algorithm.
Historically, researchers have avoided this by focusing on simple reachability goals or restricting players to memoryless strategies. This paper seeks a middle ground: handling sophisticated goals and perfect memory without hitting the wall of undecidability.
Methodology
The authors focus on co-safe properties, a subset of PCTL. These are requirements that, if satisfied, are guaranteed to be satisfied within a finite number of steps (e.g., "eventually reach the goal" or "recharge within 10 minutes"). The key methodological steps include:
- Finite-Depth Witnesses: Proving that for any co-safe property, a winning strategy can be represented by a finite-length path or tree.
- Model Unfolding: Unfolding the stochastic game into a tree structure up to a calculated depth based on the co-safe property.
- Memory Bounds: Establishing a mathematical upper bound on the memory required for a strategy. By showing memory requirements are finite, the search space becomes manageable.
- Robustness Analysis: Introducing "robust" planning, where strategies must remain valid even under slight perturbations (noise) in transition probabilities.
Key Results
The central contribution of this work is proving that planning for stochastic games with co-safe PCTL objectives is decidable for both Deterministic Perfect Recall (DP) and Randomized Perfect Recall (RP) strategies.
As summarized in Figure 2, while general PCTL remains undecidable under perfect recall, co-safe PCTL is decidable. For deterministic strategies, the authors provide an algorithm and show the problem is in 3-EXPTIME. Although this complexity class is high, it moves the problem from "impossible" to "theoretically solvable." Additionally, the authors prove that the satisfiability of co-safe PCTL is decidable, answering a long-standing question in the logic community.
Discussion and Future Work
While the 3-EXPTIME complexity presents a hurdle for immediate practical application, the shift to decidability is a significant theoretical milestone. The results are limited to co-safe properties; "safe" properties (which must hold over an infinite timeline) remain outside this specific proof's scope.
Future research will focus on identifying more efficient algorithms or larger fragments of PCTL that remain decidable under perfect recall. There is also significant interest in applying these theoretical bounds to develop practical, heuristic-based planners for real-world stochastic environments.
Summary updated