Towards a Better Understanding of Learning with Multiagent Teams

1 Introduction

In Multiagent Systems (MAS), the study of how multiple agents work together in groups or teams has been a significant area of research for several decades [Pollack, 1986; Radke et al., 2022]. In settings with individual learning agents, teams are typically defined so that agents learn from their individual experiences but share rewards to varying extents [Baker et al., 2019; McKee et al., 2020]. In this paper, we investigate how teams and different team structures influence and guide the learning process of individual agents.

We consider mixed-motive stochastic games, where agent interests are sometimes aligned and sometimes in conflict, often to varying extents [Dafoe et al., 2020]. Past work studying cooperation in mixed-motive domains typically assumes that a fully cooperative population (i.e., a single team) achieves the best results [Yang et al., 2020; Gemp et al., 2022]. However, recent work has indicated that non-fully cooperative populations can learn significantly more productive joint policies than a fully cooperative population [Durugkar et al., 2020; Radke et al., 2023]. Even though a larger team has more agents at its disposal to perform tasks, smaller teams can achieve better global outcomes because agents learn more effective joint policies. While this phenomenon has been observed across multiple domains, the underlying reasons have not been fully explored or understood.

∗Contact Author

This paper provides theoretical groundwork as to why, and under which conditions, smaller teams outperform larger teams. We focus on two areas of how teams impact learning: 1) how the introduction of teammates initially improves the ability for individual agents to learn about valuable areas of the state space (Section 4), and 2) how the credit-assignment problem (i.e. learning the value of taking a particular action) becomes more challenging as a team gets larger (Section 5).

Thus, this paper emphasizes the importance of teams and team structures to shape the learning problems and reward functions while agents learn: teams can help improve agents' learning processes to a point, but sub-optimal team structures can hinder learning. This paper provides some theoretical underpinnings to help understand the impacts of teams on the learning processes of individual agents. We make the following contributions:

• We theoretically explore how teams can reduce the complexity of learning problems in certain environments.
• We show how sub-optimal team structures increase the difficulty for agents to identify valuable experiences, expanding previous work [Arumugam et al., 2020] to the multiagent team setting.
• We validate our theory empirically with widely used multiagent testbeds.

2 RelatedWork

Research on multiagent teams with individual learners includes frameworks where agents share mental models or plans [Pollack, 1986; Pollack, 1990; Tambe, 1997], ad hoc teamwork [Stone et al., 2010], and multiagent reinforcement learning (MARL) teams with shared rewards [Radke et al., 2022; Radke et al., 2023]. InMARLwith individual learners, algorithms to improve decentralized learning from a shared team reward have defined multiple learning rates [Matignon et al., 2007] or regulated replay buffers [Palmer et al., 2019]. While the behavior of reward-sharing agents is often studied, the underlying impact on the learning process and environment, analyzed in this work, are often overlooked.

Groups sharing a team reward can cause a credit assignment problem - where it may be difficult to determine the value of actions on an objective (i.e., reward for specific actions). In cooperative settings with control over all agents, an existing approach to reduce credit assignment issues and achieve effective teamwork is the centralized training decentralized execution (CTDE) methodology, where value decomposition algorithms are effective [Rashid et al., 2020]. During a centralized training phase, value decomposition learns to distribute team (or sub-team [Phan et al., 2021]) reward among it's members to guide learning towards favorable policies. This methodology relies on a fully cooperative population, access to agents' internal learning algorithms, and a separate training phase. Our work focuses on mixedmotive environments with individual learners where these assumptions do not hold and a cooperative population is often assumed to achieve the best result [Yang et al., 2020; Dong et al., 2021].

In single agent settings, ideas like reward shaping have been well studied. Reward shaping adds extra rewards to help agents discover valuable state-action pairs; however, this typically follows a fixed reward redistribution policy in stationary environments [Ng et al., 1999; Wiewiora et al., 2003]. RUDDER [Arjona-Medina et al., 2019] uses supervised learning as a way to dynamically redistribute reward to reward-causing state-action pairs in an agent's memory. Options [Sutton et al., 1999; Konidaris and Barto, 2007] and Hierarchical RL (HRL) [Nachum et al., 2018; G¨urtler et al., 2021] create artificial sub-goals in the environment (instead of in memory) to guide an action policy towards potentially valuable state-action pairs as it learns. In curriculum learning, agents train with increasingly complex tasks to discover valuable state-action pairs [Wang et al., 2021].

