PaperlayerView exact revision on arXiv

Source-linked AI summary

CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedules

Jiaxing Guo, Lei Ye

arXiv:2608.14761v1cs.GTcs.LG

TL;DR

Persistent partial evaluation in CFR covers each public outcome once per epoch, but evolving strategy profiles make its feedback history-coupled rather than conditionally unbiased. The paper develops a deterministic discrepancy–path transfer theory and finds that persistent order improves shallow HUNL performance, with complete coverage dominating beyond a 32–64 outcome-budget crossover.

  • Problem

    Persistent CFR schedules have exact epoch coverage but history-coupled feedback, leaving a gap between stochastic unbiased-sampling guarantees and persistent pathwise analysis.

  • Method

    The paper proves a discrepancy–path target-transfer theorem, convergence for consecutively balanced additive RM/RM+ schedules, necessity of the discrepancy–path product, and trace-level certification.

  • Results

    All 21 registered shallow width-by-horizon contrasts favor partial additive RM+, while complete coverage dominates beyond a crossover between 32 and 64 full-cut outcome budgets.

  • Takeaways & Limitations

    Public-chance width and order are learning variables, supporting deterministic design and auditing of persistent CFR schedules.

  • Takeaways & Limitations

    The guarantees apply to executions satisfying a declared additive-lane contract with fixed game, registry, width, update-order, origin, and output-clock declarations.

Abstract

from arXiv · show

At a finite public-chance cut, counterfactual regret minimization (CFR) must choose how many outcomes to evaluate before each regret update. Exact evaluation processes the full cut at one strategy profile; persistent partial evaluation processes a fixed without-replacement order across evolving profiles. The latter covers every outcome once per epoch, yet its feedback is generally conditionally biased because earlier batches influence the profiles seen by later batches. We establish a deterministic target-transfer theorem for uniform, nonnested additive public cuts. The theorem bounds full-cut exploitability by regret on the delivered feedback and a public-debit term that couples prefix coverage discrepancy with motion along the realized strategy path. Consecutively balanced schedules consequently converge for additive signed regret matching (RM) and RM+ under predetermined averaging weights, while a fixed RM+ construction proves that the discrepancy--path product is necessary in general. A component-resolved form of the theorem converts an execution trace into a numerical exploitability certificate. On two released heads-up no-limit hold'em turn endgames, persistent order improves substantially over fresh reshuffling despite identical epochwise coverage, and partial coverage wins every registered shallow matched-budget comparison. A depth study locates a crossover between 32 and 64 full-cut outcome budgets, after which complete coverage dominates. These results characterize public-chance width and order as learning variables and provide a deterministic basis for designing and auditing persistent CFR schedules.

1 INTRODUCTION

Persistent partial evaluation in CFR can produce history-coupled, conditionally biased feedback even when every public-chance outcome is covered once per epoch. The paper develops deterministic discrepancy–path guarantees and shows that persistent order and partial coverage can improve HUNL learning at matched budgets, before complete coverage dominates beyond a measured crossover.

  • Problem: Persistent without-replacement schedules cover every outcome once per epoch, but evolving strategy profiles make their feedback conditionally biased.Exact CFR evaluates the full cut at one profile, whereas persistent partial evaluation follows a fixed order across profiles.
  • Problem: The public debit is a signed temporal error caused by component motion between evaluation times, so reversing public order can change learning at identical counts and work.Exact epoch coverage cancels static selection coefficients, but not the motion-dependent debit.
  • Theory: The discrepancy–path transfer theorem converts prefix coverage imbalance and realized strategy motion into deterministic full-cut exploitability guarantees.The proof combines summation by parts, multiaffinity of finite-game counterfactual components, and an alternating-update bridge to exploitability.
  • Experiments: 1,964 mbb/g beats 2,278 for fresh epoch reshuffling and 5,042 for with-replacement singleton sampling at the same selected-outcome budget.On two independent endgames, all 21 registered shallow width-by-horizon contrasts favor partial additive RM+ in every seed; complete coverage dominates after a crossover between 32 and 64 full-cut outcome budgets.
  • Theory: Consecutively balanced schedules converge for additive RM and RM+, while a fixed RM+ construction establishes that the discrepancy–path product is necessary in general.The theory also yields a component-resolved, trace-level exploitability certificate.

2 PROBLEM SETUP AND PERSISTENT BALANCED FEEDBACK

