acceptodds
Under review as a conference paper at ICLR 2027

Epsilon-Nash Equilibria in History-Dependent SA-MDPs

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.

Primary area:
reinforcement learning
Keywords:
robust reinforcement learning, state-adversarial MDPs, stochastic games, partially observable stochastic games, game theory, history-dependent policies, adversarial robustness

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dP5rOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies state-adversarial MDP (SA-MDP) as a game of observation-space attacks. It further shows that Markovian policies could be sub-optimal and shows non-existent of universal history-dependent equilibrium policies. They fiurther give algorithms to gert ϵ\epsilon approximate initial-state dependent equilibria.

Critical strengths
  1. Addresses an important problem in robust reinforcement learning where the adversary can condition its behavior on the entire interaction history.
  2. Motivates why history-dependent strategies may be necessary rather than simply an implementation choice.
  3. Proposes an elegant game-theoretic reduction
  4. The paper develops strategy-correspondence results and an approximate-equilibrium guarantee.
Critical weaknesses
  1. Validity of the game transformation. The proposed reduction from a history-dependent SA-MDP to a constrained zero-sum OS-POSG is central to the paper. The authors should clarify the exact correspondence between the feasible strategy spaces and demonstrate that expected returns and equilibrium properties are preserved under the transformation, including the treatment of dummy actions, observation histories, and terminal conditions.

  2. Equilibrium guarantees. The paper should more explicitly explain how the upper–lower value gap used by the HSVI-based solver implies an ϵ\epsilon-Nash equilibrium in the original game. In particular, the authors should state precisely which approximation errors are covered by the guarantee and clarify the assumptions required for termination.

  3. Empirical evaluation and scalability. The experiments demonstrate the method on a small, analytically tractable example, but do not sufficiently establish its practical scalability. Additional comparisons with appropriate baselines, together with runtime and memory measurements across larger horizons and state/action spaces, would strengthen the empirical claims.

  4. Novelty and computational benefit. The paper relies on existing constrained-game formulations and an HSVI-based solution approach. The authors should better distinguish the new theoretical contribution from existing robust-MDP and partially observable stochastic-game methods, and quantify the computational overhead introduced by the transformation.

Questions for authors

See Weaknesses

4 comments
AuthorsOpenReview ↗

Response to dP5r (Part 1 of 2)

We address the reviewer's 4 points below (over 2 parts to enable us to quote the reviewer's specific critiques). Let us know if anything remains unaddressed or unclear.

"Validity of the game transformation. The proposed reduction from a history-dependent SA-MDP to a constrained zero-sum OS-POSG is central to the paper. The authors should clarify the exact correspondence between the feasible strategy spaces and demonstrate that expected returns and equilibrium properties are preserved under the transformation":

We do this extensively in the appendix in the proof of Theorem 2.4, literally checking each component you raise over 3 lemmas comprehensively. This was originally in the body of the paper (and we would love the statements to be there), but there simply isn't enough room in ten pages to include this, the other results, the algorithm, and the empirics. However, we have added a proof sketch highlighting what we do in the appendix.

"Equilibrium guarantees. The paper should more explicitly explain how the upper–lower value gap used by the HSVI-based solver implies an ϵϵ-Nash equilibrium in the original game...":

This comes directly from the HSVI properties. For the policies, the agent (who aims to maximize a lower-bound for the value function for an arbitrary adversary strategy) secures at least LL and the upper-bound adversary (who aims to minimize an upper-bound for the value function UU) ensures the value of the agent's response is at most UU. Thus, either player’s unilateral gain from altering strategies is at most U−L≤ϵU−L\leq \epsilon. This is the exact definition of an epsilon-NE. The strategy correspondence transfers this to the original game. The result assumes strategy feasibility is preserved, valid exact backups, bounded rewards, discount factor λ<1\lambda < 1, and 0<D<(1−λ)ϵ2δ0<D<\frac{(1−\lambda)\epsilon}{2\delta} when δ=U0−L02>0\delta=\frac{U_0−L_0}{2} > 0.

"Empirical evaluation and scalability. The experiments demonstrate the method on a small, analytically tractable example, but do not sufficiently establish its practical scalability. Additional comparisons with appropriate baselines, together with runtime and memory measurements across larger horizons and state/action spaces, would strengthen the empirical claims":

We strongly disagree with the reviewer on this comment and are unsure what prompted this as most of the requested results are already shown in Section 3. We wonder whether they may have missed this material in their first review. If not, please clarify and correct their criticism, as it is clearly incorrect as written. We do not only look at analytic games.

