# Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning

Anuj Mahajan  Mikayel Samvelyan  Lei Mao  Viktor Makoviychuk  Animesh Garg
Jean Kossaifi  Shimon Whiteson  Yuke Zhu  Animashree Anandkumar

###### Abstract

Reinforcement Learning in large action spaces is a challenging problem.
Cooperative multi-agent reinforcement learning (MARL) exacerbates matters by
imposing various constraints on communication and observability. In this work,
we consider the fundamental hurdle affecting both value-based and policy-
gradient approaches: an exponential blowup of the action space with the number
of agents. For value-based methods, it poses challenges in accurately
representing the optimal value function. For policy gradient methods, it makes
training the critic difficult and exacerbates the problem of the _lagging_
critic. We show that from a learning theory perspective, both problems can be
addressed by accurately representing the associated action-value function with
a low-complexity hypothesis class. This requires accurately modelling the
agent interactions in a sample efficient way. To this end, we propose a novel
tensorised formulation of the Bellman equation. This gives rise to our method
Tesseract, which views the $Q$-function as a tensor whose modes correspond to
the action spaces of different agents. Algorithms derived from Tesseract
decompose the $Q$-tensor across agents and utilise low-rank tensor
approximations to model agent interactions relevant to the task. We provide
PAC analysis for Tesseract-based algorithms and highlight their relevance to
the class of rich observation MDPs. Empirical results in different domains
confirm Tesseract’s gains in sample efficiency predicted by the theory.

Machine Learning, ICML

##  1 Introduction

Many real-world problems, such as swarm robotics and autonomous vehicles, can
be formulated as multi-agent reinforcement learning (MARL) (Buşoniu et al.,
2010) problems. MARL introduces several new challenges that do not arise in
single-agent reinforcement learning (RL), including exponential growth of the
action space in the number of agents. This affects multiple aspects of
learning, such as credit assignment (Foerster et al., 2018), gradient variance
(Lowe et al., 2017) and exploration (Mahajan et al., 2019). In addition, while
the agents can typically be trained in a centralised manner, practical
constraints on observability and communication after deployment imply that
decision making must be decentralised, yielding the extensively studied
setting of centralised training with decentralised execution (CTDE).

Recent work in CTDE-MARL can be broadly classified into value-based methods
and actor-critic methods. Value-based methods (Sunehag et al., 2017; Rashid et
al., 2018; Son et al., 2019; Wang et al., 2020a; Yao et al., 2019) typically
enforce decentralisability by modelling the joint action $Q$-value such that
the argmax over the joint action space can be tractably computed by local
maximisation of per-agent utilities. However, constraining the representation
of the $Q$-function can interfere with exploration, yielding provably
suboptimal solutions (Mahajan et al., 2019). Actor-critic methods (Lowe et
al., 2017; Foerster et al., 2018; Wei et al., 2018) typically use a
centralised critic to estimate the gradient for a set of decentralised
policies. In principle, actor-critic methods can satisfy CTDE without
incurring suboptimality, but in practice their performance is limited by the
accuracy of the critic, which is hard to learn given exponentially growing
action spaces. This can exacerbate the problem of the lagging critic (Konda &
Tsitsiklis, 2002). Moreover, unlike the single-agent setting, this problem
cannot be fixed by increasing the critic’s learning rate and number of
training iterations. Similar to these approaches, an exponential blowup in the
action space also makes it difficult to choose the appropriate class of models
which strike the correct balance between expressibility and learnability for
the given task.

In this work, we present new theoretical results that show how the
aforementioned approaches can be improved such that they accurately represent
the joint action-value function whilst keeping the complexity of the
underlying hypothesis class low. This translates to accurate, sample efficient
modelling of long-term agent interactions.

In particular, we propose Tesseract (derived from "Tensorised Actors"), a new
framework that leverages tensors for MARL. Tensors are high dimensional
analogues of matrices that offer rich insights into representing and
transforming data. The main idea of Tesseract is to view the output of a joint
$Q$-function as a tensor whose modes correspond to the actions of the
different agents. We thus formulate the Tensorised Bellman equation, which
offers a novel perspective on the underlying structure of a multi-agent
problem. In addition, it enables the derivation of algorithms that decompose
the $Q$-tensor across agents and utilise low rank approximations to model
relevant agent interactions.

Many real-world tasks (e.g., robot navigation) involve high dimensional
observations but can be completely described by a low dimensional feature
vector (e.g., a 2D map suffices for navigation). For value-based Tesseract
methods, maintaining a tensor approximation with rank matching the intrinsic
task dimensionality111We define intrinsic task dimensionality (ITD) as the
minimum number of dimensions required to describe an environment helps learn a
compact approximation of the true $Q$-function (alternatively MDP-dynamics for
model based methods). In this way, we can avoid the suboptimality of the
learnt policy while remaining sample efficient. Similarly, for actor-critic
methods, Tesseract reduces the critic’s learning complexity while retaining
its accuracy, thereby mitigating the lagging critic problem. Thus, Tesseract
offers a natural spectrum for trading off accuracy with computational/sample
complexity.

To gain insight into how tensor decomposition helps improve sample efficiency
for MARL, we provide theoretical results for model-based Tesseract algorithms
and show that the underlying joint transition and reward functions can be
efficiently recovered under a PAC framework (in samples polynomial in accuracy
and confidence parameters). We also introduce a tensor-based framework for
CTDE-MARL that opens new possibilities for developing efficient classes of
algorithms. Finally, we explore the relevance of our framework to rich
observation MDPs.

Our main contributions are:

  1. 1.

A novel tensorised form of the Bellman equation;

  2. 2.

Tesseract, a method to factorise the action-value function based on tensor
decomposition, which can be used for any factored action space;

  3. 3.

PAC analysis and error bounds for model based Tesseract that show an
exponential gain in sample efficiency of $O(|U|^{n/2})$; and

  4. 4.

Empirical results illustrating the advantage of Tesseract over other methods
and detailed techniques for making tensor decomposition work for deep MARL.

##  2 Background

##### Cooperative MARL settings

In the most general setting, a fully cooperative multi-agent task can be
modelled as a multi-agent partially observable MDP (M-POMDP) (Messias et al.,
2011). An M-POMDP is formally defined as a tuple $G=\left\langle
S,U,P,r,Z,O,n,\gamma\right\rangle$. $S$ is the state space of the environment.
At each time step $t$, every agent $i\in\mathcal{A}\equiv\\{1,...,n\\}$
chooses an action $u^{i}\in U$ which forms the joint action
$\mathbf{u}\in\mathbf{U}\equiv U^{n}$.
$P(s^{\prime}|s,\mathbf{u}):S\times\mathbf{U}\times S\rightarrow[0,1]$ is the
state transition function. $r(s,\mathbf{u}):S\times\mathbf{U}\rightarrow[0,1]$
is the reward function shared by all agents and $\gamma\in[0,1)$ is the
discount factor.

Figure 1: Different settings in MARL

An M-POMDP is partially observable (Kaelbling et al., 1998): each agent does
not have access to the full state and instead samples observations $z\in Z$
according to observation distribution $O(s):S\rightarrow\mathcal{P}(Z)$. The
action-observation history for an agent $i$ is $\tau^{i}\in T\equiv(Z\times
U)^{*}$. We use $u^{-i}$ to denote the action of all the agents other than $i$
and similarly for the policies $\pi^{-i}$. Settings where the agents cannot
exchange their action-observation histories with others and must condition
their policy solely on local trajectories, $\pi^{i}(u^{i}|\tau^{i}):T\times
U\rightarrow[0,1]$, are referred to as a decentralised partially observable
MDP (Dec-POMDP) (Oliehoek & Amato, 2016). When the observations have
additional structure, namely the joint observation space is partitioned w.r.t.
$S$, i.e., $\forall s_{1},s_{2}\in S\land{z}\in Z,P({z}|s_{1})>0\land
s_{1}\neq s_{2}\implies P({z}|s_{2})=0$, we classify the problem as a multi-
agent richly observed MDP (M-ROMDP) (Azizzadenesheli et al., 2016). For both
M-POMDP and M-ROMDP, we assume $|Z|>>|S|$, thus for this work, we assume a
setting with no information loss due to observation but instead, redundancy
across different observation dimensions. Such is the case for many real world
tasks like 2D robot navigation using observation data from different sensors.
Finally, when the observation function is a bijective map $O:S\to Z$, we refer
to the scenario as a multi-agent MDP (MMDP) (Boutilier, 1996), which can
simply be denoted by the tuple : $\left\langle S,U,P,r,n,\gamma\right\rangle$.
Fig. 1 gives the relation between different scenarios for the cooperative
setting. For ease of exposition, we present our theoretical results for the
MMDP case, though they can easily be extended to other cases by incurring
additional sample complexity.

The joint action-value function given a policy $\pi$ is defined as:
$Q^{\pi}(s_{t},\mathbf{u}_{t})=\mathbb{E}_{s_{t+1:\infty},\mathbf{u}_{t+1:\infty}}\left[\sum^{\infty}_{k=0}\gamma^{k}r_{t+k}|s_{t},\mathbf{u}_{t}\right]$.
The goal is to find the optimal policy $\pi^{*}$ corresponding to the optimal
action value function $Q^{*}$. For the special learning scenario called
Centralised Training with Decentralised Execution (CTDE), the learning
algorithm has access to the action-observation histories of all agents and the
full state during training phase. However, each agent can only condition on
its own local action-observation history $\tau^{i}$ during the decentralised
execution phase.

##### Reinforcement Learning Methods

Both value-based and actor-critic methods for reinforcement learning (RL) rely
on an estimator for the action-value function $Q^{\pi}$ given a target policy
$\pi$. $Q^{\pi}$ satisfies the (scalar)-Bellman expectation equation:
$Q^{\pi}(s,\mathbf{u})=r(s,\mathbf{u})+\gamma\mathbb{E}_{s^{\prime},\mathbf{u}^{\prime}}[Q^{\pi}(s^{\prime},\mathbf{u}^{\prime})],$
which can equivalently be written in vectorised form as:

$\displaystyle Q^{\pi}=R+\gamma P^{\pi}Q^{\pi},$ (1)

where $R$ is the mean reward vector of size $S$, $P^{\pi}$ is the transition
matrix. The operation on RHS $\mathcal{T}^{\pi}(\cdot)\triangleq R+\gamma
P^{\pi}(\cdot)$ is the Bellman expectation operator for the policy $\pi$. In
Section 3 we generalise Eq. 1 to a novel tensor form suitable for high-
dimensional and multi-agent settings. For large state-action spaces function
approximation is used to estimate $Q^{\pi}$. A parametrised approximation
$Q^{\phi}$ is usually trained using the bootstrapped target objective derived
using the samples from $\pi$ by minimising the mean squared temporal
difference error: $\mathbb{E}_{\pi}[(r(s,\mathbf{u})+\gamma
Q^{\phi}(s^{\prime},\mathbf{u}^{\prime})-Q^{\phi}(s,\mathbf{u}))^{2}].$ Value
based methods use the $Q^{\pi}$ estimate to derive a behaviour policy which is
iteratively improved using the policy improvement theorem (Sutton & Barto,
2011). Actor-critic methods seek to maximise the mean expected payoff of a
policy $\pi_{\theta}$ given by
$\mathcal{J}_{\theta}=\int_{S}\rho^{\pi}(s)\int_{\mathbf{U}}\pi_{\theta}(\mathbf{u|s})Q^{\pi}(s,\mathbf{u})d\mathbf{u}ds$
using gradient ascent on a suitable class of stochastic policies parametrised
by $\theta$, where $\rho^{\pi}(s)$ is the stationary distribution over the
states. Updating the policy parameters in the direction of the gradient leads
to policy improvement. The gradient of the above objective is
$\nabla\mathcal{J}_{\theta}=\int_{S}\rho^{\pi}(s)\int_{\mathbf{U}}\nabla\pi_{\theta}(\mathbf{u|s})Q^{\pi}(s,\mathbf{u})d\mathbf{u}ds$
(Sutton et al., 2000). An approximate action-value function based critic
$Q^{\phi}$ is used when estimating the gradient as we do not have access to
the true $Q$-function. Since the critic is learnt using finite number of
samples, it may deviate from the true $Q$-function, potentially causing
incorrect policy updates; this is called the lagging critic problem. The
problem is exacerbated in multi-agent setting where state-action spaces are
very large.

##### Tensor Decomposition

Tensors are high dimensional analogues of matrices and tensor methods
generalize matrix algebraic operations to higher orders. Tensor decomposition,
in particular, generalizes the concept of low-rank matrix factorization. In
the rest of this paper, we use $\hat{\cdot}$ to represent tensors. Formally,
an order $n$ tensor $\hat{T}$ has $n$ index sets ${I}_{j},\forall
j\in\\{1..n\\}$ and has elements $T(e),\forall
e\in\times_{\mathcal{I}}{I}_{j}$ taking values in a given set $\mathcal{S}$,
where $\times$ is the set cross product and we denote the set of index sets by
$\mathcal{I}$. Each dimension $\\{1..n\\}$ is also called a mode.

Figure 2: Left: Tensor diagram for an order $3$ tensor $\hat{T}$. Right:
Contraction between $\hat{T}^{1}$,$\hat{T}^{2}$ on common index sets
$I_{2},I_{3}$.

An elegant way of representing tensors and associated operations is via tensor
diagrams as shown in Fig. 2. Tensor contraction generalizes the concept of
matrix with matrix multiplication. For any two tensors $\hat{T}^{1}$ and
$\hat{T}^{2}$ with $\mathcal{I}_{\cap}=\mathcal{I}^{1}\cap\mathcal{I}^{2}$ we
define the contraction operation as $\hat{T}=\hat{T}^{1}{\odot}\hat{T}^{2}$
with
$\hat{T}(e_{1},e_{2})=\sum_{e\in\times_{\mathcal{I}_{\cap}}{I}_{j}}\hat{T}^{1}(e_{1},e)\cdot\hat{T}^{2}(e_{2},e),e_{i}\in\times_{\mathcal{I}^{i}\setminus\mathcal{I}_{\cap}}{I}_{j}$.
The contraction operation is associative and can be extended to an arbitrary
number of tensors. Using this building block, we can define tensor
decompositions, which factorizes a (low-rank) tensor in a compact form. This
can be done with various decompositions (Kolda & Bader, 2009), such as Tucker,
Tensor-Train (also known as Matrix-Product-State), or CP (for Canonical-
Polyadic). In this paper, we focus on the latter, which we briefly introduce
here. Just as a matrix can be factored as a sum of rank-$1$ matrices (each
being an outer product of vectors), a tensor can be factored as a sum of
rank-1 tensors, the latter being an outer product of vectors. The number of
vectors in the outer product is equal to the rank of the tensor, and the
number of terms in the sum is called the _rank of the decomposition_
(sometimes also called CP-rank). Formally, a tensor $\hat{T}$ can be factored
using a (rank–$k$) CP decomposition into a sum of $k$ vector outer products
(denoted by $\otimes$), as,

$\displaystyle\hat{T}=\sum_{r=1}^{k}w_{r}\otimes^{n}u_{r}^{i},i\in\\{1..n\\},||u_{r}^{i}||_{2}=1.$
(2)

##  3 Methodology

###  3.1 Tensorised Bellman equation

In this section, we provide the basic framework for Tesseract. We focus here
on the discrete action space. The extension for continuous actions is similar
and is deferred to Section B.2 for clarity of exposition.

######  Proposition 1.

Any real-valued function $f$ of $n$ arguments $(x_{1}..x_{n})$ each taking
values in a finite set $x_{i}\in\mathcal{D}_{i}$ can be represented as a
tensor $\hat{f}$ with modes corresponding to the domain sets $\mathcal{D}_{i}$
and entries $\hat{f}(x_{1}..x_{n})=f(x_{1}..x_{n})$.

Given a multi-agent problem $G=\left\langle
S,U,P,r,Z,O,n,\gamma\right\rangle$, let $\mathcal{Q}\triangleq\\{Q:S\times
U^{n}\to\mathbb{R}\\}$ be the set of real-valued functions on the state-action
space. We are interested in the _curried_(Barendregt, 1984) form $Q:S\to
U^{n}\to\mathbb{R},Q\in\mathcal{Q}$ so that $Q(s)$ is an order $n$ tensor (We
use functions and tensors interchangeably where it is clear from context).
Algorithms in Tesseract operate directly on the curried form and preserve the
structure implicit in the output tensor. (Currying in the context of tensors
implies fixing the value of some index. Thus, Tesseract-based methods keep
action indices free and fix only state-dependent indices.)

We are now ready to present the tensorised form of the Bellman equation shown
in Eq. 1. Fig. 3 gives the equation where $\hat{I}$ is the identity tensor of
size $|S|\times|S|\times|S|$. The dependence of the action-value tensor
$\hat{Q}^{\pi}$ and the policy tensor $\hat{U}^{\pi}$ on the policy is denoted
by superscripts $\pi$. The novel Tensorised Bellman equation provides a
theoretically justified foundation for the approximation of the joint
$Q$-function, and the subsequent analysis (Theorems 1-3) for learning using
this approximation.

Figure 3: Tensorised Bellman Equation for $n$ agents. There is an edge for
each agent $i\in\mathcal{A}$ in the corresponding nodes
$\hat{Q}^{\pi},\hat{U}^{\pi},\hat{R},\hat{P}$ with the index set $U^{i}$.

###  3.2 Tesseract Algorithms

For any $k\in\mathbb{N}$ let
$\mathcal{Q}_{k}\triangleq\\{Q:Q\in\mathcal{Q}\land rank(Q(\cdot,s))\leq
k,\forall s\in S\\}$. Given any policy $\pi$ we are interested in projecting
$Q^{\pi}$ to $\mathcal{Q}_{k}$ using the projection operator
$\Pi_{k}(\cdot)=\operatorname*{arg\,min}_{Q\in\mathcal{Q}_{k}}||\cdot-Q||_{\pi,F}$.
where $||X||_{\pi,F}\triangleq\mathbb{E}_{s\sim\rho^{\pi}(s)}[||X(s)||_{F}]$
is the weighted Frobenius norm w.r.t. policy visitation over states. Thus a
simple planning based algorithm for rank $k$ Tesseract would involve starting
with an arbitrary $Q_{0}$ and successively applying the Bellman operator
$\mathcal{T}^{\pi}$ and the projection operator $\Pi_{k}$ so that
$Q_{t+1}=\Pi_{k}\mathcal{T}^{\pi}Q_{t}$.

As we show in Theorem 1, constraining the underlying tensors for dynamics and
rewards ($\hat{P},\hat{R}$) is sufficient to bound the CP-rank of $\hat{Q}$.
From this insight, we propose a model-based RL version for Tesseract in
Algorithm 1. The algorithm proceeds by estimating the underlying MDP dynamics
using the sampled trajectories obtained by executing the behaviour policy
$\pi=(\pi^{i})_{1}^{n}$ (factorisable across agents) satisfying Theorem 2.
Specifically, we use a rank $k$ approximate CP-Decomposition to calculate the
model dynamics $R,P$ as we show in Section 4. Next $\pi$ is evaluated using
the estimated dynamics, which is followed by policy improvement, Algorithm 1
gives the pseudocode for the model-based setting. The termination and policy
improvement decisions in Algorithm 1 admit a wide range of choices used in
practice in the RL community. Example choices for internal iterations which
broadly fall under approximate policy iteration include: 1) Fixing the number
of applications of Bellman operator 2) Using norm of difference between
consecutive Q estimates etc., similarly for policy improvement several options
can be used like $\epsilon$-greedy (for Q derived policy), policy gradients
(parametrized policy) (Sutton & Barto, 2011)

Algorithm 1 Model-based Tesseract

1: Initialise rank $k$, $\pi=(\pi^{i})_{1}^{n}$ and $\hat{Q}$: Theorem 2

2: Initialise model parameters $\hat{P},\hat{R}$

3: Learning rate $\leftarrow\alpha$,$\mathcal{D}\leftarrow\left\\{\right\\}$

4: for each episodic iteration i do

5: Do episode rollout
$\tau_{i}=\left\\{(s_{t},\mathbf{u}_{t},r_{t},s_{t+1})_{0}^{L}\right\\}$ using
$\pi$

6: $\mathcal{D}\leftarrow\mathcal{D}\cup\left\\{\tau_{i}\right\\}$

7: Update $\hat{P},\hat{R}$ using CP-Decomposition on moments from
$\mathcal{D}$ (Theorem 2)

8: for each internal iteration j do

9: $\hat{Q}\leftarrow\mathcal{T}^{\pi}\hat{Q}$

10: end for

11: Improve $\pi$ using $\hat{Q}$

12: end for

13: Return $\pi,\hat{Q}$

For large state spaces where storage and planning using model parameters is
computationally difficult (they are $\mathcal{O}(kn|U||S|^{2})$ in number), we
propose a model-free approach using a deep network where the rank constraint
on the $Q$-function is directly embedded into the network architecture. Fig. 4
gives the general network architecture for this approach and Algorithm 2 the
associated pseudo-code. Each agent in Fig. 4 has a policy network
parameterized by $\theta$ which is used to take actions in a decentralised
manner.

Figure 4: Tesseract architecture

The observations of the individual agents along with the actions are fed
through representation function $g_{\phi}$ whose output is a set of $k$ unit
vectors of dimensionality $|U|$ corresponding to each rank. The output
$g_{\phi,r}(s^{i})$ corresponding to each agent $i$ for factor $r$ can be seen
as an action-wise contribution to the joint utility from the agent
corresponding to that factor. The joint utility here is a product over
individual agent utilities. For partially observable settings, an additional
RNN layer can be used to summarise agent trajectories. The joint action-value
estimate of the tensor $\hat{Q}(s)$ by the centralized critic is:

$\displaystyle\hat{Q}(s)\approx
T=\sum_{r=1}^{k}w_{r}\otimes^{n}g_{\phi,r}(s^{i}),i\in\\{1..n\\},\vspace{-5pt}$
(3)

where the weights $w_{r}$ are learnable parameters exclusive to the
centralized learner. In the case of value based methods where the policy is
implicitly derived from utilities, the policy parameters $\theta$ are merged
with $\phi$. The network architecture is agnostic to the type of the action
space (discrete/continuous) and the action-value corresponding to a particular
joint-action $(u^{1}..u^{n})$ is the inner product $\langle T,A\rangle$ where
$A=\otimes^{n}u^{i}$ (This reduces to indexing using joint action in Eq. 3 for
discrete spaces). More representational capacity can be added to the network
by creating an abstract representation for actions using $f_{\eta}$, which can
be any arbitrary monotonic function (parametrised by $\eta$) of vector output
of size $m\geq|U|$ and preserves relative order of utilities across actions;
this ensures that the optimal policy is learnt as long as it belongs to the
hypothesis space. In this case $A=\otimes^{n}f_{\eta}(u^{i})$ and the agents
also carry a copy of $f_{\eta}$ during the execution phase. Furthermore, the
inner product $\langle T,A\rangle$ can be computed efficiently using the
property

$\langle T,A\rangle=\sum_{r=1}^{k}w_{r}\prod_{1}^{n}\langle
f_{\eta}(u^{i})g_{\phi,r}(s^{i})\rangle,i\in\\{1..n\\}$

