How to cite

@misc{mit-multiagent-learning-lecture-8,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Lecture 8: Learning in extensive-form games},
  booktitle = {MIT Topics in Multiagent Learning Lecture Notes},
  note = {MIT 6.7980, Fall 2026},
  year = {2026},
  url = {https://www.mit.edu/~6.7980/learning_efg.html}
}

Lecture 8

Learning in extensive-form games

Instructor

Prof. Gabriele Farina (gfarina@mit.edu)

Lecture date

Thu, Oct 8, 2026

Several approaches for constructing no-regret algorithms for extensive-form games have been proposed. For one, extensive-form games are a particular instance of combinatorial games for which the multiplicative weights update algorithm can be implemented efficiently in the reduced normal form of the game, despite the exponential size. We will see more details about this in a later class.

As explained in Lecture 7, the natural representation of strategies to define learning in extensive-form games is the sequence-form representation. Indeed, in that representation utility functions are linear and the strategy set of each player a convex polytope, aligning with the requirements of the regret minimization framework.

Thanks to the sequence form representation of strategies, all the results about external regret minimization we have seen so far apply to extensive-form games as well, including for example the fact that a Nash equilibrium in a two-player zero-sum game can be found by letting two regret minimizers play against each other by exchanging sequence-form strategies at every iteration according to the canonical learning setup.

Another example is the computation of coarse correlated equilibria in any multiplayer extensive-form game via external regret minimization, or computation of best responses against static opponents.

To construct an external regret minimizer that outputs sequence-form strategies, several approaches can be followed. For one, we have seen that one can always use the online projected gradient ascent algorithm, which is a particular instantiation of the online mirror descent (OMD) algorithm. The drawback of such approach is that it requires projecting onto the polytope of sequence form strategies, which might be laborious. Alternative regularizers (i.e., distance-generating functions) that render projection easier have been proposed. However, for today we focus on a different approach, which has been extremely popular in practice: the counterfactual regret minimization (CFR) algorithm.

L8.1 The CFR algorithm

The idea of the CFR algorithm is simple: construct a regret minimizer for the whole tree-form problem starting from local regret minimizers at each decision point, each learning what actions to play at that decision point.

Example L8.1 .

As an example, consider the TFDP faced by Player 1 in the game of Kuhn poker [Kuh50[Kuh50] Kuhn, H. W. (1950). A Simplified Two-Person Poker. In H. W. Kuhn & A. W. Tucker (Eds.), Contributions to the Theory of Games (Vol. 1, pp. 97–103). Princeton University Press.], which we already introduced in Lecture 7. The black nodes are the decision points of the player, and the white nodes are the observation points.

Since the player has six decision points—denoted $j_{1} , \dots , j_{6}$ in the figure—the CFR algorithm will use six local regret minimizers, which we denote $R_{1} , \dots , R_{6}$ . Each regret minimizer $R_{j}$ will be responsible for outputting a local strategy $b_{j} \in \Delta (A_{j})$ for the decision point $$j$$ .

The local distributions output by the different local regret minimizers is then combined to form a sequence-form strategy that plays according to the local distributions at each decision point.

L8.1.1 Where the magic happens: Counterfactual utilities

What is the training signal that each local regret minimizer receives? In other words, what is the utility that the regret minimizer at decision point $$j$$ observes? The answer is the counterfactual utility.

Remember that in the sequence form representation, the dimensionality of the strategy vectors matches the number of actions controlled by the players. Hence, the gradient vector received by the regret minimizer has one entry per each action controlled by the player, intuitively representing whether the “probability flow” passing through that action scores well or poorly. The idea of counterfactual utilities is to use as training signal for every $R_{j}$ the vector of expected utilities in the subtrees rooted at each of the actions $a \in A_{j}$ .

It can be shown that the regret cumulated by the CFR algorithm satisfies the following bound.

Theorem L8.2 .

Let $\mathord{\operatorname{Reg}}_{j}^{( T )}$ , for $j \in \mathcal{J}$ , denote the regret cumulated up to time $$T$$ by each of the regret minimizers $R_{j}$ . Then, the regret $\mathord{\operatorname{Reg}}^{( T )}$ cumulated by Algorithm 1 up to time $$T$$ satisfies

\displaystyle \mathord{\operatorname{Reg}}^{\left( T \right)} \le \sum_{j \in \mathcal{J}} \operatorname*{max} \left\{0 , \mathord{\operatorname{Reg}}_{j}^{\left( T \right)}\right\} .

It is then immediate to see that if each $\mathord{\operatorname{Reg}}_{j}^{( T )}$ grows sublinearly in $$T$$ , then so does $\mathord{\operatorname{Reg}}^{( T )}$ .

In order to formally introduce counterfactual utility, we recall a bit of notation to deal with tree-form decision processes.

Notation for tree-form decision processes We recall the following notation for dealing with tree-form decision processes (TFDPs), which we introduced in Lecture 7. The notation is also summarized in Table 1.

