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 · Ruhr University Bochum & Radboud University Nijmegen, Germany · Masaryk University, Czech Republic
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.
Semantics
Breaking Point Type
Strategy Evaluation
Strategy Synthesis
Safety
Reachability
Safety
Reachability
Expected
Transient
SSP for MDP (P)
SSP for MDP (P)
SSP for SG
SSP for SG
Frequency
Cannot happen
Collapse MECs + SSP for MDP (P)
Cannot happen
Collapse MECs + SSP for SG
Worst-case
Transient
Iterative LP (PSPACE)
Iterative LP (PSPACE)
Iterative QP (PSPACE)
Iterative QP (PSPACE)
Frequency
Always 0
Collapse MECs + Worst-case analysis (P)
Always 0
Collapse 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 G with probability >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 s0 and with a probability of 0.2 in s1 .
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 π must have memory even if δ is memoryless (left), and one where the optimal δ must rely on memory even if π 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,r we denote that the action a yields a cost of r
Figure 7. The weighted MEC quotient of the MDP in Figure 6 (a) and function f={A^→104,B^→105,C^→1010} . stay action labels omitted for readability.
Figure 8. Disturbance frequency is 1 in the absolute worst case (always stay in s1 ) but it is realized with 0 probability. Here, if the action d is always played in state s1 , the steady state distribution is 1910 and 199 in state s1 and s2 respectively. This gives us the realistic worst case frequency as 1910 .
A stochastic game is an optimal control problem for multiple agents in a stochastic environment. Stochastic games contain important practical problems, related to environmental issues or traffic flows. If the number of environmental states is one, such stochastic games are called repeated games. In repeated games, several strategies which unilaterally control payoffs have been proposed, and these strategies work in a mechanism similar to feedback control. In this paper, we generalize these strategies as feedback strategies in stochastic games, and investigate their properties. In particular, we provide a necessary and sufficient condition for such feedback strategies to work as controllers of payoffs under some assumptions. We demonstrate the performance of such feedback strategies in several examples related to social dilemmas. Our findings connect the theory of payoff control in repeated games to the theory of feedback control in stochastic games.
Masahiko Ueda
Department of Physics, Tokyo Metropolitan University, Tokyo 192-0397, Japan
Embodied Agents System (EAS) are increasingly deployed in open-world physical domains, where reliability directly dictates deployment quality and human-agent trust. However, existing evaluations rely on outcome-centric metrics as success rate or safety scores that collapse diverse execution trajectories into coarse scores, obscuring the dynamic processes underlying agent behavior. Therefore, they ignore a critical property of EAS -- which we define as the Resilience -- that reflects how EASs recover, stabilize, and extend under perturbations and across iterative updates. The lack of resilience is particularly critical in open-world environments due to continuous unexpected disruptions, thus directly affecting the quality of EAS deployment. To address this problem, we gain insight from the resilience-engineering concepts to EAS groundings and propose a novel resilience evaluation framework that can be flexibly applied to any EAS. Specifically, we define the first comprehensive resilience metrics suite for EASs system that exposes Rebound, Stability, and Graceful Extensibility across embodied tasks execution, providing a practical grounding for EAS resilience analysis. We further implement the resilience evaluation layer that transforms execution process into assessments for diagnosis and optimization. Across 400 household tasks with 10 EAS, we reveal the process-level distinction hidden by outcome metrics, including recovery cost differences among successful episodes (ΔCrec=25.2), increased instability and task-family degradation. Metrics-guided optimizations reduce recovery cost and increase stability, graceful extensibility completion, showing the diagnostic effect of resilience evaluation. Our results reveal a trade-off among resilience characteristics, suggesting that a resilient EAS construction should be configured according to deployment-specific requirements.
Yapeng Liu, Yuanzhao Zhai, Xudong Gong +4
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
We propose and study distributionally robust Markov games (DR-MGs) with the average-reward criterion as a crucial framework for multi-agent decision-making under model mismatches and over extended horizons. Under a standard irreducible assumption, we first derive a correspondence between the optimal policies and the solutions of the robust Bellman equation, based on which we further show the existence of a stationary Nash Equilibrium (NE) of the game. We further study DR-MGs under a more general weakly communicating setting. We construct a set-valued map based on the constant-gain optimal robust Bellman operator and show that its value is a subset of the best-response policies. We further prove that this map admits a fixed point, which implies the existence of NE. We then design two algorithms, Robust Nash-Iteration and robust TD Descent, with provably convergent guarantees. Finally, we show that the NE under average-reward can be approximated by the ones for the discounted DR-MGs as the discount factor approaches one. Our studies provide a comprehensive theoretical and algorithmic foundation for decision-making in complex, uncertain, and long-running multi-player environments.
Zachary Roch, Yue Wang
Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.