which is $O(nkm)$ whereas a naive approach involving computation of the
tensors first would be $O(km^{n})$. Training the Tesseract-based $Q$-network
involves minimising the squared TD loss (Sutton & Barto, 2011):

$\displaystyle\mathcal{L}_{TD}(\phi,\eta)=\mathbb{E}_{\pi}[($ $\displaystyle
Q(\mathbf{u}_{t},s_{t};\phi,\eta)$ (4) $\displaystyle-$
$\displaystyle[r(\mathbf{u}_{t},s_{t})+\gamma
Q(\mathbf{u}_{t+1},s_{t+1};\phi^{-},\eta^{-})])^{2}],$ (5)

where $\phi^{-},\eta^{-}$ are target parameters. Policy updates involve
gradient ascent w.r.t. to the policy parameters $\theta$ on the objective
$\mathcal{J}_{\theta}=\int_{S}\rho^{\pi}(s)\int_{\mathbf{U}}\pi_{\theta}(\mathbf{u|s})Q^{\pi}(s,\mathbf{u})d\mathbf{u}ds$.
More sophisticated targets can be used to reduce the policy gradient variance
(Greensmith et al., 2004; Zhao et al., 2016) and propagate rewards efficiently
(Sutton, 1988). Note that Algorithm 2 does not require the individual-global
maximisation principle (Son et al., 2019) typically assumed by value-based
MARL methods in the CTDE setting, as it is an actor-critic method. In general,
any form of function approximation and compatible model-free approach can be
interleaved with Tesseract by appropriate use of the projection function
$\Pi_{k}$.

Algorithm 2 Model-free Tesseract

1: Initialise rank $k$, parameter vectors $\theta,\phi,\eta$

2: Learning rate $\leftarrow\alpha$,$\mathcal{D}\leftarrow\left\\{\right\\}$

3: for each episodic iteration i do

4: Do episode rollout
$\tau_{i}=\left\\{(s_{t},\mathbf{u}_{t},r_{t},s_{t+1})_{0}^{L}\right\\}$ using
$\pi_{\theta}$

5: $\mathcal{D}\leftarrow\mathcal{D}\cup\left\\{\tau_{i}\right\\}$

6: Sample batch $\mathcal{B}\subseteq\mathcal{D}$.

7: Compute empirical estimates for $\mathcal{L}_{TD},\mathcal{J}_{\theta}$

8: $\phi\leftarrow\phi-\alpha\nabla_{\phi}\mathcal{L}_{TD}$ (Rank $k$
projection step)

9: $\eta\leftarrow\eta-\alpha\nabla_{\eta}\mathcal{L}_{TD}$ (Action
representation update)

10: $\theta\leftarrow\theta+\alpha\nabla_{\theta}\mathcal{J}_{\theta}$ (Policy
update)

11: end for

12: Return $\pi,\hat{Q}$

###  3.3 Why Tesseract?

As discussed in Section 1, $Q(s)$ is an object of prime interest in MARL.
Value based methods (Sunehag et al., 2017; Rashid et al., 2018; Yao et al.,
2019) that directly approximate the optimal action values $Q^{*}$ place
constraints on $Q(s)$ such that it is a monotonic combination of agent
utilities. In terms of Tesseract this directly translates to finding the best
projection constraining $Q(s)$ to be rank one (Section B.1). Similarly, the
following result demonstrates containment of action-value functions
representable by FQL(Chen et al., 2018) which uses a learnt inner product to
model pairwise agent interactions (proof and additional results in Section
B.1):.

######  Proposition 2.

The set of joint Q-functions representable by FQL is a subset of that
representable by Tesseract.

MAVEN (Mahajan et al., 2019) illustrates how rank $1$ projections can lead to
insufficient exploration and provides a method to avoid suboptimality by using
mutual information (MI) to learn a diverse set of rank $1$ projections that
correspond to different joint behaviours. In Tesseract, this can simply be
achieved by finding the best approximation constraining $Q(s)$ to be rank $k$.
Moreover, the CP-decomposition problem, being a product form (Eq. 2), is well
posed, whereas in (Mahajan et al., 2019) the problem form is
$\hat{T}=\sum_{r=1}^{k}w_{r}\oplus^{n}u_{r}^{i},i\in\\{1..n\\},||u_{r}^{i}||_{2}=1$,
which requires careful balancing of different factors $\\{1..k\\}$ using MI as
otherwise all factors collapse to the same estimate. The above improvements
are equally important for the critic in actor-critic frameworks. Note that
Tesseract is complete in the sense that every possible joint Q-function is
representable by it given sufficient approximation rank. This follows as every
possible Q-tensor can be expressed as linear combination of one-hot tensors
(which form a basis for the set).

Many real world problems have high-dimensional observation spaces that are
encapsulated in an underlying low dimensional latent space that governs the
transition and reward dynamics (Azizzadenesheli et al., 2016). For example, in
the case of robot navigation, the observation is high dimensional visual and
sensory input but solving the underlying problem requires only knowing the 2D
position. Standard RL algorithms that do not address modelling the latent
structure in such problems typically incur poor performance and
intractability. In Section 4 we show how Tesseract can be leveraged for such
scenarios. Finally, projection to a low rank offers a natural way of
regularising the approximate $Q$-functions and makes them easier to learn,
which is important for making value function approximation amenable to multi-
agent settings. Specifically for the case of actor-critic methods, this
provides a natural way to make the critic learn more quickly. Additional
discussion about using Tesseract for continuous action spaces can be found in
Section B.2.

##  4 Analysis

In this section we provide a PAC analysis of model-based Tesseract (Algorithm
1). We focus on the MMDP setting (Section 2) for the simplicity of notation
and exposition; guidelines for other settings are provided in Appendix A.

The objective of the analysis is twofold: Firstly it provides concrete
quantification of the sample efficiency gained by model-based policy
evaluation. Secondly, it provides insights into how Tesseract can similarly
reduce sample complexity for model-free methods. Proofs for the results stated
can be found in Appendix A. We begin with the assumptions used for the
analysis:

######  Assumption 1.

For the given MMDP $G=\left\langle S,U,P,r,n,\gamma\right\rangle$, the reward
tensor $\hat{R}(s),\forall s\in S$ has bounded rank $k_{1}\in\mathbb{N}$.

Intuitively, a small $k_{1}$ in 1 implies that the reward is dependent only on
a small number of intrinsic factors characterising the actions.

######  Assumption 2.

For the given MMDP $G=\left\langle S,U,P,r,n,\gamma\right\rangle$, the
transition tensor $\hat{P}(s,s^{\prime}),\forall s,s^{\prime}\in S$ has
bounded rank $k_{2}\in\mathbb{N}$.

Intuitively a small $k_{2}$ in 2 implies that only a small number of intrinsic
factors characterising the actions lead to meaningful change in the joint
state. 1-2 always hold for a finite MMDP as CP-rank is upper bounded by
$\Pi_{j=1}^{n}|U_{j}|$, where $U_{j}$ are the action sets.

######  Assumption 3.

The underlying MMDP is ergodic for any policy $\pi$ so that there is a
stationary distribution $\rho^{\pi}$.

Next, we define coherence parameters, which are quantities of interest for our
theoretical results: for reward decomposition
$\hat{R}(s)=\sum_{r}w_{r,s}\otimes^{n}v_{r,i,s}$, let
$\mu_{s}=\sqrt{n}\max_{i,r,j}|v_{r,i,s}(j)|$,
$w_{s}^{\text{max}}=\max_{i,r}w_{r,s}$,$w_{s}^{\text{min}}=\min_{i,r}w_{r,s}$.
Similarly define the corresponding quantities for
$\mu_{s,s^{\prime}},w_{s,s^{\prime}}^{\text{max}},w_{s,s^{\prime}}^{\text{min}}$
for transition tensors $\hat{P}(s,s^{\prime})$. A low coherence implies that
the tensor’s mass is evenly spread and helps bound the possibility of never
seeing an entry with very high mass (large absolute value of an entry).

######  Theorem 1.

For a finite MMDP the action-value tensor satisfies
$rank(\hat{Q}^{\pi}(s))\leq k_{1}+k_{2}|S|,\forall s\in S,\forall\pi$.

###### Proof.

We first unroll the Tensor Bellman equation in Fig. 3. The first term
$\hat{R}$ has bounded rank $k_{1}$ by 1. Next, each contraction term on the
RHS is a linear combination of $\\{\hat{P}(s,s^{\prime})\\}_{s^{\prime}\in S}$
each of which has bounded rank $k_{2}$ (2). The result follows from the sub-
additivity of CP-rank. ∎

Theorem 1 implies that for approximations with enough factors, policy
evaluation converges:

######  Corollary 1.1.

For all $k\geq k_{1}+k_{2}|S|$, the procedure
$Q_{t+1}\leftarrow\Pi_{k}\mathcal{T}^{\pi}Q_{t}$ converges to $Q^{\pi}$ for
all $Q_{0},\pi$.

Corollary 1.1 is especially useful for the case of M-POMDP and M-ROMDP with
$|Z|>>|S|$, i.e., where the intrinsic state space dimensionality is small in
comparison to the dimensionality of the observations (like robot navigation
Section 3.3). In these cases the Tensorised Bellman equation Fig. 3 can be
augmented by padding the transition tensor $\hat{P}$ with the observation
matrix and the lower bound in Corollary 1.1 can be improved using the
intrinsic state dimensionality.

We next give a PAC result on the number of samples required to infer the
reward and state transition dynamics for finite MDPs with high probability
using sufficient approximate rank $k\geq k_{1},k_{2}$:

######  Theorem 2 (Model based estimation of $\hat{R},\hat{P}$ error bounds).

Given any $\epsilon>0,1>\delta>0$, for a policy $\pi$ with the policy tensor
satisfying $\pi(\mathbf{u}|s)\geq\Delta$, where

$\displaystyle\Delta=\max_{s}\frac{C_{1}\mu_{s}^{6}k^{5}(w_{s}^{\text{max}})^{4}\log(|U|)^{4}\log(3k||R(s)||_{F}/\epsilon)}{|U|^{n/2}(w_{s}^{\text{min}})^{4}}$

and $C_{1}$ is a problem dependent positive constant. There exists $N_{0}$
which is $O(|U|^{\frac{n}{2}})$ and polynomial in
$\frac{1}{\delta},\frac{1}{\epsilon},k$ and relevant spectral properties of
the underlying MDP dynamics such that for samples $\geq N_{0}$, we can compute
the estimates $\bar{R}(s),\bar{P}(s,s^{\prime})$ such that w.p. $\geq
1-\delta$,
$||\bar{R}(s)-\hat{R}(s)||_{F}\leq\epsilon,||\bar{P}(s,s^{\prime})-\hat{P}(s,s^{\prime})||_{F}\leq\epsilon,\forall
s,s^{\prime}\in S$.

Theorem 2 gives the relation between the order of the number of samples
required to estimate dynamics and the tolerance for approximation. Theorem 2
states that aside from allowing efficient PAC learning of the reward and
transition dynamics of the multi-agent MDP, Algorithm 1 requires only
$O(|U|^{\frac{n}{2}})$ to do so, which is a vanishing fraction of $|U|^{n}$,
the total number of joint actions in any given state. This also hints at why a
tensor based approximation of the $Q$-function helps with sample efficiency.
Methods that do not use the tensor structure typically use $O(|U|^{n})$
samples. The bound is also useful for off-policy scenarios, where only the
behaviour policy needs to satisfy the bound. Given the result in Theorem 2, it
is natural to ask what is the error associated with computing the action-
values of a policy using the estimated transition and reward dynamics. We
address this in our next result, but first we present a lemma bounding the
total variation distance between the estimated and true transition
distributions:

######  Lemma 1.

For transition tensor estimates satisfying
$||\bar{P}(s,s^{\prime})-\hat{P}(s,s^{\prime})||_{F}\leq\epsilon$, we have for
any given state-action pair $(s,a)$, the distribution over the next states
follows:
$TV(P^{\prime}(\cdot|s,a),P(\cdot|s,a))\leq\frac{1}{2}(|1-f|+f|S|\epsilon)$
where $\frac{1}{1+\epsilon|S|}\leq f\leq\frac{1}{1-\epsilon|S|}$, where $TV$
is the total variation distance. Similarly for any policy $\pi$,
$TV(\bar{P}_{\pi}(\cdot|s),P_{\pi}(\cdot|s)),TV(\bar{P}_{\pi}(s^{\prime},a^{\prime}|s),P_{\pi}(s^{\prime},a^{\prime}|s))\leq\frac{1}{2}(|1-f|+f|S|\epsilon)$

We now bound the error of model-based evaluation using approximate dynamics in
Theorem 3. The first component on the RHS of the upper bound comes from the
tensor analysis of the transition dynamics, whereas the second component can
be attributed to error propagation for the rewards.

######  Theorem 3 (Error bound on policy evaluation).

Given a behaviour policy $\pi_{b}$ satisfying the conditions in Theorem 2 and
executed for steps $\geq N_{0}$, for any policy $\pi$ the model based policy
evaluation $Q_{\bar{P},\bar{R}}^{\pi}$ satisfies:

$\displaystyle|Q_{P,R}^{\pi}(s,a)-Q_{\bar{P},\bar{R}}^{\pi}(s,a)|\leq$
$\displaystyle(|1-f|+f|S|\epsilon)\frac{\gamma}{2(1-\gamma)^{2}}$ (6)
$\displaystyle+\frac{\epsilon}{1-\gamma},\forall(s,a)\in S\times U^{n}$ (7)

where $f$ is as defined in Lemma 1.

Additional theoretical discussion can be found in Section B.3

##  5 Experiments

In this section we present the empirical results on the StarCraft domain.
Experiments for a more didactic domain of Tensor games can be found in Section
C.3. We use the model-free version of Tesseract (Algorithm 2) for all the
experiments.

(a) 3s5z Easy

(b) 2s_vs_1sc Easy

(c) 2c_vs_64zg Hard

(d) 5m_vs_6m Hard

(e) MMM2 Super Hard

(f) 27m_vs_30m Super Hard

(g) 6h_vs_8z Super Hard

(h) Corridor Super Hard

Figure 5: Performance of different algorithms on different SMAC scenarios:
TAC, QMIX, VDN, FQL, IQL.

##### StarCraft II

We consider a challenging set of cooperative scenarios from the StarCraft
Multi-Agent Challenge (SMAC) (Samvelyan et al., 2019). Scenarios in SMAC have
been classified as Easy, Hard and Super-hard according to the performance of
exiting algorithms on them. We compare Tesseract (TAC in plots) to, QMIX
(Rashid et al., 2018), VDN (Sunehag et al., 2017), FQL (Chen et al., 2018),
and IQL (Tan, 1993). VDN and QMIX use monotonic approximations for learning
the Q-function. FQL uses a pairwise factorized model to capture effects of
agent interactions in joint Q-function, this is done by learning an inner
product space for summarising agent trajectories. IQL ignores the multi-
agentness of the problem and learns an independent per agent policy for the
resulting non-stationary problem. Fig. 5 gives the win rate of the different
algorithms averaged across five random runs. Fig. 5(c) features 2c_vs_64zg, a
hard scenario that contains two allied agents but 64 enemy units (the largest
in the SMAC domain) making the action space of the agents much larger than in
the other scenarios. Tesseract gains a huge lead over all the other algorithms
in just one million steps. For the asymmetric scenario of 5m_vs_6m Fig. 5(d),
Tesseract, QMIX, and VDN learn effective policies, similar behavior occurs in
the heterogeneous scenarios of 3s5z Fig. 5(a) and MMM2Fig. 5(e) with the
exception of VDN for the latter. In 2s_vs_1sc in Fig. 5(b), which requires a
‘kiting’ strategy to defeat the spine crawler, Tesseract learns an optimal
policy in just 100k steps. In the super-hard scenario of 27m_vs_30m Fig. 5(f)
having largest ally team of 27 marines, Tesseract again shows improved sample
efficiency; this map also shows Tesseract’s ability to scale with the number
of agents. Finally in the super-hard scenarios of 6 hydralisks vs 8 zealots
Fig. 5(g) and Corridor Fig. 5(h) which require careful exploration, Tesseract
is the only algorithm which is able to find a good policy. We observe that IQL
doesn’t perform well on any of the maps as it doesn’t model agent
interactions/non-stationarity explicitly. FQL loses performance possibly
because modelling just pairwise interactions with a single dot product might
not be expressive enough for joint-Q. Finally, VDN and QMIX are unable to
perform well on many of the challenging scenarios possibly due to the
monotonic approximation affecting the exploration adversely (Mahajan et al.,
2019). Additional plots and experiment details can be found in Section C.1
with comparison with other baselines in Section C.1.1 including QPLEX(Wang et
al., 2020a), QTRAN(Son et al., 2019), HQL(Matignon et al., 2007),
COMA(Foerster et al., 2018) . We detail the techniques used for stabilising
the learning of tensor decomposed critic in Section C.2.

##  6 Related Work

Previous methods for modelling multi-agent interactions include those that use
coordination graph methods for learning a factored joint action-value
estimation (Guestrin et al., 2002a, b; Bargiacchi et al., 2018), however
typically require knowledge of the underlying coordination graph. To handle
the exponentially growing complexity of the joint action-value functions with
the number of agents, a series of value-based methods have explored different
forms of value function factorisation. VDN (Sunehag et al., 2017) and QMIX
(Rashid et al., 2018) use monotonic approximation with latter using a mixing
network conditioned on global state. QTRAN (Son et al., 2019) avoids the
weight constraints imposed by QMIX by formulating multi-agent learning as an
optimisation problem with linear constraints and relaxing it with L2
penalties. MAVEN (Mahajan et al., 2019) learns a diverse ensemble of monotonic
approximations by conditioning agent $Q$-functions on a latent space which
helps overcome the detrimental effects of QMIX’s monotonicity constraint on
exploration. Similarly, Uneven (Gupta et al., 2020) uses universal successor
features for efficient exploration in the joint action space. Qatten (Yang et
al., 2020) makes use of a multi-head attention mechanism to decompose
$Q_{tot}$ into a linear combination of per-agent terms. RODE (Wang et al.,
2020b) learns an action effect based role decomposition for sample efficient
learning. Policy gradient methods, on the other hand, often utilise the actor-
critic framework to cope with decentralisation. MADDPG (Lowe et al., 2017)
trains a centralised critic for each agent. COMA (Foerster et al., 2018)
employs a centralised critic and a counterfactual advantage function. These
actor-critic methods, however, suffer from poor sample efficiency compared to
value-based methods and often converge to sub-optimal local minima. While
sample efficiency has been an important goal for single agent reinforcement
learning methods (Mahajan & Tulabandhula, 2017a, b; Kakade, 2003; Lattimore et
al., 2013), in this work we shed light on attaining sample efficiency for
cooperative multi-agent systems using low rank tensor approximation.

_Tensor methods_ have been used in machine learning, in the context of
learning latent variable models (Anandkumar et al., 2014) and signal
processing (Sidiropoulos et al., 2017). Tensor methods provides powerful
analytical tools that have been used for various applications, including the
theoretical analysis of deep neural networks (Cohen et al., 2016). Model
compression using tensors (Cheng et al., 2017) has recently gained momentum
owing to the large sizes of deep neural nets. Using tensor decomposition
within deep networks, it is possible to both compress and speed them up
(Cichocki et al., 2017; Kossaifi et al., 2019). They allow generalization to
higher orders (Kossaifi et al., 2020) and have also been used for multi-task
learning and domain adaptation (Bulat et al., 2020). In contrast to prior work
on value function factorisation, Tesseract provides a natural spectrum for
approximation of action-values based on the rank of approximation and provides
theoretical guarantees derived from tensor analysis. Multi-view methods
utilising tensor decomposition have previously been used in the context of
partially observable single-agent RL (Azizzadenesheli et al., 2016;
Azizzadenesheli, 2019). There the goal is to efficiently infer the underlying
MDP parameters for planning under rich observation settings (Krishnamurthy et
al., 2016). Similarly (Bromuri, 2012) use four dimensional factorization to
generalise across Q-tables whereas here we use them for modelling interactions
across multiple agents.

##  7 Conclusions & Future Work

We introduced Tesseract, a novel framework utilising the insight that the
joint action value function for MARL can be seen as a tensor. Tesseract
provides a means for developing new sample efficient algorithms and obtain
essential guarantees about convergence and recovery of the underlying
dynamics. We further showed novel PAC bounds for learning under the framework
using model-based algorithms. We also provided a model-free approach to
implicitly induce low rank tensor approximation for better sample efficiency
and showed that it outperforms current state of art methods. There are several
interesting open questions to address in future work, such as convergence and
error analysis for rank insufficient approximation, and analysis of the
learning framework under different types of tensor decompositions like Tucker
and tensor-train (Kolda & Bader, 2009).

##  8 Acknowledgements

AM is funded by the J.P. Morgan A.I. fellowship. Part of this work was done
during AM’s internship at NVIDIA. This project has received funding from the
European Research Council under the European Union’s Horizon 2020 research and
innovation programme (grant agreement number 637713). The experiments were
made possible by generous equipment grant from NVIDIA.

