How to cite

@misc{mit-multiagent-learning-lecture-5,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Lecture 5: Learning algorithms (I)},
  booktitle = {MIT Topics in Multiagent Learning Lecture Notes},
  note = {MIT 6.7980, Fall 2026},
  year = {2026},
  url = {https://www.mit.edu/~6.7980/learning1.html}
}

Lecture 5

Learning algorithms (I)

Instructor

Prof. Gabriele Farina (gfarina@mit.edu)

Lecture date

Tue, Sep 29, 2026

In Lecture 4 we have mentioned how no-external-regret dynamics recover several solution concepts of interest, including Nash equilibria in two-player zero-sum games, normal-form coarse-correlated equilibria in multiplayer general-sum games, and more generally convex-concave saddle point problems.

In this lecture, we begin exploring how no-external-regret dynamics can be constructed, starting from normal-form games.

L5.1 No-regret algorithms for normal-form games

For a player in normal-form games the strategy space corresponds to the probability simplex $\Delta (A)$ of all distributions over the actions available to the player. As a reminder, constructing a regret minimizer for $\Delta (A)$ means that we need to build a mathematical object that supports two operations:

NextStrategy() asks the regret minimizer to output the next strategy, which is a point $x^{(t)} \in \Delta (A)$ ;
ObserveUtility $(u^{(t)})$ provides the environment’s feedback to the regret minimizer, in the form of a utility function $u^{(t)}$ . For today, we will focus on a case of particular relevance for normal-form games: the case of linear utilities (as such are the utilities in a normal-form game). In particular, to fix notation, we will let

$\displaystyle u^{\left(t\right)} : x \mapsto \left\langle g^{\left(t\right)},x \right\rangle ,$

where $g^{(t)} \in \mathbb{R}^{n}$ is the vector that defines the linear function (called with the letter $$g$$ to suggest the idea of it being the “gradient vector”) and $\left\langle ⋅,⋅ \right\rangle$ denotes the standard dot product. Since the utility in the game cannot be unbounded, we assume that the $g^{(t)}$ can be arbitrary but bounded in norm.

In this notation, the (external) regret is defined as the quantity

\displaystyle \text{Reg}^{\left(T\right)} \coloneqq \operatorname*{max}_{\hat{x} \in \Delta \left(A\right)} \left\{\sum_{t=1}^{T} \left\langle g^{\left(t\right)},\hat{x} \right\rangle - \left\langle g^{\left(t\right)},x^{\left(t\right)} \right\rangle \right\}.

Our goal is to make sure that the regret grows sublinearly in $$T$$ no matter the utility vectors $g^{(t)}$ chosen by the environment.

General principle. Most algorithms known today for the task operate by prioritizing actions based on how much regret they have incurred. In particular, a key quantity to define modern algorithms is the vector of cumulated actions regrets

\displaystyle r^{\left(t\right)} \coloneqq \sum_{τ=1}^{t} \left(g^{\left(τ\right)} - \left\langle g^{\left(τ\right)},x^{\left(τ\right)} \right\rangle \mathbf{1}\right).

(Note that

\text{Reg}^{(t)} = \operatorname*{max}_{a \in A} r_{a}^{(t)}

.) The natural question is: how to prioritize?

L5.1.1 Follow-the-leader

Perhaps the most natural idea would be to always play the action with the highest cumulated regret (breaking ties, say, lexicograpsically). After all, this is the action we wish the most we had played in the past. This algorithm is called follow-the-leader (FTL). Unfortunately, this idea is known not to work. To see that, consider the following sequence of gradient vectors:

\displaystyle g^{\left(1\right)} = \vec{}, \quad g^{\left(2\right)} = \vec{}, \quad g^{\left(3\right)} = \vec{}, \quad g^{\left(4\right)} = \vec{}, \quad g^{\left(5\right)} = \vec{}, \quad \text{etc.}

In this case, at time $$1$$ , we pick the first action and score a utility of 0. We then compute $r^{(1)} = (0, 1/2)$ and at time $$t=2$$ pick the second action since it has the highest regret. This results in a score of 0 and an updated regret vector $r^{(2)} = (1, 1/2)$ So, at time $$t=3$$ , we will pick the first action, resulting again in a score of 0 and an updated regret $r^{(3)} = (1, 3/2)$ and so on… Overall, it’s easy to see that in all this jumping around, the regrets grow linearly.

