Solving Heads-Up Limit Texas Hold'em

Introduction

Game theory provides a framework for thinking about decisions in the presence of other agents with applications in security [Tambe, 2011] and robust decision making [Chen and Bowling, 2012]. Extensive-form games describe a large class of such problems where multiple agents must make decisions with imperfect information about the state of the world. A common approach to computing policies in such games is to solve the game by finding a Nash equilibrium: a strategy for each player where each individually maximises their utility against the opponent strategies.

Recently, we announced that heads-up limit Texas hold'em poker (HULHE) is essentially solved [Bowling et al., 2015]. The resulting program Cepheus is the first computer program to solve a non-trivial imperfect information game played competitively by humans. Unlike perfect information games where it is easy to compute an exact solution, imperfect information solutions are usually approximated. Essentially solving a game involves computing an approximation of a Nash equilibrium along with an argument that the approximation is of a sufficient quality relative to the inherent stochasticity in the game. Cepheus is close enough to a Nash equilibrium of the game of HULHE that a lifetime of human play cannot be used to distinguish Cepheus from an exact Nash equilibrium with high confidence.

HULHE has over 1014 information sets (i.e., decision points where a player must act). Even after removing strategically identical suit isomorphisms [Billings et al., 2003; Gilpin et al., 2007], the game has over 1013 information sets, one thousand times larger than any previously solved imperfect information game. Solving an imperfect information game at this scale poses two challenges: computation and space. Solution techniques generally require space at least on the order of the size of the resulting strategy. For this reason, space-efficient algorithms like Counterfactual Regret Minimization (CFR) [Zinkevich et al., 2007], and its family of algorithms, are a popular choice for large games [Jackson, 2013; Brown et al., 2015]. Even with space efficient CFR algorithms, HULHE would require 262 TiB (assuming 4-byte values) to store the strategy and regret during computation. A second challenge is computation time. The running time of CFR also grows with the size of the game, and so solving HULHE with traditional CFR variants is also infeasible.

Cepheus overcame these limitations using a new algorithm, CFR+ [Bowling et al., 2015; Tammelin, 2014]. While our original work demonstrated the scalability of CFR+ to solve HULHE, it provided no proof of correctness and no theoretical explanation for its improvements. Furthermore, there was little discussion of the engineering choices required to scale to large problems, and no exploration of the technique in other games. In this paper we provide these missing pieces. We prove that CFR+ is sound, with the same asymptotic convergence rate as traditional CFR. However, in practice it results in a drastic reduction in computation time. We explore the nature of this empirical performance improvement on smaller toy games, and prove a tracking regret property on its component algorithm regret-matching+, which hints at a reason for its success. We also describe the details behind our space efficient and massively distributed implementation of CFR+, using streaming compression, which reduces the space requirement for HULHE from 262 TiB to a manageable 10.9 TiB. These algorithmic and engineering advances enabled Cepheus's 900 core-year computation to be distributed on a high-performance cluster using 4800 CPUs and completed in 68 days. The resulting strategy reached an exploitability of 0.986 mbb/g (or less than one thousandth of a big-blind per game).

Background

An extensive-form game is a formal model of the sequential interactions between one or more players. Let P be the set of players. Let H be the set possible game states, represented as the history of actions taken from the initial game state ∅. We call the state h · a ∈ H a child of its parent state h. Furthermore, we will say h is an ancestor of descendant state h′ or h ⊑ h′ when h is a prefix of h′ . Let Z be the set of all terminal states. For each non-terminal state h, A(h) gives the set of legal actions, and p(h) ↦→ P ∪ {c} gives the acting player, where c denotes the "chance player", which represents stochastic events outside of the players' control. σc(h, a) is the probability that chance will take action a ∈ A(h) from state h, and is common knowledge. For every z ∈ Z, up(z) ∈ ℜ gives the payoff for player p when the game ends in state z. HULHE is a two player zero-sum game, so P = 1, 2 and u1(z) + u2(z) = 0 for all z ∈ Z.

