WorksComputer Science
Assume/Guarantee Contracts for the Compositional Multi-Agent Reinforcement Learning of Heterogeneous Teams
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 final evaluation success. In CPU timing pilots, comparable baselines required approximately – more training-loop time.
Introduction
By distributing themselves geographically, delegating skills to different specialized agents, and working in parallel at scale, cooperative multi-agent systems (MAS) are increasingly necessary to many diverse applications, from autonomous manufacturing and field robotics, to software-based tasks such as cooperating teams of LLM agents [5, 15]. In particular, heterogeneous multi-agent systems, in which each cooperating agent may have different capabilities, are necessary to many applications in which individual agents must specialize to perform specific tasks. For instance, aerial drones excel in scouting and surveying tasks, but are often less suitable to transportation tasks, whereas ground robots can carry heavy loads much more efficiently. Because heterogeneous agents may contribute to a team task in fundamentally different ways, effective coordination requires algorithms that reason explicitly about both which agents are suited to particular subtasks and how their distinct contributions should be integrated.
Nevertheless, multi-agent teams face multiple unique challenges. First, monolithic approaches to multi-agent decision-making and learning suffer from the curse of dimensionality [3]. Moving toward distributed approaches, however, raises the problem of automatically decomposing a complex team task into subtasks representing the contributions of individual agents [14]. In heterogeneous multi-agent teams, task decomposition and assignment must also account for variation in agent performance across subtasks. When these capabilities are not known a priori, effective assignment may first require costly exploration and training to discover which agents are suited to which subtasks. Distributed multi-agent learning must also coordinate interacting agents under limited communication and decentralized execution, often while contending with non-stationarity induced by simultaneously adapting policies.
To address these challenges, we develop a theory of assume/guarantee contracts for heterogeneous agents in MAS (AGC-MAS), a framework for expressing team tasks, decomposing them into subtasks, and assigning them to heterogeneous teams of agents. While this theory applies generally to heterogeneous MAS, we focus on their development in the setting of multi-agent reinforcement learning (MARL), and we present Iterative Heterogeneous Assignment for MARL (IHA-MARL), an algorithm for task assignment and MARL in heterogeneous teams. Taken together, AGC-MAS and IHA-MARL turn heterogeneous team tasks into modular learning problems that can be trained locally, reassigned as agent capabilities are learned, and composed to guarantee the desired team-level performance.
More specifically, AGC-MAS uses contracts to specify the requirements for individual subtasks so that, when those requirements are met, the team task is completed as a whole. In particular, contracts define the conditions an agent may rely on while carrying out its subtask and the guarantees it must provide for that subtask to be considered safely completed. Formally, each contract specifies a subtask, an automaton that tracks its high-level progress and coordination with other subtasks, timeout and success-probability requirements, and dispatch behavior specifying the order in which subtasks are attempted.
This contract structure localizes the learning and execution associated with each subtask to its assigned agent, replacing a monolithic full-team learning problem with smaller, well-defined, and more tractable learning problems. Its modularity allows an agent or policy to be replaced without changing the implementations of other contracts, while contract composition ensures that meeting the local requirements collectively guarantees the required team-level performance. Our constructive algorithm automatically decomposes the team task into contracts with coordinating automata, while preserving the original team task under composition. Finally, IHA-MARL learns during training which heterogeneous agents are suited to each contract and adjusts their assignments accordingly. It also adapts the contracts’ required success probabilities to achieve the desired team-level success probability while minimizing the additional training required.

Figure 1. Heterogeneous team task: the team objective is encoded as an automaton over high-level events, together with a required probability that the team reaches the accepting state . A/G contracts: after indexing repeated events, the team-task automaton is automatically decomposed into agent-agnostic contracts, each specifying what the agent fulfilling the contract may assume and what its policy must guarantee. IHA-MARL: we formulate and solve an optimization problem to assign contracts and required performance guarantees to agents with heterogeneous capabilities. The assigned agents are trained with RL to satisfy their contracts, and the resulting policies are evaluated against the guarantees. Assignments and contract requirements are iteratively re-optimized and training continues until every guarantee is met or the training budget is exhausted. Compose: After training, each learned component (an agent together with its policy) satisfies its contract. Because contract satisfaction is preserved under composition, the composed team behavior satisfies the overall team requirement.
In a gridworld where agents with different movement capabilities coordinate pressure-plate activations to open gates, we demonstrate capability-aware reassignment and policy reuse. Across three cooperative benchmarks, IHA-MARL achieves observed 100% task success across five training seeds, with episode lengths comparable to the baselines. An empirical CPU timing pilot measured baseline training-loop times approximately 7–11× those of IHA-MARL.
Related Works
Distributed MARL leverages the decentralized structure of multi-agent tasks to enable parallel learning, robustness, and scalability [3]. Automata, long used in formal methods and model checking to specify and reason about system behavior, provide one way to structure this decentralization by representing high-level task progress and coordination [1, 4, 6]. More recently, reinforcement-learning frameworks such as Reward Machines (RMs) have used automata as high-level semantic descriptions of tasks, in which automaton states track task progress and transitions correspond to meaningful subgoals whose completion can provide reward to low-level policies [16]. This idea has also been extended to multi-agent settings, where local automata distribute high-level task information among agents and synchronize their progress toward a shared objective [11].
Existing approaches to decomposing such team-task automata construct local automata through projections onto subsets of the event alphabet and characterize when their composition preserves the original task [7]. In this work, we distinguish two roles that events play in these local automata: an agent may be responsible for realizing an event, or may need only to observe that event in order to synchronize its progress with the rest of the team. Projection at the level of event type does not distinguish different occurrences of the same event within a task, thereby coupling these two roles across all such occurrences. We instead index individual event occurrences, allowing realization and synchronization requirements to be specified independently at each point in the team task. This finer-grained representation enables the constructive decomposition developed in this paper.
Assume/guarantee (A/G) contract theory separates component requirements from their implementations and supports compositional reasoning about system behavior [2]. A/G formulations have been applied in multi-agent and dynamical-system settings [9, 13], and assumption/guarantee ideas have also been introduced in reinforcement learning [8]. However, existing RL formulations do not, to our knowledge, retain the full compositional structure of contract theory, which we adapt to MARL to support modular reasoning about learned agent behaviors.
On the algorithmic side, IHA-MARL builds on the training-sensitive optimization framework of Neary et al. Neary et al. [10], extending it to jointly determine heterogeneous agent–subtask assignments during training.
Method
As a running example, we introduce Chess-Maze (Figure 2), where a rook, king, and knight activate pressure plates to open gates and let the king reach the throne. Some gates require several plates to be held simultaneously. An automaton tracks the required activations and releases.