The section formalizes alternating CFR with additive public lanes, persistent without-replacement batches, and centered local feedback. It defines prefix coverage discrepancy and realized strategy motion, then fixes the execution contract needed for deterministic target-transfer analysis.

  • Game, local feedback, and alternating CFR: Alternating CFR updates player zero from (x_t, y_t) and player one from the intermediate profile (x_{t+1}, y_t).RM accumulates centered feedback and normalizes its positive state, whereas RM+ clips updated coordinates at zero.
  • Additive public lanes: Each additive public lane registers N_ℓ labels, uses batch width B_ℓ dividing N_ℓ, and repeats a history-dependent permutation across epochs.The permutation is partitioned into equal batches before execution; during an event, the owner’s current profile remains fixed while the selected batch is processed.
  • Multiple lanes and owner clocks: Delivered-minus-target feedback decomposes into label coefficients whose sum is zero at every event, with selected labels weighted m_s−1 and unselected labels weighted −1.The decomposition combines lane streams with owner-local event clocks mapped onto global CFR rounds.
  • Coverage discrepancy and realized strategy path: Consecutively balanced streams bound prefix discrepancy by D_T ≤ max_s(m_s−1), including horizons inside an epoch.The pair (D_T, P_T) measures departure from uniform prefix coverage and the learner’s realized behavior motion while that imbalance persists.
  • Target output and execution contract: Execution declares the game, additive registries, widths, incidence maps, update order, evaluation origins, and output clock before running the schedule.Streams use immutable owner event profiles, and all incident components are combined before the corresponding learner update, fixing the full-cut target sequence.

3 DETERMINISTIC TARGET-GAME GUARANTEES

The section distinguishes exact epoch coverage from conditional unbiasedness and proves a deterministic target-transfer theorem for persistent partial feedback. Its discrepancy–path bound yields convergence results, a matching worst-case obstruction, and execution-specific exploitability certificates.

  • Coverage versus unbiasedness: Exact coverage and conditional unbiasedness are logically independent, so persistent and independently sampled schedules require different transfer arguments.A balanced epoch covers every outcome exactly once, whereas independent uniform batches satisfy conditional inclusion probabilities but may repeat labels unevenly.
  • Target transfer: Theorem 1 bounds full-cut exploitability by delivered regret plus endpoint coverage discrepancy, discrepancy–path interaction, and alternating-origin correction terms.The learner term is regret on received rows; the schedule terms account for incomplete coverage, evolving policies, and alternating evaluation origins.
  • Convergence: Consecutively balanced additive RM and RM+ converge under predetermined averaging weights when discrepancy grows sufficiently slowly relative to the iteration horizon.The corollary uses the bound D_T ≤ D⋆ := max_s(m_s − 1), while shifted Weyl streams provide an owner-aligned logarithmic-discrepancy example.
  • Sharpness: 11/64 is a worst-case lower bound on target exploitability for a fixed zero-state additive RM+ construction, showing the discrepancy–path product is intrinsically necessary.The construction has discrepancy and path terms of matching Θ(·) scale, delivered regret O(·), and residual target error Ω(D_T P_T) after fixed linear terms are removed.
  • Trace-level certification: Trace-resolved transfer replaces the structural schedule term with a recorded quotient debit at locally epoch-closed horizons.Shared-coefficient grouping exploits cancellation across public lanes before infinity-norm aggregation, enabling numerical execution-specific certificates.

T + 2C0wT DT + (2CXDT + Lalt)wT PT

The section establishes complete coverage as the unique zero-debit endpoint among fixed uniform widths, while exact balance preserves the convergence rate and makes the two outputs coincide at m = 1. Proper widths necessarily incur nonzero debit for some component arrays.

  • Rate preservation: Exact balance with wT /WT = O(1/T) retains the Corollary 1 rate, and the two outputs coincide at m = 1.The weighted summation-by-parts and path-coreset arguments apply to clock families ranging from uniform to delayed-linear.
  • Zero-debit boundary: Complete coverage B = N is the unique fixed uniform width whose delivered row equals the full-cut target row for every current component array and event.This is the universal zero-debit boundary for the order/width family.
  • Coefficient characterization: At complete coverage, m = 1 and all component coefficients in Equation 4 vanish; every proper width assigns unequal coefficients and can produce nonzero debit.An array supported on either the selected or unselected class witnesses nonzero debit for any proper width.

4 EXPERIMENTS

Experiments show that persistent ordering improves early learning despite identical epochwise coverage, while partial coverage outperforms complete coverage at shallow matched budgets before a 32–64-round crossover. Trace-resolved certificates numerically validate transfer bounds on dense full-cut targets.

  • Order study: At 3,072 selected outcomes per lane, persistent cycles reach 1,964 mbb/g versus 2,278 mbb/g for fresh reshuffling, improving by 314 mbb/g despite identical epochwise coverage.A read-only equal-coverage averaging control retains 84.7% of the IID–reshuffle contrast.
  • Width study: Through 32 exact-equivalent rounds, all 21 registered width-by-horizon comparisons favor partial RM+; at R = 1,536, B = 16 and B = 24 improve by 23.3% and 23.8%.Both widths win in all ten seeds, and Turn Subgame 1 again yields 21 positive contrasts with ten of ten seedwise wins.
  • Depth study: Every partial width crosses complete coverage between 32 and 64 rounds; at 512 rounds, complete coverage reaches 31.1 mbb/g versus 273, 233, and 171 mbb/g for B = 8, 16, 24.Partial arms decay with exponent approximately 0.6, while complete quadratic CFR+ decays with exponent approximately 1.5.
  • Matched CPU: In matched CPU tests, widths B ∈{16, 24} beat the exact CPU staircase in 69 of 70 same-seed comparisons each, while partial RM+ wins 20 of 21 width-by-CPU cells.Signed-CFR partial coverage wins all 21 cells by 8.4–27.2%; B = 8 is the single RM+ loss because of its 1.353× per-outcome overhead.
  • Trace-resolved audit: On 2,976 retained signed-CFR checkpoints, ledger identities and delivered-to-target inequalities close numerically; all 1,216 replay checkpoints lie below both the surrogate and direct bound.The surrogate is 2.3–5.2× the exploitability of the ordinary sparse transition-clock average, and its quotient debit is exactly zero at complete coverage.
  • Trace-resolved audit: For additive RM+, thirty trajectory-identical replays certify the weighted dense average at all 210 checkpoints, while epoch-start outputs are 1.04–1.28× the certified profiles and remain below the direct weighted bound.The construction uses unclamped sums and weighted target regret.

5 RELATED WORK

The paper distinguishes deterministic epoch balance from conditionally target-valid estimators in MCCFR and situates its analysis among discrepancy–variation methods and related regret algorithms. It also contrasts its composed framework with persistent correlated chance sampling and approaches addressing different feedback or aggregation settings.

  • 5 RELATED WORK: MCCFR obtains game-level guarantees from conditionally target-valid local estimators, while Proposition 1 establishes deterministic epoch balance as a distinct interface.The cited prior work includes Lanctot et al. (2009), Johanson et al. (2012), Gibson et al. (2012), and Farina et al. (2020).
  • 5 RELATED WORK: Persistent correlated chance-sampling MCCFR provides fixed-index marginals, fixed-trajectory unbiasedness, and nodewise count control at concrete chance nodes.The passage attributes these properties to Li et al. (2026) and contrasts them with the paper’s dense-target guarantee.
  • 5 RELATED WORK: The analysis combines summation by parts and discrepancy–variation bounds with centered counterfactual components, alternating origins, nonsmooth RM/RM+, and dense realization averaging.Related methods include GraB, approximate regret, Lazy-CFR, delayed feedback, and reshuffled minimax optimization, which address different error, aggregation, feedback, or recurrence settings.

6 SCOPE AND LIMITATIONS

The formal results cover a restricted class of finite two-player zero-sum perfect-recall games and specific regret recurrences. Empirical conclusions are limited by the narrow evaluation setting and incomplete RM+ certificate assembly.

  • Formal scope: The formal results apply to finite two-player zero-sum perfect-recall games with uniform, nonnested additive public lanes and declared owner clocks.They cover additive signed RM or RM+ under these assumptions.
  • Formal scope: Nested public cuts, endogenous concrete-node clocks, and adaptive width or order selection require additional transfer or continuation-validity arguments.Nested cuts require joint registries, while endogenous clocks require arguments tolerating sparse event clocks.
  • Empirical scope: The empirical study uses two HUNL turn endgames, with depth crossover measured on one input and kernel-CPU measurements from one unpinned host excluding setup and exploitability evaluation.These design choices constrain how broadly the empirical findings can be generalized.
  • Certificate audits: The signed-CFR audit assembles the full delivered-regret plus quotient-debit certificate, whereas the RM+ audit uses the direct weighted target-regret bound and measures the epoch-start output.The weighted quotient debit and numerical epoch-coreset constants for RM+ remain to be assembled.

7 CONCLUSION

