Is Per-Agent Policy Composition Safe? Rethinking Successor-Feature Transfer in Cooperative Multi-Agent Reinforcement Learning

This paper studies transfer learning in cooperative multi-agent reinforcement learning (MARL), addressing the problem of serving objectives that change dynamically after deployment without retraining policies for each new objective. The authors investigate whether the single-agent success of successor features (SF) with generalized policy improvement (GPI) can be safely carried into multi-agent teams.

The paper notes that many reinforcement learning systems must serve objectives that change after deployment, and retraining for each new objective is prohibitively expensive. For single agents, this is well understood: "successor features (SF) and generalized policy improvement (GPI) decouple the dynamics of a policy from the objective it serves, so that a library of policies learned for a few objectives can be recombined by a closed-form rule into a policy for any new objective in the same family, with a guarantee that the recombined policy is never worse than any policy already in the library. However, multi-agent transfer has received far less attention, and the common practice of letting each agent recombine its own library independently inherits the recipe but not the guarantee."

The authors prove that "independent per-agent composition is not safe in general: even in cooperative tasks whose rewards are fully separable, the independently composed policy can be strictly worse than every policy in the library, because each agent's values were learned while its teammates followed their old policies, and recombining the library changes the environment each agent faces. This failure has no counterpart in single-agent problems, where the environment is fixed."

The formal result (Lemma 3) states: "For every number of agents N ≥ 2 there exists a cooperative multi-stage task whose rewards are fully separable (each agent's reward depends only on its own action), such that the alignment condition (Requirement 1) holds at the test objective and every library entry is suboptimal, yet the independently composed policy is strictly worse than every policy in the library, while the centralized joint-GPI rule over the same library attains the joint optimum."

The paper proves (Proposition 1) that synchronized composition is unconditionally safe: Let Π be any library, π sync the synchronized composition, and wtest any deployment objective. For every state s and every library entry k, the synchronized composition's value is at least that of any library entry. The structural reason is that synchronized switching never changes anyone's environment, so every joint successor feature stays valid.

The authors identify two conditions under which independent composition regains its guarantee:

• Requirement 1 (Selection alignment): The joint actions optimal for the test objective are reachable by per-agent greedy choices... the Individual-Global-Max (IGM) condition of value-decomposition theory carried from training time to composition time.

• Requirement 2 (Value validity): The per-agent successor features stored in the library remain the true successor features of the composed joint policy.

Proposition 2 shows that if both requirements hold, independent composition is safe. However, the paper demonstrates that a benign-looking task can break validity even when alignment holds.

The paper provides conditions for when independent composition is safe:

• Supermodularity (Proposition 4): Supermodular values make independent composition no worse than synchronized composition. If the joint GPI value is supermodular on the action lattice, then per-agent greedy choices coincide with joint greedy choices.

• Weight cone (Corollary 5): The supermodularity condition holds if and only if the test weight lies in a specific cone Kφ, checkable from library statistics.

• Factored transitions (Proposition 6): "Suppose the transition kernel factorizes per agent, s′i = fi(si, ai), so that no agent's dynamics depend on teammate actions, and the reward features decompose per agent. Then the per-agent successor feature depends on neither the entry k nor the composition. Requirement 2 therefore holds by construction."

To balance safety and flexibility, the authors propose multi-agent universal successor feature approximators (MA-USFA), a hierarchical method with two layers:

1. Lower layer: A per-agent USFA that predicts each agent's successor features while conditioned on a compact summary of what the teammates are being asked to do, so that no agent's value assumes a fixed set of teammates. The model is ψ̃i(s, ai zi, w−i), where zi is the agent's own policy encoding and w−i collects the teammates' task weights.

2. Upper layer: A small learned composer that reads the joint state and selects each agent's library component, learning exactly the cross-agent correction that a per-agent value cannot represent by itself.

The composer is "initialized at the independent rule and trained with the value layer frozen, moving only in directions that raise team value, on every objective MA-USFA starts from a fixed rule and only improves on it, at least matching it everywhere and exceeding it where the correction has something to add."

Training happens once over the distribution of objectives anticipated before deployment and applied with no per-task adaptation. Deployment is a single forward pass with no gradient updates, run on every objective.

SFWorld is a multi-agent grid world with controllable coupling parameters. The results show:

• In the Boverlap task (where agents contend for shared resources), the synchronized rule stays flat as the coupling climbs (Proposition 1), whereas the independent rule falls monotonically as its collision rate rises (Lemma 3).

• MA-USFA instead tracks the oracle ceiling at every coupling level.

• Averaged over all eight tasks MA-USFA is strongest at 34.70, ahead of retraining (34.46) and far above every fixed rule.

On a Manhattan grid of 28×7 intersections (196 signal agents):

• MA-USFA is best on every metric, and its margins over the two fixed rules are an order of magnitude larger than the gap between those rules.

• On the homogeneous task: the composer reaches return 2165 against 2009 (independent) and 1993 (synchronized), throughput 518 against 368 and 356, and mean waiting 6.60 s against 10.35 and 11.95 s.

• On the heterogeneous task: it reaches return 1650 against 1515 and 1527, throughput 483 against 337 and 352, and waiting 5.48 s against 8.57 and 8.50 s.

The paper concludes: "In this paper, we study transfer learning in cooperative multi-agent reinforcement learning, covering both heterogeneous and homogeneous tasks. We first identify that independent per-agent composition (the approach adopted by most prior work) does not inherit the single-agent safety guarantee. In contrast, the only unconditionally safe fixed rule is synchronized composition, albeit at the cost of coverage. To balance safety and flexibility, we propose MA-USFA, a hierarchical solution that combines a frozen per-agent value layer with a learned cross-agent correction. Trained once over the preference distribution and deployed with zero per-task adaptation, MA-USFA attains both the safety of synchronized composition and the flexibility of independent recombination."

Improvement 1: Safe Multi-Agent Transfer Without Retraining

The improved AI system can serve dynamically changing objectives in cooperative multi-agent settings (e.g., traffic light networks, warehouse robots, power grids) without retraining per new objective. It uses a two-layer architecture: a frozen per-agent value layer (predicting successor features conditioned on teammate task summaries) and a small learned composer that corrects cross-agent interactions. This guarantees that the deployed policy is never worse than any previously learned policy (safety), while still allowing flexible recombination for novel objectives (coverage). The system runs a single forward pass at deployment—no gradient updates—making it suitable for real-time adaptation.

Improvement 2: Detection and Avoidance of Unsafe Independent Composition

The improved AI system can automatically detect when per-agent independent composition would fail (e.g., when agents’ rewards are separable but their dynamics are coupled, or when teammate policy changes alter each agent’s environment). It checks two conditions: (a) selection alignment (whether joint optimal actions are reachable by per-agent greedy choices) and (b) value validity (whether stored per-agent successor features remain accurate under the composed joint policy). If either fails, the system switches to synchronized composition or triggers the learned composer, preventing catastrophic performance drops that standard multi-agent transfer methods suffer from.

Improvement 3: Guaranteed Performance Bounds for Any Library

The improved AI system can provide a formal performance guarantee: for any library of policies and any new objective, the synchronized composition rule yields a value at least as high as every library entry. This is useful for safety-critical applications (e.g., autonomous vehicle coordination, emergency response) where worst-case performance must be bounded. The system can also verify whether independent composition is safe by checking supermodularity of the joint value function or by computing a weight cone from library statistics—if the test weight lies in that cone, independent composition is provably no worse than synchronized composition.

Improvement 4: Scalable Coordination in Large-Scale Systems

The improved AI system can handle hundreds of agents (e.g., 196 traffic signal agents in a city grid) with zero per-task adaptation. It learns a compact summary of teammate task weights, so each agent’s value prediction remains valid even as teammates’ objectives change. The learned composer reads the joint state and selects each agent’s library component, capturing cross-agent corrections that per-agent values cannot represent. This enables the system to outperform both independent and synchronized fixed rules by large margins (e.g., 20% higher return, 40% higher throughput, 35% lower waiting time) in heterogeneous and homogeneous tasks, while maintaining safety guarantees.

Improvement 5: Training-Time Efficiency and Deployment Simplicity

The improved AI system can be trained once over a distribution of anticipated objectives (e.g., varying traffic densities, resource availability) and then deployed on any new objective without further adaptation. This reduces computational cost by orders of magnitude compared to retraining per objective. The training process is stable because the value layer is frozen, and the composer is initialized at the independent rule, so it only learns corrections that strictly improve team value. This makes the system practical for real-world deployment where objectives change frequently and retraining is infeasible.