Where to go from here? A few ideas seem natural:

We can replace picking the action with the highest regret with picking actions proportionally to their regret; this leads to the algorithm called Regret Matching, which we will discuss in Section L5.1.2.
We can smooth out the maximum operator by using the softmax function. This leads to the multiplicative weights update algorithm, which we will discuss in Section L5.1.4.
We can regularize the maximum operator by adding a term that penalizes large jumps in the strategy space. This leads to a very flexible algorithm called follow-the-regularized-leader algorithm, which we will discuss in Section L5.2 as well as in the next lecture.

All these ideas work. Before we move on, though, it is worth knowing that—while flawed—the follow-the-leader algorithm is not completely hopeless.

Remark L5.1 (Fictitious play) .

In the canonical learning setup (see Lecture 4), the use of follow-the-leader by all players goes under the name of fictitious play [Bro49[Bro49] Brown, G. W. (1949). Some notes on computation of games solutions. Rand Corporation.] [Bro51[Bro51] Brown, G. W. (1951). Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1), 374.]. In certain classes of games, including two-player zero-sum games, fictitious play is able to recover a Nash equilibrium, albeit with a potentially exponentially slow convergence rate [Rob51[Rob51] Robinson, J. (1951). An iterative method of solving a game. Annals of Mathematics, 54(2), 296–301. link].

L5.1.2 The Regret Matching (RM) algorithm

The Regret Matching algorithm [HM00[HM00] Hart, S., & Mas-Colell, A. (2000). A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica, 68(5), 1127–1150. link] picks probabilities proportional to the “ReLU” of the cumulated regrets, that is,

\displaystyle x^{\left(t+1\right)} ∝ \left[r^{\left(t\right)}\right]^{+}

(1)

whenever $[r^{(t)}]^{+} \ne 0$ , and an arbitrary point otherwise.

The algorithm is presented in pseudocode in Algorithm 1.

Regret Matching

r^{(0)} ← 0 \in \mathbb{R}^{A}, \quad x^{(0)} ← \mathbf{1}/|A| \in \Delta (A)

function NextStrategy()

[r^{(t-1)}]^{+} \ne 0

return

x^{(t)} ← \frac{[r^{(t-1)}]^{+}}{\Vert [r^{(t-1)}]^{+}\Vert_{1}}

else

return

x^{(t)} ←

any point in

\Delta (A)

function ObserveUtility(

g^{(t)}

)

r^{(t)} ← r^{(t-1)} + g^{(t)} - \left\langle g^{(t)},x^{(t)} \right\rangle \mathbf{1}

Regret Matching⁺

r^{(0)} ← 0 \in \mathbb{R}^{A}, \quad x^{(0)} ← \mathbf{1}/|A| \in \Delta (A)

function NextStrategy()

[r^{(t-1)}]^{+} \ne 0

return

x^{(t)} ← \frac{[r^{(t-1)}]^{+}}{\Vert [r^{(t-1)}]^{+}\Vert_{1}}

else

return

x^{(t)} ←

any point in

\Delta (A)

function ObserveUtility(

g^{(t)}

)

r^{(t)} ← [r^{(t-1)} + g^{(t)} - \left\langle g^{(t)},x^{(t)} \right\rangle \mathbf{1}]^{+}

Theorem L5.2 (Regret bound for RM) .

The Regret Matching algorithm (Algorithm 1) is an external regret minimizer, and satisfies the regret bound $\text{Reg}^{(T)} \le \Omega (\sqrt{T})$ , where $\Omega$ is the maximum norm of $\Vert g^{(t)} - \left\langle g^{(t)},x^{(t)} \right\rangle \mathbf{1}\Vert_{2}$ up to time $$T$$ .

In particular, if all the gradient vectors satisfy $\Vert g^{(t)}\Vert_{∞} \le 1$ at all times $$t$$ then the regret satisfies

\displaystyle \text{Reg}^{\left(T\right)} \le \sqrt{T ⋅ \left|A\right|}.

Proof.

We start by observing that, at all times $$t$$ ,

\displaystyle \left(g^{\left(t+1\right)} - \left\langle g^{\left(t+1\right)},x^{\left(t+1\right)} \right\rangle \mathbf{1}\right)^{\top} x^{\left(t+1\right)} = 0

(this is always true, not just for Regret Matching). Plugging in the definition (1) of how $x^{(t+1)}$ is constructed, we therefore conclude that