We denote the set of decision points in the TFDP as $\mathcal{J}$ , and the set of observation points as $\mathcal{K}$ . At each decision point $j \in \mathcal{J}$ , the agent selects an action from the set $A_{j}$ of available actions. At each observation point $k \in \mathcal{K}$ , the agent observes a signal $s_{k}$ from the environment out of a set of possible signals $S_{k}$ .
We denote by $$ρ$$ the transition function of the process. Picking action $a \in A_{j}$ at decision point $j \in \mathcal{J}$ results in the process transitioning to $ρ (j , a) \in \mathcal{J} ∪ \mathcal{K} ∪ \{\bot \}$ , where $\bot$ denotes the end of the decision process. Similarly, the process transitions to $ρ (k , s) \in \mathcal{J} ∪ \mathcal{K} ∪ \{\bot \}$ after the agent observes signal $s \in S_{k}$ at observation point $k \in \mathcal{K}$ .
A pair $$(j , a)$$ where $j \in \mathcal{J}$ and $a \in A_{j}$ is called a sequence. The set of all sequences is denoted as $Σ \coloneqq \{(j , a) : j \in \mathcal{J} , a \in A_{j}\}$ . For notational convenience, we will often denote an element $$(j , a)$$ in $$Σ$$ as $$j a$$ without using parentheses.
Given a decision point $j \in \mathcal{J}$ , we denote by $p_{j}$ its parent sequence, defined as the last sequence (that is, decision point-action pair) encountered on the path from the root of the decision process to $$j$$ . If the agent does not act before $$j$$ (that is, $$j$$ is the root of the process or only observation points are encountered on the path from the root to $$j$$ ), we let $p_{j} = \emptyset$ .

Example L8.3 .

As an example, consider again the TFDP faced by Player 1 in the game of Kuhn poker [Kuh50], which was also recalled above in Example L8.1. We have that $J = \{j_{1} , \dots , j_{6}\}$ and $K = \{k_{1} , \dots , k_{4}\}$ . We have:

\displaystyle A_{j_{1}} = S_{k_{4}}

\displaystyle = \left\{\mathsfit{c} \mathsfit{h} \mathsfit{e} \mathsfit{c} \mathsfit{k} , \mathsfit{r} \mathsfit{a} \mathsfit{i} \mathsfit{s} \mathsfit{e}\right\} , \qquad A_{j_{5}}= \left\{\mathsfit{f} \mathsfit{o} \mathsfit{l} \mathsfit{d} , \mathsfit{c} \mathsfit{a} \mathsfit{l} \mathsfit{l}\right\} , \qquad S_{k_{1}}= \left\{\mathsfit{j} \mathsfit{a} \mathsfit{c} \mathsfit{k} , \mathsfit{q} \mathsfit{u} \mathsfit{e} \mathsfit{e} \mathsfit{n} , \mathsfit{k} \mathsfit{i} \mathsfit{n} \mathsfit{g}\right\}

\displaystyle p_{j_{4}}

\displaystyle = \left(j_{1} , \mathsfit{c} \mathsfit{h} \mathsfit{e} \mathsfit{c} \mathsfit{k}\right) , \qquad p_{j_{6}}= \left(j_{3} , \mathsfit{c} \mathsfit{h} \mathsfit{e} \mathsfit{c} \mathsfit{k}\right) , \qquad p_{j_{1}}= p_{j_{2}} = p_{j_{3}} = \emptyset .

Furthermore,

\displaystyle ρ \left(k_{3} , \mathsfit{c} \mathsfit{h} \mathsfit{e} \mathsfit{c} \mathsfit{k}\right)

\displaystyle = ρ \left(j_{2} , \mathsfit{r} \mathsfit{a} \mathsfit{i} \mathsfit{s} \mathsfit{e}\right) = \bot , \qquad ρ \left(k_{1} , \mathsfit{k} \mathsfit{i} \mathsfit{n} \mathsfit{g}\right)= j_{3} , \qquad ρ \left(j_{2} , \mathsfit{c} \mathsfit{h} \mathsfit{e} \mathsfit{c} \mathsfit{k}\right) = k_{3} .

Notation for the components of vectors Any vector $x \in \mathbb{R}^{Σ}$ has, by definition, as many components as sequences $$Σ$$ . The component corresponding to a specific sequence $j a \in Σ$ is denoted as $$x [j a]$$ . Similarly, given any decision point $j \in \mathcal{J}$ , any vector $x \in \mathbb{R}^{A_{j}}$ has as many components as the number of actions at $$j$$ . The component corresponding to a specific action $a \in A_{j}$ is denoted $$x [ a ]$$ .