In an imperfect information game, the game specifies an information partition. Let Ip be a partition of all of the states with player p to act. For any information set I ∈ Ip, any two states h, j ∈ I are indistinguishable by player p. Let I(h) be the information set which contains h, let Z(I, a) be the set of all z ∈ Z such that h · a ⊑ z for some h ∈ I, and let z[I] be the state h ∈ I such that h ⊑ z. HULHE is a game where players have perfect recall, which means that any two states h and j in an information set I ∈ Ip have the same sequence of player p information sets and actions. Informally, perfect recall means that a player does not forget their own actions or any information observed before making those actions.

A behaviour strategy σp ∈ Σp is a function σp(I, a) ↦→ ℜ which defines a probability distribution over valid actions for every information set I ∈ Ip. For simplicity, we will say σp(h, a) to mean σp(I(h), a). A strategy profile σ ∈ Σ is a tuple of strategies, one for each player. Given σ, it is useful to refer to certain products of probabilities. Let πσ (h) = ∏j·a⊑h σP(j)(j, a) be the joint probability of reaching h if all players follow σ. We use πσ-p (h) to refer to the product of terms where P(h) ̸= p, and πσ p (h) to refer to the product of only the terms where P(h) = p. In games with perfect recall, πp(h) = πp(h′ ) for all states h, h′ in I ∈ Ip, so we can also speak of πp(I). We also use πσ (j, h) to refer to the product of terms only from j to h.

The expected utility uσp to player p if all players follow σ is ∑Z πσ (z)up(z). The expected utility uσp (I, a) of taking an action at an information set is ∑z∈Z(I,a) πσ (z)up(z). We also use an alternative utility function called counterfactual value: vσ p (I, a) = ∑z∈Z(I,a) πσ-p (z)πσ p (z[I] · a, z)up(z). Informally, the counterfactual value of information set I and action a for the player acting at I is the expected value assuming the player plays to reach I and choose a.

σp is a player p best response to an opponent strategy σ-p if σp maximises u〈σp,σ-p〉 p . A Nash equilibrium is a strategy profile where all strategies are simultaneously best responses to each other, and an ϵ-Nash equilibrium is a profile where the expected value for each player is within ϵ of the value of a best response strategy. We use the term exploitability to refer to a profile's average loss to a best response across its component strategies. A Nash equilibrium has an exploitability of zero.

Counterfactual Regret Minimization

Consider a repeated decision making problem where we have acted T times in the past by choosing between actions in a set A. Let σt (a) be our probability of selecting action a at timestep t. Regret is the measurement of how much additional utility might have been gained by following some alternative strategy instead in hindsight. One popular notion, external regret, considers only static actions as the alternative strategies: RT (a) = ∑Tt=1 (vt (a) - ∑b∈A σt (b)vt (b)). The overall regret is then RT =maxa RT (a).

Regret-matching [Blackwell, 1956] defines a policy σt (a) = Rt-1 (a)+/ ∑b∈A Rt-1 (b)+ given observed regret prior to the current time, where x+ = max (x, 0). An implementation of regret-matching will generally store the regrets Rt (a) for each action, incrementally updating the values using ∆Rt (a) = vt (a) - ∑b∈A σt (b)vt (b) to compute Rt (a) = Rt-1 (a) +∆Rt (a). Blackwell showed that if the values are drawn from a bounded interval of width L and we use the regret matching policy, we can bound the overall regret RT ≤ L√|A|T for any sequence of values vt . This implies that the average regret RT /T approaches zero as T approaches infinity. Such an algorithm can then be used to approximate an equilibrium in two-player zero-sum games, since if both players have at most ϵ average regret, their average strategies form a 2ϵ-Nash equilibrium.

