Algorithm finds approximate equilibria in state-adversarial decision games
Epsilon-Nash Equilibria in History-Dependent SA-MDPs
Computer Science and Game TheoryCryptography and Security
Summary
This work looks at decision-making scenarios where an agent tries to act based on observations that an adversary can manipulate. The authors show that strategies depending on full history behave quite differently than strategies just on the current observation, and universal solutions don’t exist. They develop an algorithm to find approximate best strategies for both sides when these depend on the initial state. Their approach reformulates the problem as a special kind of game, and they test it on simple examples as well as a version of the Atari Freeway game.
What this means in practice
- •For game ai developers: Design AI agents robust against strategic observation manipulations by adversaries in games and simulations.
- •For cybersecurity system designers: Develop methods to model and counteract strategic sensor or observation attacks on autonomous system decision processes.
Authors
Brandon Gary Kaplowitz, Dominik Bohnet Zurcher, Akash Agrawal, Tala Jafari, Christian Schroeder de Witt, Paul W. Goldberg
Abstract
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.