Correlated Chance Sampling for Monte Carlo Counterfactual Regret Minimization

Monte Carlo Counterfactual Regret Minimization (MCCFR) repeatedly allocates chance outcomes while its strategy evolves, yet standard sampling draws those outcomes independently on every visit. We introduce Correlated Chance Sampling MCCFR (CCS-MCCFR), a drop-in replacement that assigns each concrete chance node a persistent randomized Weyl stream and maps its phases through the node's chance distribution. Each fixed-index draw has the correct marginal law, while the first N draws consumed during N visits to one concrete node achieve deterministic local frequency error O(!log(N+1)/N), compared with the O(N-1/2) expected scale of i.i.d. frequencies. We further establish unbiasedness along fixed strategy trajectories, isolate adaptive phase selection through a conditional scalar bound, and show that a per-traversal reset variant retains the standard O(1/√T) External Sampling guarantee. In paired experiments, CCS-MCCFR reduces final exploitability by 19.05% to 34.01% across Kuhn poker and four Leduc poker configurations, with every paired-bootstrap confidence interval above zero, and by a significant 4.27% on Goofspiel-4. The gain survives to 3M Leduc node touches and combines with Linear CFR to reach the lowest measured exploitability. The sampler introduces no new hyperparameters and no measurable time overhead, so CCS-MCCFR turns a one-line change to the chance sampler into explicit local guarantees and large exploitability reductions across tabular poker.