Section 3.2 already reports a depth-10 random tree with roughly 3.1 million states and a peak of 8.6 GB, along with five-seed timing results at smaller depths (for context, many approximate solvers for very large games (poker, stratego, etc.) would solve typically ~2-3 layers down at each node, whereas we go ten down). Second, we also run over large real-world Atari benchmarks.

Our approach in the experimental section was as follows:

  1. The solved small example games test that our algorithm is valid and agrees with an analytic solution (establishing the comparison with "ground truth" the reviewer requested in another portion of their review.
  2. The random trees measure how much the solve time increases as the depth of the tree grows to see how scalable our method is when using an exact solver (our LP stage game solver.) This establishes both growth in memory and growth in time and allows us to estimate the time complexity to some extent (see the graphs in the appendix that also directly address the reviewer's critique.) This specifically checks the complexity when the tree is "dense" in information partitions: that is, there is little reduction between neighboring states when solving at each information partition instead of each possible history.
  3. Atari Freeway tells us first whether "history matters" in a large-scale, empirical and standard RL benchmark example to see when Markovian vs history-dependent strategies have very different values and which direction this gap goes. Also, what strategies practically look like given an initial hidden state.

We state these questions at the start of Section 3 to clarify this in the revised version.

AuthorsOpenReview ↗

Response to dP5r (Part 2 of 2)

"Novelty and computational benefit. The paper relies on existing constrained-game formulations and an HSVI-based solution approach. The authors should better distinguish the new theoretical contribution from existing robust-MDP and partially observable stochastic-game methods, and quantify the computational overhead introduced by the transformation.":

We think we are pretty clear and upfront about our contribution compared to the robust-MDP and the POSG literature. We solve history-dependent strategies for observation-space attack games and analyze them theoretically. Our constrained game formulation is new. Our algorithm uses HSVI as its solver to guarantee convergence and our HSVI for the constrained game formulation is also new. The extensive reduction, the analysis and the theory is completely new. We don't need to rely on HSVI, as any solver would work in principle inside our algorithm, including approximate solvers like deep reinforcement learning-based methods. However, HSVI provides exact convergence guarantees. Our implementation of HSVI and the code side involve several tricks to make the algorithm feasible at very large scales. The overhead of our reduction is negligible, so we don't include it. For context, for Atari Freeway depth 12 frameskip 30, the mapping + information state construction took 0.011 s. The overall solve time was around 0.502s in the latest run, so about 2% of the time was constructing information states and performing the reduction. For the depth-10 random tree, it took 6.043 s. The overall run time for the entire solver was 2,200 s or 36 m 40s. That means the overhead for info state construction + reduction here was approximately 0.275% of the total solve time.

Each original state has two copies and each move becomes two half-steps, with only one player makes a nontrivial choice at each half-step. The new part is the reduction and the constrained stage games and the fact we are able to map two completely different classes of games together and use this to help solve them.

Relying on HSVI for our internal solver, where we don't aim to contribute, is not "non-novel" or a novelty weakness. That would be like saying that because HSVI relies on LP and uses the simplex method, it is non-novel. Any paper that depends on any other method, that is, any paper that places itself in the existing literature (a strength, not a weakness), would be subject to the same critique. Maybe the reviewer meant something different.

Additionally, the setup for the standard HSVI for OS-POSGs does not involve the same set of constraints because it must include constraints on the adversary's ability to perturb observations, which requires novel checks in the HSVI algorithm.

AuthorsOpenReview ↗

New Rebuttal Version

We have uploaded a revised version of the paper that addresses some of the minor issues raised in the rebuttal that we said we would address. We believe this, along with our response, comprehensively addresses your concerns. Please let us know if we have addressed them.

If so, we would appreciate it if you would consider adjusting your score accordingly.

We appreciate your help in strengthening our paper!

I thank the authors for their response and in coorespondance to their answers I have increased the score by 1. I have no further questions.

Reviewer_eN8zOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers state-adversarial MDPs, in which an adversary can perturb an agent’s observation of the state under certain constraints (a proximity set of allowed observations for each state). The authors show that history dependence is a relevant concept to consider, in contrast to existing work that considers conditioning the policy only on the last observation. The game-theoretic implications of history dependence are studied, including showing how to apply a POMDP algorithm in this setting. While mainly a theoretical contribution, the results are showcased in a set of numerical experiments.

Critical strengths

The study of robust RL methods is an important area.

The mapping that allows POMDP algorithms to be used is valuable.

Critical weaknesses

The motivation to consider this specific version of robust RL is somewhat lacking.

The algorithmic contributions are limited (although the fact that existing algorithms can easily be applied could also be seen as a strength).

The experiments are hard to follow (quite some details about how Atari Freeway needed to be modified but the bigger picture was missing) and limited in scope.

The clarity of the manuscript needs improvement. Here are some specific issues:

  • The notion of “state-robust optimal” is not sufficiently defined (only in the appendix).
  • The example in Figure 1 could use some clarification, although also without being able to follow the example, I’m quite convinced that history-dependent policies need to be considered here.
  • In the introduction, the paper introduces oto^t as the observation that the agent receives, but then in Section 1.2 s~\tilde{s} is used.
  • Section 2.4 is poorly connected to the previous sections.
Questions for authors

What is the motivation behind the proximity constraint neighborhood of sts_t? The adversary is allowed to perturb the observation, but if I understood correctly, the agent has full knowledge of the proximity sets (i.e., function B(s)B(s)).

In definition 1.1, I was wondering why the reward function of player 1 depends on a2a_2?

The authors use a POMDP algorithm that tracks upper and lower bounds on the value of beliefs, but requires discounting. This is presented as an issue, but the original problem is also defined using a discounted objective. Can the authors clarify?

4 comments
AuthorsOpenReview ↗

Response to eN8z: Part 1/3

We address the reviewer's points below over the 3 part response. If anything is left unclear, please let us know.

"The motivation to consider this specific version of robust RL is somewhat lacking":

We could have considered alternative definitions of robustness as considered in the robust MDP literature, for example, robustness to reward perturbations or robustness to action perturbations (e.g., trembles), instead of robustness to observations. Those are the three primary forms of robustness to my knowledge. They all require different setups and results obviously need not translate between the different versions.

There are a few reasons why we focused on observation perturbations. First, the most trivial is our paper is based on a line of literature started by Zhang et al., 2020. They left this question open and unresolved in their study of SA-MDPs and limited their results to Markovian games. We already address this in our motivation section.

Second, of the three forms of robustness, observation-space robustness seems particularly salient in many practical real-world settings. Rewards are often constructed and it is not obvious how to go about modifying them, while strategies are typically determined by the agent and require either interfering with agents' control of a setting or their actual architecture. Observations, however, are just the input that an agent takes when deciding on a policy. These are very easy to manipulate. For example, simple corruption of input observations in robotics tasks is sufficient. Visual confusion is used for attacking VLMs and other vision models, like pixel-space attacks. For LLMs, when viewed as agents, prompt injection, and jailbreaking, arguably the standard attacks for LLMs can both be viewed as observation attacks, since they are attacks on input pixels (e.g., see https://www.anthropic.com/news/disrupting-AI-espionage).

For an RL-based system, manipulation of observations is a major salient concern. Imagine a self-driving car trained via RL, or using a related method like a World Model. A simple manipulation of its visual inputs and lack of robustness to these manipulations could lead the car to behave in dangerous ways. If this manipulation is deliberate, it is literally our setting. However, even if it is not and it is just some arbitrary visual manipulation (the sun shining in the camera of the car, for example and making some objects hard to see), our method gives the worst case guarantees on the behavior of the car and what is optimal to do, within a ball of constrained possibilities.

The ball is equally natural and appears even in works like Zhang et al., 2020. Without constraints on the adversary's ability to manipulate observations, the adversary can make the observation the same across all states and hence "useless". The optimal strategy for the agent is to then just ignore the observations entirely and behave in the way that maximizes their reward, given they are "blind". They never respond to changing observations. This is obviously "uninteresting" and is a result of the adversary not being sufficiently constrained. Empirically, when we made the radius of the ball too large in games like Atari (i.e., the adversary could manipulate pixels too freely), this was also exactly what we observed.

"The algorithmic contributions are limited (although the fact that existing algorithms can easily be applied could also be seen as a strength)":

Our major contribution is the reduction and its feasibility-preserving adaptation of the stage games, together with the resulting equilibrium guarantee, while the underlying HSVI search and its value-bound machinery build on Horak et al. This does not limit the algorithmic contribution of the solver. One way to view why this is the case is that, in principle, we could have replaced HSVI with any approximate solver for the OS-POSG, including self-play methods with deep RL. That is, in our biased opinion, a pretty powerful tool. HSVI was specifically chosen because of the guarantees on converging to an epsilon-NE. We aimed to make the division between our contributions and what we adopted from Horak et al. (2023) explicit. This is our major algorithmic contribution. The simplicity of it does not make it any less important, nor any less surprising that such a reduction even exists. (As a reminder the original Zhang et al 2020 question has remained open for 6 years on history-dependent strategies.)

On HSVI itself as we use it, our algorithmic contributions are indeed highly limited (highlighted in blue in the algorithm.) They consist of imposing extra constraints to standard HSVI for OS-POSGs because it must include constraints on the adversary's ability to perturb observations, which requires novel feasibility constraints in the HSVI algorithm.

We have added this clarification immediately after our algorithm pseudocode (now in the main body of the paper).

AuthorsOpenReview ↗

Response to eN8z: Part 2 / 3

"The experiments are hard to follow (quite some details about how Atari Freeway needed to be modified but the bigger picture was missing) and limited in scope."

It is not obvious what the reviewer's concern is about Atari for the big picture, and a more specific critique would be helpful. However, we add a response based on a response to another reviewer about additional detail we plan to provide in that section in the revision. Let us know if this addresses your concerns. The intent of the examples in the experiment section was the following:

  1. The solved small example games test that our algorithm is valid and agrees with an analytic solution (establishing the comparison with "ground truth" the reviewer requested in another portion of their review.
  2. The random trees measure how much the solve time increases as the depth of the tree grows to see how scalable our method is when using an exact solver (our Lp stage game solver.) This establishes both growth in memory and growth in time and allows us to estimate the time complexity to some extent (see the graphs in the appendix.) This specifically checks the complexity when the tree is "dense" in information partitions: that is, there is little reduction between neighboring states when solving at each information partition instead of each possible history.
  3. Atari Freeway tells us first whether "history matters" in a large-scale, empirical and standard RL benchmark example to see when Markovian vs history-dependent strategies have very different values and which direction this gap goes. Also, what strategies practically look like given an initial hidden state.

We have stated these questions at the start of Section 3 to clarify this in the revised version.

Specifically, on Freeway, we go into so much detail on the setup for the following reason. For the initial state hidden warm-up we describe, we introduce a brief justification, which is that if we used a fixed initial state, then agents could use observation-independent optimal strategies, since they know what state they started in and the transitions in Atari are deterministic, so they can track states from the initial state. Empirically, we found that even randomized actions via ``sticky-actions'' did not solve this problem, necessitating also the introduction of a random initial state that allows for two mutually-confusable initial states that the agent is not sure which they started from.

On Laidlaw et al., 2023, we want to preempt the following confusion (brought up even in other reviews), which is sometimes used as justification that our approach is infeasible/nonscalable, that we enumerate all the Atari states.

We do not fully enumerate the Atari states, which would be infeasible. We enumerate the reachable rollout at depth 12, with frame skip 30, and merge behaviorally equivalent states. We then study the information partitions of behaviorally equivalent states following Laidlaw et al. 2023. This is described in Section 3.2 in quite some detail. Secondly, while the random trees are meant primarily as the large-scale game test, Atari is also meant to show we can apply our method to "practical" large-scale real-world models. Atari Freeway illustrates history dependence in a standard benchmark setting commonly used for things like RL. For context/comparison, "typical" approximate solvers solve to depth 2-6 at most (see, for example, ReBeL, a leading method used for solving the POSG Poker https://arxiv.org/pdf/2007.13544, pg. 17, where they compare themselves, solving for 6 layers of values, with two other methods solving for depth 2 or 3), so depth 12 is substantial, especially given the exponential blow-up. We end up with about 5000 information partitions that we solve at after consolidation, which is not insignificant. Finally, the actual state space and observation space is very large for each stage, as each state consists of a (210, 160, 3) shape uint8 matrix (which has 266 possible values). This is the Atari screen at each frame. This yields $256^ {(2101603=100,800)} $ possible different frames (of which we have 12), or a 242,751-digit number of frames. This is clearly a "large" experiment.

"The notion of “state-robust optimal” is not sufficiently defined (only in the appendix)":

We thank the reviewer for pointing this out. We have added this definition of state-robust optimality immediately before the definition in the latest draft, taken from the appendix.

"The example in Figure 1 could use some clarification, although also without being able to follow the example, I’m quite convinced that history-dependent policies need to be considered here."

We now explicitly discuss what changes when s4s_4 is introduced and distinguish between the first and second panels. We explicitly discuss history-dependent policies briefly. We are also considering adding a single panel as a replacement that will show both cases in a single image.

AuthorsOpenReview ↗

Response to eN8z: Part 3 / 3

"In the introduction, the paper introduces oto^{t} as the observation that the agent receives, but then in Section 1.2 s s^{{~}} is used."

We now consistently use oto^t everywhere. We thank the reviewer for catching this. The original intent was s s^{{~}} would denote the perturbed state in the SA-MDP and the oto^t in the OS-POSG the observation, but we agree this distinction is artificial and we weren't super strict about keeping it in the original proofs.

"Section 2.4 is poorly connected to the previous sections":

We now lead in with an introductory sentence. The point of section 2.4 is that it is our final result: that we can demonstrate a valid reduction between the original SA-MDP to the zero-sum one-sided POSG. However, to do this, we need to impose some additional (pretty weak) requirements on what our game must satisfy, namely the L1(s)=L1(s′)L_1(s)=L_1(s') requirement.

In the OS-POSG, we simply track the set of states available for each player, not the action-observation history (maybe this is your confusion: the history for player 1 h1h_1 is the action-observation history over observables and actions, not states, actions, and rewards, again as is standard and should hopefully be self-evident from the fact that player 11 only sees observations.) Clearly, multiple different observational histories can be consistent with different possible states today because the adversary perturbs the observations meaning many possible states could have generated the same observation. Now, we require that all of those states must offer player 1 the exact same set of legal actions. Otherwise, the available set of actions available to choose (a "menu" for our agent), would itself reveal hidden information about which states we could or could not be in. In the extreme case that each state is associated with a unique action, then the presence of the action immediately tells the player what the true state is and renders the observation pointless. We now emphasize this in the latest revision.

"What is the motivation behind the proximity constraint neighborhood of s&#95;{t}? The adversary is allowed to perturb the observation, but if I understood correctly, the agent has full knowledge of the proximity sets (i.e., function B(s)B(s))."

BB is indeed assumed known by the agent (who has full knowledge about the game). At true state ss the adversary must choose a report in B(s). The agent knows this constraint and sees the chosen report, but does not observe ss directly. For bounded observation corruption, the interpretation of BB is that it is a neighborhood of possible manipulations of the state, which captures which observations the attacker can physically induce the agent to see. For example, in Atari, B(s)B(s) concretely tells us for each frame of the game how much we can alter the color of given pixels and how many pixels we can alter. The reason for including BB is an unconstrained adversary can trivially force the agent to a worst case outcome where they ignore their observations entirely and just work off their prior knowledge about the game structure. This is relatively "uninteresting" as the player's strategies never vary or depend on observations.

"In definition 1.1, I was wondering why the reward function of player 1 depends on a&#95;{2}?"

The reward function we use in the definition R(s,a1,a2)R(s,a_1,a_2) is for the general game as defined in the original Horak et al 2023 paper. (An arbitrary OS-POSG). We keep this to ensure consistency with their definition. In general, for any game, the reward will depend on both player's actions. In our setup, you are correct that a2a_2 can only affect RR by changing a1a_1.

We note this explicitly in the revised version after the definition and add a parenthetical citation in the definition header to make clear this definition is drawn from Horak et al., 2023.

In our reduction, the reporting stage pays zero. The agent’s stage pays the appropriately rescaled original reward R(s,a₁), with player 2 forced to its dummy action.

"The authors use a POMDP algorithm that tracks upper and lower bounds on the value of beliefs, but requires discounting. This is presented as an issue, but the original problem is also defined using a discounted objective. Can the authors clarify?"

This is correct and our infinite-horizon theorem already assumes discounting. However, in some finite-horizon experiments we aim to approximate an undiscounted total reward (since this is standard in a finite-horizon game setting) using a solver that requires a discount factor strictly less than one. In general, the closer gamma is to 1, the longer convergence takes. This means we need to choose a γ≈1\gamma\approx 1 that is close enough to 1 to achieve some specified low-error bound (such as 10^{-6}) in our model, but also the minimal such gamma that achieves that error bound for the fewest iterations in solving. We discuss this on lns. 357-366 and 1344-1350 in the appendix.

AuthorsOpenReview ↗

New Rebuttal Version

We have uploaded a revised version of the paper that addresses some of the minor issues raised in the rebuttal that we said we would address. We believe this, along with our response, comprehensively addresses your concerns. Please let us know if we have addressed them.

If so, we would appreciate it if you would consider adjusting your score accordingly.

We appreciate your help in strengthening our paper!

Reviewer_hEfMOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the state-adversarial MDPs from the game theoretical perspective. The main contribution is that the authors show that the class of optimal history-dependent policies depends on the initial state distribution. Next, the authors provide the reduction from SA-MDPs to Zero-Sum One-Sided Partially Observable Stochastic Game of Horak et al. (2023) and derived an algorithm to compute the optimal history-dependent policy. Finally, the authors have shown that their algorithm is implementable on various environments.

Critical strengths

The main result on necessity of dependence of even history-dependent optimal policies on initial distribution is a good contribution since it gives some insights on the difficulty of the problem, although it is not surprising given a prior work of Zhang et al. (2020) on the Markovian case.

Critical weaknesses

The main weakness of the paper is writing, and, more precise, (a) lack of any sketches of proof in the main text, (b) lack of the description of the actual analyzed algorithm in the main text, and (c) notation issues: many parts of the notation is defined in the middle of the corresponding proofs. For example

  • Σ1\Sigma_1 and Σ2\Sigma_2 in Theorem 2.1 are defined in the middle of Appendix;
  • The definition of “state-robust optimality”, used in the formulation of Theorem 2.2, is defined only in the proof of Theorem 2.2;
  • The paper changes the notation for agent’s and adversary’s policies in different sections: in Section 1.2 it is (π,ν)(\pi, \nu), in Section 2.1 it is (σ,τ)(\sigma, \tau), and in Theorem 2.2 it is (σv,σa)(\sigma_v, \sigma_a).

The second weakness is the experimental section: it is unclear what is intended to be shown there. Also, as far as I understand, all these examples are finite-horizon, so they should admit a closed-form solution (since history-dependent policies become finite-dimensional object in that case) which was not done for random trees or Atari example.Without any comparison to the ground truth solution, it is impossible to understand if the algorithm actually converged to the optimal policy.

Additionally, given that the authors have performed a full enumeration of states in that Atari game, it is unclear why it should be considered as a large-scale experiment. Another clear baseline which is lacking from random tree comparisons is against optimal Markovian policy, and the gap between optimal Markovian and non-Markovian policies should be the best demonstration of the value of this paper. This comparison was done for the Atari experiment, which I appreciate, although indeed, as authors have remarked, since both adversary and the agent policy classes are now extended, it is unclear how to compare them. And, finally, the paper does not provide any infinite-horizon examples, where the question of parameterization of history-dependent policies become much more important.

Questions for authors
  • How do you parametrize the infinite-horizon history-dependent policies for your algorithm?
  • How many states Atari Freeway has after the full consolidation and enumeration?
  • What is non-standard in Lemma 2.1 which make it require a separate lemma? It seems to be a very standard result on equivalence between max-min solutions and Nash equilibrium (see, e.g. Osborne & Rubinstein, A Course in Game Theory (1994), Proposition 22.2);

Separate suggestions:

  • Definition 2.4 is very unclear, in particular the phrase “whenever two states s,s′s, s′ may occur at the same player-1 information history” makes it very hard to understand;
  • Is it possible to show a result on learning history-dependent agent policy while adversary is only Markovian?
  • Is it possible to provide some deep RL approximation of your algorithm, where the history-dependent policies are parameterized by RNNs?
  • It is extremely hard to understand what is going on in the examples in Section 2.2: Figure 1b is never cited but it seems that the text refers to it since it refers to the state s4s_4. It is not really clear what does mean “the adversary would focus its manipulations on”, “increase misreport”. I would prefer to have a more formal statement of what is going on in this example, and, additionally, draw uncertainty states BB on the figure themselves, as well as make it clear what actions a1a_1 and a2a_2 are doing. Section C.2 and C.3 are duplicates;
8 comments
AuthorsOpenReview ↗

Response to hEfM Part 1/4

We respond to the reviewer below over 4 parts. If anything is not fully addressed, please let us know.

"...although it is not surprising given a prior work of Zhang et al. (2020) on the Markovian case":

We respectfully but strongly disagree. The fact that this took 6 years to resolve despite Zhang et al continuing to work in this area, that Zhang et al 2020 leave as an open question, and that they have no strong opinion as to whether it is true or not suggests otherwise.

There seems to be a fundamental confusion here. Our best guess is that the reviewer has flipped the specificity of the Markovian and history-dependent case. Showing that something doesn't work in the specialized Markov-Markov case says nothing about the more general History-dependent - History-dependent case. Conceptually, the agent has become stronger, but so has the adversary. It is unclear "which" will dominate conceptually. It turns out the stronger agent "conceptually" is true, coincidentally agreeing with the Markov-Markov case, but a priori this is not at all obvious.

Markovian and history-dependent strategies, and their related games/equilibrium concepts, form one of the major modern divisions in game theory. Conceptually, we are moving from Markov games to extensive-form games. Both of these are major subfields of game theory with very different proof methods, algorithms, and theory. The fact that they connect at all in this case is quite surprising and means we can bring techniques from one field to another. In our (obviously biased) opinion, missing this greatly undersells the paper and misses its significance.

"(a) lack of any sketches of proof in the main text":

Many sketches were moved to the appendix due to the 9-page limit. They can be viewed there in the uploaded draft in the lead-in to each theorem. We have restored these to the main text. Where they were missing (e.g., Lemma 2.1), we added new proof sketches to the revised version.

"(b) lack of the description of the actual analyzed algorithm in the main text":

We respectfully don't fully agree. Section 2.5 already describes the algorithm at a high level, including the reduction method and the constrained stage game solver. However, to fully address the reviewer's concerns, we moved the algorithm pseudocode from the appendix into the main body in the revised version.

"{Σ}&#95;{1} and {Σ}&#95;{2} in Theorem 2.1 are defined in the middle of Appendix":

This claim is incorrect. In the submitted draft, these were actually defined in Lemma 2.1 (not Theorem 2.1) as "unrestricted full-history behavioral strategy spaces {Σ}&#95;{1} and {Σ}&#95;{2} for the agent and the adversary, respectively." However, we have removed any mention of these from Lemma 2.1 in the revised version.

"The definition of “state-robust optimality”, used in the formulation of Theorem 2.2, is defined only in the proof of Theorem 2.2;":

Thank you for catching this. We have copied this exact appendix definition into the main body of the paper before Theorem 2.2.

"The paper changes the notation for agent's and adversary's policies in different sections: in Section 1.2 it is (π,ν)(π,ν), in Section 2.1 it is (σ,τ)(σ,τ), and in Theorem 2.2 it is ({σ}&#95;{v},{σ}&#95;{a})."

Thank you for catching this. We corrected this in a prior revision of the paper post-submission and notation in the latest revised draft should be consistent. We now consistently use π1\pi_1, π2\pi_2. Similarly, we always use oo for observations. Any remaining differences (e.g., σ1\sigma_1 vs π1\pi_1 for strategies in SA-MDP vs OS-POSG) are intentional.

"The second weakness is the experimental section: it is unclear what is intended to be shown there.":

The intent of the examples in the experimental section was the following:

  1. The solved small example games test that our algorithm is valid and agrees with an analytic solution (establishing the comparison with "ground truth" the reviewer requested in another portion of their review.)
  2. The random trees measure how much the solve time increases as the depth of the tree grows to see how scalable our method is when using an exact solver (our Lp stage game solver.) This establishes both growth in memory and growth in time and allows us to estimate the time complexity to some extent (see the graphs in the appendix.)
  3. Atari freeway tells us first whether "history matters" in a large scale, empirical example to see when markovian vs. history dependent strategies have very different values and which direction this gap goes.

We state these questions at the start of Section 3 in the revised version.

AuthorsOpenReview ↗

Response to hEfM Part 2/4

"Also, as far as I understand, all these examples are finite-horizon, so they should admit a closed-form solution (since history-dependent policies become finite-dimensional object in that case) which was not done for random trees or Atari example.":

The finite games do admit a sequence-form linear program with perfect recall, which can (in theory) be solved directly with a Lp solver. That doesn't mean that these have analytic solutions. And, ultimately, what you would end up with is effectively what we already report, an epsilon-NE (that is, we do solve exactly via HSVI).

In general, this becomes incredibly computationally costly as the number of states blows up. It is exponential in the number of states, and doubly exponential in the depth of the tree (versus our exponential with low coefficient in the size of the tree.) This is clearly infeasible for even moderate size game trees. For context, for our random game tree of depth 10, our best estimate would be your method would involve a scaling in the depth of something like 2(1,400,000)2^(1,400,000) times the solve time at depth 1 (that is an integer with 421,442 digits when written out.) Delage et al. 2024 (https://pure.rug.nl/ws/portalfiles/portal/1121105202/s13235-023-00519-6.pdf)[https://pure.rug.nl/ws/portalfiles/portal/1121105202/s13235-023-00519-6.pdf] benchmarked your proposed sequence form against HSVI (on the Competitive Tiger game, a tiny game compared to Atari) to argue how unreasonable this approach is for zero-sum, one-sided, partially observable games. The sequential form Lp solver took 1 second at horizon 2, 14 minutes at horizon 4, and returned no result within 1 hour at horizon 5. Memory similarly would scale doubly-exponentially.

"Without any comparison to the ground truth solution, it is impossible to understand if the algorithm actually converged to the optimal policy.":

The paper already reports comparison with a hand-solved analytic solution on small games, verifying our solution against a ground-truth and valid bounds for the discounted solver. Our HSVI solver has theoretical guarantees that give it exact convergence to an epsilon-NE, if it converges. As mentioned later in the review, beyond the small games we already explore the sequential Lp solver is not feasible, meaning there is no alternative method to explore. There is no "ground-truth" in general so it is not obvious what else you would want us to compare against.

"Additionally, given that the authors have performed a full enumeration of states in that Atari game, it is unclear why it should be considered as a large-scale experiment":

We do not do a full enumeration of the Atari state...we enumerate the reachable rollout for depth 12, with frame skip 30, and merge behaviorally equivalent states. We then study the information partitions of behaviorally equivalent states following Laidlaw et al 2023. This is detailed in Section 3.2. The random trees are meant primarily as the large-scale game test. However, Atari is also meant to show we can apply our method to "practical" large-scale real-world models. Atari Freeway illustrates history dependence in a standard benchmark setting commonly used for things like RL. For context/comparison, "typical" approximate solvers solve to depth 2-6 at most (see, for example, ReBeL, a leading method used for solving the POSG Poker https://arxiv.org/pdf/2007.13544,where they compare themselves, solving for 6 layers of values, with two other methods solving for depth 2 or 3), so solving to depth 12 is substantial, especially given the exponential blow-up. We end up with about 5000 information partitions that we solve at after consolidation, which is not insignificant. Finally, the actual state space and observation space is very large for each stage, as each state consists of a (210, 160, 3) shape uint8 matrix. This is the pixels per frame. This yields $256^ {(100,800)} $ possible observations and states for each frame (of which we have 12), or a 242,751-digit number of states. This is clearly an absurd number of possible states and is clearly a large scale experiment. This also justifies why we use the Laidlaw et al., (2023) approach. Note that the number of information sets is several orders of magnitude higher than this. For example, the ~5000 information partitions for history-dependent strategies come from about 231 consolidated states after applying Laidlaw et al. (2023).

"Another clear baseline which is lacking from random tree comparisons is against optimal Markovian policy, and the gap between optimal Markovian and non-Markovian policies should be the best demonstration of the value of this paper":

The purpose of the random forest experiments is to measure the cost of solving the full-history game, not to compare Markovian vs. history-dependent strategies. A Markovian strategy on the same tree is used for Atari to show that history matters, which is where the Markovian vs. history-dependent strategies matters.

AuthorsOpenReview ↗

Response to hEfM Part 3/4

"This comparison was done for the Atari experiment, which I appreciate, although indeed, as authors have remarked, since both adversary and the agent policy classes are now extended, it is unclear how to compare them."

We don't agree with the concern. We consider history-dependent strategies for both agents and Markov strategies for both agents. That is the relevant comparison for "when history matters" as it compares the Markovian setting to the non-Markovian one and that is regardless of the setting. We agree that the impact of extending both is non-obvious. That is why we do this instead of the Markovian vs. History-dependent vs. both history dependent or both Markovian, where one strategy set being a subset of the other means analytically we know direction-wise what happens to the value.

"And, finally, the paper does not provide any infinite-horizon examples, where the question of parameterization of history-dependent policies become much more important":

Indeed, we focus on finite-horizon games. Our numerical examples use a finite reward horizon followed by a zero-reward absorbing tail. A continuing game with recurrent informative decisions would be a new empirical test. We can add something to the appendix saying we focus on finite-horizon games. It is not obvious how one would go about solving infinite-horizon games without some kind of approximate truncation that turns them into finite games (e.g. when their reward-to-go is less than epsilon) or repeated games, which are not relevant to our question of interest. We can note these as a future research direction.

"How do you parametrize the infinite-horizon history-dependent policies for your algorithm?":

Analytically? In general, you cannot. If you mean how do we play it, it would be as follows: For player 1, start with a lower-bound value function, a vector attaining the initial bound, choose its strategy to maximize this lower-bound and update its continuation value, Player 2 chooses a strategy that minimizes an upper bound on the value function at the current belief and updates that belief. You can then update these values iteratively. These updates can run over an unbounded history.

"How many states Atari Freeway has after the full consolidation and enumeration?":

We already include this information in Section 3.2 of our paper. We have 5242 info partitions and 231 consolidated latent states, following Laildaw et al. (2023).

"What is non-standard in Lemma 2.1 which make it require a separate lemma? It seems to be a very standard result on equivalence between max-min solutions and Nash equilibrium (see, e.g. Osborne & Rubinstein, A Course in Game Theory (1994), Proposition 22.2); ":

The cited theorem is for non-sequential games. The minimax-nash equilibrium correspondence is in general well-known and indeed we cite a stronger variant of it when we cite the von Neumann minimax theorem for the finite horizon case in our proof. However, before doing so we need to use Kuhn's equivalence principle to convert from behavioral strategies to mixed strategies for the entire game over the space of all outcomes. That is effectively most of the proof in lemma 2.1 for the finite horizon case, but the fact we need both results makes it nonstandard. We will include this as a quick sketch of the proof. We need to also establish this equilibrium even exists (both sets are nonempty), which the proposition does not do.

The infinite horizon case is considerably harder and we included for full generality (an earlier version of the paper focused just on finite horizon games.) This requires a more sophisticated argument involving a series of limiting saddlepoints and corresponding nash equilibria for a series of finite horizon games. This takes up most of the body of the lemma, as it requires showing things like sequential compactness holds in the space of games.

Comments on the paper

1 comment

As the discussion period is approaching its end, please take a moment to review the authors’ responses and share any remaining thoughts or updates to your assessment. Thanks for your thoughtful reviews and discussion!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.