Learning Individual Policies in Large Multi-agent Systems through Local Variance Minimization

In this paper, we are motivated by large scale multi-agent systems such as car matching systems (Uber, Lyft, Deliveroo etc.), food delivery systems (Deliveroo, Ubereats, Foodpanda, DoorDash etc.), grocery delivery systems (AmazonFresh, Deliv, RedMart etc) and traffic routing guidance. The individual agents need to make sequential decisions (e.g.,on where to position themselves) in the presence of uncertainty. The objective in aggregation systems is typically to maximize overall revenue and this can result in individual agent revenues getting sacrificed. Towards ensuring fair outcomes for individual agents, our focus in this paper is on enabling computation of approximate equilibrium solutions.

Competitive Multi-Agent Reinforcement Learning (MARL) (Littman 1994) with an objective of computing equilibrium is an ideal model for representing the underlying decision problem. There has been a significant amount of research on learning equilibrium policies in MARL problems (Littman 1994; Watkins and Dayan 1992; Hu, Wellman et al. 1998; Littman 2001). However, these approaches typically can scale to problems with few agents. Recently, there have been Deep Learning based MARL methods (Yu et al. 2021; Heinrich and Silver 2016; Yang et al. 2018; Lowe et al. 2017) that can scale to a large number of agents on account of using decentralized learning. While decentralized learning is scalable, such approaches consider all other agents in aggregate or as part of the environment and this can have an impact on overall effectiveness (as demonstrated in our experimental results).

To that end, we propose a Stochastic Non-atomic Congestion Game (SNCG) model, which combines Stochastic Game (Shapley 1953) and Non-atomic Congestion Game (NCG) models (Roughgarden and Tardos 2002; Krichene, Drighès, and Bayen 2015). SNCG helps exploit anonymity in interactions and minimal contribution of individual agents, which are key facets of aggregation systems of interest in this paper. More importantly, we use a key theoretical property of the SNCG model to design a novel model free multi-agent reinforcement learning approach that is suitable for both non-atomic and nearly non-atomic agents. Specifically, we prove that at equilibrium values of non-atomic agents, which are all in the same local state are equal. Our model free MARL approach, referred to as LVMQ (Local Variance Minimizing Q-learning) reduces variance in “best response” agent values in local states to move joint solutions towards equilibrium solutions.

We demonstrate the utility of our new approach for individual drivers on a large dataset from a major Asian city by comparing against leading decentralized learning approaches including Neural Fictitious Self Play (NFSP) (Heinrich and Silver 2016), Mean Field Q-learning (MFQ) (Yang et al. 2018) and Multi-Agent Actor Critic (MAAC) (Lowe et al. 2017). In addition, we also provide results on a general purpose simulator for aggregation systems.

The most relevant research is on computing equilibrium policies in MARL problems, which is represented as learning in stochastic games (Shapley 1953). Nash-Q learning (Hu, Wellman et al. 1998) is a popular algorithm that extends the classic single agent Q-learning (Watkins and Dayan 1992) to general sum stochastic games. In fictitious self play (FSP) (Heinrich, Lanctot, and Silver 2015) agents learn best response through self play. FSP is a learning framework that implements fictitious play (Brown 1951) in a sample-based fashion. There are a few works which assume existence of a potential function and either need to know the potential function a priori (Marden 2012) or estimate potential function’s value (Mguni 2020). Unfortunately, all these algorithms are generally suited for a few agents and do not scale if the number of agents is very large, which is the case for the problems of interest in this paper.

Recently, some deep learning based algorithms have been proposed to learn approximate Nash equilibrium in a decentralized manner. NFSP (Heinrich and Silver 2016) combines FSP with a neural network to provide a decentralized learning approach. Due to decentralization, NFSP is scalable and can work on problems with many agents. Centralized learning decentralized execution (CTDE) algorithms learn a centralized joint action value function during the training phase, however individual agents optimize their actions based on their local observation. MAAC (Lowe et al. 2017) is a CTDE algorithm which is a best response based learning method and does not focus on learning equilibrium policy. M3DDPG (Li et al. 2019) learn policies against altering adversarial policies by optimizing a minimax objective. SePS (Christianos et al. 2021) is another CTDE algorithm which focuses on parameter sharing to increase scalabilty of MARL. However these methods do not consider infinitesimal contribution of individual agents. As we demonstrate in our experimental results, our approach that benefits from exploiting key properties of SNCG is able to outperform NFSP and MAAC with respect to the quality of approximate equilibrium solutions on multiple benchmark problem domains from literature. There are some CTDE algorithms (Sunehag et al. 2018; Rashid et al. 2018; Yu et al. 2021) which focus on cooperative settings and not suitable for non-cooperative setting of our interest.

