Convergence Rates of Bayesian Network Policy Gradient for Cooperative Multi-Agent Reinforcement Learning

Authors: dingyang  chen
zhenyu  zhang
xiaolong  kuang
xinyang  shen
ozalp  ozer
qi  zhang
Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-08-27 23:19:03

Abstract: Human coordination often benefits from executing actions in a correlated manner, leading to improved cooperation. This concept holds potential for enhancing cooperative multi-agent reinforcement learning (MARL). Despite this, recent advances in MARL predominantly focus on decentralized execution, which favors scalability by avoiding action correlation among agents. A recent study introduced a Bayesian network to incorporate correlations between agents' action selections within their joint policy, demonstrating global convergence to Nash equilibria under a tabular softmax policy parameterization in cooperative Markov games. In this work, we extend these theoretical results by proving the convergence rate of the Bayesian network joint policy with log-barrier regularization.

Main paper: 
 introduction: 
 Cooperative multi-agent reinforcement learning (MARL) enables autonomous agents to collectively maximize their utility, offering promising applications in areas such as traffic control [1] , coordination of multi-robot systems [2] , and power grid management [3] . However, the joint action space in MARL grows exponentially with the number of agents, posing scalability challenges. To mitigate this, many approaches rely on product policies, where each agent independently selects its action based on its observations. While this simplifies decision-making, it can lead to suboptimal outcomes in cooperative tasks-consider a group of drones performing a synchronized search mission. If each drone acts independently without considering the actions of others, they might overlap in their search areas, wasting resources. In contrast, acting sequentially, where each drone's actions depend on the others, can significantly improve efficiency and coverage. The key research question is how to introduce correlations in multi-agent policies without exacerbating scalability issues. A promising solution is to use a Bayesian network (BN) to capture essential dependencies among agents. This paper provides a theoretical justification on why action dependencies are beneficial.Recent work has focused on addressing this challenge within Cooperative Markov Games (MGs), a key subclass of Markov games where agents share the same reward function. Policy gradient methods have been shown to converge to Nash policies under product joint policies, with guarantees in tabular settings using both direct [4] and softmax parameterization [5, 6] . However, while product policies offer scalability, they may incur suboptimality for the learned joint policy. To overcome the limitations of product joint policies, a recent advance [7] has introduced the use of Bayesian networks to capture correlations among agents' actions. This approach has demonstrated global convergence to Nash equilibria under a tabular softmax policy parameterization. Nonetheless, challenges remain: these methods lack convergence rate analysis and do not achieve optimality as shown in the single-agent setting, particularly when using dense Bayesian networks that can factorize any joint policy, thereby behaving similarly to the single-agent setting [8] . In this paper, we address these gaps by providing a theoretical justification for the benefits of action dependencies in multi-agent policies, along with a convergence rate analysis using log-barrier regularization. Our results show that it is possible to achieve optimality with a dense Bayesian network, offering a promising direction for improving the performance of cooperative MARL systems. 
