# Rationality of Learning Algorithms in Repeated Normal-Form Games

Shivam Bajaj  Pranoy Das  Yevgeniy Vorobeychik  Vijay Gupta

###### Abstract

Many learning algorithms are known to converge to an equilibrium for specific
classes of games if the same learning algorithm is adopted by all agents.
However, when the agents are self-interested, a natural question is whether
agents have a strong incentive to adopt an alternative learning algorithm that
yields them greater individual utility. We capture such incentives as an
algorithm’s _rationality ratio_ , which is the ratio of the highest payoff an
agent can obtain by deviating from a learning algorithm to its payoff from
following it. We define a learning algorithm to be _$c$ -rational_ if its
rationality ratio is at most $c$ irrespective of the game. We first establish
that popular learning algorithms such as fictitious play and regret matching
are not $c$-rational for any constant $c\geq 1$. We then propose and analyze
two algorithms that are provably $1$-rational under mild assumptions, and have
the same properties as (a generalized version of) fictitious play and regret
matching, respectively, if all agents follow them. Finally, we show that if an
assumption of perfect monitoring is not satisfied, there are games for which
$c$-rational algorithms do not exist, and illustrate our results with
numerical case studies.

##  1 Introduction

Learning in a multi-agent framework with cooperative, non-cooperative, or
mixed agents (Jacq et al., 2020; Nguyen et al., 2019; Lowe et al., 2017; Zhang
et al., 2021b) has been expanding rapidly with proposed applications including
cyber-physical systems (Adler & Blue, 2002; Bashendy et al., 2023), finance
(Lee et al., 2007), sensor networks (Choi et al., 2009), and robotics (Cui et
al., 2020; Orr & Dutta, 2023). A popular framework in this area is to model
for the interactions among self-interested and rational agents as a repeated
or stochastic game (Yang & Wang, 2020; Hu et al., 1998; Littman, 1994; Bowling
& Veloso, 2002; Zhang et al., 2021a). Given that computation of an equilibrium
of the underlying game is often not computationally feasible, a fundamental
line of research in this model is to identify simple learning procedures that,
if adopted by all agents (i.e., in _self-play_), converge to an equilibrium
(Monderer & Shapley, 1996; Leslie & Collins, 2006; Sayin et al., 2022; Baudin
& Laraki, 2022; Jacq et al., 2020; Chasnov et al., 2019). A long line of work
has identified many algorithms, including fictitious play and regret-matching,
that converge to an equilibrium for specified classes of games (Fudenberg &
Levine, 1998; Robinson, 1951; Hart & Mas-Colell, 2000). This was subsequently
followed up by a literature that aimed to develop learning algorithms that,
additionally, satisfy other desirable properties, such as converging to a
policy that is optimal if facing a stationary opponent (Bowling & Veloso,
2002; Conitzer & Sandholm, 2007). A closely related line of work considered
_rational learning_ in which agents use Bayesian belief updates, with the
classic result by Kalai & Lehrer (1993) showing convergence of such learning
to a Nash equilibrium of the corresponding extensive form game. However, this
result requires that the distribution over histories induced by the actual
strategies is continuous with respect to the distribution induced by an
agent’s beliefs (Shoham & Leyton-Brown, 2008). This condition has been argued
to be restrictive (Nachbar, 2001) and there exists games for which such an
algorithm does not converge to Nash equilibrium (Foster & Young, 2001).

Even in the cases of equilibrium convergence in self-play, however, the
learning algorithms themselves need not constitute equilibrium behavior of the
corresponding _dynamic_ (e.g., stochastic, or repeated) game. Indeed, since
the nature of the very games under consideration is non-cooperative, insofar
as there are strong incentives for individual agents to deviate from learning
algorithms, we would expect them to do so (Vundurthy et al., 2023).

In their classic work, Brafman & Tennenholtz (2002) address this issue by
introducing the notion of a _learning equilibrium_ which requires that the
learning algorithms are rational, in the sense that self-play is a symmetric
equilibrium of the dynamic game, and proposing specific learning algorithms
that indeed constitute an equilibrium in self-play. However, they assumed a
uniform bound on game payoffs, and did not connect this equilibrium notion to
more conventional learning approaches in games, such as fictitious play or
regret matching. A natural question remains whether such conventional
approaches are already nearly in equilibrium in self-play, and if not, whether
we can induce this property in a way that is outcome-equivalent to these
algorithms in self-play (thereby satisfying whatever other desirable
properties these algorithms possess, such as no-regret learning (Greenwald et
al., 2006; Hart & Mas-Colell, 2000)).

Designing learning algorithms that are rational (i.e., constitute a near-
equilibrium) in self-play is challenging, since such algorithms may not even
exist for certain classes of games. We will see later in Theorem 4.6 that this
is indeed possible. In such cases, a quantifiable metric that characterizes
how much an agent may benefit by deviating from its learning algorithm is
required to allow the system designer to compare various learning algorithms
and choose one appropriately.

To this end, we consider a two-agent repeated game framework under an
assumption of perfect monitoring and introduce _rationality ratio_ , defined
as the ratio of the most an agent can obtain by deviating from a learning
algorithm to their payoff from following it. A learning algorithm is
$c$-rational if its rationality ratio is no more than $c$ in the worst-case.
Finally, a learning algorithm is said to be _perfectly rational_ if $c=1$. We
first establish that classic learning algorithms such as fictitious play and
regret matching algorithms are not $c$-rational for any given constant $c$. We
then provide two algorithms which, under certain conditions, are provably
perfectly rational. We also establish that there exists games for which
$c$-rational algorithms do not exist if the assumption of perfect monitoring
does not hold.

Apart from the line of literature discussed above that started from (Brafman &
Tennenholtz, 2002; Bowling & Veloso, 2002; Conitzer & Sandholm, 2007), other
works closely relevant to ours include (Jacq et al., 2020; DiGiovanni &
Tewari, 2022). However, in contrast to these works, we consider non-
cooperative agents and do not impose any assumption on the strategies followed
by the agents upon deviating from the specified algorithm.

This work is organized as follows. Section 2 reviews some basic concepts and
formally describes the model as well as the rationality ratio. Section 3
establishes that the rationality ratio of fictitious play and regret matching
algorithms is unbounded in the worst-case. Section 4 presents two algorithms
that are provably perfectly rational. Finally, Section 5 provides numerical
insights into our algorithms and Section 6 outlines some directions for future
work.

##  2 Model and Definitions

We first review some basic concepts in game theory and present the model
considered in this work. A _game_ describes an interaction among a set of
agents, wherein the rules of the game describe the order of moves by the
agents, the information available to each agent, and the final outcome for
each agent. Formally, a stage game is defined as follows.

######  Definition 2.1 (Stage Game).

A two agent stage game is a tuple
$\mathcal{G}=(A_{1},A_{2},\mathcal{R}_{1},\mathcal{R}_{2})$, where $A_{i}$,
$i\in\\{1,2\\}$, denotes a finite set of actions available to agent $i$ and
$\mathcal{R}_{i}:A_{1}\times A_{2}\to\mathbb{R}$ is a payoff function for
agent $i$. A _strategy_ $\pi_{i}$ for agent $i$ is a probability distribution
over its action set $A_{i}$. A _pure strategy_ is a strategy in which the
probability of selecting a particular action is set to one. A _mixed strategy_
is a probability distribution over pure strategies.

Following standard notation, when referring to an agent $i$, we will refer to
the other agent as the agent $-i$. Further, for simplicity, we will assume
that $\mathcal{R}_{i}>0$.

We will focus on the class of stage games for two agents that can be described
using a bi-matrix whose rows (resp. columns) correspond to the possible
actions of the first (resp. second) agent. The $(j,k)$ entry of the bi-matrix
contains a pair of values denoting the payoffs to each agent when agent 1
(resp. agent 2) plays action $j$ (resp. $k$). The payoffs corresponding to the
entry $(j,k)$ in the bi-matrix is denoted as $(r^{1}_{j,k},r^{2}_{j,k})$. When
referring to the payoffs of the agents separately, we will use $R^{1}$ and
$R^{2}$ to denote the payoff matrix of agent $1$ and agent $2$, respectively.
Thus, $r^{1}_{j,k}$ (resp. $r^{2}_{j,k}$) corresponds to the $(j,k)$ entry of
matrix $R^{1}$ (resp. $R^{2}$). Figure 1 illustrates two bi-matrix stage
games. The first is a _zero-sum_ stage game in which the sum of the payoffs of
the agents is $0$ and the second is a general sum stage game, in which the
agents are neither pure competitors nor they have identical interests.

(a) A zero-sum stage game.

(b) A general-sum stage game.

Figure 1: Illustration of two player stage games.

The agents’ strategies are in equilibrium if no agent unilaterally benefits by
changing its strategy, given the other agent’s strategy. One such equilibrium
is defined as follows.

######  Definition 2.2 (Nash Equilibrium).

A strategy profile $(\pi_{1}^{*},\pi_{2}^{*})$ is a Nash equilibrium if

$\displaystyle\mathcal{R}_{1}(\pi_{1}^{*},\pi_{2}^{*})\geq\mathcal{R}_{2}(\pi_{1},\pi_{2}^{*}),\forall\pi_{1}\neq\pi_{1}^{*},$
$\displaystyle\mathcal{R}_{2}(\pi_{1}^{*},\pi_{2}^{*})\geq\mathcal{R}_{2}(\pi_{1}^{*},\pi_{2}),\forall\pi_{2}\neq\pi_{2}^{*}.$

