betaFeedback

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 100%100\% final evaluation success. In CPU timing pilots, comparable baselines required approximately 77–11×11\times 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.

Heterogeneous team task, assume/guarantee contracts, IHA-MARL, and compose workflow

Figure 1. Heterogeneous team task: the team objective is encoded as an automaton over high-level events, together with a required probability pteamp_{\mathrm{team}} that the team reaches the accepting state uFu_F. 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.

Chess-Maze environment and automaton

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: YY, RR, BB, and PP denote pressing the corresponding pressure plate, ¬Y\neg Y and ¬B\neg B denote releasing it, and TT 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 M=(S,A,P)\mathcal{M} = (S,A,P), with the team task specified and learning objectives derived below. Let I={i1,i2,…,in}I = \{i_1,i_2,\ldots,i_n\} denote the set of agents. The joint state space is S=S1×⋯×Sn×SeS = S_1 \times\cdots\times S_n \times S_e, where SmS_m denotes the state space of agent imi_m, for 1≤m≤n1 \leq m \leq n, and SeS_e denotes the state space of the environment. Let sinit∈Ss_{\mathrm{init}} \in S denote the initial joint state of the multi-agent environment. Similarly, the joint action space is A=A1×⋯×AnA = A_1 \times\cdots\times A_n, where AmA_m is the action space of agent imi_m. The transition kernel P(s′∣s,a)P(s' \mid s,a) defines a probability distribution over SS for each s∈Ss \in S and a∈Aa \in A.

For a subset of agents D={ij1,…,ijk}D = \{i_{j_1},\ldots,i_{j_k}\}, let SDS_D be the state space Sj1×…×SjkS_{j_1} \times\ldots\times S_{j_k}. For s=(s1,…,sn,se)s = (s_1,\ldots,s_n,s_e), its coordinate projection onto SDS_D is sD=(sj1,…,sjk)s_D = (s_{j_1},\ldots,s_{j_k}), retaining only the tuple coordinates of agents in DD; s−Ds_{-D} retains those of the complement agents I∖DI \setminus D. For a single agent iji_j, we write s−js_{-j} 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 iji_j admits an idle policy πidlej:Sj→Δ(Aj)\pi_{\mathrm{idle}}^j : S_j \to\Delta(A_j), under which the agent does not interfere with the dynamics of agents participating in the current task, where Δ(Aj)\Delta(A_j) denotes the set of probability distributions over AjA_j. More precisely, for any subset D⊆ID \subseteq I, if every agent ij∉Di_j \notin D follows its idle policy, so that aj∼πidlej(sj)a_j \sim\pi_{\mathrm{idle}}^j(s_j), for ij∉Di_j \notin D, then the transition dynamics factor as

P(sD′,s−D′,se′∣sD,s−D,se,aD,a−D)=PD(sD′,se′∣sD,se,aD)P−D(s−D′∣s−D,a−D).P(s'_D,s'_{-D},s'_e \mid s_D,s_{-D},s_e,a_D,a_{-D}) = P_D(s'_D,s'_e \mid s_D,s_e,a_D)P_{-D}(s'_{-D} \mid s_{-D},a_{-D}).

for appropriate transition kernels PDP_D and P−DP_{-D}. Thus, when the agents outside DD follow their idle policies, they neither affect the environment state nor interfere with the transition dynamics of the agents in DD.

In Chess-Maze, each agent state records its piece’s grid position, while SeS_e 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 A=(Σ,U,uI,F,→)A = (\Sigma,U,u_I,F,\to) where Σ\Sigma is a finite set of events, UU is a finite set of states, →⊆U×Σ×U\to\subseteq U \times\Sigma\times U is a transition relation, uIu_I is an initial state, and FF is a set of final states indicating task completion. For brevity, we write (u,α,v)∈→(u,\alpha,v) \in\to as u→αvu \xrightarrow{\alpha} v. An automaton is deterministic if u→αvu \xrightarrow{\alpha} v and u→αwu \xrightarrow{\alpha} w implies v=wv=w.

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 BB 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 A1=(Σ1,U1,u1I,F1,→1)A_1 = (\Sigma_1, U_1, u_1^I, F_1, \to_1) and A2=(Σ2,U2,u2I,F2,→2)A_2 = (\Sigma_2, U_2, u_2^I, F_2, \to_2) we define as A1∥A2=(Σ,U,uI,F,→)A_1 \parallel A_2 = (\Sigma, U, u^I, F, \to), where Σ=Σ1∪Σ2\Sigma= \Sigma_1 \cup\Sigma_2, U=U1×U2U = U_1 \times U_2, uI=(u1I,u2I)u^I = (u_1^I, u_2^I), F=F1×F2F = F_1 \times F_2, and

(u1,u2)→α(u1′,u2′)⟺{u1→1αu1′∧u2→2αu2′if α∈Σ1∩Σ2u1→1αu1′∧u2=u2′if α∈Σ1∖Σ2u2→2αu2′∧u1=u1′if α∈Σ2∖Σ1undefinedelse(u_1,u_2) \mathrel{\to^\alpha} (u'_1,u'_2) \Longleftrightarrow \begin{cases} u_1 \mathrel{\to^\alpha_1} u'_1 \land u_2 \mathrel{\to^\alpha_2} u'_2 & \text{if } \alpha\in\Sigma_1 \cap\Sigma_2 \\ u_1 \mathrel{\to^\alpha_1} u'_1 \land u_2 = u'_2 & \text{if } \alpha\in\Sigma_1 \setminus\Sigma_2 \\ u_2 \mathrel{\to^\alpha_2} u'_2 \land u_1 = u'_1 & \text{if } \alpha\in\Sigma_2 \setminus\Sigma_1 \\ \text{undefined} & \text{else} \end{cases}

The operation of parallel composition is associative [1], so we lose no sleep in defining the composition of multiple automata as

∥i=1nAi=A1∥(A2∥…(An−1∥An)…).\mathop{\parallel}_{i=1}^{n} A_i = A_1 \parallel(A_2 \parallel\ldots(A_{n-1} \parallel A_n) \ldots).

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 L:U×S→2ΣL : U \times S \to2^\Sigma 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 α\alpha at state uu, to effect the transition u→αu′u \mathrel{\to^\alpha} u', then the goal set is G(u,α)={s∈S:α∈L(u,s)}G(u,\alpha) = \{s \in S : \alpha\in L(u,s)\}.

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 uu. Let prec⁡(u)⊆→\operatorname{prec}(u) \subseteq\to be the set of transitions with destination uu. The entry set includes their goal sets and, at uIu_I, the initial joint state:

I(u)=⋃(v,α,u)∈prec⁡(u)G(v,α)∪{{sinit},u=uI,∅,u≠uI.\mathcal{I}(u) = \bigcup_{(v,\alpha,u)\in\operatorname{prec}(u)} G(v,\alpha) \cup \begin{cases} \{s_{\mathrm{init}}\}, & u = u_I,\\ \varnothing, & u \ne u_I. \end{cases}

Therefore, in order for a low-level policy to trigger a high level event α\alpha at high level state uu, it must be trained to produce actions that bring the system from any state in I(u)\mathcal{I}(u) to a state in G(u,α)G(u,\alpha). 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 Y1Y_1 and Y2Y_2. 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 A=(Σ,U,uI,F,→)A = (\Sigma,U,u_I,F,\to) be a deterministic automaton. The indexed automaton of AA is the automaton A′=(Σ′,U,uI,F,→′)A' = (\Sigma',U,u_I,F,\to'), where

Σ′={(u,α)∈U×Σ:∃v∈U such that u→αv}.\Sigma' = \{(u,\alpha) \in U \times\Sigma: \exists v \in U \text{ such that } u \mathrel{\to^\alpha} v\}.

For notational convenience, we write the indexed event (u,α)(u,\alpha) as αu\alpha_u. Define u→αuvu \mathrel{\to^{\alpha_u}} v iff u→αvu \mathrel{\to^\alpha} v.

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 Σ∗\Sigma^* denote the set of finite event strings over Σ\Sigma. For σ=α1⋯αn∈Σ∗\sigma= \alpha_1 \cdots\alpha_n \in\Sigma^*, write u→σvu \mathrel{\to^\sigma} v when there is a path u→α1⋯→αnvu \mathrel{\to^{\alpha_1}} \cdots\mathrel{\to^{\alpha_n}} v. A state uu is reachable if uI→σuu_I \mathrel{\to^\sigma} u for some σ∈Σ∗\sigma\in\Sigma^*. Define

r(u)={v∈U:∃σ∈Σ∗, u→σv},r(u) = \{v \in U : \exists\sigma\in\Sigma^*,\ u \mathrel{\to^\sigma} v\},
s(u)={v∈U:∃σ∈Σ∗, v→σu}∖{u}.s(u) = \{v \in U : \exists\sigma\in\Sigma^*,\ v \mathrel{\to^\sigma} u\} \setminus\{u\}.

Thus, r(u)r(u) contains the states reachable from uu, while s(u)s(u) contains the states from which uu is reachable, excluding $u itself.

Definition 3.4. (Isomorphic Automata) Let Ai=(Σ,U,uiI,Fi,→i)A_i = (\Sigma,U,u_i^I,F_i,\to_i), i=1,2i = 1,2 be automata. We say that A1A_1 and A2A_2 are isomorphic if there exists a bijection f:r(u1I)→r(u2I)f : r(u_1^I) \to r(u_2^I) such that f(u1I)=u2If(u_1^I) = u_2^I and, for all u1,u1′∈r(u1I)u_1,u'_1 \in r(u_1^I) and α∈Σ\alpha\in\Sigma, u1→1αu1′u_1 \mathrel{\to^\alpha_1} u'_1 if and only if f(u1)→2αf(u1′)f(u_1) \mathrel{\to^\alpha_2} f(u'_1);

moreover, for every u∈r(uI1)u \in r(u_I^1), u∈F1u \in F_1 if and only if f(u)∈F2f(u) \in F_2. Then, we write A1≅A2A_1 \cong A_2.

Given a team-task automaton AA, 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 A=(Σ,U,uI,F,→)A = (\Sigma, U, u_I, F, \to) be a deterministic indexed automaton with a unique sink state s∈Fs \in F, such that every state is reachable from uIu_I and has a path to ss. Then, there exist ∣Σ∣|\Sigma| automata Ai=(Σi,Ui,uIi,Fi,→i)A_i = (\Sigma_i, U_i, u_I^i, F_i, \to_i) with Ui={armed,active,resolved}U_i = \{\mathrm{armed}, \mathrm{active}, \mathrm{resolved}\} and ⋃iΣi=Σ\bigcup_i \Sigma_i = \Sigma such that A≅∥iAiA \cong\parallel_i A_i.

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 Σ={α1,…,αm}\Sigma= \{\alpha_1, \ldots, \alpha_m\}, where each indexed event αi\alpha_i labels a unique transition ui→αiviu_i \xrightarrow{\alpha_i} v_i. For each αi\alpha_i, partition the team-task states into Uarmedi=s(ui)U_{\mathrm{armed}}^i = s(u_i), Uactivei={ui}U_{\mathrm{active}}^i = \{u_i\}, and Uresolvedi=U∖(s(ui)∪{ui})U_{\mathrm{resolved}}^i = U \setminus(s(u_i) \cup\{u_i\}). Let qi:U→{armed,active,resolved}q_i: U \to\{\mathrm{armed}, \mathrm{active}, \mathrm{resolved}\} map each team-task state to its corresponding partition element.

The local automaton associated with αi\alpha_i retains precisely the indexed events needed to update this three-state view. Specifically, define Σi={αj∈Σ:qi(uj)≠qi(vj)}∪{αi}\Sigma_i = \{\alpha_j \in\Sigma: q_i(u_j) \ne q_i(v_j)\} \cup\{\alpha_i\}, and let Ai=(Σi,Ui,uIi,Fi,→i)A_i = (\Sigma_i, U_i, u_I^i, F_i, \to_i), where Ui={armed,active,resolved}U_i = \{\mathrm{armed}, \mathrm{active}, \mathrm{resolved}\}, uIi=qi(uI)u_I^i = q_i(u_I), Fi={qi(u):u∈F}F_i = \{q_i(u) : u \in F\}, and, for every αj∈Σi\alpha_j \in\Sigma_i, qi(uj)→αjiqi(vj)q_i(u_j) \xrightarrow{\alpha_j}_i q_i(v_j). Since indexed events label unique transitions, each AiA_i is deterministic, and ⋃iΣi=Σ\bigcup_i \Sigma_i = \Sigma.

Each AiA_i therefore stores exactly the high-level information needed to track its indexed event αi\alpha_i: 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 αi\alpha_i 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 AiA_i 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 AiA_i constructed above for indexed event αi\alpha_i its compositional atomic subtask automaton (CASA).

We also write Aαu=AiA_{\alpha_u} = A_i when αu=αi\alpha_u = \alpha_i.

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 αu\alpha_u corresponding to the transition u→αvu \xrightarrow{\alpha} v, define succ⁡(αu)\operatorname{succ}(\alpha_u) to be the set of indexed events whose transitions leave vv. Similarly, succ⁡(uI)\operatorname{succ}(u_I) is the set of indexed events whose transitions leave the initial state.

Definition 3.7 (Dispatching Policy). A dispatching policy is a function μ:({⊥}∪Σ)×Σ→[0,1]\mu: (\{\mathord{\bot}\} \cup\Sigma) \times\Sigma\to[0,1] such that μ(β∣x)=0\mu(\beta\mid x) = 0 whenever β∉succ⁡(x)\beta\notin\operatorname{succ}(x) and ∑β∈succ⁡(x)μ(β∣x)=1\sum_{\beta\in\operatorname{succ}(x)} \mu(\beta\mid x) = 1 whenever succ⁡(x)≠∅\operatorname{succ}(x) \ne\varnothing.

At initialization, the first indexed event is sampled according to μ(⋅∣uI)\mu(\cdot\mid u_I). The initial dispatch policy is implemented by an external agent that commissions the team. Thereafter, when an indexed event αu\alpha_u is successfully realized, the next event is sampled according to μ(⋅∣αu)\mu(\cdot\mid\alpha_u). Thus, μ\mu acts as a high-level policy over indexed events.

Let pteam∈[0,1]p_{\mathrm{team}} \in[0,1] denote the desired probability that the team automaton reaches a state in FF and thereby completes the task successfully. To support such a team-level requirement, we associate each indexed event αu\alpha_u with a timeout t(αu)>0t(\alpha_u) > 0 and a required success probability p(αu)∈[0,1]p(\alpha_u) \in[0,1]. These event-level quantities form the performance requirements that will later be assigned through contracts.

We call any subset X⊆Σ\mathcal{X} \subseteq\Sigma 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

C=(XC,AC,tC,pC,μC),\mathcal{C} = (\mathcal{X}_{\mathcal{C}}, \mathcal{A}_{\mathcal{C}}, t_{\mathcal{C}}, p_{\mathcal{C}}, \mu_{\mathcal{C}}),

where ∅≠XC⊆Σ\varnothing\ne\mathcal{X}_{\mathcal{C}} \subseteq\Sigma is a subtask, AC=∥αu∈XCAαu\mathcal{A}_{\mathcal{C}} = \parallel_{\alpha_u \in\mathcal{X}_{\mathcal{C}}} A_{\alpha_u} is the parallel composition of the CASAs corresponding to its indexed events, tC:XC→R>0t_{\mathcal{C}} : \mathcal{X}_{\mathcal{C}} \to\mathbb{R}_{>0} specifies the timeout for each indexed event, pC:XC→[0,1]p_{\mathcal{C}} : \mathcal{X}_{\mathcal{C}} \to[0,1] specifies its required probability of successful realization, and μC=μ∣XC×Σ\mu_{\mathcal{C}} = \mu|_{\mathcal{X}_{\mathcal{C}} \times\Sigma} 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 Y2Y_2 and B2B_2, since the two plates must be pressed simultaneously to open the gate.

Let D⊆(2I)Σ\mathcal{D} \subseteq(2^I)^\Sigma denote the set of legal assignments of indexed events to subteams. We call D:X→2ID : \mathcal{X} \to2^I a legal sub-assignment if it is the restriction of some d∈Dd \in\mathcal{D}. Let Δ(AD)\Delta(A_D) denote the set of probability distributions over the joint action set ADA_D.

Definition 3.9 (Component). A component is a tuple

M=(XM,DM,ΠM,μM),M = (\mathcal{X}_M, D_M, \Pi_M, \mu_M),

where XM⊆Σ\mathcal{X}_M \subseteq\Sigma is the set of indexed events implemented by the component, DM:XM→2ID_M : \mathcal{X}_M \to2^I is a legal sub-assignment, for each αu∈XM\alpha_u \in\mathcal{X}_M, ΠM(αu):SDM(αu)→Δ(ADM(αu))\Pi_M(\alpha_u) : S_{D_M(\alpha_u)} \to\Delta(A_{D_M(\alpha_u)}) is a policy used by the assigned agents to realize αu\alpha_u, and μM:XM×Σ→[0,1]\mu_M : \mathcal{X}_M \times\Sigma\to[0,1] is the component’s dispatching policy.

When αu\alpha_u is dispatched, the agents in DM(αu)D_M(\alpha_u) execute ΠM(αu)\Pi_M(\alpha_u) 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 D⊆ID \subseteq I, define the local goal set GD(αu)={(sD,se):α∈L(u,(sD,s−D,se)) for all s−D∈S−D}G_D(\alpha_u) = \{(s_D, s_e) : \alpha\in L(u, (s_D, s_{-D}, s_e)) \text{ for all } s_{-D} \in S_{-D}\}, using the state projection notation defined in Subsection 3.1. Thus, reaching GD(αu)G_D(\alpha_u) guarantees that α\alpha is realized independently of the states of agents outside DD.

Likewise, define the local entry set

ID(u)={(sD,se):∃s−D such that (sD,s−D,se)∈I(u)}.I_D(u) = \{(s_D, s_e) : \exists s_{-D} \text{ such that } (s_D, s_{-D}, s_e) \in I(u)\}.

This is the projection of the possible low-level states encountered when the team-task automaton enters uu 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 αu∈XM\alpha_u \in X_M, let π(αu)=(ΠM(αu),πidle−DM(αu))\pi(\alpha_u) = (\Pi_M(\alpha_u), \pi_{\mathrm{idle}}^{-D_M(\alpha_u)}) denote the joint policy under which the assigned subteam executes ΠM(αu)\Pi_M(\alpha_u) and all other agents execute their idle policies. For a set EE, let τE\tau_E denote its first hitting time. The success probability achieved by component MM on αu\alpha_u within time tt is

pM(αu;t)=inf⁡s0∈IDM(αu)(u)Pr⁡π(αu)(τGDM(αu)(αu)≤t∣s0).(1)p_M(\alpha_u;t) = \inf_{s^0 \in I_{D_M(\alpha_u)}(u)} \Pr_{\pi(\alpha_u)}\left(\tau_{G_{D_M(\alpha_u)}(\alpha_u)} \leq t \mid s^0\right). \tag*{(1)}

Definition 3.10 (Contract Satisfaction). Component MM satisfies contract CC, written M⊨CM \models C, if XC⊆XMX_C \subseteq X_M and, for every αu∈XC\alpha_u \in X_C, pM(αu;tC(αu))≥pC(αu)p_M(\alpha_u;t_C(\alpha_u)) \geq p_C(\alpha_u), and μM(β∣αu)=μC(β∣αu)\mu_M(\beta\mid\alpha_u) = \mu_C(\beta\mid\alpha_u) for all β∈Σ\beta\in\Sigma.

Composition. Two contracts C1C_1 and C2C_2 are composable if XC1∩XC2=∅X_{C_1} \cap X_{C_2} = \varnothing. Their composition is

C1⊗C2=(XC1∪XC2,AC1∥AC2,tC1∪tC2,pC1∪pC2,μC1∪μC2).C_1 \otimes C_2 = (X_{C_1} \cup X_{C_2}, A_{C_1} \parallel A_{C_2}, t_{C_1} \cup t_{C_2}, p_{C_1} \cup p_{C_2}, \mu_{C_1} \cup\mu_{C_2}).

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 M1M_1 and M2M_2 are composable if XM1∩XM2=∅X_{M_1} \cap X_{M_2} = \varnothing and DM1∪DM2D_{M_1} \cup D_{M_2} 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 M1⊨C1M_1 \models C_1 and M2⊨C2M_2 \models C_2, and both pairs are composable, then M1⊗M2⊨C1⊗C2M_1 \otimes M_2 \models C_1 \otimes C_2.

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 CC atomic if ∣XC∣=1|X_C| = 1, and likewise call a component MM atomic if ∣XM∣=1|X_M| = 1. Every contract can be expressed as the composition of atomic contracts, and every component as the composition of atomic components.

Closed Contracts. A contract CC is closed if μ(αu∣uI)=0\mu(\alpha_u \mid u_I) = 0 for every αu∉XC\alpha_u \notin X_C and μC(β∣αu)=0\mu_C(\beta\mid\alpha_u) = 0 for every αu∈XC\alpha_u \in X_C and β∅∉XC\beta_\varnothing\notin X_C. 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 pteamp_{\mathrm{team}}, 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 x∈Σx \in\Sigma. A pair (i,x)(i, x) denotes the candidate assignment of agent ii to event xx, for which we maintain a policy trained to realize xx. Let zi,x∈{0,1}z_{i,x} \in\{0,1\} indicate whether this assignment is selected, and let σi,x∈[0,1]\sigma_{i,x} \in[0,1] denote the current estimated success probability of its policy, evaluated according to Equation (1) using the fixed timeout txt_x. In practice, σi,x\sigma_{i,x} is estimated empirically from rollouts initialized from the corresponding entry set and is set to zero if no policy has yet been trained for (i,x)(i,x). 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 x∈Σx \in\Sigma, let px∈[0,1]p_x \in[0,1] denote the required success probability of its atomic contract and let dx≥0d_x \ge0 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 uFu_F and assign reward rx=1r_x = 1 to indexed events whose transitions enter uFu_F through the collapsed accepting states, with rx=0r_x = 0 otherwise. The resulting expected discounted reward therefore represents discounted task-completion probability. We add an artificial terminal self-loop uF→ϵuFu_F \xrightarrow{\epsilon} u_F, with pϵ=1p_\epsilon= 1 and rϵ=0r_\epsilon= 0, for flow bookkeeping. It acts as a flow sink: its occupancy absorbs flow reaching uFu_F without contributing to the incoming-flow sums. The flow constraints below use the state set and transition incidences of this modified automaton. Let R∗R^* denote the maximum discounted completion reward obtainable under the same flow constraints when all event success probabilities are set to one. Thus, R∗R^* 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

Event0.941.311.882.502.75
Upper path (uI→u1→⋯u_I \rightarrow u_1 \rightarrow\cdots)
Y1Y_1♟ 0.01––––
R1R_1♟ 0.98––––
Y3Y_3♟ 1.00––––
B2B_2♞ 0.99––––
T1T_1♟ 0.55––––
Lower path (uI→u6→⋯u_I \rightarrow u_6 \rightarrow\cdots)
B3B_3–♟ 0.00♜ 0.00♞ 0.99♞ 0.99
R2R_2–♟ 0.00♞ 1.00♞ 1.00♞ 1.00
B5B_5–♜ 0.00♜ 0.00–♜ 0.98
Y5Y_5–♟ 0.98♟ 1.00–♟ 1.00
Y4Y_4–––♟ 1.00–
B4B_4–––♜ 0.02–
P1P_1–♞ 1.00♞ 1.00♞ 1.00♜ 1.00
T2T_2–♟ 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

min⁡z,p,d∑x∈Σ(px−∑i∈Iσi,xzi,x)\min_{z,p,d}\quad\sum_{x\in\Sigma}\left(p_x-\sum_{i\in I}\sigma_{i,x}z_{i,x}\right)
s.t.∑i∈Izi,x≤1∀x∈Σ,\text{s.t.}\quad\sum_{i\in I}z_{i,x}\le1 \qquad\forall x\in\Sigma,
σi,xzi,x≤px≤∑i∈Izi,x∀x∈Σ,\sigma_{i,x}z_{i,x}\le p_x\le\sum_{i\in I}z_{i,x}\qquad\forall x\in\Sigma,
∑i∈Izi,x=0⟹dx=0∀x∈Σ,\sum_{i\in I}z_{i,x}=0\Longrightarrow d_x=0\qquad\forall x\in\Sigma,
px≤σi,x+(1−σi,x)(1−zi,x)∀(i,x)∈C,p_x\le\sigma_{i,x}+(1-\sigma_{i,x})(1-z_{i,x})\qquad\forall(i,x)\in C,
Az≤b,zi,x∈{0,1}.Az\le b,\qquad z_{i,x}\in\{0,1\}.
∑x∈out⁡(u)∖{ϵ}rxdxpx≥pteamR∗,\sum_{x\in\operatorname{out}(u)\setminus\{\epsilon\}}r_xd_xp_x\ge p_{\mathrm{team}}R^*,
∑x∈out⁡(u)dx−γ∑x∈in⁡(u)src⁡(x)≠uFdxpx=1{u=uI},∀u∈U,\sum_{x\in\operatorname{out}(u)}d_x-\gamma\sum_{\substack{x\in\operatorname{in}(u)\\ \operatorname{src}(x)\ne u_F}}d_xp_x=\mathbf{1}\{u=u_I\},\qquad\forall u\in U,
pϵ=1,dx≥0,px∈[0,1].p_\epsilon=1,\qquad d_x\ge0,\qquad p_x\in[0,1].

We solve this optimization problem using Gurobi, as in [10]. Here, out⁡(u)\operatorname{out}(u) and in⁡(u)\operatorname{in}(u) denote the indexed events leaving and entering automaton state uu, respectively, uIu_I is the initial state, and γ∈(0,1]\gamma\in(0,1] is the discount factor. The linear constraints Az≤bAz\le b encode the admissible agent assignments, while CC 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 pteamR∗p_{\mathrm{team}}R^*. 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 (i,x)∈C(i,x)\in C, the upper and lower bounds force px=σi,xp_x=\sigma_{i,x}, preventing the optimizer from requesting further improvement from that policy.

After each solve, up to kk non-converged selected pairs (i,x)(i,x) with the largest positive deficits px−σi,xp_x-\sigma_{i,x} are chosen for further training. Each selected policy is initialized if necessary and trained for a batch of up to NtrainingN_{\mathrm{training}} epochs, capped by its remaining per-pair budget of Nmax⁡N_{\max} epochs. The resulting σi,x\sigma_{i,x} values are then updated and the optimization is solved again. Once a policy reaches Nmax⁡N_{\max} training epochs, its pair is added to CC. 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 dxd_x 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 0.94×1060.94 \times10^{6} nominal training steps, the king’s performance on Y1Y_{1} and T1T_{1} 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 T1T_{1}. On the lower path, R2R_{2} and B3B_{3} pass to the knight, the order of the simultaneous presses briefly reverses through Y4Y_{4} and B4B_{4}, and assigning P1P_{1} to the rook permits the knight to perform B5B_{5}. 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

Evaluation performance of IHA-MARL, LOTaD, ATAD, and Monolithic policies on Cooperative Buttons, Four Buttons, and Asymmetric Advantages

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-tt 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

A=(Σ,U,uI,F,→)A = (\Sigma, U, u_I, F, \to)

be a finite deterministic indexed automaton with a unique sink state s∈Fs \in F, such that every state is reachable from uIu_I and has a path to ss. Then there exist ∣Σ∣|\Sigma| automata

Ai=(Σi,Ui,uiI,Fi,→i),A_i = (\Sigma_i, U_i, u_i^I, F_i, \to_i),

with

Ui={armed,active,resolved}and⋃iΣi=Σ,U_i = \{\text{armed},\text{active},\text{resolved}\} \qquad\text{and}\qquad \bigcup_i \Sigma_i = \Sigma,

such that

A≅∥iAi.A \cong\mathbin{\|}_{i} A_i.

Proof. Let

Σ={α1,…,αm},\Sigma= \{\alpha_1,\ldots,\alpha_m\},

where, because AA is indexed, each event αi\alpha_i labels a unique transition

ui→αivi.u_i \xrightarrow{\alpha_i} v_i.

Construction of the local automata. For each indexed event αi\alpha_i, partition UU into

Uarmedi=s(ui),Uactivei={ui},Uresolvedi=U∖(s(ui)∪{ui}),U_{\mathrm{armed}}^i = s(u_i), \qquad U_{\mathrm{active}}^i = \{u_i\}, \qquad U_{\mathrm{resolved}}^i = U \setminus\left(s(u_i) \cup\{u_i\}\right),

where s(ui)s(u_i) denotes the set of states from which uiu_i is reachable, excluding uiu_i itself.

Define

qi:U→Ui={armed,active,resolved}q_i: U \to U_i = \{\text{armed},\text{active},\text{resolved}\}

by

qi(u)={armed,u∈Uarmedi,active,u∈Uactivei,resolved,u∈Uresolvedi.q_i(u) = \begin{cases} \text{armed}, & u \in U_{\mathrm{armed}}^i,\\ \text{active}, & u \in U_{\mathrm{active}}^i,\\ \text{resolved}, & u \in U_{\mathrm{resolved}}^i. \end{cases}

We include in the alphabet of AiA_i every indexed event whose transition changes the iith partition state, together with αi\alpha_i itself:

Σi={αj∈Σ:qi(uj)≠qi(vj)}∪{αi}.\Sigma_i = \{\alpha_j \in\Sigma: q_i(u_j) \ne q_i(v_j)\} \cup\{\alpha_i\}.

In particular, αi∈Σi\alpha_i \in\Sigma_i for every ii, and hence

⋃i=1mΣi=Σ.\bigcup_{i=1}^{m} \Sigma_i = \Sigma.

Now define

Ai=(Σi,Ui,uiI,Fi,→i),A_i = (\Sigma_i,U_i,u_i^I,F_i,\to_i),

where

uiI=qi(uI),Fi={qi(u):u∈F},u_i^I = q_i(u_I), \qquad F_i = \{q_i(u):u\in F\},

and, for every αj∈Σi\alpha_j \in\Sigma_i,

qi(uj)→αjqi(vj).q_i(u_j) \xrightarrow{\alpha_j} q_i(v_j).

Because each indexed event labels a unique transition in AA, each αj∈Σi\alpha_j \in\Sigma_i induces a unique transition in AiA_i. Therefore each AiA_i is deterministic.

Let

M=∥i=1mAiM = \mathbin{\|}_{i=1}^{m} A_i

and define

f:U→U1×⋯×Umf: U \to U_1 \times\cdots\times U_m

by

f(u)=(q1(u),…,qm(u)).f(u) = (q_1(u),\ldots,q_m(u)).

We show that ff defines an isomorphism between AA and the reachable portion of MM. Since uiI=qi(uI)u_i^I = q_i(u_I) for every ii, we have f(uI)=(u1I,…,umI)f(u_I) = (u_1^I,\ldots,u_m^I), the initial state of $M.

Injectivity. Suppose f(x)=f(y)f(x)=f(y). First suppose that xx is not the sink state. Since every state has a path to the sink, xx is the source of some transition

x→αkx′.x \xrightarrow{\alpha_k} x'.

Hence x=ukx=u_k, and therefore

qk(x)=active.q_k(x)=\mathrm{active}.

Since f(x)=f(y)f(x)=f(y), their kkth coordinates agree:

qk(y)=qk(x)=active.q_k(y)=q_k(x)=\mathrm{active}.

But

Uactivek={uk},U^k_{\mathrm{active}}=\{u_k\},

so qk(y)=activeq_k(y)=\mathrm{active} implies

y=uk=x.y=u_k=x.

It remains to consider the case in which xx is the sink. If yy were not the sink, then applying the preceding argument to yy would give some kk such that

qk(y)=active.q_k(y)=\mathrm{active}.

Since the active block of the kkth partition is the singleton {uk}\{u_k\} and the sink is not uku_k, we would have

qk(x)≠active,q_k(x)\ne\mathrm{active},

contradicting f(x)=f(y)f(x)=f(y). Thus y=xy=x, and ff is injective.

Preservation of transitions. We next show that transitions of AA induce transitions of MM. Suppose

x→αjyx \xrightarrow{\alpha_j} y

in AA. For each local automaton AiA_i, there are two cases. If αj∈Σi\alpha_j\in\Sigma_i, then by construction

qi(x)→αjiqi(y).q_i(x) \xrightarrow{\alpha_j}_i q_i(y).

If αj∉Σi\alpha_j\notin\Sigma_i, then by the definition of Σi\Sigma_i,

qi(x)=qi(y).q_i(x)=q_i(y).

Therefore, by the definition of parallel composition,

f(x)→αjf(y)f(x) \xrightarrow{\alpha_j} f(y)

in MM.

No additional reachable transitions. Conversely, suppose

f(x)→αjzf(x) \xrightarrow{\alpha_j} z

in MM. Since αj∈Σj\alpha_j\in\Sigma_j, the jjth component must execute its αj\alpha_j transition. The source of that transition is

qj(uj)=active,q_j(u_j)=\mathrm{active},

so

qj(x)=active.q_j(x)=\mathrm{active}.

Because the active block of the jjth partition is the singleton {uj}\{u_j\}, it follows that

x=uj.x=u_j.

Let vjv_j be the unique state satisfying

uj→αjvju_j \xrightarrow{\alpha_j} v_j

in AA. By the forward direction already established,

f(uj)→αjf(vj)f(u_j) \xrightarrow{\alpha_j} f(v_j)

in MM. Each AiA_i is deterministic, and therefore their parallel composition MM is deterministic: from any product state, each component has at most one successor under a given event, and consequently so does the product. Hence

z=f(vj).z=f(v_j).

Thus every transition of MM originating from a state in the image of ff corresponds uniquely to the transition with the same label in AA.

Reachable states. By definition, automaton isomorphism here requires a bijection between the reachable states of the two automata. Every state of AA is reachable from uIu_I by assumption. Since transitions are preserved in the forward direction, every f(u)f(u) with u∈Uu \in U is reachable from

f(uI)=(uI1,…,uIm)f(u_I) = (u_I^1,\ldots,u_I^m)

in MM.

It remains to show that MM has no other reachable states. We proceed by induction on the length of a path from f(uI)f(u_I). The initial product state f(uI)f(u_I) is clearly in the image of ff. Now suppose that a reachable product state is of the form f(u)f(u) and that

f(u)→αjz.f(u) \xrightarrow{\alpha_j} z.

By the converse transition argument above,

u=ujandz=f(vj).u = u_j \qquad\text{and} \qquad z = f(v_j).

Thus every reachable successor of a state in the image of ff also lies in the image of ff. By induction, every reachable state of MM belongs to f(U)f(U).

Since ff is injective, it follows that

f:U→Reach⁡(M)f : U \to\operatorname{Reach}(M)

is a bijection.

Accepting states. Finally, we show that ff preserves acceptance. If u∈Fu \in F, then by definition of FiF_i,

qi(u)∈Fiq_i(u) \in F_i

for every ii. Therefore

f(u)∈F1×⋯×Fm.f(u) \in F_1 \times\cdots\times F_m.

Conversely, suppose u∉Fu \notin F. Since the unique sink state ss belongs to FF, uu is not the sink. Because uu has a path to the sink, it is therefore the source of some transition

u→αku′.u \xrightarrow{\alpha_k} u'.

Hence

qk(u)=active.q_k(u) = \mathrm{active}.

The corresponding partition block is the singleton

Uactivek={u}.U^k_{\mathrm{active}} = \{u\}.

Since u∉Fu \notin F, no accepting state is mapped to active by qkq_k, and therefore

active∉Fk.\mathrm{active} \notin F_k.

Consequently,

f(u)∉F1×⋯×Fm.f(u) \notin F_1 \times\cdots\times F_m.

Thus ff is a bijection between the states of AA and the reachable states of MM that preserves the initial state, labelled transitions, and accepting states. Hence

A≅∏i=1mAi.A \cong\prod_{i=1}^{m} A_i.

Experimental Details

Environments

Chess-Maze. The 16×2116 \times21 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 10×1010 \times10 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 5×95 \times9 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 QQ-policies sequentially, with learning rate 0.2 and constant ϵ\epsilon-greedy exploration ϵ=0.2\epsilon= 0.2. 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-MazeCBFBAA
IHA-MARL
Target fraction0.950.980.980.95
Q-learning discount0.950.950.950.99
Team-model discount0.990.950.970.99
Local horizon (ticks)50100100200
Episodes per capability batch1,2501,0001,0001,000
Maximum episodes per capability5,00010,00020,00020,000
Capabilities before re-solving10101010
Configured team horizon (ticks)1,000100100200
Plotted comparison budget—2.5×1062.5 \times10^63×1063 \times10^610610^6
PPO baselines
Learning rate—5×10−45 \times10^{-4}5×10−45 \times10^{-4}2.5×10−42.5 \times10^{-4}
Discount—0.950.970.99
Entropy coefficient—0.10.10.01
Target KL—0.050.1None

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-tt 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.

EnvironmentIHA-MARLMonolithicATADLOTaD
Cooperative Buttons1.1010.2910.7710.20
Four Buttons1.8914.0915.7014.72
Asymmetric Advantages132.021,400.381,447.001,368.63

Table 3. Median training-loop time in seconds over three timing-pilot seeds.

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_zfcb3vr7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents