How to cite

@misc{mit-multiagent-learning-lecture-4,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Lecture 4: Foundations of learning in 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_intro.html}
}

Lecture 4

Foundations of learning in games

Instructor

Prof. Gabriele Farina (gfarina@mit.edu)

Lecture date

Thu, Sep 24, 2026

With this lecture we begin to explore what it means to “learn” in a game, and how that “learning”, which is intrinsically a dynamic and local (per-player) concept, relates to the much more static and global concept of game-theoretic equilibrium.

L4.1 Hindsight rationality and $\Phi$ -regret

What does it mean to “learn” in games? Multiple answers are correct. However, today we focus on a powerful answer through the concept of hindsight rationality.

Take the point of view of one player in a game, and denote with $$X$$ be their set of available strategies. In normal-form games, we have seen that a strategy is just a distribution over the set of available actions $$A$$ for the player, so $X = \Delta (A)$ . At each time $t =1,2,\dots$ , the player will play some strategy $x^{(t)} \in X$ , receive some form of feedback, and will incorporate that feedback to formulate a “better” strategy $x^{(t+1)} \in X$ for the next repetition of the game. A typical (and natural) choice of “feedback” is just the utility of the player, given what all the other agents played. However, for the purposes of the abstract model we are building today, let’s not make any assumptions about how the feedback is assigned; we will strive to build algorithms that perform competitively under any feedback—even adversarial one.

Now suppose that the game is played infinite times, and looking back at what was played by the player we realize that every single time the player played a certain strategy $$x$$ , they would have been strictly better by consistently playing different strategy $$x'$$ instead. Can we really say that the player has “learnt” how to play? Perhaps not.

This concept goes under the name of hindsight rationality:

Definition L4.1 (Hindsight rationality, informal) .

The player has “learnt” to play the game if looking back at the history of play, they cannot think of any transformation

ϕ : X \to X

of their strategies that, when applied at the whole history of play, would have given strictly better utility to the player.

We have thus arrived at the following formalization.

Definition L4.2 ( $\Phi$ -regret minimizer) .

Given the convex and compact strategy set $$X$$ and a set $\Phi$ of linear transformations $ϕ:X\to X$ , a $\Phi$ -regret minimizer for the set $$X$$ is a model for a decision maker that repeatedly interacts with a black-box environment. At each time $$t$$ , the regret minimizer interacts with the environment through two operations:

NextStrategy() takes no input, and has the effect that the regret minimizer will output an element $x^{(t)} \in X$ .
ObserveUtility $(u^{(t)})$ provides the environment’s feedback to the regret minimizer, in the form of a linear utility function $u^{(t)} : X \to \mathbb{R}$ that evaluates how good the last-output point $x^{(t)}$ was. The utility function can depend adversarially on the outputs $x^{(1)}, \dots , x^{(t)}$ .

Its quality metric is its cumulative $\Phi$ -regret, defined as the quantity

\displaystyle \Phi \text{-Reg}^{\left(T\right)} \coloneqq \operatorname*{max}_{\hat{ϕ} \in \Phi} \left\{\sum_{t=1}^{T} u^{\left(t\right)}\left(\hat{ϕ}\left(x^{\left(t\right)}\right)\right) - u^{\left(t\right)}\left(x^{\left(t\right)}\right)\right\},

(1)

The goal for a $\Phi$ -regret minimizer is to guarantee that its $\Phi$ -regret grows asymptotically sublinearly as time $$T$$ increases, no matter the sequence of utility functions $u^{(t)}$ .

Calls to NextStrategy and ObserveUtility keep alternating to each other: first, the regret minimizer will output a point $x^{(1)}$ , then it will received feedback $u^{(1)}$ from the environment, then it will output a new point $x^{(2)}$ , and so on. The decision making encoded by the regret minimizer is online, in the sense that at each time $$t$$ , the output of the regret minimizer can depend on the prior outputs $x^{(1)}, \dots ,x^{(t-1)}$ and corresponding observed utility functions $u^{(1)},\dots ,u^{(t-1)}$ , but no information about future utilities is available.

L4.1.1 Notable choices of transformations $\Phi$

The size of the set of transformations $\Phi$ considered by the player defines a natural notion of how “rational” the agent is. There are several choices of interest for $\Phi$ for a normal-form strategy space $X = \Delta (A)$ .

$\Phi =$ set of all stochastic matrices, mapping $\Delta (A) \to \Delta (A)$ . This notion of $\Phi$ -regret is known under the name swap regret. This notion is related to convergence to the set of correlated equilibria.
$\Phi =$ set of all “probability mass transport” on $$X$$ , defined as $\Phi = \{ϕ_{a\to b}\}_{a, b \in A}$ , where

$\displaystyle \left(ϕ_{a\to b}\left(x\right)\right)_{s} \coloneqq \begin{cases}0 & \text{if } s = a \quad \left(\text{remove mass from } a ...\right) \\ x_{b} + x_{a} & \text{if } s = b \quad \left(\text{... and give it to } b\right) \\ x_{s} & \text{otherwise.}\end{cases}$

This is known as internal regret.

Theorem L4.3 (Informal; formal version in Theorem L4.11) .

When all agents in a multiplayer general-sum normal-form game play so that their internal or swap regret grows sublinearly, their average correlated distribution of play converges to the set of correlated equilibria of the game.

In sequential games, the above concept extends to $\Phi =$ a particular set of linear transformations called trigger deviation functions. It is known that in this case the $\Phi$ -regret can be efficiently bounded with a polynomial dependence on the size of the game tree. The reason why this choice of deviation functions is important is given by the following fact.

Theorem L4.4 (Informal) .

When all agents in a multiplayer general-sum extensive-form game play so that their $\Phi$ -regret relative to trigger deviation functions grows sublinearly, their average correlated distribution of play converges to the set of extensive-form correlated equilibria of the game.
$\Phi =$ constant transformations. In this case, we are only requiring that the player not regret substituting all of the strategies they played with the same strategy $\hat{x} \in \Delta (A)$ . $\Phi$ -regret according to this set of transformations $\Phi$ is usually called external regret, or more simply just regret. While this seems like an extremely restricted notion of rationality, it actually turns out to be already extremely powerful. We will spend the rest of this class to see why.

Theorem L4.5 (Informal; formal version in Theorem L4.11) .

When all agents in a multiplayer general-sum normal-form game play so that their external regret grows sublinearly, their average correlated distribution of play converges to the set of coarse correlated equilibrium of the game.

Corollary L4.6 (Informal) .

When all agents in a two-player zero-sum normal-form game play so that their external regret grows sublinearly, their average strategies converge to the set of Nash equilibria of the game.

L4.1.2 An important special case: regret minimization

The special case where $\Phi$ is chosen to be the set of constant transformations is so important that it warrants its own special definition and notation.

Definition L4.7 (Regret minimizer) .

Let $$X$$ be a set. An external regret minimizer for $$X$$ —or simply “regret minimizer for $$X$$ ”—is a $\Phi^{\text{const}}$ -regret minimizer for the special set of constant transformations

\displaystyle \Phi^{\text{const}} \coloneqq \left\{ϕ_{\hat{x}}: x \mapsto \hat{x}\right\}_{\hat{x} \in X}.

Its corresponding $\Phi^{\text{const}}$ -regret is called “external regret” or simply “regret”, and it is indicated with

\displaystyle \text{Reg}^{\left(T\right)} \coloneqq \operatorname*{max}_{\hat{x} \in X} \left\{\sum_{t=1}^{T} u^{\left(t\right)}\left(\hat{x}\right) - u^{\left(t\right)}\left(x^{\left(t\right)}\right)\right\}.

Again, the goal for a regret minimizer is to ensure its cumulative regret $\text{Reg}^{(T)}$ grows sublinearly in $$T$$ .

An important result asserts the existence of algorithms that guarantee sublinear regret for any convex and compact domain $$X$$ , typically of the order $\text{Reg}^{(T)} = O(\sqrt{T})$ asymptotically.

As we will show below, external regret minimization alone is enough to guarantee convergence to Nash equilibrium in two-player zero-sum games, to coarse correlated equilibrium in multiplayer general-sum games, to best responses to static stochastic opponents in multiplayer general-sum games, and much more.

Teaser: From regret minimization to $\Phi$ -regret minimization. As discussed, regret minimization is one instantiation of $\Phi$ -regret minimization—and perhaps the smallest sensible instantiation. Then, clearly, coming up with a regret minimizer for a set $$X$$ cannot be harder than the problem of coming up with a $\Phi$ -regret minimizer for $$X$$ for richer sets of transformation functions $\Phi$ . It might then seem surprising that there exists a construction that reduces $\Phi$ -regret minimization to regret minimization. We will discuss more about this in Supplementary reading S6.

L4.2 Applications of regret minimization

To establish regret minimization as a meaningful abstraction for learning in games, we check that regret minimizing and $\Phi$ -regret minimizing dynamics indeed lead to the expected behavior in common scenarios.

Definition L4.8 (Canonical learning setup) .

In the cases that we will mention, a recurring idea will be to consider the setup in which all players $i \in [n]$ play according to the outputs $x_{i}^{(t)}$ of a $\Phi$ -regret minimizer. At each iteration, the utility function that each player $$i$$ observes from the environment is the utility function $u_{i}$ of that player, evaluated in the strategies played by all players, that is,

\displaystyle u^{\left(t\right)} : \Delta \left(A_{i}\right) \to \mathbb{R} \quad \quad \quad \quad u^{\left(t\right)} \left(x_{i}\right) \coloneqq u_{i} \left(x_{i}, x_{-i}^{\left(t\right)}\right).

Given its importance, we give to this natural setup the name of canonical learning setup.

L4.2.1 Learning a best response against stochastic opponents

As a first smoke test, let’s verify that over time a regret minimizer would learn how to best respond to static, stochastic opponents. Specifically, consider this scenario. We are playing a repeated $$n$$ -player general-sum game with multilinear utilities (this captures normal-form game and extensive-form games alike), where Players $i = 1, \dots , n-1$ play stochastically, that is, at each $$t$$ they independently sample a strategy $x_{i}^{(t)} \in X_{i}$ from the same fixed distribution (which is unknown to any other player). Formally, this means that

\displaystyle \mathop{\mathbb{E}}\limits \left[x_{i}^{\left(t\right)}\right] = \overline{x}_{i} \quad \quad \forall i =1,\dots ,n -1, \quad t = 1,2,\dots .

Player $$n$$ , on the other hand, is learning in the game, picking strategies according to some algorithm that guarantees sublinear external regret, where the feedback observed by Player $$n$$ at each time $$t$$ is their own linear utility function:

\displaystyle \boldsymbol{u}^{\left(t\right)} \coloneqq X_{n} ∋ x_{n} \mapsto u_{n} \left(x_{1}^{\left(t\right)}, \dots , x_{n-1}^{\left(t\right)}, x_{n}\right).

Then, the average of the strategies played by Player $$n$$ converges almost surely to a best response to $\overline{x}_{1}, \dots ,\overline{x}_{n-1}$ , that is,

\displaystyle \frac{1}{T} \sum_{t=1}^{T} x_{n}^{\left(t\right)} \quad \mathop{⟶}\limits^{\text{a.s.}} \quad \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\hat{x}_{n} \in X_{n}} \left\{u_{n} \left(\overline{x}_{1}, \dots , \overline{x}_{n-1}, \hat{x}_{n}\right)\right\}.

(You should try to prove this!)

L4.2.2 Learning a Nash equilibrium in two-player zero-sum games

It turns out that regret minimization can be used to converge to bilinear saddle points, that is solutions to problems of the form

\displaystyle \operatorname*{max}_{x \in X} \operatorname*{min}_{y \in Y} x^{\top} U y,

(2)