Regret-matching alone is intractable for extensive-form games, since it would require storing regrets for the exponential number of deterministic strategies. CFR [Zinkevich et al., 2007] overcomes this challenge by independently minimizing regret at each information set. It uses regret-matching over the available actions A(I) at an information set I, computing the regrets Rt (I, a) using the counterfactual value v(I, a) of an action a. Its regret with respect to the exponential number of deterministic strategies can be bounded by the sum of the regrets at the linear number of information sets. When employed in self-play, the average strategy of the players are then guaranteed to converge to a Nash equilibrium.

Poker

From the beginning, poker has had an important role in the development of game theory [Borel, 1921; von Neumann, 1928; von Neumann and Morgenstern, 1947; Nash and Shapley, 1950; Kuhn, 1950]. Full-scale poker has been a challenge problem for artificial intelligence, operations research, and psychology, with work going back more than 40 years [Billings et al., 2002]. We examine two variants of poker in this paper: HULHE, which is played by humans, and Rhode Island hold'em, a synthetic game created for research.

HULHE is a two player poker game that consists of four betting rounds, called the pre-flop, flop, turn, and river. Before each game of poker, both players put in some number of chips, called the blinds, into a community pot. One player puts in the small blind, and the other player puts in the big blind, which is twice as many chips as the small blind. In the pre-flop and flop all bets are the size of the big blind, and in the turn and river all bets are twice the size of the big blind. These fixed ratios mean that instead of using chips, we can describe all outcomes in terms of fractions of a big blind.

Each player gets two private cards at the beginning of the game. As the game progresses, public cards are dealt out: three cards on the flop, one card on the turn, and another card on the river. These public cards are also called board cards.

Rhode Island hold'em is a synthetic two-player poker game constructed for artificial intelligence research [Shi and Littman, 2001]. It is a smaller game than HULHE, with three shorter betting rounds, one private player card, and a single public card dealt on each of the last two rounds. Rhode Island hold'em has around 4×106 information sets, and was solved in 2005 [Gilpin and Sandholm, 2005].

A New Scalable Approach

Cepheus needed both algorithmic and engineering advances to make the solving of HULHE possible. Each are discussed in-depth below.

The CFR+ Algorithm

Cepheus uses a new variant of CFR, called CFR+, which we will later show converges dramatically faster than CFR. CFR+ involves four changes. First, CFR+ uses a weighted average strategy ¯σT p = 2/(T 2 + T) ∑Tt=1 tσtp , rather than the uniform average used by CFR. Second, many CFR implementations use sampling techniques to speed convergence [Lanctot et al., 2009], whereas CFR+ uses no sampling. Third, CFR as described in the original paper simultaneously updates regret for both players, while CFR+ does alternating updates. Fourth, and most importantly, CFR+ uses regret-matching+ in place of regret-matching.

Regret-matching+ is a regret-minimizing algorithm that operates very similarly to regret-matching. Where regretmatching ignores actions that have an accumulated negative regret, regret-matching+ actively resets any accumulated negative regret back to zero. Formally, regret-matching+ does not store the regrets Rt (a), but instead tracks a regretlike value: Qt (a) = (Qt-1 (a) +∆Rt (a))+, and bases its policy on these values σt (a) = Qt-1 (a)/ ∑b∈A Qt-1 (b).

Theorem 1 Given a set of actions A, and any sequence of T value functions vt : A ↦→ ℜ with a bound L such that |vt (a) - vt (b)| ≤ L for all t and a, b ∈ A, an agent acting according to the regret-matching+ algorithm will have regret of at most L√|A|T .

The proof of all of the theorems in this paper are in the appendix. So, regret-matching+ has the same regret bound as regret-matching, and therefore CFR+ has the same regret bound as CFR. However, in the next section we show in practice CFR+ dramatically outperforms CFR.

This empirical difference has a partial explanation. Intuitively, one might expect regret-matching+ to outperform regret-matching when the best action suddenly changes. Regret-matching must wait for the previously poor action to prove itself, overcoming all of its accumulated negative regret. Regret-matching+, though, will start playing the new best action immediately since its accumulated negative regret is forgotten. This intuition can be captured by examining the algorithms in terms of tracking regret. Tracking regret [Herbster and Warmuth, 1998] considers the hindsight performance of a larger set of alternatives, e.g., strategies that change their action at most (k - 1) times. Regret-matching has very poor tracking regret properties, possibly having linear regret even against strategies with a single switch (k = 2). In contrast, regret-matching+ is the first regret-matching based algorithm with sublinear tracking regret.