Symbol	Description
$\mathcal{J}$	Set of decision points
$A_{j}$	Set of legal actions at decision point $j \in \mathcal{J}$
$\mathcal{K}$	Set of observation points
$S_{k}$	Set of possible signals at observation point $k \in \mathcal{K}$
$$ρ$$	Transition function: given $j \in \mathcal{J}$ and $a \in A_{j}$ , $$ρ ( j , a )$$ returns the next decision or observation point $$v$$ in $\mathcal{J} ∪ \mathcal{K}$ in the decision tree that is reached after selecting legal action $a \in j$ , or $\bot$ if the decision process ends; given $k \in \mathcal{K}$ and $s \in S_{k}$ , $$ρ ( k , s )$$ returns the next decision or observation point $v \in \mathcal{J} ∪ K$ in the decision tree that is reached after observing signal $$s$$ at $$k$$ , or $\bot$ if the decision process ends
$$Σ$$	Set of sequences, defined as $Σ \coloneqq \{( j , a ) : j \in \mathcal{J} , a \in A_{j}\}$
$p_{j}$	Parent sequence of decision point $j \in \mathcal{J}$ , defined as the last sequence (decision point-action pair) on the path from the root of the TFDP to decision point $$j$$ ; if the agent does not act before $$j$$ , $p_{j} = \emptyset$ .

L8.1.2 Pseudocode for CFR

Pseudocode for CFR is given in Algorithm 1. Note that the implementation is parametric on the regret minimization algorithms $R_{j}$ run locally at each decision point. Any regret minimizer $R_{j}$ for simplex domains can be used to solve the local regret minimization problems. Popular options are the regret matching algorithm, and the regret matching plus algorithm (Lecture 5).

CFR regret minimizer

Data:

R_{j}

, regret minimizer for

\Delta (A_{j})

; one for each decision point

j \in \mathcal{J}

of the TFDP.

Function NextStrategy()

Step 1: ask each of the $R_{j}$ for their next strategy local at each decision point.

For each decision point

j \in \mathcal{J}

b_{j}^{(t)} \in \Delta (A_{j}) ← R_{j}.\text{NextStrategy}()

Step 2: we construct the sequence-form representation of the strategy that plays according to the distribution $b_{j}^{(t)}$ at each decision point $j \in \mathcal{J}$ .

x^{(t)} = 0 \in \mathbb{R}^{Σ}

For each decision point

j \in \mathcal{J}

in top-down traversal order in the TFDP:

For each action

a \in A_{j}

p_{j} = \emptyset

x^{(t)}[j a] ← b_{j}^{(t)}[a]

Else:

10.

x^{(t)}[j a] ← x^{(t)}[p_{j}] ⋅ b_{j}^{(t)}[a]

You should convince yourself that the vector $x^{(t)}$ we just filled in above is a valid sequence-form strategy, that is, it satisfies the required consistency constraints we saw in Lecture 7. In symbols, $x^{(t)} \in \mathcal{Q}$ .

11.

Return

x^{(t)}

12.

Function ObserveUtility( $g^{(t)} \in \mathbb{R}^{|Σ|}$ )

Step 1: we compute the expected utility for each subtree rooted at each node $v \in \mathcal{J} ∪ \mathcal{K}$ .

13.

V^{(t)} ←

empty dictionary. Eventually, it will map keys $\mathcal{J} ∪ \mathcal{K} ∪ \{\bot \}$ to real numbers.

14.

V^{(t)}[\bot ] ← 0

15.

For each node in the tree

v \in \mathcal{J} ∪ \mathcal{K}

in bottom-up traversal order in the TFDP:

16.

v \in \mathcal{J}

17.

Let

\(j \leftarrow v\)

18.

V^{(t)}[j] ← \sum_{a \in A_{j}} b_{j}^{(t)}[a] ⋅ (g^{(t)}[j a] + V^{(t)}[ρ(j, a)])

19.

Else:

20.

Let

\(k \leftarrow v\)

21.

V^{(t)}[k] ← \sum_{s \in S_{k}} V^{(t)}[ρ(k, s)]

Step 2: at each decision point $j \in \mathcal{J}$ , we now construct a local utility vector $g_{j}^{(t)}$ called counterfactual utility.

22.

For each decision point

j \in \mathcal{J}

23.

g_{j}^{(t)} ← 0 \in \mathbb{R}^{A_{j}}

24.

For each action

a \in A_{j}

25.

g_{j}^{(t)}[a] ← g^{(t)}[j a] + V^{(t)}[ρ(j, a)]

26.

R_{j}.\text{ObserveUtility}(g_{j}^{(t)})

L8.1.3 Learning using self-play

The CFR algorithm can be used to learn a Nash equilibrium in a two-player zero-sum game by letting two regret minimizers play against each other. The two regret minimizers exchange their sequence-form strategies at every iteration according to the canonical learning setup.

L8.2 Bibliography for this lecture

[Kuh50]

Kuhn, H. W. (1950). A Simplified Two-Person Poker. In H. W. Kuhn & A. W. Tucker (Eds.), Contributions to the Theory of Games (Vol. 1, pp. 97–103). Princeton University Press.

Changelog

2025-10-09: Fixed typos (thanks Josh Rountree!).