Many of these single-agent approaches do not directly translate to the nonstationary domains of MARL. Our work demonstrates how, under certain conditions, teams have emergent features that influence the learning process similarly to the aforementioned single-agent frameworks. We show how teammates redistribute reward to valuable rewardcausing state-action pairs. This rate of redistribution is not fixed, but rather the reward signal increases in strength as agents learn to act and obtain more reward (similar to RUDDER and curriculum learning). We draw comparisons with these ideas to highlight how research with teams has ties to several fundamental problems across RL.

3 Background

A typical environment in which multiagent teams operate is a stochastic game: a generalized Markov Decision Process (MDP) with multiple agents [Shapley, 1953]. We model our base environment as a stochastic game G = ⟨N, {S}i∈N, {A}i∈N, {R}i∈N, P, γ, Σ⟩. N is our set of agents with size N ∈ N that learn online from experience and S the state space, observable by all agents. We use si ∈ Si to define a single state observed by agent i in the set of states i observes. A = A1 × . . . × AN is the joint action space for all agents where Ai is the action space of agent i and a ∈ A. R = R1 × . . . × RN is the joint reward space for all agents where Ri is the reward function of agent i, defined as Ri : S × A × S ↦→ R, a real-numbered reward for taking an action in a state and transitioning to the next state. We assume all agents have identical (deterministic) reward functions (i.e., receive the same reward for the same behavior). The transition function, P : S × A ↦→ ∆(S), maps a joint state and joint action into a next joint state with some probability and γ is the discount factor. Σ represents the policy space of all agents and the policy of agent i is πi : S ↦→ Ai, which specifies an action that agent i should take in an observed state. 1 πN = π1 × . . . × πN denotes the joint policy of N agents.

We assume agents are independent learners and learn policies πi based on their individual observations si and actions ai, but the rewards that they receive can depend on the actions of others. Bold notation represents joint states st and joint actions at of all agents. In particular, at each timestep, t, agent i receives reward Rt i (st , at , st+1 ). Learning agents seek to learn policies which maximize their sum of discounted future rewards, Vi = ∑∞t=0 γ tRt i (st , at , st+1 ).

3.1 Model of Teams

We define a team as a subset of individual learning agents that share common interest for team-level goals through a shared reward. Given a population, multiple teams with different preferences and interests may co-exist [Mathieu et al., 2001]; real-world examples include work teams within the same company, position teams that make up a sports team, or faculties within a university. Team structure denotes the number and size of teams in a population. Our theory depends on all N agents and scales to environments with multiple teams; thus, we use "team structure" to denote "team size" when considering a single team to remain general. We refer to the set of all teams as T , the set of teams agent i belongs to as Ti, and a specific team that agent i belongs to as Ti ∈ Ti. For readability, we define the size of a team |Ti| = n.

Agents on a team continue to observe only their individual state si and take individual actions ai but share rewards through a shared team reward function TRi[n], isolating the team infrastructure to only the reward signal. Replacing Ri in agents' optimization problems' with TRi[n], agents learn to maximize the sum of discounted future team rewards. Any deterministic function for reward-sharing can define TRi[n] as long as every agent in a team gets some amount of the team's reward. We use:

where teammates share their rewards equally to be consistent with past work [Baker et al., 2019; Radke et al., 2022].

Much of our theory relies on features of agent or team trajectories. We define τi = {(s1i , a1i ), (s2i , a2i ), · · · , (sHi , aHi )} to be a trajectory of individual state-action pairs generated by agent i following πi over H timesteps. A joint policy for Ti is the collection of individual behavior policies of all n agents in Ti, πTi . A joint trajectory for team Ti, τTi , is the collection of joint state-action pairs generated by agents in Ti. We are required to index trajectories in three ways: first τ tTi = (stTi , atTi ), second τ 1:t-1 Ti = {(s1Ti , a1Ti ), · · · , (st-1 Ti , at-1 Ti )}, and third τ -t Ti is the H-timestep trajectory without timestep t. Let Z(τTi ) be a random variable denoting the team return obtained after team Ti completes the joint trajectory τTi following their individual policies that compose πTi . We define ZTi ≜ Z(sTi , aTi ) to be a random variable denoting the team reward observed at the joint state of all teammates sTi having taken joint action aTi and following their individual policies thereafter. Note that sTi is dependent on all N agents in the system by definition of stochastic games.