## References

  * Anandkumar et al. (2012) Anandkumar, A., Hsu, D., and Kakade, S. M.  A method of moments for mixture models and hidden markov models.  In _Conference on Learning Theory_ , pp. 33–1, 2012.
  * Anandkumar et al. (2014) Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M., and Telgarsky, M.  Tensor decompositions for learning latent variable models.  _Journal of Machine Learning Research_ , 15:2773–2832, 2014\.
  * Azizzadenesheli (2019) Azizzadenesheli, K.  _Reinforcement Learning in Structured and Partially Observable Environments_.  PhD thesis, UC Irvine, 2019.
  * Azizzadenesheli et al. (2016) Azizzadenesheli, K., Lazaric, A., and Anandkumar, A.  Reinforcement learning in rich-observation mdps using spectral methods.  _arXiv preprint arXiv:1611.03907_ , 2016.
  * Barendregt (1984) Barendregt, H. P.  Introduction to lambda calculus.  1984\.
  * Bargiacchi et al. (2018) Bargiacchi, E., Verstraeten, T., Roijers, D., Nowé, A., and Hasselt, H.  Learning to coordinate with coordination graphs in repeated single-stage multi-agent decision problems.  In _International conference on machine learning_ , pp. 482–490, 2018.
  * Boutilier (1996) Boutilier, C.  Planning, learning and coordination in multiagent decision processes.  In _Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge_ , TARK ’96, pp. 195–210. Morgan Kaufmann Publishers Inc., 1996.
  * Bromuri (2012) Bromuri, S.  A tensor factorization approach to generalization in multi-agent reinforcement learning.  In _2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology_ , volume 2, pp. 274–281. IEEE, 2012.
  * Bulat et al. (2020) Bulat, A., Kossaifi, J., Tzimiropoulos, G., and Pantic, M.  Incremental multi-domain learning with network latent tensor factorization.  2020\.
  * Buşoniu et al. (2010) Buşoniu, L., Babuška, R., and De Schutter, B.  Multi-agent reinforcement learning: An overview.  In _Innovations in multi-agent systems and applications-1_ , pp. 183–221. Springer, 2010.
  * Chen et al. (2018) Chen, Y., Zhou, M., Wen, Y., Yang, Y., Su, Y., Zhang, W., Zhang, D., Wang, J., and Liu, H.  Factorized q-learning for large-scale multi-agent systems.  _arXiv preprint arXiv:1809.03738_ , 2018.
  * Cheng et al. (2017) Cheng, Y., Wang, D., Zhou, P., and Zhang, T.  A survey of model compression and acceleration for deep neural networks.  _arXiv preprint arXiv:1710.09282_ , 2017.
  * Cichocki et al. (2017) Cichocki, A., Phan, A.-H., Zhao, Q., Lee, N., Oseledets, I., Sugiyama, M., Mandic, D. P., et al.  Tensor networks for dimensionality reduction and large-scale optimization: Part 2 applications and future perspectives.  _Foundations and Trends® in Machine Learning_ , 9(6):431–673, 2017.
  * Cohen et al. (2016) Cohen, N., Sharir, O., and Shashua, A.  On the expressive power of deep learning: A tensor analysis.  In _Conference on Learning Theory_ , pp. 698–728, 2016.
  * Foerster et al. (2018) Foerster, J. N., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S.  Counterfactual multi-agent policy gradients.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Greensmith et al. (2004) Greensmith, E., Bartlett, P. L., and Baxter, J.  Variance reduction techniques for gradient estimates in reinforcement learning.  _Journal of Machine Learning Research_ , 5(9), 2004.
  * Guestrin et al. (2002a) Guestrin, C., Lagoudakis, M., and Parr, R.  Coordinated reinforcement learning.  In _ICML_ , volume 2, pp. 227–234. Citeseer, 2002a.
  * Guestrin et al. (2002b) Guestrin, C., Venkataraman, S., and Koller, D.  Context-specific multiagent coordination and planning with factored mdps.  In _AAAI/IAAI_ , pp. 253–259, 2002b.
  * Gupta et al. (2020) Gupta, T., Mahajan, A., Peng, B., Böhmer, W., and Whiteson, S.  Uneven: Universal value exploration for multi-agent reinforcement learning.  _arXiv preprint arXiv:2010.02974_ , 2020.
  * Hillar & Lim (2013) Hillar, C. J. and Lim, L.-H.  Most tensor problems are np-hard.  _Journal of the ACM (JACM)_ , 60(6):1–39, 2013\.
  * Jain & Oh (2014) Jain, P. and Oh, S.  Provable tensor factorization with missing data.  In _Advances in Neural Information Processing Systems_ , pp. 1431–1439, 2014.
  * Kaelbling et al. (1998) Kaelbling, L. P., Littman, M. L., and Cassandra, A. R.  Planning and acting in partially observable stochastic domains.  _Artificial intelligence_ , 101(1-2):99–134, 1998\.
  * Kakade (2003) Kakade, S. M.  _On the sample complexity of reinforcement learning_.  PhD thesis, UCL (University College London), 2003.
  * Kearns et al. (1994) Kearns, M. J., Vazirani, U. V., and Vazirani, U.  _An introduction to computational learning theory_.  MIT press, 1994.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kolda & Bader (2009) Kolda, T. G. and Bader, B. W.  Tensor decompositions and applications.  _SIAM review_ , 51(3):455–500, 2009.
  * Konda & Tsitsiklis (2002) Konda, V. and Tsitsiklis, J. N.  _Actor-Critic Algorithms_.  PhD thesis, USA, 2002.  AAI0804543.
  * Kossaifi et al. (2019) Kossaifi, J., Bulat, A., Tzimiropoulos, G., and Pantic, M.  T-net: Parametrizing fully convolutional nets with a single high-order tensor.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Kossaifi et al. (2020) Kossaifi, J., Toisoul, A., Bulat, A., Panagakis, Y., Hospedales, T., and Pantic, M.  Factorized higher-order cnns with an application to spatio-temporal emotion estimation.  In _IEEE CVPR_ , 2020.
  * Krishnamurthy et al. (2016) Krishnamurthy, A., Agarwal, A., and Langford, J.  Pac reinforcement learning with rich observations.  In _Advances in Neural Information Processing Systems_ , pp. 1840–1848, 2016.
  * Lattimore et al. (2013) Lattimore, T., Hutter, M., and Sunehag, P.  The sample-complexity of general reinforcement learning.  In _International Conference on Machine Learning_ , pp. 28–36. PMLR, 2013.
  * Lowe et al. (2017) Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, O. P., and Mordatch, I.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In _Advances in Neural Information Processing Systems_ , pp. 6379–6390, 2017.
  * Mahajan & Tulabandhula (2017a) Mahajan, A. and Tulabandhula, T.  Symmetry detection and exploitation for function approximation in deep rl.  In _Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems_ , pp. 1619–1621, 2017a.
  * Mahajan & Tulabandhula (2017b) Mahajan, A. and Tulabandhula, T.  Symmetry learning for function approximation in reinforcement learning.  _arXiv preprint arXiv:1706.02999_ , 2017b.
  * Mahajan et al. (2019) Mahajan, A., Rashid, T., Samvelyan, M., and Whiteson, S.  Maven: Multi-agent variational exploration.  In _Advances in Neural Information Processing Systems_ , pp. 7611–7622, 2019.
  * Matignon et al. (2007) Matignon, L., Laurent, G. J., and Le Fort-Piat, N.  Hysteretic q-learning: an algorithm for decentralized reinforcement learning in cooperative multi-agent teams.  In _2007 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pp. 64–69. IEEE, 2007.
  * Messias et al. (2011) Messias, J. a. V., Spaan, M. T. J., and Lima, P. U.  Efficient offline communication policies for factored multiagent pomdps.  In _Proceedings of the 24th International Conference on Neural Information Processing Systems_ , pp. 1917–1925. Curran Associates Inc., 2011\.
  * Oliehoek & Amato (2016) Oliehoek, F. A. and Amato, C.  _A Concise Introduction to Decentralized POMDPs_.  SpringerBriefs in Intelligent Systems. Springer, 2016.
  * Rashid et al. (2018) Rashid, T., Samvelyan, M., de Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S.  QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 4295–4304, 2018.
  * Samvelyan et al. (2019) Samvelyan, M., Rashid, T., de Witt, C. S., Farquhar, G., Nardelli, N., Rudner, T. G., Hung, C.-M., Torr, P. H., Foerster, J., and Whiteson, S.  The StarCraft Multi-Agent Challenge.  In _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems_ , 2019.
  * Sidiropoulos et al. (2017) Sidiropoulos, N. D., De Lathauwer, L., Fu, X., Huang, K., Papalexakis, E. E., and Faloutsos, C.  Tensor decomposition for signal processing and machine learning.  _IEEE Transactions on Signal Processing_ , 65(13):3551–3582, 2017.
  * Son et al. (2019) Son, K., Kim, D., Kang, W. J., Hostallero, D. E., and Yi, Y.  Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning.  _arXiv preprint arXiv:1905.05408_ , 2019.
  * Sunehag et al. (2017) Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., and Graepel, T.  Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward.  In _Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems_ , 2017.
  * Sutton (1988) Sutton, R. S.  Learning to predict by the methods of temporal differences.  _Machine learning_ , 3(1):9–44, 1988.
  * Sutton & Barto (2011) Sutton, R. S. and Barto, A. G.  Reinforcement learning: An introduction.  2011\.
  * Sutton et al. (2000) Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y.  Policy gradient methods for reinforcement learning with function approximation.  In _Advances in neural information processing systems_ , pp. 1057–1063, 2000.
  * Tan (1993) Tan, M.  Multi-agent reinforcement learning: Independent vs. cooperative agents.  In _Proceedings of the Tenth International Conference on Machine Learning_ , pp. 330–337, 1993.
  * Wang et al. (2020a) Wang, J., Ren, Z., Liu, T., Yu, Y., and Zhang, C.  Qplex: Duplex dueling multi-agent q-learning.  _arXiv preprint arXiv:2008.01062_ , 2020a.
  * Wang et al. (2020b) Wang, T., Gupta, T., Mahajan, A., Peng, B., Whiteson, S., and Zhang, C.  Rode: Learning roles to decompose multi-agent tasks.  _arXiv preprint arXiv:2010.01523_ , 2020b.
  * Wei et al. (2018) Wei, E., Wicke, D., Freelan, D., and Luke, S.  Multiagent soft q-learning.  In _2018 AAAI Spring Symposium Series_ , 2018.
  * Yang et al. (2020) Yang, Y., Hao, J., Liao, B. L., Shao, K., Chen, G., Liu, W., and Tang, H.  Qatten: A general framework for cooperative multiagent reinforcement learning.  _ArXiv_ , abs/2002.03939, 2020.
  * Yao et al. (2019) Yao, X., Wen, C., Wang, Y., and Tan, X.  Smix: Enhancing centralized value functions for cooperative multi-agent reinforcement learning.  _arXiv preprint arXiv:1911.04094_ , 2019.
  * Zhao et al. (2016) Zhao, T., Niu, G., Xie, N., Yang, J., and Sugiyama, M.  Regularized policy gradients: direct variance reduction in policy gradient estimation.  In _Asian Conference on Machine Learning_ , pp. 333–348. PMLR, 2016\.

##  Appendix A Additional Proofs

###  A.1 Proof of Theorem 2

######  Theorem 2 (Model based estimation of $\hat{R},\hat{P}$ error bounds).

Given any $\epsilon>0,1>\delta>0$, for a policy $\pi$ with the policy tensor
satisfying $\pi(\mathbf{u}|s)\geq\Delta$, where

$\displaystyle\Delta=\max_{s}\frac{C_{1}\mu_{s}^{6}k^{5}(w_{s}^{\text{max}})^{4}\log(|U|)^{4}\log(3k||R(s)||_{F}/\epsilon)}{|U|^{n/2}(w_{s}^{\text{min}})^{4}}$
(8)

and $C_{1}$ is a problem dependent positive constant. There exists $N_{0}$
which is $O(|U|^{\frac{n}{2}})$ and polynomial in
$\frac{1}{\delta},\frac{1}{\epsilon},k$ and relevant spectral properties of
the underlying MDP dynamics such that for samples $\geq N_{0}$, we can compute
the estimates $\bar{R}(s),\bar{P}(s,s^{\prime})$ such that w.p. $\geq
1-\delta$,
$||\bar{R}(s)-\hat{R}(s)||_{F}\leq\epsilon,||\bar{P}(s,s^{\prime})-\hat{P}(s,s^{\prime})||_{F}\leq\epsilon,\forall
s,s^{\prime}\in S$.

###### Proof.

For the simplicity of notation and emphasising key points of the proof, we
focus on orthogonal symmetric tensors with $n=3$. Guidelines for more general
cases are provided by the end of the proof.