where $$X$$ and $$Y$$ are convex compact sets and $$U$$ is a matrix. These types of optimization problems are pervasive in game-theory. The canonical prototype of bilinear saddle point problem is the computation of Nash equilibria in two-player zero-sum games (either normal-form or extensive-form). There, a Nash equilibrium is the solution to (2) where $$X$$ and $$Y$$ are the strategy spaces of Player $$1$$ and Player $$2$$ respectively (probability simplexes for normal-form games or sequence-form polytopes for extensive-form games), and $$U$$ is the payoff matrix for Player $$1$$ . Other examples include social-welfare-maximizing correlated equilibria and optimal strategies in two-team zero-sum adversarial team games.

The idea behind using regret minimization to converge to bilinear saddle-point problems is to use self play. We instantiate two regret minimization algorithms, $R_{X}$ and $R_{Y}$ , for the domains of the maximization and minimization problem, respectively. At each time $$t$$ the two regret minimizers output strategies $x^{(t)}$ and $y^{(t)}$ , respectively. Then, they receive feedback $u_{X}^{(t)}, u_{Y}^{(t)}$ defined as

\displaystyle u_{X}^{\left(t\right)} : x \mapsto \left(U y^{\left(t\right)}\right)^{\top} x ,\quad \quad \quad u_{Y}^{\left(t\right)} : y \mapsto -\left(U^{\top} x^{\left(t\right)}\right)^{\top} y.

We can summarize the process pictorially as follows.

A well known folk theorem establish that the pair of average strategies produced by the regret minimizers up to any time $$T$$ converges to a saddle point of (2), where convergence is measured via the saddle point gap

\displaystyle 0 \le \gamma \left(x , y\right) \coloneqq \left(\operatorname*{max}_{\hat{x} \in X} \left\{\hat{x}^{\top} U y\right\} - x^{\top} U y\right) + \left(x^{\top} U y - \operatorname*{min}_{\hat{y} \in Y} \left\{x^{\top} U \hat{y}\right\}\right) = \operatorname*{max}_{\hat{x} \in X} \left\{\hat{x}^{\top} U y\right\} - \operatorname*{min}_{\hat{y} \in Y} \left\{x^{\top} U \hat{y}\right\}.

A point $(x , y) \in X \times Y$ has zero saddle point gap if and only if it is a solution to (2).

Theorem L4.9 .

Consider the self-play setup summarized in the figure above, where $R_{X}$ and $R_{Y}$ are regret minimizers for the sets $$X$$ and $$Y$$ , respectively. Let $\text{Reg}_{X}^{(T)}$ and $\text{Reg}_{Y}^{(T)}$ be the (sublinear) regret cumulated by $R_{X}$ and $R_{Y}$ , respectively, up to time $$T$$ , and let $\overline{x}^{(T)}$ and $\overline{y}^{(T)}$ denote the average of the strategies produced up to time $$T$$ . Then, the saddle point gap $\gamma (\overline{x}^{(T)}, \overline{y}^{(T)})$ of $(\overline{x}^{(T)}, \overline{y}^{(T)})$ satisfies

\displaystyle \gamma \left(\overline{x}^{\left(T\right)}, \overline{y}^{\left(T\right)}\right) = \frac{\text{Reg}_{X}^{\left(T\right)} + \text{Reg}_{Y}^{\left(T\right)}}{T} \to 0 \quad \quad \text{as } T\to ∞.

Proof.

By definition of regret,

\displaystyle \frac{\text{Reg}_{X}^{\left(T\right)} + \text{Reg}_{Y}^{\left(T\right)}}{T}

\displaystyle \hspace{14.17pt} = \frac{1}{T} \operatorname*{max}_{\hat{x} \in X} \left\{\sum_{t=1}^{T} u_{X}^{\left(t\right)}\left(\hat{x}\right)\right\} - \frac{1}{T} \sum_{t=1}^{T} u_{X}^{\left(t\right)}\left(x^{t}\right) + \frac{1}{T} \operatorname*{max}_{\hat{y} \in Y} \left\{\sum_{t=1}^{T} u_{Y}^{\left(t\right)}\left(\hat{y}\right)\right\} - \frac{1}{T} \sum_{t=1}^{T} u_{Y}^{\left(t\right)}\left(y^{t}\right)