1 We can also allow for randomized policies.

4 Identifying Valuable State-Action Pairs

We study the most restrictive case where teammates have no communication or coordination mechanisms and focus only on features of the team reward function. By the definition of a stochastic game, rewards obtained from the environment depend on the joint states and actions of all agents. Thus, there can exist reward-causing state-action pairs - experiences that may not yield reward themselves, but allow reward to be obtained elsewhere in the environment [Arjona-Medina et al., 2019]. Identifying these pairs can be challenging, since independently each state may provide little or no reward.

We want to understand when teams of agents can leverage these reward-causing state-action pairs. We distinguish between the direct reward an agent receives from the environment when transitioning into their own observed state st+1 i , Rt i (st , at , st+1 i ), and the team reward, TRi[n]. We identify an environmental property where the team reward signal is stronger than the individual reward signal (i.e., E [Rt i (st , at , st+1 i )] < E [TRi[n] ]) because of the rewardcausing state-action pair effect. This signal causes agents to become more attracted to, and thus learn to execute, rewardcausing state-action pairs more often.

Consider the two state environment shown in Figure 1. This environment can support any number of agents (N ≥ 1), and the state transitions and rewards depend on the joint action of all N agents. For simplicity, we assume the existence of only one team (i.e., n = N). A stochastic game (n = 2) diagram is given in Figure 5 in Appendix A. 2 There exists two physical states that agents individually observe: sc and sr. Agents have two actions: stay at their current state (a0) or move to the other state (a1). The "c" in sc corresponds to a binary signal (explained below) and "r" in sr refers to a reward state.

There is never an environmental reward given to agent i for transitioning to sc, thus Rt i (st , at , st+1 c ) = 0. However, any agent (regardless of team affiliation) visiting sc changes a binary signal c that allows reward to be collected at sr. Thus, the possible rewards (dependent on c) given to any agent in sr are Rt i (st , at , st+1 r ) = {0, r}, where r > 0. When agent i individually transitions to sr, their reward (before sharing with their team) is Rt i (st , at , st+1 r ) = 0 if c = 0, and their reward is Rt i (st , at , st+1 r ) = r if c = 1. Once reward is consumed at sr, c has to be reset by visiting sc again. Thus, the reward-causing state-action pair in this environment is to "visit sc", causing a reward to be obtained when visiting sr. With teams, the rewards given to individual agents are transformed into the team reward by Equation 1 for agents to learn.

2 https://cs.uwaterloo.ca/∼dtradke/pdfs/ijcai23 teamsapdx.pdf

We can generalize features of this environment to support theory about how teams impact learning under certain conditions. In doing so, our theory is applicable to any multiagent environment where the following assumptions hold:

1. Agents' policies are initialized at random and fully explore the state space (in the limit).
2. The environment yields mid-episode rewards (not only at termination state) and any agent can collect rewards.
3. Executing a reward-causing state-action pair returns a minimum reward in the environment if the agent is not in a team (e.g., visiting sc returns a reward of 0, the minimum reward of the environment in Figure 1).

Theorem 1. There exists an environment where increasing team size increases the probability of an agent receiving a reward for executing any reward-causing state-action pair that is greater than if they were not in a team.

The proof of this theorem is in Appendix B. This theorem has direct implications on the policy that i learns - more positive reward for executing a particular state-action pair will cause i to execute that pair more often. A larger team monotonically increases the probability that any teammate will be in a corresponding reward state and instantaneously share this reward with i through TRi[n]. From the perspective of individual agents, this distributes the environment's reward function to other areas of the state space.

Consider our two state environment in Figure 1. Agents individually receive a reward of 0 for visiting sc but receive a reward of r for visiting sr when c = 1. Without teammates (n = 1), agent i only receives the environmental reward when visiting sc (i.e., reward of 0). With teammates, i receives a reward (through TRi[n]) of at least rn > 0 when visiting sc if at least one teammate is visiting sr. This probability increases if there are more teammates. The implications of this is that i will learn the benefit of executing it's part in a reward-causing state-action pair, leading it to execute this role more often.

5 Teams Impact on Credit Assignment

Whereas the previous section showed how teams increase the reward agents receive for executing reward-causing stateaction pairs (i.e., visiting sc), we now analyze the relationship between team structure and the distribution of rewards across all state-action pairs. In this section, we use information theory to explore how sub-optimal team structures impact the ability for agents to perform credit assignment.