The pair
$(\mathcal{R}_{1}(\pi_{1}^{*},\pi_{2}^{*}),\mathcal{R}_{2}(\pi_{1}^{*},\pi_{2}^{*}))$
is known as the Nash outcome of the stage game.

Unfortunately, calculation of Nash equilibria is known to be computational
difficult. One of the commonly used model for how agents can learn these
equilibria is that of a _repeated game_. In a repeated game, the agents play a
given stage game repeatedly. At each iteration or time step of the stage game,
the agents observe their (and possibly the other agent’s) rewards and actions
from all previous iterations of the stage game. Based on the observations made
by the agent, the agent may update its strategy. An _algorithm_ for agent $i$
is a mapping from the set of possible histories $H$ to an action $a_{i}\in
A_{i}$ at every iteration.

A fundamental component of a learning algorithm is to specify what information
about the stage game is known to the agents. A payoff matrix $R^{i}$ is said
to be _completely known_ to agent $i$ if agent $i$ has the information of all
entries of $R^{i}$. Similarly, a row $j$ (resp. column $k$) of $R^{i}$ is said
to be _completely known_ to agent $i$ if agent $i$ has the information of the
all of the entries of $j$th row (resp. $k$th column) of $R^{i}$. In our work,
we assume that, in the first iteration, the agents do not have any information
about their own as well as the other agent’s payoff matrices. Instead, we
assume a _perfect monitoring_ setting in which, at each iteration or time $t$
of the stage game, an agent can observe the actions as well as the payoffs
received by both agents.

Given a repeated game formed through iterations of the stage game
$\mathcal{G}$, the _value_ for agent $1$ is defined as
$U_{1}(\mathcal{G},\mathcal{A}_{1},\mathcal{A}_{2})=\lim\inf_{T\to\infty}\mathbb{E}[\tfrac{1}{T}\sum_{t=0}^{T}\mathcal{R}_{1,t}]$,
where $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ denote the learning algorithm
followed by agent $1$ and agent $2$, respectively, and $\mathcal{R}_{1,t}$
(resp. $\mathcal{R}_{2,t}$) is the payoff received by agent $1$ (resp. agent
$2$) at time or iteration $t$ of the stage game. In what follows, to avoid
notational clutter, we will drop the dependence on $\mathcal{G}$ from the
notation of $U_{i}(\mathcal{G},\mathcal{A}_{1},\mathcal{A}_{2})$,
$i\in\\{1,2\\}$ and write the term as
$U_{i}(\mathcal{A}_{1},\mathcal{A}_{2})$. Note that
$U_{i}(\mathcal{A}_{1},\mathcal{A}_{2})>0$ given our assumption that
$\mathcal{R}_{i}>0$ for a stage game $\mathcal{G}$.

Traditionally, the learning algorithms followed by the agents are assumed to
be prescribed a priori and further often fixed to the same choice for both the
agents. Instead, we say that agent $i$ _deviates_ from a prescribed learning
algorithm $\mathcal{A}$ if agent $i$ selects its actions according to any
other algorithm $\mathcal{A}^{\prime}$ in at least one interval of times or
iterations $[t_{1},t_{2}]$ for any $t_{2}\geq t_{1}\geq 0$. Note that there
may exist more than one interval in which an agent $i$ deviates.

We now define a quantity that characterizes how much an agent $i$ gains by
deviating from a learning algorithm $\mathcal{A}$.

######  Definition 2.3 (Rationality Ratio).

Suppose agent $1$ deviates from a self-play algorithm $\mathcal{A}$ to any
algorithm $\mathcal{A}^{\prime}$. Then, the _rationality ratio_ of algorithm
$\mathcal{A}$ is defined as

$s(\mathcal{A}^{\prime},\mathcal{A})\coloneqq\frac{U_{1}(\mathcal{A}^{\prime},\mathcal{A})}{U_{1}(\mathcal{A},\mathcal{A})}.$
(1)

Further, we say that algorithm $\mathcal{A}$ is $c$-_rational_ if

$\sup_{\mathcal{G},\mathcal{A}^{\prime}}s(\mathcal{A}^{\prime},\mathcal{A})\leq
c,$ (2)

for a constant $c$. Finally, an algorithm $\mathcal{A}$ is _perfectly
rational_ if $c=1$.

The definition when agent $2$ deviates is analogous.

When $c=1$, then it means that there is no benefit for an agent to deviate
from algorithm $\mathcal{A}$.

We now review two classic self-play learning algorithms, namely fictitious
play and regret matching, that are are known to converge to the Nash and
correlated equilibria, respectively, for a wide class of games. We refer the
reader to the long line of literature starting from (Hart & Mas-Colell, 2000;
Brown, 1951) for more details on these algorithms.

In fictitious play, at each time $t$, each agent $i$ selects an action that
corresponds to the _best-response_ to the empirical frequency of the actions
played by agent $-i$. Formally,

$BR_{i}^{\text{Fict}}(\hat{\textbf{a}}_{-i}(t-1))\coloneqq\operatorname*{arg\,max}_{a\in
A_{i}}\mathcal{R}_{i}(a,\hat{\textbf{a}}_{-i}(t-1)),$ (3)

where $\hat{\textbf{a}}_{-i}(t)$ denotes the vector of empirical frequencies
of actions $a_{-i}\in A_{-i}$ played until time $t$.

To describe the regret matching algorithm, we first define the _instantaneous_
regret of agent $i$ at time $t$ for action $a\in A_{i}$ as
$\delta_{i}^{t}(a)\coloneqq\mathcal{R}_{i}(a,a_{-i}(t))-\mathcal{R}_{i}(a_{i}(t),a_{-i}(t))$.
Further, we define the average regret of agent $i$ for action $a\in A_{i}$ at
time $T$ as

$\displaystyle\delta^{\text{avg}}_{T,i}(a)\coloneqq\frac{1}{T}\sum_{t=1}^{T}\delta_{i}^{t}(a).$

Let $\delta^{\text{avg}}_{+}(a)$ denote the positive regret defined as
$\delta^{\text{avg}}_{+}(a)\coloneqq\max\\{0,\delta^{\text{avg}}_{T,i}(a)\\}$.
The regret-matching algorithm requires agent $i$ to pick an action with
probability proportional to the positive regret on that action. Specifically,
at each time $t+1$, agent $i$ selects action $a\in A_{i}$ with probabilities

$p_{t+1}^{i}(a)=\begin{cases}\frac{\delta^{\text{avg}}_{+}(a)}{\sum_{a^{\prime}\in
A_{i}}\delta^{\text{avg}}_{+}(a^{\prime})},\text{ if }\sum_{a^{\prime}\in
A_{i}}\delta^{\text{avg}}_{+}(a^{\prime})>0,\\\ \frac{1}{|A_{i}|},\text{
otherwise,}\end{cases}$ (4)

where $|\cdot|$ denotes the cardinality of a set.

##  3 Irrationality of existing self-play algorithms

The following results provide a discouraging result – some commonly used
learning algorithms are not $c$-rational for any given constant $c$. The
proofs of all of the results are contained in the Appendix.

######  Theorem 3.1.

Fictitious play algorithm is not $c$-rational for any given constant $c\geq
1$.

######  Theorem 3.2.

Regret matching algorithm is not $c$-rational for any given constant $c\geq
1$.

Given these negative results, it is natural to ask whether any $c$-rational
learning algorithms exist. Fortunately, the answer is in the affirmative. In
the next section, we will design two algorithms that are provably perfectly
rational (or equivalently $1$-rational).

##  4 Rational Learning Algorithms

We will now present two new learning algorithms and establish that they are
perfectly rational. The two algorithms, summarized in Algorithm 1 and
Algorithm 2, build upon the classical fictitious play and regret matching
algorithms, respectively. The idea behind these algorithms is to specify two
strategies. The first is a strategy that is followed by the agent $i$ as long
as agent $-i$ follows the same strategy. However, if agent $-i$ is detected to
deviate from this strategy, agent $i$ switches to a prescribed punishment
strategy. Thus, our algorithms consists of two phases; namely the self-play
phase and the punishment phase. One challenge here is that the agents do not
have any information about the payoff matrices of the stage game
$\mathcal{G}$. Thus, the self-play phase itself needs to consist of two sub-
phases called the exploration sub-phase and the exploitation sub-phase, each
of which is described below.

Exploration Sub-Phase: Since the payoff matrices are not completely known at
the start, our algorithms begin in the exploration sub-phase. In the
exploration sub-phase, every agent maintains and updates a local estimate of
the payoff matrix of the other agent. The exploration sub-phase ends once the
payoff matrices of both the agents are completely known to both the agents.
Since the exploration sub-phase is different for both our algorithms, we defer
the specific details to later when we describe the algorithms.

Exploitation Sub-Phase: The agents enter this sub-phase once the exploration
sub-phase ends and if no agent has deviated from the algorithm during the
exploration sub-phase. In this sub-phase, our first (resp. second) algorithm
selects action according to fictitious play (resp. regret-matching) and
remains in this phase until it detects that the other agent has deviated from
fictitious play (resp. regret-matching).

Punishment phase: An agent enters this phase if it detects that the other
agent has deviated from the prescribed learning algorithm. Note that this
means that the agent may enter the punishment phase either from the
exploration sub-phase or from the exploitation sub-phase. Since the punishment
strategy is common to both our algorithms, we now describe the punishment
strategy.

We start with the definition of the _minimax_ strategy which is used in the
punishment phase.

######  Definition 4.1.

The minimax value for agent $1$ on some matrix $Q$ is defined as

$\bar{V}_{1}(Q)=\min_{y\in\mathcal{Y}}\max_{z\in\mathcal{Z}}y^{\top}Qz,$ (5)

where

$\displaystyle\mathcal{Y}:=\\{y\in\mathbb{R}^{|A_{1}|}:\sum_{j}y_{j}=1,\quad
y_{j}\geq 0\forall j\\},$
$\displaystyle\mathcal{Z}:=\\{z\in\mathbb{R}^{|A_{2}|}:\sum_{k}z_{k}=1,\quad
z_{k}\geq 0\forall k\\},$

and the corresponding policy $y^{*}$ is called the minimax strategy for agent
$1$. The definitions for the minimax value and strategy for agent $2$ are
analogous.

In what follows, without loss of generality, we will assume that agent $1$
deviates and refer to it as the adversary. Further, we will denote the local
estimate of the payoff matrix of agent $1$ that agent $2$ maintains as
$\hat{R}^{1}$. Note that, when the payoff matrix of agent $1$ is completely
known by agent $2$, $\hat{R}^{1}=R^{1}$. In the punishment phase, the idea is
to _punish_ the adversary for not adhering to the algorithm. Since the
adversary can deviate from the algorithm either during the exploration sub-
phase or the exploitation sub-phase, the punishment strategy depends on when
the adversary deviates. We will first describe the punishment strategy when an
adversary deviates during the exploitation sub-phase followed by when it
deviates during the exploration sub-phase. We summarize the punishment
strategy in Algorithm 3.

Let $t$ denote the time when the punishment phase begins. Recall that in the
exploitation sub-phase, the payoff matrices $\hat{R}^{1}$ and $R^{2}$ are
completely known by agent $2$. Therefore, if the adversary deviates during the
exploitation sub-phase, the punishment strategy is to select an action for
agent $2$ by computing the minimax strategy, defined in Definition 4.1, on
matrix $\hat{R}^{1}$ and execute it for all time $\tau\geq t$. On the other
hand, if the adversary deviates during the exploration sub-phase, since the
payoff matrix $R^{1}$ of the adversary is not completely known to agent $2$,
the minimax strategy on $\hat{R}^{1}$ cannot be computed. Therefore, the idea
is to replace the payoff matrix $\hat{R}^{1}$ with a different payoff matrix
$\tilde{R}^{1}$ and execute a minimax strategy on $\tilde{R}^{1}$.
Specifically, agent $2$ constructs a payoff matrix $\tilde{R}^{1}$
corresponding to the local estimate of the adversary’s original payoff matrix
$\hat{R}^{1}$ such that the entries that are known in $\hat{R}^{1}$ are the
same in $\tilde{R}^{1}$. For the entries that are not known in $\hat{R}^{1}$,
agent $2$ substitutes those entries as $0$ in $\tilde{R}^{1}$. Then, agent $2$
selects an action with equal probability of $\frac{1}{|A_{2}|}$ until at least
one of the rows of matrix $\hat{R}^{1}$ is completely known, updating the
unknown entries matrix $\tilde{R}^{1}$ as they are revealed to the agent. Note
that in case agent $2$ deviates instead of agent $1$, then agent $1$ selects
an action with equal probability of $\frac{1}{|A_{1}|}$ until at least one of
the columns of matrix $\hat{R}^{2}$ is completely known. Once at least one of
the rows of matrix $\hat{R}^{1}$ is completely known, agent $2$ then computes
and executes the minimax strategy, defined in Defintion 4.1, on matrix
$\tilde{R}^{1}$. If no new entry of matrix $R^{1}$ is revealed, the agent
continues to play the computed minimax strategy. Otherwise, agent $2$ updates
$\hat{R}^{1}$ and $\tilde{R}^{1}$ and recomputes the minimax strategy on
$\tilde{R}^{1}$.

######  Lemma 4.2.

Let $\mathcal{A}$ denote an algorithm that consists of the punishment strategy
defined in Algorithm 3 and without loss of generality, suppose agent $1$
deviates from $\mathcal{A}$. Further, let $\bar{V}_{1}^{p}:=\min_{a_{2}\in
A_{2}}\max_{a_{1}\in A_{1}}r^{1}_{a_{1},a_{2}}$. Then, algorithm $\mathcal{A}$
is perfectly rational if the following condition holds:

$\bar{V}_{1}^{p}\leq U_{1}(\mathcal{A},\mathcal{A}).$ (6)

Lemma 4.2 ensures that by using the punishment strategy described in this
section, we can design learning algorithms that are perfectly rational.
However, we have not described how a learning algorithm detects if an agent
has deviated or not. We now present two algorithms that can detect any
deviation by an agent and incorporate the punishment strategy described in
Algorithm 3. Note that, for ease of understanding, we will describe the
algorithms for agent $2$. The description for agent $1$ is analogous.

Algorithm 1 Rational Fictitious Play (R-GFP)

Select first action in $A_{i}$.

for time $t>1$ do

if in exploration sub-phase then

Compute $E_{i}^{t}$ and select
$a_{i}^{t}=BR_{i}^{\text{Fict}}(\hat{\textbf{a}}_{-i}(t))$ on $E_{t}^{i}$.

else

Select $a_{i}^{t}=BR_{i}^{\text{Fict}}(\hat{\textbf{a}}_{-i}(t))$ on $R^{i}$.

end if

Observe the payoffs and the actions.

if Agent $-i$ deviated then

Enter Punishment Phase (Algorithm 3).

end if

end for

###  4.1 Rational Generalized Fictitious Play

In this section, we describe our first algorithm Rational Generalized
Fictitious Play (R-GFP). We start with the following definition that
generalizes the fictitious play algorithm described in Section 2.

######  Definition 4.3 (Generalized Fictitious Play (GFP)).

For a repeated game formed through iterations of the stage game $\mathcal{G}$,
let $H_{2}(t)$ denote the sequence of actions selected by agent $2$ until time
$t$. Let $h_{2}(t)\subseteq H_{2}(t)$ denote any subset of $H_{2}(t)$. Then,
the best-response $BR(\cdot)$ for agent $1$ at time $t+1$ is defined as

$BR_{1}^{\text{GFP}}(h_{2}(t))\coloneqq\arg\max_{a\in
A_{1}}R^{1}(a,\hat{\textbf{a}}_{2}(h_{2}(t))),$ (7)

where $\hat{\textbf{a}}_{2}(h_{2}(t))$ denotes the vector of empirical
frequencies of actions $a_{2}\in A_{2}$ determined by using $h_{2}(t)$.

The definition for agent $2$ is analogous. Note that when $h_{2}(t)=H_{2}(t)$,
we retrieve the fictitious play algorithm. Algorithm R-GFP is summarized in
Algorithm 1 and is described as follows.

(a) Time $t=2$.

(b) Time $t=3$.

Figure 2: Construction of matrix $E_{2}^{t}$ in Algorithm R-GFP at times $t=2$
and $t=3$.

The exploration sub-phase begins at time $t=1$. At the first time instant,
Algorithm R-GFP selects the first action in the set $A_{2}$ for agent $2$. If
any entry except the $(1,1)$ entry of matrix $R^{2}$ is revealed, then that
means that agent $1$ has deviated from the algorithm and the algorithm enters
the punishment phase. Otherwise, Algorithm R-GFP continues as follows. At each
time $1<t\leq|A_{1}||A_{2}|$, agent $2$ constructs a matrix $E_{2}^{t}$ with
all of the entries as zero except the $(j,k)$ entry, where $j=q$,
$k=t-(q-1)|A_{2}|$, $q:=\lceil\frac{t}{|A_{2}|}\rceil$, and
$\lceil\cdot\rceil$ denotes the ceil function. The $(j,k)$ entry of the payoff
matrix $E_{2}^{t}$ is set to $\mu$, where $\mu$ is any positive real
number111The quantity $\mu$ need not be same for both agents.. Then, agent $2$
selects an action according to fictitious play, defined in equation (3), on
$E_{2}^{t}$. Agent $2$ then observes its own and agent $1$’s payoff and
updates $\hat{R}^{1}$ and $R^{2}$. If at time $t$, any entry other than
$(j,k)$ entry of $R^{2}$ is revealed, Algorithm R-GFP enters the punishment
phase. Figure 2 provides an illustration of matrix $E_{2}^{t}$ for different
values of time $t$.

Once the exploration sub-phase ends, i.e., at time $t=|A_{1}||A_{2}|+1$,
Algorithm R-GFP enters the exploitation sub-phase in which agent $2$ selects
its actions according to the generalized fictitious play defined in equation
7. Agent $2$ then observes the payoffs obtained by both agents. Given that the
payoffs matrices are completely known in this sub-phase, agent $2$ then
determines whether agent $1$ deviated or not. Mathematically, agent $2$ checks
whether the following condition holds at time $t$.

$a_{1}^{t}=BR_{1}^{\text{GFP}}(h_{2}(t)).$ (8)

If equation (8) holds at time $t$, then agent $2$ continues to select action
according to equation (3) for time $t+1$. Otherwise, Algorithm R-GFP enters
the punishment phase.

To determine if agent $1$ deviated at time $t$, agent $2$ requires the
information of $h_{2}(t)$ that agent $1$ considers. This can be achieved by
keeping $h_{i}(t),i\in\\{1,2\\}$ for both agents same, such as in fictitious
play.

######  Theorem 4.4.

Let $\pi_{1}^{*}$ and $\pi_{2}^{*}$ denote the strategies of agent $1$ and
agent $2$, respectively, if they selected actions according to generalized
fictitious play defined in Definition 4.3. Then,

  1. 1.

Algorithm R-GFP is perfectly rational if the condition defined in equation (6)
holds.

  2. 2.

If $\pi_{1}^{*}$ and $\pi_{2}^{*}$ converge to an equilibrium then, the
strategies of the agents obtained when they follow Algorithm R-GFP also
converge to an equilibrium.

Algorithm 2 Rational Regret Matching (R-RM)

Input: $\delta\in(0,1)$.

Select first action in $A_{i}$.

for epoch $t>1$ do

if in exploration sub-phase then

Compute $E_{t}^{i}$ and select $a_{i}^{t}$ according to equation (11).

else

Compute the probability distribution over actions $a_{i}$ according to
equation (4).

Compute $N_{t}$ and $\epsilon_{t}$.

for $n\leq N_{t}$ do

Select $a_{i}^{t}$ according to the computed probability distribution.

Observe agent $\mathcal{P}_{-i}$’s actions.

end for

end if

if Agent $\mathcal{P}_{-i}$ deviated then

Enter Punishment Phase (Algorithm 3).

end if

end for

Algorithm 3 Strategy for Punishment Phase

Assumes agent $1$ deviates.

for time $t\geq 1$ do

if matrix $\hat{R}^{1}$ is completely known to agent $2$ then

Select minimax strategy (Defintion 4.1) on $\hat{R}^{1}$.

else

Construct matrix $\tilde{R}^{1}$.

Select minimax strategy (Defintion 4.1) on $\tilde{R}^{1}$.

Update matrix $\hat{R}^{1}$ and $\tilde{R}^{1}$ if new entry is revealed.

end if

end for

###  4.2 Rational Regret Matching

We now describe our second algorithm which, with high probability, is also
perfectly rational. The idea behind Algorithm Rational Regret Matching (R-RM)
is similar to that of Algorithm R-GFP. Specifically, during the exploitation
sub-phase, agent $2$ selects an action according to regret-matching described
in Section 2 and checks whether agent $1$ has deviated or not. However, recall
from Section 2, that there is a probability distribution over the actions in
regret matching algorithm. Thus, to determine whether agent $1$ has deviated,
agent $2$ must compare the probability distribution over the actions selected
by agent $1$ with the probability distribution over the actions that agent $1$
must have selected its actions from. To achieve this, Algorithm R-RM runs in
epochs consisting of a finite number of iterations. We summarize Algorithm
R-RM in Algorithm 2 and describe it in greater detail below.

In the first epoch, Algorithm R-RM selects the first action from the set
$A_{2}$. If any entry except the $(1,1)$ entry of matrix $R^{2}$ is revealed,
then the algorithm enters the punishment phase. Otherwise, the algorithm
continues as follows.

In every epoch $t$, $1<t\leq|A_{1}||A_{2}|$, agent $2$ constructs a matrix
$E_{2}^{t}$ in which, excluding at most two entries, all other entries are
zero. Denote the two non-zero entries as $(j_{1},k_{1})$ and $(j_{2},k_{2})$.
Let $q:=\lceil\frac{t}{|A_{2}|}\rceil$. Then, entry $(j_{1},k_{1})$ is set to
$\mu>0$ and is defined as follows.

$\displaystyle j_{1}=\begin{cases}\max\\{1,(q-1)\\},\text{ if
}t=(q-1)|A_{2}|+1,\\\ q,\text{ otherwise.}\end{cases}$ (9) $\displaystyle
k_{1}=\begin{cases}1,\text{ if }t=(q-1)|A_{2}|+1,\\\ t-|A_{2}|(q-1),\text{
otherwise.}\end{cases}$ (10)

Entry $(j_{2},k_{2})$ is set to $\nu>0$ if $t=(q-1)|A_{2}|+1$ and zero
otherwise, where $j_{2}=q$ and $k_{2}=|A_{2}|$.

(a) Time $t=2$.

(b) Time $t=4$.

Figure 3: Construction of $E_{2}^{t}$ at epoch $t=2$ and $t=4$ for Algorithm
R-RM.

Figure 3 provides an illustration of matrix $E_{2}^{t}$ for different epochs
$t$. Once matrix $E_{2}^{t}$ is determined, agent $2$ selects an action
proportional to the instantaneous regret determined on $E_{2}^{t}$. Formally,
the instantaneous regret for epoch $t$ for agent $2$ for action $a\in A_{2}$
is $\delta_{2}^{t}(a)=e^{2}_{a_{1}^{t},a}-e^{2}_{a_{1}^{t},a_{2}^{t}}$, where
$e^{2}_{i,j}$ denotes the $(i,j)$ entry of $E_{2}^{t}$. Agent $2$ then selects
action $a\in A_{2}$ with probabilities

$\displaystyle
p_{t+1}^{2}(a)=\begin{cases}\frac{\delta_{+}(a)}{\sum_{a^{\prime}\in
A_{2}}\delta_{+}(a^{\prime})},\text{ if }\sum_{a^{\prime}\in
A_{2}}\delta_{+}(a^{\prime})>0,\\\ a_{2}(t-1),\text{ otherwise,}\end{cases}$
(11)

where $\delta_{+}(a)\coloneqq\max\\{0,\delta_{2}^{t}(a)\\}$. Similar to
Algorithm R-GFP, the exploration sub-phase in Algorithm R-RM ensures that the
payoffs of the original matrices is revealed sequentially to the agent. Thus,
if agent $1$ deviates from Algorithm R-RM during the exploration sub-phase, it
is guaranteed to be detected by agent $2$. Once the exploration phase ends,
the Algorithm R-RM enters the exploitation sub-phase.

During the exploitation sub-phase, at the start of epoch $t>|A_{1}||A_{2}|+1$
and since the payoff matrices are completely known, Algorithm R-RM determines
the probability distribution over the actions of agent $2$ as well as agent
$1$ by using equation (4). Let $\phi_{t}^{1}$ and $\phi_{t}^{2}$ denote the
probability distribution over the actions from which agent $1$ and agent $2$,
respectively, must choose their actions from, if they were following the
regret matching algorithm. Every epoch $t$ consists of $N_{t}$ iterations,
where $N_{t}$ will be determined shortly. In every iteration $n\leq N_{t}$ of
epoch $t$, agent $2$ selects action according to $\phi^{2}_{t}$, and observes
the action selected by agent $1$. Once the epoch ends, i.e., after $N_{t}$
iterations, agent $2$ determines the empirical cumulative distribution
function (CDF) from the observed actions of agent $1$. Formally, let
$a_{l},l\in\\{1,\dots,N_{t}\\}$, be the actions of agent $1$ observed by agent
$2$ in epoch $t$. Then, the empirical CDF $F_{t}^{1}$ over the actions of
agent $1$ computed by agent $2$ after epoch $t$ is defined as

$F_{t}^{1}(x)=\frac{1}{N_{t}}\sum_{i=1}^{N_{t}}\textbf{1}_{\\{a_{i}\leq
x\\}},~{}x\in\mathbb{R}.$ (12)

Let $\mathcal{F}_{t}^{1}(x)$ denote the CDF determined using
$\phi_{t}^{1}(a)$. Then, after computing the empirical CDF, Algorithm R-RM
checks whether the following condition holds at the end of epoch $t$:

$\displaystyle\sup_{x\in\mathbb{R}}|\mathcal{F}_{t}^{1}(x)-F_{t}^{1}(x)|>\epsilon_{t},$
(13)

where $\epsilon_{t}=\tfrac{1}{t}$. If condition (13) holds, Algorithm R-RM
proceeds to the next epoch $t+1$. Otherwise, Algorithm R-RM enters the
punishment phase.

Algorithm R-RM sets
$N_{t}=\frac{c_{1}\log(\frac{c_{2}t}{\delta})}{\epsilon^{2}_{t}}$, where
$\delta\in(0,1)$ is an input to Algorithm R-RM and $c_{1}>0$ and $c_{2}>1$ are
some real numbers satisfying $2\geq c_{2}t^{2c_{1}-1}$. Although the choice of
$N_{t}$ will be clear from the proof of Theorem 4.5, we provide an intuition
behind this choice. On one hand, we require that in case agent $1$ does not
deviate from Algorithm R-RM, the equilibrium strategies of Algorithm R-RM
converge to that of when the agents would have selected actions according to
the regret matching algorithm. To achieve this, we must ensure that the
condition defined in equation (13) holds with very low probability (almost
$0$), when agent $1$ does not deviate. On the other hand, in case agent $1$
deviates, we require that Algorithm R-RM enters the punishment phase. Thus,
motivated from (Conitzer & Sandholm, 2007), we select $N_{t}$ (resp.
$\epsilon_{t}$) such that it increases (resp. decreases) in every epoch $t$.

######  Theorem 4.5.

Let $\pi_{1}^{*}$ and $\pi_{2}^{*}$ denote the strategies of agent $1$ and
agent $2$, respectively, if they selected actions according to regret-
matching. Then, for a given $\delta\in(0,1)$,

  1. 1.

Algorithm R-RM is perfectly rational if the condition defined in equation (6)
holds..

  2. 2.

If $\pi_{1}^{*}$ and $\pi_{2}^{*}$ converge to an equilibrium then, with
probability $1-\delta$, the strategies of the agents converge to an
equilibrium if they follow Algorithm R-RM.

We now conclude this work by establishing that, for any given constant $c$, a
$c$-rational algorithm may not always exist in case of _imperfect monitoring_
, i.e., when an agent can observe the actions of the other agent but not its
payoffs.

######  Theorem 4.6.

Under imperfect monitoring, there exist classes of games for which no
algorithm is $c$-rational for any $c\geq 1$.

For certain classes of games such as zero-sum games or common interest games,
a $c$-rational algorithm may exist under imperfect monitoring. This is
because, in these classes of games, the payoff of the agent $i$ provides
information about the payoffs of agent $-i$ as well.

##  5 Numerical Results

We now provide numerical results to illustrate the analytical results
established in Theorems 4.4 and 4.5. Note that when agent $i$ deviates during
the exploration (resp. exploitation) sub-phase, then the algorithm followed by
agent $i$ is denoted as $\mathcal{A}^{\prime}_{\text{explore}}$ (resp.
$\mathcal{A}^{\prime}$). The constants $c_{1}$, $c_{2}$, and $\delta$ were
selected to be $\tfrac{9}{8}$, $8$, and $0.01$, respectively. Further, all of
our numerical results represents the mean over $50$ runs.

Figure 4: Numerical plot illustrating value of agent $1$ (adversary) over
time. Figure 5: Game used for the numerical results in Figure 4.

Figure 4 illustrates the value of agent $1$ in four cases: (a) when both
agents follow Algorithm R-GFP, (b) when agent $1$ deviates and agent $2$
follows fictitious play (FP), (c) when agent $1$ deviates during exploitation
sub-phase and agent $2$ follows Algorithm R-GFP, and (d) when agent $1$
deviates during exploration sub-phase and agent $2$ follows Algorithm R-GFP.
In all of these cases, the agents utilize the entire history, i.e.,
$h_{i}(t)=H_{i}(t)$, and thus, the generalized fictitious play is equivalent
to fictitious play (FP). An optimal strategy for an adversary against
fictitious play was determined in (Vundurthy et al., 2023). Thus, upon
deviation, agent $1$ follows the strategy described in (Vundurthy et al.,
2023). The game is illustrated in Figure 5 and has three Nash equilibria with
Nash outcomes $(6,10)$, $(8.33,7.83)$, and $(6.66,7.3)$.

The strategies obtained for agent $1$ and agent $2$ when they both follow
Algorithm R-GFP is $\begin{bmatrix}0.167&0.833\end{bmatrix}^{\top}$ and
$\begin{bmatrix}0&0.167&0.833\end{bmatrix}^{\top}$, respectively,
corresponding to the Nash outcome of $(8.3,7.83)$. The curve obtained for
$U_{2}(\text{FP},\text{FP})$ is analogous to that of
$U_{2}(\text{R-GFP},\text{R-GFP})$ and thus has not been shown in Figure 4.
From Figure 4, the value $U_{1}(\mathcal{A}^{\prime},\text{FP})$ of agent $1$
is higher than that of $U_{1}(\text{FP},\text{FP})$ meaning that there is
benefit for agent $1$ to deviate from fictitious play. However,
$U_{1}(\mathcal{A}^{\prime},\text{R-GFP})<U_{1}(\text{R-GFP},\text{R-GFP})$
meaning that there is no benefit for agent $1$ to deviate from Algorithm R-GFP
as characterized in Theorem 4.4. Finally, note that for low values of time,
$U_{1}(\mathcal{A}^{\prime}_{\text{explore}},\text{R-GFP})<U_{1}(\mathcal{A}^{\prime},\text{R-GFP})$
and as $t\to\infty$,
$U_{1}(\mathcal{A}^{\prime}_{\text{explore}},\text{R-GFP})\to
U_{1}(\mathcal{A}^{\prime},\text{R-GFP})$. This is because, as time increases,
matrix $R^{1}$ is completely known by agent $1$ and thus, the minimax value is
same in both cases.

Figure 6: Numerical plot illustrating value of agent $2$ (adversary) over
time. regret-matching is denoted as RM. Figure 7: Game used for numerical
result in Figure 6.

Figure 6 illustrates the value of agent $2$ in four cases as described for
Figure 4. Upon deviation, agent $2$ follows the strategy described as follows:

$a_{2}^{*}=\operatorname*{arg\,max}_{a_{2}\in A_{2}}R^{2}(BR(a_{2}),a_{2}),$
(14)

where $BR(a_{2}):=\operatorname*{arg\,max}_{a_{1}\in
A_{1}}R^{1}(a_{1},a_{2})$. Note that the strategy defined in equation (14) may
not be optimal. For instance, $U_{2}(RM,\mathcal{A}^{\prime})=14.9$, where
$\mathcal{A}^{\prime}$ is defined in equation (14). However, by considering a
mixed strategy as $\begin{bmatrix}0.15&0.85&0\end{bmatrix}^{\top}$ for agent
$2$ yields a higher payoff of $17.3$. When agent $1$ follows regret-matching
(RM) and agent $2$ deviates,
$U_{2}(\text{RM},\mathcal{A}^{\prime})>U_{2}(\text{RM},\text{RM})$ implying
that by deviating from regret-matching, agent $2$ can obtain a higher value.
Since $U_{2}(\text{RM},\text{RM})=U_{2}(\text{R-RM},\text{R-RM})$, the curve
for $U_{2}(\text{RM},\text{RM})$ is not shown in Figure 6. However,
$U_{2}(\text{R-RM},\mathcal{A}^{\prime})<U_{2}(\text{R-RM},\text{R-RM})$ and
$U_{2}(\text{R-RM},\mathcal{A}^{\prime}_{\text{explore}})<U_{2}(\text{R-RM},\text{R-RM})$
implying that Algorithm R-RM is perfectly rational. Finally, since the
strategy followed by agent $2$ does not change once agent $1$ follows minimax
strategy, $U_{2}(\text{R-RM},\mathcal{A}^{\prime}_{\text{explore}})$ is
approximately the same as $U_{2}(\text{R-RM},\mathcal{A}^{\prime})$.

We provide additional numerical results in the Appendix for various games to
illustrate the results for both Algorithm R-GFP and Algorithm R-RM.

##  6 Conclusion

In this work, we considered a two-agent non-cooperative repeated game
framework and introduced rationality ratio, which is a ratio of the most an
agent can obtain by deviating from a learning algorithm to their payoff from
following it under an assumption of perfect monitoring. A learning algorithm
is called $c$-rational if its rationality ratio is at most $c$. We first
established that fictitious play and regret-matching algorithm are not
$c$-rational for any given constant $c$ and then presented two algorithms that
are provably $1$-rational. Finally, we established that there exists classes
of games in which a $c$-rational algorithm does not exist under imperfect
monitoring.

Our algorithms extends to the case of $n$ agents when at most one agent can
deviate. If more than one agent can deviate, the possibility of collusion
arises which will be considered in the future. Apart from designing
$c$-rational algorithms under imperfect monitoring (for classes of games in
which they might exist), generalization to stochastic games is another
potential future direction of this work.

##  7 Impact Statement

This paper presents work whose goal is to advance the field of non-cooperative
multi-agent reinforcement learning. There are many potential societal
consequences of our work. For instance, given the importance of learning
algorithms in digital and financial markets, this work is useful in reducing
the exploitability of learning algorithms in strategic situations.

