acceptodds
Withdrawn from ICLR 2027

Dominated Actions Slow Down Counterfactual Regret Minimization

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

Abstract

Counterfactual regret minimization (CFR) is the leading framework for solving imperfect-information games and underlies superhuman poker AI. Its fastest variants, CFR+, predictive CFR+ (PCFR+) and the discounted PDCFR+, all start every information set from the uniform strategy, and that start carries a cost. At the first iteration the baseline against which regrets are measured is the unweighted mean of the counterfactual action values, so dominated actions pull it down and every non-dominated action receives the same additive offset in its first regret. The offset is uninformative, since pairwise differences are unchanged. Regret matching+ keeps it in the cumulative regret until later updates outweigh it, so those iterations are spent separating good actions whose order the offset does not change. We propose cold-start regret attenuation (CSRA), which multiplies the first non-zero regret of each information set by a constant c ∈ (0, 1] at the moment it appears and leaves every later update verbatim. The first strategy update is unchanged, the reduction costs one additive constant in the regret bound, and a single reduction preserves the convergence rate of any base algorithm whose analysis is sequence-agnostic. CSRA is the limiting case of PDCFR+, and truncating PDCFR+’s discount after its first iteration leaves its convergence within the variation across perturbed starts. Appending k dominated actions to every decision node of a controlled experiment multiplies the iterations PCFR+ needs at k = 32 by 5.40, pushes CFR+ past the budget, and changes those of CSRA by at most a factor of 1.27. On the standard benchmarks, evaluated with perturbation ensembles because the iteration at which a single run reaches a given exploitability is not reproducible on the games with large offsets, CSRA-PCFR+ matches PDCFR+ without a discount schedule. On the two games with the largest offsets, Battleship and Small Matrix, it reaches a given exploitability 2.43 to 9.38 times faster than PCFR+ and up to 3.12 times faster than PDCFR+, and it also accelerates PDCFR+ and APCFR+. A statistic computed from the first iteration alone, the common lower bound on the first regret, separates the games where the offset is large. The uniform start of CFR is not free, and CSRA removes its cost with a single multiplication at the first regret.

Primary area:
reinforcement learning
Keywords:
equilibrium, reinforcement learning, counterfactual regret minimization

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

This paper proposes cold-start regret attenuation (CSRA) to handle the case with dominated actions, which multiplies the first non-zero regret of each information set by a constant c ∈ (0, 1] at the moment it appears and leaves every later update verbatim. The first strategy update is unchanged, the reduction costs one additive constant in the regret bound, and a single reduction preserves the convergence rate of any base algorithm whose analysis is sequence-agnostic.

Critical strengths

This paper extends CFR to overcome the challenge of CFR in some games.

Critical weaknesses
  1. The novelty is limited, and this paper does not discuss the relation between CSRA and Weighted Averaging Schemes for CFR in Noam Brown and Tuomas Sandholm. Solving imperfect-information games via discounted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1829–1836, 2019a.
  • CSRA seems a special case of Weighted Averaging Schemes for CFR. The current setting in CSRA is equivalent to a non-decreasing weight sequence shown in Brown and Sandholm (2019a): c,c,…,c,1,1,1,…; i.e., if one assigns weight c to the zero regrets before non-zero term.
  1. The theory only preserves the base rate; it does not prove faster convergence.

  2. The results in figures and tables show that the proposed CSRA does not consistently outperform the best baselines; in most games it is neutral or worse.

  3. Presentation should be improved:

  • v(a), r_t(a) are undefined

  • What is the meaning of the bound in Proposition 1?

  • In addition, CSRA(c) is used in Proposition 1, but it has not been introduced before Proposition 1.

  • The theoretical condition should be stated and defined clearly, but "the perturbation protocol of Appendix C.4" in Lemma 2 made it confusing.

  • The size of the font in figures and tables is too small to read. The bold locations in Table 1 seem wrong.

Questions for authors

Because CSRA has nothing to remove at games whose equilibrium is close to uniform over the good actions. How to determine whether the equilibrium is close to uniform over the good actions or not before computing the equilibrium?

Reviewer_4DkjOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies Counterfactual Regret Minimization, specifically its first iteration. CFR iteratively computes regret, and the first iteration may increase the regret of some dominated actions, thereby influencing future iterations. The authors propose scaling this first iteration down, which should reduce this problem and allow faster convergence. The authors then provide robust evaluation across several standard benchmark domains.

