Balancing Individual Preferences and Shared Objectives in Multiagent Reinforcement Learning

1 Introduction

When independent agents jointly learn to perform a cooperative task, multiagent reinforcement learning (RL) methods can be brought to bear [Busoniu et al., 2008; Hernandez-Leal et al., 2019] . When they must do so without any prior co[Barrett et

al., 2013; Stone et al., 2010]. Ad hoc teamwork typically assumes that the participating agents have fully aligned preferences - that they prioritize the shared task completely.

In contrast, in this paper we consider ad hoc teamwork in which agents working together on a shared task have individual preferences regarding how to accomplish it. For example, consider a (human) musical ensemble. Each musician learns to play their instrument independently, and typically has their own aesthetic preferences regarding what they'd like the shared music to sound like. However, when performing together, the musicians also have to harmonize and coordinate so that they produce music that is pleasing to their audience, who serve as a shared and extrinsic reward signal.

To incorporate the agents' individual preferences, we assume that each agent linearly blends their individual preference with the shared task reward. A natural assumption would be that the more weight the agents place on their individual preferences, i.e. the more selfishly they behave, the worse the team will perform. On the contrary, we find that a certain degree of selfishness can be beneficial to team performance.

∗ equal contribution

The main contribution of this paper is a detailed analysis of this phenomenon, from both a theoretical and an empirical perspective. In particular:

• We theoretically analyze the conditions in which individual preferences can still lead to maximizing task reward.
• We empirically study how different blending proportions (mixing schemes) for individual and shared reward impact learning of the shared task.
• For a given set of preferences, we show a practical method to search over mixing schemes for the purpose of optimizing joint task performance.

We observe this effect in two different multiagent domains, the predator prey domain (a canonical multiagent RL environment also known as the Pursuit domain), and a novel music generation environment motivated by human musical ensembles. 1

2 Background

Reinforcement Learning (RL) considers an agent acting in a Markov Decision Process (MDP), a mathematical framework for modeling sequential decision-making [Sutton and Barto, 2018]. An MDP is defined as a tuple 〈S,A, T,R, γ〉, where S is the set of states, A is the set of actions, and T is the transition probability, p(st+1|st, at), where st, st+1 ∈ S and at ∈ A. R(st, at, st+1) ∈ R is the reward for taking action at in state st and transitioning to state st+1. The discount factor γ ∈ [0, 1) specifies how much to discount future rewards. Reinforcement learning aims to maximize the return, i.e. the sum of expected discounted future rewards Eπ ∑∞t=0 γ tR(st, at, st+1).

π is a stochastic policy that specifies the probability of taking an action at ∈ A in state st ∈ S. To maximize the expected returns, one possible technique is to optimize the policy directly: π∗ = argmaxπ Eπ ∑∞t=0 γ tR(st, at, st+1)

1 Appendix at https://tinyurl.com/yb8hzx73.

In this study we use proximal policy gradient (PPO) [Schulman et al., 2017], which is an algorithm to optimize the policy directly using the policy gradient technique [Sutton et al., 2000].

2.1 Multiagent Reinforcement Learning

In the multiagent setting, we consider a fully observable environment with K agents acting simultaneously. Most of the MDP formulation for RL with a single agent carries over to this setting without notational modifications. The action space is modified to A ≡ AK . At each time step, all agents take their actions, and the joint action vector at = [a1,t, a2,t, . . . , aK,t] acts on the state to produce the transition to the next state and reward, Re(st, at, st+1).

We consider a cooperative setting where the environment's reward Re is shared among all the agents. In this study we focus on the decentralized learning scenario, in which each agent's policy πk (parameterized by θk) is learned and updated separately by each individual agent. To learn in this manner, we provide this shared reward to all the agents and the agents individually use PPO to improve their policies, with a small learning step to allow the PPO algorithm learning to proceed in a stable manner.

2.2 Individual Preferences