## References

  * Adler & Blue (2002) Adler, J. L. and Blue, V. J.  A cooperative multi-agent transportation management and route guidance system.  _Transportation Research Part C: Emerging Technologies_ , 10(5-6):433–454, 2002.
  * Bashendy et al. (2023) Bashendy, M., Tantawy, A., and Erradi, A.  Intrusion response systems for cyber-physical systems: A comprehensive survey.  _Computers & Security_, 124:102984, 2023.
  * Baudin & Laraki (2022) Baudin, L. and Laraki, R.  Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games.  In _International Conference on Machine Learning_ , pp. 1664–1690. PMLR, 2022.
  * Berger (2005) Berger, U.  Fictitious play in 2$\times$ n games.  _Journal of Economic Theory_ , 120(2):139–154, 2005.
  * Bowling & Veloso (2002) Bowling, M. and Veloso, M.  Multiagent learning using a variable learning rate.  _Artificial intelligence_ , 136(2):215–250, 2002.
  * Brafman & Tennenholtz (2002) Brafman, R. and Tennenholtz, M.  Efficient learning equilibrium.  _Advances in Neural Information Processing Systems_ , 15, 2002.
  * Brown (1951) Brown, G. W.  Iterative solution of games by fictitious play.  _Act. Anal. Prod Allocation_ , 13(1):374, 1951.
  * Chasnov et al. (2019) Chasnov, B., Ratliff, L. J., Mazumdar, E., and Burden, S. A.  Convergence analysis of gradient-based learning with non-uniform learning rates in non-cooperative multi-agent settings.  _arXiv preprint arXiv:1906.00731_ , 2019.
  * Choi et al. (2009) Choi, J., Oh, S., and Horowitz, R.  Distributed learning and cooperative control for multi-agent systems.  _Automatica_ , 45(12):2802–2814, 2009.
  * Conitzer & Sandholm (2007) Conitzer, V. and Sandholm, T.  Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents.  _Machine Learning_ , 67:23–43, 2007.
  * Cui et al. (2020) Cui, J., Liu, Y., and Nallanathan, A.  Multi-agent reinforcement learning-based resource allocation for uav networks.  _IEEE Transactions on Wireless Communications_ , 19(2):729–743, 2020.  doi: 10.1109/TWC.2019.2935201.
  * DiGiovanni & Tewari (2022) DiGiovanni, A. and Tewari, A.  Balancing adaptability and non-exploitability in repeated games.  In _Uncertainty in Artificial Intelligence_ , pp. 559–568. PMLR, 2022.
  * Foster & Young (2001) Foster, D. P. and Young, H. P.  On the impossibility of predicting the behavior of rational agents.  _Proceedings of the National Academy of Sciences_ , 98(22):12848–12853, 2001.
  * Fudenberg & Levine (1998) Fudenberg, D. and Levine, D. K.  _The theory of learning in games_ , volume 2.  MIT press, 1998.
  * Greenwald et al. (2006) Greenwald, A., Li, Z., and Marks, C.  Bounds for regret-matching algorithms.  In _AI &M_, 2006.
  * Hart & Mas-Colell (2000) Hart, S. and Mas-Colell, A.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5):1127–1150, 2000.
  * Hespanha (2017) Hespanha, J. P.  _Noncooperative game theory: An introduction for engineers and computer scientists_.  Princeton University Press, 2017.
  * Hu et al. (1998) Hu, J., Wellman, M. P., et al.  Multiagent reinforcement learning: theoretical framework and an algorithm.  In _ICML_ , volume 98, pp. 242–250, 1998.
  * Jacq et al. (2020) Jacq, A., Perolat, J., Geist, M., and Pietquin, O.  Foolproof cooperative learning.  In _Asian Conference on Machine Learning_ , pp. 401–416. PMLR, 2020.
  * Jafari et al. (2001) Jafari, A., Greenwald, A., Gondek, D., and Ercal, G.  On no-regret learning, fictitious play, and Nash equilibrium.  In _ICML_ , volume 1, pp. 226–233, 2001.
  * Kalai & Lehrer (1993) Kalai, E. and Lehrer, E.  Rational learning leads to nash equilibrium.  _Econometrica: Journal of the Econometric Society_ , pp. 1019–1045, 1993.
  * Kosorok (2008) Kosorok, M. R.  _Introduction to empirical processes and semiparametric inference_ , volume 61.  Springer, 2008.
  * Lee et al. (2007) Lee, J. W., Park, J., Jangmin, O., Lee, J., and Hong, E.  A multiagent approach to $q$-learning for daily stock trading.  _IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans_ , 37(6):864–877, 2007.
  * Leslie & Collins (2006) Leslie, D. S. and Collins, E. J.  Generalised weakened fictitious play.  _Games and Economic Behavior_ , 56(2):285–298, 2006.
  * Littman (1994) Littman, M. L.  Markov games as a framework for multi-agent reinforcement learning.  In _Machine learning proceedings 1994_ , pp. 157–163. Elsevier, 1994.
  * Lowe et al. (2017) Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Advances in neural information processing systems_ , 30, 2017.
  * Monderer & Shapley (1996) Monderer, D. and Shapley, L. S.  Fictitious play property for games with identical interests.  _Journal of economic theory_ , 68(1):258–265, 1996.
  * Nachbar (2001) Nachbar, J. H.  Bayesian learning in repeated games of incomplete information.  _Social Choice and Welfare_ , 18:303–326, 2001.
  * Nguyen et al. (2019) Nguyen, K. K., Duong, T. Q., Vien, N. A., Le-Khac, N.-A., and Nguyen, M.-N.  Non-cooperative energy efficient power allocation game in d2d communication: A multi-agent deep reinforcement learning approach.  _IEEE Access_ , 7:100480–100490, 2019.
  * Nudelman et al. (2004) Nudelman, E., Wortman, J., Shoham, Y., and Leyton-Brown, K.  Run the gamut: A comprehensive approach to evaluating game-theoretic algorithms.  In _AAMAS_ , volume 4, pp. 880–887, 2004.
  * Orr & Dutta (2023) Orr, J. and Dutta, A.  Multi-agent deep reinforcement learning for multi-robot applications: a survey.  _Sensors_ , 23(7):3625, 2023.
  * Robinson (1951) Robinson, J.  An iterative method of solving a game.  _Annals of mathematics_ , pp. 296–301, 1951.
  * Sayin et al. (2022) Sayin, M. O., Parise, F., and Ozdaglar, A.  Fictitious play in zero-sum stochastic games.  _SIAM Journal on Control and Optimization_ , 60(4):2095–2114, 2022.
  * Shoham & Leyton-Brown (2008) Shoham, Y. and Leyton-Brown, K.  _Multiagent systems: Algorithmic, game-theoretic, and logical foundations_.  Cambridge University Press, 2008.
  * Vundurthy et al. (2023) Vundurthy, B., Kanellopoulos, A., Gupta, V., and Vamvoudakis, K. G.  Intelligent players in a fictitious play framework.  _IEEE Transactions on Automatic Control_ , 2023.
  * Yang & Wang (2020) Yang, Y. and Wang, J.  An overview of multi-agent reinforcement learning from game theoretical perspective.  _arXiv preprint arXiv:2011.00583_ , 2020.
  * Zhang et al. (2021a) Zhang, K., Yang, Z., and Başar, T.  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  _Handbook of reinforcement learning and control_ , pp. 321–384, 2021a.
  * Zhang et al. (2021b) Zhang, T., Ye, Q., Bian, J., Xie, G., and Liu, T.-Y.  Mfvfd: A multi-agent q-learning approach to cooperative and non-cooperative tasks.  In _IJCAI_ , pp. 500–506, 2021b.

##  Appendix A Proof of Theorem 3.1

Figure 8: A $2\times 3$ game $\mathcal{G}$ for the proof of Theorem 3.1. Pure
Nash equilibrium, highlighted in bold, is entry $(1,1)$.

###### Proof.

Without loss of generality, suppose that agent $2$ deviates from fictitious
play and let $\mathcal{A}^{\prime}$ denote the algorithm followed by agent
$1$. Further, let $\mathcal{A}$ denote the fictitious play algorithm. The idea
behind this proof is to show that there exists a game $\mathcal{G}$ and
algorithm $\mathcal{A}^{\prime}$, such that the condition defined in equation
(2) does not hold for any given constant $c$. We start by describing a game
$\mathcal{G}$.

Consider a $2\times 3$ bi-matrix game $\mathcal{G}$, as illustrated in Figure
8. The payoff $r^{2}_{2,3}$ in $\mathcal{G}$ is set to $r^{2}_{2,3}=10(c+1)$
and $r^{2}_{2,2}$ is any real number satisfying $r^{2}_{2,2}>r^{2}_{2,3}$.
Note that entry $(1,1)$ corresponds to the Nash equilibrium of $\mathcal{G}$.
Since fictitious play is known to converge to the Nash equilibrium in the
class of non-degenerate ordinal potential games (Berger, 2005), it is ensured
that when both agents follow algorithm $\mathcal{A}$ on $\mathcal{G}$, the
strategies converge to the Nash equilibrium. This implies that
$U_{2}(\mathcal{A},\mathcal{A})=10$.

We now describe algorithm $\mathcal{A}^{\prime}$ that agent $2$ follows.
Algorithm $\mathcal{A}^{\prime}$, for each time $t$, has agent $2$ select
column $k=3$. We will now show that, for algorithm $\mathcal{A}$ and a given
constant $c$, equation (2) does not hold.

Let $H_{2}(t)=\\{k,k,\dots,k\\}$ denote the sequence of actions selected by
agent $2$ until the current time $t$. As the action of agent $2$ does not
change at any time $t$, it follows that
$\hat{\textbf{a}}_{2}(t)=\begin{bmatrix}0&0&1\end{bmatrix}$. Given game
$\mathcal{G}$ as defined in Figure 8 and since agent $1$ follows fictitious
play, it follows that as $t\to\infty$, agent $1$ selects row $j=2$ as
determined from equation (3). This yields that
$U_{2}(\mathcal{A},\mathcal{A}^{\prime})=r^{2}_{2,3}$. Since
$r^{2}_{2,3}=10(c+1)$, it follows that

$\displaystyle\frac{U_{2}(\mathcal{A},\mathcal{A}^{\prime})}{U_{2}(\mathcal{A},\mathcal{A})}=c+1\implies\sup_{\mathcal{G},\mathcal{A}^{\prime}}\frac{U_{2}(\mathcal{A},\mathcal{A}^{\prime})}{U_{2}(\mathcal{A},\mathcal{A})}\geq
c+1.$

This further implies that the condition in equation (2) can never hold for any
given constant $c$. This concludes the proof. ∎

##  Appendix B Proof of Theorem 3.2

Figure 9: A $2\times 2$ game $\mathcal{G}$ for the proof of Theorem 3.1. For
any $r^{1}_{2,1}>r^{1}_{1,1}$, entry $(2,2)$ is the Nash equilibrium.

###### Proof.

Without loss of generality, suppose agent $1$ deviates from regret matching
algorithm and let $\mathcal{A}^{\prime}$ denote the algorithm followed by
agent $1$. Further, let $\mathcal{A}$ denote the regret matching algorithm.
Similar to the proof of Theorem 3.1, we start by describing a game
$\mathcal{G}$ followed by an Algorithm $\mathcal{A}^{\prime}$ for agent $1$ on
$\mathcal{G}$.

Consider a $2\times 2$ bi-matrix game $\mathcal{G}$ as shown in Figure 9 with
entry $r^{1}_{1,1}=5(c+1)$ and $r^{1}_{2,1}>r^{1}_{1,1}$. It is known that no
regret algorithms, such as regret matching, converge to the pure Nash
equilibrium in general sum $2\times 2$ game (Jafari et al., 2001). Thus, when
both agents follow algorithm $\mathcal{A}$, the strategies converge to the
pure Nash equilibrium, i.e., $(2,2)$ entry leading to the Nash outcome of
$(5,5)$. Thus, $U_{1}(\mathcal{A},\mathcal{A})=5$.

