How to cite

@misc{mit-multiagent-learning-lecture-S6,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Supplementary reading S6: Phi-regret minimization},
  booktitle = {MIT Topics in Multiagent Learning Lecture Notes},
  note = {MIT 6.7980, Fall 2026},
  year = {2026},
  url = {https://www.mit.edu/~6.7980/phi_regret.html}
}

Supplementary reading S6

Phi-regret minimization

Instructor

Max Fishelson (maxfish@mit.edu)

Edition

Fall 2026

We saw in earlier lectures the definition of $\Phi$ -regret. As we have seen, external regret minimization is a very narrow instantiation of $\Phi$ -regret minimization—perhaps the smallest sensible instantiation. Then, clearly, the problem of 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 see this general construction in Section S6.2. First, we start with an example of this principle, whose discovery predates the general construction of Section S6.2, and which happens to be a special case of it.

S6.1 Blum-Mansour’s swap regret minimization algorithm

Let’s start by considering the task of constructing a swap regret minimizer for probability simplex $X = \Delta^{n}$ over $$n$$ actions $A = \{1,\dots ,n\}$ . As we mentioned when discussing learning, when all players in a normal-form game play according to the strategies generated by such an algorithm, the average product strategy converges to the set of correlated equilibria of the game. The swap regret minimization algorithm of Blum and Mansour [BM07[BM07] Blum, A., & Mansour, Y. (2007). From external to internal regret. Journal of Machine Learning Research, 8(6).] is a simple and elegant algorithm that minimizes swap regret by starting from multiple copies of an external regret minimizer.

Recall that in swap regret minimization, the learner wants to minimize the $\Phi$ -regret with respect to the set of strategy transformations $\Phi$ represented by stochastic matrices

\displaystyle \Phi \coloneqq \left\{P = \left(p_{1} \left| \dots \right| p_{n}\right): p_{1}, \dots , p_{n} \in \Delta^{n}\right\}.

In order to construct a swap regret minimizer for $X = \Delta^{n}$ , we start with $$|A|$$ copies of an external regret minimizer for $\Delta^{n}$ , denoted by $R_{i}$ .

To compute the NextStrategy() of the swap regret minimizer, we first call the NextStrategy() of each $R_{i}$ to obtain a distribution $p_{i}^{(t)} \in \Delta^{n}$ . We will then assemble all $p_{i}^{(t)}$ into a stochastic matrix $P^{(t)}$ , and will output a fixed point

$\displaystyle x^{\left(t\right)} = P^{\left(t\right)} x^{\left(t\right)} = \sum_{i=1}^{n} x_{i}^{\left(t\right)} p_{i}^{\left(t\right)} \in \Delta^{n}.$
To compute the ObserveUtility $(u^{(t)})$ of the swap regret minimizer, we first call the ObserveUtility of each $R_{i}$ with the linear utility function

$\displaystyle v_{i}^{\left(t\right)} \coloneqq x_{i}^{\left(t\right)} u^{\left(t\right)}$

that is obtained by rescaling $u^{(t)}$ by the component $x_{i}^{(t)}$ of the last-output strategy $x^{(t)}$ .

The process can be depicted pictorially as in Figure 1.

Figure 1. Blum-Mansour’s swap regret minimization algorithm for

\Delta^{n}

We now claim that the algorithm described above is a swap regret minimizer for $\Delta^{n}$ .

Theorem S6.1 .

Let $\text{Reg}_{i}^{(T)}$ denote the regret incurred by each external regret minimizer $R_{i}$ for $\Delta^{n}$ in the Blum-Mansour construction described above. Then, the swap regret cumulated by the algorithm satisfies:

\displaystyle \text{SwapReg}^{\left(T\right)} = \sum_{i=1}^{n} \text{Reg}_{i}^{\left(T\right)}.

In particular, the swap regret grows sublinearly in

\(T\)

whenever the extenral regret minimizers

R_{i}

guarantee sublinear regret.

Proof.

By construction, the external regret incurred by each $R_{i}$ is

\displaystyle \text{Reg}_{i}^{\left(T\right)} = \operatorname*{max}_{\tilde{p}_{i} \in \Delta^{n}} \sum_{t=1}^{T} \left(v^{\left(t\right)}\left(\tilde{p}_{i}\right) - v^{\left(t\right)}\left(p_{i}^{\left(t\right)}\right)\right).

(1)

Pick any $\hat{P} = (\hat{p}_{1} | \dots | \hat{p}_{n}) \in \Phi$ . Then, the swap regret cumulated compared to always transforming strategies according to $\hat{P}$ is, by definition,

\displaystyle \sum_{t=1}^{T} u^{\left(t\right)}\left(\hat{P} x^{\left(t\right)}\right) - u^{\left(t\right)} \left(x^{\left(t\right)}\right)

\displaystyle \hspace{28.35pt}= \sum_{t=1}^{T} u^{\left(t\right)}\left(\hat{P} x^{\left(t\right)}\right) - u^{\left(t\right)} \left(P^{\left(t\right)} x^{\left(t\right)}\right)\quad \quad \quad \quad \left(x^{\left(t\right)} = P^{\left(t\right)} x^{\left(t\right)}\right)