5.1 Information Sparsity in Single-Agent Settings

Credit assignment is concerned with identifying the value past actions on observed future outcomes and rewards. In single agent Markov Decision Processes (MDPs), information theory has been used to formalize conditions which make credit assignment infeasible, such as when the environment does not provide enough information (through reward) for an agent to learn [Arumugam et al., 2020]. We expand this concept to our setting. Let si ∈ Si and ai ∈ Ai represent any arbitrary state and action by an agent i within their individual state and action spaces. Following the single-agent case definitions in [Arumugam et al., 2020] (i.e., if N = 1), let Zi be a random variable denoting the return for a single agent having taken action ai in state si, and following πi thereafter. The information gained by πi is a random variable, defined as:

the Kullback-Leibler (KL) divergence between p(Zi|si, ai) and p(Zi|si) = Σai∈Ai πi(ai|si)p(Zi|si, ai) (the distribution over returns for random state-action pairs conditioned on a particular state and action (i.e., the Q-value) versus only a particular state si (i.e., the value function)). Equation 2 is the distributional analogue to the advantage function in RL, Aπi = Qπi (si, ai) - V πi (si), the difference between the value of taking action ai at state si and the expected value of state si. Let dπi be the distribution of states visited and actions taken by i's policy. The expected amount of information carried by the actions of πi about the return of those state-action pairs is defined as:

Difficulties with credit assignment emerge when I(Ai; Zi|Si) is small enough that the actions of a policy carry almost no correlation with the reward signal. Prior work defined an ϵ-information sparse MDP as I πi (Ai; Zi|Si) ≤ ϵ for any initial policy at the beginning of training [Arumugam et al., 2020]. However, Equation 3 and ϵ-information sparsity do not fully translate to the multiagent team setting since they only consider the expected information. Teams modify the distribution, or variance, of information (Equation 2) across state-action pairs conditioned on the experienced values of the team reward random variable, ZTi .

For example, consider a non-ϵ-information sparse singleagent MDP environment where one state-action pair yields reward r and every other state-action pair gives a reward of zero. If r is divided evenly and distributed so that every stateaction pair yields the same reward, I(Ai; Zi|Si) is unchanged (due to expectation) but the agent's policy carries no correlation with the reward signal. The agent would now be unable to learn the same optimal policy as before (i.e., visiting the state which previously yielded r).

5.2 Information Sparsity with Teams

We enrich the definition of information sparsity in the context of stochastic games. This must consider two aspects of information. First, the expected information gained by i's individual policy given their team reward function, substituting Zi with ZTi in Equation 2, I πi (Ai;ZTi |Si). Second, we must also consider the variance of information gained by i's policy over the distribution of their individual state-action pairs given their team reward function, var[I πi Si,Ai (ZTi )] (see Appendix D for the extended KL-Divergence derivation).

Definition 1. Given a stochastic game with non-stationary policy class πH, let π0N denote the set of initial policies for all N agents employed at the very beginning of learning. For small constants ϵ > 0 and µ > 0, a stochastic game is (ϵ, µ)- information sparse if:

Definition 1 states that the actions of any agent i's policy given their shared team reward function must carry enough information with high enough variance for i to be able to learn. Otherwise, the stochastic game is considered (ϵ, µ)- information sparse. Low variance of information is detrimental to credit assignment since an agent would receive similar rewards regardless of their policy. By redistributing rewards, teams can significantly modify var [I πi Si,Ai (ZTi )] compared to settings without teams.

5.3 Risks of Sub-Optimal Team Structure

We now analyze convergence properties of the team reward as a function of team size, conditioned on the behavior of all N agents (i.e., global team structure). Since TRi[n] is determined by the experiences of all teammates, we focus on the joint policy of agents in Ti, πTi , which determines the team return over a joint trajectory, Z(τTi ).

First, assume we have a (non-(ϵ, µ)-information sparse) stochastic game with N agents and no teams. By Definition 1, this environment has enough information with high enough variance for individual agents to be able to learn. Creating teams of agents in this game impacts the team structure and the reward signals agents learn from. In the previous section, we showed how increasing a team's size increases the probability of i receiving a better reward signal for executing a reward-causing state-action pair than without teams. However, effectively identifying these pairs depends on an appropriate team structure.

