PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Nearly Decomposable Value Functions Via Communication Minimization

Tonghan Wang, Jianhao Wang, Chongyi Zheng, Chongjie Zhang

arXiv:1910.05366v2cs.LGstat.ML

TL;DR

Full value decomposition can miss coordination dependencies in partially observed multi-agent tasks, motivating a method that combines factorized values with selective communication. NDQ uses information-theoretic regularization to learn when and what agents should communicate, and on StarCraft II it outperforms baselines while removing more than 80% of communication without sacrificing performance.

  • Problem

    Full value decomposition can sever dependencies among agents, limiting coordination under partial observability and stochastic dynamics.

  • Method

    NDQ combines value function factorization with stochastic latent messages, maximizing message-action mutual information while minimizing message entropy.

  • Results

    NDQ significantly outperforms baseline methods on StarCraft II unit micromanagement and removes more than 80% of communication without sacrificing performance.

  • Takeaways & Limitations

    Agents can learn nearly decomposable value functions that support mostly independent action with occasional communication for coordination.

  • Takeaways & Limitations

    Training assumes access to all agents’ observation-action histories and the global state, although execution is decentralized.

Abstract

from arXiv · show

Reinforcement learning encounters major challenges in multi-agent settings, such as scalability and non-stationarity. Recently, value function factorization learning emerges as a promising way to address these challenges in collaborative multi-agent systems. However, existing methods have been focusing on learning fully decentralized value functions, which are not efficient for tasks requiring communication. To address this limitation, this paper presents a novel framework for learning nearly decomposable Q-functions (NDQ) via communication minimization, with which agents act on their own most of the time but occasionally send messages to other agents in order for effective coordination. This framework hybridizes value function factorization learning and communication learning by introducing two information-theoretic regularizers. These regularizers are maximizing mutual information between agents' action selection and communication messages while minimizing the entropy of messages between agents. We show how to optimize these regularizers in a way that is easily integrated with existing value function factorization methods such as QMIX. Finally, we demonstrate that, on the StarCraft unit micromanagement benchmark, our framework significantly outperforms baseline methods and allows us to cut off more than $80\%$ of communication without sacrificing the performance. The videos of our experiments are available at https://sites.google.com/view/ndq.

1 INTRODUCTION

Existing value factorization methods improve scalable multi-agent learning by combining decentralized values, but full decomposition cannot handle tasks where agents need occasional information exchange. NDQ addresses this with communication-minimizing coordination and outperforms baselines on StarCraft II while removing more than 80% of communication.

  • Value factorization combines decentralized agent values through a mixing network, but existing methods focus on full decomposition.
  • Many multi-agent tasks require agents to exchange information for effective coordination rather than act solely from local observations.
  • NDQ learns nearly decomposable Q-functions in which agents act independently most of the time and communicate occasionally for coordination.
  • NDQ uses mutual-information and message-entropy regularizers to make communication expressive while minimizing unnecessary messages.
  • More than 80% communication was removed on StarCraft II unit micromanagement tasks without sacrificing performance, while significantly outperforming baseline methods.

2 BACKGROUND

Centralized action-value learning is difficult to scale, while independent decentralized learning can neglect agent interactions. Value function factorization addresses this trade-off, but full decomposition may still cause severe miscoordination under partial observability and stochastic dynamics.

  • A Dec-POMDP models cooperative agents with partial observations, local action-observation histories, joint actions, shared rewards, and environment transitions.
  • Centralized action-value functions are difficult to learn as the number of agents grows, whereas independent learning can neglect interactions and cause miscoordination.
  • Value function factorization represents the global value as a mixing of decentralized values conditioned on local information.
  • Full decomposition cuts dependencies among decentralized values, leaving agents uncertain about other agents’ states and actions.
  • Figure 1 shows message embeddings combined with local histories before local action values enter a mixing network for global-value estimation.

3 METHODOLOGY