We break the proof into three parts: Let policy $\pi$ satisfy
$\pi(\mathbf{u}|s)\geq\Delta$ Eq. 8. Let $\rho$ be the stationary distribution
of $\pi$ (exists by 3) and let
$N_{1}=\max_{s}\frac{1}{\rho(s)}\log\Big{(}\frac{12\sqrt{k}||R(s)||_{F}}{\epsilon}\Big{)}$.
From $N_{1}$ samples drawn from $\rho$ by following $\pi$, we estimate
$\bar{R}$, the estimated reward tensor computed by using Algorithm $1$ in
(Jain & Oh, 2014). We have by application of union bound along with Theorem
$1.1$ in (Jain & Oh, 2014) for each $s\in S$, w.p. $\geq
1-|U|^{-5}\log_{2}\Big{(}\frac{12\sqrt{k}\prod_{s}||R(s)||_{F}}{\epsilon}\Big{)}=p_{\epsilon}$,
$||\bar{R}(s)-\hat{R}(s)||_{F}\leq\epsilon/3,\forall s\in S$. We now provide a
boosting scheme to increase the confidence in the estimation of
$\hat{R}(\cdot)$ from $p_{\epsilon}$ to $1-\delta/3$. Let
$\eta=\frac{1}{2}\Big{(}p_{\epsilon}-\frac{1}{2}\Big{)}>0$ (for clarity of the
presentation we assume $p_{\epsilon}>\frac{1}{2}$ and refer the reader to
(Kearns et al., 1994) for the other more involved case). We compute $M$
independent estimates $\\{\bar{R}_{i},i\in\\{1..M\\}\\}$ for $\hat{R}(s)$ and
find the biggest cluster $\mathcal{C}\subseteq\\{\bar{R}_{i}\\}$ amongst the
estimates such that for any
$\bar{R}_{i},\bar{R}_{j}\in\mathcal{C},||\bar{R}_{i}-\bar{R}_{j}||_{F}\leq\frac{2\epsilon}{3}$.
We then output any element of $\mathcal{C}$. Intuitively as
$p_{\epsilon}>\frac{1}{2}$, most of the estimates will be near the actual
value $\hat{R}(s)$, this can be confirmed by using the Hoeffding Lemma(Kearns
et al., 1994). It follows that for
$M\geq\frac{1}{2\eta^{2}}\ln(\frac{3|S|}{\delta})$ the output of the above
procedure satisfies $||\bar{R}(s)-\hat{R}(s)||_{F}\leq\epsilon$ w.p. $\geq
1-\frac{\delta}{3|S|}$ for any particular $s$. Thus $MN_{1}$ samples from
stationary distribution are sufficient to ensure that for all $s\in S$, w.p.
$\geq 1-\delta/3$, $||\bar{R}(s)-\hat{R}(s)||_{F}\leq\epsilon$.

Secondly we note that $\hat{P}(s,s^{\prime})$ for any $s,s^{\prime}\in S$ is a
tensor whose entries are the parameters of a Bernoulli distribution. Under 2,
it can be seen as a latent topic model (Anandkumar et al., 2012) with $k$
factors,
$\hat{P}(s,s^{\prime})=\sum_{r=1}^{k}w_{s,s^{\prime},r}\otimes^{n}u_{s,s^{\prime},r}$.
Moreover it satisfies the conditions in Theorem $3.1$ (Anandkumar et al.,
2012) so that $\exists
N_{2}=\max_{s,s^{\prime}}\frac{1}{\rho(s)}N_{2}(s,s^{\prime})$ where each
$N_{2}(s,s^{\prime})$ is
$\mathcal{O}\Big{(}\frac{k^{10}|S|^{2}\ln^{2}(3|S|/\delta)}{\delta^{2}\epsilon^{{}^{\prime}2}}\Big{)}$
depending on the spectral properties of $\hat{P}(s,s^{\prime})$ as given in
the theorem and satisfies
$||\bar{u_{s,s^{\prime},r}}-u_{s,s^{\prime},r}||_{2}\leq\epsilon^{\prime}$ on
running Algorithm B in (Anandkumar et al., 2012) w.p. $\geq
1-\frac{\delta}{3|S|}$. We pick
$\epsilon^{\prime}=\frac{\epsilon}{7n^{2}k\mu_{s,s^{\prime}}^{2}(w_{s,s^{\prime}}^{\text{max}})^{2}}$
so that
$||\bar{P}(s,s^{\prime})-\hat{P}(s,s^{\prime})||_{F}\leq\epsilon,\forall
s,s^{\prime}\in S$. We filter off the effects of sampling from a particular
policy by using lower bound constraint in Eq. 8 and sampling
$\frac{N_{2}}{\Delta}$ samples.

Finally we account for the fact that there is a delay in attaining the
stationary distribution $\rho$ and bound the failure probability of
significantly deviating from $\rho$ empirically. Let
$\rho^{\prime}=\min_{s}\rho(s)$ and $t_{\text{mix},\pi}(x)$ represent the
minimum number of samples that need to drawn from the Markov chain formed by
fixing policy $\pi$ so that for the state distribution $\rho_{t}(s)$ at time
step $t=t_{\text{mix},\pi}(x)$ we have $TV(\rho_{t}-\rho)\leq x$ for any
starting state $s\in S$ where $TV(\cdot,\cdot)$ is the total variation
distance. We let the policy run for a burn in period of
$t^{\prime}=t_{\text{mix},\pi}(\rho^{\prime}/4)$. For a sample of $N_{3}$
state transitions after the burn in period, let $\bar{\rho}$ represent the
empirical state distribution. By applying the Hoeffding lemma for each state,
we get: $P(|\bar{\rho}(s)-\rho_{t^{\prime}}(s)|\geq\rho^{\prime}/4)\leq
2\exp\Big{(}\frac{-N_{3}\rho^{{}^{\prime}2}}{8}\Big{)}$, so that for
$N_{3}\geq\frac{8}{\rho^{{}^{\prime}2}}\ln\Big{(}\frac{6|S|}{\delta}\Big{)}$
we have w.p. $\geq 1-\frac{\delta}{3|S|}$,
$|\bar{\rho}(s)-\rho(s)|<\rho^{\prime}/2,\forall s\in S$.

Putting everything together we get with
$t_{\text{mix},\pi}(\rho^{\prime}/4)+\max\\{2MN_{1},\frac{2N_{2}}{\Delta},N_{3}\\}$
samples, the underlying reward and probability tensors can be recovered such
that w.p. $\geq 1-\delta$,
$||\bar{R}(s)-\hat{R}(s)||_{F}\leq\epsilon,||\bar{P}(s,s^{\prime})-\hat{P}(s,s^{\prime})||_{F}\leq\epsilon,\forall
s,s^{\prime}\in S$.

For extending the proof to the case of non-orthogonal tensors, we refer the
reader to use whitening transform as elucidated in (Anandkumar et al., 2014).
Likewise for asymmetric, higher order ($n>3$) tensors methods shown in (Jain &
Oh, 2014; Anandkumar et al., 2014, 2012) should be used. Finally for the case
of M-POMDP and M-ROMDP, the corresponding results for single agent POMDP and
ROMDP should be used, as detailed in (Azizzadenesheli, 2019; Azizzadenesheli
et al., 2016) respectively. ∎

###  A.2 Proof of Lemma 1

######  Lemma 1.

For transition tensor estimates satisfying
$||\bar{P}(s,s^{\prime})-\hat{P}(s,s^{\prime})||_{F}\leq\epsilon$, we have for
any given state and action pair $s,a$, the distribution over the next states
follows:
$TV(P^{\prime}(\cdot|s,a),P(\cdot|s,a))\leq\frac{1}{2}(|1-f|+f|S|\epsilon)$
where $\frac{1}{1+\epsilon|S|}\leq f\leq\frac{1}{1-\epsilon|S|}$. Similarly
for any policy $\pi$,
$TV(\bar{P}_{\pi}(\cdot|s),P_{\pi}(\cdot|s)),TV(\bar{P}_{\pi}(s^{\prime},a^{\prime}|s),P_{\pi}(s^{\prime},a^{\prime}|s))\leq\frac{1}{2}(|1-f|+f|S|\epsilon)$

###### Proof.

Let $\bar{P}(\cdot|s,a)$ be the next state probability estimates obtained from
the tensor estimates. We next normalise them across the next states to get the
(estimated)distribution $P^{\prime}(\cdot|s,a)=f\bar{P}(\cdot|s,a)$ where
$f=\frac{1}{\sum_{s^{\prime}}\bar{P}(s^{\prime}|s,a)}$. Dropping the
conditioning for brevity we have:

$\displaystyle TV(P^{\prime},P)$
$\displaystyle=\frac{1}{2}\sum_{s^{\prime}}|P(s^{\prime})-f\bar{P}(s^{\prime})|$
(9)
$\displaystyle\leq\frac{1}{2}(\sum_{s^{\prime}}|P(s^{\prime})-fP(s^{\prime})|+|fP(s^{\prime})-\bar{P}(s^{\prime})|)$
(10) $\displaystyle=\frac{1}{2}(|1-f|+f|S|\epsilon)$ (11)

The other two results follow using the definition of TV and Fubini’s theorem
followed by reasoning similar to above. ∎

###  A.3 Proof of Theorem 3

######  Theorem 3 (Error bound on policy evaluation).

Given a behaviour policy $\pi_{b}$ satisfying the conditions in Theorem 2 and
being executed for steps $\geq N_{0}$, we have that for any policy $\pi$ the
model based policy evaluation $Q_{\bar{P},\bar{R}}^{\pi}$ satisfies:

$\displaystyle|Q_{P,R}^{\pi}(s,a)-Q_{\bar{P},\bar{R}}^{\pi}(s,a)|$
$\displaystyle\leq(|1-f|+f|S|\epsilon)\frac{\gamma}{2(1-\gamma)^{2}}+\frac{\epsilon}{1-\gamma},\forall(s,a)\in
S\times U^{n}$ (12)

where $f$ is as defined in Lemma 1.

###### Proof.

Let $\bar{P},\bar{R}$ be the estimates obtained after running the procedure as
described in Theorem 2 with samples corresponding to error $\epsilon$ and
confidence $1-\delta$. We will bound the error incurred in estimation of the
action-values using $\bar{P},\bar{R}$. We have for any $\pi$ by using triangle
inequality

$\displaystyle|Q_{P,R}^{\pi}(s,a)-Q_{\bar{P},\bar{R}}^{\pi}(s,a)|$
$\displaystyle\leq|Q_{P,R}^{\pi}(s,a)-Q_{\bar{P},R}^{\pi}(s,a)|+|Q_{\bar{P},R}^{\pi}(s,a)-Q_{\bar{P},\bar{R}}^{\pi}(s,a)|$
(13)

where we use the subscript to denote whether actual or approximate values are
used for $P,R$ respectively. We first focus on the first term on the RHS of
Eq. 13. Let $R_{\pi}(s_{t})=\sum_{a_{t}}\pi(a_{t}|s_{t})R(s_{t},a_{t})$. We
use $P_{t,\pi}(\cdot|s)=(P_{\pi}(\cdot|s))^{t}$ to denote the state
distribution after $t$ time steps. Consider a horizon $h$ interleaving $Q$
estimate given by:

$\displaystyle Q_{h}^{\pi}(s,a)$
$\displaystyle=R(s_{t},a_{t})+\sum_{t=1}^{h-1}\gamma^{t}\mathbb{E}_{\bar{P}_{t,\pi}(\cdot|s)}[R_{\pi}(s_{t})]+\sum_{t=h}^{\infty}\gamma^{t}\mathbb{E}_{P_{t-h,\pi}(\cdot|s_{h})\cdot\bar{P}_{h,\pi}(s_{h}|s)}[R_{\pi}(s_{t})]$
(14)

Where $s_{0}=s,a_{0}=a$ and the first $h$ steps are unrolled according to
$\bar{P}_{\pi}$, the rest are done using the true transition $P_{\pi}$. We
have that:

$\displaystyle|Q_{P,R}^{\pi}(s,a)-Q_{\bar{P},\bar{R}}^{\pi}(s,a)|$
$\displaystyle=|Q_{0}^{\pi}(s,a)-Q_{\infty}^{\pi}(s,a)|\leq\sum_{h=0}^{\infty}|Q_{h}^{\pi}(s,a)-Q_{h+1}^{\pi}(s,a)|$
(15)

Each term in the RHS of the above can be independently bounded as :

$\displaystyle|Q_{h}^{\pi}(s,a)-Q_{h+1}^{\pi}(s,a)|=$
$\displaystyle\gamma^{h+1}\Big{|}\mathbb{E}_{\bar{P}_{h+1,\pi}(s_{h+1}|s)}\Big{[}\sum_{a_{h+1}}\pi(a_{h+1}|s_{h+1})Q_{\infty}^{\pi}(s_{h+1}.a_{h+1})\Big{]}$
(16)
$\displaystyle-\mathbb{E}_{P_{\pi}\bar{P}_{h,\pi}(s_{h+1}|s)}\Big{[}\sum_{a_{h+1}}\pi(a_{h+1}|s_{h+1})Q_{\infty}^{\pi}(s_{h+1}.a_{h+1})\Big{]}\Big{|}$
(17)

As the rewards are bounded we get the expression above is
$\leq\frac{1}{1-\gamma}\gamma^{h+1}TV(\bar{P}_{\pi}(s^{\prime},a^{\prime}|s),P_{\pi}(s^{\prime},a^{\prime}|s))$.
Finally using Lemma 1 we get
$\leq(\frac{1}{2}(|1-f|+f|S|\epsilon))\frac{\gamma^{h+1}}{1-\gamma}$. And
plugging in the original expression:

$\displaystyle|Q_{P,R}^{\pi}(s,a)-Q_{\bar{P},\bar{R}}^{\pi}(s,a)|\leq(|1-f|+f|S|\epsilon)\frac{\gamma}{2(1-\gamma)^{2}}$
(18)

Next the second term on the RHS of Eq. 13 can easily be bounded by
$\frac{\epsilon}{1-\gamma}$ which gives:

$\displaystyle|Q_{P,R}^{\pi}(s,a)-Q_{\bar{P},\bar{R}}^{\pi}(s,a)|$
$\displaystyle\leq(|1-f|+f|S|\epsilon)\frac{\gamma}{2(1-\gamma)^{2}}+\frac{\epsilon}{1-\gamma}$
(19)

∎

##  Appendix B Discussion

###  B.1 Relation to other methods

In this section we study the relationship between Tesseract and some of the
existing methods for MARL.

####  B.1.1 FQL

FQL (Chen et al., 2018) uses a learnt inner product space to represent the
dependence of joint Q-function on pair wise agent interactions. The following
result shows containment of FQL representable action-value function by
Tesseract :

######  Proposition 2.

The set of joint Q-functions representable by FQL is a subset of that
representable by Tesseract.

###### Proof.

In the most general form, any join Q-function representable by FQL has the
form:

$Q_{fql}(s,\mathbf{u})=\sum_{i=1:n}q_{i}(s,u_{i})+\sum_{i=1:n,j<i}\langle
f_{i}(s,u_{i}),f_{j}(s,u_{j})\rangle$ (20)

where $q_{i}:S\times U\to\mathbb{R}$ are individual contributions to joint
Q-function and $f_{i}:S\times U\to\mathbb{R}^{d}$ are the vectors describing
pairwise interactions between the agents. There are $n\choose 2$ pairs of
agents to consider for (pairwise)interactions. Let
$\mathscr{P}\triangleq{(i,j)}$ be the ordered set of agent pairs where $i>j$
and $i,j\in\\{1..n\\}$, let $\mathscr{P}_{k}$ denote the $k$th element of
$\mathscr{P}$. Define membership function
$m:\mathscr{P}\times\\{1..n\\}\to\\{0,1\\}$ as:

$\displaystyle m((i,j),x)=\begin{cases*}1&if $x=i\vee x=j$\\\
0&otherwise\end{cases*}$ (21)

Define the mapping $v_{i}:S\to\mathbb{R}^{|U|\times D}$ where $D=d{n\choose
2}+n$ and $v_{i,k}$ represents the $k$th column of $v_{i}$.

$\displaystyle
v_{i}(s)\triangleq\begin{cases*}v_{i}(s)[j,(k-1)d+1:kd]=f_{i}(s,u_{j})&if
$m(\mathscr{P}_{k},i)=1$\\\ v_{i}(s)[j,D-n+i]=q_{i}(s,u_{j})\\\
v_{i}(s)[j,k]=1&otherwise\end{cases*}$ (22)

We get that the tensors:

$Q_{fql}(s)=\sum_{k=1}^{D}\otimes^{n}v_{i,k}(s)$ (23)

Thus any $Q_{fql}$ can be represented by Tesseract, note that the converse is
not true ie. any arbitrary Q-function representable by Tesseract may not be
representable by FQL as FQL cannot model higher-order ($>2$ agent)
interactions. ∎

####  B.1.2 VDN

VDN (Sunehag et al., 2017) learns a decentralisable factorisation of the joint
action-values by expressing it as a sum of per agent utilities
$\hat{Q}=\oplus^{n}u_{i},i\in\\{1..n\\}$. This can be equivalently learnt in
Tesseract by finding the best rank one projection of $\exp(\hat{Q}(s))$. We
formalise this in the following result:

######  Proposition 3.

For any MMDP, given policy $\pi$ having $Q$ function representable by VDN ie.
$\hat{Q}^{\pi}(s)=\oplus^{n}u_{i}(s),i\in\\{1..n\\}$, $\exists v_{i}(s)\forall
s\in S$, the utility factorization can be recovered from rank one CP-
decomposition of $\exp(\hat{Q}^{\pi})$

###### Proof.

We have that :

$\displaystyle\exp(\hat{Q}^{\pi}(s))$ $\displaystyle=\exp(\oplus^{n}u_{i}(s))$
(24) $\displaystyle=\otimes^{n}\exp(u_{i}(s))$ (25)

Thus
$(\exp(u_{i}(s)))_{i=1}^{n}\in\operatorname*{arg\,min}_{v_{i}(s)}||\exp(\hat{Q}^{\pi}(s))-\otimes^{n}v_{i}(s)||_{F}\forall
s\in S$ and there always exist $v_{i}(s)$ that can be mapped to some
$u_{i}(s)$ via exponentiation. In general any Q-function that is representable
by VDN can be represented by Tesseract under an exponential transform (Section
3.2). ∎

###  B.2 Injecting Priors for Continuous Domains

Figure 6: Continuous actions task with three agents chasing a prey. Perturbing
Agent 2’s action direction by small amount $\theta$ leads to a small change in
the joint value.

We now discuss the continuous action setting. Since the action set of each
agent is infinite, we impose further structure while maintaining appropriate
richness in the hypothesis class of the proposed action value functions.
Towards this we present an example of a simple prior for Tesseract for
continuous action domains. WLOG, let $U\triangleq\mathbb{R}^{d}$ for each
agent $\in{1..n}$. We are now interested in the function class given by
$\mathcal{Q}\triangleq\\{Q:S\times U^{n}\to\mathbb{R}\\}$ where each $Q(s)$
$\triangleq\langle T(s,\\{||u^{i}||_{2}\\}),\otimes^{n}u^{i}\rangle$, here
$T(\cdot):S\times\mathbb{R}^{n}\to\mathbb{R}^{d^{n}}$ is a function that
outputs an order $n$ tensor and is invariant to the direction of the agent
actions, $\langle\cdot,\cdot\rangle$ is the dot product between two order $n$
tensors and $||\cdot||_{2}$ is the Euclidean norm. Similar to the discrete
case, we define $\mathcal{Q}_{k}\triangleq\\{Q:Q\in\mathcal{Q}\land
rank(T(\cdot))=k,\forall s\in S\\}$. The continuous case subsumes the discrete
case with $T(\cdot)\triangleq Q(\cdot)$ and actions encoded as one hot
vectors. We typically use rich classes like deep neural nets for $Q$ and $T$
parametrised by $\phi$.

We now briefly discuss the motivation behind the example continuous case
formulation: for many real world continuous action tasks the joint payoff is
much more sensitive to the magnitude of the actions than their directions,
i.e., slightly perturbing the action direction of one agent while keeping
others fixed changes the payoff by only a small amount (see Fig. 6).
Furthermore, $T_{\phi}$ can be arbitrarily rich and can be seen as
representing utility per agent per action dimension, which is precisely the
information required by methods for continuous action spaces that perform
gradient ascent w.r.t. $\nabla_{u^{i}}Q$ to ensure policy improvement. Further
magnitude constraints on actions can be easily handled by a rich enough
function class for $T$. Lastly we can further abstract the interactions
amongst the agents by learnable maps
$f_{\eta}^{i}(u^{i},s):\mathbb{R}^{d}\times S\to\mathbb{R}^{m}$, $m>>d$ and
considering classes $Q(s,\mathbf{u})\triangleq\langle
T(s,\\{||u^{i}||\\}),\otimes^{n}f_{\eta}^{i}(u^{i})\rangle$ where
$T(\cdot):S\times\mathbb{R}^{n}\to\mathbb{R}^{m^{n}}$.

###  B.3 Additional theoretical discussion

####  B.3.1 Selecting the CP-rank for approximation

While determining the rank of a fully observed tensor is itself NP-hard
(Hillar & Lim, 2013), we believe we can help alleviate this problem due to two
key observations:

  * •

The tensors involved in Tesseract capture dependence of transition and reward
dynamics on the action space. Thus if we can approximately identify (possibly
using expert knowledge) the various aspects in which the actions available at
hand affect the environment, we can get a rough idea of the rank to use for
approximation.

  * •

Our experiments on different domains (Section 5, Appendix C) provide evidence
that even when using a rank insufficient approximation, we can get good
empirical performance and sample efficiency. (This is also evidenced by the
empirical success of related algorithms like VDN which happen to be specific
instances under the Tesseract framework.)

##  Appendix C Additional experiments and details

###  C.1 StarCraft II

Figure 7: The 2c_vs_64zg scenario in SMAC.

