acceptodds
Withdrawn from ICLR 2027

Certified Behavioral Maxmin: Semidefinite Certification Separates Abstraction Loss from Solver Loss in Imperfect-Recall Games

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

A player who forgets, facing an adversary who does not, is the normal case in deployed game solving: a poker abstraction merges information sets, and a team that cannot communicate knows less than its members do. Her best guaranteed payoff, the behavioral maxmin, is a polynomial optimization problem that is -hard even when the adversary has perfect recall, and first-order methods return a strategy without saying how far it is from that value. We add a certificate that runs once after the solver and changes nothing about it: a sum-of-squares feasibility program in which the adversary appears as a polynomial response map, so it contributes only linear variables and the semidefinite blocks carry only the player's variables. The degree of the response map defines a ladder: at degree zero the certificate bounds the minmax value, and raising the degree closes the behavioral duality gap. A posterior step makes the floating-point solution rigorous by evaluation alone, and that bound splits the deployment loss of the solver's point into an abstraction part and a solver part, which exploitability cannot distinguish: on Kuhn poker two abstractions, one with perfect recall and one without, lose the same against the full game, and the certificate assigns the first loss to the abstraction and the second to CFR stalling. On Leduc abstractions up to variables it bounds CFR's gap by in minutes where the global solver SCIP leaves to after an hour, and on three-player Kuhn teams it certifies a team-maxmin value and an interval for the value of coordination. One certificate thus separates two failures that the standard diagnostic reports as one number.

Primary area:
optimization
Keywords:
imperfect-recall games, polynomial optimization, sum-of-squares certificates, extensive-form games, abstraction

Reviews

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

This authors argue that in many real world games agents are treated asymmetrically in that a computed agent has imperfect recall as they use abstractions that merge information sets or that they cannot communicate with teammates (unlike their oponents). They provide a certificate (a convex sum-of-squares solver) that when run after any solve guarantees that the best possible value given the current abstraction is just an epsilon above the computed value. They do this by assuming the opponent is replaced by a polynomial “response map”.

From this they motivate an issue with exploitability where it combines abstraction error with error from the solver. They then show this can matter by considering two Kuhn-poker games where the exploitability are equivalent but in one the abstraction limits further improvement while in the other the solver has just not converged.

Critical strengths
  • The examples are simple, but clean and clear showing why these different sources matter
  • the theory is nice in terms of establishing a bound on both sources of error via the SOS
Critical weaknesses
  • The paper in its current form is very challenging to read, above and beyond the technical assumptions. New terms are regularly introduced without being defined for existing standard objects. Sentences are intensely “compressed” in meaning and large leaps of logic are left unexplained.
  • The only way I was able to understand what was going on at all was by using a LLM to read the paper which found the compressed material clear. To a human it is not and likely a result of using a LLM to polish the text plus the existing technical material.
  • It is not clear to me how the bound relates to prior work, if any. It is also not clear to me that in modern systems like ReBeL, where they use only extremely limited forms of action-abstraction if this critique raised in the paper about agents forgetting still applies.
  • Realistically, I think the paper has to be rewritten before it can be accepted. The ideas are good, but they are not easily understood in the current approach.
Questions for authors
  • What would you identify as the main innovation of the paper.
  • For something like ReBEL do the abstraction bounds identified still apply?
Reviewer_4eSBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies a setting where one player that has imperfect recall (due to an imperfect-recall abstraction being used) or a team plays against another player that has perfect recall. The paper presents ex post techniques (i.e., ones that operate after the equilibrium-finding algorithm has run) for determining exploitability (suboptimality) of the former side's strategy. Their technique separates the exploitability that stems from abstraction and the exploitability that stems from poor equilibrium finding in the abstraction.

Critical strengths
  • Novel approach using SoS.

  • Their technique separates the exploitability that stems from abstraction and the exploitability that stems from poor equilibrium finding in the abstraction.

  • The paper has pretty good coverage of related research.

  • With very significant rewriting, this could become a very good paper.

Critical weaknesses
  • Very poorly written and hard to follow. Seems that it may have been largely written by AI. The paper shows no understanding of what the audience would know versus what would need to be explained to the ICLR audience.

  • Assumes deep background in computational game solving, optimization, and SoS, so very few people at ICLR will be able to understand this. I am probably as close as anyone to the background knowledge, and I had a very hard time.

  • The paper is missing a relevant prior paper that also uses ex post bounds with abstraction and also works with the abstracted game only being solved approximately: "A Unified Framework for Extensive-Form Game Abstraction with Bounds", EC'18.

  • The authors knowledge of SOTA game solvers seem outdated. CFR, CFR+, and PRM+ (what the paper calls "the solvers of practice") are no longer SOTA. While PRM+ was SOTA three years ago, there are now faster ones.

Questions for authors

Seems that you assume (erroneously) that all game abstraction is imperfect-recall abstraction. Your points about abstraction apply to imperfect-recall abstraction only, correct?

How does the EC'18 paper mentioned above change your scoping and novelty claims?

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

The paper studies certain imperfect recall two-player games and approximate ways of solving them. The results describe some numerical results and observations.

Critical strengths

I can't think of any.

Critical weaknesses

I found this paper nearly impossible to read. I can't say for sure what it is even about.

It looks AI-generated, yet somehow I'd expect an AI to do better.

My most generous reading is that an AI found certain numerical approximations to certain two-player games. The paper does not contain any clear theorems (Theorem 1 has a one-line proof, and Theorem 2 is a technical proposition). The proofs in the appendix are messy and hard to parse. The experiments boil down to numerical simulations in a few examples. There's no systematic empirical evaluation or high-level claims that follow from it.

Questions for authors

I recommend clearly stating the problem that is being addressed in this paper. Then clearly state high-level contributions.

The manuscript needs a major revision and isn't ready for consumption by the machine learning community.

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

Related papers

Discussion (0)

Sign in to comment.