NDQ extends value-function factorization with selectively communicated messages, aiming to preserve coordination while minimizing unnecessary communication. Its objective combines task-value learning with information-theoretic constraints that make messages informative yet succinct.

  • Framework: NDQ lets agents condition local action-value functions on local histories and occasional messages from other agents.Messages are encoded stochastically and selectively cut before being received by the destination agent.
  • Framework: The framework combines decentralized value functions, a message encoder, and a QMIX-like mixing network trained end-to-end with TD loss.The overall objective adds a communication regularizer to the TD objective.
  • Communication objective: Communication is optimized by maximizing mutual information between messages and recipients’ action selection while minimizing message entropy.The mutual-information term promotes expressiveness, while entropy minimization discourages uninformative latent representations.
  • Communication objective: The scaling factor β trades off message expressiveness against succinctness.The resulting embedding places useless messages near the latent-space origin and informative messages away from it.
  • Optimization: A variational approximator makes the mutual-information term tractable, while a unit-covariance Gaussian formulation avoids variance collapse in entropy minimization.The method uses a variational posterior for action selection and a reference distribution for the message entropy bound.
  • Communication minimization: Messages can be dropped bit by bit by ranking their latent means, because unit covariance makes message dimensions independent.This lets the system remove messages that cannot reduce other agents’ action-value uncertainty.
  • Execution: Training is centralized with access to individual histories and the global state, whereas execution is decentralized using learned encoders and action-value functions.This preserves the centralized-training-with-decentralized-execution setting.

4 RELATED WORKS

The paper sits at the intersection of value-function factorization and learned multi-agent communication. It contrasts NDQ’s variational message-content and message-sending decisions with prior factorization, communication, and attention-based approaches.

  • Value-function factorization: Value-function factorization methods such as VDN, QMIX, and QTRAN combine decentralized Q-functions through a mixing network.These methods progressively expand the class of functions representable by the mixing network.
  • Learned communication: Communication research has studied decentralized protocols, when and whom to communicate with, and the emergence of communication languages.The cited approaches use end-to-end differentiable communication or investigate emergent natural-language-like protocols.
  • Closest related method: TarMAC is the closest comparison: it uses attention to differentiate incoming-message importance, whereas NDQ uses variational inference to select message content and sending.The paper compares NDQ with TarMAC and a TarMAC-plus-QMIX baseline.
  • Experimental comparison: Figure 2 compares the sensor task, performance on that task, and performance as different percentages of messages are dropped.NDQ communication reduction is measured by message count and by bit count, with QMIX (5M) denoting QMIX trained for 5 million time steps.
  • Communication analysis: Figure 3 shows message distributions under different β values, using a mean threshold to determine which bits are sent.At β = 10^-3, the caption identifies the learned strategy as both minimized and effective.

5 EXPERIMENTAL RESULTS

Experiments test NDQ on didactic coordination tasks and StarCraft II, comparing it with value-factorization and attentional-communication baselines. NDQ learns sparse communication protocols that preserve performance when most messages are removed.

  • Experimental setup: The experiments evaluate NDQ against QMIX, TarMAC, and QMIX+TarMAC on didactic tasks and six StarCraft II scenarios.Evaluation includes sensor, hallway, independent search, and StarCraft II unit micromanagement settings.
  • Didactic examples: QMIX reaches a sub-optimal average team reward of 12.5 per step on sensor because full factorization cannot provide sensor 1 with target information.The task requires sensor 1 to know whether target 2 is present in area 2.
  • Didactic examples: NDQ discovers a minimized sensor communication strategy in which agent 3 sends agent 1 one bit, while other pairwise messages are dropped.At β = 10^-3, the learned protocol communicates whether target 2 appears; larger or smaller β values produce empty or redundant communication, respectively.
  • Didactic examples: NDQ wins 100% of hallway episodes after 80% of communicating bits are dropped by coordinating only after one agent reaches its waiting position.The protocol has agent B repeatedly send a bit from b1 until A signals arrival at a1.
  • StarCraft II results: NDQ outperforms QMIX and QMIX+TarMAC without message cutting, while full message removal sharply reduces its win rates.The comparisons identify widespread miscoordination for full factorization and show that NDQ’s advantage under message cutting depends on retained communication.
  • StarCraft II results: More than 80% of communication can be cut from NDQ without significantly affecting performance, whereas cutting the 80% smallest QMIX+TarMAC messages causes a significant drop.The result indicates greater robustness to message removal than attentional communication methods.