Figure 2. Left: An illustration of the Chess-Maze environment. A knight, king, and rook must learn to cooperate in order to press the colored pressure plates and open the gates of matching color so that the king may reach the throne. Multicolored gates open only while all of their plates are pressed simultaneously. Right: An automaton encoding this team task. Each transition is labeled by an event: , , , and denote pressing the corresponding pressure plate, and denote releasing it, and denotes the king reaching the throne. The upper and lower branches are alternative plans for completing the task.
Multi-Agent Reinforcement Learning
We model the underlying multi-agent MDP dynamics by , with the team task specified and learning objectives derived below. Let denote the set of agents. The joint state space is , where denotes the state space of agent , for , and denotes the state space of the environment. Let denote the initial joint state of the multi-agent environment. Similarly, the joint action space is , where is the action space of agent . The transition kernel defines a probability distribution over for each and .
For a subset of agents , let be the state space . For , its coordinate projection onto is , retaining only the tuple coordinates of agents in ; retains those of the complement agents . For a single agent , we write analogously. We use the same indexing convention for actions.
We do not require the dynamics of the agents to evolve independently in general. Instead, we assume that each agent admits an idle policy , under which the agent does not interfere with the dynamics of agents participating in the current task, where denotes the set of probability distributions over . More precisely, for any subset , if every agent follows its idle policy, so that , for , then the transition dynamics factor as
for appropriate transition kernels and . Thus, when the agents outside follow their idle policies, they neither affect the environment state nor interfere with the transition dynamics of the agents in .
In Chess-Maze, each agent state records its piece’s grid position, while records pressure-plate and gate states. Actions consist of the movements permitted by the corresponding chess piece together with a no-op; attempted moves through walls or closed gates leave the agent in place, while pressure-plate occupancy updates the gate states. Agents may share cells, so an idle agent repeatedly selects the no-op, preserving any plate it already occupies without obstructing other agents.
Automata as Descriptions of Team Tasks
We use automata to encode high-level task progress [11, 12]: events represent subgoal completions, low-level policies realize these events, and the automaton coordinates their composition toward the overall task.
Definition 3.1. An automaton is a tuple where is a finite set of events, is a finite set of states, is a transition relation, is an initial state, and is a set of final states indicating task completion. For brevity, we write as . An automaton is deterministic if and implies .
In Chess-Maze, the automaton in Figure 2 describes the high-level task of activating the pressure plates in a sequence that opens the gates and allows the king to reach the throne. For example, the event represents activation of the blue pressure plate. Some gates require several pressure plates to be activated before they open. As the required events occur, the automaton transitions through states representing the team’s progress toward task completion.
Individual agents, however, need not have access to the state of the complete team-task automaton or be aware of every event that occurs. An agent may instead maintain a local automaton describing only the events and task progress relevant to its role. Some events are realized by the agent itself, while others are realized by teammates and observed through communication, allowing the agent to track task progress and coordinate when to act. For example, rather than tracking the state of the complete team-task automaton, the king may only need to track whether the knight or rook has opened the final gate, an event it observes but does not realize itself. Once this event occurs, the king can proceed to reach the throne, an event that it realizes directly.
When an event is relevant to multiple agents, their local automata synchronize on that shared event. The king synchronizes with the knight on the event of the final gate opening, causing both local automata to advance to states in which the remaining task is for the king to reach the throne. Parallel composition provides a formal mechanism for combining such local automata while preserving this synchronization.
Definition 3.2. (Parallel Composition of Automata) The parallel composition of automata and we define as , where , , , , and
The operation of parallel composition is associative [1], so we lose no sleep in defining the composition of multiple automata as
Linking Automata to the Multi-Agent Environment
In order to make use of the automata for RL tasks, we need to create a bridge between high-level events and the low-level dynamics. To do so, we use labeling functions [11]. Let map each low-level state at a task state to the events that hold at that state. From this map, we can derive a low-level goal set, into which a policy must drive the system in order to realize an event. If we would like to trigger event at state , to effect the transition , then the goal set is .
To train such a policy, we must also determine the low-level entry set from which the policy may begin when the automaton enters state . Let be the set of transitions with destination . The entry set includes their goal sets and, at , the initial joint state:
Therefore, in order for a low-level policy to trigger a high level event at high level state , it must be trained to produce actions that bring the system from any state in to a state in . For example, a policy trained on the knight to press the blue button must find a path from any initial knight position with the blue gate yet unopened to a state where the knight is on the blue pressure plate.
Indexed Automata and Task Decomposition
In many automata-based multi-agent formulations, events are distributed among agents at the level of event type [11, 12]. For example, if the knight’s local automaton contains the yellow pressure-plate event, then every occurrence of that event is represented in its local task, even if only some occurrences are relevant to the knight. However, when the same event occurs at multiple points in the team task, it may be desirable for an agent to realize the event or synchronize with another agent’s realization of it on only particular occurrences.
In Chess-Maze, for example, the yellow pressure plate must be activated twice. On its first occurrence, the knight activates it to open the yellow gate, since before the red gate is opened the knight is the only agent capable of reaching the plate by jumping over the walls. On its second occurrence, however, the rook must activate the yellow plate while the knight simultaneously occupies the blue plate to open the final blue/yellow gate. The rook has no need to observe or synchronize on the first yellow-plate event. Requiring every occurrence of the same event type to be treated identically therefore imposes an unnecessary restriction on task allocation and synchronization, preventing different occurrences from being distributed independently among agents.
To distinguish these occurrences, we index events with the source state of their transition. Thus, the two yellow-plate events may be represented as and . Although both correspond to the same underlying event, their indices distinguish their roles within the team task and allow them to be assigned independently to different agents. This motivates the following definition.
Definition 3.3. (Indexed Automaton) Let be a deterministic automaton. The indexed automaton of is the automaton , where
For notational convenience, we write the indexed event as . Define iff .
We call an automaton indexed if it is obtained by this indexing construction.
When the team-task automaton is specified first, we must derive local automata whose parallel composition preserves it, so that completing the local subtasks guarantees completion of the original task. We formalize this requirement using automaton isomorphism, a stronger relation than the bisimulation notions commonly used in the literature.
Let denote the set of finite event strings over . For , write when there is a path . A state is reachable if for some . Define
Thus, contains the states reachable from , while contains the states from which is reachable, excluding $u itself.
Definition 3.4. (Isomorphic Automata) Let , be automata. We say that and are isomorphic if there exists a bijection such that and, for all and , if and only if ;
moreover, for every , if and only if . Then, we write .
Given a team-task automaton , we now ask how it can be decomposed into smaller automata whose parallel composition preserves the original task. Existing approaches construct agent automata by projecting the team-task automaton onto candidate subsets of its event alphabet and then verify whether their parallel composition preserves the original task [7, 14]. Finding a desirable decomposition may therefore require searching over different choices of local event sets. By indexing individual event occurrences, we instead obtain the following constructive decomposition with a fixed three-state structure.
Theorem 3.5. Let be a deterministic indexed automaton with a unique sink state , such that every state is reachable from and has a path to . Then, there exist automata with and such that .
The proof of Theorem 3.5 is constructive. We give the construction here, since it also provides the intuition behind the resulting local automata.
Let , where each indexed event labels a unique transition . For each , partition the team-task states into , , and . Let map each team-task state to its corresponding partition element.
The local automaton associated with retains precisely the indexed events needed to update this three-state view. Specifically, define , and let , where , , , and, for every , . Since indexed events label unique transitions, each is deterministic, and .
Each therefore stores exactly the high-level information needed to track its indexed event : whether that event may be required in the future (armed), is enabled at the current team-task state (active), or can no longer be required (resolved). Events other than appear in its alphabet only when their occurrence changes this status, allowing the local automata to remain synchronized with the evolving team task. We call a compositional atomic subtask automaton (CASA): it is atomic because it is centered on the realization of a single indexed event, and compositional because Theorem 3.5 establishes that the parallel composition of all such CASAs reconstructs the original team-task automaton. The complete proof constructs the corresponding isomorphism and is provided in the supplementary material.
Definition 3.6. We call the automaton constructed above for indexed event its compositional atomic subtask automaton (CASA).
We also write when .
Assume/Guarantee Contract Theory
We assume that indexed events in the team-task automaton are realized sequentially: at any time, at most one indexed event is dispatched for implementation. After an event is realized and the team-task automaton reaches its next state, several successor events may be available. A choice must therefore be made as to which event to dispatch for realization next. For example, at the initial state of Chess-Maze, the team must choose between alternative paths through the gates at the initial automaton state. We represent these choices using a high-level dispatching policy.
For an indexed event corresponding to the transition , define to be the set of indexed events whose transitions leave . Similarly, is the set of indexed events whose transitions leave the initial state.
Definition 3.7 (Dispatching Policy). A dispatching policy is a function such that whenever and whenever .
At initialization, the first indexed event is sampled according to . The initial dispatch policy is implemented by an external agent that commissions the team. Thereafter, when an indexed event is successfully realized, the next event is sampled according to . Thus, acts as a high-level policy over indexed events.
Let denote the desired probability that the team automaton reaches a state in and thereby completes the task successfully. To support such a team-level requirement, we associate each indexed event with a timeout and a required success probability . These event-level quantities form the performance requirements that will later be assigned through contracts.
We call any subset a subtask. A contract specifies a subtask together with requirements on its synchronization, reliability, timeout, and dispatch behavior.
Definition 3.8 (Contract). A contract is a tuple
where is a subtask, is the parallel composition of the CASAs corresponding to its indexed events, specifies the timeout for each indexed event, specifies its required probability of successful realization, and specifies its dispatch behavior.
A contract specifies the requirements that a subtask must satisfy, while a component specifies how that subtask is implemented. A component assigns a subteam of agents to each event in the subtask and specifies the policy executed by that subteam. Not every such assignment is feasible. For example, in Chess-Maze, the knight cannot be assigned to realize both and , since the two plates must be pressed simultaneously to open the gate.
Let denote the set of legal assignments of indexed events to subteams. We call a legal sub-assignment if it is the restriction of some . Let denote the set of probability distributions over the joint action set .
Definition 3.9 (Component). A component is a tuple
where is the set of indexed events implemented by the component, is a legal sub-assignment, for each , is a policy used by the assigned agents to realize , and is the component’s dispatching policy.
When is dispatched, the agents in execute while all other agents follow their idle policies. By the idle-policy assumption, these agents do not interfere with the dynamics of the dispatched subteam.
The low-level objective of each policy is derived from the labeling function defined in Subsection 3.3. For , define the local goal set , using the state projection notation defined in Subsection 3.1. Thus, reaching guarantees that is realized independently of the states of agents outside .
Likewise, define the local entry set
This is the projection of the possible low-level states encountered when the team-task automaton enters onto the state coordinates of the participating agents.
The subteam assigned to a dispatched event reports whether it successfully realizes that event; undispatched events are ignored by the automaton. For , let denote the joint policy under which the assigned subteam executes and all other agents execute their idle policies. For a set , let denote its first hitting time. The success probability achieved by component on within time is
Definition 3.10 (Contract Satisfaction). Component satisfies contract , written , if and, for every , , and for all .
Composition. Two contracts and are composable if . Their composition is
Because their event sets are disjoint, these unions are well-defined. The automaton component is determined by the combined subtask through the CASA construction, up to the canonical identification of product states.
Similarly, components and are composable if and is a legal sub-assignment. Their composition is obtained by taking the corresponding unions of their event sets, assignments, and policies.
Proposition 3.11. If and , and both pairs are composable, then .
This follows immediately because the requirements of a contract are event-wise, and composition preserves the satisfying implementation of each event.
For convenience, we call a contract atomic if , and likewise call a component atomic if . Every contract can be expressed as the composition of atomic contracts, and every component as the composition of atomic components.
Closed Contracts. A contract is closed if for every and for every and . Thus, the initial dispatch lies within the contract and any subsequent dispatch after an event implemented by the contract also lies within the contract. A closed contract therefore specifies a self-contained high-level task whose dispatched execution requires no external event implementation.
The contracts, components, and their composition operations instantiate the contract-theoretic framework of Benveniste et al. [2]. By separating the requirements of a subtask from its implementation, this formulation allows the team to replace one satisfying component with another without reconsidering the correctness of the overall team task. It also enables distributed learning and execution, since the policies associated with different subtasks can be trained and executed by their assigned subteams rather than by the full team jointly. Finally, the modular structure of contracts enables components to be reused across different higher-level contracts. For example, a component in which the knight activates the initial yellow pressure plate can be reused regardless of whether the subsequent team-level dispatching policy sends the team along the upper or lower path to the throne.
Iterative Heterogeneous Assignment
Given a desired team completion probability , we seek a collection of atomic contracts whose composition is closed and whose collective satisfaction guarantees the team-level requirement. We may restrict attention to atomic contracts because every contract can be expressed as a composition of them. These contracts specify the performance required for each indexed event, but do not assume that satisfying components are already available.
Here, IHA-MARL uses single-agent assignments, while the contract framework supports extensions to subteams. To construct a component for each atomic contract, we must determine which agent should be assigned to its indexed event and train a policy for that agent to realize the event with the required performance. Thus, we must jointly determine the agent assignments and the policies to train on those assignments. These decisions are coupled, since suitable assignments depend on the capabilities of the available policies, while those capabilities are themselves learned through training.
IHA-MARL addresses this coupling iteratively. At each iteration, the optimization chooses atomic contract requirements that collectively guarantee the team-level requirement while remaining as close as possible to the current performance of the assigned policies, thereby minimizing the additional training required. The policies associated with the selected assignments are then trained further, their performance is re-evaluated, and the optimization is solved again.
Since each atomic contract contains a single indexed event, we identify it by its event . A pair denotes the candidate assignment of agent to event , for which we maintain a policy trained to realize . Let indicate whether this assignment is selected, and let denote the current estimated success probability of its policy, evaluated according to Equation (1) using the fixed timeout . In practice, is estimated empirically from rollouts initialized from the corresponding entry set and is set to zero if no policy has yet been trained for . These empirical estimates are not certified lower bounds on the worst-case success probabilities. Following [10], Hoeffding’s inequality can quantify uncertainty in success estimates from independent evaluation rollouts. Certification of the worst-case probability in Equation (1) additionally requires bounds that hold uniformly over the entry set.
For each , let denote the required success probability of its atomic contract and let denote its discounted occupancy in the high-level dispatch process. Together with the corresponding dispatch behavior, a selected assignment and its policy define an atomic component.
For the optimization, we collapse the accepting states into the terminal sink state of the automaton and assign reward to indexed events whose transitions enter through the collapsed accepting states, with otherwise. The resulting expected discounted reward therefore represents discounted task-completion probability. We add an artificial terminal self-loop , with and , for flow bookkeeping. It acts as a flow sink: its occupancy absorbs flow reaching without contributing to the incoming-flow sums. The flow constraints below use the state set and transition incidences of this modified automaton. Let denote the maximum discounted completion reward obtainable under the same flow constraints when all event success probabilities are set to one. Thus, represents the best performance permitted by the task structure in the absence of execution failures.
Extending the flow formulation of Neary et al. [10] to the heterogeneous multi-agent setting, we choose the assignments, contract
| Event | 0.94 | 1.31 | 1.88 | 2.50 | 2.75 |
| Upper path () | |||||
| ♟ 0.01 | – | – | – | – | |
| ♟ 0.98 | – | – | – | – | |
| ♟ 1.00 | – | – | – | – | |
| ♞ 0.99 | – | – | – | – | |
| ♟ 0.55 | – | – | – | – | |
| Lower path () | |||||
| – | ♟ 0.00 | ♜ 0.00 | ♞ 0.99 | ♞ 0.99 | |
| – | ♟ 0.00 | ♞ 1.00 | ♞ 1.00 | ♞ 1.00 | |
| – | ♜ 0.00 | ♜ 0.00 | – | ♜ 0.98 | |
| – | ♟ 0.98 | ♟ 1.00 | – | ♟ 1.00 | |
| – | – | – | ♟ 1.00 | – | |
| – | – | – | ♜ 0.02 | – | |
| – | ♞ 1.00 | ♞ 1.00 | ♞ 1.00 | ♜ 1.00 | |
| – | ♟ 0.71 | ♟ 0.99 | ♟ 0.99 | ♟ 0.99 |
Table 1. Agent assignments during Chess-Maze training. Each entry specifies the agent (♟, ♞, or ♜) assigned to an indexed event and its estimated success probability. Events not required by the current high-level plan are left blank. Red values indicate an empirical success probability that is well below the algorithm-specified requirement (between 0.97 and 1 throughout). Shaded entries indicate that a new agent has been assigned to the event since it was last required.
requirements, and occupancies by solving
We solve this optimization problem using Gurobi, as in [10]. Here, and denote the indexed events leaving and entering automaton state , respectively, is the initial state, and is the discount factor. The linear constraints encode the admissible agent assignments, while contains agent–event pairs whose policies are treated as converged.
The objective minimizes the total improvement requested beyond the current performance of the selected policies, while the reward and flow constraints ensure that the resulting atomic contracts achieve at least . The optimization specifies target requirements; the trainer iteratively improves the selected policies toward these targets, with achieved performance assessed by evaluation. For a selected converged pair , the upper and lower bounds force , preventing the optimizer from requesting further improvement from that policy.
After each solve, up to non-converged selected pairs with the largest positive deficits are chosen for further training. Each selected policy is initialized if necessary and trained for a batch of up to epochs, capped by its remaining per-pair budget of epochs. The resulting values are then updated and the optimization is solved again. Once a policy reaches training epochs, its pair is added to . Training stops when no selected pair has a positive deficit beyond the evaluation tolerance, the requirements problem becomes infeasible, or the total training budget is exhausted. The dispatching policy is recovered from the resulting occupancies by normalizing the positive values over the events enabled at each automaton state.
Experimental Results
We evaluate IHA-MARL as described above in our Chess-Maze example and compare its performance with the Monolithic, ATAD, and LOTaD baselines on Cooperative Buttons, Four Buttons, and Asymmetric Advantages. These cooperative multi-agent gridworlds require agents to work together to complete tasks, with some steps requiring multiple agents to act together. The Chess-Maze experiment illustrates capability-aware assignment and training, while the benchmark comparisons measure task success and episode length. IHA-MARL’s low-level policies use tabular Q-learning. Experimental settings are provided in the supplementary material.
Table 1 reports the selected agents and their estimated success probabilities during training in our Chess-Maze example (Figure 2). After approximately nominal training steps, the king’s performance on and remains below the contract requirements, prompting a switch from the upper to the lower path. With slip probability 0.2, unintended moves can send agents into lava, potentially contributing to the king’s difficulty on . On the lower path, and pass to the knight, the order of the simultaneous presses briefly reverses through and , and assigning to the rook permits the knight to perform . The resulting team completes the maze in the recorded rollout, illustrating capability-aware reassignment under the coordination constraints.
Successful same-agent policies are also reused at other automaton indices with matching event labels, followed by further training and validation. The reassignment of task roles illustrates the flexibility underlying component substitutability: alternative implementations can be considered subject to the same contract requirements and legal-assignment constraints. Unlike the baseline implementations, IHA-MARL explicitly tracks agent–event success estimates and uses contract requirements to determine which policies need further training.
Figure 3 shows that IHA-MARL reaches observed success rates of 100% in all three environments at the displayed budget endpoints, whereas baseline reliability varies across environments. Episode lengths are comparable, though somewhat longer in some environments, consistent with our sequential rather than concurrent task execution. An empirical CPU timing pilot recorded baseline training-loop times approximately 7–11× those of IHA-MARL; its

Figure 3. Evaluation performance of IHA-MARL (ours), LOTaD, ATAD, and Monolithic policies on Cooperative Buttons, Four Buttons, and Asymmetric Advantages versus cumulative training timesteps. Top: proportion of evaluation episodes completing the team task. Bottom: mean completion steps; failures contribute the episode horizon. Curves show smoothed means across five independent training seeds; shaded bands denote pointwise 90% Student- confidence intervals across seeds. After training terminates, the final evaluation estimate is held constant to the end of the comparison budget.
settings and measurements are provided in the supplementary material.
Conclusions
We present an assume/guarantee contract theory for heterogeneous multi-agent reinforcement learning (MARL), in which contracts specify subtasks and a required success probability, so that any capable agent can satisfy them. We introduce the compositional atomic subtask automaton (CASA) and use it to obtain a constructive decomposition of team-task automata satisfying the assumptions of Theorem 3.5 into subtasks, removing the need to search over candidate decompositions. 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× more training-loop time. Future work includes allowing independent contracts to execute concurrently rather than dispatching one indexed event at a time, relaxing the assumptions that idle agents do not interfere with one another and that the team-task automaton and labeling function are given, and developing contract refinement to further support the reuse of learned components across tasks and teams.
References
Supplementary Material
The following appendices provide the complete decomposition proof and experimental details for this paper.
Complete Proof of the Automata Decomposition Theorem
For completeness, we provide the full proof of Theorem 3.5 from the main paper.
Theorem A.1 (Automata Decomposition). Let
be a finite deterministic indexed automaton with a unique sink state , such that every state is reachable from and has a path to . Then there exist automata
with
such that
Proof. Let
where, because is indexed, each event labels a unique transition
Construction of the local automata. For each indexed event , partition into
where denotes the set of states from which is reachable, excluding itself.
Define
by
We include in the alphabet of every indexed event whose transition changes the th partition state, together with itself:
In particular, for every , and hence
Now define
where
and, for every ,
Because each indexed event labels a unique transition in , each induces a unique transition in . Therefore each is deterministic.
Let
and define
by
We show that defines an isomorphism between and the reachable portion of . Since for every , we have , the initial state of $M.
Injectivity. Suppose . First suppose that is not the sink state. Since every state has a path to the sink, is the source of some transition
Hence , and therefore
Since , their th coordinates agree:
But
so implies
It remains to consider the case in which is the sink. If were not the sink, then applying the preceding argument to would give some such that
Since the active block of the th partition is the singleton and the sink is not , we would have
contradicting . Thus , and is injective.
Preservation of transitions. We next show that transitions of induce transitions of . Suppose
in . For each local automaton , there are two cases. If , then by construction
If , then by the definition of ,
Therefore, by the definition of parallel composition,
in .
No additional reachable transitions. Conversely, suppose
in . Since , the th component must execute its transition. The source of that transition is
so
Because the active block of the th partition is the singleton , it follows that
Let be the unique state satisfying
in . By the forward direction already established,
in . Each is deterministic, and therefore their parallel composition is deterministic: from any product state, each component has at most one successor under a given event, and consequently so does the product. Hence
Thus every transition of originating from a state in the image of corresponds uniquely to the transition with the same label in .
Reachable states. By definition, automaton isomorphism here requires a bijection between the reachable states of the two automata. Every state of is reachable from by assumption. Since transitions are preserved in the forward direction, every with is reachable from
in .
It remains to show that has no other reachable states. We proceed by induction on the length of a path from . The initial product state is clearly in the image of . Now suppose that a reachable product state is of the form and that
By the converse transition argument above,
Thus every reachable successor of a state in the image of also lies in the image of . By induction, every reachable state of belongs to .
Since is injective, it follows that
is a bijection.
Accepting states. Finally, we show that preserves acceptance. If , then by definition of ,
for every . Therefore
Conversely, suppose . Since the unique sink state belongs to , is not the sink. Because has a path to the sink, it is therefore the source of some transition
Hence
The corresponding partition block is the singleton
Since , no accepting state is mapped to active by , and therefore
Consequently,
Thus is a bijection between the states of and the reachable states of that preserves the initial state, labelled transitions, and accepting states. Hence
Experimental Details
Environments
Chess-Maze. The map and task automaton appear in the main paper. The king moves to adjacent cells, the knight makes chess-knight jumps, and the rook moves along unobstructed rows or columns; all can stay. Pressure-plate events occur on entry, while simultaneous activations require distinct agents to hold the relevant plates. Release events are executed by the agent currently occupying the corresponding plate, and only the king can reach the throne. Walls and closed gates block movement; entering lava disables an agent. In the reported run (seed 1), each non-stay action has probability 0.2 of being replaced by a uniformly sampled passable adjacent move. The scheduler table records nominal steps: training episodes multiplied by the local horizon of 50, rather than actual transitions. The saved team is executed for at most 1,000 ticks; the reported completion is one demonstration rollout.
Cooperative Buttons and Four Buttons. Both use grids with cardinal moves and a stay action. Movement succeeds as intended with probability 0.98; each perpendicular direction has probability 0.01. Cooperative Buttons uses three agents: yellow and green buttons enable access for other agents, and two agents must jointly hold the red button to allow the remaining agent to reach the goal. Four Buttons uses two agents to activate all four buttons; activating red before yellow irreversibly violates the task.
Asymmetric Advantages. Two cooks occupy separate sides of a kitchen with a shared pot. They add three onions, wait 20 ticks for cooking, collect soup using a dish, and deliver it. Different distances to ingredients and delivery locations create asymmetric roles. IHA-MARL represents cooking as an autonomous waiting component with an analytically computed probability of completion within its deadline, rather than a learned third agent.
Training and Evaluation
Each training epoch comprises one local episode. IHA-MARL trains tabular -policies sequentially, with learning rate 0.2 and constant -greedy exploration . Local rewards are 1 on completing the event and −0.01 otherwise. Each iteration trains at most ten selected agent–event policies; pairs reaching their episode limit are treated as converged. Training stops when no selected policy needs improvement or the requirements problem is infeasible. For learned policies, capability success after each batch is the fraction of 128 greedy validation episodes completing the event within its local horizon, with initial states sampled from the component’s reachable entry set. These empirical estimates are not certified worst-case probabilities. Policies for the same agent and event label can initialize tasks at other automaton indices and are then trained and revalidated. The target in Table 2 is a fraction of ideal abstract discounted return, not a measured whole-team success threshold.
| Chess-Maze | CB | FB | AA | |
| IHA-MARL | ||||
| Target fraction | 0.95 | 0.98 | 0.98 | 0.95 |
| Q-learning discount | 0.95 | 0.95 | 0.95 | 0.99 |
| Team-model discount | 0.99 | 0.95 | 0.97 | 0.99 |
| Local horizon (ticks) | 50 | 100 | 100 | 200 |
| Episodes per capability batch | 1,250 | 1,000 | 1,000 | 1,000 |
| Maximum episodes per capability | 5,000 | 10,000 | 20,000 | 20,000 |
| Capabilities before re-solving | 10 | 10 | 10 | 10 |
| Configured team horizon (ticks) | 1,000 | 100 | 100 | 200 |
| Plotted comparison budget | — | |||
| PPO baselines | ||||
| Learning rate | — | |||
| Discount | — | 0.95 | 0.97 | 0.99 |
| Entropy coefficient | — | 0.1 | 0.1 | 0.01 |
| Target KL | — | 0.05 | 0.1 | None |
Table 2. Parameters for the reported Chess-Maze demonstration and original five-seed comparison. CB: Cooperative Buttons; FB: Four Buttons; AA: Asymmetric Advantages. Horizons and capability limits are in episodes or ticks as indicated; budgets use the counters described above.
The PPO baselines use the LOTaD implementation.1 Monolithic assigns each agent the full team task; ATAD fixes one candidate decomposition; LOTaD uses UCB to select among ten candidates. Decomposition scoring uses size and balance weights 2 and 0.5, respectively; UCB uses exploration coefficient 0.5 and forgetting factor 1. PPO uses shared task-conditioned policies with two 64-unit tanh hidden layers, rollout length 2,048, minibatches of 256, five epochs, GAE parameter 0.95, clipping 0.2, value-loss coefficient 0.5, and gradient-norm limit 0.5.
The comparison uses seeds 11–15. The original IHA-MARL runs have no global training cap; plotted observations are restricted to the budgets in Table 2. Its counter sums physical transitions during low-level training and excludes validation and testing. PPO counts agent slots: three per joint step in Cooperative Buttons and two in the other domains. Thus equal numerical budgets do not imply equal joint interactions or wall-clock time. Chess-Maze’s nominal counter is separate from both conventions.
IHA-MARL checkpoints request 20 greedy whole-team evaluations every 50,000 training transitions, with 50 additional final tests per seed. Baseline checkpoints use one stochastic-policy evaluation episode, every 15,000, 10,000, and 3,000 agent slots in Cooperative Buttons, Four Buttons, and Asymmetric Advantages, respectively. Success means acceptance of the team task; episode lengths include failures and retain each implementation’s termination conventions. For plotting, IHA-MARL observations are carried forward onto a 50,000-step grid and smoothed using trailing windows of 15, 10, and 3 points, respectively; baseline windows contain 50 observations. Means and pointwise 90% Student- intervals are computed across the five smoothed seed curves. If training terminates due to successful trained and assigned components, the final available estimate is carried forward to the plot boundary for visualization. Observations beyond the plotted budget are excluded.
Parameters and Timing
Separate timing pilots use seeds 11–13, a nominal counter limit of 100,000, and unchanged learning settings. Jobs run sequentially on an Apple M1 CPU, with PyTorch, BLAS/OpenMP, and Gurobi limited to one thread. Each checkpoint uses one evaluation episode, approximately every 20,000 counter units; IHA-MARL also performs one final test and retains its 128-episode capability validations. Table 3 reports median elapsed training-loop time including checkpoint evaluations. PPO’s timer covers learn; IHA-MARL’s also includes assignment optimization, capability validation, serialization, and an execution check. Process startup is excluded. PPO completes rollouts beyond the cap, and IHA-MARL can stop early (as occurred for one Cooperative Buttons seed). These pilots measure implementation cost under the stated counters, rather than time to a specified success rate; they do not establish full-budget speedups or isolate assignment from the Q-learning/PPO learner difference.
| Environment | IHA-MARL | Monolithic | ATAD | LOTaD |
| Cooperative Buttons | 1.10 | 10.29 | 10.77 | 10.20 |
| Four Buttons | 1.89 | 14.09 | 15.70 | 14.72 |
| Asymmetric Advantages | 132.02 | 1,400.38 | 1,447.00 | 1,368.63 |
Table 3. Median training-loop time in seconds over three timing-pilot seeds.
References
- [1]Christel Baier and Joost-Pieter Katoen. 2008. Principles of Model Checking. The MIT Press. https://mitpress.mit.edu/9780262026499/principles-of-model-checking/
- [2]Albert Benveniste, Benoît Caillaud, Dejan Nickovic, Roberto Passerone, Jean-Baptiste Raclet, Philipp Reinkemeier, Alberto Sangiovanni-Vincentelli, Werner Damm, Thomas A. Henzinger, and Kim G. Larsen. 2018. Contracts for System Design. Found. Trends Electron. Des. Autom. 12, 2–3 (March 2018), 124–400. doi:10.1561/1000000053
- [3]Lucian Busoniu, Robert Babuska, and Bart De Schutter. 2008. A Comprehensive Survey of Multiagent Reinforcement Learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 38, 2 (2008), 156–172. doi:10.1109/TSMCC.2007.913919
- [4]Xuchu Ding, Stephen Smith, Calin Belta, and Daniela Rus. 2014. Optimal Control of Markov Decision Processes With Linear Temporal Logic Constraints. IEEE Trans. Automat. Control 59 (05 2014), 1244–1257. doi:10.1109/TAC.2014.2298143DOI
- [5]Taicheng Guo, Xueying Chen, Yiqing Wan, Ruiqi Zhang, Shichao Pei, Nitesh Chawla, Olaf Wiest, and Xiangliang Zhang. 2024. Large Language Model based Multi-Agents: A Survey of Progress and Challenges. doi:10.13140/RG.2.2.36311.85928DOI
- [6]Lewis Hammond, Alessandro Abate, Julian Gutierrez, and Michael Wooldridge. 2021. Multi-Agent Reinforcement Learning with Temporal Logic Specifications. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (Virtual Event, United Kingdom) (AAMAS ’21). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 583–592.arxiv.org/abs/2102.00582
- [7]Mohammad Karimadini and Hai Lin. 2011. Guaranteed global performance through local coordinations. Automatica 47, 5 (May 2011), 890–898. doi:10.1016/j.automatica.2011.01.078DOI
- [8]Milad Kazemi, Mateo Perez, Fabio Somenzi, Sadegh Soudjani, Ashutosh Trivedi, and Alvaro Velasquez. 2024. Assume-guarantee reinforcement learning. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence (AAAI’24/IAAI’24/EAAI’24). AAAI Press, Article 2368, 9 pages. doi:10.1609/aaai.v38i9.30116arxiv.org/abs/2312.09938
- [9]Siyuan Liu, Adnane Saoud, Pushpak Jagtap, Dimos V. Dimarogonas, and Majid Zamani. 2022. Compositional Synthesis of Signal Temporal Logic Tasks via Assume-Guarantee Contracts. In 2022 IEEE 61st Conference on Decision and Control (CDC). 2184–2189. doi:10.1109/CDC51059.2022.9992715DOI
- [10]Cyrus Neary, Christos Verginis, Murat Cubuktepe, and Ufuk Topcu. 2022. Verifiable and Compositional Reinforcement Learning Systems. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 32. 529–537.arxiv.org/abs/2106.05864
- [11]Cyrus Neary, Zhe Xu, Bo Wu, and Ufuk Topcu. 2021. Reward Machines for Cooperative Multi-Agent Reinforcement Learning. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (Virtual Event, United Kingdom) (AAMAS ’21). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 934–942.
- [12]Ameesh Shah, Niklas Lauffer, Thomas Chen, Nikhil Pitta, and Sanjit A. Seshia. 2025. Learning Symbolic Task Decompositions for Multi-Agent Teams. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (Detroit, MI, USA) (AAMAS ’25). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1904–1913.arxiv.org/abs/2502.13376
- [13]Miel Sharf, Bart Besselink, Adam Molin, Qiming Zhao, and {Karl Henrik} Johansen. 2021. Assume/Guarantee Contracts for Dynamical Systems: Theory and Computational Tools. In Proceedings of the 7th IFAC Conference on Analysis and Design of Hybrid Systems, Brussels, Belgium (IFAC-PapersOnLine, 5), {Raphaël M.} {Jungers} and {Necmiye} {Ozay} (Eds.). Elsevier, 25–30. 7th IFAC Conference on Analysis and Design of Hybrid Systems ADHS 2021; Conference date: 07-07-2021 Through 09-07-2021. doi:10.1016/j.ifacol.2021.08.469DOI
- [14]Sophia Smith, Cyrus Neary, and Ufuk Topcu. 2023. Automatic Decomposition of Reward Machines for Decentralized Multiagent Reinforcement Learning. In 2023 62nd IEEE Conference on Decision and Control (CDC). 5423–5430. doi:10.1109/CDC49753.2023.10384224DOI
- [15]Peter Stone and Manuela Veloso. 2000. Multiagent Systems: A Survey from a Machine Learning Perspective. Autonomous Robots 8 (05 2000). doi:10.1023/A:1008942012299DOI
- [16]Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. McIlraith. 2022. Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research 73 (Jan. 2022), 173–208. doi:10.1613/jair.1.12440