We consider an individual preference for agent k as the policy πp k that the agent prefers to execute while performing the shared task. The agent can be initialized to this policy or can use a dataset Dk of tuples (st, at) generated by executing πp k and recover the maximum likelihood policy via Behavioral Cloning. We then model this preference via an individual reward Rk that most likely induces this preferred policy. The individual reward can be inferred via inverse RL [Abbeel and Ng, 2004]. Specifically, we use GAIL [Ho and Ermon, 2016] (an adversarial form of inverse RL) to infer an individual reward via the dataset Dk.

3 Balancing Preferences with Shared Task

Figure 1 illustrates the framework of individual preference reward balanced with a shared objective. At each time step, the environment presents a reward Re(st, at, st+1). But each agent also receives its individual reward or preference signal Rk, inferred according to Section 2.2. For each agent, we balance Re and Rk using a mixing factor αk ∈ [0, 1]. We refer to the combination of α values for all agents (〈α1, α2, . . . , αK〉) as the mixing scheme. We train the agent policies to maximize this weighted joint reward Rk,e(st, at, st+1), calculated for the kth agent as:

Both our theoretical analysis in Section 4 and our empirical analysis in Section 5 lead to the somewhat counter-intuitive conclusion that blending in individual preferences (i.e. setting the αk's to be < 1) can aid team learning.

4 Game-Theoretic Analysis

In this section we examine the interplay between individual preferences and task rewards. For simplicity, we look at a single step of a game, and show under which conditions individual preferences lead to maximizing the shared task reward. While we do not assume that the learning process converges to a Nash equilibrium, we show that if individual and environment returns are predicted correctly, they will lead to a Nash equilibrium for a certain range of α coefficients (i.e. mixing scheme). A priori, it seems intuitive that individual preferences can be substantially harmful to team performance if these preferences are not perfectly aligned with the shared task. However, this analysis establishes that there is a range of selfishness conditions under which the game does converge to an equilibrium which maximizes task reward even if selfish preferences are not perfectly aligned with the shared reward.

Let us assume there are two agents A and B interacting in a game [Leyton-Brown and Shoham, 2008] in which each agent can take one of two actions (this can be BachStravinsky or Matching Pennies or any other game of this form). Agents A,B's preferences are denoted with the following payoff matrices, respectively:

However, unlike a typical game, in this game there is also an environment which gives both agents the following reward according to their matching actions:

Let αa, αb be the mixing scheme for agents A,B respectively, determining their extent of blending environment and individual reward signals. The resulting game payoff matrices for A,B are then:

Assume w.l.o.g. that e11 yields the highest environment reward. Let us consider which α values could lead to e11

being an equilibrium. 2 The combination of actions leading to e11 is a Nash equilibrium [Osborne and Rubinstein, 1994] if: (1 - αa) · a11 + αa · e11 > (1 - αa) · a21 + αa · e21 and (1-αb) · b11 +αb · e11 > (1-αb) · b12 +αb · e12.

Simplifying the math leads to: αa > a21-a11 e11-e21+a21-a11 , and analogously, αb > b12-b11 e11-e12+b12-b11 .

Let us define δ(a) = a21 -a11 and δ(e) = e21 -e11. Then δ(a) and δ(e) denote the utility in defecting from action a11 to action a21 in terms of selfish reward and environment reward, respectively. Observe that δ(e) ≤ 0 since by definition ∀eij, e11 ≥ eij. Then αa > δ(a) δ(a)-δ(e) .

If we consider δ(a) as the selfish improvement by defecting to the suboptimal action, and δ(a) - δ(e) as the impact of defecting combined with the global relative payoff of not defecting, then this means that α needs to be greater than the ratio between the agent's selfish improvement and this combined global payoff impact.

If we also consider that 1 ≥ αa ≥ 0 and 1 ≥ αb ≥ 0, we get a simple set of linear inequalities - if it has a feasible solution, then there exists a mixing scheme for the agents that would lead to the environment-wise ideal solution becoming a game-theoretic equilibrium. Observe that this analysis holds even for arbitrary values of eij , which implies that we can exhaustively study how multiple mixing schemes can lead to multiple equilibria. This observation can be straightforwardly generalized to k agents, leading to this set of inequalities:

With action l to be the best response for agent Ai.

Let us denote δ(aij ) = aij̸=l - ail and δ(eij ) = ej̸=l - eil (recall ail and eil are assuming the other agents' actions are fixed). Then we obtain a generalized set of inequalities:

These inequalities, combined with the constraints that ∀i.1 ≥ αi ≥ 0, can all be solved efficiently, and if satisfied, it means the vector of αi values again leads to a Nash equilibrium. Refer to Appendix D for a detailed derivation. Interestingly, this result bears some resemblance to the findings of Peterson [Peterson, 2009], who studied cooperation in a generalization of coalition games.

We note that it is straightforward to extend this analysis to a multi-step scenario as a repeated stage game with the above conditions repeated at each step.

While this analysis is conducted for a single step k-agent game, it nonetheless provides formal support for the idea that optimal shared task performance can be reached as a stable equilibrium when taking individual preferences into account, even when these preferences are not aligned perfectly with the shared task reward. This analysis also specifies the concrete conditions the mixing scheme needs to satisfy in order to maximize environment reward.

2 There may be other equilibria as well. The purpose of this analysis is to show that there are non-trivial α values (i.e. α < 1) that lead to some equilibrium

5 Experimental Analysis

In this section we investigate empirically whether the above conclusion holds in more realistic, more complex settings.The experimental methodology is detailed in Algorithm 1. In Section 5.1 we detail two domains set in the multiagent MDP framework from section 2.1. In our first experiment (Section 5.2), we vary the different preference signals and the mixing schemes and compare the effect on learning the shared task. Somewhat surprisingly, we find that preferences accelerate improvement in the task performance in both these environments. Further, in Section 5.3 we demonstrate a method to find a mixing scheme that outperforms purely task-reward-based learning in both domains.

5.1 Environments

We study the above framework on two multiagent cooperative domains: the well known predator prey domain [Barrett et al., 2013], and a new chord generation domain. We consider these domains as they are suited to different policy combinations by the agents (homogeneous policies for predator prey and heterogeneous for chord generation).

The first domain, predator prey, has 4 predators and one prey in a 10 × 10 toroidal grid world (i.e. wrapped around on all sides), and they prey is caught only if the predators surround the prey on all four sides. Episodes are 100 steps long with a reward of -1 at the end if the prey is not caught. If the prey is caught, the episode terminates with a reward of +1. All other steps have a reward of 0 and we use a discount factor γ = 0.99. The evaluation metric used is the number of steps it takes to capture the prey (lower is better). For preferences, we use three policies from the literature that can catch the prey and one policy that cannot (random actions). These policies also form the baselines we compare to. Refer to Appendix A.1 for further details.

For the second domain, we introduce the chord domain to learn how to generate a sequence of chords. A motivation for this setting is the musical ensemble scenario from Section 1.

Algorithm 1 Experimental Methodology

Input: K, preferences R1,R2, . . .RK, dataset D1,D2, . . .DK, mixing values α1, α2, . . . , αk, shared reward Re, number of training episodes H, episode length T Initialize policies π1, π2, . . . πK for i ← 0 to K do pretrain(πi, Di) using Behavioral Cloning for h = 0; h <H; h+ = 1 do for t = 0; t < T; t+ = 1 do get joint action at act in environment compute mixed reward Rk,e (Equation 1) optimize policies

In this setting each agent plays a single note at each time step out of the 12 possible pitch classes, simply denoted with integer values {0, . . . , 11}. 3 The agents must generate a valid chord (which is a possible 4 · 12 = 48 note configurations out of 124 = 20736 possible 4-note configurations), as well as valid transitions (no repetitions or inversions).

The reward signal is designed to reward generating valid note configurations, and penalizing repetitions and inversions, and repeated intervals (same chord configuration with base note changed). We model different reward functions by changing the relative weighting between these two penalties (w1) and between the above penalties and the rewards for valid chords (w2). These criteria are heuristics designed by us, but with solid grounding in music theory, as surprise and novelty are basic driving forces in Western music [Cook, 1994]. It is important to note that while musical performance is subjective, we have designed this particular domain to focus on chord generation, which can be evaluated objectively through our reward function. The task is trained in a continuing manner (with no termination), over 30000 steps, with γ = 0.99. The individual preferences are policies that prefer certain chord sets, and are further differentiated with variations on the actual reward function they maximize (by setting w1 and w2 to {0.2, 0.8} and {0.8, 0.2}).

5.2 VaryingMixing Schemes and Agent Configurations

As we've established in Section 4, under reasonable conditions there exists a mixing scheme, i.e. a blend of selfishness and selflessness for all agents, which ensures that the individual preferences do not take precedence over the shared task. To verify this effect in practice, in this section we study the performance of agents with different preferences and mixing schemes in the two aforementioned environments.

Given 4 possible agent preference models in each domain, we considered 23 different mixes of different agent types, sampled from the overall 44 = 256 possible agent configurations. Similarly, to better study the trade offs between different agent configurations and different mixing schemes, we canvased a wide range of configurations. A technical discussion on how preferences were constructed in each environment is presented in Appendices A.1 and A.3.

Figure 2 presents the effects of different preferences and different mixing schemes at the end of training in the predator prey domain. Figure 3 presents the effects of different preferences and different mixing schemes at the end of training in the chord generation domain. Scores for these configurations are averaged over 8 independent runs. The red asterisk in each column marks the mixing scheme that works best for those preferences at that time step.

A surprising observation arising from Figures 2 and 3 is that the optimal configuration is not the baseline (four selfless agents attempting to maximize their reward w.r.t. shared task reward only). Rather, in each environment a mixing scheme exists which performs the best on a variety of agent mixes. Interestingly, even in the case of random preferences (preference #0 in Figure 2) in the predator-prey domain, despite overall reduced performance, an intermediate mixing scheme still does better than a selfless mixing scheme (α = 1).

3 Relating the scale to actual notes, 0 denotes C, 1 denotes C#, 2 denotes D and so forth up to 11 = B.

On a side note, we verify that this effect is not due to the reduced search space induced due to more directed policies (Appendix C).

5.3 Optimizing the Mixing Scheme

In the previous section we have established that some mixing schemes lead to accelerated improvement and better asymptotic performance on the shared task under certain conditions. This observation raises the question of how difficult it is to directly optimize these values in order to find a mixing scheme which leads to maximization of task performance. We find below that given a set of reasonable preferences, it is possible to find a mixing scheme that outperforms the purely taskreward-based approach rather handily.

In order to optimize the mixing scheme, we frame the problem as a constrained global Bayesian optimization task using Gaussian processes as described in [Snoek et al., 2012]. Subsequently, we use the gradual posterior inference procedure to guide the optimization towards increasingly more beneficial mixing schemes. The actual evaluation of each mixing scheme sampled is done by running a trial on the shared task with these values and observing the resultant team performance. To evaluate the utility of a given mixing scheme, we run a trial with that scheme and consider the evaluation score.

The results for such a procedure in the predator-prey domain are presented in Figure 4. As can be observed, with a total of only 34 samples (i.e.runs) in total, we were able to find a configuration that outperforms the "preference-free" default of α = 〈1, 1, 1, 1〉 (i.e., completely selfless agents with no previous preferences). More precisely, the mixing scheme in the neighborhood of α = 〈0.15, 0.09, 0.19, 0.35〉 does best, leaning more towards preferences than the shared task reward. This mixing scheme resulted in a joint policy with an average 100 episode score of 17.68, more than twice as good as our strongest baseline in this domain.

Similarly, the optimization results in the chord generation domain (Figure 5) are based on 29 samples (trials) and radial basis function interpolation. The best mixing scheme found through the optimization procedure (〈0.98, 0.69, 0.95, 0.49〉) leads to results more than three times better than the default values of pure selflessness (α = {1, 1, 1, 1}). The above mixing scheme is interesting, indicating that two agents that are mostly selfless and two agents that balance selflessness and selfishness perform best in this domain. Such a result is somewhat reflective of observations made by Colman et al. [Colman et al., 2008] and Sugden et al. [Sugden, 2008], who analyzed empirically observed team behaviors as a decomposition of selfish actors vs. team-reasoners.

These encouraging outcomes suggest a practical method to efficiently tune mixing schemes, making the framework proposed in this paper more immediately useful in cases in which adjusting the mixing scheme or selecting the agent configuration is feasible.

6 RelatedWork

Multiagent RL has been studied and applied in a variety of settings [Busoniu et al., 2008], whereas the issue of cooperation and selfishness in team games has been of interest in the game theory literature for several decades [Aumann, 1961; Peterson, 2009]. There has been considerable work in scaling multiagent RL to more complex domains and studying multiagent behavior using Deep Reinforcement Learning [Tampuu et al., 2017; Hernandez-Leal et al., 2019; Foerster et al., 2017], including human-level performance in multiplayer games [Jaderberg et al., 2019]. In multiagent RL, MADDPG [Lowe et al., 2017], QMIX [Rashid et al., 2018] and COMA [Foerster et al., 2018] have been recently proposed as algorithms to train agents. However, they assume a strong coordinating structure in learning, such as a central critic, while our approach considers completely decentralized policies.

Ad hoc teamwork [Barrett et al., 2013; Stone et al., 2010] is a setting in multiagent RL where individual agents come together to accomplish a shared task with no prior knowledge of the policies of the other agents. It is conceivable that in this setting, each agent has some previous policy that they prefer. Our work considers how to leverage such previously existing policies towards accomplishing the shared task.

Our approach uses GAIL as a way to generate the individual preferences which the agents use as their personal reward signals. The GAIL reward can be considered to induce directed exploration, and has been used in single agent RL scenarios to accelerate learning [Kang et al., 2018; Zhu et al., 2018].

The individual agent preferences we propose can also be considered as an approach to Curriculum Learning [Narvekar et al., 2020]. These preferences can be seen as simpler tasks that can prime the agent policies for the shared task. They can also be considered an approach to multi-task Reinforcement Learning [Wilson et al., 2007; Ammar et al., 2014] where the agent attempts to learn a policy that can satisfy multiple objectives, or the individual reward - social choice setting in the multi-objective multi-agent taxonomy [R˘adulescu et al., 2020]. Another perspective on the individual preferences is as a sort of intrinsic motivation [Barto, 2013; Sequeira et al., 2011], that uses it to encourage behaviors like exploration or better transfer [Barto et al., 2004]. Previous work has also shown the effectiveness of learning a separate reward function for different agents [Jaderberg et al., 2019], but does so from scratch using population based techniques. Our approach leverages known preferences to improve task performance. CM3 [Yang et al., 2020] learns individual agent policies in isolation before introducing the multi-agent setting. However, they do so for tasks that each individual has to accomplish individually, as opposed to the more general coordinated tasks we consider here.

7 Discussion and FutureWork

This paper analyzes the cooperative multiagent learning scenario where each agent has their own individual preference about how the shared task should be accomplished. We model this scenario with a linear mixing scheme that trades off the task reward with each agent's individual preference. Even though this model is fairly straightforward, we find it leads to the interesting outcomes where partial selfishness leads to better performance compared to purely selfless task based learning. This is a surprising result since our game theoretic analysis suggests that at best the individual preferences do not hurt the task performance. This gap between the empirical outcomes and theoretic analysis deserves more attention in future work.

Studying the impact of individual preferences on task performance is necessary in an environment where heterogeneous agents come together to accomplish a task (ad-hoc teamwork). While we do not address the question of where preferences come from, we show that a wide variety of preferences can be used in this scenario. On the other hand, our experiments with a preference that hurts task performance (random actions in predator prey) show that the exact conditions under which a preference is useful needs to be characterized further.

We also show that it is feasible to find a good mixing scheme for a given set of preferences using basic Bayesian Optimization. However, an interesting extension to this work would be to find a way to optimize the mixing scheme within the agent's lifetime.

Acknowledgements

This work has taken place in the Learning Agents Research Group (LARG) at UT Austin. LARG research is supported in part by NSF (CPS-1739964, IIS-1724157, NRI-1925082), ONR (N00014-18-2243), FLI (RFP2-000), ARO (W911NF19-2-0333), DARPA, Lockheed Martin, GM, and Bosch. Peter Stone serves as the Executive Director of Sony AI America and receives financial compensation for this work. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy on objectivity in research.