acceptodds
Under review as a conference paper at ICLR 2027

Certifying Global Optimality of Stationary Points in Imperfect-Recall Games

Abstract

Single-player decision problems with imperfect recall model a player who may forget information she once had. They arise wherever a strategy must stay compact: the absent-minded driver, imperfect-recall abstractions of poker, and team games compressed into a single forgetful player. The ex-ante optimal behavior strategy of such a problem maximizes a polynomial over a product of simplices. Deciding optimality is -complete, near-optimality is NP-hard, and the degree of the polynomial grows with the number of visits to an information set. Practice therefore relies on first-order methods: regret matching and its predictive-plus variant reach stationary points at scale. Such a point comes with no guarantee about its distance from the global optimum. We add a certificate layer that runs after the solver. A support-pruned sum-of-squares feasibility program at level bounds how far any strategy can beat the reported value. A posterior step turns the floating-point solution into a bound re-verified in exact and interval arithmetic, and the same certificate decomposes the residual gap across information sets. On instances regenerated from the generators of the reference benchmark, the layer certifies the PRM stationary point as globally optimal within relative tolerance on , or . The verdict is invariant across seed groups and of first-order methods. The global solver SCIP corroborates it to the same tolerance on all ; on one instance SCIP reaches that tolerance only at its one-hour limit, where the layer needs seconds. Support pruning is lossless at level one and wherever strict complementarity holds. The one certified loss is an interior cubic whose gap narrows one level up. On these instances, the stationary points of the standard solvers are almost always global optima, and a sum-of-squares certificate makes that fact checkable in seconds and provable in exact arithmetic in minutes.

Primary area:
optimization
Keywords:
imperfect-recall games, sum-of-squares, global optimality certificates, decision making

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

If I've got it right, the paper does the following. Imperfect-recall games give rise to optimization problems in which you'd ideally like a global optimum, but they're hard to find. In practice, solvers can find local optima (subject to some caveats about CLS-hardness in some versions of the problems). Given a local optimum, you might like to believe that in practice it's actually global, or failing that, approximately global. A "certificate layer" is a piece of software that can (sometimes) verify that a local optimum is global. The paper does some experiments with some of these optimisation problems, and gets some encouraging results that you can often find (and verify) a global optimum in practice.

Critical strengths

It's starting-point is an interesting challenge.

Critical weaknesses

The quality of the writing is inadequate.

I got about one-third of the way through page 2 before giving up. I am listing some complaints to prove that I tried to read the paper, and justify my claim that the paper is unacceptable.

The abstract is hard to read. I did OK with the first 10 lines since I have some familiarity with the work being referred to, then things went downhill. In the abstract, what does symbol u denote? The rest of the abstract contained various expressions I don't understand like "residual gap", "verdict", and "seed group".

Questions for authors

Line 043: "Through the bridge" -- ??

Page 2, problems with the text. Line 054 "We regenerate" - I don't know what it means to regenerate an instance. Does it mean to generate instances repeatedly, from some given probability distribution?

"fits the basis-size cap of Section 4" That's a weird way to refer to a later section of a paper, and I can't find where in Section 4 there's a basis-size cap being introduced. Separately, I don't know of any usage of the word "basis" that's consistent with a cap on a basis size. So I'm having to read jargon that I don't understand. The sentence on lines 056-057 makes no sense, doesn't parse. The following sentence refers to "Labels" - what labels are these? We're not in a setting of learning from labeled data.

062: Non-standard and misleading usage of "cross-validation" 069: What does Δ denote? I can guess, but I don't see why I should be required to guess.

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

This paper aims to numerically improve the speed at which sum-of-squares relaxations can bound the global optimality gap of local minima strategies in single-player imperfect-recall game. The authors propose reducing the support on which the optimal strategy lies and modify the structure of the SDP to improve the runtime by 1.49x the existing baselines.

Critical strengths

None

Critical weaknesses

Novelty: The work of Zheng et al. (2026), already established convergence for general single-player imperfect-recall games, and comparing a sum-of-squares upper bound with a candidates strategy immediately yields a global optimality gap, so the novelty of the work does not lie in creating the gap, but merely improving the computational efficiency of finding it. To this end, the method for finding this difference the authors propose assumes the SOS difference already exists, and their method does no come with a explicit convergence rate bound. Moreover, there is no runtime guarantee. The empirical speed up, at the moment, seems like the only advance of the work, and without the previously mentioned items, does not seem sufficiently important to the optimization community at ICLR.

Questions for authors

See the weaknesses section.

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

The paper studies how to certify the global optimality of a candidate behavioral strategy in single-player imperfect-recall games. It constructs sum-of-squares (SOS) upper bounds, reduces the certificate using the candidate's support, and accounts for numerical errors to obtain verifiable optimality gaps. It also studies when this reduction preserves exactness, gives examples where it loses exactness, and decomposes the certificate by information set.

Critical strengths
  1. The numerical verification is valuable: the paper goes beyond reporting an SDP solver's output and checks certificates using exact arithmetic and interval bounds.
  2. The analysis identifies both conditions for lossless pruning and a concrete example where pruning loses exactness. This helps explain the limitations of the proposed reduction.
  3. The comparison with the full certificate formulation provides evidence of computational savings: pruning reduces total certificate computation time by a factor of 1.49 on the evaluated pool.
Critical weaknesses
  1. The authors cite Zheng et al. (2026) as a closest reference to their work, but the distinction in Section 2 is misleading. The referenced paper's general single-player convergence result is not restricted to SOS-concave or SOS-monotone utilities; those subclasses receive stronger guarantees. Their Section 7.1 also compares SOS-certified optima with local-search outputs. Thus, covering general utilities and assessing local solutions do not, by themselves, distinguish this submission.
  2. Given a valid global upper bound UU, any feasible candidate μ^\hat\mu already has a certified gap bounded by U−u(μ^)U-u(\hat\mu). The contribution therefore needs to rest on the specific support reduction, certificate strengthening, numerical verification, and attribution. The comparison against the paper's own full formulation is useful, but does not establish the overall advantage over the existing hierarchy under comparable computational budgets and verification requirements.
  3. Pruning can weaken the bound and require higher relaxation levels. The paper acknowledges this theoretically, but the practical tradeoff between smaller SDPs and weaker certificates needs clearer evaluation. In particular, runtime comparisons should also consider the cost of reaching the same certified tolerance.
Questions for authors
  1. Could the authors clarify the distinction from the general single-player results of Zheng et al. (2026), and revise the discussion of that paper's scope?
  2. Could the authors compare the proposed approach with the existing SOS hierarchy on the same instances, reporting both runtime and certified gaps under comparable verification requirements?
  3. Could the authors also clarify when support pruning reduces the total cost of reaching a target tolerance, including cases that require a higher relaxation level?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.