In the SMAC bechmark(Samvelyan et al., 2019)
(https://github.com/oxwhirl/smac), agents can $\mathtt{move}$ in four cardinal
directions, $\mathtt{stop}$, take $\mathtt{noop}$ (do nothing), or select an
enemy to $\mathtt{attack}$ at each timestep. Therefore, if there are $n_{e}$
enemies in the map, the action space for each ally unit contains $n_{e}+6$
discrete actions.

####  C.1.1 Additional Experiments

(a) 3s5z Easy

(b) 2s_vs_1sc Easy

(c) 2c_vs_64zg Hard

(d) 5m_vs_6m Hard

(e) MMM2 Super Hard

(f) 27m_vs_30m Super Hard

(g) 6h_vs_8z Super Hard

(h) Corridor Super Hard

Figure 8: Performance of different algorithms on different SMAC scenarios:
TAC, QTRAN, QPLEX, COMA, HQL.

In addition to the baselines in main text Section 5, we also include 4 more
baselines: QTRAN (Son et al., 2019), QPLEX (Wang et al., 2020a), COMA
(Foerster et al., 2018) and HQL. QTRAN tries to avoid the issues arising with
representational constraints by posing the decentralised multi agent problem
as optimisation with linear constraints, these constraints are relaxed using
L2 penalties for tractability (Mahajan et al., 2019). Similarly, QPLEX another
recent method uses an alternative formulation using advantages for ensuring
the Individual Global Max (IGM) principle (Son et al., 2019). COMA is an
actor-critic method that uses a centralised critic for computing a
counterfactual baseline for variance reduction by marginalising across
individual agent actions. Finally, HQL uses the heuristic of differential
learning rates on top of IQL (Tan, 1993) to address problems associated with
decentralized exploration. Fig. 8 gives the average win rates of the baselines
on different SMAC scenarios across five random runs (with one standard
deviation shaded). We observe that Tesseract outperforms the baselines by a
large margin on most of the scenarios, especially on the super-hard ones on
which the exiting methods struggle, this validates the sample efficiency and
representational gains supported by our analysis. We observe that HQL is
unable to learn a good policy on most scenarios, this might be due to
uncertainty in the bootstrap estimates used for choosing the learning rate
that confounds with difficulties arising from non-stationarity. We also
observe that COMA does not yield satisfactory performance on any of the
scenarios. This is possibly because it does not utilise the underlying tensor
structure of the problem and suffers from a lagging critic. While QPLEX is
able to alleviate the problems arising from relaxing the IGM constraints in
QTRAN, it lacks in performance on the super-hard scenarios of Corridor and
6h_vs_8z.

####  C.1.2 Experimental Setup for SMAC

We use a factor network for the tensorised critic which comprises of a fully
connected MLP with two hidden layers of dimensions 64 and 32 respectively and
outputs a $r|U|$ dimensional vector. We use an identical policy network for
the actors which outputs a $|U|$ dimensional vector and a value network which
outputs a scalar state-value baseline $V(s)$. The agent policies are derived
using softmax over the policy network output. Similar to previous work
(Samvelyan et al., 2019), we use two layer network consisting of a fully-
connected layer followed by GRU (of 64-dimensional hidden state) for encoding
agent trajectories. We used Relu for non-linearities. All the networks are
shared across the agents. We use ADAM as the optimizer with learning rate
$5\times 10^{-4}$. We use entropy regularisation with scaling coefficient
$\beta=0.005$. We use an approximation rank of $7$ for Tesseract (’TAC’) for
the SMAC experiments. A batch size of 512 is used for training which is
collected across 8 parallel environments (additional setup details in Section
C.2). Grid search was performed over the hyper-parameters for tuning.

For the baselines QPLEX, QMIX, QTRAN, VDN, COMA, IQL we use the open sourced
code provided by their authors at https://github.com/wjh720/QPLEX and
https://github.com/oxwhirl/pymarl respectively which has hyper-parameters
tuned for SMAC domain. The choice for architecture make the experimental setup
of the neural networks used across all the baselines similar. We use a similar
trajectory embedding network as mentioned above for our implementations of HQL
and FQL which is followed by a network comprising of a fully connected MLP
with two hidden layers of dimensions 64 and 32 respectively. For HQL this
network outputs $|U|$ action utilities. For FQL, it outputs a $|U|+d$ vector:
first $|U|$ dimension are used for obtaining the scalar contribution to joint
Q-function and rest $d$ are used for computing interactions between agents via
inner product. We use ADAM as the optimizer for these two baselines. We use
differential learning rates of $\alpha=1\times 10^{-3},\beta=2\times 10^{-4}$
for HQL searched over a grid of $\\{1,2,5,10\\}\times
10^{-3}\times\\{1,2,5,10\\}\times 10^{-4}$. FQL uses the same learning rate
$5\times 10^{-4}$ with $d=10$ which was searched over set $\\{5,10,15\\}$.

The baselines use $\epsilon-$greedy for exploration with $\epsilon$ annealed
from $1.0\to 0.05$ over 50K steps. For super-hard scenarios in SMAC we extend
the anneal time to 400K steps. We use temperature annealing for Tesseract with
temperature given by $\tau=\frac{2T}{T+t}$ where $T$ is the total step budget
and $t$ is the current step. Similarly we use temperature
$\tau=\frac{4T}{T+3t}$ for super-hard SMAC scenarios. The discount factor was
set to $0.99$ for all the algorithms.

Experiment runs take 1-5 days on a Nvidia DGX server depending on the size of
the StarCraft scenario.

###  C.2 Techniques for stabilising Tesseract critic training for Deep-MARL

  * •

We used a gradient normalisation of $0.5$. The parameters exclusive to the
critic were separately subject to the gradient normalisation, this was done
because the ratio of gradient norms for the actor and the critic parameters
can vary substantially across training.

  * •

We found that using multi-step bootstrapping substantially reduced target
variance for Q-fitting and advantage estimation (we used the advantage based
policy gradient
$\int_{S}\rho^{\pi}(s)\int_{\mathbf{U}}\nabla\pi_{\theta}(\mathbf{u|s})\hat{A}^{\pi}(s,\mathbf{u})d\mathbf{u}ds$
(Sutton & Barto, 2011)) for SMAC experiments. Specifically for horizon T, we
used the Q-target as:

$\displaystyle Q_{target,t}=\sum_{k=1}^{T-t}\lambda^{k}g_{t,k}$ (26)
$\displaystyle g_{t,k}=R_{t}+\gamma R_{t+1}+...+\gamma^{k}V(s_{t+k})$ (27)

and similarly for value target. Likewise, the generalised advantage is
estimated as:

$\displaystyle\hat{A}_{t}=\sum_{k=0}^{T-t}(\gamma\lambda)^{k}\delta_{t+k}$
(28)
$\displaystyle\delta_{t}=R_{t}+\gamma\hat{Q}(s_{t+1},\mathbf{u}_{t+1})-V(s_{t})$
(29)

Where $\hat{Q}$ is the tensor network output and the estimates are normalized
by the accumulated powers of $\lambda$. We used $T=64,\gamma=0.99$ and
$\lambda=0.95$ for the experiments.

  * •

The tensor network factors were squashed using a sigmoid for clipping and were
scaled by $2.0$ for SMAC experiments. Additionally, we initialised the factors
according to $\mathcal{N}(0,0.01)$ (before applying a sigmoid transform) so
that value estimates can be effectively updated without the gradient
vanishing.

  * •

Similarly, we used clipping for the action-value estimates $\hat{Q}$ to
prevent very large estimates:

$\displaystyle clip(\hat{Q}_{t})=min\\{\hat{Q}_{t},R_{max}\\}$ (30)

we used $R_{max}=40$ for the SMAC experiments.

(a) Ablation on stabilisation techniques

(b) Ablation on rank

Figure 9: Variations on Tesseract

We provide the ablation results on the stabilisation techniques mentioned
above on the 2c_vs_64zg scenario in Fig. 9(a). The plot lines correspond to
the ablations: TAC-multi: no multi-step target and advantage estimation, TAC-
clip: no value upper bounding/clipping, TAC-norm: no separate gradient norm,
TAC-init: no initialisation and sigmoid squashing of factors. We observe that
multi-step estimation of target and advantage plays a very important role in
stabilising the training, this is because noisy estimates can adversely update
the learn factors towards undesirable fits. Similarly, proper initialisation
plays a very important role in learning the Q-tensor as otherwise a larger
number of updates might be required for the network to learn the correct
factorization, adversely affecting the sample efficiency. Finally we observe
that max-clipping and separate gradient normalisation do impact learning,
although such effects are relatively mild.

We also provide the learning curves for Tesseract as the CP rank of
Q-approximation is changed, Fig. 9(b) gives the learning plots as the CP-rank
is varied over the set $\\{3,7,11\\}$. Here, we observe that approximation
rank makes little impact on the final performance of the algorithm, however it
may require more samples in learning the optimal policy. Our PAC analysis
Theorem 2 also supports this.

###  C.3 Tensor games:

We introduce tensor games for our experimental evaluation. These games
generalise the matrix games often used in $2$-player domains. Formally, a
tensor game is a cooperative MARL scenario described by tuple $(n,|U|,r)$ that
respectively defines the number of agents (dimensions), the number of actions
per agent (size of index set) and the rank of the underlying reward tensor
Fig. 10. Each agent learns a policy for picking a value from the index set
corresponding to its dimension. The joint reward is given by the entry
corresponding to the joint action picked by the agents, with the goal of
finding the tensor entry corresponding to the maximum reward. We consider the
CTDE setting for this game, which makes it additionally challenging. We
compare Tesseract (TAC) with VDN, QMIX and independent actor-critic (IAC)
trained using Reinforce (Sutton et al., 2000). Stateless games provide are
ideal for isolating the effect of an exponential blowup in the action space.
The natural difficulty knobs for stateless games are $|n|$ and $|U|$ which can
be increased to obtain environments with large joint action spaces.
Furthermore, as the rank $r$ increases, it becomes increasingly difficult to
obtain good approximations for $\hat{T}$.

Figure 10: Tensor games example with $3$ agents ($n$) having $3$ actions each
($a$). Optimal joint-action (a1, a3, a1) shown in orange.

(a) n:5 |U|:10 r:8

(b) n:6 |U|:10 r:8

(c) Dependence on approximation rank

(d) Effects of approximation

Figure 11: Experiments on tensor games.

Fig. 11(a) Fig. 11(b) present the learning curves for the algorithms for two
game scenarios, averaged over 5 random runs with game parameters as mentioned
in the figures. We observe that Tesseract outperforms the other algorithms in
all cases. Moreover, while the other algorithms find it increasingly difficult
to learn good policies, Tesseract is less affected by this increase in action
space. As opposed to the IAC baseline, Tesseract quickly learns an effective
low complexity critic for scaling the policy gradient. QMIX performs worse
than VDN due to the additional challenge of learning the mixing network.

In Fig. 11(c) we study the effects of increasing the approximation rank of
Tesseract ($k$ in decomposition $\hat{Q}(s)\approx
T=\sum_{r=1}^{k}w_{r}\otimes^{n}g_{\phi,r}(s^{i}),i\in\\{1..n\\},$) for a
fixed environment with $5$ agents, each having $10$ actions and the
environment rank being $8$. While all the three settings learn the optimal
policy, it can be observed that the number of samples required to learn a good
policy increases as the approximation rank is increased (notice delay in ’Rank
8’, ’Rank 32’ plot lines). This again is in-line with our PAC results, and
makes intuitive sense as a higher rank of approximation directly implies more
parameters to learn which increases the samples required to learn.

We next study how approximation of the actual $Q$ tensors affects learning. In
Fig. 11(d) we compare the performance of using a rank-$2$ Tesseract
approximation for environment with $5$ agents, each having $10$ actions and
the environment reward tensor rank being varied from $8$ to $128$. We found
that for the purpose of finding the optimal policy, Tesseract is fairly stable
even when the environment rank is greater than the model approximation rank.
However performance may drop if the rank mismatch becomes too large, as can be
seen in Fig. 11(d) for the plot lines ’E_rank 32’, ’E_rank 128’, where the
actual rank required to approximate the underlying reward tensor is too high
and using just $2$ factors doesn’t suffice to accurately represent all the
information.

####  C.3.1 Experimental setup for Tensor games

For tensor game rewards, we sample $k$ linearly independent vectors
$u_{r}^{i}$ from $|\mathcal{N}(0,1)^{|U|}|$ for each agent dimension
$i\in\\{1..n\\}$. The reward tensor is given by
$T=\sum_{r=1}^{k}w_{r}\otimes^{n}u_{r}^{i},i\in\\{1..n\\}$. Thus $T$ has
roughly $k$ local maxima in general for $k<<|U|^{n}$. We normalise $\hat{T}$
so that the maximum entry is always $1$.

All the agents use feed-forward neural networks with one hidden layer having
$64$ units for various components. Relu is used for non-linear activation.

The training uses ADAM (Kingma & Ba, 2014) as the optimiser with a $L2$
regularisation of $0.001$. The learning rate is set to $0.01$. Training
happens after each environment step.

The batch size is set to $32$. For an environment with $n$ agents and $a$
actions available per agent we run the training for $\frac{a^{n}}{10}$ steps.

For VDN (Sunehag et al., 2017) and QMIX(Rashid et al., 2018) the
$\epsilon$-greedy coefficient is annealed from $0.9$ to $0.05$ at a linear
rate until half of the total steps after which it is kept fixed.

For Tesseract (’TAC’) and Independent Actor-Critic (’IAC’) we use a learnt
state baseline for reducing policy gradient variance. We also add entropy
regularisation for the policy with coefficient starting at $0.1$ and halved
after every $\frac{1}{10}$ of total steps.

We use an approximation rank of $2$ for Tesseract (’TAC’) in all the
comparisons except Fig. 11(c) where it is varied for ablation.