Epsilon-Nash Equilibria in History-Dependent SA-MDPs Brandon Gary Kaplowitz1,* Dominik Bohnet Zurcher2,* Akash Agrawal3 Tala Jafari2 Christian Schroeder de Witt1 Paul W. Goldberg2
arXiv:2609.18829v1 [cs.GT] 16 Sep 2026
1
Department of Engineering Science, University of Oxford 2 Department of Computer Science, University of Oxford 3 ML Alignment and Theory Scholars * Equal contribution. Correspondence to [email protected].
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—who knows the true state the agent is in—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.
1
Introduction
Reinforcement learning under adversarially manipulated observations poses fundamental challenges that are not captured by standard Markovian robustness models. In this work, we study stateadversarial Markov decision processes with history-dependent policies, characterize their equilibrium structure, and provide the first algorithmic approach for computing approximate history-dependent equilibria. We consider a state-adversarial Markov decision process (SA-MDP) modeling an observation-space attack game. In each time step t, an agent (player 1) takes an action at1 based on its observation, while an adversary (player 2) simultaneously selects an observation ot to send to the agent. The adversary knows the true state st and must choose ot from an allowed set B(st ) (a proximity constraint neighborhood of st ), which limits how far the observation can deviate from reality. The agent receives ot (but not st ) and the environment then transitions to a new state st+1 with probability p(st+1 | st , at1 ), and a reward R(st , at1 ) is obtained by the agent (the adversary’s payoff is the negation). This repeats indefinitely with discount factor γ ∈ (0, 1). The adversary’s goal is to minimize the agent’s total expected reward by cleverly manipulating observations. Such SA-MDP models have been studied in robust RL and planning settings, usually under the restriction that both players use Markovian (memoryless) policies.
Most prior work on SA-MDPs assumes stationary optimal policies depending only on the current state (for the adversary) or observation (for the agent). Under this assumption, the interaction can be formulated as a two-player zero-sum game with a stationary equilibrium policy pair (π1∗ , π2∗ ) (for agent and adversary respectively). However, as we argue below, an agent that can condition its strategy on past observations (i.e., a history-dependent policy) can potentially achieve higher rewards than any memoryless policy by detecting and exploiting patterns in the observation sequence. We therefore seek a solution concept allowing history-dependent policies in SA-MDPs, and develop the first algorithm to compute such an equilibrium. 1.1
Related Work
This paper is inspired by the foundational work of cooperative multi-agent learning, aiming to build adversarially-robust, collaborative autonomous agents [Cai et al., 2022, Panait and Luke, 2005, Wang et al., 2022a, 2017]. Early work studied adversarial attacks on reinforcement-learning policies mainly as empirical attack constructions and vulnerability demonstrations: adversarial perturbations to observations can substantially degrade learned policies, and attack timing can matter over trajectories [Huang et al., 2017, Lin et al., 2017]; policy-induction attacks during learning were also considered early on [Behzadan and Munir, 2017]. The SA-MDP line then formalized worst-case attacks on state observations and robust learning in this setting [Zhang et al., 2020]. Follow-up work studied stronger attacks and robust training in closely related fixed-agent, alternating-training, or restricted-policyclass settings, including learned optimal adversaries with alternating training [Zhang et al., 2021], efficient strongest-attack methods [Wang et al., 2022c], and robust/adversarial-training methods such as those of Oikarinen et al. [2021] and Liang et al. [2022]. Several nearby game-theoretic extensions are also relevant [Pendharkar, 2012]. Illusory attacks impose information-theoretic detectability constraints on observation attacks [Franzmeyer et al., 2023]. Broader online attack/defense formulations consider manipulation of states, observations, actions, and rewards [Birmpas et al., 2021, McMahan et al., 2024, Motwani et al., 2024, Sarkadi et al., 2019, Tu et al., 2021, Wang et al., 2022b]. Temporally coupled perturbations have been modeled as a partially observable two-player zero-sum game and solved approximately via equilibrium computation [Khakpour and Parker, 2025, Liang et al., 2024]. In multi-agent settings, state-adversarial Markov games can fail to admit standard optimal-policy or robust-Nash solution concepts [Han et al., 2022]. Our algorithmic approach also builds directly on the planning and game-solving literature: partially observable Markov decision processes (POMDPs) provide the underlying partial-observability formalism on the agent side [Kaelbling et al., 1998], Heuristic search value iteration (HSVI) supplies the core search/value-iteration template [Smith and Simmons, 2004], and Horák et al. [2023] gives the immediate zero-sum one-sided POSG framework and solver that our reduction and algorithm build on. Relative to this literature, our contribution is to study observation-space SA-MDPs with history-dependent policies, prove that universal history-dependent state-robust policies need not exist, and give a reduction-based route to computing ϵ-approximate equilibria for a given initial state distribution. 1.2
Background and Notation
For any set X, let ∆(X) denote the set of probability distributions over X. Zhang et al. [2020] introduce the state-adversarial Markov decision process (SA-MDP) to model an RL agent (player 1) interacting with an environment under adversarial observation perturbations (player 2). An SA-MDP can be defined as a tuple M = (S, A, R, p, γ, B), where S is the true state space, A the agent’s action space, R : S × A → R the reward function, p : S × A → ∆(S) the state transition probabilities, γ ∈ (0, 1) the discount factor, and B the function that specifies the allowable perturbations of the adversary. In particular, for each true state s ∈ S, B(s) ⊆ S is the set of states that the adversary can present to our agent as a perturbed observation. We denote the adversary’s (possibly stochastic) policy by ν : S → ∆(S), where ν(s) ∈ ∆(B(s)). At each time step, the agent observes s̃ ∼ ν(s), and then selects an action a ∈ A according to its policy π : S → ∆(A) (which is applied to the observation s̃). The environment then transitions to the next true state s′ drawn from p(s′ |s, a), and a reward R(s, a) is emitted. Notably, the adversary influences the agent’s perception but does not alter the underlying state transition; s′ depends on the actual s and a taken, not directly on s̃. The adversary’s objective is assumed to be worst-case in that it aims to minimize the agent’s 2
total return (e.g., by choosing perturbations that lead the agent to make suboptimal decisions). This worst-case observation model cannot be captured by a standard partially-observable MDP, since a POMDP uses fixed observation probabilities [Kaelbling et al., 1998], whereas here the observation distribution observed by the agent depends on the adversary’s policy. Formally, we can define the value of a given stationary agent policy π under a specific adversary ν starting from state s as ∞ hX i V π,ν (s) = Eπ,ν γ t R(st , at ) s0 = s , t=0
where at ∼ π(· | s̃t ), s̃t ∼ ν(st ), and st+1 ∼ p(· | st , at ). Of particular interest is the optimal adversary for a given π, νπ∗ . We define the optimal adversarial value function as: ∗
V π,νπ (s) = min V π,ν (s). ν
In an SA-MDP, the agent faces a two-player zero-sum game against the adversary, who chooses the worst observable state at each step. Zhang et al. [2020] show that for a fixed π, the value function under the optimal adversary νπ∗ satisfies a robust Bellman equation. Specifically, letting ∗ V̄π (s) = V π,νπ (s) denote the value under the strongest adversary, we have: h i X X π(a | s̃) · p(s′ | s, a) R(s, a) + γ V̄π (s′ ) . V̄π (s) = min (1) s̃∈B(s) a∈A
s′ ∈S
which defines a contraction operator on value functions. Intuitively, at state s the adversary chooses a perturbation s̃ ∈ B(s) that minimizes the expected return and expected distribution over future values, knowing the agent will act according to π on s̃. This worst-case Bellman operator allows “policy evaluation” under the optimal adversary. However, in order to consider history dependent policies, we introduce another game, the Zero-Sum One-Sided Partially Observable Stochastic Game, formalized by Horák et al. [2023]. Definition 1.1 (Zero-Sum One-Sided Partially Observable Stochastic Game). A Zero-Sum One-Sided Partially Observable Stochastic Game (or zero-sum OS-POSG) is a tuple G = (S, A1 , A2 , O, T, R, γ) where: • S is a finite set of game states, • A1 and A2 are finite sets of actions of player 1 and player 2, respectively, • O is a finite set of observations • T (·|s, a1 , a2 ) ∈ ∆(O × S) represents probabilistic transition function for every (s, a1 , a2 ) ∈ S × A1 × A 2 , • R : S × A1 × A2 → R is player 1’s reward function, • γ ∈ (0, 1) is a discount factor. The play unfolds as follows. First, an initial state s(0) ∼ binit is drawn from the probability distribution binit . Then, for each stage, the current state s(i) is revealed to player 2 but remains hidden from player (i) (i) 1. Simultaneously, player 1 chooses a1 ∈ A1 and player 2 chooses a2 ∈ A2 . An unobserved (i) (i) (i) (i) reward R s(i) , a1 , a2 is awarded to player 1, while player 2’s payoff is −R s(i) , a1 , a2 . The system transitions to a new state s(i+1) and emits an observation o(i) according to T o(i) , s(i+1) | (i) (i) (i) (i) s(i) , a1 , a2 . Player 2 then observes the full outcome of the stage: s(i) , a1 , a2 , o(i) . Player 1, (i) (i) by contrast, sees only a1 , o(i) , without learning a2 , s(i) , or s(i+1) .
2
Theoretical results
In Section 2.1, we show the non-existence of universal Nash equilibria, i.e. policies independent of the initial state distribution. Assuming an initial state distribution is given, in Section 2.2, we show the importance of history-dependent policies, arguing that agents are incentivized to use them, and adversaries must then modify their policies accordingly. We then show in Section 2.3 how to reduce the SA-MDP problem to a modified version of the zero-sum OS-POSG, which allows us to find an epsilon-approximate Nash equilibrium for the original SA-MDP. This equilibrium allows us to find policies that guarantee near optimal rewards. 3
(a) History Matters 1/2
a1 : R = 1 a2 : R = −1 1/2
(b) History Matters More a1 : R = −1 a2 : R = 1
S1
S2
1/2
a1 : R = 1 a2 : R = −1 2/5
1/2
a1 : R = −1 a2 : R = 1
S1
S2
2/5
2/5
2/5 1
1
S3
1/5
1/5
1/2
S3
S4
a1 , a2 : R = 0
a1 : R = −0.1 a2 : R = 0.5
a1 , a2 : R = 0 1/2
Figure 1: Examples illustrating the impact of history-dependent policies. 2.1
Non-Existence of Universal History Dependent Nash Equilibrium Policies
In a zero-sum game, the agent’s optimal strategy can be defined in two equivalent ways: as a robust policy that maximizes value against the worst-case adversary, or as part of a Nash equilibrium (NE) of the game. We show that these notions coincide for SA-MDPs. Lemma 2.1 (Robust Optimality ⇐⇒ Nash Equilibrium). Consider a zero-sum SA-MDP with finite state, action, and observation sets, nonempty perturbation sets B(s), bounded rewards, a fixed initial distribution b ∈ ∆(S), and unrestricted full-history behavioral strategy spaces Σ1 and Σ2 for the agent and the adversary, respectively. We assume perfect recall in which each player’s private history records all previously observed information and all of that player’s previous actions. For a strategy profile (σ, τ ) ∈ Σ1 × Σ2 , let V (b; σ, τ ) denote the agent’s expected return for the horizon under consideration when s0 ∼ b; when the horizon is N < ∞, we also write V N (b; σ, τ ) to make the horizon explicit. For a finite horizon, we allow γ ∈ (0, 1], with γ = 1 corresponding to the undiscounted return; for an infinite discounted horizon, we require γ ∈ (0, 1). In either case, the following equality holds for every initial distribution b ∈ ∆(S): arg max min V (b; σ, τ ) = {σ ∈ Σ1 : ∃τ ∈ Σ2 with (σ, τ ) a Nash equilibrium when s0 ∼ b} . σ∈Σ1 τ ∈Σ2
Both sets are nonempty. See proof in Appendix A. We use this lemma to demonstrate the impossibility of finding an algorithm that always returns policies Nash equilibrium agnostic of the initial state distribution. Zhang et al. [2020] showed that there exist SA-MDPs where there is no Markovian optimal agent policy that is independent of the initial state distribution b. They leave open the question of whether the same holds for history dependent policies. We revisit their concrete example and show that no history dependent policy can achieve the minimax value against all adversarial responses. According to the previous lemma, this implies that no initial-state-distribution-agnostic Nash equilibrium exists. Theorem 2.2. There exists a SA-MDP such that no history-dependent policy is state-robust optimal. See proof in Appendix A. 2.2
Why History Matters
Most models assume Markovian (memoryless) policies for both the agent and the adversary, meaning both the adversary’s and agent’s actions depend only on the current state or observation and not on past history. This yields a tractable two-player zero-sum framework with stationary, optimal policies. However, a purely Markovian agent might miss opportunities that arise from factoring in the history of play. Consider Figure 1a where the transition probabilities do not depend on the actions, the rewards are inverted for state s1 and s2 , state s3 deterministically transitions to state s1 without emitting a reward, and B(s1 ) = B(s2 ) = {s1 , s2 }, B(s3 ) = {s3 }. This setting is already complex enough for it to become difficult to analytically determine the best Markovian policy, not to mention the best history dependent policy. However, we can assume 4
that in a Markovian equilibrium, the adversary would focus its manipulations on s1 and s2 , as an incorrect action in s3 or s4 simply has less of a negative effect on the agent. In a history dependent setting, however, the presence of s4 allows the adversary to reduce the certainty the agent had in the previous example of transitioning from s3 to s1 . Thus, we would expect the adversary to increase the misreports between s1 and s4 in a history dependent environment. The inherent complexity of even this small MDP and the interplay between agent and attacker policy motivate the following study of an algorithm to find approximate history dependent Nash equilibria. Allowing for history dependent strategies vastly increases the strategy space and brings new analytical challenges. As shown in Theorem 2.2, history dependent state-robust Nash equilibrium policies (i.e. policies that are optimal for every state) do not always exist. Therefore, we seek a Nash equilibrium strategy profile for a given initial state distribution. To compute such an equilibrium under history dependence, we modify an algorithm developed by Horák et al. [2023]. The authors introduce an HSVI-based solver for one-sided partially observable stochastic games, where one player (the attacker) has full state information and the other (the agent) has only partial observability. This algorithm can efficiently approximate equilibrium strategies even in long-horizon problems. Our attacker–agent interaction fits the one-sided paradigm: the attacker knows the true state, while the agent only sees perturbed observations. By leveraging Horak’s algorithm, we can obtain a history dependent equilibrium policy pair for our game given the initial state distribution. 2.3
Modified Zero-Sum OS-POSG to Find Epsilon-Equilibria
We now state one of our main theorems: that any SA-MDP can be transformed into a strategically equivalent zero-sum one-sided POSG. Theorem 2.3. Any SA-MDP Gseq can be transformed into a strategically equivalent constrained b in which both players act simultaneously at every stage. The solution zero-sum one-sided POSG G b strategy to G can be mapped back to a unique solution strategy of Gseq . Proof. We present a high level presentation of the proof, defining its key mathematical objects in the text and its details in the appendix. The underlying idea in the transformation is to encode each sequential SA-MDP as two simultaneous micro-stages while removing all non-decisive degrees of freedom. We introduce alternating dummy actions for both the agent and the adversary. Thus, each player will still have to choose an action at every stage, but will only need to make meaningful decisions every other stage, maintaining the nature of sequential decisions within a simultaneous move game. In order to accommodate the dummy actions, we also introduce dummy states, which act as placeholders while the agent takes the meaningful action that will actually inform the transition probabilities. Defining the Transformation We begin with a sequential observation space attack game Gseq = (S, Av , R, p, γ, B) and construct b = (S, b A b1 , A b2 , O, b Tb, R, b √γ, L1 , L2 ) that is strategically a constrained zero-sum OS-POSG G equivalent to Gseq but meets the simultaneous action requirements of Horák et al. [2023]. We define b with the components of Gseq and necessary dummy actions and states. the components of G State space. For every s ∈ S create two states, an original state s and a dummy state s̄. Hence, Sb = S ∪ S̄, S̄ = {s̄ : s ∈ S}. Action sets. Introduce distinguished dummy actions ⊥1 ∈ / Av for the agent and ⊥2 ∈ / S for the b1 = Av ∪ {⊥1 }, A b2 = S ∪ {⊥2 }. adversary, and define A Agent 1 represents the agent, so its meaningful actions are the original agent actions in Av . Agent 2 represents the attacker, whose meaningful actions encode the observation reported to the agent and therefore range over S. The dummy actions ⊥1 , ⊥2 are used only on non-decisive microstages. To eliminate spurious signaling opportunities, we impose state-dependent feasible action sets: L1 (s) = {⊥1 }, L2 (s) = B(s) for each original state s ∈ S, and L1 (s̄) = Av , L2 (s̄) = {⊥2 } for each dummy state s̄ ∈ S̄. 5
(a) Sequential Move Formulation (t) aa
(b) Simultaneous Move Formulation (a1 , ∗) = 0.5 (a2 , ∗) = 0.7
s1 a1 = 0.5 a2 = 0.7
s0 s0
(∗, aa )
o(t)
ō
s1
ō
s2
sd 0
o(t) (a1 , ∗) = 0.5 (a2 , ∗) = 0.3 a1 = 0.5 a2 = 0.3
s2
Figure 2: Strategically equivalent forms of an OS-POSG.
Stage decomposition.
b One stage of Gseq is encoded as two micro-stages in G:
1. Suppose the system is in an original state s. The attacker chooses a feasible action a2 ∈ L2 (s) = B(s), which corresponds to the observation it wants the agent to receive, while the agent is forced to play ⊥1 . The system deterministically transitions to s̄ and emits observation o = a2 . 2. The system is now in the dummy state s̄. The agent chooses a1 ∈ L1 (s̄) = Av given the received observation o = a2 , while the attacker is forced to play ⊥2 . The system then transitions according to the original probability p(· | s, a1 ) to the next original state s′ and emits a special dummy observation ō. Transition Kernel Tb. For every original state s ∈ S and feasible attacker action a2 ∈ B(s), Tb(a2 , s̄ | s, ⊥1 , a2 ) = 1. For every dummy state s̄ ∈ S̄ and agent action a1 ∈ Av , Tb(ō, s′ | s̄, a1 , ⊥2 ) = p(s′ | s, a1 ). All other transitions have probability zero (equivalently, they correspond to infeasible action tuples under the state-dependent constraints above). Note that the first micro-stage depends only on the attacker’s meaningful action, while the second micro-stage depends only on the agent’s meaningful action. The dummy actions never affect transitions, rewards, or observations. b a1 , a2 ) = 0, R(s̄, b a1 , a2 ) = √1 R(s, a1 ) where the √1 accounts for the Reward. Define R(s, γ γ rewards being applied at odd indices. b = O ∪ {ō}. Player 1 receives the attackerObservations. The agent’s observation alphabet is O selected observation a2 at the first micro-stage and the dummy observation ō at the second micro-stage. The observation ō signals that the next micro-stage is attacker-decisive and the agent is constrained to play ⊥1 . Player 2 always observes the full state. √ Discount Factor. The transformed game has discount factor γ. Since the only non-zero rewards √ occur at the second micro-stage of each encoded step, we scale rewards on dummy states by 1/ γ. √ 2t+1 b √ 2t+1 1 √ R(s, a1 ) = γ t R(s, a1 ), so the transformed discounted Hence ( γ) R(s̄, a1 , ⊥2 ) = ( γ) γ return matches the original discounted return exactly. Consider the following visualization (Figure 2a) of how one stage in the sequential observation space attack game can be simulated by a simultaneous move game. We will consider the first stage of the game, transitioning from s0 to either s1 or s2 . Note that in the sequential setting, the observation emitted by the system is modified according to the attacker’s action. This observation informs the agent’s action, while the true state dictates the actual transition probabilities. 6
Strategic Equivalence b is strategically equivalent We now show that the transformed simultaneous zero-sum OS-POSG G to the original sequential observation-space attack game Gseq . We establish the following three properties: 1. Strategy correspondence: after restricting each non-decisive micro-stage to its singleton dummy action, there is a bijection b feas Φi : Σseq −→ Σ , i i
i ∈ {1, 2},
b between each player’s behavioral strategies in Gseq and feasible behavioral strategies in G. 2. Pairwise payoff preservation: for every initial belief b, its canonical embedding bb in the transformed state space, and every strategy pair (σ1 , σ2 ), V seq (b; σ1 , σ2 ) = V sim bb; Φ1 (σ1 ), Φ2 (σ2 ) . 3. ϵ-equilibrium correspondence: a strategy pair is an ϵ-Nash equilibrium, equivalently an ϵ-saddle point, of Gseq if and only if its image under (Φ1 , Φ2 ) is an ϵ-Nash equilibrium of b over feasible strategies. G b will have a These three results prove Theorem 2.3. Result 1 guarantees that a strategy found in G corresponding unique strategy in Gseq . Result 2 guarantees that the values of the Nash equilibria in both games are equal. Finally, Result 3 guarantees that the strategy in Gseq still achieves an ϵ-approximate Nash equilibrium. See remaining details of the proof on page 17. 2.4
Constrained Zero-sum OS-POSG
Definition 2.4 (Information-compatible constrained zero-sum OS-POSG). An informationcompatible constrained zero-sum one-sided partially observable stochastic game is a tuple G = (S, A1 , A2 , O, T, R, γ, L1 , L2 ), where (S, A1 , A2 , O, T, R, γ) is a finite discounted zero-sum one-sided POSG, player 1 is the uninformed maximizing player, and player 2 is the fully informed minimizing player. For player 2, L2 : S → 2A2 \ {∅} may depend on the true state. For player 1, the feasible action set is required to be measurable with respect to player 1’s information: whenever two states s, s′ may occur at the same player-1 information history, L1 (s) = L1 (s′ ). Equivalently, at every reachable player-1 information history h1 , there is a nonempty set L1 (h1 ) ⊆ A1 that is common to all states compatible with h1 . A behavioral strategy is feasible if its support is contained in the corresponding feasible action set at every information history. The game is played as before, with the additional requirement that, at state s, player 1 chooses a1 ∈ L1 (s), and player 2 chooses a2 ∈ L2 (s). Theorem 2.5. The HSVI algorithm of Horák et al. [2023] extends to the constrained zero-sum onesided POSG in Definition 2.4 by restricting each local stage game to the players’ feasible strategy sets. The algorithm maintains a lower-bound value function VLB and an upper-bound value function Γ VU B , written as VLB and VUΥB , respectively, in Algorithm 2, satisfying VLB (b) ≤ V ∗ (b) ≤ VU B (b) for every reachable belief b, where V ∗ is the optimal value function of the constrained game. 7
Let
U0 − L0 , 2 where L0 and U0 are the discounted minimum and maximum feasible reward bounds. If δ = 0, the initial bounds coincide. If δ > 0 and δ=
0<D<
(1 − γ)ϵ , 2δ
then the algorithm terminates at the initial belief b0 with VU B (b0 ) − VLB (b0 ) ≤ ϵ. The strategy obtained from the lower-bound value function for player 1 and the strategy obtained from the upper-bound value function for player 2 are feasible and form an ϵ-Nash equilibrium. In b constructed in Theorem 2.3. particular, the result applies to the constrained OS-POSG G See proof in Appendix A. The termination condition deteriorates as γ → 1. Under the uniform reward bounds used here, δ=
Rmax − Rmin , 2(1 − γ)
so the sufficient condition may be written as D<
(1 − γ)2 ϵ . Rmax − Rmin
This is a worst-case sufficient bound and becomes conservative for discount factors close to one; we discuss its practical implications and our finite-horizon use of γ = 0.999 when we discuss the limitations of our algorithm in Section 3.3. 2.5
Algorithm
Using our representation of a history-dependent SA-MDP as a constrained zero-sum OS-POSG, we devise an algorithm to solve our game. The algorithm first converts a given SA-MDP game (as encoded in a custom text file format) into an equivalent constrained OS-POSG with phase-dependent singleton feasible action sets and adversarial proximity constraints. Given this constrained OS-POSG, we then leverage Horák et al. [2023] with HSVI, modified to respect state-dependent feasibility constraints for both players. Further details of the algorithm are provided in Appendix D.
3
Experiments
3.1
Example SA-MDP Where History Matters
We construct an example history-dependent SA-MDP with analytically verifiable optimal strategies to explicitly find how much worse off a player facing a history-dependent adversary is and to provide a benchmark setting to test our algorithm. The game consists of states S = {s0 , s1 , s2 , s3 }, actions A1 = {A, B, C}, and a time horizon H = 2. Adversaries can misreport only in restricted ways, where the restriction on the support of misreporting strategies is given by B(s) ∈ 2S \ ∅ for state s ∈ S. For our problem B(s1 ) = {s1 , s2 }, B(s2 ) = {s2 , s3 } and B(s3 ) = {s3 , s1 }. Rewards are sparse and are only realized at the end of the game. The full game is shown in Figure 3. An analysis of the game in Appendix C demonstrates that the value associated with Markovian strategies for both the agent and the adversary VMarkov = 0.25, while for a history-dependent agent and adversary, we get VHist = 0. This means that the agent is strictly worse off facing a historydependent adversary, even after being allowed history-dependent strategies. There are multiple equilibrium strategies for each player. Our code successfully recovers one of these equilibrium strategies that defines the boundary of the region containing optimal strategies under a 8
s0 A
B
Nature s3 , 12
Nature
s2 , 12
Adv s3
Adv s2
s̃ ∈ {s1 , s3 }
A −2
s1 , 12
s2 , 12
Adv s1
s̃ ∈ {s2 , s3 }
B C
A
0
−1
−2
s̃ ∈ {s1 , s2 }
B C 2
−1
A
B C
0
−2
0
Figure 3: Finite horizon version of SA-MDP game tree (action C at s0 yields −10 and so omitted as never chosen): the agent chooses A or B at s0 , Nature draws the second-stage state, the adversary reports a neighbor state s̃ ∈ B(s), and the agent chooses A, B, or C for the terminal payoff. History-dependent ν(s̃ | s, a)
Markovian ν(s̃ | s)
after A
s1
s2 1 2
s2
1 3
s2
2 3
s2 s3
1 2
s3
after B
s3 s1
s3
s2
s2
Figure 4: Adversary equilibrium strategies for Markovian vs. history-dependent adversary. Left: Markovian. Right: history-dependent kernels conditioned on player action in state s0 ( A vs. after B). barrier-point linear program solver for each stage game. Full recovered strategies are shown visually in Figure 4 and written out explicitly in Appendix B. Our algorithm returns an upper and lower bound that contain the true value for the history-dependent strategies that are less than tolerance ϵ apart on convergence. The midpoint of these upper and lower bounds for history-dependent strategies is given by V̂Hist = 0 ± O(10−8 ), compared to a known analytic value of 0, for a convergence tolerance ϵ = 0.01. Because we use γ ∼ 1 (γ = 1 breaks HSVI), even with exact precision we would have small numerical error left over for an arbitrary problem. In practice, over moderate horizons, the difference is negligible. In comparison, our Markovian game solver finds a solution with a numerical tolerance of O(10−6 ), based on the numerical precision of the linear programming solver. The final solution found via the linear solver is V̂Markov = 0.2496 ± O(10−6 ), compared to a true analytical value for γ = 0.999 ∼ 1 of 0.2496 and 0.25 for the exact γ = 1. 3.2
Larger Problems
We test our algorithm up to depth 10 with 4 actions per node on randomly generated trees with 3.1 million states and 1.4 million information sets. Solving takes 2200s on a single MacBook M4 Pro CPU core and involves 18,000 explorations of the tree. We also tested our algorithm with 5 different seeds for games of sizes 2, 4, 6, and 8. We get a roughly log-linear plot in the amount of solve time per additional layer of depth. Roughly every 2 additional horizons increase solve time by 20–30×. See Figure 6 and Table 1 for detailed scaling information and Appendix D for further discussion. Finally, we practically test our algorithm on Atari Freeway at depth 12 with a frame-skip of 30. Here, following the procedure in BRIDGE [Laidlaw et al., 2023] we generate an exact enumeration of state-actions reachable within the given horizon and merge behaviorally equivalent states. We found that on the default Atari settings with frameskip 30, agents were able to find an optimal 9
Table 1: Runtime and exploration scaling by depth over 5 seeds. Explorations are the number required to reach an excess value-function gap below 10−2 . Times are rounded to hundredths of a second. Depth States Mean time (s) Std. dev. (s) Explorations 2 4 6 8
23 743 12,263 196,583
0.00 0.08 1.48 52.49
0.00 0.02 0.30 21.49
6 28 257 2,564
deterministic strategy independent of actual observations on the initial reset, and thus immune to adversary perturbations. Therefore, we made the Atari initial state “random” by hidden warm-up uncertainty and an initial adversary maximal perturbation of the radius in L2 distance as 500 (about 2.73 grayscale levels per pixel if spread uniformly), which permits multiple reports. The two initial states were generated by “warming-up” the Freeway environment and letting it run initially for a random length of time. We then searched across these possible random initial states until we found two whose distance was less than 500 apart from each other (their initial screen distance is 486.7018). This ensured that these two initial states are confusable. We then placed an equal probability of the agent starting in either of the two initial states in the Atari simulation. Here, VHD,HD lies below the no-adversary value and exceeds the approximate Markov FP value, showing history-dependent strategies matter and help the agent here. Atari Freeway is depth 12 but takes just 2.07s to solve for optimal history-dependent adversary and agent policies. This is because the number of info partitions in the OS-POSG is small after this behavioral consolidation (5,242 partitions versus 87,375 for depth 8, action 4 game). In this Atari Freeway setting, history matters, and we find a history-dependent value of 0.8167225 (0.816584–0.816861 lower and upper value bounds from HSVI after converging under 0.01 excess gap; a reported excess gap of ∼ 2 × 10−4 ) for both the agent and the adversary exhibiting historydependence, compared to 0.856748 for no adversary and 0.758971 for both agents being Markovian. Here, history dependence helps the agent detect manipulations by the adversary, leading to improved performance. Theoretically, however, the direction could go either way. Larger settings are feasible to scale to, but are limited by the use of HSVI as our algorithm for exact solving; the primary constraint is memory as our depth 10 setting uses peak RAM of 8.6GB.
3.3
Limitations of Algorithm
The primary limitation of our algorithm is that, for general games, the solver wall time scales in a roughly exponential fashion in the maximum length of history-dependence we solve for in the original SA-MDP problem. This is unsurprising, given that the number of histories themselves scale in this fashion and we are aiming to exactly solve the solution. In principle, however, any solution algorithm for general zero-sum OS-POSG games can now be applied. This means that approximate solutions involving depth-limited search, public belief-space methods, flexible neural network-based value function or policy function estimators learned via self-play could be applied to our algorithm, at the cost of our strong guarantees on convergence that we get from utilizing HSVI in exchange for even further scalability. Already, however, we have shown we can tackle SA-MDP problems of real-world relevance and size, while still retaining the use of HSVI with guarantees on the validity of the solution. A further limitation arises from using a discount factor close to one to represent finite-horizon objectives within the infinite-horizon HSVI framework. In our finitehorizon experiments, we use γ = 0.999 and absorbing zero-reward states after the terminal depth. This introduces a small difference between the intended undiscounted finite-horizon return and the discounted return optimized by the solver. Thus, although γ = 0.999 provides a close approximation to the undiscounted short-horizon objective, the corresponding worst-case termination bound can be highly conservative. Our experiments indicate that practical convergence is substantially better than this bound, but the approach remains most suitable for short- to moderate-horizon problems. We leave it to future work to explore the application of these methods to solve larger SA-MDPs with our approach. 10
4
Conclusions
We develop theory for history-dependent strategies in SA-MDPs, as well as an algorithm for computing their solutions using a novel reduction combined with HSVI. We show how this can be extended to study constrained adversaries. Finally, we verify in numerical examples that history-dependence quantitatively and qualitatively matters for optimal policies in SA-MDPs and how much an adversary can punish an agent and show that our algorithm successfully recovers Nash equilibrium strategies. This opens the door to scaling our approach to substantially larger state spaces by using compressed belief representations, using approximate solvers for POSG in a public belief space representation of the setting, and horizon truncation at the cost of guarantees and uniform bounds for HSVI.
Impact Statement This work advances the theoretical and algorithmic foundations of robust reinforcement learning under adversarial observation manipulation by formalizing and computing history-dependent equilibria in state-adversarial MDPs. By showing when history dependence fundamentally alters equilibrium behavior - and providing the first practical method to compute such equilibria - our results improve understanding of decision-making in safety-critical and adversarial environments. Potential positive impacts include more reliable autonomous systems and stronger robustness guarantees in sequential decision problems. As with many advances in adversarial modeling, these techniques could also be misused to design more effective attacks; however, we believe that making such vulnerabilities explicit is necessary for developing defenses and improving system resilience overall. Finally, the real-world applicability of our current approach is constrained by its bounded scalability.
References Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning to policy induction attacks. In International conference on machine learning and data mining in pattern recognition, pages 262–275. Springer, 2017. Georgios Birmpas, Jiarui Gan, Alexandros Hollender, Francisco J. Marmolejo Cossío, Ninad Rajgopal, and Alexandros A. Voudouris. Optimally deceiving a learning leader in stackelberg games. J. Artif. Intell. Res., 72:507–531, 2021. He Cai, Youfeng Su, and Jie Huang. Cooperative control of multi-agent systems. Cham: SpringerVerlag, 2022. Tim Franzmeyer, Stephen Marcus McAleer, Joao F Henriques, Jakob Nicolaus Foerster, Philip Torr, Adel Bibi, and Christian Schroeder de Witt. Illusory attacks: Detectability matters in adversarial attacks on sequential decision-makers. In The Second Workshop on New Frontiers in Adversarial Machine Learning, 2023. Songyang Han, Sanbao Su, Sihong He, Shuo Han, Haizhao Yang, and Fei Miao. What is the solution for state-adversarial multi-agent reinforcement learning? Trans. Mach. Learn. Res., 2022. arXiv:2212.02705. Karel Horák, Branislav Bošanskỳ, Vojtěch Kovařík, and Christopher Kiekintveld. Solving zero-sum one-sided partially observable stochastic games. Artificial Intelligence, 316:103838, 2023. Sandy H. Huang, Nicolas Papernot, I. Goodfellow, Yan Duan, and P. Abbeel. Adversarial attacks on neural network policies. In International Conference on Learning Representations, ICLR, 2017. arXiv:1702.02284. IBM. User’s manual for cplex, 2024. URL https://www.ibm.com/docs/en/icos/22.1.2? topic=optimizers-users-manual-cplex. IBM ILOG CPLEX Optimization Studio documentation. Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99–134, 1998. 11
Narges Khakpour and David Parker. Partially-observable security games for attack-defence analysis in software systems. In Alexandre Madeira and Alexander Knapp, editors, Software Engineering and Formal Methods, pages 144–161, Cham, 2025. Springer Nature Switzerland. ISBN 978-3031-77382-2. Harold W. Kuhn. Extensive games and the problem of information. In Harold W. Kuhn and Albert W. Tucker, editors, Contributions to the Theory of Games II, volume 28 of Annals of Mathematics Studies, pages 193–216. Princeton University Press, Princeton, NJ, 1953. Cassidy Laidlaw, Stuart J Russell, and Anca Dragan. Bridging rl theory and practice with the effective horizon. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 58953–59007. Curran Associates, Inc., 2023. Yongyuan Liang, Yanchao Sun, Ruijie Zheng, and Furong Huang. Efficient adversarial training without attacking: Worst-case-aware robust reinforcement learning. In Advances in Neural Information Processing Systems, volume 35, 2022. Yongyuan Liang, Yanchao Sun, Ruijie Zheng, Xiangyu Liu, Benjamin Eysenbach, Tuomas Sandholm, Furong Huang, and Stephen McAleer. Game-theoretic robust reinforcement learning handles temporally-coupled perturbations. In International Conference on Learning Representations (ICLR), 2024. arXiv:2307.12062. Yen-Chen Lin, Zhang-Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming-Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI’17, page 3756–3762. AAAI Press, 2017. ISBN 9780999241103. Jeremy McMahan, Young Wu, Xiaojin Zhu, and Qiaomin Xie. Optimal attack and defense for reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024. arXiv:2312.00198. Sumeet R Motwani, Mikhail Baranchuk, Martin Strohmeier, Vijay Bolina, Philip H Torr, Lewis Hammond, and Christian S de Witt. Secret collusion among ai agents: Multi-agent deception via steganography. Advances in Neural Information Processing Systems, 37:73439–73486, 2024. James R. Munkres. Topology. Prentice Hall, Inc., Upper Saddle River, NJ, 2nd edition, 2000. ISBN 978-0131816299. Tuomas Oikarinen, Wang Zhang, Alexandre Megretski, Luca Daniel, and Tsui-Wei Weng. Robust deep reinforcement learning through adversarial loss. Advances in Neural Information Processing Systems, 34:26156–26167, 2021. Liviu Panait and Sean Luke. Cooperative multi-agent learning: The state of the art. Autonomous agents and multi-agent systems, 11(3):387–434, 2005. Parag C Pendharkar. Game theoretical applications for multi-agent systems. Expert Systems with Applications, 39(1):273–279, 2012. Ştefan Sarkadi, Alison R Panisson, Rafael H Bordini, Peter McBurney, Simon Parsons, and Martin Chapman. Modelling deception using theory of mind in multi-agent systems. AI Communications, 32(4):287–302, 2019. Trey Smith and Reid Simmons. Heuristic search value iteration for pomdps. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI ’04, page 520–527, Arlington, Virginia, USA, 2004. AUAI Press. ISBN 0974903906. James Tu, Tsunhsuan Wang, Jingkang Wang, Sivabalan Manivasagam, Mengye Ren, and Raquel Urtasun. Adversarial attacks on multi-agent communication. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7768–7777, 2021. Jianrui Wang, Yitian Hong, Jiali Wang, Jiapeng Xu, Yang Tang, Qing-Long Han, and Jürgen Kurths. Cooperative and competitive multi-agent systems: From optimization to games. IEEE/CAA Journal of Automatica Sinica, 9(5):763–783, 2022a. 12
Xinjun Wang, Ye Cao, Ben Niu, and Yongduan Song. A novel bipartite consensus tracking control for multiagent systems under sensor deception attacks. IEEE Transactions on Cybernetics, 53(9): 5984–5993, 2022b. Yifan Wang, Lukas Rahmann, and Olga Sorkine-Hornung. Geometry-consistent neural shape representation with implicit displacement fields. In International Conference on Learning Representations, ICLR, 2022c. arXiv:2106.05187. Yue Wang, Eloy Garcia, David Casbeer, and Fumin Zhang. Cooperative control of multi-agent systems: Theory and applications. John Wiley & Sons, 2017. Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33:21024–21037, 2020. Huan Zhang, Hongge Chen, Duane S. Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. In International Conference on Learning Representations, ICLR, 2021. arXiv:2101.08452.
13
A
Proofs
Lemma 2.1 (Robust Optimality ⇐⇒ Nash Equilibrium). Consider a zero-sum SA-MDP with finite state, action, and observation sets, nonempty perturbation sets B(s), bounded rewards, a fixed initial distribution b ∈ ∆(S), and unrestricted full-history behavioral strategy spaces Σ1 and Σ2 for the agent and the adversary, respectively. We assume perfect recall in which each player’s private history records all previously observed information and all of that player’s previous actions. For a strategy profile (σ, τ ) ∈ Σ1 × Σ2 , let V (b; σ, τ ) denote the agent’s expected return for the horizon under consideration when s0 ∼ b; when the horizon is N < ∞, we also write V N (b; σ, τ ) to make the horizon explicit. For a finite horizon, we allow γ ∈ (0, 1], with γ = 1 corresponding to the undiscounted return; for an infinite discounted horizon, we require γ ∈ (0, 1). In either case, the following equality holds for every initial distribution b ∈ ∆(S): arg max min V (b; σ, τ ) = {σ ∈ Σ1 : ∃τ ∈ Σ2 with (σ, τ ) a Nash equilibrium when s0 ∼ b} . σ∈Σ1 τ ∈Σ2
Both sets are nonempty. Proof of Lemma 2.1. Throughout, player 1 is the maximizing player, and player 2 is the minimizing player. Finite horizon. Fix a horizon N < ∞. Since all underlying alphabets are finite, the induced N -stage extensive-form zero-sum game has finitely many histories and information sets. By assumption, it has perfect recall. Let PiN be the finite set of player i’s pure complete contingent plans, where a plan specifies an action at every information set of that player, including information sets that the plan itself prevents from being reached. Let MiN := ∆(PiN ) be the corresponding mixed-strategy simplex. If uN (µ, ν) denotes the expected payoff under (µ, ν) ∈ ∗ M1N × M2N , then uN is bilinear. Von Neumann’s minimax theorem, therefore, gives (µ∗N , νN )∈ N N M1 × M2 such that ∗ ∗ uN (µ, νN ) ≤ uN (µ∗N , νN ) ≤ uN (µ∗N , ν)
∀(µ, ν) ∈ M1N × M2N .
Therefore, by Kuhn’s realization-equivalence theorem for finite perfect-recall games, there are ∗ ∗ ∗ behavioral strategies σN and τN that are realization-equivalent to µ∗N and νN , respectively [Kuhn, 1953]. Here, realization equivalence means equality of the induced distribution over terminal histories against every strategy of the opponent. Conversely, every behavioral strategy in this finite game has a realization-equivalent mixed strategy over complete contingent plans. Consequently, for arbitrary behavioral deviations σ and τ , choose realization-equivalent mixed strategies µσ and ντ . The preceding normal-form saddle inequalities imply ∗ ∗ ∗ ∗ ∗ V N (b; σ, τN ) = uN (µσ , νN ) ≤ uN (µ∗N , νN ) = V N (b; σN , τN )
and
∗ ∗ ∗ ∗ V N (b; σN , τN ) = uN (µ∗N , νN ) ≤ uN (µ∗N , ντ ) = V N (b; σN , τ ). ∗ ∗ Thus (σN , τN ) is a behavioral saddle point of the N -stage game.
Infinite discounted horizon. We obtain an infinite-horizon saddle point as a limit of finite-horizon saddle points. For n ≥ 0, let Hin denote the finite set of player i’s private histories immediately before the stage-n action. Under the information structure above, generic elements of H1n and H2n , respectively, have the forms (0) (n−1) (n−1) h1,n = a1 , o(0) , . . . , a1 ,o and (0) (0) (n−1) (n−1) (n−1) (n) h2,n = s(0) , a1 , a2 , o(0) , s(1) , . . . , a1 , a2 ,o ,s , with h1,0 = ∅ and h2,0 = (s(0) ). Let Hi :=
[ n≥0
14
Hin .
Because all underlying alphabets are finite, each Hin is finite, so Hi is countable. For h ∈ Hi , let Ai (h) be the nonempty finite set of actions available to player i at h. Thus, A1 (h) = A1 for the agent, while A2 (h) = B(s) at an adversary history whose current true state is s. Define Y Σi := ∆(Ai (h)) h∈Hi
and endow it with the product topology. Each factor ∆(Ai (h)) is a compact metrizable simplex in a finite-dimensional Euclidean space. Tychonoff’s theorem therefore implies that Σi is compact in the product topology [Munkres, 2000, Theorem 37.3]. Moreover, the probability coordinates (h, a), where h ∈ Hi and a ∈ Ai (h), form a countable set. Identifying each behavioral choice with its action probabilities therefore realizes Σi , with the product topology above, as a subspace of a countable product of copies of [0, 1], which is metrizable in the product topology [Munkres, 2000, Theorem 20.5]. Thus, each Σi , and hence the finite product Σ1 × Σ2 , is compact and metrizable. It is therefore sequentially compact [Munkres, 2000, Theorem 28.2]. For N ≥ 1, define the truncated discounted payoff N
V (b; σ, τ ) := Es0 ∼b,σ,τ
"N −1 X
# t
γ Rt .
t=0
For each player i, V N (b; ·, ·) depends only on the behavioral coordinates indexed by the finite SN −1 set n=0 Hin , namely the private histories immediately preceding actions in the first N stages. Expanding the expectation as a sum over the finitely many length-N paths shows that it is a polynomial in those coordinates and therefore is continuous in the product topology. Choose R̄ < ∞ such that |Rt | ≤ R̄ almost surely. Then, uniformly over (σ, τ ) ∈ Σ1 × Σ2 , V (b; σ, τ ) − V N (b; σ, τ ) ≤
∞ X
γ t R̄ =
t=N
R̄γ N =: εN −→ 0. 1−γ
(2)
Thus V (b; ·, ·) is the uniform limit of the continuous functions V N (b; ·, ·), so V (b; ·, ·) is jointly continuous on Σ1 × Σ2 . For every N , let (σ N , τ N ) be a behavioral saddle point of the N -stage discounted game, whose existence follows from the finite-horizon argument, and extend these strategies arbitrarily at histories occurring after stage N . Sequential compactness of Σ1 × Σ2 gives a subsequence Nk → ∞ and a profile (σ ∗ , τ ∗ ) such that (σ Nk , τ Nk ) −→ (σ ∗ , τ ∗ ). Fix arbitrary infinite-horizon strategies (σ, τ ) ∈ Σ1 × Σ2 . Their restrictions to the first Nk stages are admissible behavioral deviations in the Nk stage game. Therefore V Nk (b; σ, τ Nk ) ≤ V Nk (b; σ Nk , τ Nk ) ≤ V Nk (b; σ Nk , τ ). Using (2) gives V (b; σ, τ Nk ) ≤ V (b; σ Nk , τ Nk ) + 2εNk and
V (b; σ Nk , τ Nk ) ≤ V (b; σ Nk , τ ) + 2εNk . Joint continuity of V (b; ·, ·), convergence of the strategy profiles, and εNk → 0 now imply V (b; σ, τ ∗ ) ≤ V (b; σ ∗ , τ ∗ ) ≤ V (b; σ ∗ , τ ) ∗
∀(σ, τ ) ∈ Σ1 × Σ2 .
∗
Hence, (σ , τ ) is an infinite-horizon behavioral saddle point. Equality of the two policy sets. In either horizon model, let (σ 0 , τ 0 ) be a saddle point and set v := V (b; σ 0 , τ 0 ). The saddle inequalities give v = max min V (b; σ, τ ) = min max V (b; σ, τ ). σ∈Σ1 τ ∈Σ2
τ ∈Σ2 σ∈Σ1
15
Figure 5: MDP without History-Dependent State-Robust Policy a1 : R = 0
S1
a2 : R = 1
a2 : R = 0
a1 : R = 1
S3
S2
a2 : R = 0
a1 : R = 1
Suppose that σ b is robust-optimal. Then min V (b; σ b, τ ) = v, τ
and hence V (b; σ b, τ ) ≥ v The saddle property of (σ , τ ) also gives
∀τ ∈ Σ2 .
V (b; σ, τ 0 ) ≤ v
∀σ ∈ Σ1 .
0
0
In particular, V (b; σ b, τ 0 ) = v, and consequently V (b; σ, τ 0 ) ≤ V (b; σ b, τ 0 ) ≤ V (b; σ b, τ )
∀(σ, τ ).
0
Thus (b σ , τ ) is a saddle point, equivalently a Nash equilibrium. Conversely, if (σ̄, τ̄ ) is any Nash equilibrium, then, because the game is zero-sum, it is a saddle point, and its payoff equals the game value v. Hence min V (b; σ̄, τ ) = V (b; σ̄, τ̄ ) = v,
τ ∈Σ2
so σ̄ is robust-optimal. The existence of a saddle point also proves that both sets in the statement are nonempty. Theorem 2.2. There exists a SA-MDP such that no history-dependent policy is state-robust optimal. Proof of Theorem 2.2. We begin with a high-level overview of the proof and then proceed through the details. Let σvA be the policy that always plays a1 . In the SA-MDP of Figure 5, σvA achieves robust value 0 at 1 1 s1 and 1−γ at s2 , s3 , while uniformly mixing a1 , a2 achieves 2(1−γ) everywhere. Any state-robust A optimal σv must therefore match σv at s2 , s3 and strictly improve on it at s1 . To improve at s1 against the identity adversary, σv must, after some first observed (i.e. reported by adversary) history h∗ = (s1 , a1 , . . . , s1 ), place positive probability on a2 . But the agent conditions only on reported histories: an adversary starting from true state s3 can fabricate the same h∗ by reporting s1 at every step, since σv plays a1 surely along the prefix and the true state remains s3 . Triggering a2 at true 1 s3 strictly reduces the return, so Jσv (s3 ) < 1−γ , contradicting state-robust optimality at s3 . For a history-dependent agent policy σv and state s ∈ S, define the worst-case value Jσv (s) := min V σv ,σa (s). σa
A policy σv is state-robust optimal if Jσv (s) ≥ Jσv′ (s) for every state s and every alternative policy σv′ . Consider the SA-MDP in Figure 5. Let σvA denote the policy that always plays a1 , regardless of the reported history. Direct computation gives JσvA (s1 ) = 0,
JσvA (s2 ) = JσvA (s3 ) =
For γ = 0.99, these values are 0, 100, and 100, respectively. 16
1 . 1−γ
Now let σvB be the policy that plays each of {a1 , a2 } with probability 12 at every history. Under σvB , the expected one-step reward is 12 in every state, so JσvB (s) =
1 2(1 − γ)
for all s ∈ {s1 , s2 , s3 },
which equals 50 when γ = 0.99. Therefore, any state-robust optimal policy σv must satisfy Jσv (s1 ) ≥ 50,
Jσv (s2 ) ≥ 100,
1 Since no policy can achieve more than 1−γ
Jσv (s3 ) ≥ 100.
= 100 from s2 or s3 , any state-robust optimal policy
must in fact satisfy Jσv (s2 ) = Jσv (s3 ) =
1 1−γ
and
Jσv (s1 ) ≥
1 > 0. 2(1 − γ)
(3)
Contradiction argument. Assume for contradiction that there exists a history-dependent policy σv satisfying (3). Let σaI denote the identity adversary that always reports the true state. Since Jσv (s1 ) > 0, we have in particular I V σv ,σa (s1 ) ≥ Jσv (s1 ) > 0. Hence, starting from true state s1 against σaI , there must exist some first time step n at which σv assigns positive probability to action a2 . Otherwise, σv would play a1 surely at every step in s1 , I yielding value 0, which contradicts V σv ,σa (s1 ) > 0. By minimality of n, along the identity-adversary play starting from s1 , the reported history up to time n must be h∗ = (s1 , a1 , s1 , a1 , . . . , s1 , a1 , s1 ), i.e., n repeated reports of s1 with action a1 taken with probability 1 at all earlier time steps. After this history, the policy plays a2 with positive probability: Pr a2 h∗ > 0. σv
Mimicking the history from s3 . Now consider instead starting from true state s3 , and let σa′ be the adversary that reports s1 for the first n observations (recall s1 ∈ B(s3 ), so this is feasible). Since σv conditions only on the reported history, it plays a1 with probability 1 on the first n − 1 steps—exactly as it does along h∗ from true state s1 . Because s3 is absorbing under action a1 , the true state remains s3 throughout these steps. At time n, the reported history is again h∗ , so the policy plays a2 with positive probability. However, at true state s3 , action a2 yields reward 0 and transitions out of s3 , while a1 yields reward 1 and keeps the agent in s3 . Conditioning on the event {a2 played at step n}, which occurs with positive 1 probability under σv given h∗ , the discounted return is strictly less than 1−γ . Therefore ′
V σv ,σa (s3 ) <
1 , 1−γ
which implies ′
Jσv (s3 ) ≤ V σv ,σa (s3 ) <
1 . 1−γ
1 This contradicts (3), which required Jσv (s3 ) = 1−γ . Hence no such history-dependent policy σv can exist, and no history-dependent policy is state-robust optimal in this SA-MDP.
Theorem 2.3. Any SA-MDP Gseq can be transformed into a strategically equivalent constrained b in which both players act simultaneously at every stage. The solution zero-sum one-sided POSG G b strategy to G can be mapped back to a unique solution strategy of Gseq . Proof of Theorem 2.3. After establishing the key mathematical objects and statements to prove in the main text, we now proceed with the actual proof. 17
Preliminaries and Definitions Let σ1 (resp. σ2 ) denote the agent (resp. adversary) strategy in the sequential game Gseq , with value V seq (b; σ1 , σ2 ) = Es0 ∼b
∞ hX
i γ t R st , at1 ,
t=0
b with value and let σ b1 , σ b2 be analogous strategies in the simultaneous game G V sim (bb; σ b1 , σ b2 ) = Es0 ∼b
∞ hX i √ b xn , α n , α n , ( γ)n R 1 2 n=0
where xn , αni denote states/actions at micro–step. Define a bijection Φ : (a02 , o0 , a01 , a12 , o1 , a11 , . . . ) → (⊥1 , a02 , o0 , a01 , ⊥2 , ō, ⊥1 , a12 , o1 , a11 , ⊥2 , ō, ...) b at step 2t that interleaves each stage of Gseq into two constrained simultaneous micro-stages of G: t the attacker chooses a2 while the agent is forced to play ⊥1 , and at step 2t + 1 the agent chooses at1 while the adversary is forced to play ⊥2 . Because the non-decisive actions are fixed and observations are emitted in the same order as in the sequential game, the mapping Φ is bijective and preserves each player’s information set. Given a sequential strategy pair (σ1 , σ2 ), define the feasible simultaneous strategy pair (b σ1 , σ b2 ) by σ b1 (· | Φ(hseq ), o2t+1 ) = σ1 (· | hseq , ot ),
σ b2 (· | Φ(hseq ), x2t ) = σ2 (· | hseq ),
with σ b1 (· | Φ(hseq ), o2t ) = δ⊥1 ,
σ b2 (· | Φ(hseq ), x2t+1 ) = δ⊥2 .
Here hseq denotes the relevant player’s private history. For player 1, Φ inserts the forced dummy components into its action-observation history, while for player 2, it inserts the dummy states and actions into its full state-action history. Conversely, every feasible simultaneous strategy pair induces a unique sequential strategy pair by deleting the forced dummy moves. Definition A.1 (ϵ–equilibrium concepts). Recall that player 1 is the maximizing player and player 2 is the minimizing player. b feas × Σ b feas is an ϵ–Nash equilibrium, equivalently an ϵ–saddle A feasible strategy pair (b σ1∗ , σ b2∗ ) ∈ Σ 1 2 b if point, of G V sim (bb; σ b1 , σ b2∗ ) ≤ V sim (bb; σ b1∗ , σ b2∗ ) + ϵ V sim (bb; σ b∗ , σ b2 ) ≥ V sim (bb; σ b∗ , σ b∗ ) − ϵ 1
1
b feas ∀σ b1 ∈ Σ 1 , b ∀σ b2 ∈ Σfeas .
2
2
(4) (5)
seq A strategy pair (σ1∗ , σ2∗ ) ∈ Σseq 1 × Σ2 is an ϵ–Nash equilibrium, equivalently an ϵ–saddle point, of Gseq if
V seq (b; σ1 , σ2∗ ) ≤ V seq (b; σ1∗ , σ2∗ ) + ϵ
∀ σ1 ∈ Σseq 1 ,
(6)
V seq (b; σ1∗ , σ2 ) ≥ V seq (b; σ1∗ , σ2∗ ) − ϵ
∀ σ2 ∈ Σseq 2 .
(7)
Theorem Statements and Proofs Lemma A.2 (Exact value preservation). Under optimal play, V seq (b) = max min V seq (b; σ1 , σ2 ) = max min V sim (bb; σ b1 , σ b2 ) = V sim (bb). σ1
σ2
σ b1
σ b2
Proof. We use the bijection Φ to translate any sequential strategy pair (σ1 , σ2 ) into a feasible simultaneous pair (b σ1 , σ b2 ) and vice-versa, without altering the induced probability measure over outcome streams. Observe: 18
1. Reward alignment: by construction, the only non-zero reward in the transformed game occurs at the second micro-stage x2t+1 , and b 2t+1 , α2t+1 , α2t+1 ) = √1 R(st , at1 ). R(x 1 2 γ 2. Discount consistency: therefore √ b 2t+1 , α2t+1 , α2t+1 ) = (√γ)2t+1 √1 R(st , at1 ) = γ t R(st , at1 ). ( γ)2t+1 R(x 1 2 γ 3. Measure preservation: at each original stage, corresponding strategies assign the same probabilities to the attacker’s report and the agent’s action. The inserted moves are deterministic, and the second micro-stage uses the same transition probability p(st+1 | st , at1 ). Hence, after deleting the dummy components, corresponding trajectories have the same probability. 4. Feasibility preservation: the singleton constraints ensure that the transformed game introduces no additional strategic choices beyond those already present in Gseq . Therefore, for any corresponding strategy pair, V seq (b; σ1 , σ2 ) = V sim (bb; σ b1 , σ b2 ). Taking max–min over admissible strategies yields the desired equality. Lemma A.3 (ϵ-equilibrium correspondence). Fix an initial belief b. For each player i ∈ {1, 2}, let b feas Φi : Σseq −→ Σ i i b be a bijection between the behavioral strategies in Gseq and the feasible behavioral strategies in G. Suppose that, for every (σ1 , σ2 ), V seq (b; σ1 , σ2 ) = V sim bb; Φ1 (σ1 ), Φ2 (σ2 ) . Then (σ1∗ , σ2∗ ) is an ϵ-Nash equilibrium of Gseq if and only if Φ1 (σ1∗ ), Φ2 (σ2∗ ) is an ϵ-Nash equilibb rium of G. Proof. Write
σ bi∗ = Φi (σi∗ ),
i ∈ {1, 2}.
b feas , Assume first that (σ1∗ , σ2∗ ) is an ϵ-Nash equilibrium of Gseq . For any feasible deviation σ b1 ∈ Σ 1 −1 bijectivity gives σ1 = Φ1 (b σ1 ). Hence, V sim (bb; σ b1 , σ b2∗ ) = V seq (b; σ1 , σ2∗ ) ≤ V seq (b; σ1∗ , σ2∗ ) + ϵ = V sim (bb; σ b∗ , σ b∗ ) + ϵ. 1
2
b feas , setting σ2 = Φ−1 (b Similarly, for any feasible deviation σ b2 ∈ Σ σ2 ) yields 2 2 V sim (bb; σ b1∗ , σ b2 ) = V seq (b; σ1∗ , σ2 ) ≥ V seq (b; σ1∗ , σ2∗ ) − ϵ = V sim (bb; σ b∗ , σ b∗ ) − ϵ. 1
2
b The converse follows by the same argument, applying Thus, (b σ1∗ , σ b2∗ ) is an ϵ-Nash equilibrium of G. −1 the inverse bijections Φi to arbitrary deviations in Gseq . Finally, the feasible strategy spaces of b admit no additional deviations at dummy micro-stages, since the acting player has a singleton G b corresponds uniquely to a deviation feasible action set there. Therefore, every feasible deviation in G in Gseq , as required. Lemma A.4 (Well-defined strategy correspondence). The bijection Φ ensures a one-to-one correb and strategies in Gseq . spondence between strategies in G 19
Proof. By construction of Φ. This concludes the proof of Theorem 2.3. Theorem 2.5. The HSVI algorithm of Horák et al. [2023] extends to the constrained zero-sum onesided POSG in Definition 2.4 by restricting each local stage game to the players’ feasible strategy sets. The algorithm maintains a lower-bound value function VLB and an upper-bound value function Γ VU B , written as VLB and VUΥB , respectively, in Algorithm 2, satisfying VLB (b) ≤ V ∗ (b) ≤ VU B (b) for every reachable belief b, where V ∗ is the optimal value function of the constrained game. Let
U0 − L0 , 2 where L0 and U0 are the discounted minimum and maximum feasible reward bounds. If δ = 0, the initial bounds coincide. If δ > 0 and δ=
(1 − γ)ϵ , 2δ then the algorithm terminates at the initial belief b0 with 0<D<
VU B (b0 ) − VLB (b0 ) ≤ ϵ. The strategy obtained from the lower-bound value function for player 1 and the strategy obtained from the upper-bound value function for player 2 are feasible and form an ϵ-Nash equilibrium. In b constructed in Theorem 2.3. particular, the result applies to the constrained OS-POSG G Proof of Theorem 2.5. We adapt the proof of Horák et al. [2023] by restricting the action sets in each local stage game. We state the parts of their argument that are unchanged and make explicit where the feasibility restrictions enter. Model and feasible stage strategies. At a player-1 information history h1 , let S(h1 ) be the states that may be current at that history. By the condition in Definition 2.4, all states in S(h1 ) have the common feasible action set L1 (h1 ). Thus, at a belief b ∈ ∆(S(h1 )), the stage strategies are Y π1 ∈ Π1 (h1 ) := ∆(L1 (h1 )), π2 ∈ Π2 (h1 ) := ∆(L2 (s)). s∈S(h1 )
Player 1 therefore uses one distribution over L1 (h1 ); only player 2 may condition its action on the current state. Both strategy sets are nonempty, compact, and convex. Fix b ∈ ∆(S(h1 )), a1 ∈ L1 (h1 ), and π2 ∈ Π2 (h1 ). Define X X p(o, s′ | b, a1 , π2 ) = b(s)π2 (a2 | s)T (o, s′ | s, a1 , a2 ),
Belief update.
s∈S(h1 ) a2 ∈L2 (s)
P (o | b, a1 , π2 ) =
X
p(o, s′ | b, a1 , π2 ).
s′ ∈S
For the successor history h′1 = (h1 , a1 , o), the states that may be current are S(h′1 ) = {s′ ∈ S : T (o, s′ | s, a1 , a2 ) > 0 for some s ∈ S(h1 ), a2 ∈ L2 (s)} . Action-observation pairs for which S(h′1 ) = ∅ are omitted from all continuation sums and lowerbound constraints, since their probability is zero under every feasible stage strategy. Thus S(h′1 ) depends only on S(h1 ), a1 , and o, and every posterior generated by a feasible π2 on a remaining branch is supported on S(h′1 ). When P (o | b, a1 , π2 ) > 0, player 1’s posterior after observing its action a1 and observation o is τ (b, a1 , π2 , o)(s′ ) = 20
p(o, s′ | b, a1 , π2 ) . P (o | b, a1 , π2 )
(8)
On a zero-probability branch, the posterior may be chosen arbitrarily in ∆(S(h′1 )). If player 1 uses π1 , the probability of the branch (a1 , o) is Pr [a1 , o] = π1 (a1 )P (o | b, a1 , π2 ).
b,π1 ,π2
The factor π1 (a1 ) does not appear in (8) because player 1 conditions on the action it took. The condition in Definition 2.4 also ensures that every positive-probability successor belief is supported on a set of states with one common feasible action set for player 1. For a feasible strategy σ1 of player 1, define X Vσ1 (b) = inf Eb,σ1 ,σ2 γ t−1 R(st , a1t , a2t ) , V ∗ (b) = sup Vσ1 (b),
Values and structure.
σ2
σ1
t≥1
where both optimizations are over feasible behavioral strategies. Since player 2 observes the state, a best response to a fixed σ1 can be chosen separately for each initial state. Hence Vσ1 is affine in b on each ∆(S(h1 )), and V ∗ is convex there. Let Rmin = Rmax = L0 =
min
R(s, a1 , a2 ),
max
R(s, a1 , a2 ),
s∈S, a1 ∈L1 (s), a2 ∈L2 (s) s∈S, a1 ∈L1 (s), a2 ∈L2 (s)
Rmin , 1−γ
U0 =
Rmax , 1−γ
δ=
U0 − L 0 . 2
Then L0 ≤ Vσ1 (b) ≤ U0 . As in Horák et al. [2023], every Vσ1 , and therefore V ∗ , is δ-Lipschitz in ∥·∥1 on each ∆(S(h1 )). Bellman operator. Let V be a bounded convex continuous continuation value on the reachable beliefs. At b ∈ ∆(S(h1 )), define uV,b (π1 , π2 ) = Eb,π1 ,π2 [R(s, a1 , a2 )] X X +γ Pr [a1 , o]V τ (b, a1 , π2 , o) , a1 ∈L1 (h1 ) o∈O
[HV ](b) =
max
min
b,π1 ,π2
π1 ∈Π1 (h1 ) π2 ∈Π2 (h1 )
uV,b (π1 , π2 ),
where zero-probability branches contribute zero. For fixed π2 , this payoff is affine in π1 . For fixed π1 , each continuation term is the perspective of the convex function V and is therefore continuous and convex in π2 . Sion’s minimax theorem gives max
min
π1 ∈Π1 (h1 ) π2 ∈Π2 (h1 )
uV,b (π1 , π2 ) =
min
max
π2 ∈Π2 (h1 ) π1 ∈Π1 (h1 )
uV,b (π1 , π2 ).
Thus the local stage game has a value and feasible optimal strategies. The value-composition argument of Horák et al. [2023] applies on each ∆(S(h1 )). It follows that H maps convex δLipschitz continuation values to convex δ-Lipschitz values on the current simplex. For any bounded V and W , ∥HV − HW ∥∞ ≤ γ∥V − W ∥∞ , where the supremum is over all reachable beliefs. The proof is unchanged: for fixed stage strategies, replacing V by W changes the expected continuation value by at most γ∥V − W ∥∞ , and taking the maximum and minimum preserves the inequality. Moreover, every feasible strategy of player 1 after h1 consists of a feasible distribution in ∆(L1 (h1 )) and feasible continuation strategies after each (a1 , o), and every such choice defines a feasible behavioral strategy. The strategy-decomposition argument of Horák et al. [2023] therefore gives HV ∗ = V ∗ . Hence H has a unique fixed point, which is V ∗ . 21
Lower-bound stage program. The lower bound is represented by sets of α-vectors, one for each distinct set S(h1 ). Consider a point update at b ∈ ∆(S(h1 )). For each (a1 , o), write h′1 = (h1 , a1 , o) for the successor information history, and let Γa1 ,o = {α1a1 ,o , . . . , αkaa1 ,o,o } be the current lower-bound 1 vectors on that successor set S(h′1 ). The lower-bound program of Horák et al. [2023] becomes X max b(s)Vs b α,Vs π1 ,λ,b
s.t.
s∈S(h1 )
X
Vs ≤
π1 (a1 )R(s, a1 , a2 )
a1 ∈L1 (h1 )
X
+γ
X
X
T (o, s′ | s, a1 , a2 )b αa1 ,o (s′ )
∀s ∈ S(h1 ), a2 ∈ L2 (s),
a1 ∈L1 (h1 ) o∈O s′ ∈S(h′1 ) ka1 ,o
α ba1 ,o (s′ ) =
X
∀a1 ∈L1 (h1 ), o∈O, s′ ∈S(h′1 ),
ba1 ,o αa1 ,o (s′ ) λ i i
i=1 ka1 ,o
X
ba1 ,o = π1 (a1 ) λ i
∀a1 ∈ L1 (h1 ), o ∈ O,
i=1
X
π1 (a1 ) = 1,
π1 ≥ 0,
b ≥ 0. λ
a1 ∈L1 (h1 )
For every a1 with π1 (a1 ) > 0, set αa1 ,o =
α ba1 ,o ∈ conv(Γa1 ,o ). π1 (a1 )
When π1 (a1 ) = 0, choose αa1 ,o arbitrarily from conv(Γa1 ,o ). The vector added to the lower bound is the one-step vector obtained from π1 and these continuation vectors. Equivalently, it is defined on every s ∈ S(h1 ) by the minimum of the right-hand side of the first constraint over a2 ∈ L2 (s). This fixes every coordinate of the new vector, including states to which b assigns zero probability, and its value at b equals the optimal objective of the program. The only changes are the restrictions a1 ∈ L1 (h1 ), a2 ∈ L2 (s), and the use of the lower-bound vectors for the successor belief. The vector α ba1 ,o is already multiplied by the probability π1 (a1 ), since its mixture weights sum to π1 (a1 ); it is therefore not multiplied by π1 (a1 ) again. The dual is the dual of Horák et al. [2023] with one realization weight b(s)π2 (a2 | s) for every a2 ∈ L2 (s). Both programs are finite, feasible, and bounded, so strong duality holds. Bounds and point updates. For each distinct S(h1 ), initialize the lower bound with the constant vector L0 and the upper bound with the points (es , U0 ), s ∈ S(h1 ). The first is a valid lower bound because no feasible strategy can receive less than L0 . The lower δ-Lipschitz envelope of the upper points is the constant U0 and is a valid upper bound. Every vector produced by the lower-bound program combines a feasible local strategy of player 1 with continuation vectors that already lower-bound the values of feasible continuation strategies. Following those strategies after the corresponding (a1 , o) therefore gives a feasible behavioral strategy whose value is at least the new vector. Convex combinations of stored vectors remain valid because player 1 can randomize privately among the corresponding strategies. It follows by induction that the lower bound remains valid after every point update. Moreover, every coordinate of every lower-bound vector remains in [L0 , U0 ]. This is true initially, and the one-step construction preserves these bounds because Rmin + γL0 = L0 and Rmax + γU0 = U0 . Each vector therefore defines a δ-Lipschitz linear function, and their pointwise maximum is also δ-Lipschitz. For the upper bound, add the point (b, [HVU B ](b)) and take the same lower δ-Lipschitz envelope as Horák et al. [2023], using only points on the current ∆(S(h1 )). If the stored points upper-bound V ∗ , then monotonicity of H gives [HVU B ](b) ≥ [HV ∗ ](b) = V ∗ (b), so the new point is also valid. Convexity and the δ-Lipschitz property then show that the updated envelope upper-bounds V ∗ throughout that simplex. No interpolation is performed between sets with 22
different feasible actions. Thus, throughout the algorithm, VLB (b) ≤ V ∗ (b) ≤ VU B (b). The same updates also preserve the two inequalities used by the strategy construction of Horák et al. [2023]. For the initial lower vector, any feasible π1 together with the same constant continuation gives a one-step value of at least L0 . Every subsequently added vector is the one-step vector obtained from the feasible π1 returned by the lower-bound program and continuation vectors in the corresponding P sets conv(Γa1 ,o ). The same property holds for convex combinations. Indeed, if α = j λj αj , use P π1 = j λj π1j and, after an action a1 with π1 (a1 ) > 0, mix the corresponding continuation vectors with weights λj π1j (a1 )/π1 (a1 ). This gives a feasible one-step vector that dominates α coordinatewise. For the upper bound, [HVU B ](b) ≤ VU B (b) holds initially because HU0 ≤ Rmax + γU0 = U0 , and it continues to hold after every update. To see the latter, let VU′ B be the envelope after adding a point. Since VU′ B ≤ VU B , every old point (bi , yi ) satisfies yi ≥ VU B (bi ) ≥ [HVU B ](bi ) ≥ [HVU′ B ](bi ), and the new point satisfies [HVU B ](b) ≥ [HVU′ B ](b). The convexity and δ-Lipschitz continuity of HVU′ B then imply that its lower δ-Lipschitz envelope, VU′ B , also lies above HVU′ B . This is the same argument as in Horák et al. [2023], applied separately on each ∆(S(h1 )). Termination. ρ(0) = ϵ,
If δ = 0, the initial bounds coincide. Suppose δ > 0 and define ρ(t + 1) =
ρ(t) − 2δD , γ
excess(b, t) = VU B (b) − VLB (b) − ρ(t).
Let π1U B be optimal in the upper-bound stage game and π2LB be optimal in the lower-bound stage game. The saddle-point inequalities give X [HVU B ](b) − [HVLB ](b) ≤ γ Pr [a1 , o] a1 ,o
b,π1U B ,π2LB
× VU B − VLB
τ (b, a1 , π2LB , o) .
Consequently, the forward rule of Horák et al. [2023] is unchanged: it selects the branch maximizing its probability multiplied by the successor excess, using the action-conditioned posterior in (8). If the selected quantity is nonpositive, every positive-probability successor has gap at most ρ(t + 1). After the point update, the preceding inequality gives VU B (b) − VLB (b) ≤ γρ(t + 1) = ρ(t) − 2δD. Both bounds are δ-Lipschitz on the current simplex, so their difference is 2δ-Lipschitz. Hence every belief in that simplex within distance D of b has nonpositive excess at depth t. If 0<D<
(1 − γ)ϵ , 2δ
then ρ(t) eventually exceeds the largest possible bound gap, so the recursion depth is finite. Fix a depth t and a structural state set S(h1 ), and consider the last belief reached by each trial that terminates there. After the point update at such a belief b, the excess is nonpositive throughout the D-neighborhood of b in ∆(S(h1 )). Later updates can only reduce the gap, so a later trial can terminate at that depth and state set only at a belief more than D from b. These terminal beliefs are therefore D-separated. Compactness of each ∆(S(h1 )), together with the finite recursion depth and the finitely many distinct subsets S(h1 ) ⊆ S, implies that only finitely many trials occur. Hence the algorithm terminates with VU B (b0 ) − VLB (b0 ) ≤ ϵ. 23
Strategy extraction. The strategy construction of Horák et al. [2023] uses exactly the two inequalities established above. For player 1, begin with a lower-bound vector α attaining VLB (b0 ). At each information history, play the feasible distribution associated with α and, after observing (a1 , o), replace α by the associated continuation vector in conv(Γa1 ,o ). This construction depends only on player 1’s action-observation history and the retained continuation vector; it does not require player 1 to know the current belief. If it is followed for K stages and an arbitrary feasible strategy is used thereafter, the finite-horizon induction of Horák et al. [2023] gives a value of at least VLB (b0 ) − γ K (U0 − L0 ). Letting K → ∞ gives a feasible strategy σ1LB such that inf V (b0 ; σ1LB , σ2 ) ≥ VLB (b0 ). σ2
For player 2, choose at each stage the minimizing strategy in [HVU B ](b). Player 2 observes the current state and knows the stage strategies it has used, so it can update b by (8). The inequality HVU B ≤ VU B gives, after K stages and an arbitrary feasible continuation, an upper bound of VU B (b0 ) + γ K (U0 − L0 ). Letting K → ∞ gives a feasible strategy σ2U B such that sup V (b0 ; σ1 , σ2U B ) ≤ VU B (b0 ). σ1
Since the two bounds differ by at most ϵ, neither player can gain more than ϵ by deviating. Thus (σ1LB , σ2U B ) is an ϵ-Nash equilibrium, equivalently an ϵ-saddle point. b constructed in Theorem 2.3 satisfies the required condition. In an original state, Finally, the game G player 1 has the common feasible action set {⊥1 }; in a dummy state, it has the common feasible action set Av . Player 1 observes which phase is being played, while player 2 observes the transformed b state and uses B(s) or {⊥2 } as appropriate. The result therefore applies to G.
B
Numerically Discovered SA-MDP Strategies
We use the standard game theory notation for mixed strategies p[A] + (1 − p)[B] to indicate a mixed strategy that plays action A with probability p and B with probability 1 − p, and A to indicate the pure strategy that plays A. We write the adversary’s reporting strategies the same way. B.1
Markovian Strategies
Agent We find Markovian equilibrium strategies, π1 (s0 ) = A, π1 (s1 ) = A, π1 (s2 ) = B, π1 (s3 ) = C, given observations s0 , s1 , s2 , s3 . Adversary We find equilibrium strategies ν(·|s0 ) = s0 , ν(·|s1 ) = s2 , ν(·|s2 ) = 12 [s2 ] + 12 [s3 ], ν(·|s3 ) = s3 . B.2
History Dependent Strategies
Agent Let π1 (s0 ) denote our agent’s strategy at state s0 in the first stage, and π1 (a, s̃) denote our agent’s optimal strategy after playing action a in the first stage and receiving observation s̃. Our agent’s strategy is π1 (s0 ) = A, π1 (A, s̃i ) = B for s̃i ∈ {s2 , s3 } for on-policies strategies. Off-policy, our agent best responds π1 (B, s̃i ) = B for s̃i ∈ {s2 , s3 }. Finally, again off-policy, our agent best responds π1 (C, s0 ) = A. Adversary Our adversary best responds as: At state s0 : ν(·|s0 ) = s0 . After A (on policy): ν(·|s2 , A) = 31 [s2 ] + 23 [s3 ], ν(·|s3 , A) = 1. After B, off-policy: ν(·|si , B) = s2 , for si ∈ {s1 , s2 }. After C, off-policy: ν(·|s0 , C) = s0 (which is forced due to trivial constraint).
C
Analysis of Example SA-MDP Game Where History Matters
C.1
Setup
The state space and initial distribution are given by S = {s0 , s1 , s2 , s3 , t}, µ0 = δs0 . The action space is A = {A, B, C}. Horák et al. [2023] solve for infinite horizon settings. Therefore, we choose 24
γ ∼ 1, and add absorbing states after t = 2 that return reward 0 from then on to convert our finite horizon setting to an infinite horizon game. Similarly, t is added to our state space. To simplify the notation of our SA-MDP, we drop this dependence on t, with the understanding that after t = 2, rewards are 0 from then on and all transition probabilities from a state to itself are 1 regardless of the action taken. Transitions
Only transitions out of s0 are nontrivial. Transitions are given by
p(s2 | s0 , A) = 12 ,
p(s3 | s0 , A) = 12 ,
p(s1 | s0 , A) = 0,
(9)
p(s1 | s0 , B) = 12 ,
p(s2 | s0 , B) = 12 ,
p(s3 | s0 , B) = 0,
(10)
p(s0 | s0 , C) = 1.
(11)
All other states are absorbing. Reward
We take R(s, a, s′ ) ≡ R(s, a) and specify R as s0 s1 s2 s3
Adversary Constraint Sets
A 0 0 −1 −2
B 0 −2 2 −2
C −10 0 −1 0
We restrict the adversary to report only “neighboring” states: B(s0 ) = {s0 }, B(s1 ) = {s1 , s2 }, B(s2 ) = {s2 , s3 }, B(s3 ) = {s1 , s3 }.
(12)
where at s0 the agent has to report the (trivial) true initial state. C.2
Markovian vs history-dependent observation adversaries
A Markovian adversary is any kernel ν(s̃ | s) such that supp(ν(· | s)) ⊆ B(s) for each s. Because B(s0 ) = {s0 }, we have ν(s0 | s0 ) = 1. For s1 , s2 , s3 , every such Markovian kernel can be parameterized by (t1 , t2 , t3 ) ∈ [0, 1]3 : ν(s1 | s1 ) = t1 , ν(s2 | s2 ) = t2 , ν(s1 | s3 ) = 1 − t3 ,
ν(s2 | s1 ) = 1 − t1 , ν(s3 | s2 ) = 1 − t2 , ν(s3 | s3 ) = t3 .
(13)
A history-dependent adversary is allowed to choose its reporting kernel as a function of the full history (past states/actions/observations). So the adversary is powerless at s0 (it must report s0 ), and only matters at the second stage. C.3
Markovian vs history-dependent observation adversaries
A Markovian adversary is given by a “Markov misreporting kernel” ν(s̃ | s) such that supp(ν(· | s)) ⊆ B(s) for each s. Because B(s0 ) = {s0 }, we have ν(s0 | s0 ) = 1. For s1 , s2 , s3 , every such Markovian kernel can be parameterized by (t1 , t2 , t3 ) ∈ [0, 1]3 : ν(s1 | s1 ) = t1 , ν(s2 | s2 ) = t2 , ν(s1 | s3 ) = 1 − t3 ,
ν(s2 | s1 ) = 1 − t1 , ν(s3 | s2 ) = 1 − t2 , ν(s3 | s3 ) = t3 .
(14)
A history-dependent adversary is allowed to choose its reporting kernel as a function of the full history (past states/actions/observations). 25
C.4
Markovian adversary: best responses and value
The analysis of the Markovian adversary is a fair amount of exhaustion by cases due to the division of the simplex into 4 regions, each satisfying both, either, or none of them. Setup Fix a Markovian misreporting kernel (14). Let vA (t2 , t3 ) denote the agent’s best-response value if it commits to playing action A in state s0 , and similarly vB (t1 , t2 ) the value if it commits to playing action B in s0 . Against the kernel (t1 , t2 , t3 ), the agent’s best value is F (t1 , t2 , t3 ) := max{vA (t2 , t3 ), vB (t1 , t2 )}. We compute vA and vB , then minimize F over (t1 , t2 , t3 ) ∈ [0, 1]3 . Branch A: value vA (t2 , t3 ) Under action A at s0 , the prior at the second stage is pA = (0, 12 , 12 ) over (s1 , s2 , s3 ). From s2 and s3 , the observation distributions are • s2 : report s2 with prob. t2 , report s3 with prob. 1 − t2 . • s3 : report s1 with prob. 1 − t3 , report s3 with prob. t3 . Total report probabilities under the A-branch: P(s̃ = s1 | A) = 0.5(1 − t3 ), P(s̃ = s2 | A) = 0.5t2 , P(s̃ = s3 | A) = 0.5(1 − t2 ) + 0.5t3 . Report s1 . Only s3 can produce report s1 , so P (s3 | s̃ = s1 ) = 1. From (C.1), action C is uniquely optimal at s3 with value 0. Report s2 . Only s2 can produce report s2 , so P (s2 | s̃ = s2 ) = 1. At s2 , action B is optimal with value 2. Report s3 .
Report s3 can come from s2 or s3 . Using Bayes’ rule to update beliefs, given w2 := P(s̃ = s3 , s2 | A) = 0.5(1 − t2 ), w3 := P(s̃ = s3 , s3 | A) = 0.5t3
we get P (s2 | s̃ = s3 , A) =
w2 1 − t2 = =: p. w2 + w3 1 − t 2 + t3
Expected payoffs for the report s3 : E[R | A, s̃ = s3 , A] = p(−1) + (1 − p)(−2) = −2 + p, E[R | B, s̃ = s3 , A] = p(2) + (1 − p)(−2) = −2 + 4p, E[R | C, s̃ = s3 , A] = p(−1) + (1 − p)(0) = −p. Comparisons show that • B beats C iff p ≥ 0.4. • B always beats A (for p ≥ 0). • C always beats A (for p ≤ 1). So, the best action for the report s3 is B if p ≥ 0.4 and C if p < 0.4. In terms of (t2 , t3 ), p ≥ 0.4 ⇐⇒
1 − t2 ≥ 0.4 ⇐⇒ 3 − 3t2 − 2t3 ≥ 0. 1 − t 2 + t3
Define the region CA := {(t2 , t3 ) : 3 − 3t2 − 2t3 ≥ 0}. 26
Case A1: (t2 , t3 ) ∈ CA (so report s3 7→ B).
Branch-A value.
From s2 we always play B and get 2. From s3 we play C with prob. 1 − t3 (payoff 0) and B with prob. t3 (payoff −2), so E[R | s3 ] = −2t3 . Thus, vA (t2 , t3 ) = 0.5 · 2 + 0.5 · (−2t3 ) = 1 − t3 . Case A2: (t2 , t3 ) ∈ / CA (so report s3 7→ C). From s2 , report s2 leads to B (payoff 2) and report s3 leads to C (payoff −1), so E[R | s2 ] = t2 · 2 + (1 − t2 )(−1) = 3t2 − 1. From s3 we always play C and get 0. Hence, vA (t2 , t3 ) = 0.5(3t2 − 1) + 0.5(0) = 1.5t2 − 0.5. In summary: vA (t2 , t3 ) = Branch B: value vB (t1 , t2 )
1 − t3 , 1.5t2 − 0.5,
if 3 − 3t2 − 2t3 ≥ 0, if 3 − 3t2 − 2t3 < 0.
(15)
Under action B at s0 , the prior at the second stage is pB = ( 21 , 12 , 0).
From s1 and s2 : • s1 : report s1 with prob. t1 , report s2 with prob. 1 − t1 . • s2 : report s2 with prob. t2 , report s3 with prob. 1 − t2 . Total report probabilities under the B-branch: P(s̃ = s1 | B) = 0.5t1 , P(s̃ = s2 | B) = 0.5(1 − t1 ) + 0.5t2 , P(s̃ = s3 | B) = 0.5(1 − t2 ). Report s1 .
Only s1 can produce report s1 ; best action is A (value 0).
Report s3 .
Only s2 can produce report s3 ; best action is B (value 2).
Report s2 .
Report s2 can come from s1 or s2 . Let w1 = P(s̃ = s2 , s1 | B) = 0.5(1 − t1 ), w2 = P(s̃ = s2 , s2 | B) = 0.5t2 .
Then 1 − t1 1 − t 1 + t2 t2 P (s2 | s̃ = s2 , B) = . 1 − t 1 + t2 P (s1 | s̃ = s2 , B) =
Expected payoffs for the report s2 : t2 , 1 − t 1 + t2 t2 , E[R | C, s̃ = s2 , B] = − 1 − t 1 + t2 −2(1 − t1 ) + 2t2 −2 + 2t1 + 2t2 E[R | B, s̃ = s2 , B] = = . 1 − t 1 + t2 1 − t 1 + t2 E[R | A, s̃ = s2 , B] = −
So B beats A/C iff −2 + 2t1 + 2t2 ≥ −t2 ⇐⇒ 2t1 + 3t2 ≥ 2. Define the region CB := {(t1 , t2 ) : 2t1 + 3t2 ≥ 2}. 27
Branch-B value.
Case B1: (t1 , t2 ) ∈ CB (so report s2 7→ B).
Mapping: report s1 7→ A, report s2 7→ B, report s3 7→ B. From s1 we know that report s1 gives A (payoff 0) and report s2 gives B (payoff −2), so E[R | s1 ] = −2(1 − t1 ). From s2 : both reports lead to B, so E[R | s2 ] = 2. Thus, vB (t1 , t2 ) = 0.5[−2(1 − t1 )] + 0.5 · 2 = t1 . Case B2: (t1 , t2 ) ∈ / CB (so report s2 7→ A). Mapping: report s1 7→ A, report s2 7→ A, report s3 7→ B. From s1 : always A, so E[R | s1 ] = 0. From s2 : report s2 gives A (−1), report s3 gives B (2), so E[R | s2 ] = t2 (−1) + (1 − t2 )2 = 2 − 3t2 . Hence, vB (t1 , t2 ) = 0.5(0) + 0.5(2 − 3t2 ) = 1 − 1.5t2 . In summary: vB (t1 , t2 ) = C.5
t1 , if 2t1 + 3t2 ≥ 2, 1 − 1.5t2 , if 2t1 + 3t2 < 2.
(16)
Minimizing the Markovian worst-case value
For each kernel (t1 , t2 , t3 ), the agent’s best-response value is F (t1 , t2 , t3 ) = max{vA (t2 , t3 ), vB (t1 , t2 )}, with vA and vB given by (15)–(16). The Markovian adversary’s minimax problem is VMarkov :=
inf
t1 ,t2 ,t3 ∈[0,1]
F (t1 , t2 , t3 ).
The domain splits into four regions depending on whether the conditions defining vA and vB hold: CA : 3 − 3t2 − 2t3 ≥ 0, CB : 2t1 + 3t2 ≥ 2. We consider all four combinations. On each region, vA and vB are linear, and F is the maximum of two linear functions. Region 1: CA and CB both hold.
Here vA = 1 − t3 and vB = t1 , so F = max{1 − t3 , t1 }.
To minimize F we equalize the two arguments t1 = 1 − t3 . We substitute these into CB 2(1 − t3 ) + 3t2 ≥ 2 ⇐⇒ 3t2 ≥ 2t3 ⇐⇒ t2 ≥ 23 t3 . From CA 3 − 3t2 − 2t3 ≥ 0 ⇐⇒ 3t2 ≤ 3 − 2t3 ⇐⇒ t2 ≤ 1 − 23 t3 . Together, both constraints imply 2 2 3 t3 ≤ 1 − 3 t3
⇐⇒ t3 ≤ 34 .
On the equality line Appendix C.5, F = t1 = 1 − t3 , which is minimized by taking t3 as large as possible, i.e. t3 = 3/4, giving Fmin,Region 1 = 1 − 43 = 14 . 28
Here vA = 1 − t3 and vB = 1 − 1.5t2 , so
Region 2: CA holds, CB fails.
F = max{1 − t3 , 1 − 1.5t2 }. Equalizing gives 1 − t3 = 1 − 1.5t2 ⇐⇒ t3 = 1.5t2 . Constraint CA with t3 = 1.5t2 : 3 − 3t2 − 2(1.5t2 ) ≥ 0 ⇐⇒ 3 − 6t2 ≥ 0 ⇐⇒ t2 ≤ 0.5. The condition ¬CB : 2t1 + 3t2 < 2 only restricts t1 and can be satisfied for some t1 at any given t2 ≤ 0.5, so it does not constrain t2 further. On the equality line t3 = 1.5t2 , the value is F = 1 − 1.5t2 , minimized by taking t2 as large as possible, i.e. t2 = 0.5, giving Fmin,Region 2 = 1 − 1.5 · 0.5 = 0.25. Here vA = 1.5t2 − 0.5 and vB = t1 , so
Region 3: CA fails, CB holds.
F = max{1.5t2 − 0.5, t1 }. Equalizing gives t1 = 1.5t2 − 0.5. Constraint CB becomes 2(1.5t2 − 0.5) + 3t2 ≥ 2 ⇐⇒ 3t2 − 1 + 3t2 ≥ 2 ⇐⇒ 6t2 ≥ 3 ⇐⇒ t2 ≥ 0.5. The condition ¬CA : 3 − 3t2 − 2t3 < 0 is 3t2 + 2t3 > 3. For any t2 ≥ 0.5 this can be satisfied (e.g., by choosing t3 close to 1), so it does not restrict t2 beyond t2 ≥ 0.5. On the equality line, F = t1 = 1.5t2 − 0.5, minimized at t2 = 0.5: Fmin,Region 3 = 1.5 · 0.5 − 0.5 = 0.25. Region 4: CA and CB both fail.
Here vA = 1.5t2 − 0.5 and vB = 1 − 1.5t2 , so
F = max{1.5t2 − 0.5, 1 − 1.5t2 }, which depends only on t2 . Equalizing: 1.5t2 − 0.5 = 1 − 1.5t2 ⇐⇒ 3t2 = 1.5 ⇐⇒ t2 = 0.5. At t2 = 0.5 we get F = 1.5 · 0.5 − 0.5 = 0.25. Here, the failure of CA and CB requires 3 − 3t2 − 2t3 < 0 ⇐⇒ t3 > 0.75, 2t1 + 3t2 < 2 ⇐⇒ t1 < 0.25, so, for example, (t1 , t2 , t3 ) = (0, 0.5, 0.8) lies in Region 4 and has F = 0.25. 29
Conclusion In all four regions, the infimum of F (t1 , t2 , t3 ) is 1/4. We also have explicit triples (for example (0, 0.5, 0.8)) that achieve F = 1/4. Thus, VMarkov = = =
inf
F (t1 , t2 , t3 )
min
F (t1 , t2 , t3 )
t1 ,t2 ,t3 ∈[0,1] t1 ,t2 ,t3 ∈[0,1]
1 . 4
Moreover, for any such minimizing kernel ν ∗ , the best-response value is exactly 1/4, so no (pure) agent strategy can achieve expected reward strictly larger than 1/4 against this optimal Markovian adversary. C.6
History-dependent adversary
Now, allow a history-dependent adversary that can use one kernel on the A-subtree and a different kernel on the B-subtree. Concretely, at the second stage it may choose: ν A (· | s) after first-stage action A and
ν B (· | s) after first-stage action B,
each respecting the same neighbor constraint (12). Then, two crucial facts in this new history dependent strategy are: 1. The agent has a baseline strategy with value 0 against any adversary: play any mix of A and B at s0 , and at the second stage always play action B regardless of the reported state. Under the A-branch, states {s2 , s3 } yield payoffs +2 and −2 with equal probability; under the B-branch, states {s1 , s2 } yield payoffs −2 and +2 with equal probability. In both cases, the expectation is 0, and misreporting does not matter if reports are ignored. Hence, VHist ≥ 0. 2. On each branch separately, the adversary can drive the agent’s best-response value down to 0. The first fact is self-explanatory; however, the second fact requires some additional work. For the second fact, we show that there are branch-specific values that satisfy inf vA (t2 , t3 ) = 0,
inf vB (t1 , t2 ) = 0.
t2 ,t3
t1 ,t2
For example, • On the A-branch, take (t2 , t3 ) = (0, 1), which lies in CA and gives vA = 1 − t3 = 0. • On the B-branch, take (t1 , t2 ) = (0, 2/3), which lies in ¬CB and gives vB = 1 − 1.5 · (2/3) = 0. A history-dependent adversary can therefore use ν A with (t2 , t3 ) = (0, 1) on the A-subtree and ν B with (t1 , t2 ) = (0, 2/3) on the B-subtree. Then any policy that commits to A can achieve at most 0 on that branch, any policy that commits to B can achieve at most 0 on that branch, and mixing yields a convex combination, still at most 0. Therefore, VHist ≤ 0. But by the fact that there is the baseline where the agent just ignores misreports and still obtains 0, we know that VHist ≥ 0 Therefore, combining the baseline strategy with the examples we found, we obtain the exact value VHist = 0. C.7
Conclusion of VMarkov and VHist Comparison
Thus, the history-dependent observation adversary is strictly more damaging VHist = 0 <
1 = VMarkov . 4
30
D
Algorithm Details
A high-level overview of our algorithm is provided below in Algorithm 1 and Algorithm 2. Γ In Algorithms 1 and 2, we write VLB and VUΥB for the lower- and upper-bound value functions denoted above by VLB and VU B . The superscripts emphasize that the lower bound is represented by a set Γ of α-vectors, whereas the upper bound is constructed from a set Υ of belief–value points. Thus, Γ VLB and VUΥB refer to the same bound functions as VLB and VU B , with their finite representations made explicit.
Algorithm 1 Compute ϵ-equilibrium for history-dependent SA-MDP Require: SA-MDP M = (S, A, R, p, γ, B), initial belief binit ∈ ∆(S), tolerance ϵ > 0, (optional) horizon H 1: /* Make the model stationary if finite-horizon */ 2: if H is specified then 3: S ← S ∪ {t} 4: for s ∈ S, a ∈ A do 5: if t ≥ H then 6: R(s, a) ← 0 ∀s ∈ S, a ∈ A 7: p(s|s, a) ← 1 8: p(s′ |s, a) ← 0, ∀s′ ̸= s 9: end if 10: end for{add time t to state; add absorbing terminal dynamics after t = H} 11: end if 12: /* Reduce SA-MDP to a constrained zero-sum OS-POSG */ √ b ← PARALLELIZE T O OSPOSG(M ) {dummy states/actions; γ 13: G b = γ; attacker action encodes reported observation} b ← I MPOSE S TATE D EPENDENT C ONSTRAINTS(G, b B) {set L1 (s) ← {⊥1 } and L2 (s) ← 14: G B(s) on true states;set L1 (s̄) ← Av and L2 (s̄) ← {⊥2 } on dummy states} b using HSVI (Horák et al.) */ 15: /* Solve G Γ Υ b binit , ϵ) 16: (VLB , VU B , Γ, Υ) ← HSVI(G, 17: /* Strategy extraction (online policies) */ b Γ, binit ) 18: σ b1 ← C ONTINUAL R ESOLVING(G, b V Υ , binit ) 19: σ b2 ← U PPER B OUND S TAGE P OLICY(G, UB 20: /* Map back to SA-MDP by collapsing sub-steps */ 21: (π, ν) ← C OLLAPSE D UMMY S TEPS(b σ1 , σ b2 ) {drop dummy turns; attacker action ≡ perturbed observation} Γ 22: return (π, ν, VLB (binit ), VUΥB (binit ))
31
Algorithm 2 HSVI for constrained zero-sum OS-POSGs, blue indicates change relative to Horák et al. [2023] Require: Constrained OS-POSG G = (S, A1 , A2 , O, T, R, γ, L1 , L2 ), initial belief binit , tolerance ϵ > 0, neighborhood parameter D Γ 1: Initialize VLB and VUΥB (lower/upper bounds) 2: while E XCESS(binit , 0) > 0 do 3: E XPLORE(binit , 0) 4: end while Γ 5: return (VLB , VUΥB , Γ, Υ) 6: procedure E XPLORE(bt , t) Γ 7: (π1LB , π2LB ) ← S TAGE G AME E QUILIBRIUM (bt , VLB ) {π1LB ∈ ∆(L1 (h1 )); π2LB (· | s) ∈ ∆(L2 (s)) for s ∈ S(h1 )} 8: (π1U B , π2U B ) ← S TAGE G AME E QUILIBRIUM (bt , VUΥB ) Γ 9: P OINT BASED U PDATE(bt , VLB , VUΥB ) ⋆ ⋆ 10: (a1 , o ) ← F ORWARD E XPLORE H EURISTIC(bt , t, π1U B , π2LB ) ⋆ ⋆ LB ⋆ 11: if Prbt ,π U B ,π LB [a⋆ 1 , o ] · E XCESS (τ (bt , a1 , π2 , o ), t+1) > 0 then 1 2 12: E XPLORE(τ (bt , a⋆1 , π2LB , o⋆ ), t+1) 13: end if Γ 14: P OINT BASED U PDATE(bt , VLB , VUΥB ) 15: end procedure
We use a linear programming routine to solve for optimal strategies and values at each sub-game node. The code is implemented in C++ with a Python interface and uses linear programming to solve the stage-game for HSVI and the Markovian equilibrium strategies. We use CPLEX with an educational license to solve linear programming routines. [IBM, 2024] Several implementation-specific modifications are made to our HSVI algorithm to improve computational efficiency. We cache commonly explored state-actions pairs. We also first group histories that lead to the same sets of observations at time t and then subsequently split information sets that overlap only due to the presence of a shared state in the feasibility set of the adversary into separate information sets by duplicating the state in our game tree. This enables solving many smaller convex problems versus solving fewer larger convex problems per stage and is equivalent to retaining separate extensive form (history-dependent) information sets associated with the game. However, computationally, this reduces the number of information sets that we need to keep track of and means that we only “recover the information sets as needed” at each stage. Our performance is illustrated by Figure 6 and Table 1. In Figure 6, we observe roughly linear scaling in number of states and log-linear scaling in the depth of the game. Min-max range are provided with shaded region, while bars are provided 1 std out. Normality of runs cannot necessarily be assumed, especially with only 5 seeds. Runs were declared to have converged when the excess-gap fell below an epsilon of 0.01. SA-MDP was assumed to have |A| = 4, which was kept constant across tree-depth. An actual value of γ = .99 was used to approximate the γ ∼ 1 case. The adversary’s proximity set allows the adversary to perturb any current state to any adjacent state, with first and last states being adjacent. (So, at state 1, the adversary could perturb observations to {4,1,2}, etc.)
32
Figure 6: HSVI solve time versus tree-depth.
33