preliminaries: 
 Cooperative Markov Game. We consider a cooperative Markov game (MG) ⟨N , S, A, P, r, µ⟩, involving N agents indexed by i ∈ N = {1, . . . , N }. The game consists of a state space S, a joint action space A = A 1 × • • • × A N , a transition function P : S × A → ∆(S), a shared team reward function r : S × A → R, and an initial state distribution µ ∈ ∆(S). Here, ∆(X ) denotes the set of probability distributions over X . We assume full observability, meaning each agent observes the global state s ∈ S. Under this assumption, a general joint policy π : S → ∆(A) maps states to distributions over the joint action space. Given the exponential growth of A with N , the commonly used subclass is the product policy, π = (π 1 , . . . , π N ) : S → × i∈N ∆(A i ), where the joint policy is factored as a product of local policies π i : S → ∆(A i ), such that π(a|s) = i∈N π i (a i |s). The discounted return from time step t is defined as G t = ∞ l=0 γ l r t+l , where r t := r(s t , a t ) is the team reward at time step t. The joint policy π induces the value function V π (s t ) = E st+1:∞,at:∞∼π [G t |s t ] and the action-value functionQ π (s t , a t ) = E st+1:∞,at+1:∞∼π [G t |s t , a t ]. The cumulative team reward, starting from s 0 ∼ µ, is denoted as V π (µ) := E s0∼µ [V π (s 0 )].The (unnormalized) discounted state visitation measure under policy π, starting at s 0 ∼ µ, is given by:d π µ (s) := E s0∼µ ∞ t=0 γ t Pr π (s t = s|s 0 ) ,where Pr π (s t = s|s 0 ) is the probability of being in state s t = s at time t when starting from s 0 and following π. Since all agents share the team reward, the objective in cooperative MARL, as in single-agent RL, is to optimize the joint policy to maximize its value, i.e., max π V π (µ). We now define the concepts of ϵ-Nash and ϵ-optimal policies. Definition 1 (ϵ-Nash Policy). The Nash-gap of a policy π is defined as:Nash-gap(π) := max i max πi V πi ,π -i (µ) -V π (µ) .A product policy π = (π 1 , . . . , π N ) is an ϵ-Nash policy if Nash-gap(π) ≤ ϵ. Definition 2 (ϵ-Optimal Policy). The optimality-gap of a policy π is defined as:optimality-gap(π) := max π * V π * (µ) -V π (µ)A policy π is an ϵ-optimal policy if optimality-gap(π) ≤ ϵ. 
bayesian network joint policy: 
 In this work, we focus on a class of joint policies introduced in [7] that extends beyond product policies by incorporating action dependencies through a Bayesian network (BN). A BN is represented by a directed acyclic graph (DAG) G = (N , E), where N is the set of vertices (agents), and E ⊆ {(i, j) : i, j ∈ N , i ̸ = j} is the set of directed edges. The parents of an agent i are denoted by P i := {j : (j, i) ∈ E}, and their actions are a P i ∈ × j∈P i A j , as illustrated in Figure 3 . Under full observability, a BN (joint) policy (π, G) = (π 1 , . . . , π N , G) : S → ∆(A) is defined, where each local policy π i : S × (× j∈P i A j ) → ∆(A i ) depends on both the global state and the actions of its parents. The joint action a = (a 1 , . . . , a N ) is then sampled as π(a|s) = i∈N π i (a i |s, a P i ). In this formulation, each local policy π i is parameterized using a tabular softmax function:θ i = θ i s,a P i ,a i ∈ R : s ∈ S, a P i ∈ × j∈P i A j , a i ∈ A i ,leading to the induced softmax local policy:EQUATIONwith the BN policy parameterized as π θ = (π 1 θ 1 , . . . , π N θ N ). In Lemma 1, we derive the policy gradient for the BN policy as parameterized in Equation ( 1), which will be used to establish our convergence results in this section.We also introduce several shorthand notations. For a subset M ⊆ N of agents and its complement -M, a joint action is decomposed as a = (a M , a -M ). The conditional policy for a M is defined as:π M (a M |s, a -M ) := π(a M , a -M |s) āM π(ā M , a -M |s).The corresponding action-value function is:Q π (s, a M ) := E a -M ∼π -M (•|s,a M ) Q π (s, a M , a -M ) .Let P i + := P i ∪ {i} denote the set of agent i and its parents. We will also use the abbreviations V π θ and Q π θ as V θ and Q θ , respectively.Note that for BN joint policy, the notion of ϵ-Nash policy and ϵ-optimal policy still hold. 
