cs.GTFeb 27, 2026

Resilient Strategies for Stochastic Systems: How Much Does It Take to Break a Winning Strategy?

Authors: Kush Grover, Markel Zubia, Debraj Chakraborty, Muqsit Azeem, Nils Jansen, Jan Kretinsky

Organizations: Fondazione Bruno Kessler, Italy · Ruhr University Bochum, Germany · Nanyang Technological University, Singapore · Technical University of Munich & University of Konstanz, Germany · 

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Figure 1. Drone navigation task with wind disturbances.
SemanticsBreaking Point TypeStrategy EvaluationStrategy Synthesis
SafetyReachabilitySafetyReachability
ExpectedTransientSSP for MDP (P)SSP for MDP (P)SSP for SGSSP for SG
FrequencyCannot happenCollapse MECs ++ SSP for MDP (P)Cannot happenCollapse MECs ++ SSP for SG
Worst-caseTransientIterative LP (PSPACE)Iterative LP (PSPACE)Iterative QP (PSPACE)Iterative QP (PSPACE)
FrequencyAlways 00Collapse MECs ++ Worst-case analysis (P)Always 0Collapse MECs ++ Worst-case analysis (NP)
Table 1. Overview of strategy evaluation and optimal strategy computation under different semantics and breaking point types.
Figure 2. For this SGD, if the objective is to reach GG with probability >0.4>0.4 , then the worst-case breaking point is 2, as disturbing just once will not break the policy, and the expected breaking point is 1.1 via an adversary that always disturbs in s0s_{0} and with a probability of 0.2 in s1s_{1} .
Figure 3. A gadget in the unfolded stochastic game.
Figure 4. Gadget for converting an SGD into an SG for the Expected Breaking Point.
Figure 5. An SGD where the most resilient π\pi must have memory even if δ\delta is memoryless (left), and one where the optimal δ\delta must rely on memory even if π\pi is memoryless (right).
Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6. An example of how the MEC quotient is constructed. By a,ra,\mathbf{r} we denote that the action aa yields a cost of r\mathbf{r}
Figure 7. The weighted MEC quotient of the MDP in Figure 6 (a) and function f={A^→410,B^→510,C^→1010}f=\{\hat{A}\rightarrow\frac{4}{10},\hat{B}\rightarrow\frac{5}{10},\hat{C}\rightarrow\frac{10}{10}\} . staystay action labels omitted for readability.
Figure 8. Disturbance frequency is 1 in the absolute worst case (always stay in s1s_{1} ) but it is realized with 0 probability. Here, if the action dd is always played in state s1s_{1} , the steady state distribution is 1019\frac{10}{19} and 919\frac{9}{19} in state s1s_{1} and s2s_{2} respectively. This gives us the realistic worst case frequency as 1019\frac{10}{19} .
More in this topic

Robust Markov Decision Processes

Robust Markov decision processes optimize decisions under uncertain dynamics, seeking reliable performance against adverse transition models.

See all 26 papers

Explore similar work

CardsList

  1. Feedback autocratic strategies in stochastic games

    Oct 27, 2026Masahiko UedaFeedback Control

    Department of Physics, Tokyo Metropolitan University, Tokyo 192-0397, Japan

  2. Resilience Matters for Embodied Agents System: New Metrics, Systematic Evaluation, and Optimization

    Aug 24, 2026Yapeng Liu, Yuanzhao Zhai, Xudong Gong +4AI Agent EvaluationAI Agent Reliability

    PDL Lab, College of Computer Science and Technology, National University of Defense Technology · State Key Laboratory of Complex & Critical Software Environment, Changsha 410073, Hunan, China · EmPACT Lab, Nanyang Technological University, Singapore

  3. Distributionally Robust Markov Games with Average Reward

    Aug 5, 2025Zachary Roch, Yue WangNash Equilibrium ComputationMulti-Agent System Optimization

    Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.