Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systems

Multi-Agent Reinforcement Learning, or MARL for short, considers a reinforcement learning problem where multiple agents interact with each other and with the environment to finish a common task or achieve a common objective. The key difference between MARL and single-agent RL is that each agent in MARL only observes a subset of the state and receives an individual reward and does not have global information. Examples include multi-access networks where each user senses the collision locally, but needs to coordinate with each other to maximize the network throughput, or power control in wireless networks where each wireless node can only measure its local interference but they need to collectively decide the transmit power levels to maximize a network-wide utility, or task offloading in edge computing where each user observes its local quality of service (QoS) but they coordinate tasks offloaded to edge servers to maintain a high QoS for the network, or a team of robots where each robot can only sense its own surrounding environment, but the robot team needs to cooperate and coordinate for accomplishing a rescue task.

MARL raises two fundamental aspects that are different from single-agent RL. The first aspect is the policy space (the set of policies that are feasible) is restricted to local policies since each agent has to decide an action based on information available to the agent. The second aspect of MARL is that while distributed learning, e.g. distributed policy gradient, is desired, it is impossible in general MARL because an agent does not know the global state and rewards. One popular approach to address the second issue is the centralized learning and distributed execution paradigm [8], where data samples are collected by a central entity and the central entity uses data from all agents to learn a local policy. Therefore, the learning occurs at the central entity, but the learned policy is a local policy.

In this paper, we consider a special class of MARL, which we call REward-Coupled Multi-Agent Reinforcement Learning (REC-MARL). In REC-MARL, the problem is coupled through the reward functions. More specifically, the reward function of agent $n$ depends on agent $n$’s state and action and its neighbors’ states and actions. However, the next state of agent $n$ only depends on agent $n^{\prime}$s current state and action, and is independent of other agents’ states and actions. In contrast, in general MARL, the transition kernels of the agents are coupled, so the next state of an agent depends on other agents’ states and actions.

While REC-MARL is more restrictive than MARL, a number of applications of MARL are actually REC-MARL. In wireless networks, where agents are network nodes or devices, and the state of an agent is could be its queue length or transmit power, the state only depends on an agent’s current state and its current action (see Section 2 for detailed description). For REC-MARL, this paper proposes distributed policy gradient algorithms and establish the local convergence (i.e. the algorithms achieve a stationary policy). The main contributions are summarized as follows.

• •

  We establish perfect decomposition of value functions and policy gradients in Lemmas 1 and 2, respectively, where we show that the global value functions (policy-gradients) can be written as a summation of local value functions (policy gradients). This decomposition significantly reduces the complexity of value functions and motivates our distributed multi-agent policy gradient algorithms.

• •

  We propose a Temporal-Difference (TD) learning based regularized distributed multi-agent policy gradient algorithm, named TD-RDAC in Algorithm 2. We proved in Theorem 2 that TD-RDAC achieves the local convergence with the rate $\tilde{O}\left(NS_{\max}A_{\max}/\sqrt{T}\right),$ which only depends on the maximum sizes of local state and action spaces, instead of the sizes of the global action and state spaces.

• •

  We apply TD-RDAC to the applications of real-time access and power control in ad hoc wireless networks, both are well-known challenging networking resource management problems. Our experiments show that TD-RDAC significantly outperforms the state-of-the-art algorithm [20] and well-known benchmarks [2, 21] in these two applications.

We consider a multi-agent system where the agents are connected by an interactive graph $\mathcal{G}=(\mathcal{I},\mathcal{E})$ with $\mathcal{I}$ and $\mathcal{E}$ being the set of nodes and edges, respectively. The system consists of $N=|\mathcal{I}|$ agents who are connected with edges in $\mathcal{E}.$ Each agent $n\in\mathcal{I}$ is associated with a $\gamma$-discounted Markov decision process of $(\mathcal{S}_{n},\mathcal{A}_{n},r_{n},\mathcal{P}_{n},\gamma),$ where $\mathcal{S}_{n}$ is the state space, $\mathcal{A}_{n}$ is the action space, $r_{n}$ is the reward function, and $\mathcal{P}_{n}$ is the transition kernel. Define the neighbourhood of agent $n$ (including itself) to be $\mathcal{N}(n).$ Define the states and actions of the neighbors of agent $n$ to be $s_{\mathcal{N}(n)}$ and $a_{\mathcal{N}(n)},$ respectively. We next formally define the REward-Couple Multi-Agent Reinforcement Learning.

REC-MARL: The reward of agent $n$ depends on its neighbors’ states and actions $r_{n}(s_{\mathcal{N}(n)},a_{\mathcal{N}(n)}).$ The transition kernel of agent $n,$ $\mathcal{P}_{n}(\cdot|s_{n},a_{n}),$ only depends on its own state $s_{n}$ and action $a_{n}.$ Agent $n$ uses a local policy $\pi_{n}:\mathcal{S}_{n}\to\mathcal{A}_{n},$ where $\pi_{n}(a_{n}|s_{n})$ is the probability of taking action $a_{n}$ in state $s_{n}.$

