ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 174 Vector
Institute, Toronto, Canada University of Waterloo, Waterloo Canada University
of Alberta, Edmonton, Canada Alberta Machine Intelligence Institute, Edmonton
Canada University of Waterloo Waterloo Canada University of Waterloo Waterloo
Canada

# Learning from Multiple Independent Advisors in Multi-agent Reinforcement
Learning

Sriram Ganapathi Subramanian<EMAIL_ADDRESS>,  Matthew
E. Taylor<EMAIL_ADDRESS>,  Kate Larson
<EMAIL_ADDRESS>and  Mark Crowley<EMAIL_ADDRESS>
###### Abstract.

Multi-agent reinforcement learning typically suffers from the problem of
sample inefficiency, where learning suitable policies involves the use of many
data samples. Learning from external demonstrators is a possible solution that
mitigates this problem. However, most prior approaches in this area assume the
presence of a single demonstrator. Leveraging multiple knowledge sources
(i.e., _advisors_) with expertise in distinct aspects of the environment could
substantially speed up learning in complex environments. This paper considers
the problem of simultaneously learning from multiple independent advisors in
multi-agent reinforcement learning. The approach leverages a two-level
$Q$-learning architecture, and extends this framework from single-agent to
multi-agent settings. We provide principled algorithms that incorporate a set
of advisors by both evaluating the advisors at each state and subsequently
using the advisors to guide action selection. We also provide theoretical
convergence and sample complexity guarantees. Experimentally, we validate our
approach in three different test-beds and show that our algorithms give better
performances than baselines, can effectively integrate the combined expertise
of different advisors, and learn to ignore bad advice.

###### Key words and phrases:

Multi-agent systems; Multi-agent reinforcement learning; Learning from action
advising; Reinforcement learning; Sample efficiency

##  1\. Introduction

Reinforcement learning (RL) has been successful in obtaining super-human
performances in a wide range of challenges such as Atari games (Mnih et al.,
2015), Go (Silver et al., 2016), and simple robotic tasks like opening doors
and learning visuomotor policies (Levine et al., 2016). However, it has not
been straightforward to replicate these successes in complex real-world
problems. One reason is that these problems often have a multi-agent
structure, where more than one learning agent participates at the same time,
resulting in complicated dynamics. Despite research advances in multi-agent
reinforcement learning (MARL) (Hernandez-Leal et al., 2019), poor sample
efficiency in existing algorithms is one issue that still causes significant
hurdles in applying MARL to complex problems (Silva and Costa, 2019).

Using external sources of knowledge that help in accelerating MARL training is
one solution (Barrett et al., 2017), which has extensive support in literature
Silva and Costa (2019). However, most prior work include two limiting
assumptions. First, all demonstrations need to come from a single demonstrator
(Brys et al., 2015). In complex MARL environments, since agents learn policies
that meet the twin goals of responding to changing opponent(s) and
environments Littman (1994), a learner can likely benefit from multiple
knowledge sources that have expertise in different parts of the environment or
different aspects of the task. Second, all demonstrations are near-optimal
(i.e., from an “expert”) (Piot et al., 2014). In practice, these knowledge
sources are typically sub-optimal, and we broadly refer to them as _advisors_
(to differentiate from experts).

In this paper, we provide an approach that simultaneously leverages multiple
different (sub-optimal) advisors for MARL training. Since the advisors may
provide conflicting advice in different states, an algorithm needs to resolve
such conflicts to take advantage of all the advisors effectively. We propose a
two-level learning architecture and formulate a $Q$-learning algorithm for
simultaneously incorporating multiple advisors in MARL, improving upon the
previous work of Li et al. (Li et al., 2019) in single-agent RL. This
architecture uses one level to evaluate advisors and the other learns values
for actions. Further, we extend our approach to an actor-critic variant that
applies to the centralized training and decentralized execution (CTDE) setting
(Lowe et al., 2017). Since RL is a fixed point iterative method (Szepesvari
and Littman, 1999), we provide convergence results, proving that our
$Q$-learning algorithm converges to a Nash equilibrium (Nash, 1951) (under
common assumptions). Additionally, we provide a detailed finite-time analysis
of our $Q$-learning algorithm under two different types of learning rates.
Finally, we experimentally study our approach in three different multi-agent
test-beds, in relation to standard baselines.

Since we relax the two limiting assumptions regarding learning from
demonstrators in MARL, our hope is that this approach will spur successes in
real-world applications, such as autonomous driving (Helou et al., 2021) and
fighting wildfires (Jain et al., 2020), where MARL methods could use existing
(sub-optimal) solutions as advisors to accelerate training.

##  2\. Related Work

This work is most related to the approach of _reinforcement learning from
expert demonstrations_ (RLED) (Piot et al., 2014). A well-known RLED technique
is _deep $Q$-learning from demonstrations_ (DQfD) (Hester et al., 2018), which
combines a temporal difference (TD) loss, an L2 regularization loss, and a
classification loss that encourages actions to be close to that of the
demonstrator. Another method, normalized actor-critic (NAC) (Jing et al.,
2020), drops the classification loss and is more robust under imperfect
demonstrations. However, NAC is prone to weaker performances than DQfD under
good demonstrations due to the absence of classification loss. A different
approach, _human agent transfer_ (HAT) Taylor et al. (2011), extracts
information from limited demonstrations using a classifier, while _confidence-
based human-agent transfer_ (CHAT) (Wang and Taylor, 2017) improves HAT by
using a confidence measurement to safeguard against sub-optimal
demonstrations. A related approach is the teacher-student framework Torrey and
Taylor (2013), where a pretrained policy (teacher) can be used to provide
limited advice to a learning agent (student). Subsequent works expand this
framework towards interactive learning (Amir et al., 2016), however, almost
all works in this area assume a moderate level expertise for the teacher.
Moreover, these are all independent methods primarily suited for single-agent
environments, and may not be directly applicable in MARL context.

Furthermore, external knowledge sources have also been used in MARL (Silva and
Costa, 2019), where prior works often assume near optimal experts(Reddy et
al., 2012; Waugh et al., 2011) or are only applicable to restrictive settings,
such as fully cooperative or zero-sum competitive games (Omidshafiei et al.,
2019; Silva et al., 2017; Silver et al., 2016; Wang et al., 2018; Ye et al.,
2020). Leno et al. Silva et al. (2017) introduced a framework where an agent
can learn from its peers in a shared learning environment, in addition to
learning from the environmental rewards. Here the peers can be sub-optimal,
however this work only applies to cooperative environments. Other works have
provided a cooperative teaching framework for hierarchical learning Kim et al.
(2020); Yang et al. (2021). For multi-agent general-sum environments,
_advising multiple intelligent reinforcement agents - decision making_
(ADMIRAL-DM) Subramanian et al. (2022) is a $Q$-learning approach that
incorporates real-time information from a single online sub-optimal advisor.

One limitation of many prior works is the assumption of a single source of
demonstration. In MARL, it may be possible to obtain advisors from different
sources of knowledge that provide conflicting advice. For single-agent
settings, Li et al. Li et al. (2019) provides the two-level $Q$-learning
(TLQL) algorithm that incorporates multiple advisors in RL. The TLQL maintains
two $Q$-networks, where the first $Q$-network (high-level) keeps track of each
advisor’s performance and the second $Q$-network (low-level) learns the
quality of each action. We improve upon TLQL and make it applicable to MARL
settings.

##  3\. Background

Stochastic Games: A $N$-player stochastic game is represented by a tuple
$\langle S,A^{1},\ldots,A^{N},r^{1},\ldots,r^{N},P,\gamma\rangle$, where $S$
is the state space, $A^{j}$ is the action space of the agent
$j\in\\{1,\ldots,N\\}$, and $r^{j}:S\times A^{1}\times\cdots\times
A^{N}\xrightarrow{}\mathcal{R}$ is the reward function of $j$. Also,
$P:S\times A^{1}\times\cdots A^{N}\xrightarrow{}\Omega(S)$ is the transition
probability that determines the next state given the current state and the
joint action of all agents, where $\Omega$ is a probability distribution.
Finally, $\gamma\in[0,1)$ is the discount factor. At each time $t$, all agents
observe the global state $s$ and take a local action $a^{j}$ (Shapley, 1953).
The joint action $\boldsymbol{a}=\\{a^{1},\ldots,a^{N}\\}$ determines the
immediate reward $r^{j}$ for $j$ and the next state of the system
$s^{\prime}$. Each agent learns a suitable policy that gives the best
responses to its opponent(s). The policy is denoted by
$\pi^{j}:S\xrightarrow{}\Omega(A^{j})$. Let
$\boldsymbol{\pi}\triangleq(\pi^{1},\ldots,\pi^{N})$ be the joint policy of
all agents. At a state $s$, the value function of $j$ under the joint policy
$\boldsymbol{\pi}$ is
$v^{j}_{\boldsymbol{\pi}}(s)=\sum_{t=0}^{\infty}\gamma^{t}\operatorname{\mathbb{E}}_{\pi,P}[r^{j}_{t}|s_{0}=s,\boldsymbol{\pi}]$.
This represents the expected discounted future reward of $j$, when all agents
follow the policy $\boldsymbol{\pi}$ from the state $s$. Related to the value
function, is the action-value function or the $Q$-function. The $Q$-function
of agent $j$, under the policy $\boldsymbol{\pi}$, is given by,
$Q^{j}_{\boldsymbol{\pi}}(s,\boldsymbol{a})=r^{j}(s,\boldsymbol{a})+\gamma\operatorname{\mathbb{E}}_{s^{\prime}\sim
P}[v^{j}_{\boldsymbol{\pi}}(s^{\prime})]$.

The setting we consider is general-sum stochastic games, where the reward
functions of the different agents can be related in any arbitrary fashion. In
this setting, the _Nash equilibrium_ is typically considered as the solution
concept Hu and Wellman (2003), where the joint policy
$\boldsymbol{\pi}_{*}=[\pi^{1}_{*},\ldots,\pi^{N}_{*}]$ for all $s\in S$ and
all $j$ satisfies $v^{j}(s;\pi^{j}_{*},\boldsymbol{\pi}^{-j}_{*})\geq
v^{j}(s;\pi^{j},\boldsymbol{\pi}^{-j}_{*})$. Here,
$\boldsymbol{\pi}^{-j}_{*}\triangleq[\pi^{1}_{*},\ldots,\pi^{j-1}_{*},\pi^{j+1}_{*},\ldots,\pi^{N}_{*}]$
represents the joint policy of all agents except $j$. In a Nash equilibrium,
each agent plays the best response to the other agents and any deviation from
this response is guaranteed to be worse off. Further, Hu and Wellman Hu and
Wellman (2003) proved that the $Q$-updates of an agent $j$, using the Nash
payoff at each stage eventually converges to its Nash $Q$ value ($Q^{j}_{*}$),
which is the action-value obtained by the agent $j$ when all agents follow the
joint Nash equilibrium policy for infinite periods.

Two-level $Q$-learning: The TLQL algorithm Li et al. (2019) enables single-
agent learning under the simultaneous presence of multiple advisors providing
conflicting demonstrations. Here, the challenge is to determine which advisor
to trust in a given state. In this regard, the TLQL contains two $Q$-tables, a
high-level $Q$-table (abbreviated as high-$Q$) and a low-level $Q$-table
(abbreviated as low-$Q$). The high-$Q$ stores the value of the $\langle
s,ad\rangle$ pair, where $ad\in AD$ represents an advisor (with $AD$
representing the set of all advisors). The high-$Q$ also stores the value of
following the RL policy in addition to each advisor. The low-$Q$ maintains the
value of each state-action pair.

At each time step, the agent observes the state and selects an advisor (or the
RL policy) from the high-$Q$ using the $\epsilon$-greedy strategy. If the
high-$Q$ returns an advisor, then the advisor’s recommended action is
performed. If the RL policy is returned, then an action is executed from the
low-$Q$ based on the $\epsilon$-greedy strategy Sutton and Barto (1998). The
low-$Q$ is updated using the vanilla $Q$-learning Bellman update (Watkins and
Dayan, 1992). Subsequently, the high-$Q$ is updated using a synchronization
step. In this step, when an advisor’s action is performed, the value of the
advisor in the high-$Q$ is simply assigned the value of that action from the
low-$Q$. Finally, the high-$Q$ of the RL policy is updated using the relation
$highQ(s,RL)=\max_{a}lowQ(s,a)$. This synchronization update of high-$Q$
preserves the convergence guarantees, due to the policy improvement guarantee
in single-agent $Q$-learning (Sutton and Barto, 1998).

There are two important limitations of TLQL. First, the high-$Q$ that
represents the value of the advisors also depends on the RL policy through the
synchronization step. This $Q$ value represents the value of taking the action
suggested by the advisor at the current state and then following the RL policy
from the next state onward. This definition is problematic since at the
beginning of training, the RL policy is sub-optimal, and the objective is to
accelerate learning by relying on external advisors and avoid using the RL
policy at all. As advisors are evaluated at each state using the RL policy, it
is likely that the most effective advisor among the set of advisors is not
being followed until the RL policy improves. At this stage, it might be
possible to simply follow the RL policy itself, defeating the purpose of
learning from advisors. Second, the advisors have not been evaluated at the
beginning of learning. Hence, it is impossible to find the most suitable
advisor to follow, from the available advisors. While TLQL simply follows an
$\epsilon$-greedy exploration strategy, this approach could take many data
samples to figure out the right advisor. We address both these limitations.

##  4\. Two-level Architecture in MARL

We consider a general-sum stochastic game, where there are a set of agents
that are learning a policy with an objective of providing a best response to
the other agents as well as the environment. Each agent $j$ can access a
finite set of (possibly sub-optimal) independent advisors $AD^{j}$. We use
$ad^{j}$ to represent an advisor of $j$, where
$ad^{j}\in\\{ad^{j}_{1},\ldots,ad_{|AD^{j}|}^{j}\\}$. Each advisor $ad^{j}$
can be queried by $j$ to obtain an action recommendation at each state of the
stochastic game. These online advisors provide real-time action advice to the
agent, which helps in learning to dynamically adapt to opponents. We consider
a centralized training setting and assume 1) the advisors are fixed and do not
learn, 2) the communication between agents and their advisors is free, 3)
there is no communication directly between learning agents, 4) the environment
is fully observable (i.e., an agent can observe the global state, all actions,
and all rewards), and 5) the state and action spaces are discrete. Though we
require these assumptions for theoretical guarantees, we will show that it is
possible to relax a number of these assumptions in practice.

To make TLQL applicable to multi-agent settings, we parameterize both the
$Q$-functions with the joint actions, as is common in practice (Littman,
1994). Also, we do not maintain the RL policy in the high-$Q$ table and do not
perform a synchronization step. These steps are no longer needed to preserve
the convergence results in multi-agent settings, since we do not have a policy
improvement guarantee (unlike in single-agent settings) Tan (1993). Instead,
we choose to use the probabilistic policy reuse (PPR) technique Fernández and
Veloso (2006), where a hyperparameter ($\epsilon^{\prime}\in[0,1]$) decides
the probability of following any advisor(s) (i.e., using the high-$Q$) or the
agents’ own policy (i.e., using the low-$Q$) for action selection, at each
time step during training. This hyperparameter starts with a high value
(maximum dependence on the available advisor(s)) at the beginning of training
and is decayed (linearly) over time. After some finite time step during
training, the value of this hyperparameter goes to 0 (no further dependence on
any advisor(s)) and the agent only uses its low-$Q$ (own policy) for action
selection. This helps in two ways: 1) in the time limit
($t\xrightarrow{}\infty$), a learning agent has the possibility of recovering
from poor advising (by learning from the environment), and 2) eventually the
trained agent can be independently deployed (with no requirement of having
access to any advisor(s)).

The general structure of our proposed _Multi-Agent Two-Level $Q$-Learning_
(MA-TLQL) algorithm is given in Figure 1. Since we are in a fully observable
setting, like Hu and Wellman (2003), we specify that each agent maintains
copies of the $Q$-tables of other agents from which it can obtain the joint
actions of other agents for the current state. If such copies cannot be
maintained, agents could use the previously observed actions of other agents
for the joint action as done in prior works (Subramanian et al., 2022; Yang et
al., 2018). We use the two-level architecture, where each agent will maintain
a high-$Q$ as well as a low-$Q$. The high-$Q$ provides a value for the
$\langle s,\boldsymbol{a}^{-j},ad^{j}\rangle$ tuples, where
$\boldsymbol{a}^{-j}=\\{a^{1},\ldots,a^{j-1},a^{j+1},\ldots,a^{N}\\}$ is the
joint action of all agents except the agent $j$. This high-$Q$ is a value
estimate for the advisor $ad^{j}$ as estimated by the agent $j$ at the state
$s$ and joint action $\boldsymbol{a}^{-j}$. The high-$Q$ estimates are updated
with an evaluation update given by

