L04: Learning in games

Foundations

Gabriele Farina

MIT 6.7980 · Topics in Multiagent Learning · Fall 2026

1 / 27

Can learning lead to equilibrium?

Can equilibrium arise from natural

dynamics of learning agents?

It depends on what “arise” means—and whether the agents are good enough.

However: the answer is surprisingly positive

Suitable notions of equilibrium can be extracted efficiently, no matter the number of players, actions, whether the game is simultaneous or sequential, etc.

This is despite the fact that multiagent learning can give rise to formally chaotic dynamics.

2 / 27

How do we formalize learning?

1. Interaction model At every round

Choose a strategy

→

Observe feedback

→

Update

Next round:

2. Quality metric: How do we measure if a “learner is learning”?

Consider that everything is nonstationary: no fixed objective to optimize once and for all...

3 / 27

Interaction model: what can the agent do and see?

Several choices to make:

Strategy

One action

* Distribution

→

Feedback

Expected utility of the played distribution Single real number

* Utility of every action (counterfactuals) Entire loss function; equivalently, vector of values for each of the actions the learner can pick

* Full-information model

The simplest model; directly tied to convex optimization; the basis for more complicated settings.

Good news: sampling and utility estimation reduce the other models to this core.

4 / 27

The full-information model: Notation

	Strategy set Nonempty, convex, compact; for normal-form games, .
	Our choice at round Chosen using the feedback from earlier rounds.
	Utility function at round Our utility is .

Full information: observe the whole utility function

Choose , then observe , then update for round .

5 / 27

Normal-form games: linear utility

In normal-form games the utility is linear in the learner’s strategy

Example (RPS): . Our distribution is ; the opponent’s is .

Our payoff matrix

What feedback is revealed?

We give via its gradient:

6 / 27

Bandit feedback? (L06)

Bandit feedback: observe only the utility of what we played

One number ; the utilities of counterfactual alternatives are hidden.

L06 bandit reduction: observed utility enters a gradient estimator, which supplies a full-information regret minimizer; exploration and strategy sampling produce the played strategy.

Idea: Estimate a utility vector from the observed utility, then feed the estimate to the learner.

7 / 27

The notion of regret

Consider this scenario:

Can you say you learned if, looking back at the history of play, you wish you could throw out everything you’ve done, and stick to one time-independent strategy instead?

Regret

should not grow too large (to be defined later...)

8 / 27

Φ-Regret

External regret is a very basic desideratum: a bare minimum.

“We should not wish to go back and throw out everything.”

How about more fine-grained changes?

Can you say you learned if, looking back at the history of play, you wish you could apply one deterministic transformation to everything you’ve done, and do substantially better?

9 / 27

A framework: Φ-regret

10 / 27

External regret

Constant replacement: discard the input strategy. Here, always rock.

Theorem · Equilibrium approximation

Average joint play is an -CCE, with .

Two-player zero-sum: average strategies have Nash gap .

11 / 27

Internal regret

One action-to-action switch: move all mass from to ; leave the rest unchanged.

Theorem · Computing a correlated equilibrium

Average joint play is an -CE, with .

12 / 27

Swap regret

A replacement for every action: allow all stochastic maps of the simplex.

I.e., is column-stochastic. Column of gives the replacement distribution for action .

Theorem · Computing a correlated equilibrium

Average joint play is an -CE, with .

13 / 27

Trigger deviations in sequential games

Connections between regret and equilibria go well beyond normal-form games.

Example: Sequential games.

Follow recommendations until the trigger; then switch to a fixed continuation plan.

Trigger regret → extensive-form correlated equilibrium

Average correlated play is an -EFCE, with .

14 / 27

Sublinear regret is enough

In light of the previous connections,

The goal of a “regret minimizer”

Any nontrivial regret guarantee is already interesting. (Say, even or is enough asymptotically.)

A natural goal is then to make sure that

15 / 27

The surprising might of external regret

16 / 27

From external regret to Φ-regret

External regret “feels” like such a weak notion of rationality: just make sure you stay competitive with throwing out everything and use a fixed strategy...

Surprising fact

General -regret can be reduced to external regret (albeit on a more complex space) by a beautiful construction of Gordon, Greenwald, and Marks (2008).

Idea: Embed an external regret minimizer on and a fixed-point oracle.

Gordon–Greenwald–Marks reduction: a Phi-regret minimizer contains utility construction, an external regret minimizer over transformations Phi, and a fixed-point oracle that outputs x equal to phi of x.

17 / 27

The minimax theorem

Cool fact!

The existence of no-regret algorithms is enough to prove the minimax theorem (under the hypotheses we saw last time). Bonus: it proves it constructively. It teaches us how to construct an offense strategy from defense strategies.

Let a regret minimizer play against an opponent who best responds each round.

18 / 27

Part I: Weak duality

Let

The -player plays offense

1. chooses

→

2. responds

The -player plays defense

1. chooses

→

2. responds

von Neumann’s minimax theorem guarantees .

1. The direction is free. No smart construction is needed. Why?

2. Idea: In , the -player can always reuse the commitment that guarantees .

3. Let be a maximizer in . Then

19 / 27

Part II: Strong duality via regret

Interesting direction (strong duality): .

Claim: is an offense strategy (i.e., approximate solution to ), and satisfies

I. The no-regret -learner receives utility . Hence,

II. Divide by and rearrange:

Concluding the proof. The last step comes from . Why is that true?

Hence: Strong duality

. Letting , we conclude .

20 / 27

External regret learns best responses

A basic sanity check: when the environment is static, learning should exploit it. (Multiagent learning extends single-agent learning)

Against stationary stochastic opponents, a no-external-regret learner guarantees that

is a best response.

21 / 27

Proof sketch

Idea of the proof

If opponents play according to , .

So:

22 / 27

Zero-sum self-play

Self-play at each round: two regret minimizers produce strategies, receive utility feedback determined by the other player's strategy, and update for the next round.

The Nash gap of average play

is the sum of unilateral deviation gains; exactly at Nash.

23 / 27

Any no-regret learners: convergence of averages

Blanket guarantee for averages

Any pair of no-regret learners works.

Remark: the theorem refers to the average of strategies, not the last strategy.

24 / 27

Last-iterate convergence

With more structure, stronger conclusions

Suitable optimistic dynamics also make the current strategies converge in zero-sum games. (See S04)

25 / 27

Proof sketch

Idea: write regret guarantees for the two players and sum

26 / 27

Coarse correlated equilibrium

For any number of players and actions

External regret leads to coarse correlated equilibrium

Sublinear external regret for every player makes the average joint distribution approach CCE.

27 / 27