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

1. Problem Statement

The paper addresses a critical limitation in Networked Multi-Agent Reinforcement Learning (Networked-MARL): the reliance on static communication graphs.

• Context: In many real-world decentralized systems (e.g., traffic control, smart grids), agents operate over a fixed physical communication graph (e.g., road networks) and can only observe or communicate with immediate neighbors.
• The Challenge: Existing methods often treat all local neighbors as equally informative, regardless of the current context. This leads to inefficient coordination, unnecessary message passing, and performance degradation in dynamic environments where the relevance of neighbors changes over time (e.g., traffic congestion shifting).
• The Gap: While Centralized Training with Decentralized Execution (CTDE) methods can learn dynamic graphs, they rely on global state access, which is impractical for real-world decentralized systems. Conversely, existing decentralized methods lack the ability to adapt their interaction structures based on local observations.

Core Question: Can decentralized agents learn to dynamically adapt their interaction structure using only local observations and task feedback?

2. Methodology: BayesG

The authors propose BayesG, a decentralized actor–critic framework that learns sparse, context-aware interaction structures via Bayesian variational inference.

Key Components:

1. Stochastic Graph-Based Policy:

   • Instead of conditioning decisions on a fixed set of neighbors, each agent $i$ samples a latent subgraph (an "ego-graph") from a learned distribution over its physical neighborhood.
   • The agent's policy $\pi_i$ is conditioned on this sampled subgraph $G_{V_i}$, allowing it to selectively attend to relevant neighbors and ignore irrelevant ones.

2. Bayesian Variational Inference for Latent Graphs:

   • The interaction structure is modeled as a binary mask $Z_i$ applied to the physical environment graph $G^{env}_{V_i}$.
   • The mask $Z_i$ is treated as a latent variable. The goal is to infer the posterior distribution $p(Z_i | G^{env}_{V_i}, D_i)$, where $D_i$ represents agent-local data (neighbor states, trajectories, policies).
   • Since the true posterior is intractable, it is approximated by a variational distribution $q(Z_i; \phi_i)$, parameterized by learnable logits $\phi_i$.
   • Gumbel-Softmax Reparameterization: Used to enable gradient-based learning through the discrete edge sampling process.

3. Joint Optimization via ELBO:

   • The framework integrates graph inference and policy learning into a unified objective using the Evidence Lower Bound (ELBO).
   • Objective Function: $L_{ELBO} = \mathbb{E}[-L_{\theta,\phi}] - \sum KL(q(Z_{ij}) || p(Z_{ij}))$
     • Likelihood Term ($-L_{\theta,\phi}$): The graph-conditioned actor loss (A2C objective) which provides task feedback.
     • Prior Term: A Bernoulli prior encouraging sparsity (retention bias $\lambda$).
     • Entropy Regularization: The term $-\log q$ acts as an entropy regularizer for the mask, preventing premature collapse to deterministic graphs and encouraging exploration of interaction structures.
   • The total loss combines the negative ELBO (for the actor and variational parameters) and the standard critic loss.

4. Architecture:

   • Agents use Graph Neural Networks (specifically GCNs) to encode observations, policies, and trajectories over the sampled masked graph $A^*_i = Z_i \odot G^{env}_{V_i}$.
   • Training is fully decentralized; agents only require local observations and messages from immediate physical neighbors.

3. Key Contributions

1. Stochastic Graph-Based Policy: Introduced a novel policy formulation where agents condition decisions on a sampled subgraph of their physical neighborhood, enabling dynamic adaptation to context.
2. Bayesian Formulation: Formulated latent graph learning as Bayesian variational inference, treating edge masks as posterior distributions constrained by physical topology and local data.
3. End-to-End Training Algorithm: Developed an algorithm that jointly optimizes the interaction topology and decision-making strategies via an ELBO objective, without requiring global supervision.
4. Scalability and Efficiency: Demonstrated that learning sparse, task-adaptive communication graphs significantly improves scalability in large-scale decentralized settings.

4. Experimental Results

The method was evaluated on five adaptive traffic signal control (ATSC) benchmarks using the SUMO simulator, ranging from small synthetic grids to large-scale real-world Manhattan layouts (up to 167 agents).

• Performance: BayesG consistently outperformed strong baselines (including IA2C, ConseNet, FPrint, LToS, CommNet, and NeurComm) in terms of cumulative reward (minimizing vehicle queue lengths).
• Convergence: BayesG exhibited faster convergence, particularly in early training stages, by reducing noisy or redundant communication.
• Scalability: In large-scale scenarios (NewYork167), baselines often suffered from performance plateaus or instability, whereas BayesG maintained high performance and stable learning curves.
• Qualitative Analysis: Visualizations showed that BayesG effectively reduced traffic congestion by dynamically prioritizing communication from low-congestion areas to high-congestion bottlenecks, mimicking human-designed traffic heuristics.
• Ablation Studies:
  • Masking Strategy: Learned masks significantly outperformed random masking or no masking.
  • Input Features: Combining state, trajectory, and policy features yielded the best results, with trajectory features proving crucial for capturing temporal context.

5. Significance and Impact

• Bridging the Gap: BayesG successfully bridges the gap between the theoretical power of dynamic graph learning and the practical constraints of decentralized, physically constrained systems.
• Interpretability: The learned latent graphs provide interpretability, revealing which agents are communicating and why (e.g., upstream agents coordinating to relieve downstream congestion).
• Real-World Applicability: By operating under strict local observability and fixed physical topologies, BayesG offers a principled approach for scalable coordination in real-world domains like urban traffic management, smart grids, and sensor networks, where centralized control is infeasible.
• Theoretical Contribution: The integration of variational inference with MARL provides a new paradigm for "structure-aware" cooperation, treating the communication topology itself as a learnable, uncertainty-aware component of the policy.