\displaystyle \left(g^{\left(t+1\right)} - \left\langle g^{\left(t+1\right)},x^{\left(t+1\right)} \right\rangle \mathbf{1}\right)^{\top} \left[r^{\left(t\right)}\right]^{+} = 0.

(2)

(Note that the above equation holds trivially when $[r^{(t)}]^{+}=0$ and therefore $x^{(t+1)}$ is picked arbitrarily.)

Now, we use the inequality

\displaystyle \left\Vert \left[a + b\right]^{+}\right\Vert_{2}^{2} \le \left\Vert \left[a\right]^{+} + b\right\Vert_{2}^{2},

applied to $a = r^{(t)}$ and $b = g^{(t+1)} - \left\langle g^{(t+1)},x^{(t+1)} \right\rangle \mathbf{1}$ . In particular, since by definition $a + b = r^{(t+1)}$ , we have

\displaystyle \left\Vert \left[r^{\left(t+1\right)}\right]^{+}\right\Vert_{2}^{2}

\displaystyle \le \left\Vert \left[r^{\left(t\right)}\right]^{+} + \left(g^{\left(t+1\right)} - \left\langle g^{\left(t+1\right)},x^{\left(t+1\right)} \right\rangle \mathbf{1}\right)\right\Vert_{2}^{2}

\displaystyle = \left\Vert \left[r^{\left(t\right)}\right]^{+}\right\Vert_{2}^{2} + \left\Vert g^{\left(t+1\right)} - \left\langle g^{\left(t+1\right)},x^{\left(t+1\right)} \right\rangle \mathbf{1}\right\Vert_{2}^{2} + 2 \left(g^{\left(t+1\right)} - \left\langle g^{\left(t+1\right)},x^{\left(t+1\right)} \right\rangle \mathbf{1}\right)^{\top} \left[r^{\left(t\right)}\right]^{+}

\displaystyle = \left\Vert \left[r^{\left(t\right)}\right]^{+}\right\Vert_{2}^{2} + \left\Vert g^{\left(t+1\right)} - \left\langle g^{\left(t+1\right)},x^{\left(t+1\right)} \right\rangle \mathbf{1}\right\Vert_{2}^{2} \hspace{127.56pt} \left(\text{from} \left(2\right)\right)

\displaystyle \le \left\Vert \left[r^{\left(t\right)}\right]^{+}\right\Vert_{2}^{2} + \Omega^{2}.

Hence, by induction we have

\displaystyle \left\Vert \left[r^{\left(T\right)}\right]^{+}\right\Vert_{2}^{2} \le T \Omega^{2},

which implies

\displaystyle \text{Reg}^{\left(T\right)} = \operatorname*{max}_{a \in A} r_{a}^{\left(T\right)} \le \operatorname*{max}_{a \in A} \left[ r_{a}^{\left(T\right)} \right]^{+} \le \left\Vert \left[r^{\left(T\right)}\right]^{+}\right\Vert_{2} \le \Omega \sqrt{T}.

The proof of the first part is then complete. The second part then just follows from using the inequality

\displaystyle \Omega \le \left\Vert g^{\left(t\right)} - \left\langle g^{\left(t\right)},x^{\left(t\right)} \right\rangle \mathbf{1}\right\Vert_{2} \le \left\Vert g^{\left(t\right)}\right\Vert_{2} \le \sqrt{\left|A\right|} ⋅ \left\Vert g^{\left(t\right)}\right\Vert_{∞}.

Our interest for the regret bound under the specific condition that $\Vert g^{(t)}\Vert_{∞} \le 1$ is as follows.

Remark L5.3 .

Within the canonical learning setup (see Lecture 4), the entries of

g^{(t)}

are the expected payoffs of all actions of the players. Thus, the condition

\Vert g^{(t)}\Vert_{∞} \le 1

corresponds to the condition that the game’s payoffs lie in

\([-1,1]\)

As of today, Regret Matching and its variants are still often some of the most practical algorithms for learning in games.

Remark L5.4 .

One very appealing property of the Regret Matching algorithm is its lack of hyperparameters. It just works “out of the box”.

L5.1.3 The Regret Matching⁺ (RM⁺) algorithm