Theorem 2 Consider alternative sequences of strategies that can change up to k - 1 times, then regret-matching+ has a regret bound of kL√|A|T .

The final change in CFR+ is to use a linearly-increasing weighted average strategy.

Theorem 3 Let σt be a sequence of T behaviour strategy profiles from running CFR+ for T iterations, in an extensiveform game where max |vp(l) - vp(l′ )| ≤ L for all players p and terminal histories l, l′ . Then the linearly weighted average strategy profile where ¯σT p = 2/(T 2 + T) ∑Tt=1 tσtp is a 2(|I1| + |I2|)L√k/√T-Nash equilibrium, where k = maxI∈I |A(I)|.

This result guarantees that linear weighting CFR+ achieves the same asymptotic guarantees as uniform weighting with CFR or CFR+. Theorem 3 does not apply to CFR, and in contrast to CFR+ where linear weighting improves performance, CFR performance decreases with linear weighting. In the next section we give an experimental comparison of uniform and linear weighting. We also show that in practice the current strategy in CFR+ often achieves a close approximation to the Nash equilibrium, so this aggressive weighting can further speed convergence.

Engineering Details

CFR+ is space efficient, and improves on the speed of CFR, but using CFR+ to solve a game the size of HULHE still poses a challenge both in terms of computation time and space. The 262 TiB of regret values and average strategy is unlikely to fit in RAM, and may not even fit on available disk. 900 core-years of computation time [Bowling et al., 2015] is too long for a single machine. The approach used by Cepheus is to compress and store the values on disk, and distribute the CFR+ computation across a cluster of compute nodes. Both parts of this approach have a number of important technical considerations that we discuss below.

Compressed Values on Disk Because CFR+ updates all values in the game at each iteration, rather than updating randomly selected locations, CFR+ is particularly suited for use with compression. The algorithm amortizes the compression/decompression overhead by doing a full and exact CFR update. For the same reason, CFR+ can efficiently load and save this compressed data to disk. Taking advantage of this to store compressed values on disk still requires attention to a few implementation details. Any compression method used to reduce the storage requirements must simultaneously be good enough to reduce the data to a manageable size, and fast enough that the compute nodes are not excessively waiting on loading and storing the values. In a similar vein, it is critical that disk I/O be serialized and data pre-fetched to minimize the CPUs waiting on the disk. Finally, because space is tight, some care must be taken in managing compressed, uncompressed, and newly compressed data.

We suggest two application specific ideas for combining CFR+ and compression. The entropy of the original data in CFR+ can be reduced, and it is possible to take advantage of game-specific regularity in the data that standard compression techniques may be otherwise unable to find. Both ideas were mentioned in our work on solving HULHE [Bowling et al., 2015], but here we give more detail on these critical enhancements.

First, the entropy of the regrets and average strategy can be reduced by storing values as fixed point numbers instead of floating point numbers. Floating point numbers are an obvious choice for a large computation involving expected values across probabilistic outcomes, but storing the floating point values contain more information than we need for the targeted solution quality. We can instead use floating point numbers for all intermediate computation, but scale the values and truncate them to integers before storing them. By adjusting the scaling factor, we can trade potentially decreased accuracy for fewer significant bits and more easily compressible data. In our results section, we will further explore the effects of the scaling factor.

Games may have some regular structure that a generic compressor has difficulty finding. HULHE has many groups of cards that are likely to be similar. Given a fixed betting sequence and board cards, there are private cards where we would expect to see similar regret values and action probabilities. For some board cards, we would expect values to be similar for all private cards. By sorting the boards, and then sorting the private cards, we can use earlier values to predict the next value. Instead of compressing the values directly, we can compress the errors in the predicted values. The error values take advantage of game specific knowledge encoded in the sorting order, and are more readily compressible. For HULHE, we suggest sorting the boards by the number of suits that can make a flush in each round, breaking ties by card rank, and sorting the private cards by rollout hand strength - the expected number of times the private cards are ahead given all possible opponent cards and future board cards.

