Multi-Agent Reinforcement Learning (MARL)

The core challenge in MARL is the non-stationarity of the learning environment. From the perspective of any single agent, the environment appears to be changing because the policies of all other agents are also evolving simultaneously. This breaks the foundational Markov assumption of standard RL, as the same state can lead to different outcomes based on other agents' learned behaviors. Algorithms must be designed to be robust to this inherent instability.

In most MARL settings, agents operate under Partial Observability (POMPD). An agent cannot directly observe the full global state of the environment or the internal states of other agents. It must act based on its own local observation history. This necessitates the development of policies that can reason about uncertainty and infer the intentions and actions of other agents from limited data, often using recurrent neural networks or belief states.

The credit assignment problem is significantly more complex in MARL. When a team receives a global reward, determining which agent's actions contributed to success (or failure) is ambiguous. This is known as the multi-agent credit assignment problem. Solutions include:

• Difference Rewards: Shaping an agent's reward based on its marginal contribution.
• Counterfactual Baselines: Estimating what the reward would have been had the agent taken a default action.
• Value Decomposition Networks: Learning to decompose a global team value function into individual agent contributions.

MARL encompasses a spectrum of agent relationships defined by reward structure alignment:

• Fully Cooperative: All agents share a common reward function (e.g., a team of robots moving a heavy object). The goal is to maximize collective return.
• Fully Competitive: Agents have directly opposing interests, forming a zero-sum game (e.g., Chess, Go). This is often studied as self-play.
• Mixed Motives (General-Sum): The most general and common setting, where agents have partially aligned and partially conflicting goals (e.g., traders in a market, autonomous vehicles at an intersection). This requires complex negotiation and equilibrium-seeking behavior.

MARL algorithms are categorized by where learning and execution occur:

• Centralized Training with Decentralized Execution (CTDE): The dominant paradigm for cooperative tasks. A central critic has access to global information (e.g., all agents' observations) during training to learn a coordinated policy. During execution, each agent uses only its own local observation, enabling scalability. Examples include MADDPG and QMIX.
• Decentralized Training & Execution (DTDE): Each agent learns independently based solely on its own local experience. This is simpler but struggles with non-stationarity and credit assignment. It's common in competitive or mixed-motive settings.

In competitive and mixed-motive settings, the goal is not a single optimal policy but a stable strategy profile. MARL seeks to converge to game-theoretic equilibria:

• Nash Equilibrium: A set of policies where no agent can improve its reward by unilaterally changing its strategy.
• Correlated Equilibrium: A more general concept where agents can follow signals from a common source to achieve better coordinated outcomes. Learning in these settings often involves finding policies that are best responses to the policies of others, leading to algorithms based on fictitious play or policy-space response oracles.

Reinforcement Learning (RL) is the foundational machine learning paradigm where a single agent learns an optimal policy by interacting with an environment to maximize cumulative reward. It is defined by the Markov Decision Process (MDP) framework. MARL extends this core concept to multiple interacting agents, introducing complexities like non-stationarity and credit assignment.

• Key Components: Agent, Environment, State, Action, Reward, Policy.
• Core Challenge: Balancing exploration (trying new actions) with exploitation (using known good actions).
• Example: A single robot learning to navigate a maze.

A Partially Observable Stochastic Game (POSG) is the standard mathematical framework for modeling most MARL problems. It generalizes the single-agent Partially Observable Markov Decision Process (POMDP) to multiple agents. Each agent has a local observation of the global state and selects actions based on its individual policy, with the joint action influencing a shared transition function and reward structure.

• Defines: Multi-agent environment dynamics, observation models, and reward functions.
• Central Tension: Agents must reason about other agents' beliefs and policies, which are often hidden.
• Foundation: Underlies algorithms for cooperative, competitive, and mixed (general-sum) settings.

Centralized Training with Decentralized Execution (CTDE) is a dominant paradigm in cooperative MARL. During training, algorithms can leverage global information (e.g., all agents' observations) to learn richer value functions or policies. During execution, each agent acts independently using only its local observations, enabling scalable deployment.

• Key Benefit: Mitigates the non-stationarity problem during training while maintaining decentralized, robust execution.
• Common Architecture: Uses a centralized critic and decentralized actors.
• Example Algorithms: MADDPG, QMIX, MAPPO.

The credit assignment problem in MARL refers to the challenge of attributing a team's global success or failure to the individual contributions of each agent. In cooperative settings with a shared reward, determining which agent's actions were most responsible for a positive outcome is difficult, hindering individual policy improvement.

• Impact: Causes high variance in policy gradients, slowing learning.
• Solutions: Use difference rewards, counterfactual baselines, or value decomposition networks to estimate individual agent contributions.
• Analogy: In a soccer team scoring a goal, determining the precise contribution of each passer versus the shooter.

A Nash Equilibrium is a fundamental solution concept from game theory highly relevant to MARL, especially in competitive or general-sum settings. It is a profile of strategies (one per agent) where no agent can unilaterally improve its payoff by changing its own strategy, given the strategies of the others. MARL algorithms often seek to converge to a Nash Equilibrium.

• In MARL: Represents a stable, learned outcome of agent interaction.
• Challenge: Multiple equilibria may exist, and some may be sub-optimal (e.g., Pareto-dominated).
• Example: In a two-agent traffic scenario, both stopping or both going are equilibria, but only one is efficient.

Non-stationarity is the core challenge that distinguishes MARL from single-agent RL. From the perspective of any single agent, the environment dynamics appear to change because the other agents are simultaneously learning and adapting their policies. This violates the fundamental stationarity assumption of standard RL, causing convergence issues.

• Consequence: An agent's optimal policy is a moving target.
• Mitigation Strategies: Use opponent modeling, experience replay with importance sampling, or algorithms with convergence guarantees in self-play.
• Analogy: Learning to play chess against an opponent who is also rapidly improving.