Single Deep CFR and DREAM

Main results. (a) SD-CFR plays the average exactly (Steinberger, Theorem 2). Suppose each stored network $\hat D^t$the value network of iteration $t$, trained to predict the advantage $D^t(I,a)$, the linear regret at $I$ divided by the opponent's total reach (Step 2); regret matching on it gives $\sigma^{t+1}$ reproduces its iteration's advantages exactly. Then drawing $t$ with probability proportional to $t$, once at the start of a game, and playing regret matching on $\hat D^t$ to the end plays $\bar\sigma^T$ at every information set; computing $\bar\sigma^T(I)$ explicitly from the stored networks gives the same strategy, and no opponent can tell from play which is used. Theorem 1 is the contrast: Deep CFR's buffer of sampled strategies, and so even a perfect network fit to it, is not guaranteed to represent $\bar\sigma^T$ when the buffer is finite or each iteration runs finitely many traversalswhy: an information set reached with probability below 1 can be missed by every traversal of an iteration, and then its strategy never enters the buffer (Step 4). (b) DREAM's average regret falls like $1/\sqrt T$ (Steinberger et al., appendix). The bound says how fast the average regret of CFR falls when each traversal follows one sampled path, and how much the sampling adds to the tabular rate. The learning player picks a uniformly random action with probability $\varepsilon$the exploration probability, in $(0,1]$; it keeps the importance weights bounded (Step 6). Let $\mathcal I_i$ be $i$'s information sets, $|A_i|$ the most actions at any of them, $d_i$ the most decisions $i$ makes on one path through the game, and $R^T_i$$\max_{\sigma'}\frac1T\sum_{t\le T}\big(u_i(\sigma',\sigma^t_{-i})-u_i(\sigma^t)\big)$: how much better the best fixed strategy would have done, per iteration $i$'s average regret after $T$ iterations. For every $p\in(0,1)$, with probability $1-p$,$$\begin{aligned}R^T_i\le\frac{\Delta}{\sqrt T}\Big(&\underbrace{|\mathcal I_i|\sqrt{|A_i|}}_{\text{tabular CFR}}\\&+\underbrace{2\Big(\frac{|A_i|}{\varepsilon}\Big)^{d_i}\sqrt{2\log\tfrac1p}}_{\text{sampling}}\Big).\end{aligned}$$The exploitability of $\bar\sigma^T$ is at most $R^T_1+R^T_2$, so the average strategy converges to a Nash equilibrium. Networks that fit their training data only approximately add a constant to the average regret, proportional to the largest gap between a network's training error and that of the exact minimizer (Brown et al., 2019, Theorem 1).

CFR's guarantee is for the reach-weighted average, which equals a mixture of the iterates. Regret matching keeps the cumulative counterfactual regret at each information set growing at most like $\sqrt T$, and their sum over information sets bounds the player's overall regret (Zinkevich et al., 2008): the first term of the bound in (b). In a two-player zero-sum game the exploitability of the average is at most the sum of the two players' average regrets. The iterates $\sigma^t$ themselves usually do not converge in plain or linear CFR, so the average is what must be played. The weight $\pi^{\sigma^t}_i(I)$ in $\bar\sigma^T$ is $i$'s own probability of reaching $I$ under $\sigma^t$, and with it $\bar\sigma^T$ is the behavioral strategy (a distribution over actions at each information set) that matches, at every information set, the mixture that draws $t$ with probability proportional to $t$ and then plays $\sigma^t$ throughout. This is Kuhn's theoremin games of perfect recall, where players remember all their own past actions and observations, every mixture of strategies has a behavioral strategy that produces the same distribution over play against any opponent, and Step 3 uses it.

Deep CFR fits advantages from sampled regrets and learns the average with a second network. On each iteration Deep CFR runs a batch of external-sampling traversals for the learning player $i$: every action is explored at $i$'s decisions, and opponent and chance actions are sampled from $\sigma^t$ and the deal. The sampled instantaneous regrets go into a reservoir buffera fixed-size buffer filled by reservoir sampling, which keeps a uniform random sample of everything offered to it, and a value network is trained on all of them, each weighted by its iteration number, to predict the advantage$$D^T(I,a)=\frac{\sum_{t\le T}t\,r^t(I,a)}{\sum_{t\le T}t\,\pi^{\sigma^t}_{-i}(I)}.$$The divisor is the same for every action at $I$, so regret matching on $D$ gives the same strategy as on $R$, and it keeps the targets on one scale, since reach probabilities shrink geometrically with depth. Sampling the opponent from $\sigma^t$ makes each $I$ appear with frequency proportional to $\pi^{\sigma^t}_{-i}(I)$, the reach weight in $r^t$, so a least-squares fit to the sampled regrets, weighted by $t$, estimates $D^T$. When every predicted advantage is at most 0, Deep CFR plays the action with the largest advantage instead of the uniform strategy. Because the iterates are not the answer, Deep CFR also trains a second network $\hat S$Deep CFR's average-strategy network, trained to predict $\bar\sigma^T(I)$ from strategy vectors recorded during traversals on the opponent's strategy vectors $\sigma^t_{-i}(I)$, recorded at the opponent's information sets during the same traversals. The opponent plays on-policy there, so each of its information sets is recorded with frequency proportional to its own reach probability, the weight the average needs, and the loss is weighted by $t$.

SD-CFR plays the average exactly by choosing one network per game. Keep every $\hat D^t$. At the start of a game draw $t$ with probability $t/\sum_ss$ and play regret matching on $\hat D^t$ for the whole game. Given the draw, $i$ reaches $I$ with probability $\pi^{\sigma^t}_i(I)$ times a factor from the opponent and chance that does not depend on $t$, so Bayes' rule gives the posterior over iterations at $I$ and the resulting action probability,$$\begin{aligned}P(t\mid I)&=\frac{t\,\pi^{\sigma^t}_i(I)}{\sum_ss\,\pi^{\sigma^s}_i(I)},\\P(a\mid I)&=\sum_tP(t\mid I)\,\htmlData{gr=gn5}{\sigma^t}(I,a)\\&=\bar\sigma^T(I,a).\end{aligned}$$This is Theorem 2 for this trajectory sampling, and it costs one network query per decision, as Deep CFR does. When the whole distribution $\bar\sigma^T(I)$ is needed, as for computing exploitability, $\pi^{\sigma^t}_i(I)$ is the product of $\sigma^t$ along $i$'s earlier decisions on the path to $I$, which takes at most one forward pass of each stored network per such decision, a few seconds on a CPU in poker. Storage is small: the networks used for large poker games take under 400 KB each, and Deep CFR runs a few hundred iterations. Deep CFR and SD-CFR depend on the value networks in exactly the same way, so with all networks kept SD-CFR approximates linear CFR at least as well.

A learned average can be wrong even with perfect value networks. Theorem 1 points at the sampling. With $K$the number of traversals run per iteration traversals per iteration, an information set reached with probability $q\in(0,1)$ is missed by all of them with probability $(1-q)^K\gt0$, and that iteration's strategy there never enters the buffer. A finite buffer also cannot reproduce arbitrary ratios between iterations' reach probabilities, and a game with more information sets than buffer slots cannot have all of them stored. A perfect $\hat S$ fit to this buffer fits the wrong target. The errors are largest where reach is small, deep in the game, which is what Step 5 measures.

With shared value networks, SD-CFR is less exploitable than Deep CFR and beats it head to head. The two algorithms train value networks identically, so the experiments share them and isolate the averaging. In Leduc, with networks and buffers large for the game, the exploitability curves coincide for about 100 iterations and then separate, ending near 60 against 80 mA/g after about 5,000 iterations (five runs). In 5-Flop Hold'emFlop Hold'em with five community cards instead of three, a larger game that forces the networks to generalize, SD-CFR's mean winnings against Deep CFR built from the same networks are positive at every checkpoint (five runs; a few single runs dip just below zero): about 30 mbb/g at iteration 30 and roughly 7 to 10 mbb/g from iteration 60 on, each point from 3 million hands with a 95% interval between $\pm5.4$ and $\pm6.5$ mbb/g (10 mbb/g counts as a good margin between human players). The mean absolute difference between the two average strategies grows with the number of decisions made, from 0.012 at the first decision to 0.175 after five, as Step 4 predicts. Keeping only a reservoir sample of the networks hurts: exploitability plateaus or oscillates at every capacity tried up to 1,000 networks. In a Leduc variant with 12 ranks and up to 6 bets per round the two are closer. Curve values are approximate, read from the plots.

Without a simulator only one action can be sampled, and the plain estimate is too noisy. External sampling needs to return to $I$ and try every action, which a simulator allows and a played episode does not. Outcome samplinga Monte Carlo traversal that follows one sampled path through the game: one action at every decision, the learning player's included (Lanctot et al., 2009) samples one action at every decision. The learning player samples from$$\xi^t(I,a)=\frac{\htmlData{gr=g19f}{\varepsilon}}{|A(I)|}+(1-\varepsilon)\,\sigma^t(I,a)$$to keep exploring, and the opponent plays $\sigma^t$. Sampled values are then multiplied by the importance weight $1/\xi$ at each of $i$'s decisions on the path and are zero for every action not taken, so each regret estimate rests on one path and can be very large. Training data are weighted by $1/\pi^{\xi^t}_i(I)$ to undo the exploration. Run this way with SD-CFR's averaging (OS-SD-CFR), the method stalls: about 140 mbb/g in Leduc where the simulator-based version reaches about 50, and about 100 against about 15 in Flop Hold'em (approximate, read from the plots).

DREAM's learned baseline keeps the one-sample estimate unbiased and lowers its variance. A network $\hat Q$DREAM's baseline network: $\hat Q(h,a)$ predicts $i$'s expected payoff after taking $a$ at $h$ and then following $\sigma^t$ is trained by expected SARSAregression of $\hat Q(h,a)$ on the observed reward plus $\sum_{a'}\sigma^t(h',a')\,\hat Q(h',a')$ at the next history $h'$, an expectation over the next action under the current strategy on a circular buffera fixed-size buffer that overwrites its oldest entries of played transitions. At a history $h$ on the sampled path, where action $a'$ was taken and led to $h'$, every action $a$ gets the value estimate$$\begin{aligned}\tilde v(h,a)={}&\hat Q(h,a)\\&+\frac{\mathbb 1[a=a']}{\xi(h,a)}\\&\qquad\times\big(\tilde v(h')-\hat Q(h,a)\big),\\\tilde v(h)={}&\textstyle\sum_a\sigma^t(h,a)\,\tilde v(h,a),\end{aligned}$$computed backward from the terminal payoff. Action $a$ is sampled with probability $\xi(h,a)$, so the correction has mean $\mathbb E[\tilde v(h')]-\hat Q(h,a)$, and by induction from the end of the game $\tilde v(h,a)$ is unbiased for the true value of $a$ whatever $\hat Q$ is. Its variance comes only from the residual $\tilde v(h')-\hat Q$, so a good baseline makes the $1/\xi$ factor harmless, and actions not taken get the baseline instead of 0. The sampled advantage $\tilde v(h,a)-\tilde v(h)$, trained into the advantage network with loss weight $t$, then estimates a quantity proportional to linear regret, as in Step 2, because opponent and chance are sampled on-policy. Baselines are used only for the players' actions: a baseline on chance outcomes, as in tabular VR-MCCFRvariance-reduced Monte Carlo CFR (Schmid et al., 2019): the tabular form of these baselines, for player actions and chance outcomes, needs the transition probabilities, that is, a simulator. The baseline is cheap: 100 to 3,000 minibatch updates per iteration make little difference, plausibly because $\hat Q$ starts from the previous iteration's weights. DREAM plays the SD-CFR average (Step 3).

The regret bound grows exponentially with depth because of the importance weights. DREAM's bound combines the CFR bound of Step 1 with a high-probability bound for sampled CFR (Farina et al., 2020): the average regret on the true values exceeds the one on the sampled values by at most $(M+\tilde M)\sqrt{2\log(1/p)/T}$, where $M\le\Delta$ is the range of the exact losses and $\tilde M$ the range of the sampled ones. A sampled payoff is divided by the probability $\xi[z]$ that $i$'s sampling reaches the terminal history $z$, and exploration gives $\xi[z]\ge(\varepsilon/\htmlData{gr=gn19}{|A_i|})^{d_i}$, so $\tilde M\le\Delta(|A_i|/\varepsilon)^{d_i}$ and, since that factor is at least 1, $M+\tilde M\le2\Delta(|A_i|/\varepsilon)^{d_i}$; adding this sampling term to the CFR bound of Step 1 gives (b). The bound holds for any unbiased estimator, so any baseline is allowed, but the baseline's effect on variance does not enter it: the theorem shows that DREAM converges, and its speed is an empirical matter (Step 9). The guarantee is for the returned average; the exploring policy used in training has none.

DREAM matches the simulator-based method in Leduc and leads the model-free methods in Flop Hold'em. Methods are compared at equal numbers of game states visited, with traversal counts set so that outcome and external sampling visit about as many per iteration (900 DREAM traversals against 346 for external-sampling SD-CFR in Leduc, the measured ratio being 2.6; 50,000 against 10,000 in Flop Hold'em), three runs each. In Leduc, DREAM and external-sampling SD-CFR follow the same curve, near 50 mbb/g after $10^7$ states. NFSPneural fictitious self-play (Heinrich and Silver, 2016): each player learns a best response to the other's average behavior with deep RL while a second network imitates its own average behavior, the earlier model-free standard, needs about $3\times10^8$ states to reach the 60 mbb/g that DREAM reaches near $5\times10^6$, a factor of about 50 that the paper calls two orders of magnitude. DREAM with Deep CFR's average network in place of SD-CFR's averaging levels off near 100. In Flop Hold'em exploitability is a lower bound, what a DDQNdouble deep Q-network, a standard deep RL method, here trained to play against the frozen agent; what it wins is a lower bound on exploitability best response trained against the agent wins: after $1.5\times10^8$ states DREAM is near 40 mbb/g, OS-SD-CFR and NFSP near 100, and external-sampling SD-CFR, which uses the simulator, near 15. Ablations in Leduc: exploration $\varepsilon$ from 0.25 to 1 behaves alike and 0.1 is worse, and retraining the advantage network from scratch every 10 iterations, with fine-tuning in between, reaches the exploitability of always retraining with far fewer network updates and beats never retraining. All values are approximate, read from the plots.