\displaystyle \hspace{14.17pt} = \frac{1}{T} \operatorname*{max}_{\hat{x} \in X} \left\{\sum_{t=1}^{T} u_{X}^{\left(t\right)}\left(\hat{x}\right)\right\} + \frac{1}{T} \operatorname*{max}_{\hat{y} \in Y} \left\{\sum_{t=1}^{T} u_{Y}^{\left(t\right)}\left(\hat{y}\right)\right\} \hspace{17.01pt} \left(\text{since} u_{X}^{\left(t\right)} \left(x^{\left(t\right)}\right) + u_{Y}^{\left(t\right)} \left(y^{\left(t\right)}\right) = 0\right)

\displaystyle \hspace{14.17pt} = \operatorname*{max}_{\hat{x} \in X} \left\{\hat{x}^{\top} U \overline{y}^{\left(T\right)}\right\} - \operatorname*{min}_{\hat{y} \in Y} \left\{\left(\overline{x}^{\left(T\right)}\right)^{\top} U \hat{y}\right\}

\displaystyle \hspace{14.17pt} = \gamma \left(\overline{x}^{\left(T\right)} ,\overline{y}^{\left(T\right)}\right).

Letting

T \to ∞

and using the sublinearity of regret, we obtain the statement.

L4.2.3 Proof of the minimax theorem

The very existence of regret minimizers is a powerful enough fact to imply the minimax theorem!

Theorem L4.10 (Minimax theorem) .

Let $$X$$ and $$Y$$ be convex compact sets, and let $$U$$ be a matrix. Suppose that a regret minimizer $R_{X}$ for set $$X$$ guaranteeing sublinear regret no matter the sequence of utilities can be constructed. Then,

\displaystyle \operatorname*{max}_{x \in X} \operatorname*{min}_{y \in Y} x^{\top} U y = \operatorname*{min}_{y \in Y} \operatorname*{max}_{x \in X} x^{\top} U y.

Proof.

One direction of the equality, specifically

\displaystyle \operatorname*{max}_{x \in X} \operatorname*{min}_{y \in Y} x^{\top} U y \le \operatorname*{min}_{y \in Y} \operatorname*{max}_{x \in X} x^{\top} U y,

follows from definition (this is often called weak duality).

To show the reverse inequality, we will interpret the bilinear saddle point $\operatorname*{min}_{y \in Y} \operatorname*{max}_{x \in X} x^{\top} U y$ as a repeated game. At each time $$t$$ , we will let a regret minimizer $R_{X}$ pick actions $x^{(t)} \in X$ , whereas we will always assume that $y^{(t)} \in Y$ is chosen by the environment to best respond to $x^{(t)}$ , that is,

\displaystyle y^{\left(t\right)} \in \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{min}}\limits_{y \in Y} \left(x^{\left(t\right)}\right)^{\top} U y.

The utility function observed by $R_{X}$ at each time $$t$$ is set to the linear function

\displaystyle u_{X}^{\left(t\right)} \left(x\right) = x^{\top} U y^{\left(t\right)}.

Letting $\overline{x}^{(T)} \in X$ and $\overline{y}^{(T)} \in Y$ be the average strategies output up to time $$T$$ , that is,

\displaystyle \overline{x}^{\left(T\right)} \coloneqq \frac{1}{T} \sum_{t=1}^{T} x^{\left(t\right)} \quad \quad \overline{y}^{\left(T\right)} \coloneqq \frac{1}{T} \sum_{t=1}^{T} y^{\left(t\right)},

then we have