The Regret Matching⁺ algorithm [Tam14[Tam14] Tammelin, O. (2014). Solving large imperfect information games using CFR+. Arxiv. link][TBJB15[TBJB15] Tammelin, O., Burch, N., Johanson, M., & Bowling, M. (2015). Solving Heads-up Limit Texas Hold'em. International Joint Conference on Artificial Intelligence (IJCAI).] is given in Algorithm 2. It differs from RM only on the last line, where a further thresholding is added. That small change has the effect that actions with negative cumulated regret (that is, “bad” actions) are treated as actions with $$0$$ regret. Hence, intuitively, if a bad action were to become good over time, it would take less time for RM⁺ to notice and act on that change. Because of that, Regret Matching⁺ has stronger practical performance and is often preferred over Regret Matching in the game solving literature.

With a simple modification to the analysis of RM, the same bound as RM can be proven.

Theorem L5.5 (Regret bound for RM⁺) .

The RM⁺ algorithm (Algorithm 2) is an external regret minimizer, and satisfies the regret bound $\text{Reg}^{(T)} \le \Omega \sqrt{T}$ , where $\Omega$ is the maximum norm $\Vert g^{(t)} - \left\langle g^{(t)},x^{(t)} \right\rangle \mathbf{1}\Vert_{2}$ up to time $$T$$ .

So again, if all the gradient vectors satisfy $\Vert g^{(t)}\Vert_{∞} \le 1$ at all times $$t$$ then the regret satisfies

\displaystyle \text{Reg}^{\left(T\right)} \le \sqrt{T ⋅ \left|A\right|}.

L5.1.4 Multiplicative weights update (MWU)

If we replace the “hard” maximum of follow-the-leader with the “soft” maximum given by

\displaystyle x_{a}^{\left(t\right)}

\displaystyle = \text{softmax}_{a\left(η r^{\left(t\right)}\right)}

\displaystyle \coloneqq \frac{\operatorname{exp}\left(η r_{a}^{\left(t\right)}\right)}{\sum_{j=1}^{m} \operatorname{exp}\left(η r^{\left(t\right)}\left[j\right]\right)},

where $$η > 0$$ is an inverse temperature parameter, then we obtain the multiplicative weights update algorithm [FS97[FS97] Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139.].

This algorithm is presented in Algorithm 3.

Multiplicative Weights Update

r^{(0)} ← 0 \in \mathbb{R}^{A}, \quad x^{(0)} ← \mathbf{1}/|A| \in \Delta (A)

function NextStrategy()

return

x^{(t)} ← \text{softmax}(η r^{(t-1)})

function ObserveUtility(

g^{(t)}

)

r^{(t)} ← r^{(t-1)} + g^{(t)} - \left\langle g^{(t)},x^{(t)} \right\rangle \mathbf{1}

Compared to RM, MWU has a different flavor: it uses softmax instead of ReLU. This change in prioritization function has a pretty significant impact on the regret bound that multiplicative weights guarantees. In particular, the following can be shown:

Theorem L5.6 (Regret bound for MWU) .

The regret cumulated by the MWU algorithm can be upper bounded as

\displaystyle \text{Reg}^{\left(T\right)} \le \frac{\operatorname{log} \left|A\right|}{η} + η \sum_{t=1}^{T} \left\Vert g^{\left(t\right)}\right\Vert_{∞}^{2} - \frac{1}{8 η} \sum_{t=2}^{T} \left\Vert x^{\left(t\right)} - x^{\left(t-1\right)}\right\Vert_{1}^{2},

no matter the sequence of gradient vectors $g^{(t)}$ chosen by the environment. In particular, if all the gradient vectors satisfy $\Vert g^{(t)}\Vert_{∞} \le 1$ at all times $$t$$ and $η = \sqrt{\operatorname{log} |A|/ T}$ , the regret satisfies

\displaystyle \text{Reg}^{\left(T\right)} \le \sqrt{T \operatorname{log} \left|A\right|}.

We will see the proof of Theorem L5.6 in the next lecture, as a reflection of a substantially more general framework.

For now, we remark a crucial aspect of MWU. Compared with the regret bound of RM and RM⁺, the regret bound of MWU has only a logarithmic dependence on the number of actions $$|A|$$ . Despite in practice RM/RM⁺ tend to outperform MWU (all while getting rid of any hyperparameter tuning), this property has profound theoretical implications, especially in combinatorial games where the effective number of actions is exponential. The gist of it is that several important classes of games can be converted into exponentially large normal-form games (this is the case of sequential games, for example). Since MWU only has logarithmic dependence on the number of actions of the resulting normal-form games, this shows that—at least ignoring computation—external regret minimization is possible with polynomial dependence on the game size even in these classes of complex, structured games.

L5.2 More general approaches: FTRL and OMD

Finally, we turn our attention to the third way of obtaining no-regret algorithms, that is, by considering a regularized (i.e., smoothed) version of the follow-the-leader algorithm discussed above. The idea is that, instead of playing by always putting 100% of the probability mass on the action with highest cumulated regret, we look for the distribution that maximizes the expected cumulated regret, minus some regularization term that prevents us from putting all the mass on a single action.

Definition L5.7 (Distance-generating function for a set) .

A differentiable function $ψ : \Delta (A) \to \mathbb{R}$ is a distance-generating function for the set $$X$$ if it is $$1$$ -strongly convex on $$X$$ , that is,

\displaystyle \left(∇ f\left(x\right) - ∇ f\left(x'\right)\right)^{\top} \left(x - x'\right) \ge \left\Vert x - x'\right\Vert^{2} \quad \quad \forall x,x' \in X

with respect to some norm

\Vert \cdot \Vert

. For the purposes of this lecture, we will also assume that the function attains minimum is in the relative interior of

\Delta (A)

L5.2.1 FTRL in the normal-form case

Definition L5.8 (FTRL, simplex case) .

Let $$ψ$$ be a distance-generating function for the strategy set $\Delta (A)$ . The follow-the-regularized-leader algorithm (FTRL; sometimes also called “regularized follow-the-leader”) defines the choice of strategy¹1In particular, $x^{(1)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{min}}\limits_{\hat{x} \in \Delta (A)} ψ(\hat{x})$ since the regrets of all actions are $$0$$ at the beginning.

\displaystyle x^{\left(t\right)}

\displaystyle \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\hat{x} \in \Delta \left(A\right)} \left\{\left\langle r^{\left(t-1\right)},\hat{x} \right\rangle - \frac{1}{η} ψ\left(\hat{x}\right)\right\}.

The regularization term $-ψ(\hat{x})$ limits the amount of variation between consecutive strategies. This makes intuitive sense: if $η \to 0$ , $x^{(t)}$ is constant (and equal to $\mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{min}}\limits_{\hat{x} \in \Delta (A)} ψ(\hat{x})$ ). When $$η = \infty$$ , we recover the follow-the-leader algorithm, where strategies can jump arbitrarily. For intermediate $$η$$ , as you might expect, the amount of variation between strategies at consecutive times is bounded above by a quantity proportional to $$η$$ :