The paper establishes deterministic guarantees for persistent partial public-chance evaluation by transferring delivered regret to full-cut exploitability through a discrepancy–path theorem. It also identifies a width tradeoff, with partial coverage helping early learning before complete coverage dominates, and provides reproducibility materials and certificates.

  • 7 CONCLUSION: The discrepancy–path theorem transfers delivered regret to full-cut exploitability, proves convergence for balanced additive RM and RM+, and yields a trace-level certificate with matching product-scale necessity.The theorem couples coverage imbalance to the evolving strategy path.
  • 7 CONCLUSION: HUNL experiments show partial coverage improves early learning before a measured crossover to complete coverage.The conclusion identifies public-chance width and order as practical learning variables.
  • 7 CONCLUSION: Narrow batches create earlier learner transitions, whereas complete batches remove public debit; depth and horizon determine which effect dominates.This decomposition provides ex ante conditions for convergent persistent schedules and an ex post certificate of their realized behavior.
  • 7 CONCLUSION: The supplement provides solvers, protocols, theorem verifiers, raw transcripts, per-value provenance, reproducibility records, supporting lemmas, complete proofs, and exact rational witnesses.Appendix D records campaign reproducibility, while Appendix B contains the supporting mathematical materials.

A EXTENDED RELATED WORK · B PROOF DETAILS

The related work separates unbiased sampled-feedback guarantees, persistent correlated sampling, discrepancy-aware delayed feedback, and approximate-regret analyses from this paper’s deterministic target-transfer approach. It also identifies why per-event error bounds fail in the stated regime and why signed temporal cancellation is used instead.

  • A EXTENDED RELATED WORK: The appendix compares closest theorem interfaces by research line and records the first failed reduction for each.Section 5 frames these comparisons around two decisive separations.
  • A EXTENDED RELATED WORK: Sampled counterfactual methods obtain high-probability regret from fresh or filtration-unbiased feedback across several sampling and variance-reduction approaches.The cited lines include outcome, external, and public chance sampling; generalized sampling; stochastic regret minimization; and vectorized policies.
  • A EXTENDED RELATED WORK: Persistent correlated chance sampling proves marginal and fixed-trajectory properties plus nodewise discrepancy bounds, while leaving global adaptive-process convergence open.The comparison states that neither this result nor the paper’s theorem contains the other.
  • A EXTENDED RELATED WORK: Prior work connects prefix discrepancy with stale-gradient, iterate, or integrand motion, while separate analyses study without-replacement reshuffling and delayed feedback.The cited research spans GraB, quasi–Monte Carlo, without-replacement optimization, Lazy-CFR, and delayed-feedback regret.
  • A EXTENDED RELATED WORK: Approximate-regret methods charge degradation by per-round error magnitude, but changing-payoff no-regret guarantees do not by themselves certify a fixed target.These limitations motivate distinguishing estimated-regret control from target transfer.
  • A EXTENDED RELATED WORK: Θ(1) per-event error magnitude makes conventional approximate-regret bounds uninformative in this regime, so the transfer exploits signed temporal cancellation.The passage contrasts this mechanism with charging each event’s error separately.

B.1 DETERMINISTIC BALANCED PUBLIC-CHANCE CFR … C.2 PROTOCOL AND RESOURCE ACCOUNTING

The paper develops deterministic target-transfer bounds for persistent public-chance CFR, separating coverage discrepancy from realized policy motion and extending the analysis to weighted outputs and component-resolved execution certificates. It also proves necessity results for discrepancy–path products and public-order effects, while reporting strong matched-budget performance for partial schedules.

  • B.1 DETERMINISTIC BALANCED PUBLIC-CHANCE CFR: Exact epoch coverage does not imply conditional unbiasedness, which holds uniformly only when every label has inclusion probability 1/m.Complete coverage and eventwise unbiasedness are distinct scheduling properties.
  • B.1 DETERMINISTIC BALANCED PUBLIC-CHANCE CFR: A fixed precommitted RM+ construction shows that no uniform target-transfer correction o(D_TP_T) can replace the discrepancy–path product.The witness has low normalized discrepancy with macrocycle closure, but the result does not cover signed RM.
  • B.1 DETERMINISTIC BALANCED PUBLIC-CHANCE CFR: The discrepancy–path transfer bounds target-feedback error by prefix coverage discrepancy multiplied by motion along the realized strategy path, without independence assumptions.The transfer is pathwise and applies to nonnested public cuts satisfying the stream incidence identity.
  • B.2 WEIGHTED TARGET TRANSFER AND ADDITIVE RM+: The weighted master theorem transfers arbitrary predetermined nondecreasing event weights through asynchronous streams while retaining delivered weighted regret and discrepancy–path terms.The structural constants are independent of the realized public order and behavior path.
  • T + 2C0wT DT + (2CXDT + Lalt)wT PT: When w_T/W_T = O(1/T), the weighted transfer retains the stated pointwise convergence rate for bounded discrepancy.The corresponding path contribution is controlled by the existing path lemma.
  • B.3 COMPONENT-RESOLVED TRACE CERTIFICATE: The component-resolved theorem converts locally epoch-closed execution traces into finite exploitability bounds using realized debit and path quantities.Closure is checked on local event clocks, while the denominator counts native alternating rounds.
  • B.3 COMPONENT-RESOLVED TRACE CERTIFICATE: Two balanced public streams with identical scalar metadata produce dense pre/pre NashConv values of 1/16 and 19/32, and epoch-start values of 0 and 7/16.The witness demonstrates that signed order–profile pairing is not determined by count, work, or scalar discrepancy/path metadata.
  • C.2 PROTOCOL AND RESOURCE ACCOUNTING: Widths B = 16 and B = 24 beat the exact CPU staircase in 69 of 70 same-seed comparisons each, while 20 of 21 width-by-CPU cells meet the eight-of-ten criterion.The sole loss is B = 8 at R = 1,152, where the measured 1.353× per-outcome premium enables a deeper exact run.