Next, we theoretically show how a sub-optimal team structure can transform this non-(ϵ, µ)-information sparse stochastic game into an (ϵ, µ)-information sparse stochastic game by decreasing the variance of information through TRi[n] below µ as team size increases in the limit. In practice, N (or the size of a team n) need only be sufficiently large to reduce the variance of information below µ as agents are grouped together in a team. This has implications on an agent's ability to perform credit assignment and learn an effective policy. To formalize this, we leverage a finding in [Arumugam et al., 2020] which we adapt to the multiagent team setting which equates information with reward entropy. The proof is in Appendix C.

Proposition 1. Let πTi be the joint fixed behavior policy of agents in Ti that generates a joint trajectory of experiences

τTi , where the randomness of state-action pairs in τTi depends on all N agents (by the definition of a stochastic game). Let TRt i[n] be a random variable denoting the team reward at any timestep t (where the randomness of the deterministic reward follows from the randomness of the joint state-action pairs of individual agents in Ti at time t, depending on all N agents, τ tTi ). It follows that:

The equality states that the information of the joint policy for team Ti at time t is equal to the entropy, a measure of missing information or uncertainty [Shannon, 1948], of the team reward at timestep t, TRt i[n] , given the team-wide joint trajectory up to time t. For example, if TRt i[n] returns the same value at each timestep regardless of the joint policy, the entropy of this reward function is zero and the information gained by the team's joint policy, and each agent's individual policy, is zero.

We next show how the variance of TRi[n] converges to zero as a function of increasing team size. The variance describes the distribution of potential team rewards given the randomness of state-action pairs experienced by agents in Ti. The proof is in Appendix C.