Given a REC-MARL problem, the global state space is $\mathcal{S}=\mathcal{S}_{1}\times\mathcal{S}_{2}\times\cdots\times\mathcal{S}_{n}$ with $S_{\max}=\max_{n}|\mathcal{S}_{n}|;$ the global action space is $\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}\times\cdots\times\mathcal{A}_{n}$ with $A_{\max}=\max_{n}|\mathcal{A}_{n}|;$ the global reward function is $r(s,a)=\frac{1}{N}\sum_{n=1}^{N}r_{n}(s_{\mathcal{N}(n)},a_{\mathcal{N}(n)});$ the transition kernel is $\mathcal{P}(s^{\prime}|s,a),\forall s,s^{\prime}\in\mathcal{S},\forall a\in\mathcal{A}$ with $\mathcal{P}(s^{\prime}|s,a)=\prod_{n=1}^{N}\mathcal{P}_{n}(s^{\prime}_{n}|s_{n},a_{n}).$

In this paper, we study the softmax policy parameterized by $\theta_{n}:\mathcal{S}_{n}\times\mathcal{A}_{n}\to\mathbb{R}$ that is

The global policy $\pi_{\theta}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ with $\theta=[\theta_{1},\theta_{2},\cdots,\theta_{N}]$ is as follows

In this paper, we study $\gamma$-discounted infinite-horizon Markov decision processes (MDP) with $(s(t),a(t))$ being the state and action of the MDP at time $t.$ For a global policy $\pi_{\theta},$ its value function, action value function ($Q$-function), and advantage function given the initial state and action ($s(0),a(0)$) are defined below:

Let $\rho$ be the initial state distribution. Define $V^{\pi_{\theta}}(\rho)=\mathbb{E}_{s\sim\rho}[V^{\pi_{\theta}}(s)].$ Further define the discounted occupancy measure to be

We seek policies with distributed learning and distributed execution in this paper. We will decompose the global $Q$-function as a sum of local $Q$-functions so that the agents can collectively optimize the local policy. Before presenting the details of our solution, we introduce two representative applications in wireless networks: real-time access control and distributed power control.

Real-time access control in wireless networks: Consider a wireless access network with $N$ nodes (agents) and $M$ access points as shown in Figure 1(a). At the beginning of each time slot, a packet arrives at node $n$ with probability $w_{n}$. The packet is associated with deadline $d.$ $q_{m}$ is the successful transmitting probability when transmitting to access point $m.$ A packet is removed if either it is sent to an access point (not necessarily delivered successfully) or it expires. At each time, each node decides whether to transmit a packet to one of the access points or keeping silence. A collision happens if multiple nodes send packets to the same access point simultaneously. Therefore, the throughput of a node depends not only on its decision but also its neighboring nodes’ decisions. In particular, the throughput of node $n$ is

where $a_{n,m}\in\{0,1\}$ indicate if node $n$ transmits a packet to its access point $m\in\mathcal{AC}(n).$ The goal of real-time access control is to maximize the network throughput.

The problem of real-time access control is challenging because i) the throughput functions are non-convex and highly-coupled functions of other nodes’ decisions and ii) the system parameters are unknown (e.g., $w_{n}$ and $p_{m}$). This problem can be formulated as a REC-MARL problem. In particular for node/agent $n,$ the MDP formulation is $(Q_{n},a_{n},r_{n}(a_{\mathcal{N}(n)}),Q^{\prime}_{n}):$ the state of agent $n$ is the queue length $Q_{n}=\{Q_{n}^{l}\}_{l}$ with $Q_{n}^{l}$ being the number of packets with the remaining time $l$ ; the action is $a_{n,m}$ with $m\in\mathcal{A}P(n)$ (one of access point of agent $n$); $r_{n}(a_{\mathcal{N}(n)})$ is the reward for agent $n;$ $Q^{\prime}_{n}$ is its next queue state.

Distributed power control in wireless network: The other application of REC-MARL is distributed power control in wireless networks. Consider a network with $N$ wireless links (agents) as shown in Figure 1(b). Each link can control the transmission rate by adapting its power level, and neighboring links interfere with each other. Therefore, the transmission rate of a link depends not only on its transmit power but also its neighboring links’ transmit power. In particular, the reward/utility of link $n$ is its transmission rate minus a linear power cost:

where $G_{m,n}$ is the channel gain from node $m$ to $n,$ $p_{n}$ is the power of node $n,$ $\sigma_{n}$ is the power of noise at user $n,$ and $u_{n}$ are the trade-off parameters. The goal of distributed power control to maximize the total rewards for the network.

The distributed power control is also challenging because the reward function is non-convex and highly-coupled, and the channel condition is unknown and dynamic. This problem can also be formulated as a REC-MARL problem. In particular for link/agent $n,$ the MDP formulation is $(p_{n},a_{n},r_{n}(p_{\mathcal{N}(n)}),p^{\prime}_{n}):$ the state of agent $n$ is the power level $p_{n}\in\mathbb{Z}^{+}$ with $p_{n}\leq p_{\max}$ ($p_{\max}$ is the maximum power constraint); the action is $a_{n}\in\{0,-1,+1\}$ (keep, decrease, or increase the power level by one); $r_{n}(p_{\mathcal{N}(n)})$ is the reward for agent $n;$ $p^{\prime}_{n}$ is the next power level.