Now consider Algorithm $\mathcal{A}^{\prime}$ which, at each time $t$, has
agent agent $1$ play row $j=1$. We now show that, for algorithm $\mathcal{A}$
and a given constant $c$, equation (2) does not hold.

Suppose that at time $t$, agent $2$ selects action $k=1$. Given game
$\mathcal{G}$ in Figure 9, the instantaneous regret for agent $2$ for not
selecting column $k=2$ is

$\displaystyle\delta_{2}^{t}(2)=r^{2}_{1,2}-r^{2}_{1,1}=-1.$

Similarly, at time $t$, if agent $2$ selects action $k=2$, then the
instantaneous regret for agent $2$ for not selecting column $k=1$ is

$\displaystyle\delta_{2}^{t}(1)=r^{2}_{1,1}-r^{2}_{1,2}=1.$

Since the action of agent $1$ does not change at any time $t$, it follows that
at every time $t$ at which agent $2$ selected column $2$, agent $2$
experienced a positive regret. Thus, as $t\to\infty$, from equation (4),
$p_{t+1}^{2}(1)\to 1$. This implies that
$U_{1}(\mathcal{A}^{\prime},\mathcal{A})=r^{1}_{1,1}$. Since
$r^{1}_{1,1}=5(c+1)$ it follows that

$\displaystyle\frac{U_{1}(\mathcal{A}^{\prime},\mathcal{A})}{U_{1}(\mathcal{A},\mathcal{A})}=c+1\implies\sup_{\mathcal{G},\mathcal{A}^{\prime}}\frac{U_{1}(\mathcal{A}^{\prime},\mathcal{A})}{U_{1}(\mathcal{A},\mathcal{A})}\geq
c+1.$

This means that the condition in equation (2) can never hold for any given
constant $c$ and the result is established. ∎

##  Appendix C Proof of Lemma 4.2

###### Proof.

Without loss of generality, suppose that agent $1$ deviates from algorithm
$\mathcal{A}$. First, consider that algorithm $\mathcal{A}$ enters the
punishment phase from the exploitation sub-phase. Then, agent $2$ selects
action according to the minimax strategy, defined in Definition 4.1, on matrix
$\hat{R}^{1}=R^{1}$. As $t\to\infty$,
$U_{1}(\mathcal{A}^{\prime},\mathcal{A})\to\bar{V}_{1}(\hat{R}^{1})$. Since
$\bar{V}_{1}^{p}(\hat{R}^{1})\geq\bar{V}_{1}(\hat{R}^{1})$ (Hespanha, 2017)
and given the condition in equation (6), we obtain

$\frac{U_{1}(\mathcal{A}^{\prime},\mathcal{A})}{U_{1}(\mathcal{A},\mathcal{A})}=\frac{\bar{V}_{1}(R^{1})}{U_{1}(\mathcal{A},\mathcal{A})}\leq\frac{\bar{V}_{1}^{p}(R^{1})}{U_{1}(\mathcal{A},\mathcal{A})}\leq
1.$ (15)

Note that equation (15) holds even in the case when algorithm $\mathcal{A}$
enters the punishment phase from the exploration sub-phase and there exists a
time $t$ at which the matrix $R^{1}$ is completely known by agent $2$. Further
note that, in the case when none of the rows of the payoff matrix $R^{1}$ is
completely known by agent $2$, at any time $t$, there is a positive
probability that a new entry of $R^{1}$ will be known. This implies that there
exists a time $t$ at which at least one of the row of matrix $R^{1}$ will be
completely known by agent $2$. Thus, in what follows, we will consider the
case for which the following jointly holds:

  * •

P1: algorithm $\mathcal{A}$ enters the punishment phase from the exploration
sub-phase,

  * •

P2: at least one of the rows of $R^{1}$ is completely known by agent $2$, and

  * •

P3: the matrix $R^{1}$ is not completely known by agent $2$ at any time $t$.

Without loss of generality, let the $j$th row of matrix $R^{1}$ be completely
known to agent $2$. Given P3, let $\tau$ denote the time when an entry of
matrix $R^{1}$ was revealed and no other entry of matrix $R^{1}$ is revealed
for any time $t>\tau$. Further, as $t\to\infty$ and since no new entry of
$R^{1}$ is revealed after time $\tau$,
$U_{1}(\mathcal{A}^{\prime},\mathcal{A})\to\bar{V}_{1}(\tilde{R}^{1})$.

Since $\bar{V}_{1}^{p}(\tilde{R}^{1})\geq\bar{V}_{1}(\tilde{R}^{1})$
(Hespanha, 2017), we now show that
$\bar{V}_{1}^{p}(\tilde{R}^{1})\leq\bar{V}_{1}^{p}(R^{1})$. Suppose that entry
$(j^{\prime},k)$ for any $j^{\prime}\neq j$ of matrix $R^{1}$ is not known by
agent $2$. Let $\tilde{R}^{1}_{j^{\prime}}$ denote the matrix if the entry
$(j^{\prime},k)$ was known by agent $2$. Then, if
$r^{1}_{j^{\prime},k}>r^{1}_{j,k}$, it follows that
$\bar{V}_{1}^{p}(\tilde{R}^{1}_{j^{\prime}})>\bar{V}_{1}^{p}(\tilde{R}^{1})$.
This is because the entry $r^{1}_{j^{\prime},k}=0$ in matrix $\tilde{R}^{1}$.
Further, if $r^{1}_{j^{\prime},k}\leq r^{1}_{j,k}$, it follows that
$\bar{V}_{1}^{p}(\tilde{R}^{1}_{j^{\prime}})=\bar{V}_{1}^{p}(\tilde{R}^{1})$.
Thus, for any $(j^{\prime},k)$ entry that is not known by agent $2$, we have
$\bar{V}_{1}^{p}(\tilde{R}^{1}_{j^{\prime}})\geq\bar{V}_{1}^{p}(\tilde{R}^{1})$
which further implies that
$\bar{V}_{1}^{p}(R^{1})\geq\bar{V}_{1}^{p}(\tilde{R}^{1})$. Given the
condition that $\bar{V}_{1}^{p}(R^{1})\leq U_{1}(\mathcal{A},\mathcal{A})$, we
obtain

$\displaystyle\frac{\bar{V}_{1}(\tilde{R}^{1})}{U_{1}(\mathcal{A},\mathcal{A})}\leq\frac{\bar{V}_{1}^{p}(\tilde{R}^{1})}{U_{1}(\mathcal{A},\mathcal{A})}\leq\frac{\bar{V}_{1}^{p}(R^{1})}{U_{1}(\mathcal{A},\mathcal{A})}\leq
1.$

This concludes the proof. ∎

##  Appendix D Proof of Theorem 4.4

###### Proof.

Without loss of generality, suppose agent $1$ deviates from Algorithm R-GFP.
From the definition of Algorithm R-GFP and given the perfect monitoring
setting, any deviation is ensured to be detected. Thus, it is ensured that the
algorithm enters the punishment phase once agent $1$ deviates. Thus, from
Lemma 4.2, Algorithm R-GFP is perfectly rational.

If none of the agents deviate, after time $t=|A_{1}||A_{2}|$, Algorithm R-GFP
enters exploitation phase. In the exploitation phase, the agents select their
actions according to fictitious play for all time $t>|A_{1}||A_{2}|$. This
implies that the corresponding strategies of the agents following Algorithm
R-GFP will be the same as when the agents follow fictitious play and the
result follows. ∎

##  Appendix E Proof of Theorem 4.5

The following result will be useful in the proof.

######  Lemma E.1 (Dvoretzky–Kiefer–Wolfowitz inequality(Kosorok, 2008)).

Given a natural number $n$, let $X_{1},X_{2},\dots,X_{n}$ be independent and
identically distributed random variables with CDF $\mathcal{F}$. Let $F_{n}$
denote the associated empirical distribution function defined by

$\displaystyle F_{n}(x)=\frac{1}{n}\sum_{i=1}^{n}\textbf{1}_{\\{X_{i}\leq
x\\}}.$

Then,

$\displaystyle
Pr\left(\sup_{x\in\mathbb{R}}|\mathcal{F}(x)-F_{n}(x)|>\epsilon\right)\leq
2e^{-2n\epsilon^{2}},\forall\epsilon>0.$

We now provide the proof of Theorem 4.5.

###### Proof.

Without loss of generality, suppose that agent $1$ deviates from Algorithm
R-RM. First, if agent $1$ deviates during exploration sub-phase, then any
deviation is guaranteed to be detected. This means that, if agent $1$ deviates
during exploration sub-phase, then Algorithm R-RM is ensured to enter the
punishment phase. Thus, it follows from Lemma 4.2 that, in this case,
Algorithm R-RM is perfectly rational. We now show that Algorithm R-RM is
perfectly rational when agent $1$ deviates during exploitation sub-phase.

Observe that in any epoch $t$, in the worst-case, agent $1$ can select its
actions such that the deviation between the empirical CDF and the actual CDF
is within $\epsilon_{t}$. Mathematically, in any epoch $t$ and in the worst-
case, agent $1$ can selects its action such that at after $N_{t}$ iterations,
the following condition does not hold:

$\displaystyle\sup_{x\in\mathbb{R}}|\mathcal{F}_{t}^{1}(x)-F_{t}^{1}(x)|>\epsilon_{t}.$
(16)

For any epoch $t$, as $\epsilon_{t}=\tfrac{1}{t}$, it follows that as
$t\to\infty$, $\epsilon_{t}\to 0$. Thus, for a high value of $t$, there are
two cases.

