How to cite

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

Supplementary reading S3

Learning algorithms (II)

Instructor

Prof. Gabriele Farina (gfarina@mit.edu)

Edition

Fall 2026

In recent years, there has been a lot of interest in the idea of optimism in learning algorithms. The fundamental idea behind optimism is the following:

When all players learn at the same time, the environment is nonstationary but not necessarily adversarial. Can one then take advantage of this to design learning algorithms with better regret guarantees and convergence properties?

S3.1 Predictivity, optimism, and acceleration

The idea of predictive is to anticipate the next utility gradient $g^{(t+1)}$ by having a prediction $m^{(t+1)}$ .

At least three variants can be defined.

Algorithm / variant	Update
FTRL Non-predictive	$\displaystyle x^{\left(t+1\right)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{x \in X} \left\{\left\langle \sum_{τ = 1}^{t} g^{\left(τ\right)},x \right\rangle - \frac{1}{η} ψ\left(x\right)\right\}$
FTRL Predictive	$\displaystyle x^{\left(t+1\right)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{x \in X} \left\{\left\langle {\color{#005dae}m^{\left(t+1\right)}} + \sum_{τ = 1}^{t} g^{\left(τ\right)},x \right\rangle - \frac{1}{η} ψ\left(x\right)\right\}$
OMD Non-predictive	$\displaystyle x^{\left(t+1\right)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{x \in X} \left\{\left\langle g^{\left(t\right)},x \right\rangle - \frac{1}{η} \mathord{\operatorname{D}}_{ψ} \left(x \Vert x^{\left(t\right)}\right)\right\}$
OMD Predictive / non-reflected	$\displaystyle z^{\left(t+1\right)}$ $\displaystyle \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname{max}}\limits_{z \in X} \left\{\left\langle g^{\left(t\right)},z \right\rangle - \frac{1}{η} \mathord{\operatorname{D}}_{ψ} \left(z \Vert z^{\left(t\right)}\right)\right\}$ $\displaystyle x^{\left(t+1\right)}$ $\displaystyle \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname{max}}\limits_{x \in X} \left\{\left\langle {\color{#005dae}m^{\left(t+1\right)}},x \right\rangle - \frac{1}{η} \mathord{\operatorname{D}}_{ψ} \left(x \Vert z^{\left(t+1\right)}\right)\right\}$
OMD Predictive / reflected	$\displaystyle x^{\left(t+1\right)} \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{x \in X} \left\{\left\langle g^{\left(t\right)} + {\color{#005dae}m^{\left(t+1\right)} - m^{\left(t\right)}},x \right\rangle - \frac{1}{η} \mathord{\operatorname{D}}_{ψ} \left(x \Vert x^{\left(t\right)}\right)\right\}$

While the three predictive algorithms are in general different, they coincide in the special case of Legendre regularizers (see also Lecture 5).

Remark S3.1 .

For Legendre regularizers (i.e., when

\(ψ\)

‘s gradients go to infinity at the boundary of

\(X\)

), the three predictive algorithms (FTRL, non-reflected OMD, reflected OMD) coincide.

It is also worth noting that the predictive versions of the algorithms subsume the non-predictive versions as a special case, as we point out in the next remark.

Remark S3.2 .

The standard (non-predictive) FTRL and OMD algorithms correspond to the case where the prediction is set to zero, i.e.,

m^{(t)} = 0

at all times

\(t\)

S3.1.1 Optimism

The idea of optimism is to use predictivity with the specific guess $m^{(t+1)} = g^{(t)}$ at all times $$t$$ . This corresponds to predicting that the feedback is slow-changing.

Example S3.3 (Optimistic online gradient ascent) .

The non-reflected OMD algorithm instantiated with squared Euclidean norm $ψ(x) = \frac{1}{2} \Vert x\Vert_{2}^{2}$ gives rise to the (non-reflected) optimistic online gradient ascent algorithm, whose update rule is

\displaystyle z^{\left(t+1\right)}

\displaystyle \coloneqq Π_{X}\left(z^{\left(t\right)} + η g^{\left(t\right)}\right), \quad \quad \quad \quad x^{\left(t+1\right)}\coloneqq Π_{X}\left(z^{\left(t+1\right)} + η g^{\left(t\right)}\right).

(1)

Example S3.4 (Optimistic MWU) .

For the MWU algorithm, the optimistic version of FTRL, non-reflected OMD, and reflected OMD all coincide, and give rise to the following update rule:

\displaystyle x^{\left(t+1\right)} ∝ \operatorname{exp}\left(η r^{\left(t\right)} + η \left({\color{#000000}r^{\left(t\right)} - r^{\left(t-1\right)}}\right)\right).

In two-player games, optimism serves as a form of negative momentum that pushes the iterates towards the equilibrium. We illustrate this in the following example. We will give a quantitative analysis of the effect of optimism in the convergence of learning algorithms in Section S3.2.

Example S3.5 .

The following plots show the dynamics of the optimistic and non-optimistic versions of MWU and OGD in the small two-player zero-sum game we used in Lecture 5, whose utility matrix is

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

The multiplicative weights update algorithm was set up with constant learning rate

\(η = 0.25\)

, while the online gradient descent algorithm was set up with learning rate

\(η = 0.1\)

The optimistic version of online projected gradient descent (OGD) was non-reflected. The purple dot indicates the starting strategy. The gray dotted line tracks the profile of average strategies.

As mentioned, the optimistic dynamics exhibit a “push” towards equilibrium, due to the negative momentum effect, which results in convergence towards the unique Nash equilibrium

\displaystyle x^{∗}

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

\displaystyle y^{∗}

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

S3.1.2 Predictive regret bounds (RVU)

Intuitively, one would expect that predictions help in reducing the regret of the learning algorithm. At one extreme, one would presumably hope that if the prediction is perfect, then the regret would be very small. This is indeed the case, as shown by Syrgkanis, Agarwal, Luo and Schapire [SALS15[SALS15] Syrgkanis, V., Agarwal, A., Luo, H., & Schapire, R. E. (2015). Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems (NeurIPS), 28.].

Theorem S3.6 (RVU bound, [SALS15]) .

Predictive FTRL and Predictive OMD satisfy the following regret bound, which is often called RVU bound (regret bounded by variation in utilities):

\displaystyle \text{Reg}^{\left(T\right)} \le \operatorname*{max}_{\hat{x} \in X}\frac{ψ\left(\hat{x}\right) - ψ\left(x^{\left(1\right)}\right)}{η} + η \sum_{t=1}^{T} \left\Vert g^{\left(t\right)} - m^{\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

Remark S3.7 .

A consequence of the previous regret bound is the fact that—assuming

m^{(t)} = g^{(t)}

is omniscent—the regret of the learning algorithm does not grow with time.

S3.1.3 Accelerated learning of Nash equilibria in two-player zero-sum games

As noted by [SALS15], the RVU bound implies accelerated convergence to Nash equilibria in two-player zero-sum games. The proof is quite elementary, and we present it next.

Theorem S3.8 (Accelerated convergence to Nash equilibria in two-player zero-sum games, [SALS15]) .

Consider any two-player zero-sum game; let $\mathord{\operatorname{U}}_{1} \in \mathbb{R}^{m \times n}$ be the utility matrix for Player 1. If the players employ regret minimizers that guarantee RVU regret bounds of the form

\displaystyle \text{Reg}_{1}^{\left(T\right)}

\displaystyle \le \frac{\Omega_{1}}{η} + η \sum_{t=1}^{T} \left\Vert \mathord{\operatorname{U}}_{1} \left(y^{\left(t\right)} - y^{\left(t-1\right)}\right)\right\Vert_{∗}^{2} - \frac{1}{8 η} \sum_{t=1}^{T} \left\Vert x^{\left(t\right)} - x^{\left(t-1\right)}\right\Vert^{2}

\displaystyle \text{Reg}_{2}^{\left(T\right)}

\displaystyle \le \frac{\Omega_{2}}{η} + η \sum_{t=1}^{T} \left\Vert \mathord{\operatorname{U}}_{1}^{\top} \left(x^{\left(t\right)} - x^{\left(t-1\right)}\right)\right\Vert_{∗}^{2} - \frac{1}{8 η} \sum_{t=1}^{T} \left\Vert y^{\left(t\right)} - y^{\left(t-1\right)}\right\Vert^{2},

and $η \le 1/(4 \Vert \mathord{\operatorname{U}}_{1}\Vert_{\text{op}})$ , where $\Vert \mathord{\operatorname{U}}_{1}\Vert_{\text{op}} \coloneqq \operatorname*{max}_{z \in \mathbb{R}^{n}} \Vert \mathord{\operatorname{U}}_{1} z\Vert_{∗} / \Vert z\Vert$ is the operator norm of $\mathord{\operatorname{U}}_{1}$ , then, at any time $$T$$ , the sum of the regrets of the players satisfies the bound

\displaystyle \text{Reg}_{1}^{\left(T\right)} + \text{Reg}_{2}^{\left(T\right)} \le \frac{\Omega_{1} + \Omega_{2}}{η}

which is constant with respect to time. This immediately implies convergence to the set of Nash equilibria in two-player zero-sum games at the rate of

O_{T} (1/T)

Proof.

The statement follows from summing up the RVU bounds, and observing that the middle terms cancel out with the right-most terms. More precisely, we have

\displaystyle \text{Reg}_{1}^{\left(T\right)}

\displaystyle \le \frac{\Omega_{1}}{η} + η \left\Vert \mathord{\operatorname{U}}_{1}\right\Vert_{\text{op}} \sum_{t=1}^{T} \left\Vert y^{\left(t\right)} - y^{\left(t-1\right)}\right\Vert_{∗}^{2} - \frac{1}{8 η} \sum_{t=1}^{T} \left\Vert x^{\left(t\right)} - x^{\left(t-1\right)}\right\Vert^{2}

\displaystyle \text{Reg}_{2}^{\left(T\right)}

\displaystyle \le \frac{\Omega_{2}}{η} + η \left\Vert \mathord{\operatorname{U}}_{1}\right\Vert_{\text{op}} \sum_{t=1}^{T} \left\Vert x^{\left(t\right)} - x^{\left(t-1\right)}\right\Vert_{∗}^{2} - \frac{1}{8 η} \sum_{t=1}^{T} \left\Vert y^{\left(t\right)} - y^{\left(t-1\right)}\right\Vert^{2}

Summing the inequalities and using the fact that $η \le 1/4 \Vert \mathord{\operatorname{U}}_{1}\Vert_{\text{op}}$ by assumption, we obtain the statement.

S3.1.4 Accelerated learning of coarse correlated equilibria in general games

Rates of $\tilde{O}(1/T)$ for coarse correlated and correlated equilibria (CCE) via learning in normal-form games (and beyond) are also known for the multiplayer case, but they are significantly harder to prove. One of the main obstacles is due to the fact that convergence to CCE is driven by the maximum of the regrets of the players, and not the sum as in two-player zero-sum Nash equilibria.

We mention some of the results in this direction.

Syrgkanis, Agarwal, Luo and Schapire [SALS15] showed $O(n \operatorname{log} |A| T^{-\frac{3}{4}})$ for OMWU using RVU bounds.
This result was later improved by Chen and Peng [CP20[CP20] Chen, X., & Peng, B. (2020). Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33, 18990–18999.] to $O(n \operatorname{log}^{\frac{5}{6}} |A| T^{-\frac{5}{6}})$ for two-player general-sum games only.
Daskalakis, Fishelson and Golowich [DFG21[DFG21] Daskalakis, C., Fishelson, M., & Golowich, N. (2021). Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34, 27604–27616.] showed $O(n \operatorname{log} |A| \frac{\operatorname{log}^{4} T}{T})$ convergence for OMWU using a very complicated analysis based on the idea of high-order stability.
Farina, Anagnostides, Luo, Lee, Kroer and Sandholm [FAL+22[FAL+22] Farina, G., Anagnostides, I., Luo, H., Lee, C.-W., Kroer, C., & Sandholm, T. (2022). Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35, 39076–39089.] showed $O(n |A| \frac{\operatorname{log} T}{T})$ convergence rates using RVU bounds paired with a special regularizer.

S3.2 Convergence in iterates

The convergence results we have seen so far pertain to the average strategies (either individual, or the average of the product) produced by learning dynamics. One might then wonder what is known about the iterate convergence to equilibrium.

Complexity-theoretic considerations regarding the hardness of approximating Nash equilibria preclude this phenomenon beyond two-player zero-sum games. As we now argue, in two-player zero-sum games the phenomenon is indeed possible.

Best-iterate convergence. Anagnostides, Panageas, Farina and Sandholm [APFS22[APFS22] Anagnostides, I., Panageas, I., Farina, G., & Sandholm, T. (2022). On Last-Iterate Convergence Beyond Zero-Sum Games. International Conference on Machine Learning.] showed that when both players use optimistic gradient ascent, the best iterate converges to the Nash equilibrium in two-player zero-sum games at the rate of $O_{T} (1/\sqrt{T})$ . At a high level, the proof of this result is in two steps. First, the authors show that the sum of the squared distances between consecutive iterates is bounded by a constant. This implies that at least one iterate is close to the previous one. Second, they show that small simultaneous movements imply proximity to a Nash equilibrium. Both of these steps require only elementary calculations; feel free to try to reproduce the result yourself or check the details in the original paper.

Last-iterate convergence. Cai, Oikonomou and Zheng [COZ22[COZ22] Cai, Y., Oikonomou, A., & Zheng, W. (2022). Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games. Advances in Neural Information Processing Systems (NeurIPS), 35.] improved the best-iterate result mentioned above by showing last iterate converges to the Nash equilibrium at the rate of $O_{T} (1/\sqrt{T})$ for optimistic OGD. Their analysis is significantly more involved, and revolves around studying a Lyapunov potential function that was discovered via semidefinite programming.

Both of the results mentioned above pertain to optimistic OGD.

Arguably, it was believed for a while in the community that good last-iterate convergence of OMWU were in the air, just “one good trick” away. After all, OMWU had always spoiled us with its good properties. Furthermore, the paper by Hsieh, Antonakopoulos and Mertikopoulos [HAM21[HAM21] Hsieh, Y.-G., Antonakopoulos, K., & Mertikopoulos, P. (2021). Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. Conference on Learning Theory, 2388–2422.] showed asymptotic (i.e., in the limit, but without any concrete rates) convergence of optimistic MWU to the set of equilibria in two-player zero-sum games. So, it seemed pretty likely that good, concrete rates of convergence could be established beyon optimistic gradient ascent. However, in a recent twist, it was shown that the sitution is less rosy than expected. We illustrate this with an example.

Example S3.9 (Poor last-iterate convergence of FTRL, [CFG+24[CFG+24] Cai, Y., Farina, G., Grand-Clément, J., Kroer, C., Lee, C.-W., Luo, H., & Zheng, W. (2024). Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms. Arxiv. link]) .

Consider the two-player zero-sum game with utility matrix for Player 1 given by

\displaystyle \mathord{\operatorname{U}}_{1}\left(\delta \right) \coloneqq \begin{pmatrix}\nicefrac{1}{2} + \delta & \nicefrac{1}{2} \\ 0 & 1\end{pmatrix}.

The game admits the unique Nash equilibrium $(x^{∗}, y^{∗})$ , where

\displaystyle x^{∗} = \left(\frac{1}{1+\delta}, \frac{\delta}{1+\delta}\right) \quad \quad \text{and} \quad \quad y^{∗} = \left(\frac{1}{2\left(1+\delta \right)}, \frac{1+2\delta}{2\left(1+\delta \right)}\right).

In particular, when $\delta$ is small, the equilibrium strategy for Player 1 is approximately $x^{∗} = (1 - \delta , \delta )$ and thus very close to the boundary of the strategy polytope of the player. This proximity to the boundary affects the performance of all known instantiations of the the optimistic FTRL algorithm. To see this numerically, the next four plots show the evolution of three optimistic FTRL variants (entropic, Euclidean, and logarithmic) and the optimistic gradient ascent algorithm, in the game defined by $\delta = 10^{-2}.$

The dynamics for the the first two algorithms get extremely close to the boundary—for example, when using OMWU, iterates reached strategies with $1 - e^{-50} < x_{1} < 1$ .

By studying the dynamics produced by instantiations of the FTRL algorithm in the previous game, the following result can be established.

Theorem S3.10 (Informal, [CFG+24]) .

Under standard assumptions about the regularizer, there is no function

\(f\)

such that optimistic FTRL produces a last-iterate convergence rate of

f(|A_{1}|, |A_{2}|, T) \to 0

when all payoffs of the game are in [0, 1], and

|A_{1}|

and

|A_{2}|

are the number of actions of the players. In other words, the last-iterate convergence rate must depend on some form of condition number of the game.

Bibliography for this lecture

[SALS15]	Syrgkanis, V., Agarwal, A., Luo, H., & Schapire, R. E. (2015). Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems (NeurIPS), 28.
[CP20]	Chen, X., & Peng, B. (2020). Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33, 18990–18999.
[DFG21]	Daskalakis, C., Fishelson, M., & Golowich, N. (2021). Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34, 27604–27616.
[FAL+22]	Farina, G., Anagnostides, I., Luo, H., Lee, C.-W., Kroer, C., & Sandholm, T. (2022). Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35, 39076–39089.
[APFS22]	Anagnostides, I., Panageas, I., Farina, G., & Sandholm, T. (2022). On Last-Iterate Convergence Beyond Zero-Sum Games. International Conference on Machine Learning.
[COZ22]	Cai, Y., Oikonomou, A., & Zheng, W. (2022). Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games. Advances in Neural Information Processing Systems (NeurIPS), 35.
[HAM21]	Hsieh, Y.-G., Antonakopoulos, K., & Mertikopoulos, P. (2021). Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. Conference on Learning Theory, 2388–2422.
[CFG+24]	Cai, Y., Farina, G., Grand-Clément, J., Kroer, C., Lee, C.-W., Luo, H., & Zheng, W. (2024). Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms. Arxiv. `https://doi.org/10.48550/arXiv.2406.10631`