Critical strengths

The evaluation uses several standard baselines and domains.

The resulting algorithm and the ideas behind it are simple (which I also see as a weakness).

Critical weaknesses

This entire paper can be summarized in a single paragraph, as the authors do in the introduction. The simplicity of the approach is often its strength, but here the whole algorithm boils down to multiplying the first-iteration regret by constants 0<c<10 < c < 1, which sounds more like a technical hack than an algorithm. Moreover, all the theory seems to follow from the CFR warm-start theory, like [1]. I don't see much novelty in the paper to make it sufficient for conferences such as ICLR.

Based on the results in standard benchmark games, the authors' approach is not much better than the baselines (which are already strong).

[1] Brown, N., & Sandholm, T. (2016). Strategy-Based Warm Starting for Regret Minimization in Games. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10056

Questions for authors
  1. Have you tried some specific weighting schemes beyond the first iteration, like some different variants of weighting than DCFR?
Reviewer_hDvUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Cold-Start Regret Attenuation (CSRA), a simple modification to Counterfactual Regret Minimization (CFR) algorithms that scales down the first non-zero regret vector at each information set. The motivation is that dominated actions can inflate the initial cumulative regrets of non-dominated actions, making it difficult for regret-matching-based algorithms to distinguish between good actions in subsequent iterations. The authors provide a theoretical analysis of this phenomenon and show that CSRA preserves the sublinear regret guarantees of the underlying algorithms. Experiments on various imperfect-information games demonstrate that CSRA can substantially accelerate convergence in certain settings, particularly when the initial regrets contain large common offsets.

Critical strengths

The proposed method is straightforward to implement and introduces negligible computational overhead. It can also be integrated into several existing CFR variants without modifying their subsequent update rules. And the paper provides controlled experiments by introducing additional dominated actions into existing games, illustrating how these actions can slow down CFR variants. The improvements on Small Matrix and Battleship are particularly notable. For the theoretical analysis, the paper build the connection between CSRA and the limiting behavior of PDCFR+ is also interesting and helps explain the role of early regret discounting.

Critical weaknesses
  1. The novalty might be limited. The central observation that dominated actions can produce large initial cumulative regrets and slow down CFR has already been discussed in Brown and Sandholm (2019) and Xu et al. (2024). In particular, Xu et al. (2024) explicitly investigate this issue and introduce PDCFR+ to mitigate it through regret discounting. The proposed CSRA can be viewed as a simplified form of early regret discounting, and the paper itself establishes a connection between CSRA and the limiting behavior of PDCFR+. Consequently, the conceptual and algorithmic novelty appears relatively limited.

  2. The main theoretical guarantee establishes that CSRA preserves the existing sublinear regret bound up to an additive term. However, it does not establish a better regret bound or a provably faster convergence rate compared with the underlying CFR algorithms. The analysis of strategy inertia is interesting, but its implications for the global exploitability convergence rate remain unclear.

  3. The authors claim that the additional Battleship experiment supports a prediction of substantial acceleration, but the reported median first-hit iterations are 510 for CSRA-PCFR+ and 440 for PCFR+, indicating that CSRA-PCFR+ is actually slower in this experiment.

Questions for authors
  1. Theorem 1 only shows that CSRA preserves the sublinear regret guarantees of the underlying algorithms, whereas the main claimed benefit is faster convergence in exploitability. Can the authors provide a finite-time regret or exploitability bound that explicitly captures the benefit of attenuating the initial regret, potentially in terms of the scaling factor cc and the initial regret offset JJ? In particular, it is unclear how the local strategy-inertia analysis in Proposition 1 translates into faster global convergence. Additionally, Proposition 3 claims sκ=Θ(J/δ)s_\kappa=\Theta(J/\delta) under D≤J/2D\leq J/2, but this assumption does not appear sufficient for arbitrary κ>1\kappa>1, since the stated lower bound can be non-positive. Could the authors clarify the conditions required for this result?

  2. Under what conditions is CSRA expected to outperform continuous regret discounting? In particular, how sensitive are the improvements to the scaling factor cc, the payoff scale, and the magnitude of the dominated-action gap relative to the differences among non-dominated actions? Could the authors also provide comparisons with recent hyperparameter-scheduling methods to better establish the advantages of attenuating only the first non-zero regret?

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

Related papers

Discussion (0)

Sign in to comment.