{'fraction_non_alphanumeric': 0.03992595397366318, 'fraction_numerical': 0.013757415120535152, 'mean_word_length': 4.501041425595927, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reinforcement Learning in Factored Action Spaces using Tensor Decompositions

We present an extended abstract for the previously published work TESSERACT [Mahajan et al., 2021], which proposes a novel solution for Reinforcement Learning (RL) in large, factored action spaces using tensor decompositions. The goal of this abstract is twofold: (1) To garner greater interest amongst the tensor research community for creating methods and analysis for approximate RL, (2) To elucidate the generalised setting of factored action spaces where tensor decompositions can be used. We use cooperative multi-agent reinforcement learning scenario as the exemplary setting where the action space is naturally factored across agents and learning becomes intractable without resorting to approximation on the underlying hypothesis space for candidate solutions.


Introduction
Reinforcement learning (RL) has experienced tremendous advancements in recent years towards coming up with agents which can solve complex tasks and demonstrate generally performant intelligent behaviour [Silver et al., 2017, Vinyals et al., 2019, DeepMind-OEL et al., 2021. One dimension in which task complexity in RL has seen big growth is that of size of the action space over which an agent (or a group of agents) have to make decisions. Thus, a lot of research efforts are being made towards creating approximation methods for learning in large action spaces which would otherwise be unnameable for classical methods. This has set the stage for development of innovative methods, analysis and addressal of new challenges which arise from the above approximation. Factorisation of the action space is one such strategy for overcoming computational intractability and learning approximately optimal policies. Factorisation involves decomposing/partitioning the action space into smaller sets so that RL can be done tractably on these smaller sets. This naturally provides a multi-agent perspective to the problem as each factored component can be seen as an agent working jointly with other such agent towards maximising the expected cumulative rewards. Factorisation can be imposed on an RL problem for tractability or it may arise from the problem/environment constraints such as communication limitations, partial observability and multi-agentness. In this work we will be focussing on product based factorisation of the action space U that can be decomposed as cross product over action sets {U i } n 1 such that U = n i=1 U i . This form of decomposition naturally occurs in many application like robotics where action space is multi-dimensional (ex. a single robot has a joint-policy for locomotion and communication) and swarm roboticsBuşoniu et al. [2010] where each robot signifies a factor in decomposition.
We will next see how TESSERACT [Mahajan et al., 2021] utilises the structure present in the above factored action spaces using a novel tensorised form of the Bellman equation. This novel form allows for creating algorithms for RL which can provide exponential gain in sample efficiency in the number of factors under the PAC framework. Further it opens up opportunities for using various forms of tensor decomposition for approximation based on the problem structure.

Background
Factored action spaces We consider the simplest setting for factored action space (FAS) where the state of the system is completely observed and is available for deciding an action from each component in the action space factorisation (we refer to this as an 'agent' from hereon, implying the factored problem has n agents, one for each factor). We refer the reader to Mahajan et al. [2021] for the more general scenarios. For the above scenario, a FAS can be modelled using a multi-agent Markov Decision Process (MMDP) which is defined as the tuple: S, U, P, r, n, γ . Here, S is the state space of the environment with joint action space U = U n . Note that we have assumed without loss of generality that each factor/agent admits the same set of actions U ie. U i = U ∀i ∈ A ≡ {1, ..., n}. A policy in FAS is the mapping π : S → P(U) which gives a distribution over the joint action space given a state. At each time step t, an action u i ∈ U is chosen for every agent i ∈ A using π which forms the joint action u ∈ U ≡ U n . The joint action-value function given a policy π is defined as: Q π (s t , u t ) = E st+1:∞,ut+1:∞ ∞ k=0 γ k r t+k |s t , u t . In RL, the goal is to find the optimal policy π * corresponding to the optimal action value function Q * .
Reinforcement Learning Methods RL methods come in a wide variety, but can fundamentally be classified as model based methods and model free methods. Model based methods typically estimate the underlying dynamics of the MDP (P, r) whereas model free methods implicitly account for them. Another important dimension of variance is the algorithmic setup used for learning which differentiates the methods as policy based, value based or actor-critic (a hybrid of previous two). Sutton and Barto [2011] gives a comprehensive overview of these methods. Value-based and actorcritic methods which can attributed most of the recent progress in RL for large action spaces, both rely on an estimator for the action-value function Q π given a target policy π. Q π satisfies the (scalar)-Bellman expectation equation: Q π (s, u) = r(s, u) + γE s ,u [Q π (s , u )], which can equivalently be written in vectorised form as: where R is the mean reward vector of size S, P π is the transition matrix. The operation on RHS T π (·) R + γP π (·) is the Bellman expectation operator for the policy π. However, Eq. (1) doesn't expose the structure present in FAS problems, in Section 3 we discuss how TESSERACT generalises the Bellman expectation equation (and analogously the Bellman optimality equation) to a novel tensor form suitable for sample efficient learning in FAS. Tensor Decomposition Tensors are high dimensional analogues of matrices and tensor methods generalize matrix algebraic operations to higher orders. In the rest of this paper, we use· to denote tensors. Formally, an order n tensorT has n index sets I j , ∀j ∈ {1..n} and has elements T (e), ∀e ∈ × I I j taking values in a given set S, where × is the set cross product and we denote the set of index sets by I. Each dimension {1..n} is also called a mode. An elegant way of representing tensors and associated operations is via tensor diagrams as shown in Fig. 1. Tensor contraction generalizes the concept of matrix with matrix multiplication. For any two ten-sorsT 1 andT 2 with I ∩ = I 1 ∩ I 2 we define the contraction operation asT =T 1 T 2 witĥ T (e 1 , e 2 ) = e∈× I ∩ IjT 1 (e 1 , e) ·T 2 (e 2 , e), e i ∈ × I i \I∩ I j . 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 andBader, 2009, Janzamin et al., 2020], 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 terms in the sum is called the CP-rank. Formally, a tensorT can be factored using a (rank-k) CP decomposition into a sum of k vector outer products (denoted by ⊗), as, .n}, ||u i r || 2 = 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 can be found in Mahajan et al. [2021]. Given a multi-agent problem G = S, U, P, r, n, γ , let Q {Q : S × U n → R} be the set of realvalued functions on the state-action space. We are interested in the curried Barendregt [1984] form Q : S → U n → R, Q ∈ 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. 2 gives the equation whereÎ is the identity tensor of size |S| × |S| × |S|. The dependence of the action-value tensorQ π and the policy tensorÛ π on the policy is denoted by superscripts π. 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. There is an edge for each factor in product decomposition/agent i ∈ A in the corresponding nodesQ π ,Û π ,R,P with the index set U i .

TESSERACT Algorithms
Algorithm 1 Model-based Tesseract 1: Initialise rank k, π = (π i ) n 1 andQ 2: Initialise model parametersP ,R 3: Learning rate ← α,D ← {} 4: for each episodic iteration i do 5: UpdateP ,R using CP-Decomposition on moments from D 8: for each internal iteration j do 9:Q ← T πQ 10: end for 11: Improve π usingQ 12: end for 13: Return π,Q It turns out that, constraining the underlying tensors for dynamics and rewards (P ,R) is sufficient to bound the CP-rank ofQ (Theorem 1, Mahajan et al. [2021]). From this insight, a model-based RL version for TESSERACT can be constructed in Algorithm 1 (reproduced here from Mahajan et al. [2021]). The algorithm proceeds by estimating the underlying MDP dynamics using the sampled trajectories obtained by executing the behaviour policy π = (π i ) n 1 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 π 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 -greedy (for Q derived policy), policy gradients (parametrized policy) Sutton and Barto [2011] For large state spaces, where storage and planning using model parameters is computationally difficult, Mahajan et al. [2021] provide a model free version of the approach, details of which can be found in Appendix A with a sample of empirical results from the original paper in Appendix C. We next briefly revisit the main theoretical results from TESSERACT. Additional related works can be found in Appendix D.

Analysis
Under mild assumptions on the underlying dynamics of the FAS problem (see Appendix B for these along with additional constants appearing in Theorem 2), we have that the following results hold, where k 1 , k 2 are upper bounds on CP rank of the reward and transition tensor respectively (proofs for which can be found in the original text, Mahajan et al. [2021]): Theorem 1. For a finite FAS the action-value tensor satisfies rank(Q π (s)) ≤ k 1 +k 2 |S|, ∀s ∈ S, ∀π.
The next PAC result empowers Algorithm 1 by lower bounding the number of samples required to infer the reward and state transition dynamics for finite MDPs with high probability using sufficient approximate rank k ≥ k 1 , k 2 : Theorem 2 (Model based estimation ofR,P error bounds). Given any > 0, 1 > δ > 0, for a policy π with the policy tensor satisfying π(u|s) ≥ ∆, where n 2 ) and polynomial in 1 δ , 1 , k and relevant spectral properties of the underlying MDP dynamics such that for samples ≥ N 0 , we can compute the estimatesR(s),P (s, s ) such that w.p.
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 factored action-space MDP, Algorithm 1 requires only O(|U | 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. This is addressed in the next result, which bounds 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 π b satisfying the conditions in Theorem 2 and executed for steps ≥ N 0 , for any policy π the model based policy evaluation Q π P ,R satisfies:

Conclusions & Future Work
In this extended abstract we discussed the main ideas introduced in TESSERACT [ Mahajan et al., 2021], a novel framework utilising the insight that the action value function for RL problems with factored action space 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 also revisited the main theoretical results of TESSERACT.

A Model free Tesseract
For large state spaces where storage and planning using model parameters is computationally difficult (they are O(kn|U ||S| 2 ) in number), Mahajan et al. [2021] 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. 3 gives the general network architecture for this approach and Algorithm 2 the associated pseudo-code. Each agent in Fig. 3 has a policy network parameterized by θ which is used to take actions in a decentralised manner. The observations of the individual agents along with the actions are fed through representation function g φ whose output is a set of k unit vectors of dimensionality |U | corresponding to each rank. The output g φ,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 tensorQ(s) by the centralized critic is: 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 θ are merged with φ. 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 T, A where A = ⊗ n u i (This reduces to indexing using joint action in Eq. (2) for discrete spaces). More representational capacity can be added to the network by creating an abstract representation for actions using f η , which can be any arbitrary monotonic function (parametrised by η) of vector output of size m ≥ |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 = ⊗ n f η (u i ) and the agents also carry a copy of f η during the execution phase. Furthermore, the inner product T, A can be computed efficiently using the property 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 and Barto [2011]: where φ − , η − are target parameters. Policy updates involve gradient ascent w.r.t. to the policy parameters θ on the objective J θ = S ρ π (s) U π θ (u|s)Q π (s, u)duds. 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 individualglobal 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 Π k .

B Assumptions used for analysis
The following assumptions are used in TESSERACT [Mahajan et al., 2021] which we reproduce here for reference: Assumption 1. For the given MMDP G = S, U, P, r, n, γ , the reward tensorR(s), ∀s ∈ S has bounded rank k 1 ∈ N.
Intuitively, a small k 1 in Assumption 1 implies that the reward is dependent only on a small number of intrinsic factors characterising the actions.
Intuitively a small k 2 in Assumption 2 implies that only a small number of intrinsic factors characterising the actions lead to meaningful change in the joint state. Assumption 1-2 always hold for a finite MMDP as CP-rank is upper bounded by Π n j=1 |U j |, where U j are the action sets. Assumption 3. The underlying MMDP is ergodic for any policy π so that there is a stationary distribution ρ π .
Next, we define coherence parameters, which are quantities of interest for our theoretical results: for reward decompositionR(s) = r w r,s ⊗ n v r,i,s , let µ s = √ n max i,r,j |v r,i,s (j)|, w max s = max i,r w r,s , w min s = min i,r w r,s . Similarly define the corresponding quantities for µ s,s , w max s,s , w min s,s for transition tensorsP (s, s ). 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).

C Experiments
In this section we reproduce the main empirical results for TESSERACT on the StarCraft domain for the decentralised multi agent scenario. Complete experimental analysis and setup details can be found in the original paper. The experiments use the model-free version of TESSERACT (Algorithm 2).   [Chen et al., 2018], and IQL [Tan, 1993], the latter being algorithms specifically designed for cooperative decentralised multi agent reinforcement learning. 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. 4 gives the win rate of the different algorithms averaged across five random runs. Fig. 4(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. 4(d), TESSERACT, QMIX, and VDN learn effective policies, similar behavior occurs in the heterogeneous scenarios of 3s5z Fig. 4(a) and MMM2Fig. 4(e) with the exception of VDN for the latter. In 2s vs 1sc in Fig. 4(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. 4(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. 4(g) and Corridor Fig. 4(h) which require careful exploration, TESSERACT is the only algorithm which is able to find a good policy. It is observed 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].

D 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. [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. [2020] 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 and 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], signal processing Sidiropoulos et al. [2017], deep learning and computer vision Panagakis et al. [2021]. They provide 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  and have also been used for multi-task learning and domain adaptation . 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 singleagent 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.