\displaystyle \left\Vert x^{\left(t+1\right)} - x^{\left(t\right)}\right\Vert \le η \left\Vert g^{\left(t\right)}\right\Vert_{∗},

where $\Vert \cdot \Vert_{∗}$ is the dual norm of $\Vert \cdot \Vert$ .

We will see the regret bound for FTRL in the general case in Section L5.2.3.

L5.2.2 OMD in the normal-form case

The last general method that we mention today is the online mirror descent (OMD) algorithm. This is the online generalization of the mirror descent optimization method, one of the workhorses of modern optimization theory. A good way to think about OMD is as a generalization of gradient ascent.

Definition L5.9 (OMD, simplex case) .

Let $ψ : \Delta (A) \to \mathbb{R}$ be a distance-generating function. The online mirror descent algorithm (OMD) defines the choice of strategy

\displaystyle x^{\left(t\right)}

\displaystyle \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\hat{x} \in \Delta \left(A\right)} \left\{\left\langle g^{\left(t-1\right)},\hat{x} \right\rangle - \frac{1}{η} \operatorname{D}_{ψ} \left(\hat{x} \parallel x^{\left(t-1\right)}\right)\right\},

where

\displaystyle \operatorname{D}_{ψ} \left(\hat{x} \parallel x\right) \coloneqq ψ\left(\hat{x}\right) - ψ\left(x\right) - \left\langle ∇ ψ\left(x\right),\hat{x} - x \right\rangle

is called the Bregman divergence associated with

\(ψ\)

Two choices of regularizer are standard for the probability simplex:

The negative entropy function $H(x) \coloneqq \sum_{a \in A} x_{a} \operatorname{log} x_{a}$ . This is 1-strongly convex with respect to the $ℓ_{1}$ norm $\Vert \cdot \Vert_{1}$ (and therefore also with respect to $\Vert \cdot \Vert_{2}$ ). OMD instantiated with this regularizer leads to the multiplicative weights update algorithm seen in Section L5.1.4; see also Section L5.2.4.
The squared Euclidean norm $ψ(x) \coloneqq \frac{1}{2} \Vert x\Vert_{2}^{2}$ , which is 1-strongly convex with respect to the $ℓ_{2}$ norm $\Vert \cdot \Vert_{2}$ . OMD instantiated with this regularizer leads to the online projected gradient descent algorithm, which we will discuss in Section L5.2.5.

L5.2.3 The general case

FTRL and OMD apply well beyond the case of probability simplices. In fact, they can be applied to any convex and compact domain $$X$$ . In this case, the vector of regrets $r^{(t)}$ must be replaced with the cumulative gradient vector $\sum_{τ=1}^{t} g^{(τ)}$ , as follows:

Definition L5.10 (FTRL, general version) .

For a generic convex and compact domain $$X$$ , the FTRL algorithm produces strategies $x^{(t)}$ by solving the optimization problem

\displaystyle x^{\left(t\right)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\hat{x} \in X} \left\{\left\langle \sum_{τ=1}^{t-1} g^{\left(τ\right)},\hat{x} \right\rangle - \frac{1}{η} ψ\left(\hat{x}\right)\right\}.

Definition L5.11 (OMD, general version) .

The OMD algorithm produces strategies $x^{(t)}$ by solving the optimization problem

\displaystyle x^{\left(t\right)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\hat{x} \in X} \left\{\left\langle g^{\left(t-1\right)},\hat{x} \right\rangle - \frac{1}{η} \operatorname{D}_{ψ} \left(\hat{x} \parallel x^{\left(t\right)}\right)\right\}.

We also remark the following connection between the two algorithms.

Remark L5.12 .

When

\(ψ\)

is a Legendre regularizer (that is, the gradients of

\(ψ\)

go to infinity at the boundary of

\(X\)

), the OMD algorithm is equivalent to the FTRL algorithm.

We mention the following regret bound for the general case. We will mention an even more powerful result next time.

Theorem L5.13 (Regret bound for FTRL and OMD) .

The regret cumulated by the FTRL and OMD algorithms is upper bounded by

\displaystyle \text{Reg}^{\left(T\right)} \le \operatorname*{max}_{x,x' \in X}\frac{ψ\left(x'\right) - ψ\left(x\right)}{η} + η \sum_{t=1}^{T} \left\Vert g^{\left(t\right)}\right\Vert_{∗}^{2} - \frac{1}{8 η} \sum_{t=2}^{T} \left\Vert x^{\left(t\right)} - x^{\left(t-1\right)}\right\Vert^{2},

where

\Vert \cdot \Vert_{∗}

is the dual norm of

\Vert \cdot \Vert

. In particular, if the norm of the gradient vectors is bounded, then by picking learning rate

η = \frac{1}{\sqrt{T}}

, we obtain that

\text{Reg}^{(T)}

is bounded as roughly

\sqrt{T}

(a sublinear function!) at all times

\(T\)

L5.2.4 Multiplicative weights update (MWU) as a special case

Multiplicative weights update is the special case of both FTRL and OMD in which the regularizer $$ψ$$ is set to the negative entropy function

\displaystyle H\left(x\right) \coloneqq \sum_{a \in A} x_{a} \operatorname{log} x_{a}.

Example L5.14 .

The adjacent plot displays the negative entropy function in the case of

\(|A|=2\)

actions.

The negative entropy function has the following properties:

it is $$1$$ -strongly convex with respect to the $ℓ_{1}$ norm $\Vert \cdot \Vert_{1}$ ;
the maximum of the function is $$0$$ , attained at any deterministic strategy;
the minimum is attained at the uniformly random strategy

$\displaystyle \overline{x} = \left(1/m, \dots , 1/m\right),$

at which $H(\overline{x}) = m ⋅ \frac{1}{m} \operatorname{log} \frac{1}{m} = -\operatorname{log} m$ .

Plugging the bound above into the general analysis of FTRL and OMD algorithms (Theorem L5.13) yields Theorem L5.6.

L5.2.5 Online Projected Gradient Ascent

In the special case in which $ψ(x) \coloneqq \frac{1}{2} \Vert x\Vert_{2}^{2}$ , then the OMD algorithm reduces to online projected gradient ascent.

