Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning

Motivation

• CTDE methods can learn dynamic interaction graphs but require global observations and centralized infrastructure that are impractical under decentralized sensing and communication constraints.Networked MARL instead models agents interacting over fixed physical graphs with local observations and nearby communication.Source: §1 · pp. 1–2
• Static communication graphs force agents to exchange information with all local neighbours, causing inefficient coordination and potentially degrading performance when neighbour relevance changes.This motivates learning interaction structures that adapt to context rather than treating every physical neighbour identically.Source: §1 · p. 2

BayesG

• BayesG is a decentralized graph-based actor–critic framework that learns latent interaction structures through Bayesian inference over each agent’s local neighbourhood.Each agent operates on an ego-graph and infers a binary mask over physically available neighbours.Source: §1 · p. 2

Contribution

• BayesG prioritizes critical local communication links and prunes irrelevant ones without global supervision, producing task-adaptive, uncertainty-aware, and communication-efficient coordination.Experiments on synthetic and real-world traffic-control benchmarks report performance and interpretability advantages over state-of-the-art MARL baselines.Source: §1 · p. 2

BayesG

• BayesG uses a stochastic graph-based policy, Bayesian variational inference for edge masks, and end-to-end actor–critic training with an ELBO objective.The learned variational distribution produces sparse subgraphs for policy computation while respecting the environment topology and local data.Source: §1 · p. 2

Networked MARL

• Networked MARL methods commonly coordinate over fixed topologies using consensus, spatial priors, predicted trajectories, communication, or predefined sampling distributions.These approaches generally do not adapt communication structure to task context.Source: §2 · p. 2

BayesG

• BayesG adaptively selects task-relevant neighbours from each agent’s physical graph through Bayesian latent graph inference, enabling locally grounded and communication-efficient coordination.Its posterior approximation produces a sparse subgraph used for graph-conditioned policy learning through an ELBO objective.Source: §2 · pp. 2–3

Graph-based MARL and Latent Structure Learning

• DICG and HGAP use attention mechanisms or graph neural networks to infer inter-agent dependencies and guide information exchange, while variational approaches treat interaction graphs as latent variables.Source: §2 · p. 3

Limitations of Prior Work

• Many existing latent-graph and coordination-graph methods assume centralized training with global state or reward signals and permit unrestricted graph rewiring.Those assumptions are impractical when agents must operate under local observability and physical communication constraints.Source: §2 · p. 3

Networked MARL Formulation

• Each agent in the fixed interaction graph communicates with local neighbours N_i and defines a closed neighbourhood V_i that includes itself.The local observation is ˜s_i = f(s_Vi), allowing the encoder to aggregate neighbourhood-level context before action selection.Source: §3 · p. 3
• A local policy π_i(u_i | ˜s_i) selects actions from neighbourhood-encoded observations, while agent transitions depend on local states and neighbour actions.The local reward is defined over the closed neighbourhood, R(s_Vi, u_Vi).Source: §3 · p. 3

Objective

• The objective is to maximize expected discounted return over local rewards with discount factor γ ∈ (0, 1].The formulation evaluates future neighbourhood rewards across the trajectory.Source: §3 · p. 3

Decentralized A2C

• Decentralized A2C uses local actor and critic networks trained from on-policy minibatches containing states, actions, rewards, and neighbour actions.The setup includes target critic outputs, a rollout horizon, distance-weighted neighbour influence α, and entropy regularization controlled by β.Source: §3 · pp. 3–4

4 Method

• BayesG learns sparse, context-aware interaction graphs via variational inference while jointly optimizing decentralized policy behavior.The total objective combines the ELBO and critic loss across agents, preserving the physical environment structure.Source: §4 · p. 4, §4.2 · p. 6

4.1 Graph-based Policy with Latent Interaction Structures

• Each agent samples a binary subgraph over its closed physical neighborhood and conditions action selection on the resulting graph-conditioned representation.The sampled graph is restricted to physically permitted connections, while the graph-conditioned encoder and action policy process the selected structure.Source: §4.1 · p. 4
• The stochastic graph distribution lets agents emphasize contextually relevant neighbors and suppress irrelevant ones using local observations, supporting adaptation to non-stationary dynamics.The paper gives traffic signal control as an example in which congested junctions can receive greater emphasis.Source: §4.1 · p. 4

4.2 BayesG: Variational Latent Ego-graph Inference for Policy Optimisation

• BayesG models each latent edge mask as a Bayesian variable conditioned on the physical graph and agent-local data, capturing uncertainty in coordination structures.The local data may include neighbor states, policy outputs, and trajectory embeddings; the likelihood measures how well a masked graph explains observed behavior.Source: §4.2 · p. 5
• A variational posterior over edge masks is trained with an ELBO whose likelihood term uses the graph-conditioned actor loss, thereby integrating graph inference with policy learning.The variational distribution is optimized against a Bayesian posterior, and the resulting objective jointly optimizes policy and latent-subgraph structure.Source: §4.2 · p. 5
• Mask entropy regularization prevents premature collapse to deterministic graphs and supports uncertainty-aware neighbor selection alongside entropy-regularized action selection.This dual entropy treatment is presented as important for robustness when both action diversity and adaptive communication matter.Source: §4.2 · p. 5

5.1 Experimental Setup

• The evaluation uses five SUMO traffic-control benchmarks, including 5×5 ATSC_Grid, 28-intersection Monaco, and NewYork networks with 33, 51, and 167 intersections.Agents observe local traffic conditions and control local signals over fixed physical neighborhoods.Source: §5.1 · p. 6

5.1.2 Implementation Details

• BayesG replaces fixed communication with a sampled binary mask over each agent’s physical graph and performs masked GNN message passing over the resulting effective graph.The implementation uses GCNs and processes observation, policy, and trajectory features to learn sparse, context-aware communication structures.Source: §5.1.2 · p. 7

5.2 Performance Comparison

• BayesG consistently outperforms non-communicative and communication-based baselines across five ATSC environments, with faster convergence and more stable, higher returns in large networks.The large-scale scenarios include NewYork33, NewYork51, and NewYork167; returns are defined as the negative of total queue length and averaged over five seeds.Source: §5.2 · pp. 7–8, Figure 2 · p. 7
• On the Grid map, BayesG produces smoother traffic flow than IA2C, CommNet, and NeurComm, with thinner and less congested road segments at 3,500 seconds.Road thickness and color encode vehicle density, with thicker and redder segments indicating heavier congestion.Source: §5.2 · p. 8, Figure 3 · p. 8

5.3 Case Study: Interpreting Learned Interaction Structures

• The learned interaction graph prioritizes communication from low-congestion intersections toward congested regions, supporting directional upstream coordination to regulate inflow.The case study represents edge thickness as inferred communication likelihood and links higher coordination weights to downstream congestion patterns.Source: §5.3 · pp. 8–9, Figure 4 · p. 9

5.4 Ablation Studies

• Ablations show that learned masking outperforms no masking and random masking, while combining state, trajectory, and policy features yields the strongest mask-learning results.Trajectory features outperform state-only inputs, and policy-based masks provide meaningful behavioral signals.Source: §5.4 · pp. 9–10, Figure 5 · p. 9

6.1 Comparison with Sampling-based Networked MARL

• BayesG learns context-dependent per-edge distributions q(Zi; ϕi) jointly with the policy through an ELBO, whereas prior methods use predefined, uniform, or globally controlled sampling.Its adaptivity operates at the policy level, with each agent sampling a task-adaptive 1-hop subgraph for local decision-making.Source: §6.1 · p. 10
• The method is complementary to convergence-focused sampling approaches because it learns which neighbors to attend to end-to-end with policy optimization.The comparison emphasizes learned neighbor selection rather than only structural sampling guarantees.Source: §6.1 · p. 10

6.2 Distinction from Dec-POMDP-based Coordination Graphs

• BayesG addresses Spatiotemporal-MDPs with local transitions and rewards over physically connected neighborhoods under fully decentralized learning.This setting models systems such as traffic networks, power grids, and sensor fields where agents observe and affect local neighbors.Source: §6.2 · p. 10
• Dec-POMDP coordination-graph methods assume global state, global reward, joint transitions, and CTDE, while allowing graph rewiring unconstrained by physical topology.The paper therefore excludes them as incompatible with physically grounded networked systems.Source: §6.2 · p. 10

7 Conclusion

• BayesG jointly optimizes interaction topology and policy by combining ego-graph Bayesian inference with actor–critic training through an ELBO objective.Agents infer communication structures from local observations while respecting the environment’s physical topology.Source: §7 · p. 10
• Across five adaptive traffic signal control benchmarks, BayesG consistently outperforms strong baselines, achieving superior coordination and reduced congestion.Case studies and ablations further highlight the efficiency and interpretability of its learned graphs.Source: §7 · p. 10

A.1 Derivation of Graph-based Policy

• Each agent samples a binary subgraph from a learned variational distribution and conditions its action policy on graph-filtered neighborhood information.The encoder applies GNNs over the masked subgraph, allowing sparse, context-aware local reasoning.Source: §A.1 · p. 15
• Sampled interaction subgraphs are constrained to edges permitted by the environment graph, preserving physically feasible communication.Agents can sample only from edges in the physical topology.Source: §A.1 · p. 15

A.2 Derivation of Graph-based A2C Objective

• BayesG extends A2C with graph-conditioned actor losses and entropy regularization, so policy optimization incorporates stochastic subgraph sampling.The graph-based actor loss is integrated into the main training objective.Source: §A.2 · p. 15

A.3 Derivation of Variational Objective and ELBO for BayesG

• Bayesian variational inference approximates the intractable posterior over binary edge masks and maximizes an ELBO combining data likelihood, graph priors, and variational entropy.The variational distribution is trained by minimizing KL divergence, equivalently maximizing the ELBO up to an additive constant.Source: Bayesian Inference over Latent Graphs · p. 16, Variational Approximation and KL… · p. 16

Final Objective

• The final BayesG objective jointly optimizes policy and latent graph structure using a Bernoulli edge distribution with retention bias λ.The objective combines graph-conditioned policy loss with prior regularization over sampled edge masks.Source: §2 · p. 16, Final Objective · p. 17

B.2 Why Spatiotemporal-MDP Fits ATSC

• ATSC supplies localized dynamics, fixed sparse topology, local sensing, and decentralized execution constraints that motivate physically grounded communication masks.Traffic rewards and transitions depend on local intersection and neighbor information, while centralized control faces scalability and communication limits.Source: §B.1 · p. 18, §B.2 · p. 19

C NewYork Scenario Visualization and Graph Statistics

• NewYork33, NewYork51, and NewYork167 are SUMO-based Manhattan traffic networks whose MARL graphs contain signalized intersections and direct controlled-agent connections.The environment graph excludes unsignalized intersections and skipped intermediate traffic lights.Source: C NewYork Scenario Visualization and… · p. 19, Table 1 · p. 19

D Algorithms

• BayesG training alternates edge sampling and message propagation with trajectory collection, value estimation, and gradient updates to actor, critic, and graph parameters.Algorithm 1 samples Zi from q(Zi; ϕi) and updates θi and ϕi through the ELBO objective.Source: D Algorithms · pp. 19–20
• During decentralized execution, each agent observes locally, samples a latent mask, encodes its neighborhood, and selects actions without global information.The procedure uses local communication and control intervals rather than centralized state access.Source: D Algorithms · p. 20
• Training-loss visualizations include BayesG curves for ATSC_Grid and Monaco, documenting optimization behavior across representative environments.The supplied figures identify training loss curves for ATSC_Grid and Monaco.Source: Figure 7 · p. 21, Figure 8 · p. 21

E Training Loss Analysis

• Across varying network scales, the loss behavior supports stable joint optimization of policy learning and latent graph inference.The reported curves are interpreted as balancing exploration and exploitation during graph learning.Source: E Training Loss Analysis · pp. 21–22
• The policy loss may spike as latent masks change, then stabilizes as policy learning and graph inference converge.The transient increases are attributed to distributional shifts in graph-conditioned states.Source: E Training Loss Analysis · pp. 21–22
• The ELBO remains smooth and stable across seeds on Grid and Monaco despite increasing policy confidence and KL penalties.Its increasing trend reflects lower entropy and greater deviation from the Bernoulli prior.Source: E Training Loss Analysis · p. 22
• On NewYork33, the ELBO first decreases as useful sparse subgraphs align with the prior, then rises as deterministic graphs increase the KL term.This U-shaped trajectory reflects a trade-off between policy certainty and stochastic subgraph exploration.Source: E Training Loss Analysis · p. 22
• Mask entropy decreases, prior loss stabilizes, and value loss steadily decreases during training.Together, these trends indicate increasingly deterministic communication structures and reliable value-function learning.Source: E Training Loss Analysis · p. 22

F Additional Visualizations on Grid Environment

• IA2C remains congested without communication, CommNet over-communicates with irrelevant neighbors, and NeurComm reduces congestion with a relatively fixed structure.These comparisons provide distinct baselines for BayesG’s adaptive communication behavior.Source: F Additional Visualizations on Grid… · p. 23
• Across multiple simulation times, BayesG dynamically emphasizes critical neighbors and suppresses redundant links, producing the smoothest overall traffic flow.Road thickness and color encode vehicle density; BayesG is contrasted with noncommunicative, overcommunicative, and relatively fixed schemes.Source: F Additional Visualizations on Grid… · pp. 22, 24, Figure 10 · p. 23

G Extended Case Study: Dynamic Graph Adaptation Across Time and Runs

• Figure 11 represents each ego-graph as a probabilistic mask and uses edge width to show communication probability alongside traffic density snapshots.Rows correspond to different simulation steps and independent training runs.Source: G Extended Case Study: Dynamic Graph… · p. 24, Figure 11 · p. 25
• In both runs, increasing local congestion is accompanied by higher communication probabilities among nearby agents, directing coordination toward problematic areas.The reported behavior is directional cooperation involving upstream or adjacent intersections.Source: G Extended Case Study: Dynamic Graph… · p. 24

H Detailed Comparison with Sampling-based Networked MARL

• Table 2 distinguishes sampling methods by target, distribution type, adaptivity locus, and first-hop inclusion probability.BayesG learns context-dependent per-edge distributions jointly with policy rather than using predefined or uniform sampling.Source: Table 2 · p. 26, H Detailed Comparison with… · p. 26

• BayesG assumes a predefined static environment graph, limiting generalization to domains with dynamic or learned topology.The authors identify dynamic graph adaptation as a future-work direction.Source: I Limitations · pp. 26–27
• Local ego-graph observations limit BayesG's ability to reason over long-range dependencies requiring more global context.Source: I Limitations · p. 26
• Mask performance depends on Gumbel-softmax temperature and sparsity-prior tuning, with poor settings potentially causing under- or over-pruning and degraded coordination.Source: I Limitations · p. 26
• Variational sampling and masked GNN computation add training overhead that can grow with neighborhood size or message-passing depth.The authors nevertheless characterize BayesG as efficient in practice.Source: I Limitations · p. 27