PaperlayerView exact revision on arXiv

Source-linked AI summary

Epsilon-Nash Equilibria in History-Dependent SA-MDPs

Brandon Gary Kaplowitz, Dominik Bohnet Zurcher, Akash Agrawal, Tala Jafari, Christian Schroeder de Witt, Paul W. Goldberg

arXiv:2609.18829v2cs.GTcs.CR

TL;DR

The paper addresses the limits of Markovian robustness models for SA-MDPs by studying history-dependent strategies and reducing the problem to a constrained zero-sum one-sided partially observable stochastic game. It reports that history dependence matters for optimal policies and adversarial impact, and that its algorithm recovers Nash equilibrium strategies, while general-game solve time grows roughly exponentially with the history horizon.

  • Problem

    Prior SA-MDP work focuses on stationary policies, although agents may gain reward by conditioning on past observations and adversaries may need to adapt.

    Source: §1 · p. 2

  • Method

    The authors reduce history-dependent SA-MDPs to a constrained zero-sum one-sided partially observable stochastic game and adapt an HSVI-based solver to compute approximate equilibria.

    Source: §2 · p. 4, §2.5 · p. 8

  • Results

    The numerical examples show that history dependence affects optimal policies and adversarial impact, and that the algorithm recovers Nash equilibrium strategies.

    Source: §4 · p. 11

  • Takeaways & Limitations

    The reduction provides a route to studying history-dependent SA-MDP solutions and could be scaled using compressed beliefs, approximate solvers, or horizon truncation at the cost of guarantees and uniform bounds for HSVI.

    Source: §4 · p. 11

    For general games, solver wall time scales roughly exponentially with the maximum history length, making the approach most suitable for short- to moderate-horizon problems.

    Source: §3.3 · pp. 10–11

Abstract

from arXiv · show

We study state-adversarial Markov decision processes (SA-MDPs) as games 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. 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. Our main result presents the first algorithmic route to computing $\epsilon$-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 test our algorithm on small analytically verifiable games and show that it scales to larger, more realistic benchmarks, including Atari Freeway rollouts with a 12-period ahead horizon.

1 Introduction

The paper studies SA-MDPs as observation-space attack games and extends their analysis from memoryless strategies to history-dependent policies. It situates this approach among prior adversarial-observation work and introduces the notation and game setting used in the paper.

1 Introduction

  • In an SA-MDP, an adversary who knows the true state chooses a permitted perturbed observation, then the agent acts on that observation as the environment transitions.The adversary seeks to minimize the agent’s discounted expected reward; the observation perturbation does not directly change the state transition.Source: §1 · p. 1

1.1 Related Work

  • Prior SA-MDP work usually restricts both players to Markovian policies, while this paper studies history-dependent strategies using a reduction-based route to approximate equilibria.The paper builds on the one-sided partially observable stochastic-game framework and its HSVI solver.Source: §1 · p. 2, §1.1 · p. 2

1.2 Background and Notation

  • The paper models observation attacks with a state-adversarial MDP in which the adversary selects observations from state-dependent perturbation sets and the agent acts on them.Unlike a standard POMDP with fixed observation probabilities, the agent’s observation distribution depends on the adversary’s policy.Source: §1.2 · pp. 2–3

2 Theoretical results

The theoretical results show why history-dependent SA-MDPs require equilibria tailored to an initial-state distribution, then reduce the game to a constrained one-sided POSG to compute approximate equilibria. The reduction preserves strategies, payoffs, and ε-equilibrium status, and supports an HSVI-based solution approach.

2.1 Non-Existence of Universal History Dependent Nash Equilibrium Policies

  • No SA-MDP always admits a history-dependent policy that is state-robust optimal, so an equilibrium policy independent of the initial-state distribution need not exist.For each fixed initial distribution, robust optimality and Nash equilibrium coincide under the stated full-history behavioral-strategy setting.Source: §2.1 · p. 4

2.2 Why History Matters

  • History-dependent policies can exploit observation-sequence patterns, prompting the adversary to adapt its strategy as well.The example describes how an additional state can let the adversary reduce the agent’s certainty about a transition.Source: §2.2 · pp. 4–5

2.3 Modified Zero-Sum OS-POSG to Find Epsilon-Equilibria

  • Any SA-MDP can be transformed into a strategically equivalent constrained zero-sum one-sided POSG whose solution strategies map back to the original game.The transformed game requires simultaneous actions at each stage.Source: §2.3 · p. 5

Defining the Transformation

  • The transformation encodes each sequential stage as two micro-stages, using dummy actions and states to preserve the sequential decision structure.The attacker first selects the observation; the agent then acts on it, and the original transition kernel governs the next state.Source: §2.3 · p. 5, Defining the Transformation · p. 6