Lemma 1. The team reward random variable TRi[n] for any state-action pair converges to the mean environmental reward (mean of any agent's individual reward function) as team size increases in the limit (i.e., TRi[n](st , at , st+1 ) → Ri as n → ∞).

Using Proposition 1 and Lemma 1, we conclude that the information carried by the joint policy of teammates over the joint trajectory τTi converges to zero as team size increases. The proof is in Appendix C.

Theorem 2. The information in a stochastic game at time t, I(Z(τ i); τ ti |τ -t i ), converges to 0 as the size of a team, n, increases in the limit.

Since µ > 0, defining larger teams will make a non(ϵ, µ)-information sparse stochastic game into an (ϵ, µ)- information-sparse stochastic game if the team is too large. In this setting, TRi[n] would not provide enough information about agents' individual policies and has implications on credit assignment, leaving agents unable to learn.

Theorems 1 and 2 imply the existence of an optimal team structure. Increasing the size of teams can help agents identify reward-causing state-action pairs (Theorem 1); however, sub-optimal team structure carries the risk of infeasible credit assignment (Theorem 2). Since ϵ and µ are domain dependent, discovering the best team structure to help agents learn remains subject to many domain specific variables. We can theoretically define a general rule that this team structure follows: maxn s.t. supπi∈π0N I πi (Ai;ZTi |Si) > ϵ and

supπi∈π0N var [I πi Si,Ai (ZTi )] > µ. To investigate features of this optimal structure in practice, we next empirically evaluate teams across multiple multiagent domains that support increasingly large populations of agents.

6 Experimental Environments

We study the impact of team structure on learning in four environments: 4-States, an Iterated Prisoner's Dilemma (IPD) [Rapoport, 1974], Cleanup Gridworld Game [Vinitsky et al., 2019], and Neural MMO (NMMO) [Suarez et al., 2019]. We specifically choose environments that support any number of agents (there is no fixed maximum), are not zerosum, and have a diverse set of reward-causing state-action pairs. Our evaluation is designed to study various levels of RL algorithm and environmental complexity. Due to space, the IPD details and results, including an analysis of policy network smoothness (influence of n on the maximum eigenvector of the policy Hessian matrix, λmax), appear in Appendix F. We give preliminary overviews of the environments here and include all details of environments in Appendices E, F, G, and H.

4-States. 4-States is a simple, partially observable stochastic game based on the two state environment in Figure 1 (Figure 6 in Appendix E.1). In addition to sr and sc, we add two new states, s3 and s4, which generate no reward. Agents simultaneously choose among four actions: stay still or move to any of the other three states. An action transitions agents to their intended next state with 90% probability and to another random state with 10% probability. We fix |T | = 1 and increase n by a factor of 2 to remove the impact of other teams on the binary signal. Agents use Tabular Q-Learning [Sutton and Barto, 2018] with γ = 0.9 and ϵ-exploration (ϵ = 0.3) for 50 trials of 1,000 episodes (100 steps each).

Cleanup Gridworld Game. Cleanup [Vinitsky et al., 2019] is a temporally and spatially extended Markov game representing a sequential social dilemma. We keep the underlying environment unchanged from previous setups [Leibo et al., 2017] with the exception of the team reward. Agent observability is limited to an egocentric 15 × 15 pixel window and collecting an apple yields +1 reward (apple regrowth rate is dependent on the cleanliness of an adjacent river). We set |T | = 1 and increase team size to remove impacts of other teams on the conditional reward structure. We implement Proximal Policy Optimization (PPO) [Schulman et al., 2017] agents for 10 trials of 1.6 × 108 environmental steps (1,000 timesteps per-episode) using the Rllib RL library. 3

Neural MMO. Neural MMO (NMMO) [Suarez et al., 2019] is a large, customizable, and partially observable multiagent environment that supports foraging and exploration. Agent observability is limited to an egocentric 15 × 15 pixel window and have movement and combat actions. Agents maintain a stash of consumable resources (food and water) that deplete by 0.02 each timestep (minimum of 0) but are replenished by 0.1 by harvesting in the environment (maximum of 1.0 each). Agents share rewards and resources to resemble a hunter-gatherer society. There is no standard NMMO configuration; therefore, we reward agents for positive increases to their lowest resource: min(I)t -min(I)t-1 when min(I)t > min(I)t-1 , where I is the inventory of food and water. Agents must learn to maintain both food and water to receive reward, creating multiple dynamically changing reward-causing state-action pairs, a more challenging scenario than the other environments. We implement PPO agents for eight trials of 1.5 × 107 environmental timesteps (1,000 per-episode) using Rllib. Additional details in Appendix H.1.

3 https://docs.ray.io/en/latest/rllib/index.html

7 Empirical Results

In this section, we evaluate how the size of teams affects team performance. We observe a similar trend across all environments and learning algorithms: performance initially increases with more teammates, but decreases once teams become too large. Thus, our results highlight a "sweet spot" team structure that helps guide agents' learning in these environments.

7.1 4-States Environment Results

Due to the small number of states, larger teams in 4-States can generate more reward, even if agents act randomly (more agents can collect a reward of 1 in sr). Thus, we measure team reward as a fraction of each team structure's theoretical optimal reward assuming no randomness (mean episode reward of 12 for n = 1, n-1 n for n > 1). Figure 2a (top) shows the team reward compared to optimal (y-axis) over timesteps of our experiments (x-axis). Each line represents a different team size with 95% confidence intervals. When n = 1, only 25.2% of the optimal reward is achieved. Increasing to n = 2 dramatically increases the reward to 66.5% of the optimal solution, and larger teams result in diminishing returns. Considering ϵ-exploration and transitions impose about 33% randomness, n = 2 performs well.

The y-axis of Figure 2a (bottom) shows the mean difference in Q-values between actions, scaled by the maximum Q-value in the table at each timestep. Lower values indicate agents expect similar values for any action and have not learned the reward dynamics of the environment. This plot follows the same trend as the reward: agent learn more disparate Q-values when n = 2, but larger teams cause agents to learn similar values for all actions. This indicates a decrease of environmental information as n grows.

Figure 3 shows the team state visitation frequencies as a fraction of the optimal policy with 95% confidence intervals (i.e., transitioning between sc to sr when n = 1, and one agent in sc while n - 1 agents in sr when n > 1). When n = 1, the agent fails to learn the value of transitioning to sc. Agents perform closest to optimal when n = 2, suggesting they learn the value of visiting both sc and sr while avoiding s3 and s4. The agents are unable to fully converge to the optimal policy due to the stochastic transition function and ϵ-greedy action selection. With larger n, agents tend to visit sc more often than optimal and sr with less frequency, suggesting they fail to learn the reward-causing dynamics of the environment with larger groups, supporting our theory.

7.2 Cleanup Gridworld Game Results

Figure 2b shows the team reward (top) and mean policy entropy (bottom) along the y-axes with 95% confidence intervals, and timesteps along the x-axis. Our results follow a similar trend as seen in 4-States. More reward is initially obtained by adding teammates and is highest when n = 2 or n = 4, due to a division of labor: half of the agents specialize in each role of cleaning the river or picking apples. When n = 3, two agents specialize in river-cleaning roles while only one collects apples, causing slightly less team reward due to more sharing than when n = 2, but collecting fewer apples than when n = 4. Team structures with n > 4 tend to have decreasing team reward, following our theoretical findings in Section 5.3. We use policy entropy (πi entropy) to better understand role specialization on teams, where lower πi entropy implies higher role specialization and less random actions (Figure 2b bottom). We observe that when n = 2, mean πi entropy is lowest and as n increases, agents policies tend to become more random. We observe a correlation between team reward and agents' convergence to specialized roles, measured by πi entropy, and find the lowest mean πi entropy when n = 2. This πi entropy tends to increase as n is larger, suggesting agents' policies become more random.

Figure 4 shows the mean team reward three agents receive (columns) at different map locations when they are in a team of n = 4 (top row) and n = 6 (bottom row), where darker red indicates more reward. The plots for the remaining teammates in each row are shown in Figure 9 in Appendix G.2. When n = 4, we find that the two agents that specialize in river-cleaning roles (agent 0 and 3) also spatially divide the labor into different parts of the river, one in the top half and one in the bottom half. This allows their two other teammates (agents 1 and 2) to collect apples and reward for the team. However, when n = 6 we observe that three agents specialize in river-cleaning roles (agents 0, 3, and 4), but are less specialized in their cleaning locations. Agents 0 and 3 tend to clean the same segment of the river, converging to redundant policies that do not generate significantly more apples for their apple-picking teammates to collect.

7.3 Neural MMOResults

Figure 2c shows the NMMO results. When n = 1, the agent fails to learn the value of collecting both food and water which results in no reward. As teammates are introduced, the agents learn complimentary harvesting roles and gain the highest team reward when n = 2, 3, 4. However, we observe diminishing returns with larger teams (when n > 4). We hypothesize that these values are highly correlated with the number of inventory item types and harvesting tasks. Similar to Cleanup, agents have significantly less πi entropy in these settings, suggesting that agents have converged to specific roles on their team and act less randomly than when they have no teammates or many teammates. This result supports our theory and is consistent with our other experiments: a sufficient number of teammates results in more favorable policies, but too many teammates leads to diminishing returns. Our spatial results in NMMO, similar to the findings in Cleanup in Figure 4, are shown in Figure 11 in Appendix H.2.

8 Discussion

Our research provides an understanding as to why, and under which conditions, smaller teams can outperform larger teams. Introducing teammates can help agents identify reward-causing state-action pairs (Section 4), but too many teammates can make credit assignment more difficult which hinders learning (Section 5). This provides theoretical explanations behind the empirical results of several recent papers [Durugkar et al., 2020; Radke et al., 2022].

A common perception about RL theory is that convergence to the optimal policy is guaranteed given infinite computation. While this finding is true for single-agent RL [Sutton and Barto, 2018], convergence guarantees are known to not hold in many multiagent settings. Our paper's context of multiagent teams, even in a scenario with one team (i.e., cooperative population), is a setting where convergence to an optimal joint policy is not guaranteed, even with infinite computation. This is a result of our finding in Theorem 2, since information converges to zero as a function of team size. However, information does not need to be zero for RL to fail (it can fail when information is sufficiently small); thus, in practice, infinitely large team size is not required for this result. We are unable to guarantee non-convergence since random policy updates could theoretically result in the optimal joint policy; however convergence to this policy is not guaranteed.

While we provide much needed insights into the importance of teams and team structures to shape the learning problems and reward functions for individual learning agents, there are several opportunities for future work. These include developing social planning algorithms to construct highly efficient team structures within a population of agents from domain variables, precisely measuring ϵ and µ from domain variables, alternate definitions of teams or reward schemes, and developing agents that can regulate their own team alignment to overcome a sub-optimal team structure situation [Radke and Tilbury, 2023]. Further progress in this direction will be pivotal to better understand how and in what social scenarios cooperation and complex behaviors can naturally emerge at individual and group levels.

Acknowledgements

This research is funded by the Natural Sciences and Engineering Research Council of Canada (NSERC), an Ontario Graduate Scholarship, a Cheriton Scholarship, and the University of Waterloo President's Graduate Scholarship. We thank the Vector Institute for providing the compute resources necessary for this research to be conducted. We also thank Alexi Orchard, Valerie Platsko, Kanav Mehra, and all reviewers for their feedback and useful discussion on earlier drafts of this work.