With compressed data, it becomes necessary to decompress the data to run the computation, and then re-compress new results. There are two memory management issues that need to be handled carefully. First, decompressing all of the data may require too much space. This can be handled by using just-in-time decompression and compression, decompressing only the necessary blocks of values before re-compressing the data. Second, using separate space for old and newly compressed data doubles the required space. This can be handled by using a linked list of fixed size chunks to store compressed data, recycling chunks from old compressed data after they have been completely consumed by the decompressor.

Distributed Computation CFR+ is a large recursive computation: the counterfactual values used to update regrets at an information set I are combined with the current policy at I to produce one of the counterfactual values for the parent of I. Because of this, the game can be split into a trunk and subgames located on separate machines [Johanson et al., 2011], with probabilities coming in from the trunk, and counterfactual values coming back from the subgames.

If we split the game of HULHE after the second round of betting there are 63 betting sequences and 1755 possible combinations of board cards, for a total of 110, 565 subgames. There are at most 2 ∗ (49 2 ) = 2352 probabilities to pass to each subgame, one for each possible combination of private cards for each player. Each subgame passes the same number of counterfactual values back to the trunk. This is only 1 GiB of communication in each direction per iteration, even using 8-byte floating point values. With full unsampled CFR+ iterations, the cost for 2 GiB of network communication is negligible.

The architecture for Cepheus has one node processing the trunk, sending probabilities for subgames to worker nodes, and then waiting on subgame values from the worker nodes. Each worker node has one thread receiving subgame probabilities from the trunk node and reading the necessary compressed subgames off disk to fill a buffer of subgames to process. Worker nodes have another thread which empties a buffer of processed subgames by writing them to disk. Finally, worker nodes have multiple threads which remove subgames from the common pool of unprocessed subgames, do the CFR+ update, send values to the trunk node, and add the updated subgame to the buffer of processed subgames.

Empirical Results

In this section, our experiments will demonstrate the empirical advantages of CFR+ over CFR, and highlight the engineering decisions that must be made for large-scale implementations. Our domain for these experiments is Rhode Island hold'em, a small synthetic poker game with a similar structure to HULHE. We also demonstrate the strong performance of CFR+ is not limited to poker-like games by comparing CFR and CFR+ in matrix games.

We begin our empirical analysis by considering the two key differences between CFR+ and CFR: using regretmatching+instead of regret-matching, and applying a linear weight to the average strategy updates instead of a constant weight. In Figure 1a, we show the convergence of the average strategies generated by CFR+ and CFR, as well as variants that make only one of these changes. This result illustrates that applying regret-matching+alone provides an advantage over CFR in this game, and also applying the linear weight gives a further improvement.

In Figure 1b, we compare the convergence of the CFR and CFR+ average strategies against the exploitability of their current strategies. The theoretical proofs for CFR and CFR+ guarantee that the average strategy converges towards a Nash equilibrium. While the CFR current strategy does not converge to a Nash equilibrium in theory or in practice, in this figure we observe that the CFR+ current strategy appears to converge in practice in this game, and at a faster rate than the CFR average strategy. Cepheus exploited this observation in solving HULHE, in which the CFR+ current strategy was used as its solution, ultimately converging more quickly than the average.