Strategic Equivalence

  • The reduction preserves behavioral-strategy correspondence, pairwise payoffs, and ε-equilibrium status between the original and transformed games.A strategy found in the transformed game has a unique corresponding strategy in the original game, with equal equilibrium values.Source: Strategic Equivalence · p. 7

2.4 Constrained Zero-sum OS-POSG

  • The constrained OS-POSG solution yields feasible strategies that form an ε-Nash equilibrium for the constructed game.The HSVI extension maintains lower and upper value bounds while restricting local stage games to feasible strategy sets.Source: §2.4 · p. 8
  • The sufficient termination bound is worst-case and becomes conservative as γ approaches one.The paper notes practical convergence is substantially better than the bound and uses γ = 0.999 for finite-horizon problems.Source: §2.4 · p. 8

2.5 Algorithm

  • The algorithm converts an SA-MDP into an equivalent constrained OS-POSG, then applies HSVI modified for state-dependent feasibility constraints.The conversion uses phase-dependent singleton feasible action sets and adversarial proximity constraints.Source: §2.5 · p. 8

3 Experiments

The experiments show that history dependence changes equilibrium outcomes, with opposite effects in the analytic game and Atari Freeway. The solver recovers equilibrium strategies and scales to larger games, while its runtime and memory constrain the problems it can handle.

3.1 Example SA-MDP Where History Matters

  • 0.25 under Markovian strategies falls to 0 under history-dependent strategies in the analytically verifiable game, making the agent strictly worse off.The analytic history-dependent value holds even when the agent is allowed history-dependent strategies.Source: §3.1 · p. 9
  • The algorithm recovers one of multiple equilibrium strategies for each player, selecting strategies on the boundary of the optimal-strategy region.The recovered strategies are shown in Figure 4 and provided explicitly in Appendix B.Source: §3.1 · p. 9, Figure 4 · p. 9
  • 0 ± O(10^-8) is the history-dependent midpoint at ϵ=0.01, while the Markovian solver returns 0.2496 ± O(10^-6), matching its analytic γ=0.999 value.For γ=1, the analytic Markovian value is 0.25; γ=1 breaks HSVI, and γ near 1 leaves some numerical error.Source: §3.1 · p. 9

3.2 Larger Problems

  • Each two added horizons increased solve time by roughly 20–30×; tests reached depth 10 with 3.1 million states and 1.4 million information sets.That depth-10 solve took 2,200 seconds on one MacBook M4 Pro CPU core; Table 1 reports runtime and exploration scaling by depth over five seeds.Source: §3.2 · pp. 9–10, Table 1 · p. 10
  • At depth 12, Atari Freeway took 2.07 seconds to solve after behavioral consolidation left 5,242 information partitions.The experiment used two confusable initial states, equally likely, with maximum perturbation radius 500.Source: §3.2 · p. 10
  • 0.8167225 is the history-dependent value in Atari Freeway, above the Markovian value 0.758971 but below the no-adversary value 0.856748.The authors report that history dependence helps the agent detect adversarial manipulations in this setting, while noting that the direction could theoretically go either way.Source: §3.2 · p. 10

3.3 Limitations of Algorithm

  • For general games, solver wall time scales roughly exponentially with the maximum history length, and peak RAM reaches 8.6GB at depth 10.The authors suggest approximate OS-POSG solvers as a route to greater scalability, at the cost of HSVI’s strong convergence guarantees.Source: §3.3 · p. 10, §3.2 · p. 10
  • Using γ=0.999 to approximate finite-horizon returns gives a close short-horizon approximation, but its worst-case termination bound is highly conservative.The authors report practical convergence substantially better than the bound and say the approach is best suited to short- to moderate-horizon problems.Source: §3.3 · pp. 10–11

4 Conclusions

The paper develops theory and an HSVI-based algorithm for history-dependent SA-MDP strategies. Its numerical examples show that history dependence changes optimal policies and that the algorithm recovers Nash equilibrium strategies.

4 Conclusions

  • The paper develops theory and an algorithm using a novel reduction combined with HSVI to compute solutions for history-dependent SA-MDP strategies.Numerical examples verify that history dependence can change optimal policies and that the algorithm recovers Nash equilibrium strategies.Source: §4 · p. 11

Impact Statement

The work formalizes and computes history-dependent equilibria in state-adversarial MDPs, with potential benefits for reliability and robustness. Its current real-world applicability is constrained by bounded scalability, and the authors note possible misuse for designing stronger attacks.

