acceptodds
Under review as a conference paper at ICLR 2027

Maximin-Sufficient Learning under Strategic Feedback in Zero-Sum Games with an Informed Opponent

Abstract

A defender can test a policy in resettable diagnostic episodes before deployment, but an informed opponent may choose, among its best responses, those that hide the unknown game model. Identifying the model may then be impossible, and it is stronger than needed: the defender only needs one policy that is -maximin for every model the data cannot rule out. We ask when this weaker target can be certified. Because best responses can tie, each diagnostic query induces a set of transcript laws, from which the opponent selects adaptively. For a learner that sees only the recorded transcripts, we show that certification is impossible whenever a group of models that no single policy serves within tolerance shares a common transcript law at every accessible query. For finite models, queries and transcripts, with deployment and inference sharing one tolerance and small enough , this joint obstruction is the only one: a confidence sequence that tests empirical transcript frequencies against each model's set of laws returns an -maximin policy with probability at least exactly when no such group exists. An acquisition score from minimax-regret duality (RDI) targets the deployment decision and affects only speed. On matrix, patrolling, search and poker designs, identifying the model takes to times as many episodes as reaching the policy certificate on the same runs. On the patrolling and search designs, RDI query selection is about three times faster than uniform querying, mostly through an allocation that could be fixed before any data; the exact RDI score is at most times faster than a cheaper pairwise score there, and six times faster on an interdiction design built so that pairwise evidence vanishes. The certificate is conditional on the candidate library: in a misspecification study whose library misses the true game, the method certified every run, and % of the runs had a gap above the tolerance.

Primary area:
learning theory
Keywords:
zero-sum games, game theory, security games, one-sided partially observable stochastic games, pure exploration, fixed-confidence identification, sample complexity lower bounds, minimax regret, robust decision-making, value of information, anytime-valid inference, confidence sequences

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_pgHROpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies a setting between a defender and an attacker. The defender seeks to maximize their total reward but does not apriori know the underlying (zero-sum) game, while the attacker knows the true game and best-responds to the defender's strategies. In this paper, the objective of the defender is to learn a maximin policy without necessarily having to identify the true underlying game. The main results give a characterization of when this is possible, and an adaptive algorotihm for learning such a maximin policy.

Critical strengths

At a high-level, I believe the setting and motivation for learning a maximin strategy even without necessarily identifying the underlying game is interesting.

Critical weaknesses

Ultimately, I found this paper incredibly difficult to read and parse. In particular, I believe the manuscript falls short in explaining the setting, the main results, their interpretation, and their signifcance.

For example, the first two paragraphs of section 3 ("Game family and objective", and "Diagnostic queries and strategic feedback") are difficult to follow and, in my reading, don't adequately introduce the problem setting in a clear, understandable way. Many terms are stated without any explanation or intuition, e.g., "robust radius", "A_\theta", "Tier I" and "Tier II", and even a precise definition of "transcript law".

The organization of Sections 4 and 5 were also hard to follow and make the main contributions very difficult to understand and also verify.

Questions for authors

My primary suggestion in a future revision is to substantially rewrite sections 3 and 4 in order to make the problem setting and contributions more clear and understandable.

2 comments

Thank you again for your detailed comments on the presentation, which guided our revision. As you suggested, we substantially rewrote Sections 3 and 4 and revised Section 5 accordingly. Section 3 now introduces the diagnostic protocol and a two-game running example before the general notation, and defines the robust radius, AθA_\theta and the transcript law explicitly. Section 4 opens with a roadmap, gives each theorem an informal statement and a proof sketch, and restates Theorem 4.4 in three parts (validity, characterization and an algorithm), while Section 5 now explains Tier I and Tier II where they are used. The experiments in Section 6 show why certifying a policy without identifying the model matters: on the same runs, identification requires up to 19.2 times as many episodes as certification. We would appreciate your view on whether the revised Sections 3 and 4 now present the setting and contributions clearly.

Thanks to the authors for their responses. I will maintain my score and encourage the authors to continue to revise the exposition in a future version.

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

Despite my best efforts, I do not understand this paper at all due to its extremely poor writing, so I can only provide a very rough summary of what I think the paper is about.

The basis setting is that there is a family of games, and only the attacker know the true game but not the defender. The defender can have ``diagnostic episodes'' by executing some policies to gather information. The attacker must best respond to such polices based on the true game but can choose arbitrary tie breakers to confuse the defender. The defender does not need to (and cannot) identify the true game, but the goal is to somehow learn a policy with a small gap compared to the value of the maximin policy.

However, as in what exactly the setup is, what information the defender can obtain, and what the actual results are in the paper, I just cannot understand.

Critical strengths

Not applicable until I understand the paper.

Critical weaknesses

As mentioned, the paper is extremely poorly written, to the extent that after reading a few pages, I still have no ideas what it is trying to address. In particular, the paper is full of incoherent sentences, cryptic terms, and undefined notations. I do not believe it is helpful for me to list all these issues I encountered, but I will still just keep the following notes that I made when reading the paper.

