Game theory paper proves biased CFR feedback still converges — and beats random shuffling in poker AI

In imperfect-information games like poker, counterfactual regret minimization (CFR) is the standard algorithm for computing near-optimal strategies. But when a game has a large public-chance event — such as a turn card with many possible outcomes — evaluating every outcome at each iteration becomes computationally prohibitive. Practitioners often sample a subset, but that introduces bias. Guo and Ye's new paper, accepted for arXiv (2608.14761), tackles this head-on by showing that you can abandon unbiasedness entirely and still get deterministic convergence guarantees.

The key contribution is a 'target-transfer theorem' for uniform, nonnested additive public cuts. It decomposes full-cut exploitability into regret on the delivered feedback plus a 'public-debit term' that couples prefix coverage discrepancy with motion along the strategy path. This allows 'consecutively balanced schedules' to converge for regret matching (RM) and RM+ under fixed averaging weights. The authors also prove the discrepancy-path product is necessary, and they provide a component-resolved form that turns any execution trace into a numerical exploitability certificate. In experiments on two heads-up no-limit hold'em turn endgames, persistent ordered schedules significantly outperform fresh reshuffling at identical epochwise coverage, and partial coverage wins every shallow matched-budget comparison. A depth study finds a crossover between 32 and 64 full-cut outcome budgets, after which complete coverage dominates. The work reframes public-chance width and order as learning variables, giving a deterministic basis for designing and auditing persistent CFR schedules.