$\begin{array}[]{lll}highQ^{j}_{t+1}(s,\boldsymbol{a}^{-j},ad^{j})=highQ^{j}_{t}(s,\boldsymbol{a}^{-j},ad^{j})\\\
\quad+\alpha\Big{(}(r^{j}_{t}+\gamma
highQ^{j}_{t}(s^{\prime},\boldsymbol{a^{\prime}}^{-j},ad^{j})-highQ^{j}_{t}(s,\boldsymbol{a}^{-j},ad^{j})\Big{)},\end{array}$
(1)

where $s$ and $s^{\prime}$ are the states at $t$ and $t+1$, and $\alpha$ is
the learning rate. Also, $\boldsymbol{a}^{-j}$ and
$\boldsymbol{a^{\prime}}^{-j}$ are joint actions at $s$ and $s^{\prime}$,
respectively.

Figure 1. Structure of MA-TLQL, for a representative agent having access to a
set of AD advisor(s)

As described previously, a hyperparameter is used to decide between choosing
to follow an advisor or the RL policy. If the agent follows an advisor, the
high-$Q$ is used to select an advisor using an ensemble selection technique.
Let us denote,
$\mathcal{Q}^{j}=\\{highQ^{j}(s,\boldsymbol{a}^{-j},ad_{1}^{j}),\ldots,highQ^{j}(s,\boldsymbol{a}^{-j},ad_{m}^{j})\\}$,
to represent the high-$Q$ estimates of a set of $M$ advisors (with $|M|=m$)
advising the same action $a^{j}$ to an agent $j$. Here, $ad^{j}_{i}$
represents an advisor $i\in\\{1,\ldots,m\\}$ of $j$. Then the value of vote
for action $a^{j}$, at the state $s$ and the joint action
$\boldsymbol{a}^{-j}$, denoted by
$\mathcal{V}^{j}(s,\boldsymbol{a}^{-j},a^{j})$, is calculated as

$\begin{array}[]{l}\mathcal{V}^{j}(s,\boldsymbol{a}^{-j},a^{j})=\max\mathcal{Q}^{j}\\\
+\sum_{i=1,i\neq\operatorname*{arg\,max}_{i}highQ^{j}(s,\boldsymbol{a}^{-j},ad^{j}_{i})}^{m}\frac{1}{\mu(s)}highQ^{j}(s,\boldsymbol{a}^{-j},ad^{j}_{i}).\end{array}$
(2)

Here, $\mu(s)$ is the number of times the agent has visited the state $s$. In
Eq. 2, if an action is recommended by more than one advisor, the value of its
vote is a weighted sum of all high-$Q$ estimates of advisors recommending that
action. Each high-$Q$ estimate (except the best high-$Q$ estimate) is weighted
by the reciprocal of the number of times the respective state is visited. In
this way, when a state is visited many times, the advisor with the best
high-$Q$ estimate is likely to be followed (wisdom of individual). When a
state is visited only a few times, then the action suggested by a majority of
advisors is likely to be selected (wisdom of crowd). From Eq. 2, if an action
$a^{j}$ is recommended by only one advisor, then the value of vote for $a^{j}$
will be equal to the high-$Q$ estimate of that advisor. After the value of
votes for all actions are calculated, the action with the maximum value of
vote is executed, and the high-$Q$ estimate of the advisor recommending this
action is updated by the agent $j$ using Eq. 1.

If the agent decides to use its RL policy, it uses its low-$Q$, which contains
a value for the $\langle s,\boldsymbol{a}^{-j},a^{j}\rangle$ tuples (value for
each action). At each step, the low-$Q$ is updated using a control update as
follows:

$\begin{array}[]{ll}lowQ^{j}_{t+1}(s,\boldsymbol{a}^{-j},a^{j})=lowQ^{j}_{t}(s,\boldsymbol{a}^{-j},a^{j})\\\
+\alpha\big{(}r^{j}_{t}+\gamma\max_{a^{\prime
j}}lowQ^{j}_{t}(s^{\prime},\boldsymbol{a}^{\prime-j},a^{\prime
j})-lowQ^{j}_{t}(s,\boldsymbol{a}^{-j},a^{j})\big{)}.\end{array}$ (3)

Now we describe how MA-TLQL addresses the two limitations of TLQL. The first
was the dependence of high-$Q$ on the RL policy in TLQL. Note, the high-$Q$ in
MA-TLQL maintains the $Q$ values of the advisor themselves, i.e., the value of
following the advisor’s policy from the current state onward (see Eq. 1).
Thus, the coupling between the advisor values and the RL policy is removed (no
synchronization). The second was the difficulty in picking the right advisor
in TLQL. MA-TLQL uses an ensemble technique to choose the advisor during the
early stages of learning. In later stages, it switches to following the best
advisor according to the high-$Q$ estimates, which addresses this limitation
of TLQL. In Appendix J, we present a toy example that illustrates the
limitations of TLQL.

We provide the complete pseudocode for a tabular implementation of the MA-TLQL
algorithm in Appendix A (Algorithm 1). Further, we extend this approach to
large state-action environments using a neural network based implementation
(Algorithm 2), which uses a target network and a replay buffer, as in the Deep
$Q$-learning (DQN) algorithm (Mnih et al., 2015). We also provide an actor-
critic implementation (Algorithm 3) which is suitable for CTDE (Lowe et al.,
2017). We will refer to this algorithm as _multi-agent two-level actor-critic_
(MA-TLAC). In MA-TLAC, each agent has two actors and two critics (high-level
and low-level), where the respective $Q$-functions serve as the critic and the
corresponding policies serve as the actors. In this CTDE method, agents can
obtain global information (including actions and rewards of other agents)
during training, however, the agents only require access to its local
observation during execution. This makes our method applicable to partially
observable environments as in Lowe et al. Lowe et al. (2017). MA-TLAC applies
to continuous state space environments as well (refer to Appendix A for more
details).

##  5\. Theoretical Results

We present a convergence guarantee for tabular MA-TLQL and characterize the
convergence rate. For these results, we build on some prior works that provide
several fundamental results on the nature of stochastic iterative functions
Bertsekas and Tsitsiklis (1996); Even-Dar and Mansour (2003). We apply these
to MA-TLQL in general-sum stochastic games using three assumptions from Hu and
Wellman Hu and Wellman (2003), where the first two are standard (Szepesvari
and Littman, 1999).

######  Assumption 1.

Every $s\in\mathcal{S}$ and $a^{j}\in A^{j}$, for every agent $j$ are visited
infinitely often, and the reward function ($\forall j$) stays bounded.

######  Assumption 2.

For all $s,t$, and $\boldsymbol{a}$, $0\leq\alpha_{t}(s,\boldsymbol{a})<1$,
$\sum_{t=0}^{\infty}\alpha_{t}(s,\boldsymbol{a})=\infty$,
$\sum_{t=0}^{\infty}[\alpha_{t}(s,\boldsymbol{a})]^{2}<\infty$.

######  Assumption 3.

The Nash equilibrium is a global optimum or saddle point in every stage game
of the stochastic game.

The third assumption is a restriction on the nature of the stochastic game.
Several prior works note that this assumption is restrictive but needed to
theoretically prove the convergence of $Q$-learning methods in general-sum
stochastic games with two or more agents. In practice, however, it is still
possible to observe convergence of $Q$-learning methods when this assumption
is violated (Hu and Wellman, 2003; Subramanian et al., 2022; Yang et al.,
2018).

Now we prove our theoretical results. All theorem statements are provided
here, while the proofs can be found in Appendices B – D. First, we provide the
convergence guarantee for the low-$Q$. Recall, the PPR technique guarantees
that the MA-TLQL dependence on high-$Q$ is only until a finite time step
during training. After this step, the agent only uses its low-$Q$ for action
selection. As the convergence result in Theorem 1 is provided in the time
limit ($t\xrightarrow{}\infty$), the influence of high-$Q$ can be neglected
for this result.

######  Theorem 1.

Given Assumptions 1, 2, 3, the low-$Q$ values of an agent $j$ converges to its
Nash $Q$ value in the limit ($t\xrightarrow{}\infty$).

Next, we provide sample complexity bounds for the MA-TLQL algorithm. Instead
of explicitly considering the high-$Q$ values, we specify that the underlying
joint policy has a covering time of $L$. The covering time specifies an upper
bound on the number of time steps needed for all state-joint action pairs to
be visited at least once starting from any state-joint action pair. Further,
since the action selection is only based on the low-$Q$ values in the limit
($t\xrightarrow{}\infty$), we are most interested in the sample complexity of
low-$Q$, where the dependence on the high-$Q$ is effectively represented by
$L$.

Regarding sample complexity, as is done in Even-Dar and Mansour (2003), we
distinguish between two kinds of learning rates. Consider the following
equation for the low-$Q$ (rewriting Eq. 3 and dropping $low$ for simplicity),

$\begin{array}[]{l}Q^{j}_{t+1}(s_{t},\boldsymbol{a}_{t})=\big{(}1-\alpha^{\omega}_{t}(s_{t},\boldsymbol{a}_{t}))(Q^{j}_{t}(s_{t},\boldsymbol{a}_{t})\big{)}\\\
\quad\quad\quad\quad\quad\quad+\alpha^{\omega}_{t}(s_{t},\boldsymbol{a}_{t})\big{(}r^{j}_{t}+\gamma\max_{a^{j}}Q^{j}_{t}(s_{t+1},\boldsymbol{a}_{t+1})\big{)}.\end{array}$
(4)

The value of
$\alpha^{\omega}_{t}(s,\boldsymbol{a})=\frac{1}{[\\#(s,\boldsymbol{a},t)^{\omega}]}$,
where $\\#(s,\boldsymbol{a},t)$ is the number of times until $t$ that the
joint action $\boldsymbol{a}$ is performed at $s$. Here, we consider
$\omega\in(1/2,1]$. The learning rate is linear if $\omega=1$, and the
learning rate is polynomial if $\omega\in(1/2,1)$.

The next theorem provides a lower bound on the number of time steps needed for
convergence in the case of a polynomial learning rate. From Assumption 1, let
us specify that all rewards for the agent $j$ are bounded by $R^{j}_{\max}$.
We consider a variable $Q^{j}_{\max}$, which denotes the maximum possible
low-$Q$ value for the agent $j$, which is bounded by
$Q^{j}_{\max}=R^{j}_{\max}/(1-\gamma)$. Additionally, we also use another
variable $\beta=(1-\gamma)/2$ to present our upcoming results concisely.

######  Theorem 2.

Let us specify that with probability at least $1-\delta$, for an agent $j$,
$||Q^{j}_{T}-Q^{j}_{*}||_{\infty}\leq\epsilon$. The bound on the rate of
convergence of low-$Q$, $Q^{j}_{T}$, with a polynomial learning rate of factor
$\omega$ is given by (with $Q^{j}_{*}$ as the Nash $Q$-value of the agent $j$)

$\begin{array}[]{l}T=\Omega\Big{(}\Big{(}\frac{L^{1+3\omega}Q^{2,j}_{\max}\ln(\frac{|S|\Pi_{i}|A_{i}|Q^{j}_{\max}}{\delta\beta\epsilon})}{\beta^{2}\epsilon^{2}}\Big{)}^{1-\omega}/L\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\Big{(}(\frac{L}{\beta}\ln\frac{Q^{j}_{\max}}{\epsilon}+1)/2\Big{)}^{\frac{1}{1-\omega}}\Big{)}.\end{array}$
(5)

Assuming the same action spaces for all agents (i.e.
$|A_{1}|=|A_{2}|=\cdots=|A_{N}|=|A|$), we note that the dependence on the
number of agents is $\ln|A|^{N}=N\ln|A|$. Overall this results in a sub-linear
dependence on the number of agents based on the value of $\omega$, which is
far superior to recent works that report an exponential dependence on the
number of agents when learning in general-sum stochastic game environments
(with an arbitrary number of agents) for convergence to a Nash equilibrium
(Liu et al., 2021; Song et al., 2021). Further, the dependence on the state
space and action space in Theorem 2 is sub-linear ($\ln|S|$), and the
dependence on the covering time is
$\Omega(L^{2\omega-3\omega^{2}}+L^{1/1-\omega})$, which is a polynomial
dependence.

The next theorem considers the linear learning rate case.

######  Theorem 3.

Let us specify that with probability at least $1-\delta$, for an agent $j$,
$||Q^{j}_{T}-Q^{j}_{*}||_{\infty}\leq\epsilon$. The bound on the rate of
convergence of low-$Q$, $Q^{j}_{T}$, with a linear learning rate is given by

$T=\Omega\Big{(}(L+\psi
L+1)^{\frac{1}{\beta}\ln\frac{Q^{j}_{\max}}{\epsilon}}\frac{Q^{2,j}_{\max}\ln(\frac{|S|\Pi_{i}|A_{i}|Q^{j}_{\max}}{\delta\beta\epsilon\psi})}{\beta^{2}\epsilon^{2}\psi^{2}}\Big{)},$
(6)

where $\psi$ is a small arbitrary positive constant satisfying $\psi\leq
0.712$.

Theorem 3 shows that the bound is linear in the number of agents and sub-
linear in the state and action spaces. This linear dependence on the number of
agents is also superior to prior results (Liu et al., 2021; Song et al.,
2021). Note, the dependence on the covering time in Theorem 3 could be much
worse than that of Theorem 2, depending on the value of $Q^{j}_{\max}$ and
$\epsilon$. Since the value of $\epsilon$ is small, the dependence is
certainly worse than that obtained for the polynomial learning rate case.
Also, the dependence on $Q^{j}_{\max}$ is exponential as opposed to a
polynomial dependence for Theorem 2. The last two theorems illustrate the
performance benefit in using a polynomial learning rate as opposed to a linear
learning rate in our algorithm.

##  6\. Experiments and Results

We consider three different experimental domains, one each for competitive,
cooperative, and mixed settings, where each agent has access to a set of four
advisors. We use neural network implementations of MA-TLQL and MA-TLAC, along
with 5 other baselines: DQN (Mnih et al., 2015), DQfD (Hester et al., 2018),
CHAT (Wang and Taylor, 2017), ADMIRAL-DM (Subramanian et al., 2022), and TLQL
(Li et al., 2019). In Appendix F, we tabulate the characteristics of these
baselines and provide further details regarding our choices. Since CHAT and
ADMIRAL-DM assume the presence of a single advisor, we use a weighted random
policy approach for implementing these two algorithms in the multiple-advisor
setting, as in Li et al. Li et al. (2019). If different advisors provide
different actions at the same state, each action is weighted based on the
number of advisors suggesting that action. For DQfD, during pre-training
(Hester et al., 2018), we populate the replay buffer using advisor
demonstrations from all the available advisors. For all our experiments, we
will describe the critical details here, while the complete description is in
Appendix K. All the experiments are repeated 30 times, with averages and
standard deviations reported. For statistical significance we use the unpaired
2-sided t-test and report $p$-values, where $p<0.05$ is considered
significant. The tests compare the highest performing algorithm (typically MA-
TLQL) with the second-best baseline and best/average advisor performance. We
conduct a total of seven experiments. The code for all experiments is open-
sourced Subramanian (2023). Appendix K tabulates all our experimental
settings. Appendix L provides the hyperparameter details and Appendix M
contains the wall clock times.

Experiments 1–4 use the competitive, two-agent version of Pommerman (Resnick
et al., 2018). The environment is complex, with each state containing roughly
200 elements related to agent position and special features (e.g., bombs). The
reward function is sparse: agents only receive a terminal reward of
$\\{-1,0,+1\\}$. Experiments are conducted in two phases. In the first phase
(training), our algorithms and the baselines train against a standard DQN
opponent for 50,000 episodes, where we plot the cumulative rewards. During
this phase, algorithms can use advisors to accelerate training. In the second
phase (execution), we test the performance of the trained policies against DQN
for 1000 episodes, where we plot the win rate (fraction of games won) for each
algorithm. During this phase, agents cannot access advisors, take no
exploratory actions, and do not learn. All advisors pertaining to these four
experiments are rule-based agents.

(a) Training

(b) Execution

Figure 2. Two agent Pommerman with four sufficient advisors of different
quality (Experiment 1)

Experiment 1: Our first experiment uses a set of four advisors ranked in terms
of quality from Advisor 1 to Advisor 4. Here, Advisor 1 is the best advisor,
capable of teaching the agent all skills needed to win the game of Pommerman,
and Advisor 4 only suggests random actions. In Pommerman, there is a fixed set
of six skills that an agent needs to master to be able to win Resnick et al.
(2018). Since this set of advisors can teach all these skills, we say the
agent has access to a _sufficient set_ of advisors. We plot the training and
execution performances in Figure 2(a) and (b) respectively, including the
performance of the best and average advisors (average of all Advisors 1–4)
against DQN. MA-TLQL gives the best performance ($p<0.01$) and is the only
algorithm providing a better performance than the best advisor ($p<0.11$) in
both training and execution. MA-TLAC performs better than the average advisor
($p<0.04$). None of the others show better performances than the average
advisor. CHAT and ADMIRAL-DM are not capable of leveraging and distinguishing
amongst a set of advisors. DQfD uses pre-training, which is not very effective
in the non-stationary multi-agent context. Learning from online advising is
preferable in MARL. Also, DQfD and CHAT are independent techniques that are
not actively tracking the opponent’s performance. While TLQL is capable of
learning from multiple advisors, its independent nature in addition to
coupling of advisor values with the RL policy reduces its effectiveness in
multi-agent environments. MA-TLQL gives a better performance than MA-TLAC in
both training and execution ($p<0.01$). As noted previously, the $Q$-learning
family of algorithms tends to induce a positive bias while using the maximum
action value, which leads to providing the best possible response van Hasselt
(2010). This explains the superior performance of MA-TLQL. We conclude that
MA-TLQL is capable of leveraging a set of good and bad advisors. Further, the
training results in Figure 2(a) show that MA-TLQL is able to learn a better
policy faster than the baselines by using advisors ($p<0.01$). The evaluation
results in Figure 2(b) show that amongst all algorithms trained for the same
number of episodes, MA-TLQL provides the best performance, when deployed
without any advisors ($p<0.01$). Both observations point to better sample
efficiency in MA-TLQL. Supplementary experiments in Appendix E show that MA-
TLQL comes to relying more on good advisors than poor advisors, as compared to
the baselines, illustrating its superiority.

(a) Training

(b) Execution

Figure 3. Two-agent Pommerman with four sufficient advisors of similar quality
(Experiment 2)

Experiment 2: We use the same domain as in Experiment 1, but with a different
set of advisors. Now, all four advisors can teach strictly different Pommerman
skills. For example, Advisor 1 can teach how to escape the enemy (and nothing
else), and Advisor 2 can teach how to obtain necessary power-ups (and nothing
else — full details are in Appendix K). These advisors provide psuedo-random
action advice in states outside their expertise. This set of advisors is also
a sufficient set. Now, learning agents must decide what advisor to listen to
in the current state. From the training and execution results in Figure 3(a)
and (b), we see that MA-TLQL gives the best overall performance ($p<0.02$),
exceeding the average performance of the four advisors ($p<0.05$). Since all
four advisors have similar quality, we only choose to use the average
performance of the four advisors in this experiment for comparison. We
conclude that MA-TLQL is capable of leveraging the combined knowledge of a set
of advisors with different individual expertise, during learning.

(a) Training

(b) Execution

Figure 4. Two-agent Pommerman with four insufficient advisors of different
quality (Experiment 3)

Experiment 3: We use the same domain as in Experiment 1 but with a different
set of four advisors. These advisors are similar to the set of advisors in our
first experiment, where Advisor 1 gives the best advice throughout the domain,
and Advisor 4 is random. However, this set of advisors is _not_ capable of
teaching all the strategies (i.e, Pommerman skills) needed to win in
Pommerman, and compose an insufficient set (more details in Appendix K). It is
critical for agents to learn from the environment in addition to the advisors.
Training and execution results in Figure 4 shows the superior performance of
MA-TLQL, the only algorithm that outperforms the best advisor ($p<0.05$) and
all baselines ($p<0.02$). Surprisingly, TLQL performs better than MA-TLAC
($p<0.02$), likely due to the positive bias of $Q$-learning. This experiment
reinforces the observation that MA-TLQL is capable of learning from good
advisors and avoids bad advisors (also see Appendix E). Since MA-TLQL
outperforms the best advisor, this experiment demonstrates that MA-TLQL can
learn from both, advisors and through direct interactions with the
environment, hence having a much improved sample efficiency as compared to
other algorithms that learn only from the environment. This is observed during
both training and execution.

(a) Training

(b) Execution

Figure 5. Two-agent Pommerman with four insufficient advisors of similar
quality (Experiment 4)

Experiment 4: This is similar to the Experiment 2: four advisors have similar
quality, but each understands a different Pommerman skill. However, our set of
advisors in this experiment are insufficient to teach all the skills in
Pommerman, and the agent must also learn from the environment. The results in
Figure 5 shows that MA-TLQL is capable of leveraging the combined expertise of
the advisors and learning from the environment to obtain the best performance,
as compared to the baselines ($p<0.04$) and advisors ($p<0.05$). This makes
MA-TLQL more sample efficient than the prior algorithms.

(a)  Training

(b)  Execution

Figure 6. Team (mixed) Pommerman (Experiment 5)

Experiment 5: We now switch to a four-agent version of Pommerman, which is two
vs. two. This is a mixed setting as agents need to learn cooperative as well
as competitive skills. Overall, this is a more complex domain with a larger
state space. We consider four sufficient advisors of different quality,
similar to Experiment 1. We conduct two phases — training (for 50,000
episodes) and execution (for 1000 episodes). The training and execution
results in Figure 6 show that MA-TLQL provides the best performance compared
to the baselines ($p<0.04$) but does not perform better than the best
available advisor. Since this is a more complex domain, MA-TLQL needs a larger
training period for learning good policies. However, MA-TLQL still performs
better than the average performance of the four advisors ($p<0.03$). We
conclude that although MA-TLQL’s performance suffers in the more difficult
mixed setting, it still outperforms all the other baselines and is capable of
distinguishing between good and bad advisors (see also Appendix E). From both
training and execution results in Figure 6, we note that MA-TLQL has a
superior sample efficiency as compared to the other baselines.

(a) Training

(b) Execution

Figure 7. Cooperative Pursuit setting (Experiment 6)

Experiment 6: This experiment switches to the cooperative Pursuit domain Gupta
et al. (2017). There are eight pursuer learning agents that learn to capture a
set of 30 randomly moving targets (evaders) (details in Appendix K). We use
four pre-trained DQN networks as the advisors, learning for 500, 1000, 1500,
and 2000 episodes, respectively. We again have two phases — training and
execution. During training, all algorithms are trained for 2000 episodes. The
trained networks are then used in the execution phase for 100 episodes with no
further training or influence from advisors. Figure 7(a) plots the episodic
rewards obtained during training and the Figure 7(b) plots the number of
targets captured in the execution phase, where MA-TLQL shows the best
performance ($p<0.03$). Hence, MA-TLQL can outperform all baselines in a
cooperative environment as well.

(a) Training

(b) Execution

Figure 8. Mixed Predator-Prey setting (Experiment 7)

Experiment 7: This final experiment considers a mixed cooperative competitive
Predator-Prey environment which is a part of the Multi Particle Environment
(MPE) suite Lowe et al. (2017). Our implementation uses a discrete action
space and a continuous state space (more details in Appendix K). There are a
total of eight predators trying to capture eight prey (prey are not removed,
but respawned upon capture). In our experiment, each algorithm trains the
predators while the prey is trained using a standard DQN opponent. The
experiments have two phases of training and execution, which is modelled as a
CTDE setting. Here each agent obtains information about the actions and
rewards of all other agents during training, but only has local observation
during execution. Since this environment requires decentralization during
execution, we omit the fully centralized MA-TLQL and ADMIRAL-DM. We also omit
DQfD since it gave poor performances previously. As in Experiment 6, we use
four pretrained DQN (predator) networks as advisors (trained for 1000, 2000,
7000, and 12000 episodes). Training is conducted for 12000 episodes and
execution is conducted for 100 episodes. The training results in Figure 8(a)
(plot of episodic rewards) show that MA-TLAC is the most sample efficient
compared to other algorithms as it is able to leverage the available advisors
better than others, thus outperforming them ($p<0.04$). The execution results
in Figure 8(b) plots the average prey captured by each algorithm. MA-TLAC
outperforms others during execution as well ($p<0.03$).

From all the p-values across the seven experiments, we note that most of our
observations are statistically significant. Despite observing MA-TLQL
outperforming the best advisor in many of the experiments, some of these
comparisons are not statistically significant (i.e., $p\geq 0.05$). While the
main experiments of the paper consider fixed advisors, our algorithms can also
be implemented with learning/changing advisors (see Appendix G). In Appendix I
we study performances under different numbers of advisors. Also, our
algorithms can be used along with opponent modelling techniques as done by
prior works He et al. (2016) (more details in Appendix H).

##  7\. Ablation Study

In this section, we run an ablation study on the three components of MA-TLQL
that differ from the previously introduced TLQL algorithm by Li et al. Li et
al. (2019). To recall these three components are: i) joint action (JA)
updates, ii) ensemble method (EM), and iii) advisor evaluation (AE). For this
ablation study we will consider the two-agent version of Pommerman with four
sufficient advisors having different (Experiment 1) and similar quality
(Experiment 2).