Case 1: The first case is that after some epoch $t$, since
$\epsilon_{t}\approx 0$, the condition defined in equation (13) holds in which
case Algorithm R-RM enters punishment phase. In this case, from Lemma 4.2,
Algorithm R-RM is perfectly rational.

Case 2: The second case is that, since $\epsilon_{t}\to 0$ as $t\to\infty$,
agent $1$ starts selecting actions according to regret matching and does not
deviate. This means that from this moment on, both agents select their actions
according to regret matching algorithm. We now show that in this case, the
strategies obtained from Algorithm R-RM converge to $\pi_{1}^{*}$ and
$\pi_{2}^{*}$, with probability $1-\delta$.

Intuitively, the idea is to show that the probability with which Algorithm
R-RM enters punishment phase when the agents do not deviate is very small. For
any epoch $t$, using Lemma E.1, the probability that condition defined in
equation (13) holds is

$\displaystyle
Pr\left(\sup_{x\in\mathbb{R}}|\mathcal{F}(x)-F_{N_{t}}(x)|>\epsilon_{t}\right)\leq
2e^{-2N_{t}\epsilon_{t}^{2}}.$

Then, by taking the union bound over all possible epochs $t$, it follows that
the probability that the condition defined in equation (13) never holds is at
least $1-t2e^{-2N_{t}\epsilon_{t}^{2}}$. For some positive real constants
$c_{1}$ and $c_{2}$, by selecting $N_{t}$ as

$\displaystyle
N_{t}=\frac{c_{1}\log(\frac{c_{2}t}{\delta})}{\epsilon^{2}_{t}},$

we obtain that the probability that the condition defined in equation (13)
never holds is at least $1-\frac{2\delta}{c_{2}t^{2c_{1}-1}}$. By selecting
$c_{1}$ and $c_{2}$ such that $\frac{2\delta}{c_{2}t^{2c_{1}-1}}\geq\delta$,
it follows that with probability at least $1-\delta$, the condition defined in
equation (13) never holds until epoch $t$. This means that, with probability
$1-\delta$, Algorithm R-RM does not enter the punishment phase until epoch
$t$. Thus, if $\pi_{1}^{*}$ and $\pi_{2}^{*}$ converge to an equilibrium, the
strategies obtained from Algorithm R-RM will also converge to the equilibrium.

Finally, the proof for the case when no agent deviates and the strategies
obtained from Algorithm R-RM converges to the equilibrium, with probability
$1-\delta$, if $\pi_{1}^{*}$ and $\pi_{2}^{*}$ converge to an equilibrium is
analogous to that of Case 2. This concludes the proof. ∎

##  Appendix F Proof of Theorem 4.6

(a) Game $\mathcal{G}_{1}$.

(b) Game $\mathcal{G}_{2}$.

Figure 10: Games $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ for the proof of
Theorem 4.6. The equilibrium entries are highlighted in bold.

###### Proof.

Without loss of generality, suppose that agent $2$ deviates from an algorithm
$\mathcal{A}$ and follows algorithm $\mathcal{A}^{\prime}$. Consider two games
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ as depicted in Figure 10. In game
$\mathcal{G}_{1}$ (resp. $\mathcal{G}_{2}$), the entry $(2,2)$ (resp. entry
$(1,1)$) is the only possible equilibrium (because of domination) and suppose
that, if both agents select their actions according to algorithm
$\mathcal{A}$, their respective strategies converge to the entries
corresponding to the equilibrium of the game.

Suppose agent $2$ always selects column $2$ and the game is $\mathcal{G}_{2}$.
Further, even by assuming that Algorithm $\mathcal{A}$ has the information
that the game selected is either $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ and
completely knows its own payoff matrices, $\mathcal{A}$ cannot determine the
actual game being played by the agents. This is because of the imperfect
monitoring setting and that the payoffs for agent $1$ is identical in both
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$. Thus, given that agent $1$ can only
observe agent $2$’s actions and since agent $2$ selects only column $2$,
algorithm $\mathcal{A}$ selects row $2$ for agent $1$. This is because, given
that agent $2$ selects column $2$, selecting row $1$ yields a lower payoff for
agent $1$. This means that $U_{2}(\mathcal{A},\mathcal{A}^{\prime})=10(c+1)$.
Thus, even by restricting the set of games to only $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$, it follows that
$\sup_{\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{A}^{\prime}}\frac{U_{2}(\mathcal{A},\mathcal{A}^{\prime})}{U_{2}(\mathcal{A},\mathcal{A})}=c+1$.
This implies that
$\sup_{\mathcal{G},\mathcal{A}^{\prime}}\frac{U_{2}(\mathcal{A},\mathcal{A}^{\prime})}{U_{2}(\mathcal{A},\mathcal{A})}>c$,
for any constant $c$ meaning that $\mathcal{A}$ is not $c$-rational for any
constant $c$. This concludes the proof. ∎

##  Appendix G Additional Numerical Results

In this section, we provide additional numerical results to illustrate the
analytical results established in this work.

Table 1: Numerical results for Algorithm R-GFP. Fictitious play is denoted as FP. Game | $U_{1}(\mathcal{A}^{\prime},\text{FP})$ | $U_{1}(\text{R-GFP},\text{R-GFP})$ | $U_{1}(\mathcal{A}^{\prime},\text{R-GFP})$ | $U_{1}(\mathcal{A}^{\prime}_{\text{explore}},\text{R-GFP})$
---|---|---|---|---
$\mathcal{G}_{1}^{\text{GFP}}$ | $99.3$ | $25.3$ | $1.2$ | $1.1$
$\mathcal{G}_{2}^{\text{GFP}}$ | $42$ | 34 | $27.5$ | $27.5$
$\mathcal{G}_{3}^{\text{GFP}}$ | $72$ | 66 | $41.4$ | $10.4$

(a) Game $\mathcal{G}_{1}^{\text{GFP}}$.

(b) Game $\mathcal{G}_{2}^{\text{GFP}}$.

(c) Game $\mathcal{G}_{3}^{\text{GFP}}$.

Figure 11: Games $\mathcal{G}_{1}^{\text{GFP}}$,
$\mathcal{G}_{2}^{\text{GFP}}$, and $\mathcal{G}_{3}^{\text{GFP}}$ for Table
1.

(a) Game $\mathcal{G}_{1}^{\text{RM}}$.

(b) Game $\mathcal{G}_{2}^{\text{RM}}$.

(c) Game $\mathcal{G}_{3}^{\text{RM}}$.

Figure 12: Games $\mathcal{G}_{1}^{\text{RM}}$, $\mathcal{G}_{2}^{\text{RM}}$,
and $\mathcal{G}_{3}^{\text{RM}}$ for Table 2.

Table 1 and Table 2 illustrates the numerical results for Algorithm R-GFP and
Algorithm R-RM, respectively. The games considered in Table 1 and Table 2 were
generated using GAMUT (Nudelman et al., 2004) and are illustrated in Figure 11
and Figure 12, respectively.

Table 1 presents different values of payoffs obtained by agent $1$ (adversary)
for different cases. We consider that the agents use the entire history and
thus, the generalized fictitious play is equivalent to fictitious play and
implement the strategy for agent $1$ as described in (Vundurthy et al., 2023).
In game $\mathcal{G}_{1}^{\text{GFP}}$ and $\mathcal{G}_{2}^{\text{GFP}}$, the
payoff obtained by the adversary upon deviating during the exploration sub-
phase is approximately equal to when it deviates during the exploitation sub-
phase. This is because the matrix $R^{1}$ is eventually completely known by
agent $2$ as $t\to\infty$. In game $\mathcal{G}_{3}^{\text{GFP}}$, the
adversary never selects row $2$ meaning that the matrix $R^{1}$ is never fully
known to agent $2$. Thus, for game $\mathcal{G}_{3}^{\text{GFP}}$, the payoff
obtained by the adversary upon deviating during the exploration sub-phase is
less than when it deviates during exploitation sub-phase. Finally, for all
games,
$U_{1}(\mathcal{A}^{\prime},\text{R-GFP})<U_{1}(\text{R-GFP},\text{R-GFP})$
implying that Algorithm R-GFP is perfectly rational.

Table 2: Numerical results for Algorithm R-RM. Regret-matching is denoted as RM. Game | $U_{2}(\text{RM},\mathcal{A}^{\prime})$ | $U_{2}(\text{R-RM},\text{R-RM})$ | $U_{2}(\text{R-RM},\mathcal{A}^{\prime})$ | $U_{2}(\text{R-RM},\mathcal{A}^{\prime}_{\text{explore}})$
---|---|---|---|---
$\mathcal{G}_{1}^{\text{RM}}$ | $72$ | 54.9 | $18.2$ | $18$
$\mathcal{G}_{2}^{\text{RM}}$ | $98.5$ | $60.1$ | $22.2$ | $22.1$
$\mathcal{G}_{3}^{\text{RM}}$ | $97.8$ | $79$ | $31.5$ | $30.9$

Table 2 presents different values of payoffs obtained by agent $2$ (adversary)
for various cases. Upon deviation, agent $2$ follows the strategy as described
in equation (14). Similar to Algorithm R-GFP, for all games in Table 2,
$U_{2}(\text{R-RM},\mathcal{A}^{\prime})<U_{2}(\text{R-RM},\text{R-RM})$
implying that Algorithm R-RM is perfectly rational. Finally, for all games in
Table 2, the value of agent $2$ when it deviates during exploration sub-phase
is approximately equal to the vale when agent $2$ deviates during exploitation
sub-phase as matrix $R^{2}$. This is because the strategy followed by agent
$2$ does not change in both exploration and exploitation sub-phase once agent
$1$ follows minimax strategy.