Impact Statement

  • The approach may support more reliable autonomous systems and stronger robustness guarantees, but its real-world applicability is bounded and it could also aid attack design.The authors argue that making vulnerabilities explicit is necessary for developing defenses and improving resilience.Source: Impact Statement · p. 11

A Proofs

For a fixed initial distribution, robust optimality coincides with Nash equilibrium, but no history-dependent policy is state-robust optimal in every state in the constructed SA-MDP. The proofs also establish saddle-point existence and connect sequential games to constrained simultaneous games.

A Proofs

  • For any fixed initial distribution, robust optimality and Nash equilibrium are equivalent in the zero-sum SA-MDP.The result covers finite horizons with γ ∈ (0, 1] and infinite discounted horizons with γ ∈ (0, 1).Source: A Proofs · p. 14
  • Finite-horizon saddle points extend to an infinite-horizon behavioral saddle point under bounded rewards and discounted returns.The proof uses compactness of the strategy spaces, continuity of the value, and a limit of finite-horizon saddle points.Source: A Proofs · pp. 14–15
  • No history-dependent policy is state-robust optimal in every state in the constructed SA-MDP.A policy that improves value from one state can be induced to take a harmful action from another by an adversary that fabricates the same reported history.Source: A Proofs · pp. 16–17

Preliminaries and Definitions

  • The sequential SA-MDP can be represented by a strategically equivalent constrained simultaneous one-sided POSG, with strategies corresponding in both directions.The construction interleaves stages using forced dummy moves.Source: A Proofs · p. 18, Preliminaries and Definitions · p. 18

Theorem Statements and Proofs

The theorem statements establish that the sequential and constrained simultaneous games preserve values and ε-equilibria, and that a constrained HSVI extension computes such equilibria. The numerical example reports Markovian equilibrium strategies for both players.

Theorem Statements and Proofs

  • A sequential strategy pair is an ε-Nash equilibrium if and only if its mapped feasible pair is one in the constrained simultaneous game.The correspondence follows from the bijection between strategies and preservation of outcome probabilities.Source: Theorem Statements and Proofs · pp. 19–20
  • The constrained HSVI extension returns feasible strategies forming an ε-Nash equilibrium for the transformed game.It restricts local stage games to feasible strategy sets and maintains lower- and upper-bound value functions.Source: Theorem Statements and Proofs · p. 20
  • The algorithm terminates after finitely many trials by combining finite recursion depth with separated terminal beliefs in compact belief simplexes.After updates, later terminating beliefs at the same depth and structural state set must be more than D apart.Source: Theorem Statements and Proofs · p. 23

B.1 Markovian Strategies

  • The example’s Markovian agent equilibrium chooses A, A, B, C at observations s0, s1, s2, s3, while the adversary uses the reported state-dependent kernel.At s2 the adversary mixes equally between s2 and s3.Source: §B.1 · p. 24

B.2 History Dependent Strategies

The history-dependent example specifies how the agent and adversary respond to histories that include the first-stage action and subsequent observation.

B.2 History Dependent Strategies

  • After first-stage action A and observation s2 or s3, the agent plays B on-policy; its off-policy responses also depend on the prior action and observation.After B it responds with B to s2 or s3, and after C it responds with A to s0.Source: §B.2 · p. 24
  • The adversary’s response varies with the current state and prior action, mixing between s2 and s3 after on-policy A at s2.After off-policy B at s1 or s2 it reports s2; after C at s0 the report is forced to s0.Source: §B.2 · p. 24

C Analysis of Example SA-MDP Game Where History Matters

The example uses a four-state action game with a two-stage effective horizon and restricted neighboring-state reports. It contrasts Markovian reporting kernels with adversaries that may condition reports on full history.

C.1 Setup

  • The example has states s0–s3 plus an absorbing state t, actions A, B, C, and rewards specified by state and action.The setup converts the two-stage example to an infinite-horizon game by adding zero-reward absorbing behavior after t = 2.Source: §C.1 · pp. 24–25
  • The adversary’s reports are restricted to neighboring states, with s0 forced to report its true state.The allowed sets are B(s0)={s0}, B(s1)={s1,s2}, B(s2)={s2,s3}, and B(s3)={s1,s3}.Source: §C.1 · p. 25

C.2 Markovian vs history-dependent observation adversaries

  • A Markovian adversary uses a state-dependent reporting kernel, parameterized for s1, s2, and s3 by q1, q2, and q3.The history-dependent adversary may instead condition its reporting kernel on the full history of states, actions, and observations.Source: §C.2 · p. 25

