Multi-Agent Reinforcement Learning (MARL)

The defining challenge of MARL: each agent's policy changes during training, making the environment appear non-stationary from any single agent's perspective. This violates the Markov assumption central to single-agent RL convergence proofs.

• Simultaneous learning breaks the static environment assumption
• An agent's optimal policy at time t may become suboptimal at t+1 as others adapt
• Requires specialized algorithms like centralized training with decentralized execution (CTDE) to stabilize learning
• Contrasts with distributed RL, where agents operate in independent, stationary environments

MARL systems operate across a spectrum of agent relationships that fundamentally alter the learning objective and solution concept.

• Fully Cooperative: All agents share a common reward function, maximizing global return. Requires coordination to avoid redundancy. Example: multi-robot warehouse picking.
• Fully Competitive: Zero-sum or constant-sum games where one agent's gain is another's loss. Converges to minimax strategies. Example: adversarial spectrum jamming.
• Mixed-Motive: General-sum games with elements of both conflict and cooperation. Agents must navigate social dilemmas like the Prisoner's Dilemma or Stag Hunt. Example: spectrum sharing where operators benefit from coordination but compete for bandwidth.

A dominant paradigm addressing non-stationarity by allowing agents to access global information during training but act on local observations during execution.

• Training phase: A centralized critic uses joint state-action information to compute accurate value estimates, stabilizing learning
• Execution phase: Agents deploy with decentralized policies using only local observations, preserving scalability and privacy
• Actor-critic architectures naturally implement CTDE: the critic sees everything, the actor sees only local data
• Key algorithms: MADDPG, QMIX, MAPPO
• Directly applicable to spectrum sharing coordination, where base stations can share channel state information during offline training but must make real-time allocation decisions independently

Agents can learn to develop their own communication protocols—discrete symbols or continuous vectors—to share intentions, observations, or requests without explicit programming.

• Emergent language: Agents invent sparse, efficient signaling systems through reinforcement, often uninterpretable to humans
• Differentiable communication channels allow gradients to flow between agents during training, optimizing what and when to communicate
• Spectrum application: Cognitive radios can learn to broadcast minimal coordination signals (e.g., channel reservation tokens) that reduce collision probability without a centralized controller
• Related to Distributed Constraint Optimization (DCOP) but learned rather than solved analytically
• Challenges include the lazy agent problem, where agents learn to ignore messages if not incentivized to listen

Determining which agent's action contributed to a shared outcome is exponentially harder than single-agent credit assignment. A global reward signal provides no direct feedback on individual contributions.

• Difference rewards shape individual rewards by comparing global reward with and without an agent's action, preserving the Nash Equilibrium of the original game
• Value decomposition networks (VDN) and QMIX factor the joint Q-function into per-agent utility functions while maintaining a monotonicity constraint
• COMA (Counterfactual Multi-Agent Policy Gradients) uses a centralized critic to compute a baseline that marginalizes out a single agent's action
• Critical for cooperative spectrum sensing, where multiple radios contribute to a detection decision and must learn which sensors provide reliable information

Training independent policies for hundreds or thousands of agents is computationally intractable. Parameter sharing allows homogeneous agents to use a single neural network conditioned on agent-specific observations.

• Agents share the same policy network weights but behave differently based on their unique local observations and agent ID embeddings
• Enables training with a small number of agents and deploying to a much larger population—a form of zero-shot generalization
• Mean-field MARL approximates interactions with many agents by modeling the average effect of neighboring agents, reducing complexity from O(n²) to O(n)
• Essential for large-scale spectrum sharing scenarios with dense IoT deployments, where thousands of devices must coexist without pairwise coordination