acceptodds
Withdrawn from ICLR 2027

Intransitivity Can Raise the Minimum Abstraction Size

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

Abstract

Large poker solvers group private hands into buckets before they solve. The number of buckets is a parameter set by experiment: coarse enough that the abstract game fits the solver, fine enough that the resulting strategy is not obviously exploitable. The theory of abstraction takes an abstraction as given. Lossless methods merge states that are interchangeable against every opponent, and lossy methods bound the exploitability of a coarsening already chosen. Neither answers how many buckets a game requires. The minimum also cannot be read off one equilibrium, which may distinguish hands it has no need to. We compute the exact minimum in one-card poker, a family small enough to enumerate. One player's strategy is a finite-state automaton reading the private card and then the public betting actions, so at each betting action a state is a bucket. When each post-card observation identifies one decision history, the fewest states attaining the equilibrium value equal the *joint width*, the fewest blocks of one partition of the deck that serves every decision the player faces. With one decision after the deal this is the *label-class width*; with several it can be larger, and the second player in four-card Kuhn poker needs four states although its two decisions need three and two. Sweeping the showdown relation exactly, we find a total order keeps width at most three on every deck from to cards, attained by a contiguous partition of card rank, with width three recurring with period ten. Reversing one comparison lifts width to on five cards. Over all seven-card isomorphism classes width reaches , one bucket per card, while three quarters of the classes need at most two. How many cards each card beats does not determine the width. Deck size alone does not set the bucket requirement: at seven cards the order needs two, the worst relation seven, others one.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
imperfect-information games, game abstraction, poker

Reviews

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

The paper tries to figure out the absolute minimum number of "buckets" (state abstractions) needed in small poker games to keep the exact equilibrium value. The authors map the strategy to a finite-state automaton and prove that the minimum number of states equals what they call the "joint width" of the deck. They run exact mathematical calculations on very small setups—up to 40 cards for totally ordered decks, and up to 7 cards for intransitive (rock-paper-scissors style) matchups. Their main finding is that ordered decks only ever need a few buckets, while intransitivity causes the required number of buckets to spike.

Critical strengths

1.Mathematical rigor: The authors made sure to avoid floating-point errors by using exact rational arithmetic for all their proofs and empirical checks. The formal link between automaton states and joint width seems logically sound.

2.Clear writing: Even though I am outside this exact subfield, I found the paper relatively easy to read. Figure 1 does a good job explaining the core pipeline.

Critical weaknesses

1.The setup is too small to be useful: The experiments are restricted to extreme "toy" games (one-card poker) with a maximum of 40 cards for simple ordered decks and just 7 cards for the intransitive ones. I am not convinced that the patterns observed here (like the period-10 recurrence on ordered decks) mean anything for real, large-scale imperfect-information games. It reads more like a discrete math puzzle than a machine learning paper suitable for ICLR.

2.No algorithmic contribution: The paper measures the minimum abstraction size but doesn't actually give us a practical algorithm to find or approximate it for games we actually care about solving. The authors even admit in Appendix D that their characterization "does not find" the abstraction. Because of this, the practical takeaway for the AI community feels very limited.

Questions for authors

1.I'm struggling to see the scalability here. How would your framework handle multi-round betting with chance nodes (like dealing a flop and turn in standard poker), where the decision trees are vastly deeper?

2.Since you mentioned in Appendix D that the identity doesn't give us a search algorithm, what is the actual use case of this theory for practitioners trying to build AI for large games?

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

This paper considers a toy-version of a poker problem: There are nn cards and, in their standard setting, each a lower card loses to a higher card. Given information about one card, the problem is whether to fold or call, possibly with some random probability. The question in the paper asks how many "buckets" of different probabilities are needed to achieve an optimal strategy. When considering a certain resource model, the paper gives the answer of two or three (depending on nn modulo 1010) for nn between 33 and 4040. The paper also considers a intransitive cards where each pair has an arbitrary win-loss relationship; quite naturally, intransitive cards require many more buckets. The paper proves their main computational by solving an LP to get the optimal game value, and then checking buckets of size 11, 22 and 33.

Critical strengths

I don't doubt the main result of the paper.

Critical weaknesses

The paper is clearly written by AI and basically unreadable.

As far as I understand, ICLR is a machine learning conference. Besides being written by AI, I'm not sure what the paper has to do with ML.

The following closely related work is not discussed: "Finding Optimal Abstract Strategies in Extensive-Form Games" by Johanson, Bard, Burch, and Bowling in 2012.

The model is different than the (main?) prior work in this area: The paper's state minimum is conditional on fixing the automaton transition skeleton before randomizing over action plans. This is materially different from the mixed-machine strategies of Černý, Bošanský, and An in 2020 where randomization over machines is permitted.

Questions for authors

Could you please write the paper yourself?

Why do you think this paper belongs at ICLR?

Could a more careful analysis of the LP give results for n≥40n \geq 40?

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

This paper investigate levels of abstraction when applying certain solving techniques in poker games. Technical results are provided on the number of buckets required in small games.

The results are clearly presented and explained well, but the result is specific to small poker variations where enumeration of state is possible, and further motivation or significance is not given. Experimental results validate the theoretical findings.

However, I don't think the paper has the necessary impact or significance for this conference.

Critical strengths

The paper presents sound technical results. An epxerimental validation of the theory is given.

Critical weaknesses

There is little attempt to explain the significance of the result or the relevance beyond small poker games.

Questions for authors

No further elaboration is required

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

Related papers

Discussion (0)

Sign in to comment.