6 CLOSING REMARKS

The framework combines value function factorization with communication learning so agents act independently when possible and communicate for coordination. On challenging StarCraft II tasks, it outperforms baselines while reducing communication by more than 80%.

  • 6 CLOSING REMARKS: The framework fuses value function factorization and communication learning to learn nearly decomposable value functions.It uses two information-theoretic regularizers to minimize communication while maximizing message information for coordination.
  • 6 CLOSING REMARKS: Agents act independently most of the time and communicate when necessary for coordination.
  • 6 CLOSING REMARKS: More than 80% communication is reduced without sacrificing performance in challenging StarCraft II tasks.
  • 6 CLOSING REMARKS: The method learns nearly minimal messages, such as one or two bits, for effective coordination.

A VARIATIONAL BOUND ON MUTUAL INFORMATION

The method maximizes mutual information between an agent's action selection and received messages using a variational lower bound. The bound is expressed with a posterior estimator and message-generation terms conditioned on local histories and other messages.

  • A VARIATIONAL BOUND ON MUTUAL INFORMATION: Mutual information between agent j's action selection and message Mij is maximized to reduce uncertainty in its action-value function.
  • A VARIATIONAL BOUND ON MUTUAL INFORMATION: A variational-inference derivation provides a lower bound for the mutual-information regularizer.
  • A VARIATIONAL BOUND ON MUTUAL INFORMATION: The bound uses agent j's local action-observation history, the joint history sampled from replay data, and a variational posterior estimator.
  • A VARIATIONAL BOUND ON MUTUAL INFORMATION: The message distribution is determined by the message encoder and a Markov chain.
  • A VARIATIONAL BOUND ON MUTUAL INFORMATION: The resulting mutual-information term is used as part of the optimization objective.

B IMPLEMENTATION DETAILS

The implementation minimizes both message count and message length while preserving fixed-size inputs for the recipient's action-value approximator. Binary masks identify dropped bits with negligible additional bandwidth.

  • B IMPLEMENTATION DETAILS: Messages vary in length because the method minimizes both the number and length of transmitted messages.
  • B IMPLEMENTATION DETAILS: Binary masks indicate which message bits were dropped so recipients can provide fixed-length inputs to the action-value approximator.
  • B IMPLEMENTATION DETAILS: Each mask is treated as a binary number and consumes only negligible additional channel bandwidth.

B.2 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE

The implementation uses PyMARL's QMIX defaults alongside dedicated fully connected networks for message encoding and posterior estimation. Training uses experience from 16 parallel environments on NVIDIA RTX 2080Ti GPUs.

  • B.2 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE: The implementation is based on PyMARL and uses its default QMIX network structure and hyperparameters.
  • B.2 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE: The message encoder is a fully connected network with one 64-dimensional hidden layer and ReLU activation.
  • B.2 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE: The posterior estimator qξ uses two 20-dimensional fully connected hidden layers with ReLU activations.
  • B.2 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE: Training uses NVIDIA RTX 2080Ti GPUs and experience sampled from 16 parallel environments.

C.1 DIDACTIC EXAMPLE: INDEPENDENT SEARCH

Independent search tests whether agents can recognize when coordination is unnecessary: two agents search separate rooms, and NDQ achieves optimal team performance without communication.

  • Independent search places two agents in separate 5 × 5 rooms, where each searches for its own landmark for 100 time steps.
  • The task is designed to test whether NDQ learns not to communicate when agents are totally independent.
  • NDQ achieves optimal team performance without communication in the independent-search task.
Loading 1910.05366v2…