learning dynamics 4.1 policy gradient dynamics with log-barrier regularization: 
 Building on the method in the single-agent setting [8] , we introduce a log-barrier regularized objective, detailed below, to provide finite-time convergence guarantees for policy gradient dynamics:L λ (θ) :=V θ (µ) -λ N i=1 E s,a P i ∼Unif S×A P i KL(Unif A i , π θ (•|s, a P i )) =V θ (µ) + λ N i=1s,a P i ,a i log π i θ i (a i |s,a P i )|S||A P i ||A i | + log |A i |where the log barrier regularization, i.e., the KL divergence with respect to the uniform actionselection distribution, is applied to each agent's policy independently. Lemma 1 (Tabular softmax BN policy gradient form with log-barrier regularization, proof in Appendix A). For the tabular softmax BN policy parameterized as in Equation ( 1), we have:∂L λ (θ) ∂θ i s,a P i ,a i = 1 1 -γ d π θ µ (s, a P i )π i θ i (a i |s, a P i )A i θ (s, a P i , a i ) + λ |S||A P i | 1 |A i | -π i θ i (a i |s, a P i )whered π θ µ (s, a P i ) := d π θ µ (s) a -P i π θ (a -P i , a P i |s), A i θ (s, a P i , a i ) := Q θ (s, a P i + ) -Q θ (s, a P i ).The policy gradient form with log-barrier regularizer in Lemma 1 generalizes its counterpart for single-agent policies [8] and for multi-agent product policies [5, 6] under the tabular softmax policy parameterization, which enables us to extend the convergence results to the BN joint policies. Below we state the assumptions used in the convergence results for product policies [5, 6] . Assumption 1. For any π and any state s of the Markov game, d π µ (s) > 0. Assumption 2 (Reward function is bounded). The reward function r is bounded in the range [r min , r max ], such that the value function V is bounded asV min ≤ V π (s) ≤ V max ∀s, π.We next present our finite-time convergence results for standard policy gradient dynamics with log-barrier regularization in Section 4.2, with proofs in the appendix A.In Theorem 1, we establish, under the tabular softmax BN policy parameterization, the finite time convergence to a near-Nash policy in a coopertaive MGs of the standard policy gradient dynamics (with log-barrier regularization):EQUATIONwhere η is the fixed stepsize and the update is performed by every agent i ∈ N .For each agent i, parent actions a P i , and local action a i , Equation (2) becomesEQUATIONLemma 2. ((Log barrier regularization's approximate first-order stationary points are near-Nash, proof in Appendix A.2) Suppose θ is such that∥∇ θ L λ (θ)∥ 2 ≤ λ/(2|S||A| max i |A i |). Then the BN (joint) policy π θ = (π 1 θ 1 , ..., π N θ N , G) is a 2λM -Nash policy where M := max π,π ′ d π µ d π ′ µ ∞, which is well-defined by Assumption 1.Lemma 2 extends the results in [8] in the single-agent setting, and the results in [5, 6] in the multiagent setting with an uncorrelated uncorrelated product policy, stating that, with the log barrier regularization, approximate first-order stationary points in a BN policy are near-Nash. With Lemma 2, we establish the convergence rate as stated in Theorem 1.Theorem 1 (Convergence rate of the BN policy gradient with log-barrier regularization, proof in Appendix A). Under Assumptions 1 and 2, suppose every agent i follows the policy gradient dynamics (2), which results in the update dynamics (3) for each each agent i, parent actions a P i , and local action a i , with η ≤ 1 β λ , then we have min t<T Nash-gap t ≤ ϵ wheneverT ≥ 256N M 2 |S| 2 max i |A i | 2 (r max -r min ) 2 (1 -γ) 4 ϵ 2 + 32λM |S| max i |A i | 2 i 1 |A P i | (r max -r min ) (1 -γ)ϵ where β λ = 8N (rmax-rmin) (1-γ) 3 + i 2λ |S||A P i | is an upper bound on the smoothness of L λ (θ).The main trick is to view the parent actions a P i as part of the state, so that d π θ µ (s, a P i ) becomes the new state visitation measure for the augmented state (s, a P i ). With this transformation, the update dynamics in 1 is similar to the ones for the product policy,i.e., G := (N , ∅), and thus generalize the results to the BN policy.With the help of a log-barrier regularizer, we establish convergence to the optimal joint policy with a dense Bayesian network in Theorem 2, an outcome not achieved in [7] . This regularizer ensures that every action has a positive and bounded probability of selection, which is crucial for the sufficient coverage of parent actions and achieving optimality. Definition 3 (Fully-correlated BN policy). A BN policy (π, (N , E)) is fully-correlated if |E| = N (N -1)/2, the maximum number of edges in a BN. Lemma 3. ((Fully-correlated BN policy with Log barrier regularization's approximate first-order stationary points are near-optimal, proof in Appendix A.4) Suppose θ is such that∥∇ θ L λ (θ)∥ 2 ≤ λ/(2|S||A| max i |A i |). Then the BN (joint) policy π θ = (π 1 θ 1 , ..., π N θ N , G) is a 2 N +1 N λM -optimal policy where M := max π,π ′ d π µ d π ′ µ ∞, which is well-defined by Assumption 1.Theorem 2 (Convergence rate of the fully-correlated BN policy gradient with log-barrier regularization, proof in Appendix A.5). Under Assumptions 1 and 2, suppose every agent i follows the policy gradient dynamics (2) , which results in the update dynamics (3) for each each agent i, parent actions a P i , and local action a i , with η ≤ 1 β λ , then we have min t<T optimality-gap t ≤ ϵ wheneverT ≥ 2 N +8 N 3 M 2 |S| 2 |A| 2 max i |A i | 2 (r max -r min ) 2 ϵ 2 (1 -γ) 4 + 8N M |S||A| 2 max i |A i | 2 (r max -r min ) i 1 |A P i | ϵ(1 -γ)whereβ λ = 8N (rmax-rmin) (1-γ) 3 + i 2λ |S||A P i |is an upper bound on the smoothness of L λ (θ). 
limitations: 
 This work primarily focuses on the theoretical aspects of Bayesian network joint policies without exploring their integration with standard MARL algorithms for practical applications. [7] shows that V θ is 8N (rmax-rmin) (1-γ) 3 -smooth. From the perspective of the augumented state, the Lemma D.4 in [8] becomes that the regularizer for each agent i is 2λ2 Lemma 4. L λ (θ) is β λ -smooth, where β λ = 8N (rmax-rmin) (1-γ) 3 + i 2λ |S||A P i | Proof. Lemma A.3 in|S||A P i | -smooth. Thus, β λ = 8N (rmax-rmin) (1-γ) 3 + i 2λ |S||A P i |is an upper bound on the smoothness of L λ (θ).Proof.EQUATION-EQUATIONAccording to lemma 5.1 in [7] ,(1) = 1 1 -γ d π θ µ (s, a P i )π i θ i (a i |s, a P i )A i θ (s, a P i , a i )By the definition of KL Divergence,(2) = ∂ λ N i=1 E s,a P i ∼Unif S×A P i λ N i=1s,a P i ,a i log π i θ i (a i |s,a P i )|S||A P i ||A i | + log |A i | ∂θ i s,a P i ,a i = - λ |S||A P i | 1 |A i | -π i θ i (a i |s, a P i ) Therefore, ∂L λ (θ) ∂θ i s,a P i ,a i = (1) -(2) = 1 1 -γ d π θ µ (s, a P i )π i θ i (a i |s, a P i )A i θ (s, a P i , a i ) + λ |S||A P i | 1 |A i | -π i θ i (a i |s, a P i ) A.2 Proof of lemma 2Proof. The proof extends the proof of Theorem 5.2 in [8] by the usage of the multi-agent performance difference lemma (Lemma C.1 in [4] ).Similar to the proof of Theorem 5.2 in [8] , we can bound A i θ (s, a i ) ≤ for any (s, a i )-pair. It suffices to bound A i θ (s, a i ) for any (s, a i ) whereA i θ (s, a i ) ≥ 0 (else A i θ (s, a i ) ≤ is trivially true): λ/(2|S||A| max j |A j |) ≥ λ/(2|S||A P i ||A i |) =: ϵ opt ≥ ∂L λ (θ) ∂θ i s,a P i ,a i (i) = 1 1 -γ d π θ µ (s, a P i )π i θ i (a i |s, a P i )A i θ (s, a P i , a i ) + λ |S||A P i | 1 |A i | -π i θ i (a i |s, a P i ) ≥ λ |S||A P i | 1 |A i | -π i θ i (a i |s, a P i )where the last inequality is due to A i θ (s, a P i , a i ) ≥ 0, and by rearranging we getEQUATIONSolving (i) for A i θ (s, a P i , a i ), we haveEQUATIONWe are now ready to use the multi-agent performance difference lemma on two BN joint policy with only agent i's parameters changed. For convenience, denote a -P i π θ (a -P i , a P i |s) asπ P i θ (•|s) so that d π θ µ (s, a P i ) = d π θ µ (s)π P i θ (•|s). ∀i ∈ N , let θ ′ * = [θ -i * , θi * ]be the parameters of any joint policy where only agent i's parameters are changed. By performance difference lemma,V θ ′ * -V θ * = 1 1 -γ E s∼d π θ ′ * µ E ā∼π θ ′ * A θ * (s, ā) = 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ ′ * (•|s) E āi ∼π i θi * (•|s,ā P i ) E ā-P i + ∼π -P i + θ ′ * (•|s,a P i + ) Q θ * (s, āP i , āi , ā-P i + )-V θ * (s) Since (θ ′ * ) -i = θ -i * which means π P i θ ′ * (•|s) = π P i θ * (•|s), π -P i + θ ′ * (•|s, a P i + ) = π -P i + θ * (•|s, a P i + ), = 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ * (•|s) E āi ∼π i θi * (•|s,ā P i ) E ā-P i + ∼π -P i + θ * (•|s,a P i + ) Q θ * (s, āP i , āi , ā-P i + )-V θ * (s) = 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ * (•|s) E āi ∼π i θi * (•|s,ā P i ) Q i θ * (s, āP i , āi ) -V θ * (s) = 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ * (•|s) E āi ∼π i θi * (•|s,ā P i ) A i θ * (s, āP i , āi ) + Q i θ * (s, āP i ) -V θ * (s) = 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ * (•|s) E āi ∼π i θi * (•|s,ā P i ) A i θ * (s, āP i , āi ) + 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ * (•|s) E āi ∼π i θi * (•|s,ā P i ) Q i θ * (s, āP i ) -V θ * (s) ≤ 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ * (•|s) E āi ∼π i θi * (•|s,ā P i ) 2(1 -λ)λ d π θ µ (s, āP i )|S||A P i | + 1 1 -γ E s∼d π θ ′ * µ (•) E āP i ∼π P i θ * (•|s) Q i θ * (s, āP i ) -V θ * (s)By definition of ϵ-Nash, we know that the BN (joint) policy π θ = (π 1 θ 1 , ..., π N θ N , G) is a 2λM -Nash policy.Since L λ (θ) is β λ -smooth, we havemin t≤T ∇ θ L λ (θ (t) ) 2 2 ≤ 2β λ (L λ (θ * ) -L λ (θ 0 )) T ≤ 2β λ (V max -V min ) T ≤ 2β λ (r max -r min ) T (1 -γ) ,where the last inequality is because we need to choose T large enough such that2β λ (r max -r min ) T (1 -γ) ≤ λ/(2|S| max i |A i |).Solving the above inequality we obtainT ≥ 8β λ |S| 2 maxi |A i | 2 (rmax-rmin) λ 2 (1-γ). By Lemma 2, we should set λ = ϵ/2M to achieve the specified Nash-gap of ϵ. Plugging in λ = ϵ/2M andβ λ := 8N (rmax-rmin) (1-γ) 3 + i 2λ |S||A P i | , we have T ≥ 32M 2 |S| 2 max i |A i | 2 β λ (r max -r min ) ϵ 2 (1 -γ) = 256N M 2 |S| 2 max i |A i | 2 (r max -r min ) 2 (1 -γ) 4 ϵ 2 + 64λM 2 |S| max i |A i | 2 i 1 |A P i | (r max -r min ) (1 -γ)ϵ 2 = 256N M 2 |S| 2 max i |A i | 2 (r max -r min ) 2 (1 -γ) 4 ϵ 2 + 32λM |S| max i |A i | 2 i 1 |A P i | (r max -r min ) (1 -γ)ϵ A.4 Proof of lemma 3Proof. By bound on the advantage inequality (5), we know that ∀s, A P i , a i ,EQUATIONBy inequality (4), we knowEQUATIONAssume without loss of generality that agents Q π θ (s, a P i-1, ā-P i-1EQUATIONFollow the reverse topological ordering, ∀a = [a P N , a N ],Q π θ * (s, a) = Q π θ * (s, a P N , a N ) = Q π θ * ,N (s, a P N , a N ) By inequality (5) , ≤ Q π θ * ,N2 N +1 N (1 -γ)λ d π θ µ (s)|S| ≤ 1 1 -γ s M 2 N +1 N (1 -γ)λ |S| = 2 N +1 N λMThen, since ∀s, a, Q π θ * (s, a) ≤ V π θ * (s), we know that (π 1θ 1 * , • • • , π N θ N *, G) is an 2 N +1 N λM -optimal policy.Since L λ (θ) is β λ -smooth, we havemin t≤T ∇ θ L λ (θ (t) ) 2 2 ≤ 2β λ (L λ (θ * ) -L λ (θ 0 )) T ≤ 2β λ (V max -V min ) T ≤ 2β λ (r max -r min ) T (1 -γ) ,where the last inequality is because we need to choose T large enough such that2β λ (r max -r min ) T (1 -γ) ≤ λ/(2|S||A| max i |A i |).Workshop on Bayesian Decision-making and Uncertainty, 38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
 
 Appendix:  



Reviews: review: title: title: This work introduces non-asymptotic convergence results for a policy gradient algorithm for cooperative multi-agent reinforcement learning.
main_review: main_review: This work extends the results from [1], which dealt with learning policies for cooperative Markov games. Instead of a product factorization for the joint policy, the joint policy is modeled as a Bayesian network. The problem setting and motivation are well-explained. While [1] provided an asymptotic convergence result for policy gradient in this setting, in this work the authors provide non-asymptotic convergence results.

The one weakness I wish to point out is that the authors do not provide a discussion on the bounds that they obtain (on lines 122 and 141). The bounds are quite complex, and some insight into how individual variables affect the bound and practical recommendations based on it, for instance, could both enhance readability and make a stronger case for the results of the paper.

This paper also lacks empirical evaluation, which the authors point out as a limitation. That being said, theoretical aspects of learning algorithms, particularly non-asymptotic bounds, are valuable and can be used to guide implementations. I feel that the theorems and their proofs demonstrate sufficient originality for acceptance.

---

## Minor comments
- On line 59, the quantity $V\_{\bar{\pi}^i, \pi^{-i}}$ is not defined.
- I found the notation quite cumbersome, for example, $\nabla_{\theta^i_{s, a^{\mathcal{P}^i}, a^i}}$ on line 110. Using more compact notation could make the paper much easier to read.
---

## References
[1] Dingyang Chen and Qi Zhang. Context-aware Bayesian network actor-critic methods for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning. 2023.
title: title: Good paper, extending previous theoretical results
main_review: main_review: ## Summary:

This paper focuses on a setting using Bayesian network to inaugurate correlations between agents’ action selections in their
Joint policy. Previous work has demonstrated a global convergence to Nash equilibria under a tabular softmax policy parameterization under this setting. This paper further gives an analysis of the convergence rate under this setting. 

## Strengths:
   - Clarity : The writing is clear and makes it easy for reviewers unfamiliar with the previous work to follow the author's discussion.

   - Quality: The contribution of the paper is clear and important, filling the gaps in previous work.

   - Originality: To the best of my knowledge, this work is novel.
  
   - Significance:  This paper is important and valuable for the setting the author cares about. But I am concerned about whether this paper can provide insights to the broader MARL community.

## Questions: 

- Can learnable DAGs be combined with sequentially updated MARL algorithms, such as HAPPO?
- If they can be combined, can the theoretical properties still be maintained?