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.