Undefine notations: ΠD,ΠA,Aθ,G†,θ⋆,Zq,Lθq,ν(Z)\Pi_D, \Pi_A, A_\theta, G^\dagger, \theta^\star, Z_q, L_\theta^{q,\nu}(Z) and many more.

Sentences that really do not make much sense (and frankly, show a strong sign of pure AI generations with little human effort):

"Tier I assumes a fixed finite pool; Tier II adds priced query columns."

"Under it the reported times remain upper bounds, but Theorem 4.3 must be re-checked"

"Oracle programs are in Appendix B"

(and many more)

Questions for authors

I have no questions whose answers could materially affect my assessment.

3 comments

Thank you again for your review and for the detailed list of undefined notation and unclear sentences, which directly informed the revision. Each symbol you listed (ΠD\Pi_D, ΠA\Pi_A, AθA_\theta, G†G^\dagger, θ⋆\theta^\star, Zq\mathcal Z_q, Lθq,ν(Z)\mathcal L_\theta^{q,\nu}(Z)) is now defined in Section 3, which also specifies what the defender observes in each episode, and the three sentences you quoted have been removed or rewritten. Section 3 further works through a two-game example that illustrates the central idea: at one query, the attacker's tie-breaking can make the two games indistinguishable, and when only that query is available, this precludes certification exactly when no single policy is acceptable in both. Theorems 4.3–4.4 extend this observation to groups of models: in the exact finite setting of Theorem 4.4, certification is impossible exactly when, for some group of models with no common acceptable policy, the attacker can choose one transcript law shared by all of them at every available query. We hope that the revised Sections 3 and 4 make the paper easier to assess, and we would be happy to answer any further questions.

I thank the authors for their response and the revision. I want to make it clear that the issues I pointed out were only a few examples (and I gave up taking notes after realizing how severe the writing issue is). I will keep my score for now and encourage the authors to fully revise the paper manually before submitting it to the next conference.

Thanks for your response. We understand that the issues you listed were examples, and the revision was not limited to them; we have rewritten Sections 3–5 throughout, introducing the setting through the diagnostic protocol and an example before the general notation, accompanying each theorem with an informal statement and a proof sketch, and moving detailed technical material to the appendix. If there are still particular parts of the revised version that remain unclear to you, we would be grateful if you could point us to them, and we will continue to improve the exposition. We appreciate your engagement during the discussion.

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

The paper studies learning a defender policy in a zero-sum game when one fixed but unknown model belongs to a known candidate set. An informed attacker best-responds during diagnostic episodes and may choose among tied responses to hide information about the model. The goal is to certify a policy that is within ε\varepsilon of the maximin value in every model still plausible, without necessarily identifying the true model. The paper gives conditions for certification, a statistical procedure, and a rule for selecting diagnostic queries.

Critical strengths
  1. The theoretical analysis characterizes when a near-maximin policy can be certified despite strategic choices among best responses, under the stated finite-setting assumptions.
  2. The experiments distinguish the savings from stopping before model identification from the benefits of query selection, with useful comparisons against fixed allocations and simpler selection rules.
Critical weaknesses
  1. The impossibility result is restricted to a learner that retains only the prescribed transcripts. If those transcripts omit the defender's executed actions, retaining those actions can change what is learnable: Appendix A.2 gives an example where one episode then identifies the model. This limits the practical scope of the result unless the restricted logging interface is justified.
  2. Exact RDI is substantially more expensive than the pairwise rule, with limited additional gains on the patrolling and search designs. Fixed query allocations also capture most of the improvement over uniform querying. The larger gain on the interdiction design relies on an instance constructed to defeat pairwise inference, leaving the broader practical benefit unclear.
Questions for authors
  1. What applications justify excluding the defender's executed actions or execution seed from its retained information? How does retaining this information change the learnability characterization?
  2. When does exact RDI reduce total cost over fixed allocations or the pairwise rule, accounting for both diagnostic episodes and computation?
  3. How does the proposed approach compare with solving a bounded diagnostic interaction as an augmented imperfect-information game?
2 comments

Thank you again for your careful review and for the three questions, which helped us clarify the scope of the results. We summarize below how our reply and the revised paper address them. Regarding retained information, Section 3 now states that anything the learner keeps from an episode, such as its executed actions, is part of the transcript (the full transcripts of the patrolling and search designs already record the executed tour or plan), and Appendix A.2 shows that retaining more information can remove an obstruction (Proposition A.1) but never create one. Regarding cost, exact RDI saves episodes over the pairwise rule on S5 and S6 but not on S4, and on S6 a static allocation performs equally well (Table 27). On S5, exact RDI lowers total cost relative to the pairwise rule only when an interaction costs at least 6 ms, or 119 ms with a cold cache (Section 6 and Appendix G.7). Regarding the augmented game, our reply gives a matching finite-budget formulation: solving it maximizes the success probability at a fixed budget, whereas our characterization determines when finite certification is possible and permits data-dependent stopping. We would be happy to provide further clarification on any of these points.

Thank you for the responses. I will maintain my score and agree with the other reviewers that the paper might benefit from a tighter exposition so that the immediate benefit is clear.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.