Assume/Guarantee Contracts for the Compositional Multi-Agent Reinforcement Learning of Heterogeneous Teams

Dominic Klukas, Cyrus NearyarXiv 2026 · arXiv

TL;DR

This paper introduces a formal framework for breaking down complex, multi-agent tasks into modular "contracts" that specify what an agent must achieve and what it can assume about its teammates. By combining this theory with an iterative assignment algorithm (IHA-MARL), the authors enable heterogeneous teams to learn specialized roles efficiently, achieving 100% task success on benchmarks while training 7–11x faster than traditional monolithic approaches.

What Problem Does This Paper Address?

Training a team of diverse agents (e.g., a mix of drones and ground robots) to complete a complex task is notoriously difficult. Standard Multi-Agent Reinforcement Learning (MARL) often treats the team as a single "monolithic" entity, which leads to the curse of dimensionality: as you add more agents and actions, the state space explodes.

Furthermore, even if you try to decompose a task into subtasks, two major hurdles remain:

  1. Coordination: How do you ensure that if every agent completes its subtask, the overall team goal is actually met?
  2. Heterogeneity: If agents have different capabilities that aren't known beforehand, how do you decide who should do what? An agent might need to "try" a task through training before the system realizes it’s a poor fit for that specific role.

Methods

The authors propose a two-part solution:

1. AGC-MAS (Assume/Guarantee Contracts for MAS)

This is a theoretical framework that treats subtasks as formal contracts. Each contract includes:

  • An Automaton: A high-level state machine that tracks progress (e.g., "Wait for button A," "Press button B," "Task Done").
  • Performance Requirements: Specific timeouts and success probability thresholds.
  • Compositionality: A mathematical guarantee that if individual agents satisfy their local contracts, their combined behavior is guaranteed to satisfy the overall team objective.

A key innovation here is Event Indexing. Instead of just having a "Press Button" event, the system distinguishes between "Press Button (Occurrence 1)" and "Press Button (Occurrence 2)." This allows different agents to be assigned to the same type of action at different stages of a mission.

2. IHA-MARL (Iterative Heterogeneous Assignment for MARL)

This algorithm manages the "who does what" problem through an iterative loop:

  • Assign: Solve an optimization problem (using a flow-based formulation) to assign agents to contracts based on their current estimated capabilities.
  • Train: Agents use Reinforcement Learning (specifically tabular Q-learning in this paper) to satisfy their assigned contracts locally.
  • Evaluate: The system assesses how well the agents are performing. If an agent is struggling to meet its contract's success probability, the optimizer may reassign that subtask to a different, more capable agent in the next iteration.

Datasets

The researchers evaluated their approach on several cooperative multi-agent gridworld benchmarks:

  • Chess-Maze (New): A custom environment featuring a King, Knight, and Rook. Each has unique movement rules (e.g., the Knight jumps over walls). They must coordinate to press pressure plates in a specific sequence to open gates for the King.
  • Cooperative Buttons & Four Buttons: Standard benchmarks requiring agents to coordinate button presses to reach a goal.
  • Asymmetric Advantages: A "kitchen" environment where two agents (cooks) have different distances to ingredients, forcing them into specialized roles.

Key Insights and Ideas

  • Modularity is King: Because the contracts are "agent-agnostic," you can swap one agent for another or reuse a learned policy in a different team context without retraining the entire system.
  • CASA (Compositional Atomic Subtask Automata): The authors developed a way to automatically decompose a large team-task automaton into tiny, 3-state "atomic" automata (Armed, Active, Resolved). This removes the need for manual, "guess-and-check" task decomposition.
  • Training-Sensitive Optimization: The system doesn't just pick an assignment and stick to it. It treats agent capability as a dynamic variable, shifting roles as it learns which agents are actually "talented" at specific subtasks.

Key Results

  • 100% Success Rate: Across all three main benchmarks (with five different random seeds), IHA-MARL achieved a perfect evaluation success rate.
  • Massive Speedup: In CPU timing pilots, the IHA-MARL training loop was 7–11x faster than comparable baselines like Monolithic PPO or other decomposition methods (ATAD, LOTaD).
  • Robust Reassignment: In the Chess-Maze experiment, the system successfully detected when the "King" agent was failing a subtask due to environmental hazards (lava) and automatically pivoted the team to an alternative high-level plan that utilized the other agents more effectively.

Limitations and Future Work

  • Sequential Execution: Currently, the framework dispatches one indexed event at a time. While this simplifies synchronization, it prevents agents from acting truly in parallel on independent subtasks.
  • Idle Interference: The theory assumes that "idle" agents (those not currently executing a contract) do not interfere with the environment. In real-world robotics, an idle robot might still be an obstacle.
  • Given Automata: The system requires the high-level team task to be provided as an automaton. Future work could involve learning these task structures directly from demonstrations or natural language.

Summary updated

Abstract

Multi-agent reinforcement learning (MARL) problems for heterogeneous teams require agents to collaborate to complete team tasks while making the best use of diverse agent capabilities. We introduce assume/guarantee contracts for heterogeneous multi-agent systems (AGC-MAS) and Iterative Heterogeneous Assignment for MARL (IHA-MARL). AGC-MAS contracts are compositional objects that encode the assumptions provided to, and the guarantees required of, each subtask contributing to the overall team task. We formulate contracts as tuples that specify a subtask, an automaton, timeout and success-probability requirements, and dispatch behavior. The automaton tracks an agent's high-level progress through the subtask associated with its contract and provides a natural mechanism for synchronization across contracts. Our abstraction enables robust interaction across heterogeneous low-level subtask implementations, allows heterogeneous agents to substitute for one another in satisfying contracts, and supports reuse of previously satisfied contracts in new team contexts. Having defined our theoretical framework, we develop a decomposition algorithm that breaks down a team task into a set of contracts. We then propose an iterative algorithm for task assignment and MARL that alternates between assigning contracts representing subtasks to individual agents, training the assigned agents to satisfy their contracts, and assessing their resulting capabilities to inform the next round of task assignments until the team's success probability meets the desired threshold. Our experimental results demonstrate the versatility of contracts in enabling agent substitution and contract reuse. Across three benchmarks with five seeds each, IHA-MARL achieves observed $100\%$ final evaluation success. In CPU timing pilots, comparable baselines required approximately $7$--$11\times$ more training-loop time.
BibTeX
@misc{klukas2026assume,
  author = {Dominic Klukas and Cyrus Neary},
  title = {{Assume/Guarantee Contracts for the Compositional Multi-Agent Reinforcement Learning of Heterogeneous Teams}},
  year = {2026},
  eprint = {2611.19078},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19078},
}
Figure