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.
From the original article
1 min read at arxiv.orgWe 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.
By Brandon Gary Kaplowitz · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.