In the following, we present distributed multi-agent reinforcement learning algorithms that can be used to solve these two problems and show that our algorithm outperforms the existing benchmarks.

To implement a paradigm of distributed learning and distributed execution, we first establish the decomposition of value and policy gradient functions in Lemma 1 and Lemma 2, respectively. The value and policy gradient functions could be represented locally and computed/estimated via exchange information with their neighbors.

In this section, we introduce distributed policy gradient based algorithms (DPG) for the multi-agent system. Before introducing the algorithms, we assume that the initial state distribution $\mu$ induced by our policy is strictly positive:

This assumption imposes the sufficient exploration for the state space for each agent and is common in the literature [1, 15]. We first propose a regularized distributed policy gradient algorithm assuming the access of an inexact gradient, and then introduce TD-learning methods to estimate the gradient.

In this section, we evaluate TD-RDAC for real-time access control problem and distributed power control problem in wireless networks as described in Section 2.

In our experiment, we considered two types of network topology: a line network and a grid network as shown in the lefthhand side of Figure 2. The tabular method is used to represent value functions since the size of the table is tractable in this experiment.

The line network has $6$ nodes and $5$ access points as shown in the left-up of Figure 2. We considered two settings in the line network with the same arrival probability but distinct success transmission probabilities to represent reliable/unreliable environments. Specifically, the arrival probabilities are $w=[0.5,0.3,0.5,0.5,0.3,0.5];$ the transmission probabilities of the reliable/unreliable environments are $q=[0.9,0.95,0.9,0.95,0.9]$ and $q=[0.5,0.6,0.7,0.6,0.5],$ respectively. The deadline of packets is $d=2.$ We ran $9$ different instances with different random seeds and the shaded region represents the $95\%$ confidence interval. We observe our algorithm increases steady in Figures 3(a) and 3(b) and outperforms both SAC algorithm in [20] and ALOHA algorithm in the reliable and unreliable environment, where the converged rewards of (our algorithm v.s. SAC v.s. ALOHA) are ($0.814$ v.s. $0.735$ v.s. $0.334$) and ($0.503$ v.s. $0.464$ v.s. $0.222$) for the reliable and unreliable environment, respectively.

The grid network is similar as in [20], shown in the left-bottom of Figure 2. The network has $36$ nodes and $25$ access points. The arrival probability $w_{n}$ of node $n$ and success transmission probability $q_{m}$ of access point $m$ are generated uniformly random from $[0,1].$ The deadline of packets is also set $d=2.$ We observe our algorithm again increases steady in Figure 3(c) even with the relatively dense environment and outperforms both SAC algorithm in [20] and ALOHA algorithm [21], where the converged rewards of (our algorithm v.s. SAC v.s. ALOHA) are ($0.393$ v.s. $0.369$ v.s. $0.138$).

For the reward/utility in (3), we set $G_{n,n}=1$ and $G_{m,n}=\kappa/({dist}_{m,n})^{2}$ with $\kappa=0.1$ as the fading factor and ${dist}_{m,n}$ is the distance between nodes $m$ and $n.$ The average power of the noise is $\sigma_{n}=0.1.$ We set the trade-off parameter $u_{n}=0.1,\forall n.$ For each environment, we ran $9$ different instances with different random seeds and the shaded region represents the $95\%$ confidence interval.

For $6$-nodes network, we represent value functions with tables in Algorithm 2. We observe the learning processes are quite stable in Figure 4(a). We observe our algorithm outperforms the SAC and DPC algorithm as the training time increases: the converged reward are ($17.60$ v.s. $17.43$ v.s. $16.77$). For 9-nodes , we approximate value functions with neural networks in Algorithm 2. We observe Algorithm 2 outperforms the SAC and DPC algorithms as the training time increases in Figure 4(b) ($28.92$ v.s. $28.76$ v.s. $27.64$). For 25 nodes, Figure 4(c) shows the results with a heterogeneous topology. Again, we observe our algorithm increases steady in Figure 4(c) and outperforms the SAC and DPC algorithms ($98.35$ v.s. $95.70$ v.s. $95.34$).

Finally, we note that both ALOHA and DPC algorithms are model-based algorithm and the agents need to know the systems parameters (success transmitting probability in the real-time access control problem and channel gains and interference levels in the power control problem) while our algorithm is model-free and does not need to know these parameters.

In this paper, we studied a weakly-coupled multi-agent reinforcement learning problem where agents’ reward functions are coupled but the transition kernels are not. We propose TD-learning based regularized multi-agent policy actor-critic algorithm (TD-RDAC) that achieve the local convergence result. We demonstrated the effectiveness of TD-RDAC with two important applications in wireless networks: real-time access control and distributed power control and showed that our algorithm outperforms the existing benchmarks in the literature.