---
abstract: 'Simple adaptive procedures that converge to correlated equilibria are known to exist for normal form games [@hart2000simple], but no such analogue exists for extensive-form games. Leveraging inspiration from @zinkevich2008regret (), we show that any internal regret minimization procedure designed for normal-form games can be efficiently extended to finite extensive-form games of perfect recall. Our procedure converges to the set of forgiving correlated equilibria, a refinement of various other proposed extensions of the correlated equilibrium solution concept to extensive-form games [@forges1986approach; @forges1986correlated; @von2008extensive]. In a forgiving correlated equilibrium, players receive move recommendations only upon reaching the relevant information set instead of all at once at the beginning of the game. Assuming all other players follow their recommendations, each player is incentivized to follow her recommendations *regardless of whether she has done so at previous infosets*. The resulting procedure is completely decentralized: players need neither knowledge of their opponents' actions nor even a complete understanding of the game itself beyond their own payoffs and strategies.'
author:
- |
    Hugh Zhang[^1]\
    Department of Economics and Computer Science\
    Stanford University\
    `ashleypowell@example.net`
bibliography:
- 'main.bib'
title: A Simple Adaptive Procedure Converging to Forgiving Correlated Equilibria
---

Introduction {#sec:intro}
============

Algorithmic game theory aims to discover simple, efficient algorithms that converge to equilibria. While in many cases, such algorithms are useful in their own right, they can also contribute towards more classical uses of game theory such as modelling real-world behavior. For example, if researchers can show the nonexistence of an algorithm that efficiently computes a given equilibrium, it raises questions on how well that equilibrium could model real-world behavior, since how would the real-world agents themselves discover it? Conversely, the existence of simple procedures that efficiently converge to an equilibrium increases the plausibility that such an equilibrium could arise naturally.

To model such procedures, we imagine that players play a game repeatedly and choose their actions at each iteration of the game based on a simple learning procedure over their past results. To model selfish agents, we are specifically interested in *uncoupled* learning procedures, where each player's actions do not depend on *another* player's payoffs. Blackwell's Approachability Theorem ([-@blackwell1956analog]) was later used to show that uncoupled dynamics could lead to a Nash equilibrium for two-player zero-sum games if each player chose their strategies with probabilities proportional to their regret for not choosing that strategy in the past. Separately, <span>@hannan1957approximation ([-@hannan1957approximation])</span> discovered a similar result via a modified version of fictitious play. More recently, @hart2000simple ([-@hart2000simple]) extended this result to converge to correlated equilibria for any normal-form game with any number of players. A separate paper also showed the nonexistence of any uncoupled procedure that converged to a Nash equilibrium in the general case [@hart2003uncoupled].

This paper asks whether we can achieve similar results for extensive-form games, where players play sequentially rather than simultaneously. One recent successful approach has been counterfactual regret minimization [@zinkevich2008regret], which converges to the Nash equilibrium for two-player zero-sum extensive-form games. As such, counterfactual regret minimization has been used extensively in building modern computer poker agents, which have recently surpassed humans in many popular forms of poker [@bowling2015heads; @moravvcik2017deepstack; @brown2018superhuman; @brown2019superhuman]. Counterfactual regret minimization uses a tree decomposition approach to break up the original game into a large number of "minigames", each of which can be independently optimized with any external regret minimization algorithm (e.g. @blackwell1956analog ()). We discuss counterfactual regret minimization as well as other methods of decomposing global regrets into local regrets in Section \[sec:globaldecomposition\].

Directly attempting to extend counterfactual regret minimization to converge to the set of correlated equilibria of general extensive-form games runs into the hurdle that describing the set of correlated equilibria may require an exponentially large number of incentive constraints. We consider several possible generalizations of the correlated equilibrium to extensive-form games and focus primarily on a new solution concept we call the forgiving correlated equilibrium. In a nutshell, the forgiving correlated equilibrium differs from the canonical correlated equilibrium by recommending actions only when a player encounters an infoset instead of revealing the complete recommended strategy at the beginning of the game. Assuming all other players follow their recommendations, each player is incentivized to follow her recommendations *regardless of whether she has done so at previous infosets*. We discuss the forgiving correlated equilibrium and its cousins in more detail in Section \[sec:equilibria\].

Our procedure follows in the footsteps of @zinkevich2008regret ([-@zinkevich2008regret]) by decomposing "global" regrets (which concern strategies over the entire game) into "local" regrets (which concern only actions at a single infoset). Our approach relies on both the tree decomposition technique that they use as well as a variation of the well known one-shot deviation principle. The resulting procedure converges to the set of forgiving correlated equilibria for any finite game of perfect recall. At each timestep, each player observes her past strategies and payoffs and uses this information to determine her future strategy. Our procedure is completely decentralized: players need neither knowledge of their opponents' actions nor even a complete understanding of the game itself beyond their own payoffs and strategies. Previously, <span>@huang2008computing ([-@huang2008computing])</span> give a polynomial-time algorithm converging to the set of extensive-form correlated equilibria, but no algorithm is known to converge to the set of autonomous correlated equilibria (or by extension the set of forgiving correlated equilibria) in polynomial time.

This work was done concurrently and independently from <span>@celli2020no ([-@celli2020no])</span>. Their work leverages the recent framework of regret circuits [@farina2018regret] whereas we rely primarily on inspiration from <span>@zinkevich2008regret ([-@zinkevich2008regret])</span> and the one-shot deviation principle, but their resulting procedure shares substantial similarities with the low memory variation of our procedure that converges to extensive-form correlated equilibria (Section \[sec:lowmemory\]).

Notation {#sec:notation}
========

We consider finite extensive-form games of perfect recall. For the present, we assume that there are no chance moves, though we address this issue separately in Section \[chance\]. Using standard notation for extensive-form games, let $N$ denote the number of players in the game. Let $\Sigma$ be the set of pure strategy profiles. Let $\mathcal{I}$ denote the set of all infosets. For any $s \in \Sigma$ and $I \in \mathcal{I}$, let $s(I)$ denote the action the strategy profile $s$ recommends at infoset $I$. Let the player function $P$ map from an infoset to the player who plays at that infoset. Let the action function $A$ map from an infoset to the set of valid actions at that infoset. In our setting, imagine that players play a game repeatedly. At each timestep $t = 1, 2, \dots$, the players each individually choose their strategies, and we represent their collective choice with the strategy profile $s^t$.

We now introduce the following notation: Let $O(s, I, a) \in \{0, 1\}$ denote if both the following conditions are true:

1.  $s(I) = a$

2.  Assuming everyone plays according to the strategy profile $s$, infoset $I$ is on the path of play.

We can additionally define $O(s, I) = \sum_{a \in A(I)} O(s, I, a)$. Colloquially, we say that an infoset action pair $(I, a)$ is *observed* at timestep t, if $O(s^t, I, a) = 1$. We may also say that an infoset $I$ is observed at timestep $t$ if $O(s^t, I) = 1$.

Let ($R$ for reachable) $R(s, I) \in \{0, 1\}$ represent whether player $P(I)$ can play in such a way that $I$ is observed, assuming that everyone else plays according to strategy profile $s$.

Let $s | _{I\rightarrow b}$ denote the strategy profile where all players play according to $s$ except that player $P(I)$ plays as necessary to reach infoset $I$ and plays action $b$ at infoset $I$. Similarly, let $s_I$ be the strategy profile where everyone plays according to $s$ except that player $P(I)$ plays to reach $I$. If player $P(I)$ cannot play to reach infoset $I$, everyone plays according to $s$ all the time.

Let (N for next) $N(s, I, a)$ represent the infoset where player $P(I)$ next plays after $I$ assuming everyone plays according to $s |_{I\rightarrow a}$. If player $P(I)$ cannot play to reach infoset $I$ or she does not play again after infoset $I$, we let $N(s, I, a) = \emptyset$. Let $Succ(I, a) = \bigcup_{s \in \Sigma} \, \{ N(s, I, a) \}$, which intuitively denotes all possible next infosets player $P(I)$ can play at assuming she plays action $a$ at infoset $I$. Let $DES(I)$ represent all possible infosets which are owned by player $P(I)$ and that are descendants of $I$ (including $I$ itself).

Call the ancestry of an infoset $I$ the sequence of infosets and actions that lead to $I$ from the start of the game from the perspective of player $P(I)$. Specifically, denote it as the longest possible sequence

$$I_1, a_1, I_2, a_2 \dots I_n, a_n, I_{n+1}$$

where for all $k$, $a_k \in A(I_k)$, $P(I) = P(I_k)$, $I_k \in Succ(I_{k-1}, a_{k-1})$ and $I_{n+1} = I$. By the assumption of perfect recall, this ancestry is unique for each infoset. Now, given the above ancestry of an infoset $I$ define the signal history function $S(s, I)$ as the length $n+1$ vector. $$\begin{pmatrix} s(I_1) & \dots & s(I_n) & s(I) \end{pmatrix}$$

Additionally, denote the first $n$ elements of $S(s, I)$ as the partial signal history represented by $$S(s, I)_{-1} = \begin{pmatrix} s(I_1) & \dots & s(I_n) \end{pmatrix}$$

Denote the set of all possible signal histories at an infoset $I$ as $S(I) = \bigcup_{s \in \Sigma} S(s, I)$

When discussing either autonomous correlated equilibria or forgiving correlated equilibria, for any player $i$, define a deviation plan $d$ as a function mapping every infoset $I$ owned by player $i$ and signal history ${\bm{\vec{a}}}\in S(I)$ pair to an action $a \in A(I)$. For a player $i$, call the set of all her deviation plans $\mathcal{D}_i$.

Let $u(I, s_1, s_2)$ represent the utility player $P(I)$ receives if everyone plays in the following manner. All players other than $P(I)$ always play according to strategy profile $s_2$. Player $P(I)$ plays whatever moves are necessary to reach infoset $I$ and then plays according to strategy profile $s_1$ afterward, including at infoset $I$.

Note that because we assume perfect recall, this uniquely determines the strategy of all players as the sequence of actions to reach $I$ is unique. Additionally, we often abbreviate $u(I, s_2) = u(I, s_2, s_2)$, which intuitively denotes the payoff player $P(I)$ receives when everyone plays according to strategy profile $s_2$ except that $P(I)$ deviates only as necessary to guarantee that she reaches infoset $I$ if it is possible to do so. If it is not possible for player $P(I)$ to reach infoset $I$ if everyone else plays according to $s_2$, let $u(I, s_1, s_2) = 0$. When discussing autonomous correlated equilibria or forgiving correlated equilibria, let $u(I, d, s)$ represent the utility of player $P(I)$ if she plays to reach infoset $I$ and then follows deviation plan $d$ afterwards (including at infoset $I$), while all other players follow strategy profile $s$ all the time. If it is not possible for player $P(I)$ to reach infoset $I$, all players always play according to strategy profile $s$.

Correlating Signals in Extensive-Form Games {#sec:equilibria}
===========================================

In this section, we define and analyze various equilibria which extend the correlated equilibria solution concept to extensive-form games. As with the canonical correlated equilibrium, all the following solution concepts have a mediator select a strategy profile $s$ according to some probability distribution $h$ before play begins. However, unlike the canonical correlated equilibrium, these solution concepts all have the mediator show player $P(I)$ her action recommendation $a \in A(I)$ only when she reaches infoset $I$ instead of revealing the entire strategy recommendation at the beginning of the game. In a normal-form game, all these solution concepts collapse onto each other and the canonical correlated equilibrium since there is only one infoset to consider.

As a result of how the recommendations are revealed, each of these equilibria (with the exception of forgiving correlated equilibria) forms a superset of the set of correlated equilibria since at any given point in time, each player has only seen a partial strategy recommendation and has less information to decide whether she wants to deviate from the recommendation.

The canonical correlated equilibrium can pose incentive constraints that grow in number exponential to the number of infosets for extensive-form games, and it is currently not known if any algorithm can discover such an equilibrium in polynomial time. We review three potential candidate solution concepts that generalize the correlated equilibrium to extensive-form games by posing only a polynomial number of (relevant) incentive constraints relative to the number of infosets in the game: the agent form correlated equilibrium, the extensive-form correlated equilibrium, and the autonomous correlated equilibrium. We additionally propose a new solution concept, the forgiving correlated equilibrium, that refines all the above solution concepts.

To ensure standard notation, we give definitions for all equilibria considered in the following sections, as well as intuitive explanations for what they denote.

Agent Form Correlated Equilibrium
---------------------------------

The agent form correlated equilibrium was proposed by @forges1986correlated ([-@forges1986correlated]). Imagine constructing a variation of an extensive-form game where each infoset is controlled by a separate agent. The correlated equilibrium of that game variant forms an agent correlated equilibrium of the original game. An alternative equivalent characterization of an agent correlated equilibrium is that there is no profitable one-shot deviation from any action recommendation given at any infoset observed with positive probability. Of all the generalizations of the correlated equilibrium to extensive-form games we consider, the agent form correlated equilibrium poses the weakest incentive constraints on the players.

<span>Agent Form Correlated Equilibrium</span>

Let $h$ be a probability distribution over strategy profiles. $h$ forms an *agent form correlated equilibrium* if it satisfies: $$\max_{I \in \mathcal{I}} \max_{a \in A(I)} \max_{b \in A(I)} \sum_{s \in \Sigma} h(s) O(s, I, a) (u(I, s_{I\rightarrow b}, s) - u(I, s)) \leq 0$$

Extensive-Form Correlated Equilibrium {#efce}
-------------------------------------

The extensive-form correlated equilibrium [@von2008extensive] poses a stricter constraint than the agent form correlated equilibrium in that players are not restricted to one-shot deviations. However, upon deviating from the mediator's recommendation, they will no longer receive any future recommendations from the mediator (other players still do). This differs from the standard correlated equilibrium since in that setting, each player receives her recommendations for the whole game at the beginning of the game before making any of her action choices.

A correlating signal $h$ forms an extensive-form correlated equilibrium if every player is incentivized to follow their signal, assuming that all the other players will follow their signals regardless of her choice. If $h$ is the signal for an extensive-form correlated equilibrium, then for all infoset action pairs $(I, a)$, at least one of the following two conditions holds

1.  Infoset $I$ is never reached if players play according to the recommendation signal $h$ or action recommendation $a$ is never given by $h$ at infoset $I$ (i.e. $\forall s, h(s) O(s, I, a) = 0)$

2.  Conditional on observing infoset $I$ and recommendation $a$, player $P(I)$ would prefer to follow her recommendation and continue receiving information than to unilaterally deviate to any strategy $s'$.

Based on this observation, we can formally define the extensive-form correlated equilibrium.

<span>Extensive-Form Correlated Equilibrium</span>

Let $h$ be a probability distribution over strategy profiles. $h$ forms an *extensive-form correlated equilibrium* if it satisfies: $$\max_{I \in \mathcal{I}} \max_{a \in A(I)} \max_{s' \in \Sigma} \sum_{s \in \Sigma} h(s) O(s, I, a) (u(I, s', s) - u(I, s)) \leq 0$$

Autonomous Correlated Equilibria
--------------------------------

The autonomous correlated equilibrium (@forges1986approach) poses an even stricter incentive constraint compared to the extensive-form correlated equilibrium in that signals will continue to be given even after a player deviates from their recommendations. Thus, players will have more information after deviating than their counterparts in an extensive-form correlated equilibrium since the signals received after deviating could reveal information on what the other players are receiving as recommendations. Because we need to account for this additional information, our definition for the autonomous correlated equilibrium (and its refinement, the forgiving correlated equilibrium), use the concept of a deviation plan defined in Section \[sec:notation\].

Let $h$ be a probability distribution over strategy profiles. A signal $h$ forms an *autonomous correlated equilibrium* if it satisfies: $$\max_{I \in \mathcal{I}} \max_{{\bm{\vec{a}}}\in S(I)} \max_{d \in \mathcal{D}_{P(I)}} \sum_{s \in \Sigma} h(s) O(I, s) \mathds{1}(S(I, s) = {\bm{\vec{a}}}) (u(I, d, s) - u(I, s)) \leq 0$$

To explain the definition using the English language, for every possible infoset and signal history combination ($I, {\bm{\vec{a}}}$), summing over all possible strategies weighted by how often the signal gives a specific set of recommendations ($\sum_{s\in \Sigma} h(s)$), for all instances where it is possible to receive action recommendation ${\bm{\vec{a}}}$ at infoset $I$ if all players follow their recommendations ($\mathds{1}(S(I, s) = {\bm{\vec{a}}})O(I, s)$), player $P(I)$ has no incentive to deviate from her strategy recommendations at either the current point or any point in the future $(u(I, d, s) - u(I, s))$.

Forgiving Correlated Equilibria
-------------------------------

The forgiving correlated equilibrium poses the strictest incentive constraint of all the considered extensions of correlated equilibria to extensive-form games. As in an autonomous correlated equilibrium, recommendations continue to be given to each player even after they deviate from their recommendations, but a forgiving autonomous correlated equilibrium additionally requires that these recommendations continue to guide the player in the right direction. As such, in contrast to the autonomous correlated equilibrium and the extensive-form correlated equilibrium, the mediator is "forgiving" in that she will continue to give each player the best possible recommendation even after that player has already ignored her advice.

Concretely, we say a signal forms a forgiving correlated equilibrium if, assuming everyone else always follows their signals, you are incentivized to follow your signal, regardless of whether you have done so in previous infosets this game. Stated another way, deviating from the mediator's recommendation at any point in time will never be profitable, even if you have previously already deviated from the mediator's recommendations. Note that this is related but not the same as the concepts of subgame perfection and sequential rationality, as we continue to assume that at most one player will ever deviate from her recommendations.

\[facedefinition\]

Let $h$ be a probability distribution over strategy profiles. A signal $h$ forms a *forgiving correlated equilibrium* if it satisfies: $$\max_{I \in \mathcal{I}} \max_{{\bm{\vec{a}}}\in S(I)} \max_{d \in \mathcal{D}_{P(I)}} \sum_{s \in \Sigma} h(s) R(I, s) \mathds{1}(S(I, s) = {\bm{\vec{a}}}) (u(I, d, s) - u(I, s)) \leq 0$$

Notice the strong similarities between the definitions for forgiving correlated equilibria and autonomous correlated equilibria. The two definitions, in fact, only differ by one character as the forgiving correlated equilibrium uses the reachability condition ($R$) instead of the observability condition $O$. As such, in the autonomous correlated equilibrium, we constrain only infosets that are on the path of play but in a forgiving correlated equilibrium, we constrain all infosets that are *reachable* under a strategy $s$ with the $R(s, I)$ term assuming only player $P(I)$ deviates from her recommendations. Additionally, note that the forgiving correlated equilibrium refines all the above solution concepts, so any procedure that converges to the set of forgiving correlated equilibria also automatically converges to the set of any of the other equilibria in question.

Equilibria in the Real World
----------------------------

We consider two broad use cases for such equilibria in the real world. One is to model observed behavior, and the other is to advise it. Extensive-form games are commonly used to model real-world scenarios where actions are taken sequentially instead of ashleypowell@example.net. Like the canonical correlated equilibrium, the autonomous correlated equilibrium (and the forgiving correlated equilibrium by extension) allows for the correlating signal to arise "naturally'' for such games. As a concrete example, we imagine a group of ancient politicians quarantined (separately) in the same general area during a long-forgotten pandemic. Since there is no internet and nonessential mail is slow during such times, communicating directly with one another is difficult. Nevertheless, each politician is required to vote on urgent government matters received via priority mail that still does function in such times. Every morning, each politician receives a briefing from the government with information on the results of yesterday's vote and the bill they must vote on today, as well as a collection of private information compiled by their hardworking staff. They must mail in their vote by the end of the day. Despite the lack of direct communication, politicians can still coordinate if they have access to a common signal. For instance, if they all have windows, the coordinated policy could even be something as simple as all politicians in a coalition voting no if it rains that day.

To return from the analogy to the language of game theory, each infoset is the information each player receives at the start of each day combined with their memory of past briefings, and the exogenous variation of the weather forms the correlating signal. As such, solution concepts such as the forgiving correlated equilibrium have the potential to help explain the behavior of agents playing extensive-form games in the real world.

Yet another purpose can be to advise behavior. To a rough approximation, Google Maps can be viewed as a mediator in a forgiving correlated equilibrium. When we are instructed to take a certain route to get to our destination, it is usually in our interest to follow that route. Additionally, even if we deviate from the recommended route, Google Maps will recalculate the best route given our decision rather than shutting off and leaving us to find our own way to the destination, as the mediator in an extensive-form correlated equilibrium would be apt to do. One can also imagine other applications where such equilibria may prove useful for advising behavior, such as routing Internet traffic or coordinating global shipping.

From Global To Local Regrets {#sec:globaldecomposition}
============================

Having defined the equilibria we hope to converge to, we now proceed to describe our procedure. Directly attempting to satisfy the incentive constraints describing the various equilibria as defined in Section \[sec:equilibria\] is likely challenging. Even simply computing many of the inequalities that define such equilibria by directly enumerating all possible strategy deviations would require exponential amounts of time, because if we let $M = {\left\lvert\max_{I \in \mathcal{I}} \mathcal{A}(I)\right\rvert}$, the number of strategy profiles in the game is on the order of ${\left\lvert\mathcal{I}\right\rvert}^{M}$. We call such regrets "global" if they operate over strategy deviations of the entire game. To make such computations tractable, one approach, popularized by <span>@zinkevich2008regret ([-@zinkevich2008regret])</span>, is to break down these "global" regrets into "local" regrets which operate only on single actions at a given infoset. If these local regrets can be minimized independently and there are only a polynomial number of (relevant) regrets to minimize, then the runtime can be converted to a much more tractable $O( \texttt{poly}(M \times {\left\lvert\mathcal{I}\right\rvert}))$.

We start by reviewing the tree decomposition approach used by <span>@zinkevich2008regret ([-@zinkevich2008regret])</span> in the counterfactual regret minimization procedure before discussing how we can achieve similar results using a variation of the one-shot deviation principle.

Counterfactual Regret Minimization {#cfr}
----------------------------------

The following is an overview of counterfactual regret minimization, adapted slightly for our purposes. We walk through the procedure of <span>@zinkevich2008regret ([-@zinkevich2008regret])</span> with the exception that we add an additional $O(s^t, I^P, a)$ term at each step, which allows us to filter for only the timesteps where the pair $(I^P, a)$ was observed.

Regrets
-------

We assume $P(I^P) = P(I)$ and that $I^P$ is an ancestor of $I$.

<span>External Regrets ($ER$)</span>

For any $b \in A(I)$ and $a \in A(I^P)$, we can define the external regret as follows:

$$ER^T(I^P, a, I) = \max\limits_{s^B \in \Sigma} \frac{1}{T} \sum_{t=1}^T O(s^t, I^P, a) R(s^t, I) (u(I, s^B, s^t) - u(I, s^t))$$ $$ER^{T+}(I^P, a, I) = \max (0, ER^T(I^P, a, I))$$

Intuitively, $ER$ is the external regret for the subgame rooted at infoset $I$ (from player $P(I)$'s perspective), filtering only for timesteps where the infoset action pair $(I^P, a)$ was observed.

<span>Counterfactual Regrets ($CFR$)</span>

For any $b \in A(I)$ and $a \in A(I^P)$, we can define the $CFR$ (counterfactual regret) as follows:

$$CFR^{T}(I^P, a, I, b) = \frac{1}{T} \sum_{t=1}^T O(s^t, I^P, a) R(s^t, I) (u(I, s^t |_{I \rightarrow b}, s^t) - u(I, s^t))$$ $$CFR^{T+}(I^P, a, I) = \max\limits_{b \in A(I)} \max(0, CFR^{T}(I^P, a, I, b))$$

Notice the substantial similarities between $CFR$ and $ER$. While $ER$ regrets are "global" in that they allow deviations described by an entire strategy, $CFR$ regrets are "local" in that they only allow only changes of a single action. In the following sections, we show how $ER$ can be bounded by a sum of a collection of $CFR$ regrets.

Tree Decomposition
------------------

Note that via rearrangement, we have

$$\begin{aligned}
& \max\limits_{s^B \in \Sigma} \: (u(I, s^B, s^t) - u(I, s^t))\\
= \: & \max\limits_{s^B \in \Sigma}  \: (u(I, s^B, s^t) - u(I, s^t) + u(I, s^t |_{I\rightarrow s^B(I)}) - u(I, s^t |_{I\rightarrow s^B(I)})) \\
= \: & \max\limits_{s^B \in \Sigma}\:(u(I, s^t |_{I\rightarrow s^B(I)}) - u(I, s^t)) + (u(I, s^B, s^t) - u(I, s^t |_{I\rightarrow s^B(I)})) \\
\leq \: & \max\limits_{s^B \in \Sigma}\:(u(I, s^t |_{I\rightarrow s^B(I)}) - u(I, s^t)) + \max\limits_{s^B \in \Sigma}\:(u(I, s^B, s^t) - u(I, s^t |_{I\rightarrow s^B(I)}))\end{aligned}$$

This is the core technique behind counterfactual regret minimization as well as our decomposition in Section \[mainprop\].

CFR Inequality
--------------

The main purpose of this inequality is to show that we can minimize our $ER$ regrets by simply minimizing $CFR$ regrets at each infoset that is a descendent of $I^P$.

$$ER^{T}(I^P, a, I) \leq CFR^{T+}(I^P, a, I) + \max\limits_{b \in A(I)} \sum_{I' \in Succ(I, b)} ER^{T}(I^P, a, I')$$

$$\begin{aligned}
ER^{T}(I^P, a, I) = & \; \max\limits_{s^B \in \Sigma} \frac{1}{T} \sum_{t=1}^T O(s^t, I^P, a) R(s^t, I) (u(I, s^B, s^t) - u(I, s^t)) \\
\leq & \; \max\limits_{s^B \in \Sigma}\:\frac{1}{T} \sum_{t=1}^T O(s^t, I^P, a) R(s^t, I) (u(I, s^t |_{I\rightarrow s^B(I)}) - u(I, s^t)) \: + \\
& \;  \max\limits_{s^B \in \Sigma} \frac{1}{T} \sum_{t=1}^T  O(s^t, I^P, a) R(s^t, I)  (u(I, s^B, s^t) - u(I, s^t |_{I\rightarrow s^B(I)}))\end{aligned}$$

This is an application of the tree decomposition technique discussed previously. Now, examine the two maximization terms separately. The first term is

$$\begin{aligned}
& \max\limits_{s^B \in \Sigma}\:\frac{1}{T} \sum_{t=1}^T O(s^t, I^P, a) R(s^t, I) (u(I, s^t |_{I\rightarrow s^B(I)}) - u(I, s^t)) \\
= & \max\limits_{b \in A(I)}\:\frac{1}{T} \sum_{t=1}^T O(s^t, I^P, a) R(s^t, I) (u(I, s^t |_{I\rightarrow b}) - u(I, s^t)) \\
\leq & \; CFR^{T+}(I^P, a, I)\end{aligned}$$

The second term is

$$\begin{aligned}
& \max\limits_{s^B \in \Sigma} \frac{1}{T} \sum_{t=1}^T  O(s^t, I^P, a) R(s^t, I)  (u(I, s^B, s^t) - u(I, s^t |_{I\rightarrow s^B(I)})) \\
= & \max\limits_{b \in A(I)} \max\limits_{s^B \in \Sigma} \frac{1}{T} \sum_{t=1}^T  O(s^t, I^P, a) R(s^t, I)  (u(I, s^B|_{I\rightarrow b}, s^t) - u(I, s^t |_{I\rightarrow b})) \\
= &  \max\limits_{b \in A(I)} \max\limits_{s^B \in \Sigma} \sum_{I' \in Succ(I, b)} \frac{1}{T} \sum_{t=1}^T  O(s^t, I^P, a) R(s^t, I')  (u(I', s^B, s^t) - u(I', s^t)) \\
\leq &  \max\limits_{b \in A(I)} \sum_{I' \in Succ(I, b)} \max\limits_{s^B \in \Sigma}  \frac{1}{T} \sum_{t=1}^T  O(s^t, I^P, a) R(s^t, I')  (u(I', s^B, s^t) - u(I', s^t)) \\
= &  \max\limits_{b \in A(I)} \sum_{I' \in Succ(I, b)} ER(I^P, a, I')\end{aligned}$$

$$ER^{T+}(I^P, a, I) \leq CFR^{T+}(I^P, a, I) + \max\limits_{b \in A(I)} \sum_{I' \in Succ(I, b)} ER^{T+}(I^P, a, I')$$

We can expand out the above inequality recursively, and write

\[cfrdecomp\] $$ER^{T+}(I^P, a, I) \leq \sum_{I' \in DES(I)} CFR^{T+}(I^P, a, I')$$

$$\begin{aligned}
ER^{T+}(I^P, a, I) \leq \; & CFR^{T+}(I^P, a, I) + \max\limits_{b \in A(I^P)} \sum_{I' \in Succ(I^P, b)} ER^{T+}(I^P, a, I') \\
\leq \; &  CFR^{T+}(I^P, a, I) +  \sum\limits_{b \in A(I^P)} \sum_{I' \in Succ(I^P, b)} ER^{T+}(I^P, a, I') \\
\leq \; &  \sum_{I' \in DES(I)}  CFR^{T+}(I^P, a, I')\end{aligned}$$

where the last step expands out $ER$ recursively and uses the assumption of perfect recall to show that each $I'$ appears at most once in the sum.

In their original paper, <span>@zinkevich2008regret ([-@zinkevich2008regret])</span> minimized (slightly modified) $CFR$ regrets independently at each $I'$ using Blackwell's regret minimization. This resulted in convergence to the set of coarse correlated equilibria, which in the special case of two-player zero-sum games, corresponds to the Nash equilibrium of the game.

Regret Decomposition via the One-Shot Deviation Principle
---------------------------------------------------------

An alternative method of decomposing regrets is via a variation of the one-shot deviation principle for subgame perfect Nash equilibria. Proposition \[faceredefinition\] asserts that if there is no profitable "local" deviation from the signal (even if you have already deviated before), there is no profitable "global" deviation from the signal either.

\[faceredefinition\] A signal $h$ satisfies the inequalities given in Definition \[facedefinition\] (definition of a forgiving correlated equilibrium) if and only if it satisfies $$\max_{I \in \mathcal{I}} \max_{{\bm{\vec{a}}}\in S(I)} \max_{b \in A(I)} \sum_{s\in \Sigma} h(s) R(I, s) \mathds{1}(S(I, s) = {\bm{\vec{a}}}) (u(I, s_{I\rightarrow b}) - u(I, s_{I})) \leq 0$$

The backward direction falls out immediately, as all local deviations are also global deviations, so if no global deviations exist, no local ones will either. For the forward direction, consider the following lemma. \[globlocal\]

If $h$ is not a forgiving correlated equilibrium (as per Definition \[facedefinition\]), there exists at least one pair $(I, {\bm{\vec{a}}})$ such that both of the following are true:

1.  **Possibility**. Under signal $h$, it is possible that signal history ${\bm{\vec{a}}}$ is observed at infoset $I$ (i.e. $\exists s$ s.t. $h(s)\mathds{1}(S(I, s) = {\bm{\vec{a}}}) > 0$)

2.  **Local Profitability** Player $P(I)$ believes it is profitable to deviate from the signal history ${\bm{\vec{a}}}$ at the current infoset, but believes that it will not be profitable to deviate from the recommendation for any descendent infosets $I' \in DES(I)$, $I' \neq I$.

Consider the set of $(I, {\bm{\vec{a}}})$ pairs that are possible under signal $h$. Define a sequence $L_n$ as follows. Choose $L_1$ to be any possible pair $(I_1, {\bm{\vec{a}}}_1)$ where ${\bm{\vec{a}}}_1 \in S(I_1)$ and where our player believes it is profitable (in expectation) to deviate from the signal recommendation ${\bm{\vec{a}}}_1$ at infoset $I$ and follow some arbitrary deviation plan $d$ from this point onwards. By the assumption that $h$ does not form a forgiving correlated equilibrium, at least one such instance must exist. For any $n > 1$, choose $L_n$ to be any $(I_n, {\bm{\vec{a}}}_n)$ pair that satisfies both the above conditions and also ensures that $I_n \in DES(I_{n-1})$ and $I_n \neq I_{n-1}$. Because our game is finite and perfect recall guarantees that there are no cycles in our game tree (from the perspective of a single player), this sequence must terminate. The last such $(I_n, {\bm{\vec{a}}}_n)$ pair satisfies our criteria.

We can immediately deduce the following corollary, which is the contrapositive of the lemma.

If there is no such $(I, {\bm{\vec{a}}})$ pair that satisfies both the possibility and local profitability conditions defined above, then there is no profitable global deviation either.

This completes our proof, as the definition proposed by Proposition \[faceredefinition\] directly encodes the possibility and local profitability conditions for every $I, {\bm{\vec{a}}}$ pair.

Main Procedure {#sec:mainprocedure}
==============

In our setting, we imagine that players play a game repeatedly and choose their actions at each iteration of the game based on a simple learning procedure over their past results. Our goal is to design a procedure that will cause the resulting play to efficiently converge to the desired equilibrium. This is typically done in two steps. First, we define a collection of regrets, chosen such that if all such regrets go to $0$, then the resulting play will converge to the desired equilibrium. Secondly, we show that we can send all such regrets to $0$ by having players play in a particular fashion. We define the $CFIR$ regrets as follows and show that minimizing these regrets is sufficient to converge to the set of forgiving correlated equilibria.

<span>Counterfactual Internal Regrets (CFIR)</span> $$CFIR^{T+}(I, {\bm{\vec{a}}}, b) = \sum_{t = 1}^T R(I, s^t) \mathds{1}(S(I, s^t) = {\bm{\vec{a}}}) (u(I, s^t_{I\rightarrow b}) - u(I, s^t_{I}))$$ $$CFIR^{T+}(I, {\bm{\vec{a}}}) = \max_{b \in A(I)} CFIR^{T+}(I, {\bm{\vec{a}}}, b)$$

\[cfirconvergence\] If $CFIR^{T+}(I, {\bm{\vec{a}}}) \rightarrow 0$ for all $I$ and ${\bm{\vec{a}}}\in S(I)$ as $T \rightarrow \infty$, then the distance between the signal $h^T(s) = \frac{1}{T}\sum_{t=1}^T \mathds{1}(s^t=s)$ and the set of forgiving correlated equilibria converges to 0.

If this is not the case, then at least one of the inequalities which define the forgiving correlated equilibrium as per Proposition \[faceredefinition\] must be violated infinitely often by some $\epsilon > 0$. Consider the specific $I$ and ${\bm{\vec{a}}}$ that define this inequality. We can write, $$\begin{aligned}
& CFIR^{T+}(I, {\bm{\vec{a}}}) \\
= & \max_{b \in A(I)} \sum_{t = 1}^T R(I, s^t) \mathds{1}(S(I, s^t) = {\bm{\vec{a}}}) (u(I, s^t_{I\rightarrow b}) - u(I, s^t_{I})) \\
= & \max_{b \in A(I)} \sum_{s\in \Sigma} h^T(s)  R(I, s^t) \mathds{1}(S(I, s) = {\bm{\vec{a}}}) (u(I, s_{I\rightarrow b}) - u(I, s_{I}))\end{aligned}$$

which is the exact inequality in question. Since we assume that $CFIR^{T+}(I, {\bm{\vec{a}}}) \rightarrow 0$, this inequality cannot be violated by at least $\epsilon$ for an infinite number of timesteps.

Procedure
---------

For simplicity, we use <span>@hart2000simple ([-@hart2000simple])</span> though any other internal regret minimization procedure will also work. At each timestep, each player traverses through her infosets in any order such that an infoset is encountered only after encountering all of its ancestors. Because perfect recall guarantees that the infosets (for a single player) form a proper tree with no cycles, such an ordering is always possible, and the common breadth-first and depth-first order traversals both satisfy this requirement. If we have our player choose her strategy $s^t(I)$ as we encounter each infoset $I$, this traversal ordering allows us to compute the partial signal history $S(s^t, I)_{-1}$ when we encounter each infoset $I$, since it only requires $s^t$ to be specified for ancestors and not descendants of $I$ (or $I$ itself).

How do have our player choose her actions $s^t(I)$ when she encounters an infoset? Our player recalls from memory the past timesteps where she observed the signal $S(s^t, I)_{-1}$ when encountering infoset $I$ and pretends that she is playing to minimize her internal regrets for only this subset of timesteps. Concretely, we can denote her action at the latest timestep where she observed $S(s^t, I)_{-1}$ at infoset $I$ as $a$. If no such timestep exists, choose $a$ arbitrarily. We concatenate the partial signal history with this past action to get the full signal history ${\bm{\vec{a}}}= (S(s^t, I)_{-1}, a)$. As per <span>@hart2000simple ([-@hart2000simple])</span>, she either repeats her action $a$ or departs from it to action $b$ with probability proportional to her positive regrets from not deviating to any action $b$ for only this subset of timesteps.

Proof of Convergence
--------------------

We say that a sequence of random variables $(L_n)_n$ converges to $L$ with high probability if, for every $\epsilon, \alpha > 0$, we can find $N$ such that $n > N$ implies $\Pr({\left\lvertL_n - L\right\rvert} > \epsilon) < \alpha$. To guarantee that our procedure converges to the set of forgiving correlated equilibria, Theorem \[cfirconvergence\] shows that we merely need to show that all CFIR regrets go to zero with high probability.

\[highprobabilityconvergence\] If all players play according to the above procedure, $CFIR^{T+}(I, {\bm{\vec{a}}})$ converges to $0$ with high probability for all $I$ and ${\bm{\vec{a}}}\in S(I)$.

For any fixed infoset $I$ and signal history ${\bm{\vec{a}}}$, examine the timesteps $t$ where $I$ is reachable and ${\bm{\vec{a}}}$ is observable. Mathematically, we can represent this as the set of timesteps $t$ that satisfy $$R(I, s^{t}) \mathds{1}(S(I, s^{t}) = {\bm{\vec{a}}}) = 1$$ Say that we visit $(I, {\bm{\vec{a}}})$ at timestep $t$ if $t$ satisfies this condition. For a given $(I, {\bm{\vec{a}}})$, notice that any timestep $t$ where we do not visit $(I, {\bm{\vec{a}}})$ automatically contributes $0$ regret to $CFIR^{T+}(I, {\bm{\vec{a}}})$ due to the definition of $CFIR$. Consider for the sake of argument that we visit $(I, {\bm{\vec{a}}})$ every timestep. If so, then this sequence of $CFIR$ is exactly an internal regret and because our choice of actions is constrained by an internal regret minimizing procedure, $CFIR^{T+}(I, {\bm{\vec{a}}}, b)$ converges to 0 with high probability as desired. Of course, in the general case, we may not visit $(I, {\bm{\vec{a}}})$ at every timestep $t$. Let $B$ represent the maximum possible regret for any strategy profile choice in our game. To prove convergence to 0 with high probability in general, choose any $\epsilon < B$ and $\alpha > 0$. Choose $N'$ such that if every timestep visited $(I, {\bm{\vec{a}}})$, $n > N'$ would guarantee that

$$\Pr(CFIR^{T+}(I, {\bm{\vec{a}}}, b) \geq \epsilon) \leq \alpha$$

Choosing $N = \frac{BN'}{\epsilon}$ satisfies our condition without this assumption. We show this in two cases. For any $n > N$, if less than $N'$ timesteps between $1 \dots n$ visit $(I, {\bm{\vec{a}}})$, then our maximum possible regret is bounded by $\frac{BN'}{N} = \epsilon$ so we satisfy the condition. On the other hand, if $N'$ or more of these timesteps observe $(I, {\bm{\vec{a}}})$, then the condition is satisfied directly by the fact that $N > N'$, as all the remaining timesteps that do not visit $(I, {\bm{\vec{a}}})$ contribute no regret.

Chance Nodes {#chance}
------------

Up to this point, we have assumed that our games lack any element of randomness. We can modify our game to include chance nodes controlled by a new "chance" player whose strategy is fixed. As our procedure includes no interaction between players, the resulting correlating signal will not induce any correlation between the chance player and the other player's recommendations. Additionally, since all regret minimization procedures guarantee that the regrets will go to zero regardless of how other players play, we can immediately guarantee convergence for games with chance moves without any changes to our procedure.

Memory Usage
------------

Our procedure requires that each player keep track of all their regrets and latest moves for every $(I, {\bm{\vec{a}}})$ pair. In the worst case, this results in exponentially large memory usage, as the number of possible signal histories can be exponential in the number of infosets in a game if the tree is very unbalanced. Note though that, if we let $M$ denote the number of infosets in the game, running our procedure for $N$ steps will only require at most $O(NM)$ memory, as only one of the exponentially many regrets will be relevant at any given infoset for a given timestep. As a result, running our algorithm for a number of steps polynomial in $M$ will also only require memory polynomial in $M$.

[^1]: Originally published in 2020 as a senior honors thesis under the supervision of Gabriel Carroll at https://purl.stanford.edu/hk596cg1085.

{'source': 'arXiv_out/2207'}