Regret stops living in a table: Haar-wavelet compression cuts game-solving memory 50,000-fold and outpaces Deep CFR
Synopsis
In imperfect-information games with ordered state spaces, cumulative regrets are no longer stored cell by cell for every information set; they are transformed into Haar wavelet coefficients and only the largest are kept. Tabular CFR+ previously grew memory linearly with the game tree under fine discretization, while Deep CFR traded memory for neural inference latency. On Deep-Stack Kuhn poker, growing the state count from one thousand to ten million raised memory only from 0.6 MB to 2.1 MB, a compression ratio above 99.9%; on Flop Hold'em, reaching comparable exploitability took about one-sixth the wall-clock time of Deep CFR.
Interpretation
When solving imperfect-information games, cumulative regrets can be compressed as a one-dimensional signal ordered along the state domain instead of keeping a dense array per information set. Standard tabular CFR+ treats each information set as an independent index, so fine discretization grows the information-set count combinatorially and exhausts 64 GB of memory at around one hundred thousand states in Deep-Stack Kuhn poker. As the state count grew from one thousand to ten million, a ten-thousand-fold increase, Haar-CFR peak memory rose only from 0.6 MB to 2.1 MB, a reduction of more than fifty thousand times against the tabular baseline at the largest size.
Compressed regrets still support CFR+ iterations, and strategy quality matches the uncompressed version. Compression introduces truncation error, which has to be shown not to break the no-regret guarantee of CFR. On Leduc Hold'em, keeping the top 5% of coefficients tracked the exact tabular baseline's exploitability curve, with a p-value of 0.812 for the comparison, judged a tie.
On large games such as Flop Hold'em with more than ten billion nodes, a CPU-based fast Haar transform reaches comparable strategy quality faster than neural approximation. Deep CFR approximates the regret surface with neural networks, and even batched inference is slowed by forward-pass and data-transfer latency. To reach 100 mbb/h exploitability, Haar-CFR took about 4 hours and Deep CFR about 26 hours, roughly one-sixth the wall-clock time.
In a market-making stress test, a single equilibrium strategy reflects both inventory and information risk. The Avellaneda–Stoikov model skews quotes linearly with inventory only, and the Glosten–Milgrom model widens the spread with information asymmetry only; the two previously sat in separate computational frameworks. On a 2000-level price grid with inventory from minus ten to plus ten and toxicity drawn uniformly from zero to one each episode, the learned quote surface shows a linear inventory skew at low toxicity and a no-trade plateau at high toxicity.
Perspective
The reported scope is the authors' evaluation on standard poker benchmarks and a self-built market-making simulation: Leduc Hold'em, Deep-Stack Kuhn poker, Flop Hold'em, and a market-making environment with a 2000-level price grid, inventory from minus ten to plus ten, and toxicity drawn uniformly from zero to one each episode. The intended readers are algorithm researchers and quantitative engineers concerned with memory and latency in large-scale game solving. The authors propose extending the framework to two-dimensional wavelets for multi-asset correlations, exploiting wavelet-coefficient independence for GPU parallelism, and applying spectral regularization to other ordered game domains such as energy grid bidding and auctions.
The method's effectiveness is bounded by the sparsity of the equilibrium strategy: in the ablation, lowering the coefficient ratio to 0.001 left exploitability stuck at about 250 mbb/h, which the authors attribute to too few coefficients to represent strategic discontinuities. The authors also note the sparsity assumption may fail in games with highly oscillatory, high-entropy, or fractal mixed strategies, where the required coefficient count grows linearly with state count and behavior reverts to standard tabular CFR. The financial findings come from a simulated environment, and the statistical comparison rests on 100 episodes.