Next, we explore the use of scaling parameters for fixedpoint arithmetic involving regret values in our CFR+ implementation. Lower regret scaling factors result in less accurate values, but also enables better compression so that less space is used. For the HULHE solution, it was necessary to carefully tune this parameter so that the computation would reach the target exploitability of 1 milli-big-blind per game while remaining within available storage. In Figure 1c, we demonstrate the first part of this tradeoff in Rhode Island hold'em. Each curve shows the convergence of the CFR+ average strategy when the regret values use a scaling parameter from the set: {0.25, 0.5, 0.75, 1, 1.5, 2, 4, 8, 16, 32, 64}. Note that the chart focuses on iterations 100 through 2000; before iteration 100, all of the curves followed the same trajectory. However, after iteration 100, we see the curves with low parameter values diverge in increasing order, with four unable to reach the goal of 1 milli-big-blind per game within 2000 iterations.

In Figure 1d, we consider the memory required for each of the parameter choices, at the iteration when they reached an exploitability of 1 milli-big-blind per game. While conservative (and therefore large) scaling factors converge reliably in Figure 1c, they also require more memory than smaller parameter choices. However, overly aggressively small parameters may also require more memory if they converge more slowly and must store larger regret values accumulated over additional iterations. Through experiments in small games, this parameter can be tuned to make a large-scale computation feasible as was done by Cepheus.

Matrix Games

The strong performance of CFR+ is not limited to a few variants of poker. We use matrix games to examine the wider applicability of CFR+ and regret-matching+.

Figure 2a shows the performance of CFR and CFR+ in the matching pennies game, a two by two matrix game. If HULHE is at one extreme as a large, complex game, two by two matrix games are at the other extreme. In the matching pennies game, each player has a coin with two sides, heads and tails. Both players secretly place their coin with either heads or tails facing up. After the coins are placed, both players reveal their coin. We used skewed zero-sum payoffs, where the row player wins 1 if both coins were heads, wins 4 if both coins were tails, and otherwise loses 2.

While the benefit of CFR+ shown in Figure 2a is not as large as in HULHE or Rhode Island hold'em, CFR+ is still producing low exploitability strategies more quickly than CFR. For example, given a target exploitability of 10-3 , CFR first reaches the target by iteration 3, 539, while CFR+ reaches the same target by iteration 343. The very different nature of the matching pennies game compared to HULHE also shows up in the large fluctuations in the exploitability of the average strategy, compared to the visibly smooth progress in larger games.

Figure 2b shows results from a game somewhere between HULHE and the matching pennies game, using 10 randomly generated, 1000 by 1000 matrix games. Payoffs for each pair of strategies in a game were identically and independently sampled from a normal distribution with mean 0 and a standard deviation of 1. We ran CFR and CFR+ on each of the 10 games, and the exploitabilities in Figure 2b are the average values across the 10 runs.

The large performance advantage of CFR+ is visible again in larger matrix games. A target exploitability of 10-3 is achieved by CFR in 510 iterations and by CFR+ in 83 iterations. CFR does not reach a target of 10-4 at all within 10, 000 iterations, while CFR+ requires only 331 iterations to reach 10-4 , and reaches 10-6 by iteration 4, 836.

Conclusion

Good play in imperfect information games like poker requires deception and bluffing, which are not generally considered to be machine-like traits. HULHE is the first competitively played game of imperfect information to be essentially solved, marking a significant milestone in game theory and artificial intelligence. The computation behind this result posed both algorithmic and engineering challenges. Cepheus solved HULHE using a new algorithm CFR+, fast custom compression to reduce space, careful use of disk to increase available space, and 4800 CPUs on a high performance research cluster. We demonstrate that the CFR+ algorithm outperforms the commonly used CFR algorithm, prove that CFR+ and its component algorithm regret-matching+ are sound, and show that regret-matching+minimizes a regret measure where traditional regret-matching does not. This establishes the new state-of-the-art in solving large extensiveform games.

Acknowledgements

This research was supported by the Natural Sciences and Engineering Research Council (NSERC), Alberta Innovates Centre for Machine Learning (AICML), and Alberta Innovates Technology Futures (AITF). Computing resources were provided by Calcul Qu´ebec, Westgrid, and Compute Canada.

Proofs