\displaystyle \operatorname*{max}_{x \in X} \operatorname*{min}_{y \in Y} x^{\top} U y \ge \operatorname*{min}_{y \in Y} \left\{\left(\overline{x}^{\left(T\right)}\right)^{\top} U y\right\} = \frac{1}{T} \operatorname*{min}_{y \in Y} \sum_{t=1}^{T} \left(x^{\left(t\right)}\right)^{\top} U y \ge \frac{1}{T} \sum_{t=1}^{T} \left(x^{\left(t\right)}\right)^{\top} U y^{\left(t\right)}.

The important insight is that the right-hand side can be related to the regret incurred on $$X$$ : by definition,

\displaystyle \frac{1}{T} \sum_{t=1}^{T} \left(x^{\left(t\right)}\right)^{\top} U y^{\left(t\right)}

\displaystyle = -\frac{\text{Reg}_{X}^{\left(T\right)}}{T} + \frac{1}{T} \operatorname*{max}_{x \in X} \left\{\sum_{t=1}^{T} x^{\top} U y^{\left(t\right)}\right\}

\displaystyle = -\frac{\text{Reg}_{X}^{\left(T\right)}}{T}+ \operatorname*{max}_{x \in X} x^{\top} U \overline{y}^{\left(T\right)}

\displaystyle \ge -\frac{\text{Reg}_{X}^{\left(T\right)}}{T} + \operatorname*{min}_{y \in Y} \operatorname*{max}_{x \in X} x^{\top} U y

Combining the expressions, we obtain

\displaystyle \operatorname*{max}_{x \in X} \operatorname*{min}_{y \in Y} x^{\top} U y \ge \operatorname*{min}_{y \in Y} \operatorname*{max}_{x \in X} x^{\top} U y - \frac{\text{Reg}_{X}^{\left(T\right)}}{T}.

Letting $T \to ∞$ proves the result.

L4.2.4 Learning (coarse) correlated equilibria

The previous result is in fact a direct corollary of the more general connection between $\Phi$ -regret minimization and the set of coarse-correlated equilibria in multiplayer general-sum games. We present a general form of this connection in the next theorem.

Theorem L4.11 (Formal version of Theorems L4.3 andL4.5) .

Let $x_{1}^{(t)}, \dots , x_{n}^{(t)}$ the strategies played by the players at any time $$t$$ , and let $\Phi \text{-Reg}_{i}^{(t)}$ denote the internal regret incurred by Player $$i$$ up to time $$t$$ . Consider now the average correlated distribution of play up to any time $$T$$ , that is, the distribution $\mu^{(T)}$ that selects a time $\overline{t}$ uniformly at random from the set $\{1,\dots ,T\}$ , and selects actions $(a_{1},\dots , a_{n})$ independendently according to the $x_{i}^{(\overline{t})}$ , that is,

\displaystyle \mu^{\left(T\right)} \coloneqq \frac{1}{T} \sum_{t=1}^{T} x_{1}^{\left(t\right)}⊗\dots ⊗ x_{n}^{\left(t\right)}.

This distribution satisfies the inequality

\displaystyle \operatorname*{max}_{ϕ \in \Phi} \mathop{\mathbb{E}}\limits_{a \sim \mu^{\left(T\right)}} \left[u_{i} \left(ϕ\left(a_{i}\right), a_{-i}\right) - u_{i} \left(a_{i}, a_{-i}\right)\right] \le \frac{\Phi \text{-Reg}_{i}^{\left(T\right)}}{T}.

Proof.

Pick an arbitrary $ϕ \in \Phi$ . With the usual slight abuse of notation, we will denote with $$ϕ(a)$$ , where $$a$$ is an action, as the strategy returned by $$ϕ$$ when evaluated in the deterministic strategy that places all the mass on $$a$$ . Expanding the specific structure of $\mu^{(T)}$ , we can decompose the expectation

\displaystyle \mathop{\mathbb{E}}\limits_{a \sim \mu^{\left(T\right)}} \left[u_{i} \left(ϕ\left(a_{i}\right), a_{-i}\right) - u_{i} \left(a_{i}, a_{-i}\right)\right]

\displaystyle \mathop{\mathbb{E}}\limits_{a \sim \mu^{\left(T\right)}} \left[u_{i} \left(ϕ\left(a_{i}\right), a_{-i}\right) - u_{i} \left(a_{i}, a_{-i}\right)\right]

