Epsilon-Nash Equilibria in History-Dependent SA-MDPs
Researchers give the first algorithm for computing epsilon-approximate history-dependent equilibria in state-adversarial Markov decision processes with observation-perturbing adversaries.
The paper studies state-adversarial Markov decision processes (SA-MDPs) where an adversary knowing the true state perturbs observations within state-dependent proximity sets each step. The authors prove universal history-dependent equilibrium policies do not exist and reduce SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game, enabling the first algorithmic route to epsilon-approximations of initial-state dependent equilibria. The algorithm is validated on small analytically verifiable games and scales to larger benchmarks, including Atari Freeway rollouts with a 12-period-ahead horizon.
- Proves universal history-dependent equilibrium policies do not exist in state-adversarial MDPs.
- Reduces SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game.
- First algorithm computing epsilon-approximations of initial-state dependent equilibria.
- Validated on small verifiable games and Atari Freeway rollouts with 12-period horizon.
Full article173 words · extracted from arxiv.org · click to collapse
We study state-adversarial Markov decision processes (SA-MDP) as a game of observation-space attacks: at each step, an agent selects an action from a received observation while an adversary$\unicode{x2014}$who knows the true state the agent is in$\unicode{x2014}$chooses a perturbed observation within a state-dependent proximity set. While existing work focuses on Markovian policies, we develop a solution concept and computational approach for SA-MDPs under history dependence. This is motivated by results showing that history dependence can materially change equilibrium outcomes and can force both the agent and the adversary to adapt their strategies. First, we prove the non-existence of universal (agnostic of the initial state distribution) history-dependent equilibrium policies. In response to this finding, our main result presents the first algorithmic route to computing $ε$-approximations of initial-state dependent equilibria. We do so by reducing SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game. We conclude by testing our algorithm on small analytically verifiable games and showing it scales to larger, more realistic benchmarks, including Atari Freeway rollouts with a 12-period ahead horizon.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.18829