Lemma 1 Given a sequence of strategies σ1 , ..., σT , each defining a probability distribution over a set of actions A, let Qt (a) = (Qt-1 (a) +∆Rt (a))+ and Q0 (a) = 0 for all actions a ∈ A. The regret-like value Qt (a) is then an upper bound on the regret Rt (a), and Qt (a) - Qt-1 (a) ≥ ∆Rt (a) = Rt (a) - Rt-1 (a).

Proof For any t ≥ 1 we have

Lemma 2 Given a set of actions A, and any sequence of T value functions vt : A ↦→ ℜ with a bound L such that |vt (a) - vt (b)| ≤ L for all t and a, b ∈ A, after playing the sequence σt of regret-matching+ strategies, the regretlike value QT (a) ≤ L√|A|T for all a ∈ A.

Proof

Q0 (a) = 0 for all a, so by induction (maxa QT (a))2 ≤ T |A|L2 , which gives us QT (a) ≤ L√|A|T . □

Proof of Theorem 1 From Lemma 2, we have QT (a) ≤ L√|A|T . From Lemma 1, we get RT (a) ≤ L√|A|T . This holds for all a ∈ A, so regret RT ≤ L√|A|T . □

Proof of Theorem2 Consider an arbitrary k-partition strategy ⃗s = s1 , ..., sT for T time steps, with si ∈ A, that switches actions at most k - 1 times. If we played policies σ1 , ..., σT on the T time steps, the regret for ⃗s is RT ⃗s = ∑Tt=1 vt (st ) - ∑a∈A σt (a)vt (a).

For this arbitrary k-partition strategy, we can construct a partition B of the T time steps into contiguous blocks of time such that for any B ∈ B we have |B| ≤ k andsi = sj for any i, j ∈ B. Let f[B] and l[B] be the first and last time step of any block B ∈ B, and sB be the action chosen by ⃗s at all time steps in block B. We can re-write the regret for ⃗s as RT ⃗s = ∑B∈B ∑l[B] t=f [B] ∆Rt (sB ).

Consider the quantity RB (sB ) = ∑l[B] t=f [B] ∆Rt (sB ). From Lemma 1 RB (sB ) ≤ ∑l[B] t=f[B] ∆Qt (sB ). By the definition of regret-matching+ we get RB (sB ) ≤ ∑l[B] t=1 ∆Qt (sB ) = Ql[B] . From Lemma 2, RB (sB ) ≤ L√|A|l[B] ≤ L√|A|T .

Because we have a bound on RB (sB ) that does not depend on B, we have RT ⃗s ≤ |B|L√|A|T ≤ kL√|A|T. Finally, ⃗s was an arbitrary k-partition strategy, so this bound holds for all k-partition strategies, including the strategy with maximum regret. □

Lemma 3 Call a sequence x1, ..., xT of bounded real values B-plausible if B > 0, ∑it=1 xt ≥ 0 for all i, and ∑Tt=1 xt ≤ B. For any B-plausible sequence, ∑Tt=1 txt ≤ TB.

Proof Consider any B-plausible sequence that maximises the weighted sum. That is, let x∗1 , ..., x∗T =

argmaxx′1 ,...,x′T ∑Tt=1 tx′t . We will show this by proving that x∗i ≥ 0 for all 1 ≤ i ≤ T .

For any i < T, it can not be the case that for any i < j that x∗i > 0, x∗j < 0, and x∗k ≥ 0 for all k where i < k < j. Assume this were true, then let δ = min(|x∗i |, |x∗j |). Construct a new sequence x′ where x′i = x∗i -δ, x′j = x∗j +δ, and x′k = x∗k for all k ̸= i, j. This new sequence x′ is Bplausible. For all k where i ≤ k < j we have ∑kt=1 x′t = -δ + ∑i-1 t=1 x∗t + ∑kt=i x∗t ≥ -δ+0+δ = 0. For all k where k < i or k ≥ j we have ∑kt=1 x′t = ∑kt=1 x∗t . Looking at the weighted sum of x′ , we also have ∑t tx′t ≥ ∑t tx∗t , which contradicts the construction of x∗ as a maximizing sequence.