(a) Training

(b) Execution

Figure 9. Ablation results using Experiment 1

The ablation results corresponding to Experiment 1 are given in Figure 9,
where we plot the performances of TLQL and MA-TLQL in addition to TLQL with
each of the three components. In Figure 9(a) and (b), the performance of TLQL
with each of the three components is better than vanilla TLQL. TLQL using the
ensemble method (i.e., TLQL+EM) is able to perform better than vanilla TLQL,
since at the beginning of training the $Q$-values of the advisors are not
accurate, and the ensemble technique chooses the advisor action that is agreed
upon by most advisors in the given set (in line with our discussions in
Section 4). Recall that the set of four different advisors had four advisors
of decreasing quality, with the first three advisors capable of teaching some
useful Pommerman skills and the last advisor being just random (see Appendix
K). Using the ensemble prevents the use of the random advisor, as the first
three advisors are more likely to agree upon an action, increasing the
possibility of the agent choosing that action. Further, we see that TLQL
highly benefits from using the joint action update (i.e., TLQL+JA) instead of
an independent update seen in vanilla TLQL. The joint action update explicitly
considers the strategies of other agent(s) and helps in providing stronger
best responses as compared to an independent update in the multi-agent
environments. Finally, TLQL using advisor evaluation in the high-$Q$ table
(i.e., TLQL+AE) provides the best benefit compared to the other components. As
discussed in Section 3 and Section 4, the high-$Q$ definition in vanilla TLQL
is limiting since the advisor evaluation through the high-$Q$ is coupled with
the inaccurate RL policy (and AE addresses this limitation). Further, from
Figure 9, we see that MA-TLQL (integrating all the three components) shows the
best performance as compared to vanilla TLQL and individual TLQL
implementations with each of the three components ($p$ ¡ 0.05). Thus, MA-TLQL
is able to seamlessly integrate the advantages of each of the individual
components of TLQL, demonstrating its superiority.

(a) Training

(b) Execution

Figure 10. Ablation results using Experiment 2

We also consider a similar ablation study using Experiment 2 (see Figure 10).
As in Figure 9, we see that TLQL with each of the three components performs
better than vanilla TLQL. Since we have four advisors of similar quality where
each advisor is good at a different Pommerman skill, their agreement on an
action is expected to be small. Hence, the ensemble technique (i.e., TLQL+EM)
provides only a small improvement over vanilla TLQL. However, the other two
components (i.e., TLQL+JA and TLQL+AE) provides a good performance benefit
over TLQL. Finally, MA-TLQL, that integrates all the three components,
provides the best performance ($p$ ¡ 0.03).

##  8\. Conclusion

This paper provided a principled approach for learning from multiple
independent advisors in MARL. Inspired by Li et al. Li et al. (2019), we
present a two-level architecture for multi-agent environments. We discuss two
limitations in TLQL and address these limitations in our approach. Also, we
provide a fixed point guarantee and sample complexity bounds regarding the
learning of MA-TLQL. Additionally, we provided an actor-critic implementation
that can work in the CTDE paradigm. Further, we performed an extensive
experimental analysis of MA-TLQL and MA-TLAC in cooperative, competitive, and
mixed settings, where we show that these algorithms are capable of suitably
leveraging a set of advisors, and perform better than baselines. As future
work, we would like to consider human advisors and further explore some
avenues in the real-world context.

## Acknowledgements

Resources used in preparing this research were provided by the province of
Ontario and the government of Canada through CIFAR, NSERC and companies
sponsoring the Vector Institute. Part of this work has taken place in the
Intelligent Robot Learning (IRL) Lab at the University of Alberta, which is
supported in part by research grants from the Alberta Machine Intelligence
Institute (Amii); a Canada CIFAR AI Chair, Amii; Compute Canada; Huawei;
Mitacs; and NSERC.

## References

  * (1)
  * Amir et al. (2016) Ofra Amir, Ece Kamar, Andrey Kolobov, and Barbara J. Grosz. 2016\.  Interactive Teaching Strategies for Agent Training. In _IJCAI_. IJCAI Press, New York, NY, USA, 9-15 July 2016, 804–811.
  * Barrett et al. (2017) Samuel Barrett, Avi Rosenfeld, Sarit Kraus, and Peter Stone. 2017.  Making friends on the fly: Cooperating with new teammates.  _Artificial Intelligence_ 242 (2017), 132–171.
  * Bertsekas and Tsitsiklis (1996) Dimitri P. Bertsekas and John N. Tsitsiklis. 1996.  _Neuro-dynamic programming_. Optimization and neural computation series, Vol. 3.  Athena Scientific, Chestnut Street, USA.
  * Brys et al. (2015) Tim Brys, Anna Harutyunyan, Halit Bener Suay, Sonia Chernova, Matthew E. Taylor, and Ann Nowé. 2015.  Reinforcement Learning from Demonstration through Shaping. In _IJCAI, July 25-31, 2015_. AAAI Press, Buenos Aires, Argentina, 3352–3358.
  * Even-Dar and Mansour (2003) Eyal Even-Dar and Yishay Mansour. 2003.  Learning Rates for Q-learning.  _Journal of Machine Learning Research_ 5 (2003), 1–25.
  * Fernández and Veloso (2006) Fernando Fernández and Manuela M. Veloso. 2006.  Probabilistic policy reuse in a reinforcement learning agent. In _5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), May 8-12, 2006_. ACM, Hakodate, Japan, 720–727.
  * Gao et al. (2018) Yang Gao, Huazhe Xu, Ji Lin, Fisher Yu, Sergey Levine, and Trevor Darrell. 2018\.  Reinforcement Learning from Imperfect Demonstrations. In _ICLR, April 30 - May 3, 2018, Workshop Track Proceedings_. OpenReview.net, Vancouver, BC, Canada.
  * Gupta et al. (2017) Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. 2017\.  Cooperative multi-agent control using deep reinforcement learning. In _AAMAS_. Springer, IFAAMAS, Sao Paulo, Brazil, 66–83.
  * He et al. (2016) He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daumé III. 2016.  Opponent modeling in deep reinforcement learning. In _International conference on machine learning_. PMLR, New York City, US, 1804–1813.
  * Helou et al. (2021) Bassam Helou, Aditya Dusi, Anne Collin, Noushin Mehdipour, Zhiliang Chen, Cristhian Lizarazo, Calin Belta, Tichakorn Wongpiromsarn, Radboud Duintjer Tebbens, and Oscar Beijbom. 2021.  The Reasonable Crowd: Towards evidence-based and interpretable models of driving behavior. In _IROS_. IEEE, Prague, Czech Republic, 6708–6715.
  * Hernandez-Leal et al. (2019) Pablo Hernandez-Leal, Bilal Kartal, and Matthew E. Taylor. 2019\.  A survey and critique of multiagent deep reinforcement learning.  _Autonomous Agents and Multi-Agent Systems_ 33, 6 (01 Nov 2019), 750–797.  https://doi.org/10.1007/s10458-019-09421-1
  * Hester et al. (2018) Todd Hester, Matej Vecerík, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, Gabriel Dulac-Arnold, John P. Agapiou, Joel Z. Leibo, and Audrunas Gruslys. 2018\.  Deep Q-learning From Demonstrations. In _AAAI, February 2-7, 2018_. AAAI Press, New Orleans, Louisiana, USA.
  * Hu and Wellman (2003) Junling Hu and Michael P Wellman. 2003.  Nash Q-learning for general-sum stochastic games.  _JMLR_ 4, Nov (2003), 1039–1069.
  * Jaakkola et al. (1994) Tommi Jaakkola, Michael I. Jordan, and Satinder P. Singh. 1994\.  On the Convergence of Stochastic Iterative Dynamic Programming Algorithms.  _Neural Computation_ 6, 6 (1994), 1185–1201.  https://doi.org/10.1162/neco.1994.6.6.1185
  * Jain et al. (2020) Piyush Jain, Sean CP Coogan, Sriram Ganapathi Subramanian, Mark Crowley, Steve Taylor, and Mike D Flannigan. 2020.  A review of machine learning applications in wildfire science and management.  _Environmental Reviews_ 28, 4 (2020), 478–505.
  * Jing et al. (2020) Mingxuan Jing, Xiaojian Ma, Wenbing Huang, Fuchun Sun, Chao Yang, Bin Fang, and Huaping Liu. 2020.  Reinforcement Learning from Imperfect Demonstrations under Soft Expert Guidance. In _AAAI, February 7-12, 2020_. AAAI Press, New York, NY, USA, 5109–5116.
  * Kim et al. (2013) Beomjoon Kim, Amir-massoud Farahmand, Joelle Pineau, and Doina Precup. 2013.  Learning from Limited Demonstrations. In _NeurIPS_. Morgan Kaufmann Publishers, Lake Tahoe, Nevada, United States, 2859–2867.
  * Kim et al. (2020) Dong-Ki Kim, Miao Liu, Shayegan Omidshafiei, Sebastian Lopez-Cot, Matthew Riemer, Golnaz Habibi, Gerald Tesauro, Sami Mourad, Murray Campbell, and Jonathan P. How. 2020\.  Learning Hierarchical Teaching Policies for Cooperative Agents. In _AAMAS, May 9-13, 2020_. IFAAMAS, Auckland, New Zealand, 620–628.
  * Konda and Tsitsiklis (1999) Vijay R. Konda and John N. Tsitsiklis. 1999.  Actor-Critic Algorithms. In _NeurIPS_. The MIT Press, Denver, CO, USA.
  * Levine et al. (2016) Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. 2016.  End-to-end training of deep visuomotor policies.  _JMLR_ 17, 1 (2016), 1334–1373.
  * Li et al. (2019) Mao Li, Yi Wei, and Daniel Kudenko. 2019.  Two-level Q-learning: learning from conflict demonstrations.  _The Knowledge Engineering Review_ 34 (2019).
  * Littman (1994) Michael L. Littman. 1994\.  Markov Games as a Framework for Multi-Agent Reinforcement Learning. In _ICML, July 10-13, 1994_. Morgan Kaufmann, New Brunswick, NJ, USA, 157–163.
  * Liu et al. (2021) Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. 2021\.  A Sharp Analysis of Model-based Reinforcement Learning with Self-Play. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 139)_. PMLR, Virtual Event, 7001–7010.
  * Lowe et al. (2017) Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. 2017\.  Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. In _NeurIPS, December 4-9, 2017_. Morgan Kaufmann Publishers, Long Beach, CA, USA, 6379–6390.
  * Matignon et al. (2012) Laetitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. 2012.  Independent reinforcement learners in cooperative markov games: a survey regarding coordination problems.  _The Knowledge Engineering Review_ 27, 1 (2012), 1–31.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. 2015\.  Human-level control through deep reinforcement learning.  _Nature_ 518, 7540 (2015), 529–533.
  * Nash (1951) John Nash. 1951\.  Non-cooperative games.  _Annals of mathematics_ (1951), 286–295.
  * Omidshafiei et al. (2019) Shayegan Omidshafiei, Dong-Ki Kim, Miao Liu, Gerald Tesauro, Matthew Riemer, Christopher Amato, Murray Campbell, and Jonathan P. How. 2019.  Learning to Teach in Cooperative Multiagent Reinforcement Learning. In _AAAI, January 27 - February 1, 2019_. AAAI Press, Honolulu, Hawaii, USA, 6128–6136.
  * Piot et al. (2014) Bilal Piot, Matthieu Geist, and Olivier Pietquin. 2014\.  Boosted Bellman Residual Minimization Handling Expert Demonstrations. In _ECML-PKDD, September 15-19, 2014_ , Vol. 8725. Springer, Nancy, France, 549–564.
  * Reddy et al. (2012) Tummalapalli Sudhamsh Reddy, Vamsikrishna Gopikrishna, Gergely V. Zaruba, and Manfred Huber. 2012\.  Inverse reinforcement learning for decentralized non-cooperative multiagent systems. In _Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC 2012), October 14-17, 2012_. IEEE, Seoul, Korea (South), 1930–1935.
  * Resnick et al. (2018) Cinjon Resnick, Wes Eldridge, David Ha, Denny Britz, Jakob Foerster, Julian Togelius, Kyunghyun Cho, and Joan Bruna. 2018\.  Pommerman: A multi-agent playground.  _arXiv preprint arXiv:1809.07124_ (2018).
  * Shapley (1953) Lloyd S Shapley. 1953\.  Stochastic games.  _Proceedings of the national academy of sciences_ 39, 10 (1953), 1095–1100.
  * Silva and Costa (2019) Felipe Leno Da Silva and Anna Helena Reali Costa. 2019.  A Survey on Transfer Learning for Multiagent Reinforcement Learning Systems.  _JAIR_ 64 (2019), 645–703.
  * Silva et al. (2017) Felipe Leno Da Silva, Ruben Glatt, and Anna Helena Reali Costa. 2017.  Simultaneously Learning and Advising in Multiagent Reinforcement Learning. In _AAMAS, May 8-12, 2017_. ACM, Sao Paulo, Brazil, 1100–1108.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. 2016\.  Mastering the game of Go with deep neural networks and tree search.  _Nature_ 529, 7587 (2016), 484.
  * Song et al. (2021) Ziang Song, Song Mei, and Yu Bai. 2021.  When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?  _arXiv preprint arXiv:2110.04184_ (2021).
  * Subramanian (2023) Sriram Ganapathi Subramanian. 2023\.  Learning from Multiple Independent Advisors in Multi-agent Reinforcement Learning.  https://github.com/Sriram94/matlql
  * Subramanian et al. (2022) Sriram Ganapathi Subramanian, Kate Larson, Matthew Taylor, and Mark Crowley. 2022.  Multi-Agent Advisor Q-Learning.  _Journal of Artificial Intelligence Research_ 74 (2022), 1–74.
  * Sutton and Barto (1998) Richard S Sutton and Andrew G Barto. 1998.  _Introduction to reinforcement learning_. Vol. 135.  MIT press, Cambridge.
  * Szepesvari and Littman (1999) Csaba Szepesvari and Michael L Littman. 1999.  A unified analysis of value-function-based reinforcement-learning algorithms.  _Neural computation_ 11, 8 (1999), 2017–2060.
  * Tan (1993) Ming Tan. 1993.  Multi-agent reinforcement learning: Independent vs. cooperative agents. In _ICML_. Cambridge University Press, Amherst, MA, USA, 330–337.
  * Taylor et al. (2011) Matthew E. Taylor, Halit Bener Suay, and Sonia Chernova. 2011\.  Integrating reinforcement learning with human demonstrations of varying ability. In _AAMAS, May 2-6, 2011_. IFAAMAS, Taipei, Taiwan, 617–624.
  * Terry et al. (2020) Justin K Terry, Benjamin Black, Mario Jayakumar, Ananth Hari, Luis Santos, Clemens Dieffendahl, Niall L Williams, Yashas Lokesh, Ryan Sullivan, Caroline Horsch, and Praveen Ravi. 2020.  PettingZoo: Gym for Multi-Agent Reinforcement Learning.  (2020).
  * Torrey and Taylor (2013) Lisa Torrey and Matthew E. Taylor. 2013.  Teaching on a budget: agents advising agents in reinforcement learning. In _AAMAS, May 6-10, 2013_. IFAAMAS, Saint Paul, MN, USA, 1053–1060.
  * van Hasselt (2010) Hado van Hasselt. 2010\.  Double Q-learning. In _NeurIPS_. Curran Associates, Inc., Vancouver, British Columbia, Canada, 2613–2621.
  * Wang et al. (2018) Yixi Wang, Wenhuan Lu, Jianye Hao, Jianguo Wei, and Ho-fung Leung. 2018.  Efficient Convention Emergence through Decoupled Reinforcement Social Learning with Teacher-Student Mechanism. In _AAMAS, July 10-15, 2018_. IFAAMAS / ACM, Stockholm, Sweden, 795–803.
  * Wang and Taylor (2017) Zhaodong Wang and Matthew E. Taylor. 2017.  Improving Reinforcement Learning with Confidence-Based Demonstrations. In _IJCAI, August 19-25, 2017_. ICJAI, Melbourne, Australia, 3027–3033.
  * Watkins and Dayan (1992) Christopher JCH Watkins and Peter Dayan. 1992.  Q-learning.  _Machine Learning_ 8, 3-4 (1992), 279–292.
  * Waugh et al. (2011) Kevin Waugh, Brian D. Ziebart, and Drew Bagnell. 2011\.  Computational Rationalization: The Inverse Equilibrium Problem. In _ICML, June 28 - July 2, 2011_. Omnipress, Bellevue, Washington, USA, 1169–1176.
  * Yang et al. (2021) Tianpei Yang, Weixun Wang, Hongyao Tang, Jianye Hao, Zhaopeng Meng, Hangyu Mao, Dong Li, Wulong Liu, Yingfeng Chen, Yujing Hu, et al. 2021\.  An Efficient Transfer Learning Framework for Multiagent Reinforcement Learning.  _NeurIPS, Virtual Event_ 34 (2021).
  * Yang et al. (2018) Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. 2018\.  Mean Field Multi-Agent Reinforcement Learning. In _ICML_ , Vol. 80. PMLR, Stockholm Sweden, 5571–5580.
  * Ye et al. (2020) Dayong Ye, Tianqing Zhu, Zishuo Cheng, Wanlei Zhou, and S Yu Philip. 2020.  Differential Advising in Multi-Agent Reinforcement Learning.  _IEEE Transactions on Cybernetics_ (2020).

##  Appendix A Algorithm Pseudocodes

A complete pseudocode of a tabular implementation of our $Q$-learning based
algorithm (MA-TLQL) is given in Algorithm 1. All agents initialize a low-$Q$
table and a high-$Q$ table in line 2. Then at each state, all agents choose to
perform an action in lines 8–20. This action can come from the advisor or the
RL policy as described in Section 4. Then the action is executed, and the next
state and reward are observed in line 21. Finally, the $Q$ values for the
low-$Q$ as well as the high-$Q$ are updated (line 22 and line 23) according to
equations presented in Section 4. The value of $\epsilon^{\prime}$ is linearly
decayed from a high-value to a value close to zero during training (line 24).

To make Algorithm 1 applicable to high dimensional state and action spaces, we
provide a function approximation-based implementation of MA-TLQL in Algorithm
2. Here neural networks are used as the function approximator, and the
algorithm uses a separate target network and a replay buffer for training, as
introduced in the well-known DQN algorithm (Mnih et al., 2015). The agent
maintains a high-$Q$ network and two low-$Q$ networks (evaluation and target
networks) and updates these networks using the temporal difference (T.D.)
errors with the update equations presented in Section 4. If the full state of
the stochastic game is not available, the agent can simply use its observation
instead of the state, as applicable in most function approximation-based RL
methods.

We also extend Algorithm 2 to an actor-critic implementation described in
Algorithm 3. This algorithm is called multi-agent two-level actor-critic (MA-
TLAC). This algorithm uses the policy as the actor and the $Q$-values as the
critic, consistent with prior work (Konda and Tsitsiklis, 1999). We maintain
two actors, and two critics to reflect the two-level (high and low) nature of
our algorithm. The high-level actor determines an advisor and the high-level
critic helps train the high-level actor, using the T.D. errors. Similarly, the
low-level actor determines the appropriate action, with the low-level critic
providing the T.D. errors for training. In MA-TLAC, since we use a separate
actor network for advisor selection, we do not use the ensemble technique from
Eq. 2. Instead, the high-level actor directly chooses one amongst the given
advisors for the current state. The advantage of this algorithm is that it can
be implemented using the popular CTDE paradigm (Lowe et al., 2017), since the
actors do not require the actions of other agents for action/advisor
selection. In CTDE, global information (i.e., information from other agents)
is available during training time but not available during execution. This
CTDE based implementation also allows our method to be used in partially
observable domains, since the actors can use the local observations for
action/advisor selection while the critic can use the joint actions and states
during training, as described in Lowe et al. Lowe et al. (2017). Also, since
the ensemble technique (Eq. 2) is not used in MA-TLAC, it is also applicable
to continuous state space environments as well (unlike MA-TLQL, which is only
applicable to environments with discrete state spaces).

All the algorithm pseudocode provided in this section assume that all agents
are using the same algorithmic steps for learning where it can maintain copies
of updates of other agents, as done in prior work (Hu and Wellman, 2003). If
this is not possible, the agents would directly use the observed previous
actions of other agents for its updates.

Algorithm 1 MA-TLQL Tabular Method

1:Let $Ad^{j}$ denote a set of advisors available to the agent $j$.

2:For all $j\in{1,\ldots,N}$, $s\in S$, and $a^{j}\in A^{j}$:
$lowQ^{j}(s,a^{j},\boldsymbol{a}^{-j})\xleftarrow{}0$ where
$\boldsymbol{a}^{-j}=[a^{1},\ldots,a^{j-1},a^{j+1},\ldots,a^{N}]$

3:For all $s\in S$, $ad^{j}\in Ad^{j}$, and for all $j\in{1,\ldots,N}$:
$highQ^{j}(s,\boldsymbol{a}^{-j},ad^{j})\xleftarrow{}0$

4:Initialize a value for hyperparameters $\epsilon$ and $\epsilon^{\prime}$
and $\eta$

5:while training is not finished do

6: For each agent $j$, get the current state $s$

7: For each agent $j$, get the joint actions of other agents
$\boldsymbol{a}^{-j}$ at state $s$ using the respective copies and previous
actions of all agents

8: For each agent $j$, let $u$ be a uniform random number between 0 and 1

9: if $u$ ¡ $\epsilon^{\prime}$ then

10: Let $u^{\prime}$ be a uniform random number between 0 and 1

11: if $u^{\prime}$ ¡ $\eta$ then

12: Choose an advisor using the high-$Q$ values of agent $j$ for the current
state and joint action of other agents from Eq. 2 and use its action as the
current action $a^{j}_{t}$

13: else

14: Set the advisor $ad^{j}$ as a random advisor from $Ad^{j}$ and use its
action as the current action $a^{j}_{t}$.

15: end if

16: else if $u$ ¿ $\epsilon^{\prime}$ and $u$ ¡ $\epsilon$ then

17: Set the action $a^{j}_{t}$ as a random action from the action space
$A^{j}$

18: else

19: Choose a greedy action $a^{j}_{t}$ from the low-$Q$ value using $s$ and
the joint action of other agents

20: end if

21: Execute the joint action $\boldsymbol{a}$, observe joint reward
$\boldsymbol{r}$ and the next state $s^{\prime}$, where
$\boldsymbol{a}=[a^{1},\ldots,a^{N}]$ and
$\boldsymbol{r}=[r^{1},\ldots,r^{N}]$

22: Update value of low-$Q$ for the agent $j$ using Eq. 3. Obtain the next
actions for other agents $\boldsymbol{a^{\prime}}^{-j}$ from the respective
copies and previous actions of other agents

23: If an advisor was chosen, update value of high-$Q$ of the advisor for the
agent $j$ using Eq. 1

24: At the end of each episode, linearly decay $\epsilon^{\prime}$

25:end while

Algorithm 2 MA-TLQL Neural Network Method

1:Let $Ad^{j}$ denote a set of advisors available to the agent $j$

2:Initialize $Q_{\phi^{j}},Q_{\phi_{-}^{j}}$ for all $j\in{1,\ldots,N}$ (to
denote low-$Q$). Initialize $Q_{\theta^{j}}$, $Q_{\theta_{-}^{j}}$ for all
$j\in{1,\ldots,N}$ (to denote high-$Q$)

3:Initialize a value for hyperparameters $\epsilon$ and $\epsilon^{\prime}$
and $\eta$

4:while training is not finished do

5: For each agent $j$, get the current state $s$

6: For each agent $j$, get the joint actions of other agents
$\boldsymbol{a}^{-j}$ at state $s$ using the respective copies and previous
actions of all agents

7: For each agent $j$, let $u$ be a uniform random number between 0 and 1

8: if $u$ ¡ $\epsilon^{\prime}$ then

9: Let $u^{\prime}$ be a uniform random number between 0 and 1

10: if $u^{\prime}$ ¡ $\eta$ then

11: Choose an advisor using the high-$Q$ values of agent $j$ from Eq. 2 for
the current state and joint action of other agents using the high-$Q$,
$Q_{\theta^{j}}$, and use its action as the current action $a^{j}_{t}$

12: else

13: Set the advisor $ad^{j}$ as a random advisor from $Ad^{j}$ and use its
action as the current action $a^{j}_{t}$.

14: end if

15: else if $u$ ¿ $\epsilon^{\prime}$ and $u$ ¡ $\epsilon$ then

16: Set the action $a^{j}_{t}$ as a random action from the action space
$A^{j}$

17: else

18: Choose a greedy action $a^{j}_{t}$ from the low-$Q$, $Q_{\phi^{j}}$, using
$s$ and the joint action of other agents

19: end if

20: Execute the joint action $\boldsymbol{a}$, observe joint reward
$\boldsymbol{r}$ and the next state $s^{\prime}$, where
$\boldsymbol{a}=[a^{1},\ldots,a^{N}]$ and
$\boldsymbol{r}=[r^{1},\ldots,r^{N}]$

21: For each agent $j$, store $\langle
s,\boldsymbol{a},\boldsymbol{r},s^{\prime},\boldsymbol{a^{\prime}}\rangle$ in
replay buffer $\mathcal{D}^{j}$, where $\boldsymbol{a}=[a^{1},\ldots,a^{N}]$,
$\boldsymbol{a^{\prime}}=[a^{\prime 1},\ldots,a^{\prime N}]$. Obtain the next
actions for other agents $\boldsymbol{a^{\prime}}^{-j}$ from the respective
copies and previous actions of other agents

22: If an advisor was used, for each agent $j$, store $\langle
s,\boldsymbol{a},\boldsymbol{r},s^{\prime},\boldsymbol{a^{\prime}},ad^{j}\rangle$
in replay buffer $\mathcal{D}^{\prime j}$, where $ad^{j}$ is the advisor

23: Set the next state $s^{\prime}$ as the current state $s$

24: At the end of each episode, linearly decay $\epsilon^{\prime}$

25: while j = 1 to N do

26: Sample a minibatch of K experiences $\langle
s,\boldsymbol{a},\boldsymbol{r},s^{\prime},\boldsymbol{a^{\prime}}\rangle$
from $\mathcal{D}^{j}$

27: Set $y^{j}=r^{j}+\gamma\max_{a^{\prime
j}}Q_{\phi^{j}_{-}}(s^{\prime},\boldsymbol{a^{\prime}}^{-j},a^{\prime j})$
according to Eq. 3

28: Update the $Q$-network $\phi^{j}$ by minimizing the loss
$\mathcal{L}(\phi^{j})=\frac{1}{K}\sum(y^{j}-Q_{\phi^{j}}(s,\boldsymbol{a}^{-j},a^{j}))^{2}$

29: Sample a minibatch of K experiences $\langle
s,\boldsymbol{a},\boldsymbol{r},s^{\prime},\boldsymbol{a^{\prime}},ad^{j}\rangle$
from $\mathcal{D^{\prime}}^{j}$

30: Set $y^{j}=r^{j}+\gamma
Q_{\theta^{j}_{-}}(s^{\prime},\boldsymbol{a^{\prime}}^{-j},ad^{j})$ according
to Eq. 1

31: Update the $Q$-network $\theta^{j}$ by minimizing the loss
$\mathcal{L}(\theta^{j})=\frac{1}{K}\sum(y^{j}-Q_{\theta^{j}}(s,\boldsymbol{a}^{-j},ad^{j}))^{2}$

32: end while

33: Update the parameters of the target network for each agent by copying over
the evaluation network every $\mathcal{T}$ steps:
$\phi^{j}_{-}\xleftarrow{}\phi^{j}$ and
$\theta^{j}_{-}\xleftarrow{}\theta^{j}$

34:end while

Algorithm 3 MA-TLAC

1:Let $Ad^{j}$ denote a set of advisors available to the agent $j$

2:Initialize $Q_{\phi^{j}},\pi_{\phi_{-}^{j}}$, the low-level critic and actor
networks for all $j\in\\{1,\ldots,n\\}$

3:Initialize $Q_{\theta^{j}},\pi_{\theta_{-}^{j}}$, the high-level critic and
actor networks for all $j\in\\{1,\ldots,n\\}$

4:Initialize a value for hyperparameters $\epsilon$ and $\epsilon^{\prime}$
and $\eta$

5:while training is not finished do

6: For each agent $j$, get the current state $s$

7: For each agent $j$, let $u$ be a uniform random number between 0 and 1

8: if $u$ ¡ $\epsilon^{\prime}$ then

9: Let $u^{\prime}$ be a uniform random number between 0 and 1

10: if $u^{\prime}$ ¡ $\eta$ then

11: Choose an advisor $ad^{j}$ using the high-level actor $\pi_{\theta^{j}}$,
for the agent $j$, for the current state $s$, and use its action as the
current action $a^{j}$

12: else

13: Set the advisor $ad^{j}$ as a random advisor from $Ad^{j}$ and use its
action as the current action $a^{j}$

14: end if

15: else if $u$ ¿ $\epsilon^{\prime}$ and $u$ ¡ $\epsilon$ then

16: Set the action $a^{j}$ as a random action from the action space $A^{j}$

17: else

18: Choose a greedy action $a^{j}$ from the low-level actor, $\pi_{\phi^{j}}$,
using $s$

19: end if

20: Execute the joint action $\boldsymbol{a}$, observe joint reward
$\boldsymbol{r}$ and the next state $s^{\prime}$, where
$\boldsymbol{a}=[a^{1},\ldots,a^{N}]$ and
$\boldsymbol{r}=[r^{1},\ldots,r^{N}]$

21: For each agent $j$, obtain the joint actions of other agents
$\boldsymbol{a}^{-j}$ (current observed actions of other agents) at state $s$

22: Set $y^{j}=r^{j}+\gamma\max_{a^{\prime
j}}Q_{\phi^{j}}(s^{\prime},\boldsymbol{a^{\prime}}^{-j},a^{\prime j})$
according to Eq. 3

23: For each $j$, update the low-level critic by minimizing the loss
$\mathcal{L}(\phi^{j})=(y^{j}-Q_{\phi^{j}}(s,\boldsymbol{a}^{-j},a^{j}))^{2}$

24: For each $j$, calculate the advantage estimate using the relation
$A(s,\boldsymbol{a}^{-j},a^{j})=y^{j}-\sum_{a^{j}}\pi_{\phi_{-}^{j}}(a^{j}|s)Q_{\phi^{j}}(s,\boldsymbol{a}^{-j},a^{j})$

25: For each $j$, update the low-level actor using the log loss
$\mathcal{J}(\phi_{-}^{j})=\log\pi_{\phi_{-}^{j}}(a^{j}|s)A(s,\boldsymbol{a}^{-j},a^{j})$

26: If an agent $j$ used an advisor $ad^{j}$, then update the advisor’s
$Q$-estimate.

27: For each $j$, set $y^{j}=r^{j}+\gamma
Q_{\theta^{j}}(s^{\prime},\boldsymbol{a^{\prime}}^{-j},ad^{j})$ according to
Eq. 1

28: Obtain the next actions for other agents $\boldsymbol{a^{\prime}}^{-j}$
from the respective copies

29: For each $j$, update the high-level critic by minimizing the loss
$\mathcal{L}(\theta^{j})=(y^{j}-Q_{\theta^{j}}(s,\boldsymbol{a}^{-j},ad^{j}))^{2}$
where $ad^{j}$ is the advisor chosen by the agent $j$

30: For each $j$, calculate the advantage estimate using the relation
$A(s,\boldsymbol{a}^{-j},ad^{j})=y^{j}-\sum_{ad^{j}}\pi_{\theta_{-}^{j}}(ad^{j}|s)Q_{\theta^{j}}(s,\boldsymbol{a}^{-j},ad^{j})$

31: For each $j$, update the high-level actor using the log loss
$\mathcal{J}(\theta_{-}^{j})=\log\pi_{\theta_{-}^{j}}(a^{j}|s)A(s,\boldsymbol{a}^{-j},ad^{j})$

32: Set the next state as the current state $s=s^{\prime}$

33: At the end of each episode, linearly decay $\epsilon^{\prime}$

34:end while

##  Appendix B Proof of Theorem 1

######  Theorem 1.

Given Assumptions 1, 2, 3, the low-$Q$ values of an agent $j$ converges to its
Nash $Q$ value in the limit ($t\xrightarrow{}\infty$).

###### Proof.

Our proof will be along the lines of Theorem 3 in Subramanian et al.
Subramanian et al. (2022).

Let us consider a lemma from prior work.

######  Lemma 1.

A random iterative process

$\begin{array}[]{l}\Delta_{t+1}(x)=(1-\alpha_{t}(x))\Delta_{t}(x)+\alpha_{t}(x)F_{t}(x)\end{array}{}$
(7)

where $x\in X$, $t=0,1,\ldots,\infty$, converges to zero with probability one
(w. p. 1) if the following properties hold:

1\. The set of possible states $X$ is finite.

2\. $0\leq\alpha_{t}(x)\leq 1$, $\sum_{t}\alpha_{t}(x)=\infty$,
$\sum_{t}\alpha^{2}_{t}(x)<\infty$ w. p. 1, where the probability is over the
learning rates $\alpha_{t}$.

3\.
$||\operatorname{\mathbb{E}}\\{{F_{t}(x)|\mathscr{P}_{t}}\\}||_{W}\leq\mathscr{K}||\Delta_{t}||_{W}+c_{t}$,
where $\mathscr{K}\in[0,1)$ and $c_{t}$ converges to zero w. p. 1.

4\. $\textrm{{var}}\\{F_{t}(x)|\mathscr{P}_{t}\\}\leq
K(1+||\Delta_{t}||_{W})^{2}$, where $K$ is some constant.

Here $\mathscr{P}_{t}$ is an increasing sequence of $\sigma$-fields that
includes the past of the process. In particular, we assume that
$\alpha_{t},\Delta_{t},F_{t-1}\in\mathscr{P}_{t}$. The notation
$||\cdot||_{W}$ refers to some (fixed) weighted maximum norm and the notation
var refers to the variance.

###### Proof.

Refer to Theorem 1 in Jaakola et al. Jaakkola et al. (1994) for proof.

∎

Across this section, since we are only focusing on the low-$Q$ values, with a
small abuse of notation, we will use $Q$ to denote the low-$Q$ values. Now, we
define a Nash operator $P_{t}$, using the following equation,

$\begin{array}[]{l}P_{t}Q^{k}(s,\boldsymbol{a})=\operatorname{\mathbb{E}}_{s^{\prime}\sim
p}[r^{k}_{t}(s,\boldsymbol{a})+\gamma\pi^{1}_{*}(s^{\prime})\cdots\pi^{n}_{*}(s^{\prime})Q^{k}(s^{\prime})]\end{array}$
(8)

where $s^{\prime}$ is the state at time $t+1$,
$(\pi^{1}_{*}(s^{\prime}),\ldots,\pi^{n}_{*}(s^{\prime}))$ is the Nash
equilibrium solution for the stage game
$(Q^{1}(s^{\prime}),\ldots,Q^{n}(s^{\prime}))$, and $p$ is the transition
function. $Q^{k}$ denotes the $Q$-value of a representative agent $k$.

######  Lemma 2.

Under Assumption 3, the Nash operator as defined in Eq. 8 forms a contraction
mapping with the fixed point being the Nash $Q$-value of the game.

###### Proof.

See Theorem 17 of Hu and Wellman Hu and Wellman (2003). ∎

Now, since the $P_{t}$ operator forms a contraction mapping,
$||P_{t}Q^{j}-P_{t}Q^{j}_{*}||\leq\gamma||Q^{j}-Q^{j}_{*}||$, is satisfied for
some $\gamma\in[0,1)$ and all $Q^{j}$. Here $Q^{j}_{*}$ is the Nash $Q$-value
of the agent $j$.

The objective is to apply Lemma 1 to show that the low-$Q$ in MATLQL converge
to the Nash $Q$ values.

The first two conditions of Lemma 1 are satisfied from the Assumption 1 and
Assumption 2. Now, comparing Eq. 7 and Eq. 3 we get that $x$ can be associated
with the state joint action pairs $(s,\boldsymbol{a})$ and
$\Delta_{t}(s_{t},a_{t})$ can be associated with
$Q^{j}_{t}(s,\boldsymbol{a})-Q^{j}_{*}(s,\boldsymbol{a})$. Here,
$Q^{j}_{*}(s,\boldsymbol{a})$ is the Nash $Q$ value of the agent $j$.

Now we get

$\begin{array}[]{l}\Delta_{t+1}(x)=(1-\alpha_{t}(x))\Delta_{t}(x)+\alpha_{t}(x)F_{t}(x),\end{array}{}$
(9)

where

$\begin{array}[]{l}F_{t}(x)=r^{j}_{t}+\gamma
v^{Nash,j}(s_{t+1})-Q^{j}_{*}(s_{t},\boldsymbol{a_{t}})\\\
\quad\quad\quad+\gamma[\max_{a^{j}}Q^{j}_{t}(s_{t+1},\boldsymbol{a}_{t+1})-v^{Nash,j}(s_{t+1})]\\\
\\\
\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}r^{j}_{t}+\gamma
v^{Nash,j}(s_{t+1})-Q^{j}_{*}(s_{t},\boldsymbol{a}_{t})+C^{j}_{t}(s_{t},\boldsymbol{a}_{t})\\\
\\\
\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}F_{t}^{Q,j}(s_{t},\boldsymbol{a}_{t})+C^{j}_{t}(s_{t},\boldsymbol{a}_{t})\par\end{array}{}$
(10)

The Nash value function $v^{Nash,j}(s)$ of an agent $j$ is defined as the
expected cumulative discounted future rewards obtained by the agent $j$, given
that all agents follow the Nash policy $\boldsymbol{\pi}_{*}$.

Here, we set,
$F_{t}(s_{t},\boldsymbol{a}_{t})=F_{t}^{Q,j}(s_{t},\boldsymbol{a}_{t})$ =
$C^{j}_{t}(s_{t},\boldsymbol{a}_{t})=0$ if
$(s,\boldsymbol{a})\neq(s_{t},\boldsymbol{a}_{t})$. Let the $\sigma$-field
generated by all the random variables provided by
$(s_{t},\alpha_{t},a^{1}_{t},\ldots,a^{n}_{t},r_{t-1},\ldots,s_{1},\alpha_{1},a_{1},Q_{0})$,
be represented by $\mathscr{P}_{t}$. Now, all the $Q$-values are
$\mathscr{P}_{t}$ measurable which makes $\Delta_{t}$ and $F_{t}$,
$\mathscr{P}_{t}$ measurable and this satisfies the measurability condition of
Lemma 1.

Hu and Wellman Hu and Wellman (2003) proved that the result,
$v^{Nash,j}(s_{t+1})\triangleq
v^{j}(s^{\prime},\pi^{1}_{*},\ldots,\pi^{n}_{*})=\pi^{1}_{*}(s^{\prime})\cdots\pi^{n}_{*}(s^{\prime})Q^{j}_{*}(s^{\prime})$
holds (see the proof in Lemma 10 of Hu and Wellman (2003)). Hence, from Lemma
2, we can show that the $\operatorname{\mathbb{E}}[F^{Q}_{t}]$ forms a
contraction mapping. This can be done using the fact that
$\operatorname{\mathbb{E}}(P_{t}Q_{*})=Q_{*}$ (refer to Lemma 11 in Hu and
Wellman (2003)). Here, the norm is the maximum norm on the joint action.

Now, we have the following for all $t$,

$\begin{array}[]{l}||\operatorname{\mathbb{E}}[F_{t}^{Q,j}(s_{t},\boldsymbol{a}_{t})|\mathscr{P}_{t}]||\leq\gamma||Q^{j}_{t}(s_{t},\boldsymbol{a}_{t})-Q^{j}_{*}(s_{t},\boldsymbol{a_{t}})||=\gamma||\Delta_{t}||\end{array}{}$
(11)

Now from Eq. 10,

$\begin{array}[]{l}||\operatorname{\mathbb{E}}[F_{t}(s_{t},\boldsymbol{a}_{t})|\mathscr{P}_{t}]||\\\
\\\
\leq||\operatorname{\mathbb{E}}[F_{t}^{Q,j}(s_{t},\boldsymbol{a}_{t})|\mathscr{P}_{t}]||+||\operatorname{\mathbb{E}}[C^{j}_{t}(s_{t},\boldsymbol{a}_{t})|\mathscr{P}_{t}]||\\\
\\\
\leq\gamma||\Delta_{t}||+||\operatorname{\mathbb{E}}[C^{j}_{t}(s_{t},\boldsymbol{a}_{t})|\mathscr{P}_{t}]||\end{array}$
(12)

This satisfies the third condition of Lemma 1, provided that
$c_{t}=||\operatorname{\mathbb{E}}[C^{j}_{t}(s_{t},\boldsymbol{a}_{t})|\mathscr{P}_{t}]||$
converges to 0 with probability 1 (w. p. 1.). From the definition of
$C^{j}_{t}$ and the Assumption 3, it can be shown that the value of
$C^{j}_{t}$ converges to 0 in the limit of time (see Theorem 3 in Subramanian
et al. Subramanian et al. (2022)).

Thus, it follows from Lemma 1 that the process $\Delta_{t}$ converges to 0 and
hence, low-$Q$ value for an agent $j$, converges to Nash $Q$ value
$Q^{j}_{*}$.

∎

##  Appendix C Proof of Theorem 2

In this section, we give the proof for Theorem 2. For providing this bound we
use the notion of covering time $L$. The covering time means that within $L$
steps from any start state, all state-joint action pairs are performed at
least once by all agents. Similar to Dar and Mansour Even-Dar and Mansour
(2003), we clarify that we do not need to assume that the state-joint action
pairs are being generated by any particular strategy. Same as in Appendix B,
across this section, we will use $Q$ to denote the low-$Q$ values. For a
representative agent $j$, we will focus on the value of
$r^{j}_{t}=||Q^{j}_{t}-Q^{j}_{*}||$ and the aim is to bound the time until
$r^{j}_{t}\leq\epsilon$. Here the norm denotes the maximum difference of the
$Q$ values across all states and joint actions. The proof of this theorem
follows the Theorem 4 in Dar and Mansour Even-Dar and Mansour (2003). While
the work of Dar and Mansour was restricted to single-agent MDPs, our result
extends the analysis of Dar and Mansour to the general-sum stochastic game
setting.

In line with the Eq. 4, let us consider a stochastic iterative process of the
form,

$X^{j}_{t+1}(i)=(1-\alpha_{t}(i))X^{j}_{t}(i)+\alpha_{t}(i)((H_{t}X^{j}_{t})(i)+w^{j}_{t}(i)).$
(13)

As mentioned in Section 5, let us specify $\beta=\frac{1-\gamma}{2}$. Also,
consider a constant $Q^{j}_{\max}$ where the $Q^{j}_{\max}$ denotes the
maximum low-$Q$ value possible to be obtained in the stochastic game by the
agent $j$. Hence, the relation $||X_{0}||\leq Q^{j}_{\max}$ holds. Further,
let us consider a sequence $D^{j}_{k}$, with $D^{j}_{1}=Q^{j}_{\max}$ and
$D^{j}_{k+1}=(1-\beta)D^{j}_{k}$ for all $k\geq 1$. By the nature of this
construction, the sequence $D^{j}_{k}$ is guaranteed to converge to 0, since
at each step the value of $D^{j}_{k}$ is being continuously multiplied by a
fractional value. Now we can prove the following result.

######  Lemma 3.

For every $k$, there exists a time $\tau_{k}$ such that, for any
$t\geq\tau_{k}$ we have $||X^{j}_{t}||\leq D^{j}_{k}$.

###### Proof.

See Theorem 8 in Dar and Mansour Even-Dar and Mansour (2003). ∎

The Lemma 3 guarantees that at time $t\geq\tau_{k}$, for any $i$ the value of
$||X^{j}_{t}(i)||$ is in the interval $[-D^{j}_{k},D^{j}_{k}]$.

We can state the following lemma, where we bound the number of iterations
until $D^{j}_{i}\leq\epsilon$.

######  Lemma 4.

For $m\geq\frac{1}{\beta}\ln(Q^{j}_{\max}/\epsilon)$ we have
$D^{j}_{m}\leq\epsilon$.

###### Proof.

Since we have that $D^{j}_{1}=Q^{j}_{\max}$ and
$D^{j}_{i}=(1-\beta)D^{j}_{i-1}$, we will need a $m$ that satisfies
$D^{j}_{m}=Q^{j}_{\max}(1-\beta)^{m}\leq\epsilon$. By taking a logarithm on
both sides, we get

$\begin{array}[]{l}\ln\Big{(}(Q^{j}_{\max})(1-\beta)^{m}\Big{)}\leq\ln(\epsilon)\\\
\\\ \ln(Q^{j}_{\max})+m\ln(1-\beta)\leq\ln(\epsilon)\\\ \\\
\implies\ln(Q^{j}_{\max})-\ln(\epsilon)\leq-m\ln(1-\beta)\\\ \\\
\implies\ln(Q^{j}_{\max}/\epsilon)\leq m\sum_{k=0}^{\infty}\beta^{k}/k\\\ \\\
\implies 1/\beta\ln(Q^{j}_{\max}/\epsilon)\leq m.\end{array}$ (14)

In the last step we omit the higher powers since $\beta$ is a small fraction.
This proves the result. ∎

Now, we define a sequence of times $\tau_{k}$, with reference to the MA-TLQL
low-level $Q$-updates with a polynomial learning rate. Let us define
$\tau_{k+1}=\tau_{k}+L\tau^{\omega}_{k}$. Here the term $\omega$ denotes the
decay factor of the learning rate with
$\alpha^{\omega}_{t}=\frac{1}{(t+1)^{\omega}}$ for $\omega\in(1/2,1)$. The
term $L\tau^{\omega}_{k}$ specifies the number of steps needed to update each
state joint action pair at least $\tau^{\omega}_{k}$ times. The time between
the $\tau_{k}$ and $\tau_{k+1}$ is denoted as the $k^{\textrm{th}}$ iteration.
Now we provide a definition for the number of times a state joint action pair
is visited.

######  Definition 1.

Let $n(s,\boldsymbol{a},t_{1},t_{2})$ be the number of times that the state
joint action pair $(s,\boldsymbol{a})$ was performed in the time step interval
$[t_{1},t_{2}]$.

Before providing the suitable bounds, we would like to provide some equations
that relate the stochastic iterative technique given in Eq. 13 with the
$Q$-update in Eq 4.

First we provide a formal definition of a stochastic game, that will be useful
for our further analysis. Consider a stochastic game that can be defined as
follows:

######  Definition 2.

A stochastic game is defined as
$\langle\mathcal{S},N,\mathbf{A},P,\mathbf{R},\gamma\rangle$ where
$\mathcal{S}$ is a finite set of states, $N$ is the finite set of agents,
$|N|=n$, and $\mathbf{A}=A^{1}\times\ldots\times A^{n}$ is the set of joint
actions, where $A^{j}$ is the finite action set of an agent $j$, and
$\boldsymbol{a}=(a^{1},\ldots,a^{n})\in\mathbf{A}$ is the joint action where
an agent $j$ takes action $a^{j}\in A^{j}$. Furthermore,
$P_{i,k}(\boldsymbol{a}):S\times\mathbf{A}\times S\mapsto[0,1]$ is the
transition function that provides the probability of reaching state $k$ from
state $i$ when all agents are performing the joint action
$\boldsymbol{a}\in\mathbf{A}$ in state $i$,
$\boldsymbol{R}(s,\boldsymbol{a})=\\{R^{1}(s,\boldsymbol{a}),\ldots,R^{n}(s,\boldsymbol{a})\\}$
is the set of reward functions, where
$R^{j}(s,\boldsymbol{a}):S\times\mathbf{A}\mapsto\mathbb{R}^{n}$ is the reward
function of the agent $j$, and $\gamma$ is the discount factor satisfying
$0\leq\gamma<1$.

Towards the same, we define an operator $H$ that can be represented as

$\begin{array}[]{l}(HQ^{j})(i,\boldsymbol{a})=\sum_{k=0}^{|S|}P_{ik}(\boldsymbol{a})(R^{j}(i,\boldsymbol{a})+\gamma\max_{b^{j}\in
A^{j}}Q^{j}(k,\boldsymbol{b})).\end{array}$ (15)

Here the $\boldsymbol{b}=\\{b^{j},b^{-j}\\}$, where $b^{-j}$ denotes the joint
action of all agents except the agent $j$.

Rewriting the $Q$-function with $H$ we get,

$\begin{array}[]{l}Q^{j}_{t+1}(i,\boldsymbol{a})=(1-\alpha_{t}(i,\boldsymbol{a}))Q^{j}_{t}(i,\boldsymbol{a})+\alpha_{t}(i,\boldsymbol{a})((HQ^{j}_{t})(i,\boldsymbol{a})+w^{j}_{t}(i,\boldsymbol{a})).\end{array}$
(16)

Let $\overline{i}$ be the state that is reached by performing joint action
$\boldsymbol{a}$ at time $t$ in state $i$ and $r^{j}(i,\boldsymbol{a})$ be the
reward observed by the agent $j$ at state $i$; then

$\begin{array}[]{l}w^{j}_{t}(i,\boldsymbol{a})=r^{j}(i,\boldsymbol{a})+\gamma\max_{b^{j}\in
A^{j}}Q^{j}_{t}(\overline{i},\boldsymbol{b})\\\
\quad\quad\quad\quad\quad-\sum_{k=0}^{|S|}P^{j}_{ik}(\boldsymbol{a})\Big{(}R^{j}(i,\boldsymbol{a})+\gamma\max_{b^{j}\in
A^{j}}Q^{j}_{t}(k,\boldsymbol{b})\Big{)}.\end{array}$ (17)

From this construction $w^{j}_{t}$ is bounded by $Q^{j}_{\max}$ for all $t$
and has zero expectation. Further we will define two other sequences
$W^{j}_{t;\tau}$ and $Y^{j}_{t;\tau}$ where $\tau$ represents some initial
time. These are given by the following equations.

$W^{j}_{t+1;\tau_{k}}(s,\boldsymbol{a})=(1-\alpha^{\omega}_{t}(i))W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})+\alpha^{\omega}_{t}(i)w^{j}_{t}(s,\boldsymbol{a})$
(18)

where $W^{j}_{\tau_{k};\tau_{k}}(s,\boldsymbol{a})=0$. The value of
$W^{j}_{t;\tau_{k}}$ bounds the contributions of
$w^{j}_{t}(s,\boldsymbol{a})$, to the value of $Q^{j}_{t}$, starting from an
arbitrary $\tau_{k}$. Now we have

$Y^{j}_{t+1;\tau_{k}}(s,\boldsymbol{a})=(1-\alpha^{\omega}_{t}(i))Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})+\alpha^{\omega}_{t}(s,\boldsymbol{a})\gamma
D^{j}_{k}$ (19)

where $Y^{j}_{\tau_{k};\tau_{k}}=D^{j}_{k}$.

Next, we can state a lemma that will bound the $Q$-functions w.r.t the
sequences $W^{j}_{t;\tau_{k}}$ and $Y^{j}_{t;\tau_{k}}$.

######  Lemma 5.

For every state $s$ and joint action $\boldsymbol{a}$ and time $\tau_{k}$, we
have

$\begin{array}[]{l}-Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})+W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\\\
\\\ \leq Q^{j}_{*}(s,\boldsymbol{a})-Q^{j}_{t}(s,\boldsymbol{a})\\\ \\\ \leq
Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})+W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\end{array}$
(20)

###### Proof.

See Lemma 4.4 in Bertsekas and Tsitsiklis Bertsekas and Tsitsiklis (1996). ∎

From the Lemma 5 we see that a bound on the difference $r^{j}_{t}$ depends on
the bound for $Y^{j}_{t;\tau_{k}}$ and $W^{j}_{t;\tau_{k}}$. So we can bound
$Y^{j}_{t;\tau_{k}}$ and $W^{j}_{t;\tau_{k}}$ separately and two bounds
together will provide a bound for $r^{j}_{t}$.

We first provide a result on the nature of the sequence
$Y^{j}_{\tau_{k};\tau_{k}}$.

######  Lemma 6.

The sequence $Y^{j}_{t;\tau_{k}}$ is a monotonically decreasing sequence.

###### Proof.

From Eq. 19 we can write (subtract $\gamma D^{j}_{k}$ from both sides),

$\begin{array}[]{l}(Y^{j}_{t+1;\tau_{k}}(s,\boldsymbol{a})-\gamma
D^{j}_{k})\\\ \\\
=(1-\alpha^{\omega}_{t}(i))Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})+(1-\alpha^{\omega}_{t}(s,\boldsymbol{a}))\gamma
D^{j}_{k}\\\ \\\
=(1-\alpha^{\omega}_{t}(i))(Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})+\gamma
D^{j}_{k}).\end{array}$ (21)

Now, the convergence of $||Y^{j}_{t+1;\tau_{k}}(s,\boldsymbol{a})-\gamma
D^{j}_{k}||$ follows since
$\lim_{n\xrightarrow{}\infty}\Pi^{n}_{t=k}(1-\alpha^{\omega}_{t}(s,\boldsymbol{a}))=0$.
This shows that the sequence $(Y^{j}_{t+1;\tau_{k}}(s,\boldsymbol{a})-\gamma
D^{j}_{k})$ monotonically decreases to 0 and hence the sequence
$Y^{j}_{t;\tau_{k}}$ monotonically decreases to $\gamma D_{k}$. This proves
our result.

∎

Next, we provide a bound on the value of $Y^{j}_{t;\tau_{k}}$.

######  Lemma 7.

Consider the low-$Q$ update given in Eq. 4, with a polynomial learning rate
and assume that for any $t\geq\tau_{k}$ we have
$Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\leq D_{k}$. Then for any
$t\geq\tau_{k}+L\tau^{\omega}_{k}=\tau_{k+1}$ we have
$Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\leq D^{j}(\gamma+\frac{2}{e}\beta)$.

###### Proof.

For each state-joint action pair $s,\boldsymbol{a}$ we are assured that
$n(s,a,\tau_{k},\tau_{k+1})\geq\tau_{k}^{\omega}$, since the covering time is
$L$ and the underlying policy has made $L\tau^{\omega}_{k}$ steps (since we
have the relation $\tau_{k+1}=\tau_{k}+L\tau^{\omega}_{k}$).

Let $Y^{j}_{\tau_{k},\tau_{k}}(s,\boldsymbol{a})=\gamma
D^{j}_{k}+\rho^{j}_{\tau_{k}}$, where $\rho_{\tau_{k}}=(1-\gamma)D^{j}_{k}$.
Now we have the following expression,

$\begin{array}[]{l}Y^{j}_{t+1,\tau_{k}}(s,\boldsymbol{a})=(1-\alpha^{\omega}_{t})Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})+\alpha^{\omega}_{t}\gamma
D^{j}_{k}=\gamma D^{j}_{k}+(1-\alpha_{t}^{\omega})\rho^{j}_{t}\end{array}$
(22)

where $\rho^{j}_{t+1}=\rho^{j}_{t}(1-\alpha_{t}^{\omega})$. We aim to show
that after time $\tau_{k+1}=\tau_{k}+\tau_{k}^{\omega}$, for any
$t\geq\tau_{k}^{\omega}$ for any $t\geq\tau_{k+1}$ we have
$\rho^{j}_{t}\leq\frac{2}{e}\beta D^{j}_{k}$. By definition, we can rewrite
$\rho^{j}_{t}$ as,

$\begin{array}[]{l}\rho^{j}_{t}=(1-\gamma)D^{j}_{k}\Pi^{t-\tau_{k}}_{l=1}(1-\alpha^{\omega}_{l+\tau_{k}})\\\
\\\ =2\beta D^{j}_{k}\Pi_{l=1}^{t-\tau_{k}}(1-\alpha^{\omega}_{l+\tau_{k}})\\\
\\\ =2\beta
D^{j}_{k}\Pi_{l=1}^{t-\tau_{k}}(1-\frac{1}{|n(s,\boldsymbol{a},\tau_{k+1},l)|^{\omega}})\end{array}$
(23)

the last identity follows from the definition of $\alpha_{t}^{\omega}$.

Since the $\tau^{\omega}_{k}$’s are monotonically decreasing,

$\rho^{j}_{t}\leq 2\beta
D^{j}_{k}(1-\frac{1}{\tau^{\omega}_{k}})^{t-\tau_{k}}.$ (24)

For $t\geq\tau_{k}+\tau^{\omega}_{k}$ we have,

$\rho^{j}_{t}\leq 2\beta
D^{j}_{k}\Big{(}1-\frac{1}{\tau^{\omega}_{k}}\Big{)}^{\tau^{\omega}_{k}}\leq\frac{2}{e}\beta
D^{j}_{k}.$ (25)

The last step is obtained from the fact that
$\lim_{x\xrightarrow{}\infty}(1-(1/x))^{x}=1/e$.

Hence, $Y_{t;\tau_{k}}(s,\boldsymbol{a})\leq(\gamma+\frac{2}{e}\beta)D_{k}$.

∎

From Lemma 7 we have provided a bound for the term $Y^{j}_{t;\tau_{k}}$ for
$t=\tau_{k+1}$ which will automatically hold for all $t\geq\tau_{k+1}$, since
the term $Y^{j}_{t;\tau_{k}}$ is monotonically decreasing (from Lemma 6) and
deterministic (from Eq. 19 and Lemma 5).

Next we bound the term $W^{j}_{t;\tau_{k}}$ by $(1-\frac{2}{e})\beta
D^{j}_{k}$. The sum of the bounds for $W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})$
and $Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})$, would be
$(\gamma+\beta)D^{j}_{k}=(1-\beta)D^{j}_{k}=D^{j}_{k+1}$, as desired.

Now we state a definition for a sequence $\eta_{i}^{k,t,j}(s,\boldsymbol{a})$
and $W^{l,j}_{t;\tau_{k}}$.

######  Definition 3.

Let

$\begin{array}[]{l}W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})=(1-\alpha^{\omega}_{t}(s,\boldsymbol{a}))W^{j}_{t-1;\tau_{k}}(s,\boldsymbol{a})+\alpha^{\omega}_{t}(s,\boldsymbol{a})w^{j}_{t}(s,\boldsymbol{a})\\\
\\\
=\sum_{i=1}^{t-\tau_{k}}\eta^{k,t,j}_{i+\tau_{k}}(s,\boldsymbol{a})w^{j}_{i+\tau_{k}}(s,\boldsymbol{a}),\\\
\\\ \textrm{ where }\\\ \\\
\eta^{k,t,j}_{i+\tau_{k}}(s,\boldsymbol{a})=\alpha^{\omega}_{i+\tau_{k}}(s,\boldsymbol{a})\Pi^{t}_{l=\tau_{k}+i+1}(1-\alpha^{\omega}_{l}(s,\boldsymbol{a})).\end{array}$
(26)

For bounding the sequence $W^{j}_{t;\tau_{k}}$ we consider the interval
$t\in[\tau_{k+1},\tau_{k+2}]$. First we provide a lemma that bounds the
coefficients in this interval and bounds the influence of
$w^{j}_{t}(s,\boldsymbol{a})$ in this interval.

######  Lemma 8.

Let
$\tilde{w}^{j,t}_{i+\tau_{k}}(s,\boldsymbol{a})=\eta_{i+\tau_{k}}^{k,t,j}(s,\boldsymbol{a})w^{j}_{i+\tau_{k}}(s,\boldsymbol{a})$,
then for any $t\in[\tau_{k+1},\tau_{k+2}]$ the random variable
$\tilde{w}^{j}_{i+\tau_{k}}(s,\boldsymbol{a})$ has zero mean and bounded by
$(L/\tau_{k})^{\omega}Q^{j}_{\max}$.

###### Proof.

Since
$\eta_{i+\tau_{k}}^{k,t,j}((s,\boldsymbol{a}))=\alpha^{\omega}_{i+\tau_{k}}(s,\boldsymbol{a})\Pi^{t}_{l=\tau_{k}+i+1}(1-\alpha^{\omega}_{l}(s,\boldsymbol{a}))$,
we can divide $\eta^{k,t,j}_{i+\tau_{k}}$ into two parts, the first
$\alpha^{\omega}_{i+\tau_{k}}$ and the second
$\mu=\Pi^{t}_{l=\tau_{k}+i+1}(1-\alpha^{\omega}_{l})$. Since, $\mu$ is bounded
from above by 1, we have,

$\begin{array}[]{l}\eta_{i+\tau_{k}}^{k,t,j}(s,\boldsymbol{a})\leq\alpha^{\omega}_{i+\tau_{k}}(s,\boldsymbol{a})\\\
\\\
=\frac{1}{|\\#(s,\boldsymbol{a},i+\tau_{k})|}\overset{*}{\leq}(\frac{L}{i+\tau_{k}})^{\omega}\leq(\frac{L}{\tau_{k}})^{\omega}.\par\end{array}$
(27)

Here, the $*$ is from the fact that in a time interval of $\tau$, each state-
joint action pair is performed at-least $\tau/L$ times by the definition of
covering time.

Hence, we get the relation that
$\eta^{k,t,j}_{i+\tau_{k}}(s,\boldsymbol{a})\leq(L/\tau_{k})^{\omega}$.

Now, consider the expectation of $\tilde{w}_{i+\tau_{k}}(s,\boldsymbol{a})$.
By definition, we have that, $w^{j}_{\tau_{k}+i}(s,\boldsymbol{a})$ has zero
mean and is bounded by $Q^{j}_{\max}$ for any history and state-joint action
pair, hence,

$\begin{array}[]{l}\operatorname{\mathbb{E}}[\tilde{w}_{i+\tau_{k}}(s,\boldsymbol{a})]\\\
\\\
=\operatorname{\mathbb{E}}[\eta_{i+\tau_{k}}^{k,t,j}(s,\boldsymbol{a})w_{i+\tau_{k}}(s,\boldsymbol{a})]\\\
\\\
=\eta_{i+\tau_{k}}^{k,t,j}(s,\boldsymbol{a})\operatorname{\mathbb{E}}[w_{i+\tau_{k}}(s,\boldsymbol{a})]=0.\end{array}$
(28)

Next we can prove that it is bounded as well,

$\begin{array}[]{l}|\tilde{w}_{i+\tau_{k}}(s,\boldsymbol{a})|\\\ \\\
=|\eta^{k,t,j}_{i}(s,\boldsymbol{a})w_{i+\tau_{k}}(s,\boldsymbol{a})|\\\ \\\
\leq|\eta^{k,t,j}_{i}(s,\boldsymbol{a})Q^{j}_{\max}|\\\ \\\
\leq(L/\tau_{k})^{\omega}Q^{j}_{\max}\end{array}$ (29)

∎

Now, let us define
$W_{t;\tau_{k}}^{l,j}(s,\boldsymbol{a})=\sum_{i=1}^{l}\tilde{w}^{t}_{i+\tau_{k}}(s,\boldsymbol{a})$.
The objective is to prove that this is a martingale difference sequence having
bounded differences.

######  Lemma 9.

For any $t\in[\tau_{k+1},\tau_{k+2}]$ and $1\leq l\leq t$ we have that
$W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})$ is a martingale sequence that
satisfies,

$|W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})-W^{l-1,j}_{t;\tau_{k}}(s,\boldsymbol{a})|\leq(L/\tau_{k})^{\omega}Q^{j}_{\max}$
(30)

###### Proof.

We first note that the term $W^{l,j}(s,\boldsymbol{a})$ is a martingale
sequence, since

$\begin{array}[]{l}\operatorname{\mathbb{E}}[W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})-W^{l-1,j}_{t;\tau_{k}}(s,\boldsymbol{a})|F_{\tau_{k}+l-1}]\\\
\\\
=\operatorname{\mathbb{E}}[\tilde{w}^{j,t}_{l+\tau_{k}}(s,\boldsymbol{a})|F_{\tau_{k}+l-1}]=0\end{array}$
(31)

where the variable $F_{\tau_{k}+l-1}$ denotes all previous values of $W^{l}$.

Also, by Lemma 8 we can show that
$\tilde{w}^{j}_{l+\tau_{k}}(s,\boldsymbol{a})$ is bounded by
$(L/\tau_{k})^{\omega}Q^{j}_{\max}$, thus

$\begin{array}[]{l}|W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})-W^{l-1,j}_{t;\tau_{k}}(s,\boldsymbol{a})|\\\
\\\
=\tilde{w}^{j}_{l+\tau_{k}}(s,\boldsymbol{a})\leq(L/\tau_{k})^{\omega}Q^{j}_{\max}\end{array}$
(32)

∎

The next lemma bounds the term $W^{j}_{t;\tau_{k}}$.

######  Lemma 10.

Consider the low-$Q$ update given in Eq. 4, with a polynomial learning rate.
With probability at least $1-\frac{\delta}{m}$ we have that, for every state-
joint action pair
$|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\leq(1-\frac{2}{e}\gamma D_{k})$ for
any $t\in[\tau_{k+1},\tau_{k+2}]$, i.e.

$\begin{array}[]{l}Pr\Big{[}\forall s,\boldsymbol{a}\forall
t\in[\tau_{k+1},\tau_{k+2}]:|W_{t;\tau_{k}}(s,\boldsymbol{a})|\leq(1-\frac{2}{e})\beta
D_{k}\Big{]}\geq 1-\frac{\delta}{m}\end{array}$ (33)

given that

$\begin{array}[]{l}\tau_{k}=\Theta\Big{(}(\frac{L^{1+3\omega}Q^{2,j}_{\max}\ln(Q^{j}_{\max}|S|\Pi_{i}|A|_{i}m/(\delta\beta
D_{k}))}{\beta^{2}D_{k}^{2}})^{1/\omega}\Big{)}\end{array}$ (34)

###### Proof.

For each state-joint action pair comparing
$W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})$ and
$W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})$ we note that
$W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})=W_{t;\tau_{k}}^{t-\tau_{k}+1,j}(s,\boldsymbol{a})$.

Let $l=n(s,\boldsymbol{a},\tau_{k},t)$, then for any
$t\in[\tau_{k+1},\tau_{k+2}]$ we have that

$\begin{array}[]{l}l\leq\tau_{k+2}-\tau_{k}=\tau_{k+1}+L\tau^{\omega}_{k+1}-\tau_{k}\\\
\\\ =\tau_{k}+L\tau^{\omega}_{k}+L(\tau_{k}+L\tau^{\omega}_{k})-\tau_{k}\\\
\\\
=L\tau^{\omega}_{k}+L\tau_{k}+L^{2}\tau^{\omega}_{k}\leq\Theta(L^{1+\omega}\tau^{\omega}_{k}).\end{array}$
(35)

By Lemma 9 we can apply Azuma’s inequality to
$W_{t;\tau_{k}}^{t-\tau_{k}+1,j}(s,\boldsymbol{a})$ with
$c_{i}=(L/\tau_{k})^{\omega}Q^{j}_{\max}$. Therefore, we can derive that

$\begin{array}[]{l}Pr\Big{[}|W_{t;\tau_{k}}(s,\boldsymbol{a})|\geq\tilde{\epsilon}|t\in[\tau_{k+1},\tau_{k+2}]\Big{]}\\\
\\\ \leq
2e^{\frac{-\tilde{\epsilon}^{2}}{2\sum^{t}_{i=\tau_{k}+1}c^{2}_{i}}}\leq
2e^{\frac{-\tilde{\epsilon}^{2}}{2lc^{2}_{i}}}\\\ \\\ \leq
2e^{-c\frac{\tilde{\epsilon}^{2}\tau^{2\omega}_{k}}{lL^{2\omega}Q_{\max}^{2,j}}}\\\
\\\ \leq
2e^{-c\frac{\tilde{\epsilon}^{2}\tau^{\omega}_{k}}{L^{1+3\omega}Q_{\max}^{2,j}}}\end{array}$
(36)

for some constant $c>0$. We can set
$\tilde{\delta}_{k}=2e^{\frac{-c\tau_{k}^{\omega}\tilde{\epsilon}^{2}}{L^{1+3\omega}Q_{\max}^{2,j}}}$,
which holds for
$\tau^{\omega}_{k}=\Theta(\ln(1/\tilde{\delta}_{k})L^{1+3\omega}Q_{\max}^{2,j}/\tilde{\epsilon}^{2})$.

Using the union bound we get,

$\begin{array}[]{l}Pr[\forall s,\forall\boldsymbol{a},\forall
t\in[\tau_{k+1},\tau_{k+2}]:W^{j}_{t,\tau_{k}}(s,\boldsymbol{a})\leq\tilde{\epsilon}]\\\
\\\ \geq 1-\sum_{t=\tau_{k+1}}^{\tau_{k+2}}Pr[\forall
s,\forall\boldsymbol{a},W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\geq\tilde{\epsilon}]\\\
\\\ \geq 1-\sum_{t=\tau_{k+1}}^{\tau_{k+2}}Pr[\forall
s,\forall\boldsymbol{a},|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\geq\tilde{\epsilon}]\\\
\\\ \geq
1-\sum_{t=\tau_{k+1}}^{\tau_{k+2}}\tilde{\delta}_{k}|S|\Pi_{i}|A|_{i}\\\ \\\
\geq
1-(\tau_{k+2}-\tau_{k+1})\tilde{\delta}_{k}|S|\Pi_{i}|A|_{i}\par\end{array}$
(37)

We would like to set a level of probability of $1-\frac{\delta}{m}$, for each
state-joint action pair. From the above equation we get,

$\begin{array}[]{l}1-(\tau_{k+2}-\tau_{k+1})\tilde{\delta}_{k}|S|\Pi_{i}|A|_{i}=1-\delta/m\\\
\\\
\implies(\tau_{k+2}-\tau_{k+1})\tilde{\delta}_{k}|S|\Pi_{i}|A|_{i}=\delta/m.\\\
\\\
\implies\tilde{\delta}_{k}=\delta/(\tau_{k+2}-\tau_{k+1})m|S|\Pi_{i}|A|_{i}.\end{array}$
(38)

Thus taking $\tilde{\delta}_{k}=\frac{\delta}{m(\tau_{k+2}-\tau_{k+1})|S||A|}$
assures $1-\frac{\delta}{m}$ for each state-joint action pair. As a result we
have,

$\begin{array}[]{l}\tau^{\omega}_{k}=\Theta\Big{(}\frac{L^{1+3\omega}Q^{2,j}_{\max}\ln(|S|\Pi_{i}|A|_{i}m\tau^{\omega}_{k}/\delta)}{\tilde{\epsilon}^{2}}\Big{)}\\\
\\\
=\Theta\Big{(}\frac{L^{1+3\omega}Q^{2,j}_{\max}\ln(|S|\Pi_{i}|A|_{i}mQ^{j}_{\max}/(\delta\tilde{\epsilon}))}{\tilde{\epsilon}^{2}}\Big{)}\end{array}$
(39)

Setting $\tilde{\epsilon}=(1-2/e)\beta D_{k}$ gives the desired bound.

∎

Now that we have bounded for each iteration the time needed to achieve the
desired probability $1-\frac{\delta}{m}$. The next lemma provides a bound for
error in all iterations.

######  Lemma 11.

Consider the low-$Q$ update given in Eq. 4, with a polynomial learning rate.
With probability $1-\delta$, for every iteration $k\in[1,m]$ and time
$t\in[\tau_{k+1},\tau_{k+2}]$ we have
$|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\leq(1-\frac{2}{e})\beta D^{j}_{k}$,
i.e.,

$\begin{array}[]{l}Pr\Big{[}\forall k\in[1,m],\forall
t\in[\tau_{k+1},\tau_{k+2}],\forall
s,\boldsymbol{a}:|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\\\
\quad\quad\quad\quad\quad\leq(1-\frac{2}{e})\beta D^{j}_{k}\Big{]}\geq
1-\delta\end{array}$ (40)

given that

$\tau_{0}=\Theta\Big{(}\big{(}\frac{L^{1+3\omega}Q^{2,j}_{\max}\ln(Q^{j}_{\max}|S|\Pi_{i}|A|_{i}m/(\delta\beta\epsilon))}{\beta^{2}\epsilon^{2}}\big{)}^{1/\omega}\Big{)}$
(41)

###### Proof.

From Lemma 10 we have that

$\begin{array}[]{l}Pr\Big{[}\forall
t\in[\tau_{k+1},\tau_{k+2}]:|W^{j}_{t;\tau_{k}}|\geq(1-\frac{2}{e})\beta
D^{j}_{k}\Big{]}\leq\frac{\delta}{m}\end{array}$ (42)

Using the union bound we have that

$\begin{array}[]{l}Pr[\forall k\leq m,\forall
t\in[\tau_{k+1},\tau_{k+2}]|W^{j}_{t;\tau_{k}}|\geq\tilde{\epsilon}]\\\ \\\
\leq\sum_{k=1}^{m}Pr[\forall
t\in[\tau_{k+1},\tau_{k+2}]|W^{j}_{t;\tau_{k}}|\geq\tilde{\epsilon}]\leq\delta\end{array}$
(43)

where $\tilde{\epsilon}=(1-\frac{2}{e})\beta D_{k}$.

∎

The next lemma solves the recurrence
$\sum_{i=0}^{m-1}L\tau^{\omega}_{i}+\tau_{0}$ and derives the time complexity.

######  Lemma 12.

Let

$a_{k+1}=a_{k}+La^{\omega}_{k}=a_{0}+\sum_{i=0}^{k}La^{\omega}_{i}$ (44)

Then for any constant $\omega\in(0,1)$,
$a_{k}=\Omega(a_{0}^{1-\omega}/L+L^{\frac{1}{1-\omega}}((k+1)/2)^{\frac{1}{1-\omega}})$.

###### Proof.

Let us define the following series

$\begin{array}[]{l}b_{k+1}=\sum_{i=0}^{k}Lb^{\omega}_{i}+b_{0}\end{array}$
(45)

with an initial condition $b_{0}=L^{\frac{1}{1-\omega}}$.

Now we lower bound $b_{k}$ by $(L(k+1)/2)^{\frac{1}{1-\omega}}$. We use
induction to prove this hypothesis. For $k=0$,

$b_{0}=L^{\frac{1}{1-\omega}}\geq(\frac{L}{2})^{\frac{1}{1-\omega}}$ (46)

Assume that the induction hypothesis holds for $k-1$ and prove for $k$,

$\begin{array}[]{l}b_{k}=b_{k-1}+Lb^{\omega}_{k-1}\\\ \\\
=(Lk/2)^{\frac{1}{1-\omega}}+L(Lk/2)^{\frac{\omega}{1-\omega}}\\\ \\\
=L^{\frac{1}{1-\omega}}((k/2)^{\frac{1}{1-\omega}}+(k/2)^{\frac{\omega}{1-\omega}})\\\
\\\ \geq L^{\frac{1}{1-\omega}}((k+1)/2)^{\frac{1}{1-\omega}}.\end{array}$
(47)

For $a_{0}\geq L^{\frac{1}{1-\omega}}$ we can view the series as starting at
$b_{k}=a_{0}$. Since the first time step is 1, we can see that the start point
has moved $\Theta(a_{0}^{1-\omega}/L)$. Therefore, we have a total complexity
of
$\Omega(a_{0}^{1-\omega}/L+L^{\frac{1}{1-\omega}}((k+1)/2)^{\frac{1}{1-\omega}})$.

∎

######  Theorem 2.

Let us specify that with probability at least $1-\delta$, for an agent $j$,
$||Q^{j}_{T}-Q^{j}_{*}||_{\infty}\leq\epsilon$. The bound on the rate of
convergence of low-$Q$, $Q^{j}_{T}$, with a polynomial learning rate of factor
$\omega$ is given by (with $Q^{j}_{*}$ as the Nash $Q$-value of $j$)

$\begin{array}[]{l}T=\Omega\Big{(}\Big{(}\frac{L^{1+3\omega}Q^{2,j}_{\max}\ln(\frac{|S|\Pi_{i}|A_{i}|Q^{j}_{\max}}{\delta\beta\epsilon})}{\beta^{2}\epsilon^{2}}\Big{)}^{1-\omega}/L\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\Big{(}(\frac{L}{\beta}\ln\frac{Q^{j}_{\max}}{\epsilon}+1)/2\Big{)}^{\frac{1}{1-\omega}}\Big{)}.\end{array}$

###### Proof.

The proof of Theorem 2 follows from Lemmas 7, 11, 4, and 12.

Specifically, from the relation in Lemma 12 substitute the value of $a_{0}$
from the Lemma 11 (value of $\tau_{0}$), and value of $k$ from Lemma 4 (lower
bound for $m$). From the Lemma 7 and Lemma 11, we see that the condition
required in Lemma 5 is satisfied to provide a lower bound.

∎

##  Appendix D Proof of Theorem 3

In this section, we aim to show that the size of the $k$th iteration is
$L(1+\psi)\tau_{k}$ for some positive constant $\psi\leq 0.712$. The covering
time property guarantees that in $(1+\psi)L\tau_{k}$ steps, each pair of
state-joint actions are performed at least $(1+\psi)\tau_{k}$ times. The
sequence of times in this case is $\tau_{k+1}=\tau_{k}+(1+\psi)L\tau_{k}$. As
in the last section, we will first bound $Y^{j}_{t;\tau_{k}}$ and then bound
$W^{j}_{t;\tau_{k}}$. As in Appendix B, we will use $Q$ to denote the low-$Q$
values across this section as well. The proof of this theorem follows the
Theorem 5 in Dar and Mansour Even-Dar and Mansour (2003). While the work of
Dar and Mansour was restricted to single-agent MDPs, our result extends the
analysis of Dar and Mansour to the general-sum stochastic game setting.

######  Lemma 13.

Consider the low-$Q$ update given in Eq. 4, with a linear learning rate.
Assume that for $t\geq\tau_{k}$ we have that
$Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\leq D^{j}_{k}$. Then for any
$t\geq\tau_{k}+(1+\psi)L\tau_{k}=\tau_{k+1}$ we have that
$Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\leq(\gamma+\frac{2}{2+\psi}\beta)D^{j}_{k}$.

###### Proof.

For each state-joint action pair, we are assured that
$n(s,\boldsymbol{a},\tau_{k},\tau_{k+1})\geq(1+\psi)\tau_{k}$, since in an
interval of $(1+\psi)L\tau_{k}$ steps, each state-joint action pair is visited
at least $(1+\psi)\tau_{k}$ times by the definition of covering time.

Let $Y^{j}_{\tau_{k},\tau_{k}}(s,\boldsymbol{a})=\gamma
D^{j}_{k}+\rho^{j}_{\tau_{k}}$, where
$\rho^{j}_{\tau_{k}}=(1-\gamma)D^{j}_{k}$. We now have,

$\begin{array}[]{l}\rho^{j}_{t}=(1-\gamma)\Pi_{l=1}^{t-\tau_{k}}(1-\alpha_{l+\tau_{k}})\\\
\\\ =2\beta D^{j}_{k}\Pi_{l=1}^{t-\tau_{k}}(1-\alpha_{l+\tau_{k}})\\\ \\\
=2\beta
D^{j}_{k}\Pi_{l=1}^{t-\tau_{k}}(1-\frac{1}{|n(s,\boldsymbol{a},\tau_{k+1},l)|}),\end{array}$
(48)

where the last identity follows from the fact that
$\alpha_{t}=\frac{1}{n(s,\boldsymbol{a},0,t)}$. Since the $\tau_{k}$’s are
monotonically decreasing, using $t=\tau_{k}+(1+\psi)L\tau_{k}$, we get (using
$\psi<0.712$),

$\begin{array}[]{l}\rho_{t}\leq
2D^{j}_{k}\beta(1-\frac{1}{(1+\psi)\tau_{k}})^{t-\tau_{k}}\\\ \\\ \leq
2D^{j}_{k}\beta(1-\frac{1}{(1+\psi)\tau_{k}})^{1+\psi L\tau_{k}}\\\ \\\ \leq
2D^{j}_{k}\beta(1-\frac{1}{(1+\psi)\tau_{k}})^{1+\psi\tau_{k}}\\\ \\\
\leq\frac{2D^{j}_{k}\beta}{e}\\\ \\\
\leq\frac{2D^{j}_{k}\beta}{2+\psi}\end{array}$ (49)

Hence,
$Y^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\leq(\gamma+\frac{2}{2+\psi}\beta)D^{j}_{k}$.

∎

The following lemma enables the use of Azuma’s inequality.

######  Lemma 14.

For any $t\geq\tau_{k}$ and $1\leq l\leq t$ we have that
$W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})$ is a martingale sequence, which
satisfies,

$|W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})-W_{t;\tau_{k}}^{l-1,j}(s,\boldsymbol{a})|\leq\frac{Q^{j}_{\max}}{n(s,\boldsymbol{a},0,t)}$
(50)

###### Proof.

$W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})$ is a martingale difference sequence
since,

$\begin{array}[]{l}\operatorname{\mathbb{E}}[W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})-W^{l-1,j}_{t;\tau_{k}}(s,\boldsymbol{a})|F_{\tau_{k}+l-1}]\\\
\\\
=\operatorname{\mathbb{E}}[\eta^{k,t,j}_{\tau_{k}+l}(s,\boldsymbol{a})w^{j}_{\tau_{k}+l}(s,\boldsymbol{a})|F_{\tau_{k}+l-1}]\\\
\\\
=\eta^{k,t,j}_{\tau_{k}+l}(s,\boldsymbol{a})\operatorname{\mathbb{E}}[w^{j}_{\tau_{k}+l}(s,\boldsymbol{a})|F_{\tau_{k}+l-1}]=0\par\par\end{array}$
(51)

For linear learning rate we have that
$\eta^{k,t,j}_{\tau_{k}+l}(s,\boldsymbol{a})\leq\alpha_{l+\tau_{k}}=1/n(s,\boldsymbol{a},0,t)$,
thus

$\begin{array}[]{l}|W^{l,j}_{t;\tau_{k}}(s,\boldsymbol{a})-W^{l-1,j}_{t;\tau_{k}}(s,\boldsymbol{a})|\\\
\\\
=\eta^{k,t,j}_{\tau_{k}+l}(s,\boldsymbol{a})|w^{j}_{\tau_{k}+l}(s,\boldsymbol{a})|\\\
\\\ \leq\frac{Q^{j}_{\max}}{n(s,\boldsymbol{a},0,t)}.\end{array}$ (52)

∎

The following lemma provides a bound for the stochastic term
$W^{j}_{t;\tau_{k}}$.

######  Lemma 15.

Consider the low-$Q$ update given in Eq. 4, with a linear learning rate. With
probability at least $1-\frac{\delta}{m}$ we have that for every state-joint
action pair
$|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\leq\frac{\psi}{2+\psi}\beta
D^{j}_{k}$, for any $t>\tau_{k+1}$ and any positive constant $\psi\leq 0.712$,
i.e.,

$\begin{array}[]{l}Pr\Big{[}\forall
t\in[\tau_{k+1},\tau_{k+2}]:W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})\leq\frac{\psi}{2+\psi}\beta
D^{j}_{k}\Big{]}\geq 1-\frac{\delta}{m}\end{array}$ (53)

given that
$\tau_{k}\geq\Theta(\frac{Q^{2,j}_{\max}\ln(Q^{j}_{\max}|S|\Pi_{i}|A|_{i}m)/(\psi\delta\beta
D_{k})}{\psi^{2}\beta^{2}D^{2}_{k}})$.

###### Proof.

By Lemma 14 we can apply Azuma’s inequality on the term,
$W_{t;\tau_{k}}^{t-\tau_{k}+1,j}$ (note that
$W_{t;\tau_{k}}^{t-\tau_{k}+1,j}=W_{t;\tau_{k}}$), and with the expression
$c_{i}=\Theta\Big{(}\frac{Q^{j}_{\max}}{n(s,a,0,t)}\Big{)}$ for any
$t\geq\tau_{k+1}$. Therefore, we derive that,

$\begin{array}[]{l}Pr[|W^{j}_{t;\tau_{k}}\geq\tilde{\epsilon}|]\leq
2e^{\frac{-2e\tilde{\epsilon}^{2}}{\sum_{i=\tau_{k}}^{t}c^{2}_{i}}}\leq
2e^{-c\frac{\tilde{\epsilon}^{2}n(s,\boldsymbol{a},\tau_{k},t)}{Q^{2,j}_{\max}}}\end{array}$
(54)

for some positive constant c.

Let us define,

$\begin{array}[]{l}\zeta_{t}(s,\boldsymbol{a})={1,\textrm{ if
}\alpha_{t}(s,\boldsymbol{a})\neq 0}\\\
\zeta_{t}(s,\boldsymbol{a})={0,\textrm{ otherwise }}.\end{array}$ (55)

Using the union bound and the property that, in an interval of length
$(1+\psi)L\tau_{k}$, each state-joint action pair is visited at least
$(1+\psi)\tau_{k}$ times, we get

$\begin{array}[]{l}Pr\Big{[}\forall
t\in[\tau_{k+1},\tau_{k+2}]:|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\geq\tilde{\epsilon}\Big{]}\\\
\\\ \leq Pr[\forall
t\geq((1+\psi)L+1)\tau_{k}:|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\geq\tilde{\epsilon}]\\\
\\\
\leq\sum^{\infty}_{t=((1+\psi)L+1)\tau_{k}}Pr\Big{[}|W^{j}_{t;\tau_{k}}(s,\boldsymbol{a})|\geq\tilde{\epsilon}\Big{]}\\\
\\\
\leq\sum^{\infty}_{t=((1+\psi)L+1)\tau_{k}}\zeta_{t}(s,\boldsymbol{a})2e^{-c\frac{\tilde{\epsilon}^{2}n(s,\boldsymbol{a},0,t)}{Q^{2,j}_{\max}}}\\\
\\\ \leq
2e^{-c\frac{\tilde{\epsilon}^{2}((1+\psi)\tau_{k})}{Q^{2,j}_{\max}}}\sum_{t=0}^{\infty}e^{-\frac{t\tilde{\epsilon}^{2}}{Q^{2,j}_{\max}}}\\\
\\\
=\frac{2e^{-c\frac{\tilde{\epsilon}^{2}((1+\psi)\tau_{k})}{Q^{2,j}_{\max}}}}{1-e^{\frac{-\tilde{\epsilon}^{2}}{Q^{2,j}_{\max}}}}\\\
\\\
=\Theta(\frac{Q^{2,j}_{\max}e^{\frac{-c^{\prime}\tau_{k}\tilde{\epsilon}^{2}}{Q^{2,j}_{\max}}}}{\tilde{\epsilon}^{2}})\par\end{array}$
(56)

for some positive constant $c^{\prime}$. Setting
$\frac{\delta}{m|S|\Pi_{i}|A|_{i}}=\Theta\Big{(}\frac{e^{-}{\frac{c^{\prime}\tau_{k}\tilde{\epsilon}^{2}}{Q^{2,j}_{\max}}}Q^{2,j}_{\max}}{\tilde{\epsilon}^{2}}\Big{)}$,
which holds for
$\tau_{k}=\Theta(\frac{Q^{2,j}_{\max}\ln(Q^{j}_{\max}|S|\Pi_{i}|A|_{i}m/(\delta\tilde{\epsilon}))}{\tilde{\epsilon}^{2}})$,
and the expression, $\tilde{\epsilon}=\frac{\psi}{2+\psi}\beta D^{j}_{k}$
assures us that for every $t\geq\tau_{k+1}$ (and as a result for any
$t\in[\tau_{k+1},\tau_{k+2}]$), with probability at least $1-\frac{\delta}{m}$
the statement holds at every state-joint action pair.

∎

We have bounded for each iteration the time needed to achieve the desired
probability of $1-\frac{\delta}{m}$. The following lemma provides a bound for
the error in all the iterations.

######  Lemma 16.

Consider the low-$Q$ update given in Eq. 4, with a linear learning rate. With
probability $1-\delta$, for every iteration $k\in[1,m]$, time
$t\in[\tau_{k+1},\tau_{k+2}]$, and any positive constant $\psi\leq 0.712$, we
have $|W^{j}_{t;\tau_{k}}|\leq\frac{\psi\beta D^{j}_{k}}{2+\psi}$, i.e.,

$\begin{array}[]{l}Pr\Big{[}\forall k\in[1,m],\forall
t\in[\tau_{k+1},\tau_{k+2}]:|W^{j}_{t;\tau_{k}}|\leq\frac{\psi\beta
D^{j}_{k}}{2+\psi}\Big{]}\geq 1-\delta\end{array}$ (57)

given that
$\tau_{0}=\Theta\Big{(}\frac{Q^{2,j}_{\max}\ln(Q^{j}_{\max}|S||A|m/(\delta\beta\epsilon\psi))}{\psi^{2}\beta^{2}\epsilon^{2}}\Big{)}$

###### Proof.

From Lemma 15, we know that

$\begin{array}[]{l}Pr\Big{[}\forall
t\in[\tau_{k+1},\tau_{k+2}]:|W^{j}_{t;\tau_{k}}|\geq\frac{\psi\beta
D^{j}_{k}}{2+\psi}\Big{]}\leq\frac{\delta}{m}.\end{array}$ (58)

Using the union bound, we have that,

$\begin{array}[]{l}Pr\Big{[}\forall k\leq m,\forall
t\in[\tau_{k+1},\tau_{k+2}]:|W^{j}_{t;\tau_{k}}|\geq\frac{\psi\beta
D^{j}_{k}}{2+\psi}\Big{]}\\\ \\\ \leq\sum_{k=1}^{m}Pr\Big{[}\forall
t\in[\tau_{k+1},\tau_{k+2}]|W^{j}_{t;\tau_{k}}|\geq\frac{\psi\beta
D^{j}_{k}}{2+\psi}\Big{]}\\\ \\\ \leq\delta.\end{array}$ (59)

∎

######  Theorem 3.

Let us specify that with probability at least $1-\delta$, we have for an agent
$j$, $||Q^{j}_{T}-Q^{j}_{*}||_{\infty}\leq\epsilon$. The bound on the rate of
convergence of low-$Q$, $Q^{j}_{T}$, with a linear learning rate is given by

$T=\Omega\Big{(}(L+\psi
L+1)^{\frac{1}{\beta}\ln\frac{Q^{j}_{\max}}{\epsilon}}\frac{Q^{2,j}_{\max}\ln(\frac{|S|\Pi_{i}|A|_{i}Q^{j}_{\max}}{\delta\beta\epsilon\psi})}{\beta^{2}\epsilon^{2}\psi^{2}}\Big{)},$

where $\psi$ is a small arbitrary positive constant satisfying $\psi\leq
0.712$

###### Proof.

The Theorem 3 follows from Lemmas 16, 13, 4, and the fact that
$a_{k+1}=a_{k}+(1+\psi)La_{k}=a_{0}((1+\psi)L+1)^{k}$.

Specifically, substitute the value of $k$ from Lemma 4 (lower bound for $m$),
value of $a_{0}$ from Lemma 16 (value of $\tau_{0}$), and see that Lemma 13
and Lemma 16 satisfy the condition for the lower bound in Lemma 5.

∎

##  Appendix E Frequency Of Listening To Advisors

This section plots the frequency of listening to each advisor in some of our
experiments. We would like to show that the MA-TLQL listens more to the good
advisor and avoids the bad advisor more than other related baselines. For
these experiments, we consider the TLQL (Li et al., 2019) and ADMIRAL-DM (Wang
and Taylor, 2017) algorithms for comparison. Since the CHAT implementation
uses the same method to choose advisors as ADMIRAL-DM (weighted random policy
approach), we will omit CHAT for these results (performance is similar to
ADMIRAL-DM). DQfD uses pretraining and does not choose advisors in an online
fashion; hence we omit DQfD for these experiments as well.

(a) Good Advisor (Advisor 1)

(b) Bad Advisor (Advisor 4)

Figure 11. Frequency of listening to advisors in the two-agent Pommerman
experiment with four sufficient advisors of different quality (Experiment 1)

We consider our first experiment in Section 6 (Experiment 1), where we had a
set of four sufficient advisors of different quality. The first advisor
(Advisor 1) had a better quality than the others, and the agents must listen
more to this advisor. On the other hand, Advisor 4 only suggested random
actions and the agents are expected to avoid listening to this advisor. In
Figure 11(a), we plot a curve that corresponds to the percentage of time steps
an algorithm listened to Advisor 1 out of all the time steps the algorithm had
an oppourtunity to listen to one of the available advisors. From the plots, we
see that MA-TLQL listens more (compared to the other baselines) to this
advisor (Advisor 1) from the beginning until the end of training. Since the
MA-TLQL uses an ensemble technique to choose an advisor, this gives it a
distinct advantage in the early stages of training. Further, since MA-TLQL
performs an explicit evaluation of the advisors independent of the RL policy,
it manages to listen more to the correct advisor as compared to other
baselines. MA-TLAC also listens more to the good advisor as compared to the
other baselines (TLQL, ADMIRAL-DM). Since TLQL couples the advisor evaluation
with the RL policy, it listens a lot less to the good advisor as compared to
MA-TLQL. Also, TLQL considers the RL policy as part of the high-level table,
which makes it less reliant on advisors. This could be a problem when good
advisors are available. In Figure 11(b), we plot the percentage of each
algorithm listening to the bad advisor (Advisor 4). We see that MA-TLQL has
the least dependence on this advisor as compared to all other algorithms. This
reinforces our observation that MA-TLQL is most likely to choose to listen to
the correct advisors in this multi-agent setting.

(a) Good Advisor (Advisor 1)

(b) Bad Advisor (Advisor 4)

Figure 12. Frequency of listening to advisors in the two-agent Pommerman
experiment with four insufficient advisors of different quality (Experiment 3)

We plot the percentage of listening to Advisor 1 and Advisor 4 in Experiment 3
from Section 6 that had an insufficient set of four advisors of decreasing
quality. The results in Figure 12(a) and (b) show that MA-TLQL listens more to
the good advisor and less to the bad advisor, same as our observations for
Experiment 1.

(a) Good Advisor (Advisor 1)

(b) Bad Advisor (Advisor 4)

Figure 13. Frequency of listening to advisors in the team Pommerman experiment
with four sufficient advisors of different quality (Experiment 5)

Similarly, we plot the percentages of listening to the good and bad advisor in
the Pommerman team environment (mixed setting) used in Experiment 5 in Figure
13(a) and (b). Here we plot the results for one of the two pommerman agents
playing in the same team (the other agent’s results are similar). Once again,
we note that MA-TLQL listens more to the correct advisor than the other
algorithms and better avoids the bad advisors compared to the other
algorithms.

##  Appendix F Nature Of Algorithms Considered

Algorithm |  Nature of Algorithm |  Number of Advisors |  Type of Demonstrations
---|---|---|---
DQN Mnih et al. (2015) |  Independent |  Does not learn from advising |  Not applicable
DQfD Hester et al. (2018) |  Independent |  One |  Offline
CHAT Wang and Taylor (2017) |  Independent |  One |  Online
ADMIRAL-DM Subramanian et al. (2022) |  Multi-agent |  One |  Online
TLQL Li et al. (2019) |  Independent |  More than one |  Online
MA-TLQL (ours) |  Multi-agent |  More than one |  Online
MA-TLAC (ours) |  Multi-agent |  More than one |  Online
Table 1. Description of all algorithms considered in this paper

In Table 1, we tabulate all the algorithms considered in this paper. The
differences between the algorithms stem from the nature of the algorithm
(independent or multi-agent), ability to naturally support learning from
conflict demonstrations (i.e., more than one advisor), and type of
demonstrations that they naturally support (offline vs. online). Offline
demonstrations are demonstrations that are collected (in a memory buffer) from
an advisor before the “training phase” where the algorithm is trained using
interactions with the environment. These demonstrations are typically used to
train the algorithm in a “pre-training” phase before regular training, as done
in several prior works Kim et al. (2013); Hester et al. (2018); Gao et al.
(2018). Alternatively, online demonstrations are obtained in real-time during
the training phase (and not pre-collected). Here, an agent can actively obtain
action recommendations directly from an advisor for the current game context.

In general, in all the experiments considered in this paper, we found that
algorithms that consider actions of other agents to provide best-responses
(non-independent) performed better than independent algorithms which consider
all other agents to be part of the environment. One reason for this behaviour
could be the fact that independent algorithms break the Markovian assumptions
in reinforcement learning methods Tan (1993). Additionally, we found that
algorithms that learn from online advising perform better as compared to
algorithms that learn from offline advising. If algorithms learn from online
advising, then these algorithms can exploit the knowledge of advisors in
response to dynamically changing other agent(s), in real-time. Since other
agent(s)/opponent(s) are not typically available before training in multi-
agent environments, offline demonstrations are not very successful in multi-
agent training, as opposed to single-agent training where they were quite
successful Hester et al. (2018). In this paper, we considered environments
where the advising come from multiple sources of independent knowledge. In
many states, the different advisors provide conflicting recommendations.
Hence, algorithms that can effectively resolve conflicting information from
the different advisors were successful as compared to other algorithms that
are not capable of naturally supporting learning under multiple conflicting
advisors. As seen from Table 1, the only two algorithms that have all the
three desirable properties (i.e, support multi-agent update, learn from
conflicting advisors, support offline demonstrations) are MA-TLQL and MA-TLAC
which gave the best performance in most of the seven experiments considered in
Section 6.

In our paper, we do not consider HMAT Kim et al. (2020) and LeCTR Omidshafiei
et al. (2019) as baselines, though these can also be classified as action
advising methods. We do not consider these algorithms as appropriate
benchmarks due to two important reasons. First, they are both restricted to
two-agent cooperative settings while we are interested in more general domains
including those with more than two agents and both competitive and mixed-
motive environments. Second, we are interested in independent learning from a
set of external advisors, while both HMAT and LeCTR focus on peer-to-peer
learning (partly due to their focus on teaching teams, as opposed to our work
which is on more general multi-agent learning problems).

##  Appendix G MA-TLQL With Learning Advisors

(a) Pursuit Environment

(b) Predator-Prey Environment

Figure 14. Performances of MA-TLQL and MA-TLAC under changing (learning)
advisors and fixed advisors. Here (a) corresponds to the setting in Experiment
6 and (b) corresponds to the setting in Experiment 7, described in Section 6.

In all the experiments in this paper we considered advisors that are fixed and
non-changing, which we specified in Section 4. If the advisors are fixed,
their $Q$-values can be determined using the high-$Q$ updates in MA-TLQL. The
fixed nature of advisors allows us to provide theoretical guarantees of
convergence of the high-$Q$ values (under the assumption of infinite updates
in the limit) using similar arguments as in Theorem 1. However, experimentally
we can still consider other types of advisors which are actively learning
during the training stage and hence are updating the policies actively (though
using such advisors do not have any theoretical guarantees of convergence). In
this section, we will revisit Experiment 6 and Experiment 7 from Section 6 and
study the performances of MA-TLQL and MA-TLAC under learning advisors. For
statistical significance we use the unpaired 2-sided t-test and report
$p$-values, as in the earlier experiments.

First we consider Experiment 6, where we used the Pursuit cooperative
environment along with four pre-trained networks of DQN as the advisor. Now,
we will consider the same set of four advisors and label them as “fixed
advisors”. Additionally, we will let the same four pre-trained networks of DQN
continue training while it is being actively used for action advising. We
label this set of four advisors as “changing advisors”. In Figure 14(a) we
plot the performances (plot of episodic rewards) of MA-TLQL and MA-TLAC along
with the fixed as well as the changing advisor set. While using the changing
advisor set, we see that MA-TLQL and MA-TLAC outperform their counterparts
using the fixed advisors ($p<0.04$). As the advisors are actively learning and
changing their strategies during the training stage, they are able to provide
better action recommendations to MA-TLQL and MA-TLAC at the different parts of
the environment. This is reflected in their superior performances.

Similarly, we revisit Experiment 7 with the Predator-Prey environment and
consider two different sets of advisors. In Experiment 7, we used four pre-
trained DQN networks as advisors. We will reuse the same set of four advisors
and label them as the “fixed advisors”. A continuously training counterpart is
labelled as the “changing advisors”. We plot the performances of MA-TLAC in
the Predator-Prey experiment in Figure 14(b), and once again we notice that
MA-TLAC using the changing advisor set outperforms MA-TLAC using the fixed
advisor set ($p<0.03$).

Hence, experimentally we see that MA-TLQL and MA-TLAC can still be used with
changing advisors which provide good empirical performances. However, the non-
stationary nature of these advisors makes it impossible to provide theoretical
guarantees of convergence. This is similar to using independent algorithms in
multi-agent environments, which do not have any theoretical guarantees of
convergence to either a local or global optimum, yet empirically, several
prior works have noted that these algorithms perform well in various multi-
agent environments Hernandez-Leal et al. (2019); Matignon et al. (2012).

##  Appendix H MA-TLQL With Opponent Modelling

(a) One vs. One Pommerman: Insufficient different quality advisors

(b) One vs. One Pommerman: Insufficient similar quality advisors

Figure 15. Performances of MA-TLQL with and without opponent modelling using
four insufficient advisors. Here (a) corresponds to the setting in Experiment
3 and (b) corresponds to the setting in Experiment 4, described in Section 6.

In all the experiments in this paper, the MA-TLQL used a multi-agent update
where it simply tracked opponent actions (by considering the previous action)
and did not perform any active opponent modelling. The core focus of this
paper is learning from advisors, and we chose not to perform any particular
opponent modelling technique to keep the algorithm simple. However, in this
section, we will implement MA-TLQL along with an opponent modelling technique
that uses a separate neural network (2 Relu layers of 50 neurons and an output
layer) to predict the action of the opponent. The network uses the state and
previous action of the opponent as the input and predicts the action of the
opponent. This predicted action of the opponent is used by the agent to
calculate best responses. Finally, the actual observed action of the opponent
is used to define a cross-entropy loss function that is used to train the
network. We revisit Experiment 3 and Experiment 4 in Section 6 where we used
four insufficient advisors of different and similar quality. Now, we will use
the same experimental procedure (with the same set of advisors) and consider
the performances of MA-TLQL with and without active opponent modelling. For
statistical significance we use the unpaired 2-sided t-test and report
$p$-values.

We plot the performances in Figure 15. From both Figure 15(a) and (b) we see
that MA-TLQL with opponent modelling performs better than the MA-TLQL
algorithm that does not perform any active opponent modelling. In the Figure
15(a) we see that opponent modelling only provides a small increase in
performance ($p<0.2$). One reason for this is the fact that MA-TLQL without
opponent modelling is already showing a high performance in this experiment by
learning efficiently from the advisors. Alternatively, Figure 15(b) shows a
considerable increase in performance while MA-TLQL is using opponent modelling
($p<0.04$). Here, the performance of MA-TLQL without opponent modelling is not
as good is the performance in Figure 15(a) and opponent modelling shows a
marked improvement in performance.

##  Appendix I MA-TLQL With Different Numbers Of Advisors

Figure 16. MA-TLQL with different numbers of advisors in the Pursuit
environment (setting used in Experiment 6, described in Section 6)

In this section we train MA-TLQL with different number of advisors in the
Pursuit environment considered in Experiment 6 of Section 6. Recall that in
Experiment 6 we considered four pre-trained networks of DQN as the advisor