portion of the coordinated outcome, it must reason about its [****]{}. We write the expected regret features as $$\begin{aligned}
{r^{{\Gamma}}_{{f}}({\sigma^{{\Gamma}}})} &= {\mathbb{E}_{{a}{\sim}{\sigma^{{\Gamma}}}}\left[{r^{{\Gamma}}_{{f}}({a})}\right]},\end{aligned}$$ and the expected regret under utility function ${w}$ as $$\begin{aligned}
{r^{{\Gamma}}_{{f}}({\sigma^{{\Gamma}}}|{w})} &= {\mathbb{E}_{{a}{\sim}{\sigma^{{\Gamma}}}}\left[{r^{{\Gamma}}_{{f}}({a}|{w})}\right]}
= {\langle {r^{{\Gamma}}_{{f}}({\sigma^{{\Gamma}}})},{w}\rangle}.\end{aligned}$$

A joint strategy is in [****]{} or, in a sense, stable if no player can benefit through a unilateral deviation. We can quantify this stability using expected regret with respect to the deviation set ${\Phi}$, $$\begin{aligned}
{\operatorname{Regret}^{{\Gamma}}_{{\Phi}}({\sigma^{{\Gamma}}}|{w})} = \max_{{f}\in{\Phi}}{r^{{\Gamma}}_{{f}}({\sigma^{{\Gamma}}}|{w})},\end{aligned}$$ and call a joint strategy ${\sigma^{{\Gamma}}}$ an [****]{} if $$\begin{aligned}
{\operatorname{Regret}^{{\Gamma}}_{{\Phi}}({\sigma^{{\Gamma}}}|{w})} \le {\varepsilon}.  \end{aligned}$$

The most general deviation set, ${\Phi^{\mbox{swap}}}$, corresponds with the [****]{} solution concept [@osborne1994course; @agt4]. Thus, regret can be thought of as the natural substitute for utility when assessing the optimality of behavior in multi-agent settings.

The set ${\Phi^{\mbox{swap}}}$ is typically intractably large. Fortunately, internal regret closely approximates swap regret and is polynomially-sized in both the number of actions and players.

If joint strategy ${\sigma^{{\Gamma}}}$ has ${\varepsilon}$ internal regret, then it is an ${A}{\varepsilon}$-correlated equilibrium under utility function $w$. That is, $\forall {w}\in{V}$, $$\begin{aligned}
{\operatorname{Regret}^{{\Gamma}}_{{\Phi^{\mbox{int}}}}({\sigma^{{\Gamma}}}|{w})} & \le {\operatorname{Regret}^{{\Gamma}}_{{\Phi^{\mbox{swap}}}}({\sigma^{{\Gamma}}}|{w})} \le
{A}\cdot{\operatorname{Regret}^{{\Gamma}}_{{\Phi^{\mbox{int}}}}({\sigma^{{\Gamma}}}|{w})}.\end{aligned}$$ \[lemma:internalapproxswap\]

The proof is provided in the Appendix.

Behavior Estimation in a Matrix Game
====================================

We are now equipped with 