Chapter 7: Multi-Agent Reinforcement Learning

7.1 Introduction to Multi-Agent RL

Multi-Agent Reinforcement Learning (MARL) extends RL to environments with multiple learning agents that interact with each other. Agents must learn not only from the environment but also adapt to other agents' changing behaviors.

Types of Multi-Agent Settings

• Fully Cooperative: All agents share the same reward (team games)
• Fully Competitive: Zero-sum games (chess, poker)
• Mixed: Both cooperation and competition (markets, social dilemmas)

7.2 Game Theory Foundations

Nash Equilibrium

A Nash equilibrium is a set of policies where no agent can improve by unilaterally changing their policy:

π* = (π₁*, π₂*, ..., πₙ*) is a Nash equilibrium if:

Q^πᵢ(s, aᵢ, a₋ᵢ) ≥ Q^π(s, a'ᵢ, a₋ᵢ) for all i, s, aᵢ, a'ᵢ

where:
- aᵢ: agent i's action
- a₋ᵢ: other agents' actions

Prisoner's Dilemma

Classic example showing tension between individual and collective rationality:

Nash equilibrium: both defect (suboptimal!). Optimal: both cooperate.

7.3 Independent Learners

Simplest approach: each agent learns independently using single-agent RL:

class IndependentQLearning:
    def __init__(self, n_agents, state_dim, action_dim):
        // Each agent has its own Q-table
        self.agents = [
            QLearningAgent(state_dim, action_dim)
            for _ in range(n_agents)
        ]

    def step(self, states):
        // Each agent selects action independently
        actions = []
        for i, agent in enumerate(self.agents):
            action = agent.select_action(states[i])
            actions.append(action)
        return actions

    def update(self, states, actions, rewards, next_states):
        // Each agent updates independently
        for i, agent in enumerate(self.agents):
            agent.update(states[i], actions[i], rewards[i], next_states[i])

When Independent Learning Works

• Agents have minimal interaction
• Environment is large enough that agents rarely meet
• Simple coordination tasks

7.4 Centralized Training, Decentralized Execution (CTDE)

CTDE is a powerful paradigm: use global information during training, but agents act independently at execution:

QMIX Algorithm

QMIX learns individual Q-functions Qᵢ(oᵢ, aᵢ) and combines them into Q_tot:

import torch
import torch.nn as nn

class QMIXNetwork(nn.Module):
    def __init__(self, n_agents, state_dim, n_actions, mixing_embed_dim=32):
        super(QMIXNetwork, self).__init__()

        // Individual Q-networks (one per agent)
        self.agent_q_networks = nn.ModuleList([
            nn.Sequential(
                nn.Linear(state_dim, 128),
                nn.ReLU(),
                nn.Linear(128, n_actions)
            )
            for _ in range(n_agents)
        ])

        // Mixing network: combines individual Q-values
        self.hyper_w1 = nn.Linear(state_dim, n_agents * mixing_embed_dim)
        self.hyper_w2 = nn.Linear(state_dim, mixing_embed_dim)

        self.hyper_b1 = nn.Linear(state_dim, mixing_embed_dim)
        self.hyper_b2 = nn.Sequential(
            nn.Linear(state_dim, mixing_embed_dim),
            nn.ReLU(),
            nn.Linear(mixing_embed_dim, 1)
        )

    def forward(self, agent_obs, global_state):
        """
        Compute Q_tot from individual Q-values.

        Monotonicity constraint: ∂Q_tot/∂Qᵢ ≥ 0
        This ensures joint action selection = individual greedy selection
        """
        // Get individual Q-values
        agent_qs = []
        for i, q_net in enumerate(self.agent_q_networks):
            q = q_net(agent_obs[i])
            agent_qs.append(q)

        agent_qs = torch.stack(agent_qs, dim=1)  # [batch, n_agents, n_actions]

        // Mixing network weights (state-dependent)
        w1 = torch.abs(self.hyper_w1(global_state))
        b1 = self.hyper_b1(global_state)

        w2 = torch.abs(self.hyper_w2(global_state))
        b2 = self.hyper_b2(global_state)

        // Mix individual Q-values
        hidden = F.elu(torch.matmul(agent_qs, w1) + b1)
        q_tot = torch.matmul(hidden, w2) + b2

        return q_tot, agent_qs

// Training
def train_qmix(env, episodes=10000):
    qmix = QMIXNetwork(n_agents=3, state_dim=obs_dim, n_actions=5)
    optimizer = torch.optim.Adam(qmix.parameters(), lr=1e-3)
    replay_buffer = ReplayBuffer()

    for episode in range(episodes):
        obs, global_state = env.reset()
        done = False

        while not done:
            // Select actions
            q_tot, agent_qs = qmix(obs, global_state)
            actions = agent_qs.argmax(dim=-1)

            // Execute
            next_obs, rewards, done, next_global_state = env.step(actions)

            // Store transition
            replay_buffer.add(obs, global_state, actions, sum(rewards), next_obs, next_global_state)

            // Update
            if len(replay_buffer) > batch_size:
                batch = replay_buffer.sample(batch_size)
                loss = compute_qmix_loss(qmix, batch)

                optimizer.zero_grad()
                loss.backward()
                optimizer.step()

            obs = next_obs
            global_state = next_global_state

7.5 Communication in MARL

CommNet Architecture

CommNet allows agents to communicate through a shared channel:

class CommNet(nn.Module):
    def __init__(self, n_agents, obs_dim, hidden_dim, n_actions):
        super(CommNet, self).__init__()
        self.n_agents = n_agents

        // Encoding
        self.encoder = nn.Linear(obs_dim, hidden_dim)

        // Communication module
        self.comm_layer = nn.Sequential(
            nn.Linear(hidden_dim, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, hidden_dim)
        )

        // Action output
        self.actor = nn.Linear(hidden_dim, n_actions)

    def forward(self, observations):
        """
        observations: [n_agents, obs_dim]
        """
        // Encode each agent's observation
        hidden = self.encoder(observations)  # [n_agents, hidden_dim]

        // Average communication (broadcast)
        comm_mean = hidden.mean(dim=0, keepdim=True)  # [1, hidden_dim]

        // Combine local and communicated information
        combined = hidden + comm_mean.expand(self.n_agents, -1)
        updated = self.comm_layer(combined)

        // Output actions
        actions = self.actor(updated)
        return actions

Learned Communication

class LearnedCommAgent(nn.Module):
    def __init__(self, obs_dim, message_dim, hidden_dim, n_actions):
        super(LearnedCommAgent, self).__init__()

        // Observation encoder
        self.obs_encoder = nn.Linear(obs_dim, hidden_dim)

        // Message generation
        self.message_gen = nn.Linear(hidden_dim, message_dim)

        // Action policy
        self.policy = nn.Sequential(
            nn.Linear(hidden_dim + message_dim * (n_agents - 1), hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, n_actions),
            nn.Softmax(dim=-1)
        )

    def generate_message(self, obs):
        """Generate message to broadcast to other agents."""
        hidden = self.obs_encoder(obs)
        message = self.message_gen(hidden)
        return message

    def act(self, obs, received_messages):
        """Select action based on observation and messages."""
        hidden = self.obs_encoder(obs)
        messages_concat = torch.cat(received_messages, dim=-1)
        combined = torch.cat([hidden, messages_concat], dim=-1)
        action_probs = self.policy(combined)
        return action_probs

7.6 Emergent Behaviors

Predator-Prey

class PredatorPreyEnv:
    """
    Multiple predators must cooperate to catch faster prey.
    Emergent behavior: surrounding, coordination, role specialization
    """
    def __init__(self, n_predators=4, grid_size=10):
        self.n_predators = n_predators
        self.grid_size = grid_size

        self.predator_positions = []
        self.prey_position = None

    def reset(self):
        // Random initial positions
        self.predator_positions = [
            (random.randint(0, self.grid_size-1),
             random.randint(0, self.grid_size-1))
            for _ in range(self.n_predators)
        ]
        self.prey_position = (random.randint(0, self.grid_size-1),
                              random.randint(0, self.grid_size-1))

        return self.get_observations()

    def step(self, actions):
        // Move predators
        for i, action in enumerate(actions):
            self.predator_positions[i] = self.move(self.predator_positions[i], action)

        // Prey tries to escape (moves away from nearest predator)
        self.prey_position = self.move_prey()

        // Capture if predators surround prey
        captured = self.check_capture()

        // Reward: +10 for capture, -0.1 per step
        rewards = [10 if captured else -0.1] * self.n_predators

        return self.get_observations(), rewards, captured

    def check_capture(self):
        """Prey is captured if ≥2 predators are adjacent."""
        adjacent_predators = 0
        for pos in self.predator_positions:
            if self.distance(pos, self.prey_position) <= 1:
                adjacent_predators += 1
        return adjacent_predators >= 2

7.7 Multi-Agent Deep Deterministic Policy Gradient (MADDPG)

MADDPG extends DDPG to multi-agent settings with centralized critics:

class MADDPG:
    def __init__(self, n_agents, obs_dim, action_dim):
        self.agents = []

        for i in range(n_agents):
            // Each agent has its own actor (decentralized)
            actor = Actor(obs_dim, action_dim)

            // Critic sees all observations and actions (centralized)
            critic = Critic(obs_dim * n_agents, action_dim * n_agents)

            self.agents.append({
                'actor': actor,
                'critic': critic,
                'actor_target': copy.deepcopy(actor),
                'critic_target': copy.deepcopy(critic),
                'actor_optimizer': optim.Adam(actor.parameters(), lr=1e-3),
                'critic_optimizer': optim.Adam(critic.parameters(), lr=1e-3)
            })

    def select_actions(self, observations):
        """Each agent selects action based on local observation."""
        actions = []
        for i, agent in enumerate(self.agents):
            obs = torch.FloatTensor(observations[i])
            action = agent['actor'](obs)
            actions.append(action)
        return actions

    def update(self, batch):
        """
        Update all agents using centralized training.
        """
        obs, actions, rewards, next_obs, dones = batch

        for i, agent in enumerate(self.agents):
            // Critic update
            with torch.no_grad():
                // Next actions from target actors
                next_actions = [
                    self.agents[j]['actor_target'](next_obs[:, j])
                    for j in range(len(self.agents))
                ]
                next_actions = torch.cat(next_actions, dim=-1)

                // Q-target
                next_obs_all = next_obs.view(batch_size, -1)
                q_next = agent['critic_target'](next_obs_all, next_actions)
                q_target = rewards[:, i:i+1] + gamma * q_next * (1 - dones[:, i:i+1])

            // Current Q-value
            obs_all = obs.view(batch_size, -1)
            actions_all = actions.view(batch_size, -1)
            q_value = agent['critic'](obs_all, actions_all)

            // Critic loss
            critic_loss = F.mse_loss(q_value, q_target)

            agent['critic_optimizer'].zero_grad()
            critic_loss.backward()
            agent['critic_optimizer'].step()

            // Actor update
            // Current actions from all actors
            current_actions = [
                self.agents[j]['actor'](obs[:, j]) if j == i else actions[:, j].detach()
                for j in range(len(self.agents))
            ]
            current_actions = torch.cat(current_actions, dim=-1)

            // Actor loss: maximize Q
            actor_loss = -agent['critic'](obs_all, current_actions).mean()

            agent['actor_optimizer'].zero_grad()
            actor_loss.backward()
            agent['actor_optimizer'].step()

            // Soft update targets
            self.soft_update(agent['actor_target'], agent['actor'])
            self.soft_update(agent['critic_target'], agent['critic'])

7.8 Mean Field Reinforcement Learning

For large-scale multi-agent systems (hundreds/thousands of agents), mean field approximation is efficient:

class MeanFieldAgent:
    def __init__(self, obs_dim, action_dim):
        // Agent policy depends on local obs and mean action distribution
        self.policy = nn.Sequential(
            nn.Linear(obs_dim + action_dim, 128),
            nn.ReLU(),
            nn.Linear(128, action_dim),
            nn.Softmax(dim=-1)
        )

    def forward(self, obs, mean_action):
        """
        obs: local observation
        mean_action: average action distribution of all other agents
        """
        x = torch.cat([obs, mean_action], dim=-1)
        return self.policy(x)

def train_mean_field(env, n_agents=100):
    agent = MeanFieldAgent(obs_dim, action_dim)

    for episode in range(episodes):
        observations = env.reset(n_agents)

        while not done:
            // Get actions from all agents
            actions = [agent(obs, mean_actions) for obs in observations]

            // Compute mean action distribution
            mean_actions = torch.stack(actions).mean(dim=0)

            // Environment step
            next_observations, rewards, done = env.step(actions)

            // Update
            loss = compute_policy_gradient_loss(agent, observations, actions, rewards, mean_actions)
            optimizer.zero_grad()
            loss.backward()
            optimizer.step()

7.9 Practical Applications

Multi-Robot Systems

• Warehouse Robots: Coordinate to transport items efficiently
• Drone Swarms: Formation control, exploration, surveillance
• Autonomous Vehicles: Intersection management, platooning

Game AI

• Dota 2 (OpenAI Five): 5v5 team coordination
• StarCraft II (AlphaStar): Unit micromanagement and macro strategy
• Honor of Kings (JueWu): MOBA game teamwork

Economics and Social Systems

• Traffic Control: Adaptive traffic lights
• Smart Grids: Distributed energy management
• Market Making: Trading algorithms interaction

7.10 Comparison of MARL Algorithms