Treating large multi-agent systems as mean field game (MFG) (Huang, Caines, and Malhamé 2003) is a popular approach to solve large scale MARL problems where each agent learns to play against mean field distribution of all other agents. For MFQ (Yang et al. 2018), individual agents learn Q-values of its interaction with average action of its neighbour agents. (Hüttenrauch et al. 2019) used mean feature embeddings as state representations to encode the current distribution of the agents. (Subramanian et al. 2020) extended MFQ to multiple types of players. In the context of finite MFGs, (Cui and Koeppl 2021) proposed approximate solution approaches using entropy regularization and Boltzmann policies. Recently (Subramanian et al. 2022) proposed decentralized MFG where agents model the mean field during the training process. This thread of research is closely related to our work and we show that by utilizing extra information shared by the central agent, LVMQ outperforms MFQ.

We have proposed to minimize variance in the values of agents present in same local state to learn equilibrium policy. Some works in single agent reinforcement learning have focused on direct and indirect (Sherstan et al. 2018; Jain et al. 2021; Tamar, Di Castro, and Mannor 2016) approaches to compute variance in the return of a single agent. This is fundamentally different from LVMQ, where variance is across values of multiple agents present in a local state (instead of variance in value distribution for a single agent in those approaches).

NCG has either been used to model selfish routing (Roughgarden and Tardos 2002; Roughgarden 2007; Fotakis et al. 2009) or resource sharing (Chau and Sim 2003; Krichene, Drighès, and Bayen 2015; Bilancini and Boncinelli 2016) problems. Here we present a brief overview of NCG (Krichene, Drighès, and Bayen 2015) from the perspective of resource sharing problem as that is of relevance to domains of interest, where taxis have to share demand in different zones.

In NCG, a finite set of resources $\mathcal{L}$ are shared by a set of players $\mathcal{N}$. To capture the infinitesimal contribution of each agent, the set $\mathcal{N}$ is endowed with a measure space: $(\mathcal{N},\mathcal{M},m)$. $\mathcal{M}$ is a $\sigma$-algebra of measurable subsets, $m$ is a finite Lebesgue measure and is interpreted as the mass of the agents. This measure is non-atomic, i.e., for a single agent set $\{i\}$, $m(\{i\})=0$. The set $\mathcal{N}$ (with $m(\mathcal{N})$=1, i.e., mass of all agents is 1) is partitioned into $Z$ populations, $\mathcal{N}=\mathcal{N}_{1}\cup...\cup\mathcal{N}_{Z}$. Each population type $z$ possesses a set of strategies $\mathcal{A}_{z}$, and each strategy corresponds to a subset of the resources. Each agent selects a strategy, which leads to a joint strategy distribution, $\bm{a}=((f^{a}_{z})_{a\in\mathcal{A}_{z}})_{z\in\mathcal{Z}}\text{ such that }\sum_{a\in\mathcal{A}_{z}}f^{a}_{z}=m(\mathcal{N}_{z})\forall z$. Here $f^{a}_{z}$ is the total mass of the agents from population $z$ who choose strategy $a$. The total consumption of a resource $l\in\mathcal{L}$ in a strategy distribution $\bm{a}$ is given by: $\phi^{l}(\bm{a})=\sum_{z=1}^{Z}\sum_{a\in\mathcal{A}_{z}|l\in a}f^{a}_{z}$

The cost of using a resource $l\in\mathcal{L}$ for strategy $\bm{a}$ is: $c_{l}(\phi^{l}(\bm{a}))$ where the function $c_{l}(.)$ represents cost of congestion and is assumed to be a non-decreasing continuous function. The cost experienced by an agent of type $z$ which selects strategy $a\in\mathcal{A}_{z}$ is given by: ${\mathcal{C}}^{a}_{z}(\bm{a})=\sum_{l\in a}c_{l}(\phi^{l}(\bm{a}))$. A strategy $\bm{a}$ is a Nash equilibrium if:

Intuitively, it implies that the cost for any other strategy, $a^{\prime}$ will be greater than or equal to the cost of strategy, $a$. It also implies that for a population $\mathcal{N}_{z}$, all the strategies with non-zero mass will have equal costs.

Packet routing problem in Figure 1a is an example of an NCG. Two agent populations ($Z=2$) $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ of mass 0.5 each share the network. Each edge is treated as a resource. Agents from $\mathcal{N}_{1}$ send packets from node $A$ to node $B$, and the the agents from $\mathcal{N}_{2}$ send from node $E$ to node $F$. Paths (strategies) $AB,ACDB,ADB$ are available for population $\mathcal{N}_{1}$ whereas paths $EF,ECDF,ECF$ are available for population $\mathcal{N}_{2}$. A joint strategy is said to be an equilibrium strategy if for population type $z$, costs on paths available to them with non-zero mass are equal. Refer to the equilibrium policy given in Table 1, the costs on paths $ACDB$ and $ADB$ (paths with non-zero mass) for population $\mathcal{N}_{1}$ will be equal at equilibrium.

In this section we propose SNCG model, which is a combination of NCG and Stochastic Games. NCG is primarily for single stage settings, we extend it to multi-stage settings in SNCG. Formally, SNCG is the tuple: $\big{<}\mathcal{N,Z,S,A,T,R}\big{>}$

• $\mathcal{N}$:

  set of agents with properties similar to the ones in NCG described in Section Background: Non-atomic Congestion Game (NCG).

• $\mathcal{Z}$:

  set of local states for individual agents (e.g., location zone of a taxi).

• $\mathcal{S}$:

  set of global states (e.g., distributions of taxis in the city). At any given time, $\mathcal{N}$ is divided into $|\mathcal{Z}|$ disjoint sets, $\mathcal{N}=\mathcal{N}^{s}_{1}\cup...\cup\mathcal{N}^{s}_{|\mathcal{Z}|}$, where $\mathcal{N}^{s}_{z}$ is the set of agents present in local state $z$ in global state $s$ and $m(\mathcal{N}^{s}_{z})$ is the mass of agents in $\mathcal{N}^{s}_{z}$. The distribution of mass of agents is considered as the global state, i.e., $s=<m(\mathcal{N}^{s}_{1}),m(\mathcal{N}^{s}_{2}),...,m(\mathcal{N}^{s}_{|\mathcal{Z}|})>,\text{ with }\sum_{z=1}^{|\mathcal{Z}|}m(\mathcal{N}^{s}_{z})=1,\forall s\in\mathcal{S}$. The global state is continuous and total mass of agents in a global state is 1.

• $\mathcal{A}$:

  is the set of actions, where $\mathcal{A}_{z}$ represents the set of actions (e.g., locations to move to) available to individual agents in the local state $z$. $\mathcal{A}=\{\mathcal{A}_{z}\}_{z\in\mathcal{Z}}$. Let $act(i)$ provides the action selected by agent $i$. We define $f^{a}_{z}(s)$ as the total mass of agents in $\mathcal{N}^{s}_{z}$ selecting action $a$ in state $s$, i.e. $\sum_{a\in\mathcal{A}_{z}}f^{a}_{z}(s)=m(\mathcal{N}_{z}^{s})$. If the agents are playing deterministic policies, $f^{a}_{z}(s)$ is given by $f^{a}_{z}(s)=\int_{i\in\mathcal{N}^{s}_{z}}\mathbbm{1}_{(act(i)=a)}dm(i)$. Similar to NCG, joint action is the distribution of masses of agents selecting available actions in each local state, i.e. for state $s$, $\bm{a}=((f^{a}_{z})_{a\in\mathcal{A}_{z}})_{z\in\mathcal{Z}}\text{ such that }\sum_{a\in\mathcal{A}_{z}}f^{a}_{z}=m(\mathcal{N}^{s}_{z})\forall z$.