\displaystyle \hspace{28.35pt}= \sum_{t=1}^{T} \left[\left(\sum_{i=1}^{n} x_{i}^{\left(t\right)} u^{\left(t\right)}\left(\hat{p}_{i}\right)\right) - \left(\sum_{i=1}^{n} x_{i}^{\left(t\right)} u^{\left(t\right)}\left(p_{i}^{\left(t\right)}\right)\right)\right]\left(\text{linearity of} u^{\left(t\right)}\right)

\displaystyle \hspace{28.35pt}= \sum_{t=1}^{T} \left(\sum_{i=1}^{n} v_{i}^{\left(t\right)}\left(\hat{p}_{i}\right) - v_{i}^{\left(t\right)}\left(p_{i}^{\left(t\right)}\right)\right)\left(\text{definition of} v_{i}^{\left(t\right)}\right)

\displaystyle \hspace{28.35pt}= \sum_{i=1}^{n} \left(\sum_{t=1}^{T} v_{i}^{\left(t\right)}\left(\hat{p}_{i}\right) - v_{i}^{\left(t\right)}\left(p_{i}^{\left(t\right)}\right)\right)\hspace{-42.52pt} \left(\text{switching summation order}\right)

\displaystyle \hspace{28.35pt}\le \sum_{i=1}^{n} \text{Reg}_{i}^{\left(T\right)}.\left(\text{from} \left(1\right)\right)

Taking a maximum over all

\hat{P} \in \Phi

gives equality: each column

\hat{p}_{i}

can be chosen independently in

\Delta^{n}

to attain the corresponding external-regret maximum. This concludes the proof.

S6.2 The general case: Gordon-Greenwald-Marks’s reduction

Blum-Mansour’s swap regret minimization algorithm is a special case of a much more general construction. Gordon, Greenwald and Marks [GGM08[GGM08] Gordon, G. J., Greenwald, A., & Marks, C. (2008). No-regret learning in convex games. Proceedings of the 25th International Conference on Machine Learning, 360–367.] show that $\Phi$ -regret minimization for a strategy set $$X$$ can be constructed starting from the following two ingredients:

an external regret minimization for the set $\Phi$ ; and
a fixed point oracle $\Phi$ , that is, an algorithm that given any $ϕ \in \Phi$ outputs a fixed point $ϕ(x) = x \in X$ .

Intuitively, the external regret minimizer for $\Phi$ has the role of tracking which transformation $$ϕ$$ the decision maker should focus on at each time. The linear utility function $U^{(t)} : \Phi \to \mathbb{R}$ observed by the external regret minimizer is constructed from the last-output strategy $x^{(t)}$ and the utility function $u^{(t)}$ observed at time $$t$$ , according to the formula

\displaystyle U^{\left(t\right)}\left(ϕ\right) = u^{\left(t\right)}\left(ϕ\left(x^{\left(t\right)}\right)\right),

(2)

where $x^{(t)}$ is the last-output strategy. The final construction is as follows:

Each call to NextStrategy first calls $$R$$ .NextStrategy to obtain the next transformation $ϕ^{(t)}$ . Then, a fixed point $x^{(t)} = ϕ^{(t)}(x^{(t)}) \in X$ is computed and output.
Each call to ObserveUtility $(u^{(t)})$ with linear utility function $u^{(t)}$ constructs the linear utility function $U^{(t)}: ϕ \mapsto u^{(t)}(ϕ(x^{(t)}))$ given in (2), and passes it to $$R$$ via $$R$$ .ObserveUtility $(U^{(t)})$ .

Graphically, we can summarize the process as in the following block diagram.

Figure 2. Gordon-Greenwald-Marks’s reduction from

\Phi

-regret minimization to external regret minimization for

\Phi

plus a fixed point oracle for

\Phi

Theorem S6.2 ([GGM08]) .

The $\Phi$ -regret $\Phi \text{-Reg}^{(T)}$ cumulated up to time $$T$$ by the algorithm we just defined is exactly equal to the (external) cumulative regret $\text{Reg}_{\Phi}^{(T)}$ cumulated by $$R$$ :

\displaystyle \Phi \text{-Reg}^{\left(T\right)} = \text{Reg}_{\Phi}^{\left(T\right)} \quad \quad \forall T = 1, 2, \dots .

Because the regret cumulated by

\(R\)

grows sublinearly by hypothesis of it being a regret minimizer, then so does the

\Phi

-regret of the

\Phi

-regret minimization algorithm defined above.

Proof.

The proof of correctness of the above construction is deceptively simple. Since $$R$$ outputs transformations $ϕ^{(1)},ϕ^{(2)},\dots \in \Phi$ and receives utilities $ϕ \mapsto u^{(1)}(ϕ(x^{(1)})), ϕ \mapsto u^{(2)} (ϕ (x^{(2)})), \dots$ , its cumulative regret $R^{(T)}$ is by definition

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

Now, since by construction $x^{(t)}$ is a fixed point of $ϕ^{(t)}$ , $ϕ^{(t)}(x^{(t)}) = x^{(t)}$ , and therefore we can write

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

where the right-hand side is exactly the cumulative

\Phi

-regret

\Phi \text{-Reg}^{(T)}

incurred by

R_{\Phi}

Bibliography for this lecture

[BM07]	Blum, A., & Mansour, Y. (2007). From external to internal regret. Journal of Machine Learning Research, 8(6).
[GGM08]	Gordon, G. J., Greenwald, A., & Marks, C. (2008). No-regret learning in convex games. Proceedings of the 25th International Conference on Machine Learning, 360–367.