Resilient Strategies for Stochastic Systems: How Much Does It Take to Break a Winning Strategy?
| Authors | Kush Grover et al. |
| Year | 2026 |
| Field | AI / ML |
| arXiv | 2602.24191 |
| Download | |
| Categories | cs.GT, cs.AI, cs.LO |
Abstract
We study the problem of resilient strategies in the presence of uncertainty. Resilient strategies enable an agent to make decisions that are robust against disturbances. In particular, we are interested in those disturbances that are able to flip a decision made by the agent. Such a disturbance may, for instance, occur when the intended action of the agent cannot be executed due to a malfunction of an actuator in the environment. In this work, we introduce the concept of resilience in the stochastic setting and present a comprehensive set of fundamental problems. Specifically, we discuss such problems for Markov decision processes with reachability and safety objectives, which also smoothly extend to stochastic games. To account for the stochastic setting, we provide various ways of aggregating the amounts of disturbances that may have occurred, for instance, in expectation or in the worst case. Moreover, to reason about infinite disturbances, we use quantitative measures, like their frequency of occurrence.
Engineering Breakdown
Plain English
This paper introduces a formal framework for studying resilient strategies in stochastic systems, where agents must make decisions that remain robust even when disturbances occur—such as when an actuator fails and prevents the intended action from executing. The authors define resilience metrics in the context of Markov decision processes (MDPs) with reachability and safety objectives, then extend the framework to stochastic games where multiple agents interact. Rather than assuming perfect execution, they provide mathematical definitions and solution methods that quantify how much disturbance a winning strategy can tolerate before it fails. The work bridges decision theory and robustness by asking: given that an agent wants to reach a goal or maintain safety, how much uncertainty or adversarial perturbation can it absorb before its strategy breaks down?
Core Technical Contribution
The core novelty is formalizing resilience as a quantifiable property of strategies in stochastic environments, specifically for MDPs and games where decisions can be disrupted. Prior work on robust control and adversarial robustness typically focused on continuous state spaces or assumed specific perturbation models; this paper provides a discrete, probabilistic framework that unifies reachability (reaching a goal state) and safety (avoiding bad states) objectives under a single resilience metric. The authors introduce multiple aggregation methods for quantifying resilience in stochastic settings—rather than a single worst-case measure, they provide tools to reason about expected, probabilistic, and worst-case resilience. This enables characterizing not just whether a strategy works, but exactly how much tolerance it has before failure, which is a departure from binary robustness guarantees.
How It Works
The framework begins by defining a strategy (a policy) in an MDP as a mapping from states to actions that achieves an objective like reaching a goal with high probability. Resilience is then quantified by introducing perturbations that flip the agent's chosen action—replacing the intended action with an alternative—and measuring the degree of perturbation required to cause the strategy to fail (dropping below a success threshold). For reachability objectives, the system solves: given a policy π that reaches goal state G with probability p, what is the maximum perturbation probability such that the perturbed policy still reaches G with at least p−ε probability? For safety objectives, it's analogous: what perturbation threshold causes the strategy to violate safety guarantees? The authors provide aggregation methods (expected resilience, probabilistic resilience, worst-case resilience) that extend to stochastic games where adversaries are present. The output is a resilience value per strategy, enabling ranking and comparison of policies by robustness rather than optimality alone.
Production Impact
For teams deploying autonomous systems (robotics, autonomous vehicles, industrial control), this work directly addresses a critical gap: agents trained to be optimal often assume perfect action execution, but in reality, actuators fail, network packets are lost, or human overrides occur. By computing and optimizing for resilience metrics alongside standard performance metrics, engineers can deploy safer systems that gracefully degrade under failures rather than catastrophically failing. In a production RL pipeline, you would extend your reward function to include a penalty for low resilience (similar to how safety constraints are added), then verify that the learned policy maintains acceptable resilience even when 5-10% of actions are randomly flipped. The trade-off is computational: computing resilience requires additional MDP simulations or game-theoretic analysis (solving potentially large systems of equations), adding latency to policy evaluation. For critical systems (medical robots, autonomous driving), this overhead is worthwhile; for low-stakes applications, it may be overkill.
Limitations and When Not to Use This
The framework assumes discrete state and action spaces (standard for MDPs), which limits applicability to high-dimensional continuous control without discretization overhead. The perturbation model—flipping actions uniformly or according to a fixed distribution—is simplistic and may not reflect real failure modes, which are often state-dependent, correlated, or adversarially structured. The paper does not provide tractable algorithms for computing resilience in large-scale games or for temporal dependencies in failure patterns (e.g., cascading failures where one action failure triggers others). Additionally, the work assumes the agent knows its strategy upfront and can modify it; in online learning or adaptive settings where policies change frequently, resilience guarantees may not transfer. The extension to stochastic games is mentioned but appears incomplete, and scalability to real-world problem sizes remains an open question.
Research Context
This paper builds on classical robust control theory (studying system stability under perturbations) and recent work on adversarial robustness in RL, but applies these ideas specifically to discrete stochastic domains with formal game-theoretic semantics. It connects to literature on formal verification of MDPs (which asks: does a policy satisfy a temporal logic formula?) by treating resilience as a quantifiable property alongside safety and liveness. The work likely benchmarks on standard MDP domains (grid worlds, games, scheduling problems) and may introduce new metrics for comparing policies. It opens directions for resilience-aware learning algorithms (training policies that are inherently robust), compositional resilience analysis (building resilient strategies from simpler components), and applications to multi-agent coordination where agents must tolerate each other's failures.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::