• $\mathcal{R}$

  : is the reward function¹¹1“cost” is often used in context of NCG. To be consistent with MARL literature we use the term “reward”., which can be assumed as negative of cost function of NCGs. The total mass of agents selecting action $a$ for a joint action $\bm{a}$ in state $s$ is given by $\phi^{a}(s,\bm{a})=\sum_{z=1}^{|\mathcal{Z}|}f^{a}_{z}(s)$. $\phi(s,\bm{a})$ refers to the vector of mass of agents selecting different actions. Similar to the cost functions in NCG, the reward function (-ve of cost) is assumed to be a non-increasing continuous function.

  Depending on whether the congestion being represented is in source state of agent (node) or on the edge between two states, we have two possible reward cases of relevance in aggregation systems:

  • R1

    : Reward dependent only on joint state, local state and joint action, i.e., $R_{z}(s,\phi(s,\mathbf{a}))$. An example of this type of reward function would be referring to congestion at attractions in theme parks and individuals (agents) are minimizing their overall wait times.

  • R2

    : Reward dependent on joint state, local state, joint action and local action, i.e., $R_{z}(s,\phi^{a}(s,\mathbf{a}))$. This is useful in representing congestion related to traffic on roads. An example would be congestion on roads, where individual drivers are trying to reach their destination in the least time.

• $\mathcal{T}$

  : $\mathcal{T}(s^{\prime}|s,\bm{a})$ is the transitional probability of global states²²2Considering local transitions is simpler, as global transition can be computed from local transitions. given joint actions. Similar to reward function, transition of global state is also dependent on the total mass of agents selecting different actions in state $s$.

In SNCG, each state is an instance of NCG where agents in a local state select actions available to them and the environment moves to the next state (another instance of NCG). Also, as the same set of actions are available to all the agents present in a given local state, agents present in the local state can be considered as agents of same population type. Figure 1b represents state transition from global state $s$ to $s^{\prime}$ for a simple grid-world with 2 zones $z_{1}$ and $z_{2}$ and total mass of agents is 1. The number in the grid represents mass of agents present in that zone, i.e. $s=<0.2,0.8>$ and $s^{\prime}=<0.4,0.6>$. Each zone has two feasible actions, $a^{st}$ = stay in the current zone and $a^{mv}$ = move to the next zone, i.e. $\mathcal{A}_{1},\mathcal{A}_{2}=\{a^{st},a^{mv}\}$. From NCG point of view, state $s$ is an NCG with 0.2 mass of agents of population type $z_{1}$ and 0.8 mass of agents of population type $z_{2}$. Similarly, $s^{\prime}$ can be viewed as an NCG with 0.4 mass of agents of type $z_{1}$ and 0.6 mass of agents of type $z_{2}$. Suppose 0.1 mass of agents in $z_{1}$ chose to stay and remaining chose to move to $z_{2}$. Similarly, 0.48 mass of agents in $z_{2}$ selected to stay whereas remaining agents selected action $a^{mv}$ and due to transition uncertainty, the environment moves to $s^{\prime}$. The joint action (which is continuous) of the agents is given by $\bm{a}=((0.1,0.1),(0.48,0.32))$.

The policy of agent $i$ is denoted by $\pi_{i}$. We observe that given a global state $s$, an agent will play different policies based on its local state $z$ as the available actions for local states are different. Hence, $\pi_{i}$ can be represented as $\pi_{i}=(\pi_{iz}(s))_{s\in\mathcal{S},z\in\mathcal{Z}}\text{ such that}\sum_{a\in\mathcal{A}_{z}}\pi_{iz}(a|s)=1$. We define $\Pi_{z}$ as the set of policies available to an agent in local state $z$, hence, $\pi_{iz}(s)\in\Pi_{z}\forall i\in\mathcal{N}^{s}_{z},\forall s\in\mathcal{S}$. $\bm{\pi}=(\pi_{i})_{(i\in\mathcal{N})}$ is the joint policy of all the agents.

Let $\gamma$ be the discount factor. The value of agent $j$ for being in local state $z$ given the global state is $s$ and other agents are following policy $\bm{\pi}_{-j}$ is given by (for the R2 reward case):

The goal is to compute an equilibrium joint strategy, where no individual agent has an incentive to unilaterally deviate.

In this section, we show that values of agents in the same local state have either equal or close to equal values at equilibrium. We begin with the case of non-atomic agents and then move to the case with large number of agents and where mass of an agent is non-zero. Due to space constraints, we only provide proof sketches and the detailed proofs are provided in the appendix.

