- 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 approximate initial-state dependent equilibria.
Critical strengths
- Addresses an important problem in robust reinforcement learning where the adversary can condition its behavior on the entire interaction history.
- Motivates why history-dependent strategies may be necessary rather than simply an implementation choice.
- Proposes an elegant game-theoretic reduction
- The paper develops strategy-correspondence results and an approximate-equilibrium guarantee.
Critical weaknesses
-
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.
-
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. In particular, the authors should state precisely which approximation errors are covered by the guarantee and clarify the assumptions required for termination.
-
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.
-
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
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.
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.
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 L and the upper-bound adversary (who aims to minimize an upper-bound for the value function U) ensures the value of the agent's response is at most U. Thus, either player’s unilateral gain from altering strategies is at most U−L≤ϵ. 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, and 0<D<2δ(1−λ)ϵ when δ=2U0−L0>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:
We state these questions at the start of Section 3 to clarify this in the revised version.