C.3 PUBLIC ORDER, WIDTH, AND HORIZON

Persistent cyclic public order outperforms IID and fresh reshuffling under matched budgets, while partial schedules beat exact coverage across the registered shallow grid. A depth ladder places the crossover between 32 and 64 rounds, after which complete coverage dominates.

  • Public order: 84.7% of the IID–reshuffle contrast is retained by a read-only equal-coverage observer.At B = 16, persistent cyclic feedback also beats IID and fresh reshuffling at all three horizons and wins all ten seedwise comparisons at R = 1,536.
  • Public order: Persistent cyclic order wins all 20 primary pairs against the three affine-cancelling alternatives.Retained component records attribute 87–97% of the debit gap between rotation and cyclic orders to order-induced changes in the adaptive component path.
  • Width: 21 of 21 partial-versus-exact paired intervals have positive lower endpoints in the held-out shallow grid.The checkpoints use 40 independent seed/schedule paths, and Turn Subgame 1 again yields 21 positive contrasts with ten of ten seedwise wins in every cell.
  • Width and horizon: Every partial width crosses complete coverage between rounds 32 and 64.At round 512, exact coverage reaches 31.1 mbb/g, whereas B = 8, 16, 24 reach 273, 233, and 171 mbb/g.

C.4 TRACE CERTIFICATES

Trace certificates validate regret identities and exploitability bounds across signed-CFR and RM+ replays. Complete coverage eliminates quotient debit, while certified averages and compressed epoch-start outputs remain controlled by the stated bounds.

  • Signed-CFR certificates: At 2,976 signed-CFR checkpoints, the target-regret assembly identity closes to relative error at most 10−9, with zero quotient debit at complete coverage.The certificate combines widths 16/24/48 and an independently collected width-8 bank; its median decreases at all 374 adjacent horizon steps.
  • Signed-CFR certificates: All 1,216 complete-epoch checkpoints lie below both the delivered-plus-debit surrogate and the direct target-regret bound.Per-width direct-bound ratios range from 2.65–2.95× at B = 8 to 4.8–5.2× at complete coverage.
  • Weighted RM+ certificate: The RM+ delivered-sum identity closes to 7.1 × 10−14, and the direct weighted target-regret bound covers the weighted dense average at all 210 checkpoints.Trajectory-identical replays cover widths 8/16/24, ten held-out seeds, and seven complete-epoch horizons.
  • Weighted RM+ certificate: The reported epoch-start output measures 1.04–1.28× the certified profile’s exploitability and remains below the direct weighted bound at every checkpoint.The retained ledger distinguishes the certified weighted dense average, direct target-regret bound, delivered-plus-debit surrogate, and epoch-start output.

D REPRODUCIBILITY

The reproducibility package preserves the solvers, verification materials, campaign records, artifacts, and tests, with provenance and fingerprints attached to principal comparisons. Quality evidence covers two released full-range HUNL turn inputs under a specified matched-CPU environment, with retained digests and restricted timing claims.

  • Reproducibility package: The package includes native solvers, theorem verifiers, campaign protocols, command manifests, raw transcripts, summary artifacts, and tests.Every figure and table links to retained per-value provenance.
  • Provenance: Principal trajectory comparisons carry learner, profile, input, and configuration fingerprints.These fingerprints accompany retained provenance for the reported comparisons.
  • Execution evidence: Quality evidence covers two released full-range HUNL turn inputs using matched-CPU measurements on a host with ten performance cores.Kernel-CPU accounting is used as described in the paper.
  • Execution evidence: Source, input, and artifact digests are retained, while timing statements are restricted to the recorded execution environment and charged interval.This bounds timing claims to the documented campaign conditions.
Loading 2608.14761v1…