\displaystyle \quad \quad = \frac{1}{T} \sum_{t=1}^{T} \mathop{\mathbb{E}}\limits_{a \sim x_{1}^{\left(t\right)}⊗\dots ⊗ x_{n}^{\left(t\right)}} \left[\left(u_{i} \left(ϕ\left(a_{i}\right), a_{-i}\right) - u_{i} \left(a_{i}, a_{-i}\right)\right)\right]

\displaystyle \quad \quad = \frac{1}{T} \sum_{t=1}^{T} \left(u_{i} \left(\mathop{\mathbb{E}}\limits_{a_{i} \sim x_{i}^{\left(t\right)}} \left[ϕ\left(a_{i}\right)\right], \mathop{\mathbb{E}}\limits_{a_{-i} \sim ⊗ x_{-i}^{\left(t\right)}}\left[a_{-i}\right]\right) - u_{i} \left(\mathop{\mathbb{E}}\limits_{a_{i} \sim x_{i}^{\left(t\right)}}\left[a_{i}\right], \mathop{\mathbb{E}}\limits_{a_{-i} \sim ⊗ x_{-i}^{\left(t\right)}} \left[a_{-i}\right]\right)\right)

\displaystyle \quad \quad = \frac{1}{T} \sum_{t=1}^{T} \left(u_{i} \left(ϕ\left(\mathop{\mathbb{E}}\limits_{a_{i} \sim x_{i}^{\left(t\right)}} \left[a_{i}\right]\right), \mathop{\mathbb{E}}\limits_{a_{-i} \sim ⊗ x_{-i}^{\left(t\right)}} \left[a_{-i}\right]\right) - u_{i} \left(\mathop{\mathbb{E}}\limits_{a_{i} \sim x_{i}^{\left(t\right)}} \left[a_{i}\right], \mathop{\mathbb{E}}\limits_{a_{-i} \sim ⊗ x_{-i}^{\left(t\right)}} \left[a_{-i}\right]\right)\right)

\displaystyle \quad \quad = \frac{1}{T} \sum_{t=1}^{T} \left(u_{i} \left(ϕ\left(x_{i}^{\left(t\right)}\right), x_{-i}^{\left(t\right)}\right) - u_{i} \left(x_{i}^{\left(t\right)}, x_{-i}^{\left(t\right)}\right)\right)

where the second equality follows by linearity of

\(ϕ\)

and

u_{i}

. Taking now a maximum over

ϕ \in \Phi

, and recognizing the definition of

\Phi

-regret on the right-hand side, we obtain the desired inequality.

Note that Theorem L4.11 holds for any set $\Phi$ . The approximate equilibria found this way are sometimes called approximate $\Phi$ -equilibria. In the special cases of $\Phi =$ all constant transformations, it is clear that the previous result implies convergence to the set of coarse correlated equilibria. For correlated equilibria, we need to convince ourselves that any arbitrary mapping $A \to A$ can be represented via a stochastic matrix. This is indeed the case, by constructing the matrix whose columns indicate what action is assigned to each action in $$A$$ by the mapping. (You should convince yourself!) Finally, for the case of $\Phi =$ all probability mass transportations, it is enough to note that the $\Phi$ -regret of any stochastic matrix transformations is at most $$|A|$$ times larger than the worst possible regret of a probability mass transportation between two actions.

Foundations of learning in games

L4.1 Hindsight rationality and \(\Phi\)-regret

L4.1.1 Notable choices of transformations \(\Phi\)

L4.1.2 An important special case: regret minimization

L4.2 Applications of regret minimization

L4.2.1 Learning a best response against stochastic opponents

L4.2.2 Learning a Nash equilibrium in two-player zero-sum games

L4.2.3 Proof of the minimax theorem

L4.2.4 Learning (coarse) correlated equilibria

L4.1 Hindsight rationality and $\Phi$ -regret

L4.1.1 Notable choices of transformations $\Phi$