Further, it can not be the case that x∗j < 0 for any j. Assume there is a negative value. Let j be the minimum index such that that x∗j < 0. Because j is the minimum index, x∗k ≥ 0 for all k < j. From above, it can not be the case that x∗i > 0 for any i < j. This means x∗k = 0 for all k < j, so we have ∑jt=1 x∗t = x∗j < 0, which contradicts x∗ being a B-plausible sequence. Therefore, we have x∗i ≥ 0 for all i.

Using the fact all values in the sequence are non-negative, ∑t tx∗t ≤ ∑t Tx∗t = T ∑t x∗t . From the definition of Bplausible, ∑t x∗t ≤ B, so ∑t tx∗t ≤ TB. □

Lemma 4 Let A be a set of actions, vt : A ↦→ ℜ be a sequence of T value functions over A with a bound L such that |vt (a) - vt (b)| ≤ L for all t and a, b ∈ A, and σt be the sequence of regret-matching+ policies over T time steps. Construct a new sequence v′t of (T 2 + T)/2 value functions by using t subsequent copies of vt (i.e., v1 , v2 , v2 , v3 , v3 , v3 , ...) and a similar sequence σ′t from σt . Then the regret RT (a) of sequence σ′ is bounded by TL√|A|T.

Proof For any action a, consider the regret R′(T 2+T)/2 (a) of the expanded sequences v′ and σ′ . We know R′(T 2+T)/2 (a) = ∑(T 2+T)/2 t=1 ∆R′t (a) where ∆R′t (a) = v′t (a) - ∑b∈A σ′t (b)v′t (b). By construction of v′ and σ′ , the sequence ∆R′t (a) is a sequence of t subsequent copies of ∆Rt (a) = vt (a) - ∑b∈A σt (b)vt (b). So R′(T 2+T)/2 (a) = ∑Tt=1 t∆Rt (a).

Let ∆Qt (a) = Qt (a) - Qt-1 (a) be the change in Q values for action a from using regret-matching+ on the T time steps with value functions vt . From Lemma 1, we have ∆Qt (a) ≥ ∆Rt (a). From above, this gives us R′(T 2+T)/2 (a) ≤ ∑Tt=1 t∆Qt (a). ∆Qt (a) is a L√|A|Tplausible sequence, so by Lemma 3 R′(T 2+T)/2 (a) ≤ ∑Tt=1 t∆Qt (a) ≤ TL√|A|T . □

Proof of Theorem 3 From the sequence of T strategy profiles σt , construct a new sequence σ′t of (T 2 + T)/2 strategy profiles consisting of t subsequent copies of σt , as in Lemma 3. From Lemma 4, we know that for any information set I and action a, R′(T 2+T)/2 (I, a) ≤ TL√|A(I)|T. Because this holds for arbitrary a, we have R′(T 2+T)/2 (I) ≤ T L√|A(I )|T .

From the original CFR convergence proof [Zinkevich et al., 2007], we have R′(T 2+T)/2 p ≤ ∑I∈Ip R′(T 2+T)/2 (I) for any player p. From above, R′(T 2+T)/2 p ≤ ∑I∈Ip TL√|A(I)|T ≤ |Ip|TL√kT. Because T 2 + T ≥ T 2 , we get the average regret 2R′(T 2+T)/2 p /(T 2 + T) ≤ 2|Ip|L√k/√T .

From the folk theorem linking regret to an ϵ-Nash equilibrium, given a sequence of strategy profiles with player 1 and 2 average regrets of a and b, the strategy profile of the average strategies is a (a + b)-Nash equilibrium. The average strategies from the sequence σ′ is therefore a 2(|I1| + |I2|)L√k/√T -Nash equilibrium.

Finally, by the construction of σ′ , for any player p the average strategy 2/(T 2 + T) ∑(T 2+T)/2 1 σ′t p = 2/(T 2 + T) ∑T1 tσtp = ¯σT p , which is the linearly weighted average strategy defined in statement of the theorem. □