Given the propositions in section Properties of equilibrium in SNCG for SNCGs, we hypothesize that values of all the agents present in any local state are equal at equilibrium (even for reward case R2) when there are a large number of agents with minor contributions from each agent (nearly non-atomic agents). This translates to having zero variance³³3We have used zero variance as an indicative of equal values of agents in the paper, however, other measures such as standard deviation can also be used for the same purpose. in individual agent values at each local state, while individual agents are playing their best responses. Please note that a joint policy which yields equal values in local states is an equilibrium policy only if agents are also playing their best response strategy. This is the key idea of our LVMQ approach and is an ideal insight for approximating equilibrium solutions in aggregation systems. The centralized entity can focus on ensuring values of agents in same local states are (close to) equal by estimating a joint policy which minimizes variance in values, while the individual suppliers can focus on computing best response solutions. During learning phase, the role of the

• $\bullet$

  Central entity is to ensure that the exploration of individual agents moves towards a joint policy where the variance in values of agents in a local state is minimum.

• $\bullet$

  Individual agents is to learn their best responses to the historical behaviour of the other agents based on guidance from central entity.

We perform experiments on three different domains, taxi simulator based on real-world and synthetic data set (Verma, Varakantham, and Lau 2019; Verma and Varakantham 2019), a single stage packet routing (Krichene, Drighes, and Bayen 2014) and multi-stage traffic routing (Wiering 2000). In all these domains a central agent that can assist (or provides guidance to) individual agents in approximating equilibrium policies is present. MARL strategy is suitable for these domains as these are large multi-agent systems where model based planning is not scalable. For taxi domain, we do not compare with other aggregation system related methods (Shah, Lowalekar, and Varakantham 2020; Lowalekar, Varakantham, and Jaillet 2018; Liu, Li, and Wu 2020) as these methods focus on joint value and disregard the fact that the individual drivers are self-interested. Different from these methods, we focus on learning from individual drivers’ perspective while considering that other drivers are also learning simultaneously.

We compare with four baseline algorithms: Independent Learner (IL), NFSP (Heinrich and Silver 2016), MFQ (Yang et al. 2018) and MAAC (Lowe et al. 2017). IL is a traditional Q-Learning algorithm that does not consider the actions performed by the other agents. Similar to LVMQ, MFQ and MAAC are also CTDE algorithms and they use joint action information at the time of training. However, NFSP is a self play learning algorithm and learns from individual agent’s local observation. Hence, for fair comparison, we provide joint action information to NFSP as well. As mentioned by (Verma and Varakantham 2019), we also observed that the original NFSP without joint action information performs worse that NFSP with joint action information. In LVMQ, the central agent learns from the collective experiences of the individual agents and suggests individuals based on this learning, whereas other algorithms receive information only about the joint action. This is one of the reasons of LVMQ performing better than other algorithms.

For decentralized learning, ideally each agent should maintain their own neural network. However, simulating thousands of learning agents at the same time requires extensive computational resources hence, we simulated 1000 agents by using 100 neural networks with 10 agents sharing a single network (providing agent id as one of the input to the network). Letting agents share a single network while providing agent id to the network is common when decentralized learning is done for a large number of agents (Yang et al. 2017, 2018). For all the individual agents, we performed $\epsilon$-greedy exploration and it was decayed exponentially. Training was stopped once $\epsilon$ decays to 0.05. We experimented with different values of aniticipatory parameter for NFSP and 0.1 provided us the best results. The results are average over runs with 5 different random seeds.

We propose a Stochastic Non-atomic Congestion Games (SNCG) model to represent anonymity in interactions and infinitesimal contribution of individual agents for aggregation systems. We show that the values of all the agents present in a local state are equal at equilibrium in SNCG. Based on this property we propose LVMQ which is a CTDE algorithm to learn approximate equilibrium policies in cases with finite yet large number of agents. Experimental results on multiple domains depict that LVMQ learns better equilibrium policies than other state-of-the-art algorithms.

In this section, we show that values of agents in the same local state have either equal or close to equal values at equilibrium. We begin with the case of non-atomic agents and then move to the case with large number of agents and where mass of an agent is non-zero.

Algorithm 1 provides detailed steps of LVMQ.