Definition L5.15 (Online projected gradient ascent) .

The online projected gradient ascent algorithm is the special case of OMD in which the regularizer is (half) the squared Euclidean norm, that is, $ψ(x) = \frac{1}{2} \Vert x\Vert_{2}^{2}$ . The choice of strategy is given by

\displaystyle x^{\left(t\right)} = \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\hat{x} \in X} \left\{\left\langle g^{\left(t-1\right)},\hat{x} \right\rangle - \frac{1}{η} \left\Vert \hat{x} - x^{\left(t-1\right)}\right\Vert_{2}^{2}\right\} = Π_{X}\left(x^{\left(t-1\right)} + η g^{\left(t-1\right)}\right).

Since the squared Euclidean norm is $$1$$ -strongly convex with respect to the $ℓ_{2}$ norm, the regret bound for OGD can be derived from the general bound for OMD (Theorem L5.13) and is as follows.

Theorem L5.16 (Regret bound for OGD) .

The regret cumulated by the OGD algorithm can be upper bounded as

\displaystyle \text{Reg}^{\left(T\right)} \le \frac{1}{η} + η \sum_{t=1}^{T} \left\Vert g^{\left(t\right)}\right\Vert_{2}^{2} - \frac{1}{8 η} \sum_{t=2}^{T} \left\Vert x^{\left(t\right)} - x^{\left(t-1\right)}\right\Vert_{2}^{2},

\displaystyle \text{Reg}^{\left(T\right)} \le \sqrt{T \left|A\right|}.

The next plots illustrate the behavior of OGD and MWU in a simple $2 \times 2$ game.

Example L5.17 .

The adjacent plots show the behavior of the online projected gradient ascent (OGD) and multiplicative weights update (MWU) algorithms in the

2 \times 2

game given by

\displaystyle U_{1} = \begin{pmatrix}2 & 1 \\ 0 & 2\end{pmatrix}.

The unique Nash equilibrium of the game is in

\displaystyle x^{∗}

\displaystyle = \left(\frac{2}{3}, \frac{1}{3}\right),

\displaystyle y^{∗}

\displaystyle = \left(\frac{1}{3}, \frac{2}{3}\right).

The purple dot indicates the starting strategy. The gray dotted line tracks the profile of average strategies, which converges to an approximate Nash equilibrium as proved in Lecture 4.

Bibliography for this lecture

[Bro49]	Brown, G. W. (1949). Some notes on computation of games solutions. Rand Corporation.
[Bro51]	Brown, G. W. (1951). Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1), 374.
[Rob51]	Robinson, J. (1951). An iterative method of solving a game. Annals of Mathematics, 54(2), 296–301. `http://www.jstor.org/stable/1969530`
[HM00]	Hart, S., & Mas-Colell, A. (2000). A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica, 68(5), 1127–1150. `http://www.jstor.org/stable/2999445`
[Tam14]	Tammelin, O. (2014). Solving large imperfect information games using CFR+. Arxiv. `https://arxiv.org/abs/1407.5042`
[TBJB15]	Tammelin, O., Burch, N., Johanson, M., & Bowling, M. (2015). Solving Heads-up Limit Texas Hold'em. International Joint Conference on Artificial Intelligence (IJCAI).
[FS97]	Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139.

Changelog

2025-10-05: Fixed typos (thanks George Cao!).
2025-11-30: Fixed typo in summation $t \to τ$ (thanks Sophie Wang!).

Notes

1In particular, $x^{(1)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{min}}\limits_{\hat{x} \in \Delta (A)} ψ(\hat{x})$ since the regrets of all actions are $$0$$ at the beginning.

Learning algorithms (I)

L5.1 No-regret algorithms for normal-form games

L5.1.1 Follow-the-leader

L5.1.2 The Regret Matching (RM) algorithm

L5.1.3 The Regret Matching+ (RM+) algorithm

L5.1.4 Multiplicative weights update (MWU)

L5.2 More general approaches: FTRL and OMD

L5.2.1 FTRL in the normal-form case

L5.2.2 OMD in the normal-form case

L5.2.3 The general case

L5.2.4 Multiplicative weights update (MWU) as a special case

L5.2.5 Online Projected Gradient Ascent

Bibliography for this lecture

Notes

L5.1.3 The Regret Matching⁺ (RM⁺) algorithm