C.3 Markovian vs history-dependent observation adversaries

  • The second description likewise distinguishes a state-conditioned Markov kernel from a history-dependent kernel that uses past states, actions, and observations.At s0 the adversary must report s0, so its choice matters only at the second stage in this example.Source: §C.3 · p. 25

C.4 Markovian adversary: best responses and value

The section derives the agent’s best-response value against a fixed Markovian misreporting kernel by evaluating its A- and B-branch responses. The best response depends on threshold conditions in the kernel parameters.

C.4 Markovian adversary: best responses and value

  • F(q1,q2,q3) is the agent’s best-response value against a fixed Markovian misreporting kernel, taking the larger of the A- and B-branch values.The section computes each branch value from the agent’s best response, then defines F as their maximum.Source: §C.4 · p. 26
  • For the A-branch report s3, the agent chooses B when p≥0.4 and C when p<0.4, where p=(1−q2)/(1−q2+q3).The posterior is computed from the probabilities that states s2 and s3 produce report s3.Source: §C.4 · p. 26
  • The A-branch value is 1−q3 when 3−3q2−2q3≥0, and 1.5q2−0.5 otherwise.For report s3, the agent chooses B when the posterior p≥0.4 and C when p<0.4.Source: §C.4 · pp. 26–27
  • The B-branch value is q1 when 2q1+3q2≥2, and 1−1.5q2 otherwise.The condition determines whether B is the best response to report s2; the branch value follows from the resulting actions and payoffs.Source: §C.4 · pp. 27–28

C.5 Minimizing the Markovian worst-case value

The Markovian adversary’s minimax problem minimizes the agent’s best-response value over kernel parameters. Splitting the parameter domain into four regions yields an exact worst-case value.

C.5 Minimizing the Markovian worst-case value

  • The analysis splits the parameter domain into four regions; within each, vA and vB are linear and F is their maximum.The minimization is over (q1,q2,q3) in [0,1]^3.Source: §C.5 · p. 28
  • In the region where both branch conditions fail, equalizing vA=1.5q2−0.5 and vB=1−1.5q2 gives the minimum at q2=0.5.This region also requires q3>0.75 and q1<0.25; (0,0.5,0.8) is one feasible triple attaining F=0.25.Source: §C.5 · p. 29
  • The Markovian adversary’s minimax best-response value is 1/4, attained by an explicit kernel triple such as (0,0.5,0.8).The section concludes that the infimum across all four regions is 1/4.Source: §C.5 · pp. 29–30

C.6 History-dependent adversary

A history-dependent adversary can use different kernels after the agent’s first-stage A and B actions, driving the best-response value to zero. The section concludes that this adversary is strictly more damaging than a Markovian one.

C.6 History-dependent adversary

  • Using separate kernels on the A- and B-subtrees drives each branch’s best-response value to zero, yielding VHist=0.The example uses (q2,q3)=(0,1) on A and (q1,q2)=(0,2/3) on B; a baseline agent strategy guarantees at least zero.Source: §C.6 · p. 30

C.7 Conclusion of VMarkov and VHist Comparison

  • The history-dependent observation adversary is strictly more damaging than the Markovian adversary.The paper’s comparison concludes that the history-dependent adversary lowers the value relative to the Markovian case.Source: §C.7 · p. 30, §C.6 · p. 30

D Algorithm Details

The algorithm reduces an SA-MDP to a constrained zero-sum one-sided partially observable stochastic game and applies HSVI to compute an approximate equilibrium. Its evaluation reports scaling with state count and tree depth.

D Algorithm Details

  • The algorithm converts a finite-horizon SA-MDP to a stationary model, then reduces it to a constrained zero-sum OS-POSG using dummy states and actions.The attacker’s action encodes the reported observation, and the reduction imposes state-dependent constraints derived from B.Source: D Algorithm Details · p. 31
  • It solves the reduced game with HSVI, using lower and upper value bounds represented by α-vectors and belief–value points.The algorithm explores while the initial-belief excess gap exceeds the tolerance.Source: D Algorithm Details · pp. 31–32
  • After solving, the algorithm extracts online policies and collapses dummy turns to map the strategies back to the SA-MDP.The attacker’s action is interpreted as the perturbed observation in the original model.Source: D Algorithm Details · p. 31
  • The implementation caches explored state-action pairs and splits overlapping information sets to solve smaller convex problems while retaining history-dependent information sets.The paper reports using CPLEX for the linear programs.Source: D Algorithm Details · p. 32
  • Figure 6 shows HSVI solve time scaling roughly linearly with number of states and log-linearly with game depth; runs were declared converged when excess-gap fell below epsilon=0.01.Source: D Algorithm Details · p. 32, Figure 6 · p. 33

Related papers

Loading 2609.18829v2…