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

# Is Per-Agent Policy Composition Safe? Rethinking Successor-Feature Transfer in Cooperative Multi-Agent Reinforcement Learning
Source: [https://arxiv.org/html/2608.11658](https://arxiv.org/html/2608.11658)
Sen LiThanks:Corresponding Author: Sen LiAffiliation:The Hong Kong University of Science and TechnologyAffiliation:The Hong Kong University of Science and Technology \(Guangzhou\)

###### Abstract

Many reinforcement learning systems, from fleet management to traffic signal control, must serve an objective that changes dynamically after deployment, and retraining a policy for each new objective is prohibitively expensive\. For a single agent, this problem is well understood: successor features with generalized policy improvement, together with their universal extension, recombine a library of learned policies into a policy for any new objective, with a guarantee that the result is never worse than any policy 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\. We prove that this independent composition can produce joint behavior strictly worse than every policy in the library, because recombining teammates changes the environment each agent faces and invalidates the values it relies on, a failure with no single\-agent counterpart\. We further show that the only unconditionally safe fixed rule is synchronized composition, which moves the whole team to one jointly trained policy but cannot serve objectives that assign different goals to different agents\. To attain safety and flexibility at once, we propose multi\-agent universal successor feature approximators \(MA\-USFA\), a hierarchical method with two layers: a lower layer of universal successor feature approximators that predicts each agent’s successor features while conditioned on its teammates’ objectives, and an upper composer that selects, across agents, which library entry each agent should follow and supplies the cross\-agent correction a per\-agent value cannot represent\. Trained once over the distribution of objectives, it is applied at deployment with no per\-task adaptation\. On a controlled grid world and a real\-world city\-scale traffic signal control problem, MA\-USFA matches or exceeds every fixed composition rule and recovers the performance of policies retrained from scratch\. The code of this paper is provided at[https://github\.com/RS2002/MA\-USFA](https://github.com/RS2002/MA-USFA)\.

## 1Introduction

Reinforcement learning is often deployed in settings where the environment and the available actions stay fixed while the objective changes repeatedly\. For example, a traffic signal controller regulates the same intersections with the same phases every day, yet the goal it should optimize shifts with the hour \(e\.g\. peak hour and off\-peak hour\), and different intersections in the same network may weigh throughput, delay, and queue length differently at the same moment \(e\.g\. main road and branchway\)\. The practical difficulty is that the two conventional responses each pay a price\. One trains a dedicated policy for every objective, as cooperative multi\-agent methods do when they factorize value for a single fixed team reward\([13](https://arxiv.org/html/2608.11658#bib.bib8);[10](https://arxiv.org/html/2608.11658#bib.bib9);[16](https://arxiv.org/html/2608.11658#bib.bib16)\); this is accurate for the objective it targets but must be redone whenever the preference changes, and the cost grows with the number of agents\. The other trains a single policy on one or a few objectives and reuses it on the rest, trading away per\-objective performance for coverage\([5](https://arxiv.org/html/2608.11658#bib.bib15)\)\. The real goal is neither of these but to serve an objective that keeps changing without paying either price\.

For a single agent this problem 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\([2](https://arxiv.org/html/2608.11658#bib.bib1);[3](https://arxiv.org/html/2608.11658#bib.bib4)\), and universal successor feature approximators \(USFA\), which inherit the goal\-conditioned value modeling of universal value function approximators \(UVFA\)\([11](https://arxiv.org/html/2608.11658#bib.bib2)\), extend the same rule from a finite library to a whole distribution of objectives\([4](https://arxiv.org/html/2608.11658#bib.bib3)\)\. Cooperative multi\-agent transfer, where the cost of retraining grows with the number of agents, has received far less attention; the natural way to carry the single\-agent recipe into a team is to let each agent apply the recombination rule to its own library, selecting its own component of the joint action independently\. Several recent works follow exactly this template\([6](https://arxiv.org/html/2608.11658#bib.bib5);[7](https://arxiv.org/html/2608.11658#bib.bib6);[8](https://arxiv.org/html/2608.11658#bib.bib7)\), on the implicit assumption that the single\-agent guarantee carries over to the team; some acknowledge that the multi\-agent improvement guarantee is not established, or allow a few steps of fine\-tuning at deployment, but none characterizes when the assumption holds and when it fails\. \(A detailed discussion of related work is deferred to Appendix[A](https://arxiv.org/html/2608.11658#A1)\.\)

We supply the missing characterization, and it has two sides\. 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 shared 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 rule that does carry a guarantee is synchronized composition, in which the whole team switches together to a single jointly trained policy indexed by one shared choice; we prove that it is unconditionally safe, never worse than any joint policy in the library for any objective, and without any assumptions on the reward or the dynamics\. We further give conditions, checkable from the library alone, under which independent composition regains its guarantee, so the field is left with both a correct safe baseline and a precise test for when the cheaper rule may still be used\.

Synchronized composition, however, guarantees only that the team performs no worse than the library; because it can only reproduce joint policies stored as a whole, it cannot serve objectives that are heterogeneous across the team, assigning different goals to different agents\. We therefore propose multi\-agent universal successor feature approximators \(MA\-USFA\), a hierarchical method with two layers\. The lower layer is 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 upper layer is 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 trained once over the distribution of objectives anticipated before deployment and applied with no per\-task adaptation\. On a controlled grid world and a real\-world city\-scale traffic signal problem with nearly two hundred agents, MA\-USFA improves throughput and delay over both fixed rules and recovers the performance of policies retrained separately for each objective\. Together these results turn independent per\-agent composition, the field’s de facto but unexamined heuristic, into a well\-posed problem: a precise diagnosis of when it fails, a provably safe baseline to fall back on, and a learned method that is safe and flexible at once\.

## 2Preliminaries and Problem Formulation

### 2\.1Single\-agent transfer: successor features, generalized policy improvement, and universal value modeling

Consider a Markov decision process with state spaceSS, action spaceAA, transition kernelPP, discount factorγ\\gamma, and a feature functionϕ:S×A→ℝd\\phi:S\\times A\\to\\mathbb\{R\}^\{d\}\. The reward is linear in the features,rw​\(s,a\)=ϕ​\(s,a\)⊤​wr\_\{w\}\(s,a\)=\\phi\(s,a\)^\{\\top\}w, so different objectives in the same family differ only in the weight vectorww\. The successor features of a policyπ\\piare the expected discounted feature sums

ψπ\(s,a\)=𝔼\[∑t=0∞γtϕ\(st,at\)\|s0=s,a0=a,π\],\\psi^\{\\pi\}\(s,a\)=\\mathbb\{E\}\\Big\[\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}\\phi\(s\_\{t\},a\_\{t\}\)\\,\\Big\|\\,s\_\{0\}=s,\\ a\_\{0\}=a,\\ \\pi\\Big\],\(1\)and the value ofπ\\piunder any objectivewwis the linear functionVwπ​\(s\)=ψπ​\(s,π⁡\(s\)\)⊤​wV\_\{w\}^\{\\pi\}\(s\)=\\psi^\{\\pi\}\(s,\\pi\(s\)\)^\{\\top\}w: a single successor feature model prices a policy under anywwwithout new rollouts\.

GPI turns this pricing rule into a composition rule over a library of policies\{π1,…,πK\}\\\{\\pi^\{1\},\\dots,\\pi^\{K\}\\\}with successor features\{ψ1,…,ψK\}\\\{\\psi^\{1\},\\dots,\\psi^\{K\}\\\}: the composed policy acts greedily with respect to the best library value,

π⁡\(s\)∈arg⁡maxa​maxk​ψk​\(s,a\)⊤​wtest,\\pi\(s\)\\in\\arg\\max\_\{a\}\\max\_\{k\}\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\},\(2\)and satisfiesVwtestπ​\(s\)≥maxk⁡Vwtestπk​\(s\)V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi\}\(s\)\\geq\\max\_\{k\}V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\)for every statess: the composed policy is never worse than any policy in the library\([2](https://arxiv.org/html/2608.11658#bib.bib1);[3](https://arxiv.org/html/2608.11658#bib.bib4)\)\. Two premises make this machinery work: the dynamics are fixed, so the successor features stored in the library remain valid whatever the objective; and there is a single decision maker, so the rule in Eq\. \([2](https://arxiv.org/html/2608.11658#S2.E2)\) is executed on the only action space there is\.

UVFA make the value model a function of the objective itself,V⁡\(s,g\)V\(s,g\), so that one network represents a whole family of value functions and generalizes to unseen objectives by interpolation rather than by retraining a separate value function for each\([11](https://arxiv.org/html/2608.11658#bib.bib2)\)\. USFA combine this idea with successor features in a single modelψ~​\(s,a,z,w\)\\tilde\{\\psi\}\(s,a,z,w\)that carries two axes: a policy axiszzthat indexes which library policy is being evaluated, and a task axiswwthat shapes the behavior during training and prices any objective at test time\. After one training run over a distribution of objectives, composition at test time is therefore a dot product over a candidate set, with no per\-objective adaptation\([4](https://arxiv.org/html/2608.11658#bib.bib3)\)\. With a single goal as the candidate set USFA reduces to UVFA, and with a finite library to SF and GPI\.

Appendix[B](https://arxiv.org/html/2608.11658#A2)recalls the pricing identity and the GPI improvement guarantee, and explains why UVFA and USFA generalize across objectives and what motivates the USFA policy\-task factorization; our multi\-agent analysis builds directly on these single\-agent facts\.

### 2\.2Cooperative multi\-agent setting

We now lift the single\-agent setup of Section[2\.1](https://arxiv.org/html/2608.11658#S2.SS1)to a team, and the notation carries an agent indexiithroughout\. We formalize the team as a multi\-agent Markov decision process: a set ofNNagents shares a state spaceSS, agentiitakes actionaia\_\{i\}, and the joint action isa=\(a1,…,aN\)a=\(a\_\{1\},\\dots,a\_\{N\}\), witha−i=\(aj\)j≠ia\_\{\-i\}=\(a\_\{j\}\)\_\{j\\neq i\}the teammates’ actions\. The transition kernelP⁡\(s′∣s,a\)P\(s^\{\\prime\}\\mid s,a\)and the features depend on the joint action\.

Our scope is cooperative transfer, where each agent carries its own objective but the team shares one criterion\. Agentiihas featuresϕi​\(s,a\)\\phi\_\{i\}\(s,a\)and a task weightwiw\_\{i\}, giving a per\-agent rewardri​\(s,a\)=ϕi​\(s,a\)⊤​wir\_\{i\}\(s,a\)=\\phi\_\{i\}\(s,a\)^\{\\top\}w\_\{i\}and, under a joint policyπ\\pi, a per\-agent reward\-to\-goViπ​\(s\)=ψiπ​\(s,π⁡\(s\)\)⊤​wiV\_\{i\}^\{\\pi\}\(s\)=\\psi\_\{i\}^\{\\pi\}\(s,\\pi\(s\)\)^\{\\top\}w\_\{i\}built from the per\-agent successor featuresψiπ\\psi\_\{i\}^\{\\pi\}of Eq\. \([1](https://arxiv.org/html/2608.11658#S2.E1)\)\. The system objective is the sum of these reward\-to\-go values,

Vπ​\(s\)=∑i=1NViπ​\(s\)=ψπ​\(s,π⁡\(s\)\)⊤​w,ψπ=∑iψiπ,V^\{\\pi\}\(s\)\\ =\\ \\sum\_\{i=1\}^\{N\}V\_\{i\}^\{\\pi\}\(s\)\\ =\\ \\psi^\{\\pi\}\(s,\\pi\(s\)\)^\{\\top\}w,\\qquad\\psi^\{\\pi\}=\\sum\_\{i\}\\psi\_\{i\}^\{\\pi\},\(3\)so the team maximizes total reward\-to\-go, the cooperative criterion\. A homogeneous task assigns all agents one shared weightww; a heterogeneous task a per\-agent vector\(w1,…,wN\)\(w\_\{1\},\\dots,w\_\{N\}\), the case single\-agent transfer has no analogue for\. The objective distribution the team is trained and deployed on spans both types\. This matters for composition: a synchronized joint policy commits the whole team to one shared weight, so it can be trained on and can serve only the homogeneous objectives, whereas the heterogeneous objectives are reachable only by composing per\-agent policies\.

Two differences from the single\-agent case of Section[2\.1](https://arxiv.org/html/2608.11658#S2.SS1)drive everything that follows, and each breaks one of its two premises\. First, execution is decentralized:NNagents each select their ownaia\_\{i\}, so the single decision maker of Eq\. \([2](https://arxiv.org/html/2608.11658#S2.E2)\) is replaced byNNof them acting in parallel\. Second, the teammates are part of each agent’s environment: the marginal transition of agentiiisPi​\(si′∣s,ai,a−i\)P\_\{i\}\(s^\{\\prime\}\_\{i\}\\mid s,a\_\{i\},a\_\{\-i\}\)and its features may beϕi​\(si,ai,a−i\)\\phi\_\{i\}\(s\_\{i\},a\_\{i\},a\_\{\-i\}\), so recomposing the library changesa−ia\_\{\-i\}and hence the very process against which agentii’s successor features were measured\. The fixed\-dynamics premise and the single\-decision\-maker premise therefore both fail, and Section[3](https://arxiv.org/html/2608.11658#S3)traces every safety question back to these two failures\.

### 2\.3Libraries and composition rules

A policy libraryΠ=\{π1,…,πK\}\\Pi=\\\{\\pi^\{1\},\\dots,\\pi^\{K\}\\\}is trained before deployment and contains two kinds of entries: synchronized entries, joint policies trained on homogeneous tasks so the whole team can switch toπk\\pi^\{k\}through a single indexkk, and independent entries, assembled from per\-agent policiesπk=\(z1k,…,zNk\)\\pi^\{k\}=\(z^\{k\}\_\{1\},\\dots,z^\{k\}\_\{N\}\)trained for their own task contexts, which span combinations no synchronized entry can represent\. Each entry carries a joint successor featureψk\\psi^\{k\}, measured directly for synchronized entries and summed from per\-agent features when the features decompose additively\. For each agentiiwe also define the per\-agent successor featureψik​\(s,ai\)\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)of entrykk: the expected discounted features of agentiiwhen it takesaia\_\{i\}while the teammates follow entrykkand everyone continues along entrykkafterwards, a snapshot quantity measured against a specific version of the teammates; Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)will turn precisely this dependence into a problem\. A composition ruleR\\mathrm\{R\}maps the library and a deployment objective to a joint policy, with no gradient updates at deployment time\. This paper studies exactly three, which differ only in how each agent’s library component is selected: two fixed rules, analyzed in Section[3](https://arxiv.org/html/2608.11658#S3), and the learned rule we propose in Section[4](https://arxiv.org/html/2608.11658#S4)\. \( Table[4](https://arxiv.org/html/2608.11658#A4.T4)\(Appendix[E](https://arxiv.org/html/2608.11658#A5)\) summarizes the three rules\.\)

The first fixed rule,*synchronized composition*, selects one library entry per state and replays its joint action,

πsync​\(s\)=πk∗​\(s\),k∗∈arg⁡maxk​ψk​\(s,πk​\(s\)\)⊤​wtest,\\pi^\{\\mathrm\{sync\}\}\(s\)\\ =\\ \\pi^\{k^\{\*\}\}\(s\),\\qquad k^\{\*\}\\in\\arg\\max\_\{k\}\\psi^\{k\}\\\!\\big\(s,\\pi^\{k\}\(s\)\\big\)^\{\\top\}w\_\{\\mathrm\{test\}\},\(4\)the composition rule of Eq\. \([2](https://arxiv.org/html/2608.11658#S2.E2)\) restricted to the joint actions the entries themselves take; under valid values the score in Eq\. \([4](https://arxiv.org/html/2608.11658#S2.E4)\) is the value of the entry itself,ψk​\(s,πk​\(s\)\)⊤​wtest=Vπk​\(s\)\\psi^\{k\}\(s,\\pi^\{k\}\(s\)\)^\{\\top\}w\_\{\\mathrm\{test\}\}=V^\{\\pi^\{k\}\}\(s\), so the synchronized rule always replays the entry that is best at the current state\.

The second fixed rule,*independent composition*, lets each agent apply the single\-agent rule to its own library,

πiind​\(s\)∈arg⁡maxai​maxk​ψik​\(s,ai\)⊤​wi,\\pi^\{\\mathrm\{ind\}\}\_\{i\}\(s\)\\in\\arg\\max\_\{a\_\{i\}\}\\max\_\{k\}\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)^\{\\top\}w\_\{i\},\(5\)which is how the recent multi\-agent transfer literature carries GPI into a team\([6](https://arxiv.org/html/2608.11658#bib.bib5);[7](https://arxiv.org/html/2608.11658#bib.bib6);[8](https://arxiv.org/html/2608.11658#bib.bib7)\)\.

The third learned rule,*MA\-USFA*, is our proposed method: it keeps the decision space of independent composition but replaces the fixed argmax in Eq\. \([5](https://arxiv.org/html/2608.11658#S2.E5)\) with a learned upper\-layer composer over a per\-agent successor\-feature layer \(Section[4](https://arxiv.org/html/2608.11658#S4)\)\. The deployment goal is zero per\-task adaptation, amortized over the preference distribution: all learning happens once, before deployment, and at deployment the rule acts on the frozen library with no adaptation to the particularwtestw\_\{\\mathrm\{test\}\}\.

## 3Fixed Methods: Synchronized and Independent Compositions

### 3\.1Design goals: safety and flexibility beyond the library

To evaluate a composition rule, we consider two criteria, and no fixed rule delivers both\. The first is*safety*: the composed policy should never be worse than the best policy already in the library\.

###### Definition 1\(Safety\)\.

A composition ruleR\\mathrm\{R\}is safe on\(Π,Wtest\)\(\\Pi,W\_\{\\mathrm\{test\}\}\)if the composed policyπR\\pi^\{\\mathrm\{R\}\}satisfies, for everywtest∈Wtestw\_\{\\mathrm\{test\}\}\\in W\_\{\\mathrm\{test\}\}and every statess,

VwtestπR​\(s\)≥maxk⁡Vwtestπk​\(s\),V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{R\}\}\}\(s\)\\geq\\max\_\{k\}V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\),\(6\)where the value is the team objectiveV=∑iViV=\\sum\_\{i\}V\_\{i\}of Eq\. \([3](https://arxiv.org/html/2608.11658#S2.E3)\) and the maximum is over library entries with valid joint successor features\.

The second goal is*flexibility*beyond the library: a heterogeneous objective can ask each agent for something that no single stored joint policy contains, so we want a rule that can serve such objectives and, where the task structure allows, improve on every stored entry rather than merely tie the best one\.

The two goals pull against each other, and the two fixed rules sit at opposite corners: synchronized composition, next, meets the safety goal but forfeits flexibility; independent composition reaches for flexibility but forfeits safety; MA\-USFA \(Section[4](https://arxiv.org/html/2608.11658#S4)\) is built to meet both\.

### 3\.2Synchronized composition is unconditionally safe

###### Proposition 1\(Synchronized composition is unconditionally safe\)\.

LetΠ\\Pibe any library,πsync\\pi^\{\\mathrm\{sync\}\}the synchronized composition of Eq\. \([4](https://arxiv.org/html/2608.11658#S2.E4)\), andwtestw\_\{\\mathrm\{test\}\}any deployment objective\. For every statessand every library entrykk,

Vwtestπsync​\(s\)≥Vwtestπk​\(s\)\.V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)\\ \\geq\\ V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\)\.\(7\)

###### Proof sketch\.

At every state the synchronized rule scores each entry by the value of replaying it,ψk​\(s,πk​\(s\)\)⊤​wtest=Vπk​\(s\)\\psi^\{k\}\(s,\\pi^\{k\}\(s\)\)^\{\\top\}w\_\{\\mathrm\{test\}\}=V^\{\\pi^\{k\}\}\(s\), and plays the action of the highest\-scoring entry; comparing against any entryπk\\pi^\{k\}, its action scores at least as high at every state, so the one\-step advantage telescopes intoVwtestπsync​\(s\)≥Vwtestπk​\(s\)V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)\\geq V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\)\(Appendix[C](https://arxiv.org/html/2608.11658#A3)\)\. ∎

The structural reason is that synchronized switching never changes anyone’s environment, so every joint successor feature stays valid; synchronized composition is therefore the safe floor any claimed improvement must beat\. What it cannot do, taken up in Section[3\.4](https://arxiv.org/html/2608.11658#S3.SS4), is coverage: its composition space is only theKKlibrary entries\.

### 3\.3Independent composition: unsafe in general, safe under two conditions

Independent composition can express the heterogeneous objectives synchronized composition cannot, but its safety is conditional on two requirements, one repairing each of the two single\-agent premises that a team breaks \(Section[2\.2](https://arxiv.org/html/2608.11658#S2.SS2)\)\. Decentralized execution breaks the single\-decision\-maker premise, so the first requirement constrains which joint actions the per\-agent choices select; teammates entering each agent’s environment breaks the fixed\-dynamics premise, so the second requirement asks whether the stored per\-agent values are still correct after recomposition\.

###### Requirement 1\(Selection alignment\)\.

The joint actions optimal for the test objective are reachable by per\-agent greedy choices: withA∗​\(s\)=arg⁡maxa​Vwtest∗​\(s,a\)A^\{\*\}\(s\)=\\arg\\max\_\{a\}V^\{\*\}\_\{w\_\{\\mathrm\{test\}\}\}\(s,a\), alignment requiresA∗​\(s\)=∏iAi∗​\(s\)A^\{\*\}\(s\)=\\prod\_\{i\}A^\{\*\}\_\{i\}\(s\), the Individual\-Global\-Max \(IGM\) condition of value\-decomposition theory\([13](https://arxiv.org/html/2608.11658#bib.bib8);[10](https://arxiv.org/html/2608.11658#bib.bib9);[12](https://arxiv.org/html/2608.11658#bib.bib10)\)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: eachψik\\psi^\{k\}\_\{i\}was measured while the teammates followed entrykk, and once composition changes their behaviorψik\\psi^\{k\}\_\{i\}prices a policy that is no longer being executed\.

###### Proposition 2\(The two requirements suffice\)\.

Fix a library and a test objectivewtestw\_\{\\mathrm\{test\}\}\. If Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1)and Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)both hold, then independent composition is safe:Vwtestπind​\(s\)≥maxk⁡Vwtestπk​\(s\)V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\)\\geq\\max\_\{k\}V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\)for every statess\.

The argument is direct: validity makes each per\-agent scoreψik​\(s,ai\)⊤​wi\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)^\{\\top\}w\_\{i\}the true value of the composed policy, and alignment makes the per\-agent greedy choice coincide with the joint\-GPI action, so independent composition executes the joint\-GPI rule with correct values and inherits its single\-agent guarantee \(Appendix[C](https://arxiv.org/html/2608.11658#A3)\)\. The two requirements are thus the whole story, and what remains is to ask when each holds\. They are fed by two independent channels of coupling: the reward channel \(cross\-features inϕ\\phi\) governs Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1), and the transition channel \(teammate actions in the dynamics\) governs Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)\. We show first that a benign\-looking task can break validity even when alignment holds, then give the exact condition on each channel under which the independent rule is not merely safe but no worse than synchronized composition\.

#### It can fail even when rewards are fully separable\.

###### Lemma 3\(Independent composition is not always safe\)\.

For every number of agentsN≥2N\\geq 2there 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](https://arxiv.org/html/2608.11658#Thmrequirement1)\) holds at the test objective and every library entry is suboptimal, yet

Vwtestπind​\(s0\)<maxk⁡Vwtestπk​\(s0\),V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\_\{0\}\)\\ <\\ \\max\_\{k\}V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\_\{0\}\),\(8\)so 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 optimumVwtest∗​\(s0\)V^\{\*\}\_\{w\_\{\\mathrm\{test\}\}\}\(s\_\{0\}\)\. The failure is therefore specific to decentralization\.

The construction is a multi\-stage task with per\-agent feature tables \(Appendix[C](https://arxiv.org/html/2608.11658#A3)\)\. The failure is not misalignment \(Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1)holds\) but validity \(Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)fails\)\. Each agent acts exactly as its library values tell it to, but the values are stale: agentiiscores its choice against the features it would accrue if the teammates kept the library’s actions, while their independent choices send the team down a different branch and the accrued features fall short\. A single stale rating pushes the team below its own best library entry, the precise sense in which teammates constitute the environment\. Whether the failure is statistically visible depends on how the library was built, so safety must be characterized structurally rather than by example\.

#### The reward channel: supermodularity and the weight cone\.

###### Proposition 4\(Supermodular values make independent composition no worse than synchronized composition\)\.

Letgs​\(a\)=maxk⁡ψk​\(s,a\)⊤​wtestg\_\{s\}\(a\)=\\max\_\{k\}\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}be the joint GPI value of the library\. Suppose that for every statess,gsg\_\{s\}is supermodular on the lattice\{0,1\}N\\\{0,1\\\}^\{N\}, and ties are broken consistently across agents\. Then the independent composition \([5](https://arxiv.org/html/2608.11658#S2.E5)\) satisfies, for every statess,

Vwtestπind​\(s\)≥Vwtestπsync​\(s\)\.V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\)\\ \\geq\\ V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)\.\(9\)

#### Mechanism\.

Supermodularity ofgsg\_\{s\}says that the marginal gain of one agent improving its action increases in the actions of the other agents; by Topkis’s monotone comparative statics\([14](https://arxiv.org/html/2608.11658#bib.bib11)\)the argmax set is then a sublattice of the action lattice, and with a consistent tie\-break the per\-agent greedy choices coincide with the joint greedy choice\. Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1)therefore holds as a condition on the value structure rather than on an assumed decomposition, the structural generalization of value decomposition, which guarantees alignment by construction during training\([13](https://arxiv.org/html/2608.11658#bib.bib8);[10](https://arxiv.org/html/2608.11658#bib.bib9);[12](https://arxiv.org/html/2608.11658#bib.bib10)\)whereas supermodularity grants it at composition time\.

###### Corollary 5\(The weight cone\)\.

Assume the per\-pair value differences of the library policies are linear in the features\. Then the per\-state supermodularity condition of Proposition[4](https://arxiv.org/html/2608.11658#Thmproposition4)holds if and only if the test weight lies in the cone

Kϕ=\{w:∑dwdΔϕd\(a,b\)≥0for every pair of joint actionsa,b\},K\_\{\\phi\}\\ =\\ \\big\\\{w:\\ \\textstyle\\sum\_\{d\}w\_\{d\}\\,\\Delta\\phi\_\{d\}\(a,b\)\\geq 0\\ \\text\{ for every pair of joint actions \}a,b\\big\\\},\(10\)whereΔ​ϕd​\(a,b\)=ϕd​\(a∨b\)\+ϕd​\(a∧b\)−ϕd​\(a\)−ϕd​\(b\)\\Delta\\phi\_\{d\}\(a,b\)=\\phi\_\{d\}\(a\\vee b\)\+\\phi\_\{d\}\(a\\wedge b\)\-\\phi\_\{d\}\(a\)\-\\phi\_\{d\}\(b\)is the supermodularity gap of featureddon the pair\. A sufficient and easy\-to\-use condition: every feature supermodular andw≥0w\\geq 0\.

The cone is checkable from library statistics: membership ofwtestw\_\{\\mathrm\{test\}\}is a dot product, so whether the free region applies to a given task can be read off the library and the test weight without running the policy\.

#### The transition channel: factorization is necessary, not sufficient\.

###### Proposition 6\(Factored transitions with per\-agent rewards\)\.

Suppose the transition kernel factorizes per agent,si′=fi​\(si,ai\)s^\{\\prime\}\_\{i\}=f\_\{i\}\(s\_\{i\},a\_\{i\}\), so that no agent’s dynamics depend on teammate actions, and the reward features decompose per agent,ϕ⁡\(s,a\)=∑iϕi​\(si,ai\)\\phi\(s,a\)=\\sum\_\{i\}\\phi\_\{i\}\(s\_\{i\},a\_\{i\}\)\. Then the per\-agent successor featureψik​\(s,ai\)\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)is the discounted feature stream of agentii’s own dynamics, and it depends on neither the entrykknor the composition\. Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)therefore holds by construction, for every library and every recomposition\. Under the supermodularity and tie\-breaking conditions of Proposition[4](https://arxiv.org/html/2608.11658#Thmproposition4), the independent composition then satisfiesVwtestπind​\(s\)≥Vwtestπsync​\(s\)V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\)\\geq V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)for every statess\.

Factorization neutralizes the transition channel only in the decomposed\-reward case, where the per\-agent values are exact marginal processes of the agent’s own dynamics\. When the reward features couple the agents, the cross\-feature components are measured against the library’s teammate behavior and recomposition invalidates them: even with factored transitions and per\-state supermodularity, the independent rule can violate the safety bound under the exact semantics of Eq\. \([5](https://arxiv.org/html/2608.11658#S2.E5)\)\.

### 3\.4Beyond the free region: when no fixed rule suffices

The two fixed rules cover complementary but incomplete parts of the problem, and a large class of tasks falls outside both\. Synchronized composition is always safe but cannot serve heterogeneous objectives: it replays one library entry as a joint action, so its reachable behavior is exactly theKKentries, and a test objective that asks different agents to pursue different components of the library has no synchronized representative\. Independent composition can express those heterogeneous choices, but only inside the free region of Propositions[4](https://arxiv.org/html/2608.11658#Thmproposition4)and[6](https://arxiv.org/html/2608.11658#Thmproposition6), and both free conditions can fail\. Transition coupling breaks Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)outright: the counterexample of Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3)is an exact failure in which the independent rule falls below the best library entry and below joint\-GPI\. Cross\-feature rewards break Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1), so even factored transitions do not by themselves restore safety\.

The two conditions are structural properties of the task, not tunable knobs\. For example, a traffic network couples each intersection to its upstream neighbors, so factorization fails by construction and real coupled problems live in the failure region, where synchronized composition is too rigid to serve heterogeneous demand and independent composition is no longer safe\. This is the region a learned composition rule must cover, and it is the design target of MA\-USFA \(Section[4](https://arxiv.org/html/2608.11658#S4)\), which is applied to every objective and is built to be at least as good as either fixed rule everywhere, so its use never depends on a safety test\. The theory of this section instead governs the fixed\-rule\-only regime: when a learned composer is unavailable, synchronized composition is the unconditionally safe default, and the independent rule may replace it precisely where its two requirements hold\.

## 4Learnable Method: MA\-USFA

### 4\.1Overview

Section[3](https://arxiv.org/html/2608.11658#S3)shows that each fixed rule is safe only on part of the objective space, so a single rule that is safe and flexible on every objective must learn the composition\. MA\-USFA is a hierarchy of two decision layers over the cooperative multi\-agent MDP of Section[2\.2](https://arxiv.org/html/2608.11658#S2.SS2)\(Fig\.[1](https://arxiv.org/html/2608.11658#S4.F1)\)\. The lower layer acts in that MDP with the primitive per\-agent actionsaia\_\{i\}: a per\-agent context\-conditioned USFA predicts each agent’s successor features, conditioned on a compact summary of the teammates’ task context, so that no agent’s value assumes a fixed set of teammates\. The upper layer is a selection layer stacked on top, and it is where composition happens\. At each state its observation is the joint statess, the task vectorww, and the lower layer’s candidate valuations\{ψ~i​\(s,⋅,zi\)⊤​wi:zi∈Ci\}\\\{\\tilde\{\\psi\}\_\{i\}\(s,\\cdot,z\_\{i\}\)^\{\\top\}w\_\{i\}:z\_\{i\}\\in C\_\{i\}\\\}; its action is a per\-agent choice of library entrygi∈Cig\_\{i\}\\in C\_\{i\}, whose primitive action the team then executes\. The upper layer thus decides which library policy each agent follows, the cross\-agent correction a per\-agent value cannot express, while the lower layer supplies the values it chooses among\. Because 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\.

### 4\.2The two layers

#### Lower layer: per\-agent context\-conditioned successor features\.

Each agentiilearns a value model

ψ~i\(s,ai∣zi,w−i\),\\tilde\{\\psi\}\_\{i\}\(s,a\_\{i\}\\mid z\_\{i\},w\_\{\-i\}\),\(11\)whereziz\_\{i\}is the agent’s own policy encoding andw−i=\(wj\)j≠iw\_\{\-i\}=\(w\_\{j\}\)\_\{j\\neq i\}collects the teammates’ task weights\. The two arguments play the two roles of USFA\([4](https://arxiv.org/html/2608.11658#bib.bib3)\):ziz\_\{i\}is the policy axis, a learned index over the agent’s library entries, and the weights carry the task axis, linear in the value and applied only at test time\. The conditioning onw−iw\_\{\-i\}is the new ingredient, the architectural answer to Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2): each teammate’s weight indexes a cluster of teammate policies, so agentiilearns expected successor features over the teammate behavior distribution rather than a snapshot against one fixed teammate version; without it the value is stale the moment the library holds more than one teammate policy, the failure Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3)exposes\. For large teams the context is summarized \(mean or learned embedding ofw−iw\_\{\-i\}\) so the model does not scale withNN\.

Training follows the USFA protocol: the TD target ofψ~i\\tilde\{\\psi\}\_\{i\}is the feature vectorϕ\\phi, so the update does not depend onww, which plays the standard roles of behavior anchor, library anchor \(z∼Dz\(⋅∣w\)z\\sim D\_\{z\}\(\\cdot\\mid w\)\), and test\-time pricing\. With per\-agent additive features the joint successor feature of a synchronized entry decomposes asψjoint,k=∑iψik\\psi^\{\\mathrm\{joint\},k\}=\\sum\_\{i\}\\psi^\{k\}\_\{i\}, so one network serves both the synchronized anchor and the per\-agent library \(Appendix[G](https://arxiv.org/html/2608.11658#A7)\)\.

#### Upper layer: the learned composer\.

The composer is a collection of per\-agent selectorsΥθ=\(Υ1θ,…,ΥNθ\)\\Upsilon^\{\\theta\}=\(\\Upsilon^\{\\theta\}\_\{1\},\\dots,\\Upsilon^\{\\theta\}\_\{N\}\)\. Its input is the joint state, the task vector, and the candidate valuations\{ψ~i​\(s,⋅,zi\)⊤​wi:zi∈Ci\}\\\{\\tilde\{\\psi\}\_\{i\}\(s,\\cdot,z\_\{i\}\)^\{\\top\}w\_\{i\}:z\_\{i\}\\in C\_\{i\}\\\}from the lower layer; its output is a selectiongi∈Cig\_\{i\}\\in C\_\{i\}per agent:

gi=Υiθ\(s,w\|\{ψ~j\(s,⋅,zj\)⊤wj\}j,zj∈Cj\)∈Ci,g\_\{i\}\\;=\\;\\Upsilon^\{\\theta\}\_\{i\}\\\!\\left\(s,\\,w\\;\\middle\|\\;\\big\\\{\\,\\tilde\{\\psi\}\_\{j\}\(s,\\cdot,z\_\{j\}\)^\{\\top\}w\_\{j\}\\,\\big\\\}\_\{j,\\,z\_\{j\}\\in C\_\{j\}\}\\right\)\\ \\in\\ C\_\{i\},\(12\)It learns the cross\-agent value correction: the lower layer absorbs the expected part of the teammate dependence, predictable from the public task context, and the composer adds the residual that depends on the joint combination of candidate policies, which no per\-agent value can price\. It does not relearn single\-agent decision making, only corrects values across agents, which is why it is small and trainable on a fraction of the library’s budget\. Similar to the lower layer, for large teams the contexts \(wwand\{ψ~j​\(s,⋅,zj\)⊤​wj\}j,zj∈Cj\\big\\\{\\,\\tilde\{\\psi\}\_\{j\}\(s,\\cdot,z\_\{j\}\)^\{\\top\}w\_\{j\}\\,\\big\\\}\_\{j,\\,z\_\{j\}\\in C\_\{j\}\}\) are summarized \(e\.g\. via attention or communication mechanisms\) to ensure scalability\.

![Refer to caption](https://arxiv.org/html/2608.11658v1/main.png)Figure 1:MA\-USFA shown for a single agent\.

### 4\.3Training and deployment

Training has two phases, one per layer \(Table[3](https://arxiv.org/html/2608.11658#A4.T3), Appendix[D](https://arxiv.org/html/2608.11658#A4); full pseudocode in Appendix[D\.2](https://arxiv.org/html/2608.11658#A4.SS2)\)\. Phase 1 trains the lower per\-agent value layer, sampling tasks at random from the homogeneous and heterogeneous scenarios with thew−iw\_\{\-i\}conditioning, and then freezes it; this layer produces the candidates the composer selects among\. Phase 2 trains the upper composer, initialized at the independent transfer policy with the value layer frozen; wherever that policy is already optimal the value\-increasing gradient vanishes and no parameters move, so the budget concentrates on the objectives whose coupling actually calls for a cross\-agent correction, namely coupled dynamics and cross\-feature rewards\. This is what keeps the composer small, the difference between MA\-USFA and an end\-to\-end composer\.

Deployment is a single forward pass with no gradient updates, run on every objective: the lower layer prices the candidates by dot product and the composer selects, so anywtestw\_\{\\mathrm\{test\}\}is served with no per\-task adaptation\. This is the entire method at test time\. The composer is always the deciding rule, and the fixed rules of Section[3](https://arxiv.org/html/2608.11658#S3)take no part in it\. The cost of learning to compose is paid once before deployment over the distribution of anticipated objectives, after which every objective needs only forward passes, the precise sense in which the method needs zero per\-task adaptation\.

## 5Experiments

### 5\.1Experiment Setup

In this section, we aim to answer three questions: \(i\) Does independent composition fail exactly where the theory says it must, while synchronized composition holds its floor \(Proposition[1](https://arxiv.org/html/2608.11658#Thmproposition1), Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3)\)? \(ii\) Does the learned composer recover per\-objective retraining where the fixed rules break? \(iii\) And do both survive at large scale scenario, where coupling is endogenous rather than dialed in? The controlled domain below answers the first two\. The third is answered by a traffic signal control task on a Manhattan grid of28×728\\times 7intersections \(196196signal agents\), run on a homogeneous task \(one shared weight\) and a heterogeneous task \(each intersection with its own weight\)\. Overall, the results show MA\-USFA dominates both fixed rules on every metric, with the largest margins on the heterogeneous task, and we leave it to Appendix[F](https://arxiv.org/html/2608.11658#A6)due to page limitation\.

#### Methods and baselines\.

We compare five methods on every objective\. The three composition rules of Section[2](https://arxiv.org/html/2608.11658#S2)are the objects of study: synchronized composition, independent composition, and MA\-USFA\. Two methods bracket them: joint\-GPI, centralized generalized policy improvement over the joint action space \(the prior\-work baseline, feasible only for small teams\), and per\-task retraining, trained from scratch on the deployment reward including the out\-of\-basis collision penalty \(the oracle ceiling MA\-USFA aims to match\)\.

### 5\.2Controlled domain: SFWorld

SFWorld is a multi\-agent grid world that exposes the two coupling channels of Section[3](https://arxiv.org/html/2608.11658#S3)as controllable parameters\.NNagents move on a5×55\\times 5grid with five actions over4040steps \(γ=0\.95\\gamma=0\.95\); featuresϕi​\(s′\)\\phi\_\{i\}\(s^\{\\prime\}\)are smooth bumps overKKresource cells, and the rewardri=ϕi​\(s′\)⊤​wi−2\.0⋅blockedir\_\{i\}=\\phi\_\{i\}\(s^\{\\prime\}\)^\{\\top\}w\_\{i\}\-2\.0\\cdot\\mathrm\{blocked\}\_\{i\}adds a collision penalty outside the feature basis that any closed\-form pricingψ⋅w\\psi\\cdot wis structurally blind to\. The coupling parameterκ\\kappais the probability that two agents targeting the same cell collide: atκ=0\\kappa=0the dynamics factorize \(Proposition[6](https://arxiv.org/html/2608.11658#Thmproposition6)\); asκ\\kappagrows, each agent’s kernel depends on the teammates’ actions\. InAdistinctA\_\{\\mathrm\{distinct\}\}the optimal regions are disjoint so coupling never binds; inBoverlapB\_\{\\mathrm\{overlap\}\}the agents contend for a shared region so collisions arise whenever the joint policy hybridizes\. More details are provided at Appendix[E](https://arxiv.org/html/2608.11658#A5)\.

Table 1:Controlled domain,N=2N=2, four\-entry corner library\. Team return over4040steps, mean±\\pmstandard deviation over three evaluation seeds;collind\\mathrm\{coll\_\{ind\}\}is the collision rate of the independent rule\. Per row,bestis bold andsecond bestunderlined \(used throughout the paper\)\.Table[1](https://arxiv.org/html/2608.11658#S5.T1)carries the whole controlled\-domain story: itsBoverlapB\_\{\\mathrm\{overlap\}\}block exhibits the four claims of the theory at once, andAdistinctA\_\{\\mathrm\{distinct\}\}isolates coverage from coupling\. DownBoverlapB\_\{\\mathrm\{overlap\}\}the synchronized rule stays flat as the coupling climbs \(Proposition[1](https://arxiv.org/html/2608.11658#Thmproposition1)\), since synchronized switching never changes anyone’s environment, whereas the independent rule falls monotonically as its collision rate rises \(Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3)\), pairing per\-agent choices into hybrid joint policies whose collisions the harvest\-only values cannot price\. The two orderings cross: the independent rule wins in the free region but the order flips once coupling binds\. MA\-USFA instead tracks the oracle ceiling at every coupling level; joint\-GPI degrades only mildly but never reaches retraining and is unavailable beyond small teams\. InAdistinctA\_\{\\mathrm\{distinct\}\}, where collisions never occur, independent composition is free as Proposition[6](https://arxiv.org/html/2608.11658#Thmproposition6)predicts\. Averaged over all eight tasks MA\-USFA is strongest at34\.7034\.70, ahead of retraining \(34\.4634\.46\) and far above every fixed rule, with team\-size and library\-coverage sweeps in Appendix[E](https://arxiv.org/html/2608.11658#A5)confirming the pattern\.

## 6Conclusion

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\. Evaluated on a controlled grid\-world scenario and a real\-world large\-scale traffic signal control task, MA\-USFA matches or exceeds every fixed composition rule and recovers the performance of per\-task retraining\.

## Ethics Statement

This work adheres to the principles outlined in the ICLR Code of Ethics\.

## References

- Alegreet al\.\(2022\)L\. N\. Alegre, A\. Bazzan, and B\. C\. Da SilvaOptimistic linear support and successor features as a basis for optimal policy transfer\.InInternational conference on machine learning,pp\. 394–413\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px1.p1.1)\.
- Barretoet al\.\(2017\)A\. Barreto, W\. Dabney, R\. Munos, J\. J\. Hunt, T\. Schaul, H\. Van Hasselt, and D\. SilverSuccessor features for transfer in reinforcement learning\.Advances in neural information processing systems30\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px1.p1.1),[Appendix B](https://arxiv.org/html/2608.11658#A2.SS0.SSS0.Px1.p1.2),[§1](https://arxiv.org/html/2608.11658#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11658#S2.SS1.p2.2),[Proposition 7](https://arxiv.org/html/2608.11658#Thmproposition7)\.
- Barretoet al\.\(2020\)A\. Barreto, S\. Hou, D\. Borsa, D\. Silver, and D\. PrecupFast reinforcement learning with generalized policy updates\.Proceedings of the National Academy of Sciences117\(48\),pp\. 30079–30087\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11658#S2.SS1.p2.2),[Proposition 7](https://arxiv.org/html/2608.11658#Thmproposition7)\.
- Borsaet al\.\(2018\)D\. Borsa, A\. Barreto, J\. Quan, D\. Mankowitz, R\. Munos, H\. Van Hasselt, D\. Silver, and T\. SchaulUniversal successor features approximators\.arXiv preprint arXiv:1812\.07626\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px1.p1.1),[Appendix B](https://arxiv.org/html/2608.11658#A2.SS0.SSS0.Px3.p1.1),[Appendix G](https://arxiv.org/html/2608.11658#A7.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11658#S2.SS1.p3.1),[§4\.2](https://arxiv.org/html/2608.11658#S4.SS2.SSS0.Px1.p1.2)\.
- Da Silva and Costa \(2019\)F\. L\. Da Silva and A\. H\. R\. CostaA survey on transfer learning for multiagent reinforcement learning systems\.Journal of Artificial Intelligence Research64,pp\. 645–703\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p1.1)\.
- de Almeidaet al\.\(2024\)V\. A\. de Almeida, L\. N\. Alegre, and A\. L\. C\. BazzanKnowledge transfer in multi\-objective multi\-agent reinforcement learning via generalized policy improvement\.Computer Science and Information Systems\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p2.1),[§2\.3](https://arxiv.org/html/2608.11658#S2.SS3.p3.2)\.
- Liuet al\.\(2022\)W\. Liu, L\. Dong, D\. Niu, and C\. SunEfficient exploration for multi\-agent reinforcement learning via transferable successor features\.IEEE/CAA Journal of Automatica Sinica9\(9\),pp\. 1673–1686\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p2.1),[§2\.3](https://arxiv.org/html/2608.11658#S2.SS3.p3.2)\.
- Nigamet al\.\(2025\)R\. Nigam, N\. Parikh, H\. Osooli, M\. Yuasa, J\. Heglund, and H\. T\. TranZero\-shot coordination in ad hoc teams with generalized policy improvement and difference rewards\.arXiv preprint arXiv:2510\.16187\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p2.1),[§2\.3](https://arxiv.org/html/2608.11658#S2.SS3.p3.2)\.
- Rashidet al\.\(2020a\)T\. Rashid, G\. Farquhar, B\. Peng, and S\. WhitesonWeighted qmix: expanding monotonic value function factorisation for deep multi\-agent reinforcement learning\.Advances in neural information processing systems33,pp\. 10199–10210\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px3.p1.1)\.
- Rashidet al\.\(2020b\)T\. Rashid, M\. Samvelyan, C\. S\. De Witt, G\. Farquhar, J\. Foerster, and S\. WhitesonMonotonic value function factorisation for deep multi\-agent reinforcement learning\.Journal of Machine Learning Research21\(178\),pp\. 1–51\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p1.1),[§3\.3](https://arxiv.org/html/2608.11658#S3.SS3.SSS0.Px3.p1.1),[Requirement 1](https://arxiv.org/html/2608.11658#Thmrequirement1.p1.1.1)\.
- Schaulet al\.\(2015\)T\. Schaul, D\. Horgan, K\. Gregor, and D\. SilverUniversal value function approximators\.InInternational conference on machine learning,pp\. 1312–1320\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px1.p1.1),[Appendix B](https://arxiv.org/html/2608.11658#A2.SS0.SSS0.Px3.p1.1),[Appendix G](https://arxiv.org/html/2608.11658#A7.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11658#S2.SS1.p3.1)\.
- Sonet al\.\(2019\)K\. Son, D\. Kim, W\. J\. Kang, D\. E\. Hostallero, and Y\. YiQtran: learning to factorize with transformation for cooperative multi\-agent reinforcement learning\.InInternational conference on machine learning,pp\. 5887–5896\.Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px3.p1.1),[§3\.3](https://arxiv.org/html/2608.11658#S3.SS3.SSS0.Px3.p1.1),[Requirement 1](https://arxiv.org/html/2608.11658#Thmrequirement1.p1.1.1)\.
- Sunehaget al\.\(2018\)P\. Sunehag, G\. Lever, A\. Gruslys, W\. M\. Czarnecki, V\. Zambaldi, M\. Jaderberg, M\. Lanctot, N\. Sonnerat, J\. Z\. Leibo, K\. Tuyls, and T\. GraepelValue\-decomposition networks for cooperative multi\-agent learning based on team reward\.InInternational Conference on Autonomous Agents and Multiagent Systems \(AAMAS\),Cited by:[Appendix A](https://arxiv.org/html/2608.11658#A1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p1.1),[§3\.3](https://arxiv.org/html/2608.11658#S3.SS3.SSS0.Px3.p1.1),[Requirement 1](https://arxiv.org/html/2608.11658#Thmrequirement1.p1.1.1)\.
- Topkis \(1998\)D\. M\. TopkisSupermodularity and complementarity\.Princeton university press\.Cited by:[§C\.4](https://arxiv.org/html/2608.11658#A3.SS4.SSS0.Px1.p1.1),[§3\.3](https://arxiv.org/html/2608.11658#S3.SS3.SSS0.Px3.p1.1)\.
- Veličkovićet al\.\(2018\)P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Lio, and Y\. BengioGraph attention networks\.InInternational Conference on Learning Representations,Cited by:[§D\.2](https://arxiv.org/html/2608.11658#A4.SS2.SSS0.Px1.p1.1)\.
- Weiet al\.\(2019\)H\. Wei, N\. Xu, H\. Zhang, G\. Zheng, X\. Zang, C\. Chen, W\. Zhang, Y\. Zhu, K\. Xu, and Z\. LiColight: learning network\-level cooperation for traffic signal control\.InProceedings of the 28th ACM international conference on information and knowledge management,pp\. 1913–1922\.Cited by:[§F\.1](https://arxiv.org/html/2608.11658#A6.SS1.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2608.11658#S1.p1.1)\.

## Appendix Contents

## Appendix ARelated Works

#### Single\-agent transfer\.

Successor features decouple the dynamics of a policy from the objective it serves: a single successor feature model prices any policy under any objective in a linear family by a dot product\([2](https://arxiv.org/html/2608.11658#bib.bib1)\)\. Generalized policy improvement turns this pricing rule into a composition rule with a guarantee: the greedy recombination of a library of policies is never worse than any policy in the library\([3](https://arxiv.org/html/2608.11658#bib.bib4)\)\. Universal value function approximators condition the value model on the goal directly and interpolate across goals\([11](https://arxiv.org/html/2608.11658#bib.bib2)\)\. Universal successor feature approximators merge the two: a model conditioned on a policy encoding and a task weight, trained once over a distribution of objectives, so that composition at test time is a closed\-form dot product over a candidate set\([4](https://arxiv.org/html/2608.11658#bib.bib3)\)\. Optimistic linear support and successor features extend the same machinery to sequential policy transfer across a set of objectives\([1](https://arxiv.org/html/2608.11658#bib.bib12)\)\. The present paper takes the operating mode of this lineage, train once and compose with no per\-task adaptation, and asks what survives in a team; the answer is that the guarantee does not survive independent per\-agent execution\.

#### Multi\-agent transfer\.

The survey of da Silva and Costa\([5](https://arxiv.org/html/2608.11658#bib.bib15)\)organizes multi\-agent transfer along what is transferred, to whom, and with what mechanism, and documents that most proposals carry single\-agent recipes into teams without re\-examining their premises\. The works closest to ours follow exactly the template we analyze:[6](https://arxiv.org/html/2608.11658#bib.bib5)transfer knowledge across multi\-objective multi\-agent tasks by letting each agent keep its own library and apply generalized policy improvement independently, and do not establish a multi\-agent improvement guarantee;[7](https://arxiv.org/html/2608.11658#bib.bib6)transfer successor features per agent to accelerate exploration, again per\-agent;[8](https://arxiv.org/html/2608.11658#bib.bib7)study zero\-shot coordination in ad hoc teams with generalized policy improvement and difference rewards, and explicitly note that the single\-agent improvement guarantee is not established for teams, the gap this paper fills with a precise negative result and a positive one\. None of these works characterizes when the per\-agent recipe is safe and when it fails; our Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3)and Propositions[4](https://arxiv.org/html/2608.11658#Thmproposition4)and[6](https://arxiv.org/html/2608.11658#Thmproposition6)draw that boundary\.

#### Value decomposition\.

The cooperative deep multi\-agent literature aligns per\-agent and joint value models at training time\. VDN sums the per\-agent values\([13](https://arxiv.org/html/2608.11658#bib.bib8)\); QMIX and Weighted QMIX mix them through monotone networks and characterize the family of joint value functions representable under monotonicity\([10](https://arxiv.org/html/2608.11658#bib.bib9);[9](https://arxiv.org/html/2608.11658#bib.bib13)\); QTRAN formalizes the individual\-global\-max \(IGM\) condition under which per\-agent greedy execution equals joint greedy execution\([12](https://arxiv.org/html/2608.11658#bib.bib10)\)\. These works guarantee alignment by construction during training, at the price of a fixed task\. Our Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1)imports the IGM condition to composition time, where the values are no longer trained together, and our Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3)shows that even when the condition holds, composition can still be unsafe because the per\-agent values are stale, the failure that Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)names and that no training\-time credit assignment mechanism addresses\.

## Appendix BSingle\-Agent Foundations

This appendix recalls the single\-agent facts that Section[2\.1](https://arxiv.org/html/2608.11658#S2.SS1)uses and that the multi\-agent proofs of Appendix[C](https://arxiv.org/html/2608.11658#A3)reduce to\. Throughout, features areϕ⁡\(s,a\)∈ℝd\\phi\(s,a\)\\in\\mathbb\{R\}^\{d\}, a reward is a linear readoutrw​\(s,a\)=ϕ​\(s,a\)⊤​wr\_\{w\}\(s,a\)=\\phi\(s,a\)^\{\\top\}w, and the successor features of a policyπ\\piare the discounted feature streamψπ\(s,a\)=𝔼π\[∑t≥0γtϕ\(st,at\)∣s0=s,a0=a\]\\psi^\{\\pi\}\(s,a\)=\\mathbb\{E\}^\{\\pi\}\\\!\\left\[\\sum\_\{t\\geq 0\}\\gamma^\{t\}\\phi\(s\_\{t\},a\_\{t\}\)\\mid s\_\{0\}=s,a\_\{0\}=a\\right\]\.

#### The pricing identity\.

Because expectation is linear and the reward is linear in the features, the value ofπ\\piunder any objectivewwis a dot product against a single, objective\-independent successor feature model:

Vwπ\(s,a\)=𝔼π\[∑t≥0γtϕ\(st,at\)⊤w\|s0=s,a0=a\]=ψπ\(s,a\)⊤w\.V^\{\\pi\}\_\{w\}\(s,a\)\\;=\\;\\mathbb\{E\}^\{\\pi\}\\\!\\Big\[\\textstyle\\sum\_\{t\\geq 0\}\\gamma^\{t\}\\,\\phi\(s\_\{t\},a\_\{t\}\)^\{\\top\}w\\,\\Big\|\\,s\_\{0\}=s,a\_\{0\}=a\\Big\]\\;=\\;\\psi^\{\\pi\}\(s,a\)^\{\\top\}w\.\(13\)The identity is what lets one model, learned once, price a policy under every objective in the linear family without re\-estimating a value function per objective\([2](https://arxiv.org/html/2608.11658#bib.bib1)\); it is the single\-agent form of the team identity \([3](https://arxiv.org/html/2608.11658#S2.E3)\), and every appearance ofψ⊤​w\\psi^\{\\top\}win the main text is an instance of it\.

#### The generalized policy improvement guarantee\.

Given a library\{πk\}k=1K\\\{\\pi^\{k\}\\\}\_\{k=1\}^\{K\}with successor features\{ψk\}\\\{\\psi^\{k\}\\\}and a test objectiveww, the GPI policy acts greedily with respect to the best library value at each state,πgpi​\(s\)∈arg⁡maxa​maxk​ψk​\(s,a\)⊤​w\\pi^\{\\mathrm\{gpi\}\}\(s\)\\in\\arg\\max\_\{a\}\\max\_\{k\}\\psi^\{k\}\(s,a\)^\{\\top\}w\.

###### Proposition 7\(GPI improvement,[2](https://arxiv.org/html/2608.11658#bib.bib1);[3](https://arxiv.org/html/2608.11658#bib.bib4)\)\.

For every statessand every library entrykk,Vwπgpi​\(s\)≥Vwπk​\(s\)V^\{\\pi^\{\\mathrm\{gpi\}\}\}\_\{w\}\(s\)\\geq V^\{\\pi^\{k\}\}\_\{w\}\(s\)\.

###### Proof\.

LetQ⁡\(s,a\)=maxk⁡ψk​\(s,a\)⊤​wQ\(s,a\)=\\max\_\{k\}\\psi^\{k\}\(s,a\)^\{\\top\}w\. For anykk, the greedy action satisfiesmaxa⁡Q⁡\(s,a\)≥Q⁡\(s,πk​\(s\)\)≥ψk​\(s,πk​\(s\)\)⊤​w=Vwπk​\(s\)\\max\_\{a\}Q\(s,a\)\\geq Q\(s,\\pi^\{k\}\(s\)\)\\geq\\psi^\{k\}\(s,\\pi^\{k\}\(s\)\)^\{\\top\}w=V^\{\\pi^\{k\}\}\_\{w\}\(s\), soπgpi\\pi^\{\\mathrm\{gpi\}\}has one\-step advantage at least that ofπk\\pi^\{k\}at every state\. The advantage telescopes: writingTgpiT^\{\\mathrm\{gpi\}\}for the Bellman operator ofπgpi\\pi^\{\\mathrm\{gpi\}\},Vwπk≤Tgpi​Vwπk≤\(Tgpi\)n​Vwπk→VwπgpiV^\{\\pi^\{k\}\}\_\{w\}\\leq T^\{\\mathrm\{gpi\}\}V^\{\\pi^\{k\}\}\_\{w\}\\leq\(T^\{\\mathrm\{gpi\}\}\)^\{n\}V^\{\\pi^\{k\}\}\_\{w\}\\to V^\{\\pi^\{\\mathrm\{gpi\}\}\}\_\{w\}by monotonicity and theγ\\gamma\-contraction ofTgpiT^\{\\mathrm\{gpi\}\}\. Proposition[1](https://arxiv.org/html/2608.11658#Thmproposition1)in the main text is the synchronized\-composition specialization of this argument to a team that switches together\. ∎

#### Why UVFA and USFA generalize across objectives\.

Universal value function approximators condition the value directly on the goal,V⁡\(s,g\)V\(s,g\), and share parameters across goals, so that a value learned for one goal transfers by function approximation to nearby goals rather than being retrained from scratch\([11](https://arxiv.org/html/2608.11658#bib.bib2)\)\. Universal successor feature approximators keep the pricing identity \([13](https://arxiv.org/html/2608.11658#A2.E13)\) but make the successor feature model itself universal,ψ~​\(s,a,z,w\)\\tilde\{\\psi\}\(s,a,z,w\), with a policy axiszzthat indexes which library policy is being priced and a task axiswwthat shapes the training behavior distribution and prices the result at test time\([4](https://arxiv.org/html/2608.11658#bib.bib3)\)\. The motivation is precisely the operating mode this paper needs: separating the policy axis from the task axis lets a single network be trained once over a distribution of objectives and then, at deployment, evaluate a dot product over a candidate set with no per\-task adaptation, because the objective enters only through the linear factorwwand never through retraining\. MA\-USFA is the multi\-agent counterpart: it keeps this policy\-task factorization per agent and adds a teammate\-context axis, so that each agent’s successor features remain valid as the teammates’ objectives change; Appendix[G](https://arxiv.org/html/2608.11658#A7)states the reuse precisely\.

## Appendix CProofs

### C\.1Proof of Proposition[1](https://arxiv.org/html/2608.11658#Thmproposition1)

Fix the libraryΠ\\Pi, the test objectivewtestw\_\{\\mathrm\{test\}\}, and an initial states0s\_\{0\}\. Writevk​\(s\)=Vwtestπk​\(s\)v^\{k\}\(s\)=V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\)for the value of entrykkunder the test objective, and letk∗​\(s\)∈arg⁡maxk​vk​\(s\)k^\{\*\}\(s\)\\in\\arg\\max\_\{k\}v^\{k\}\(s\)\. The synchronized rule \([4](https://arxiv.org/html/2608.11658#S2.E4)\) playsπk∗​\(s\)​\(s\)\\pi^\{k^\{\*\}\(s\)\}\(s\)at statess, provided the scoreψk​\(s,πk​\(s\)\)⊤​wtest\\psi^\{k\}\(s,\\pi^\{k\}\(s\)\)^\{\\top\}w\_\{\\mathrm\{test\}\}equals the true valuevk​\(s\)v^\{k\}\(s\); this is the validity premise of the proposition, and it holds exactly under the linear feature model\. We proveVwtestπsync​\(s\)≥vk​\(s\)V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)\\geq v^\{k\}\(s\)for every statessand every entrykk\.

For a finite horizonTT, letVtπ​\(s\)V\_\{t\}^\{\\pi\}\(s\)denote the value of policyπ\\piwithttsteps remaining, andVtπk​\(s\)V\_\{t\}^\{\\pi^\{k\}\}\(s\)likewise\. We show by induction onttthatVtπsync​\(s\)≥Vtπk​\(s\)V\_\{t\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)\\geq V\_\{t\}^\{\\pi^\{k\}\}\(s\)for everyssandkk\. The base caset=0t=0is trivial\. For the step, at statessthe rule playsak∗=πk∗​\(s\)​\(s\)a^\{k^\{\*\}\}=\\pi^\{k^\{\*\}\(s\)\}\(s\), and

Vt\+1πsync​\(s\)\\displaystyle V\_\{t\+1\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)=𝔼⁡\[ϕ​\(s,ak∗\)⊤​wtest\+γ​Vtπsync​\(s′\)\]\\displaystyle=\\mathbb\{E\}\\Big\[\\phi\(s,a^\{k^\{\*\}\}\)^\{\\top\}w\_\{\\mathrm\{test\}\}\+\\gamma\\,V\_\{t\}^\{\\pi^\{\\mathrm\{sync\}\}\}\(s^\{\\prime\}\)\\Big\]\(14\)≥𝔼⁡\[ϕ​\(s,ak∗\)⊤​wtest\+γ​Vtπk∗​\(s′\)\]=Vt\+1πk∗​\(s\),\\displaystyle\\geq\\mathbb\{E\}\\Big\[\\phi\(s,a^\{k^\{\*\}\}\)^\{\\top\}w\_\{\\mathrm\{test\}\}\+\\gamma\\,V\_\{t\}^\{\\pi^\{k^\{\*\}\}\}\(s^\{\\prime\}\)\\Big\]=V\_\{t\+1\}^\{\\pi^\{k^\{\*\}\}\}\(s\),\(15\)where the inequality applies the induction hypothesis at the successor states′s^\{\\prime\}, and the equality uses thatψk∗​\(s,ak∗\)⊤​wtest=Vπk∗​\(s\)\\psi^\{k^\{\*\}\}\(s,a^\{k^\{\*\}\}\)^\{\\top\}w\_\{\\mathrm\{test\}\}=V^\{\\pi^\{k^\{\*\}\}\}\(s\)by validity\. Sincek∗​\(s\)k^\{\*\}\(s\)maximizesvk​\(s\)v^\{k\}\(s\)over the library,Vt\+1πk∗​\(s\)=maxk⁡Vt\+1πk​\(s\)≥Vt\+1πk​\(s\)V\_\{t\+1\}^\{\\pi^\{k^\{\*\}\}\}\(s\)=\\max\_\{k\}V\_\{t\+1\}^\{\\pi^\{k\}\}\(s\)\\geq V\_\{t\+1\}^\{\\pi^\{k\}\}\(s\), which closes the induction\. TakingT→∞T\\to\\inftywithγ<1\\gamma<1gives the infinite\-horizon statement by standard monotone convergence \(the finite\-horizon values are increasing inTTand bounded by the discounted feature sums\)\. No assumption on the reward structure beyond validity, and none on the dynamics, is used: the argument never requires the transition kernel to factor or the features to decompose\.

### C\.2Proof of Proposition[2](https://arxiv.org/html/2608.11658#Thmproposition2)

We show that Requirements[1](https://arxiv.org/html/2608.11658#Thmrequirement1)and[2](https://arxiv.org/html/2608.11658#Thmrequirement2)together imply the safety boundVwtestπind​\(s\)≥maxk⁡Vwtestπk​\(s\)V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\)\\geq\\max\_\{k\}V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\)for every state\. Consider the joint\-GPI value of the library,gs​\(a\)=maxk⁡ψk​\(s,a\)⊤​wtestg\_\{s\}\(a\)=\\max\_\{k\}\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}, whose greedy policyπgpi​\(s\)∈arg⁡maxa​gs​\(a\)\\pi^\{\\mathrm\{gpi\}\}\(s\)\\in\\arg\\max\_\{a\}g\_\{s\}\(a\)satisfies the single\-agent guaranteeVwtestπgpi​\(s\)≥maxk⁡Vwtestπk​\(s\)V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{\\mathrm\{gpi\}\}\}\(s\)\\geq\\max\_\{k\}V\_\{w\_\{\\mathrm\{test\}\}\}^\{\\pi^\{k\}\}\(s\)\(Proposition[7](https://arxiv.org/html/2608.11658#Thmproposition7)of Appendix[B](https://arxiv.org/html/2608.11658#A2), applied to the joint action space\)\. It suffices to show that under the two requirements the independently composed policyπind\\pi^\{\\mathrm\{ind\}\}of \([5](https://arxiv.org/html/2608.11658#S2.E5)\) selects a joint action inarg⁡maxa​gs​\(a\)\\arg\\max\_\{a\}g\_\{s\}\(a\)at every state and is scored by valid values\.

Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)states that each storedψik\\psi^\{k\}\_\{i\}is the true successor feature of the composed joint policy, so every per\-agent scoreψik​\(s,ai\)⊤​wi\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)^\{\\top\}w\_\{i\}equals the corresponding component of the true joint value, and the joint score∑iψik​\(s,ai\)⊤​wi\\sum\_\{i\}\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)^\{\\top\}w\_\{i\}equalsψk​\(s,a\)⊤​wtest\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}; the values driving \([5](https://arxiv.org/html/2608.11658#S2.E5)\) are therefore the same values that definegsg\_\{s\}, with no staleness\. Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1)states that the joint maximizer ofgsg\_\{s\}is reachable by per\-agent greedy choices,A∗​\(s\)=∏iAi∗​\(s\)A^\{\*\}\(s\)=\\prod\_\{i\}A^\{\*\}\_\{i\}\(s\), so the coordinate\-wise maximizers selected by \([5](https://arxiv.org/html/2608.11658#S2.E5)\) form a joint action inarg⁡maxa​gs​\(a\)\\arg\\max\_\{a\}g\_\{s\}\(a\)\(a consistent tie\-break resolves ties within the product set\)\. Henceπind\\pi^\{\\mathrm\{ind\}\}coincides with a joint\-GPI policy scored by valid values, and the guarantee of Proposition[7](https://arxiv.org/html/2608.11658#Thmproposition7)transfers to it\. The two requirements are exactly the two premises the single\-agent argument needs once it is executed byNNdecentralized maximizers rather than one: validity restores the fixed\-dynamics premise at composition time, and alignment restores the single\-decision\-maker premise\.

### C\.3The counterexample of Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3): full construction

#### Task\.

Two agents, two stages, deterministic dynamics\. Each agent has its own two\-dimensional feature stream, and its reward depends only on its own action, so the team reward is fully separable:ri​\(s,ai\)=ϕi​\(s,ai\)⊤​wr\_\{i\}\(s,a\_\{i\}\)=\\phi\_\{i\}\(s,a\_\{i\}\)^\{\\top\}wwith a shared weightw=\(9,8\)w=\(9,8\)\. The two coupling between the agents lives entirely in the transition: the second\-stage state isT⁡\(a1,a2\)T\(a\_\{1\},a\_\{2\}\)withT⁡\(0,0\)=T⁡\(1,1\)=0T\(0,0\)=T\(1,1\)=0andT⁡\(0,1\)=T⁡\(1,0\)=1T\(0,1\)=T\(1,0\)=1\. The feature values are collected in Table[2](https://arxiv.org/html/2608.11658#A3.T2)\.

Table 2:Feature values of the Lemma[3](https://arxiv.org/html/2608.11658#Thmproposition3)construction\. Agentii’s reward at the first stage isϕi​\(ai\)⊤​w\\phi\_\{i\}\(a\_\{i\}\)^\{\\top\}w, and at the second stageϕi​\(s1,ai\)⊤​w\\phi\_\{i\}\(s\_\{1\},a\_\{i\}\)^\{\\top\}w; only the transition depends on both agents’ actions\.
#### Library\.

The library holds two entries, both suboptimal underww\(the joint optimum is321321, computed below\)\. Entryπ0\\pi^\{0\}plays\(0,1\)\(0,1\)ats0s\_\{0\}and\(0,0\)\(0,0\)at the second stage in both states; entryπ1\\pi^\{1\}plays\(0,1\)\(0,1\)ats0s\_\{0\}and\(0,1\)\(0,1\)or\(1,0\)\(1,0\)at the second stage\. Their values are

Vπ0​\(s0\)\\displaystyle V^\{\\pi^\{0\}\}\(s\_\{0\}\)=\[\(1,3\)\+\(6,5\)\+\(5,7\)\+\(3,4\)\]⋅w=\(15,19\)⋅\(9,8\)=287,\\displaystyle=\\big\[\(1,3\)\+\(6,5\)\+\(5,7\)\+\(3,4\)\\big\]\\cdot w=\(15,19\)\\cdot\(9,8\)=287,\(16\)Vπ1​\(s0\)\\displaystyle V^\{\\pi^\{1\}\}\(s\_\{0\}\)=\[\(1,3\)\+\(6,5\)\+\(3,0\)\+\(3,4\)\]⋅w=\(13,12\)⋅\(9,8\)=213,\\displaystyle=\\big\[\(1,3\)\+\(6,5\)\+\(3,0\)\+\(3,4\)\\big\]\\cdot w=\(13,12\)\\cdot\(9,8\)=213,\(17\)so the best library entry is worth287287; the second\-stage terms follow fromT⁡\(0,1\)=1T\(0,1\)=1and the entries’ second\-stage actions\. Every library entry is strictly suboptimal:287<321287<321\.

#### The independent composition\.

For each agent we compute the per\-agent snapshot value of each action, the expected feature sum when the agent takes the action while the teammate follows the entry and the team continues along the entry\. Ats0s\_\{0\}, agent 1’s values are134134fora1=0a\_\{1\}=0\(achieved through entryπ0\\pi^\{0\}: teammate plays11, the team transitions tos1=1s\_\{1\}=1alongT⁡\(0,1\)T\(0,1\), and agent 1 plays00there, so\[\(1,3\)\+\(5,7\)\]⋅w=134\[\(1,3\)\+\(5,7\)\]\\cdot w=134\) and8484fora1=1a\_\{1\}=1; agent 2’s values are175175fora2=0a\_\{2\}=0\(throughπ0\\pi^\{0\}: teammate plays00, the team transitions tos1=0s\_\{1\}=0alongT⁡\(0,0\)T\(0,0\), and agent 2 plays00there, so\[\(0,7\)\+\(7,7\)\]⋅w=175\[\(0,7\)\+\(7,7\)\]\\cdot w=175\) and153153fora2=1a\_\{2\}=1\. Neither agent faces a tie\. The independent rule therefore plays\(0,0\)\(0,0\)ats0s\_\{0\}\. The transition sends the team tos1=0s\_\{1\}=0, where the per\-agent values are the immediate feature rewards alone,\(36,60\)\(36,60\)for agent 1 and\(119,84\)\(119,84\)for agent 2, and the rule plays\(1,0\)\(1,0\)\. The composed trajectory delivers

\[\(1,3\)\+\(0,7\)\+\(4,3\)\+\(7,7\)\]⋅w=\(12,20\)⋅\(9,8\)=268<287=maxk⁡Vπk​\(s0\)\.\\big\[\(1,3\)\+\(0,7\)\+\(4,3\)\+\(7,7\)\\big\]\\cdot w=\(12,20\)\\cdot\(9,8\)=268<287=\\max\_\{k\}V^\{\\pi^\{k\}\}\(s\_\{0\}\)\.\(18\)The delivered per\-agent shares are9393for agent 1 \(rated134134\) and175175for agent 2 \(rated175175\)\.

#### Mechanism\.

Agent 1’s choice was justified by a value of134134, the features it would accrue if agent 2 kept the library’s action ats0s\_\{0\}and the team continued down the branchs1=1s\_\{1\}=1along entryπ0\\pi^\{0\}\. Agent 2’s independent choice flips the transition tos1=0s\_\{1\}=0, and agent 1 delivers9393instead: its snapshot value described a teammate that is not the one the composition pairs it with\. Agent 2’s rating happened to be accurate, because agent 1’s actual choice matches what the rating assumed; a single stale rating suffices to drag the team1919points below its own best library entry\. Both agents acted exactly as their values told them to: the failure is not a selection error, it is a validity failure \(Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)\)\. The centralized joint\-GPI rule over the same library selects\(1,1\)\(1,1\)ats0s\_\{0\}\(rated297297through entryπ0\\pi^\{0\}’s continuation\) and\(1,0\)\(1,0\)ats1=0s\_\{1\}=0, and delivers\[\(0,6\)\+\(6,5\)\+\(4,3\)\+\(7,7\)\]⋅w=\(17,21\)⋅\(9,8\)=321\[\(0,6\)\+\(6,5\)\+\(4,3\)\+\(7,7\)\]\\cdot w=\(17,21\)\\cdot\(9,8\)=321, the joint optimum: centralization protects the values, because the joint successor features remain valid descriptions of the joint policies they were measured for\. The failure is therefore specific to decentralization\.

#### Alignment holds\.

The joint actions optimal for the test objective are a singleton at every state: ats0s\_\{0\}the unique optimal joint action is\(1,1\)\(1,1\)\(value321321\); ats1=0s\_\{1\}=0it is\(1,0\)\(1,0\)\(value179179, against155155,120120and144144for the other three actions\); ats1=1s\_\{1\}=1it is\(0,0\)\(0,0\)\(value160160, against135135,8686and6161\)\. Singletons are trivially product sets, so the alignment condition of Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1)holds at every state: no alignment story can explain the failure\. What fails is Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2): the per\-agent values are snapshot quantities, measured against a specific version of the teammates, and recomposition invalidates them\.

#### A companion instance: staleness without violation\.

The same mechanism need not always produce a violation; it always voids the guarantee\. In a two\-stage companion construction with joint features, weightw=\(0\.6,0\.4\)w=\(0\.6,0\.4\), and a three\-entry library whose best entry is worth4\.24\.2\(the other two worth3\.03\.0and3\.23\.2\), the alignment condition again holds at the test objective, yet the independent rule delivers6\.26\.2: above every library entry, so the safety inequality of Definition[1](https://arxiv.org/html/2608.11658#Thmdefinition1)holds, but below the joint optimum6\.66\.6, which the centralized joint\-GPI rule attains\. The values that drove the composition were still wrong: agent 2’s choice was justified by a snapshot value of6\.66\.6, the value it would have if agent 1 followed the third entry, and the composition delivers6\.26\.2because agent 1 does not\. The composition is safe by the letter of the definition and invalid by the mechanism that produces it\.

### C\.4Proof of Proposition[4](https://arxiv.org/html/2608.11658#Thmproposition4)

We prove the alignment claim that carries the proposition, then the value comparison\. Throughout,gs​\(a\)=maxk⁡ψk​\(s,a\)⊤​wtestg\_\{s\}\(a\)=\\max\_\{k\}\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}is the joint GPI value at statess\.

#### Topkis lemma\.

Ifgsg\_\{s\}is supermodular on the lattice\{0,1\}N\\\{0,1\\\}^\{N\}, its argmax set is a sublattice\. Fora,b∈arg⁡max⁡gsa,b\\in\\arg\\max g\_\{s\}, supermodularity givesgs​\(a∨b\)\+gs​\(a∧b\)≥gs​\(a\)\+gs​\(b\)=2​gs∗g\_\{s\}\(a\\vee b\)\+g\_\{s\}\(a\\wedge b\)\\geq g\_\{s\}\(a\)\+g\_\{s\}\(b\)=2g\_\{s\}^\{\*\}, wheregs∗g\_\{s\}^\{\*\}is the maximum; since neither term can exceedgs∗g\_\{s\}^\{\*\}, both must equal it, soa∨ba\\vee banda∧ba\\wedge bare also argmaxes, which is the defining property of a sublattice\([14](https://arxiv.org/html/2608.11658#bib.bib11)\)\. The same conclusion holds whengsg\_\{s\}is supermodular on a rectangular sublattice containing all of its argmax, by restricting the argument to that sublattice\.

#### Alignment\.

The per\-agent rule maximizes, per agent, the marginal valuehi​\(ai\)=maxk⁡ψik​\(s,ai\)⊤​wih\_\{i\}\(a\_\{i\}\)=\\max\_\{k\}\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)^\{\\top\}w\_\{i\}\. When the joint value decomposes over agents,ψk​\(s,a\)⊤​w=∑iψik​\(s,ai\)⊤​wi\\psi^\{k\}\(s,a\)^\{\\top\}w=\\sum\_\{i\}\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)^\{\\top\}w\_\{i\}, which holds under per\-agent additive features, the per\-agent greedy choices are the coordinate\-wise maximizers of the decomposed library, and two facts combine: the argmax ofgsg\_\{s\}is a sublattice by the lemma, and per\-agent greedy execution with a consistent tie\-break rule \(the same resolution criterion applied by every agent, for example a shared index over entries\) selects a vector in that sublattice\. The composed policy then executes the joint GPI rule at every state, soVπind​\(s\)≥maxk⁡Vπk​\(s\)V^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\)\\geq\\max\_\{k\}V^\{\\pi^\{k\}\}\(s\)by the standard generalized policy improvement argument \(the same telescoping as in Appendix[C](https://arxiv.org/html/2608.11658#A3)above\), andmaxk⁡Vπk​\(s\)=Vπsync​\(s\)\\max\_\{k\}V^\{\\pi^\{k\}\}\(s\)=V^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)by Proposition[1](https://arxiv.org/html/2608.11658#Thmproposition1)\. This givesVπind​\(s\)≥Vπsync​\(s\)V^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\)\\geq V^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)\.

In the general case without an additive decomposition, the per\-agent marginals and the joint value are no longer the same objects, so the argument covers the additive \(value\-decomposed\) regime, the setting in which the per\-agent greedy choices realize the joint maximizer\.

### C\.5Proof of Corollary[5](https://arxiv.org/html/2608.11658#Thmproposition5)

LetΔ​ϕd​\(a,b\)=ϕd​\(a∨b\)\+ϕd​\(a∧b\)−ϕd​\(a\)−ϕd​\(b\)\\Delta\\phi\_\{d\}\(a,b\)=\\phi\_\{d\}\(a\\vee b\)\+\\phi\_\{d\}\(a\\wedge b\)\-\\phi\_\{d\}\(a\)\-\\phi\_\{d\}\(b\)be the supermodularity gap of featureddon the pair of joint actions\(a,b\)\(a,b\)\. Under the hypothesis, each library entry prices joint actions by the same feature\-linear function up to an additive constant,ψk​\(s,a\)⊤​wtest=ϕ​\(a\)⊤​wtest\+ck​\(s\)\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}=\\phi\(a\)^\{\\top\}w\_\{\\mathrm\{test\}\}\+c\_\{k\}\(s\)withck​\(s\)c\_\{k\}\(s\)independent ofaa, since the per\-pair differencesψk​\(s,a\)⊤​wtest−ψk​\(s,b\)⊤​wtest=\(ϕ⁡\(a\)−ϕ⁡\(b\)\)⊤​wtest\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}\-\\psi^\{k\}\(s,b\)^\{\\top\}w\_\{\\mathrm\{test\}\}=\(\\phi\(a\)\-\\phi\(b\)\)^\{\\top\}w\_\{\\mathrm\{test\}\}do not depend onkk\. Taking the library maximum,gs​\(a\)=ϕ​\(a\)⊤​wtest\+maxk⁡ck​\(s\)g\_\{s\}\(a\)=\\phi\(a\)^\{\\top\}w\_\{\\mathrm\{test\}\}\+\\max\_\{k\}c\_\{k\}\(s\), sogsg\_\{s\}equals the feature\-linear value up to a state\-constant\. The constant cancels in every second difference, so for every pair of joint actions

gs​\(a∨b\)\+gs​\(a∧b\)−gs​\(a\)−gs​\(b\)=∑dwdtest​Δ​ϕd​\(a,b\)\.g\_\{s\}\(a\\vee b\)\+g\_\{s\}\(a\\wedge b\)\-g\_\{s\}\(a\)\-g\_\{s\}\(b\)=\\textstyle\\sum\_\{d\}w\_\{d\}^\{\\mathrm\{test\}\}\\,\\Delta\\phi\_\{d\}\(a,b\)\.\(19\)Supermodularity ofgsg\_\{s\}is nonnegativity of the left\-hand side over all pairs, and membershipwtest∈Kϕw\_\{\\mathrm\{test\}\}\\in K\_\{\\phi\}is nonnegativity of the right\-hand side over all pairs; these are the same inequalities, sogsg\_\{s\}is supermodular if and only ifwtest∈Kϕw\_\{\\mathrm\{test\}\}\\in K\_\{\\phi\}, and Proposition[4](https://arxiv.org/html/2608.11658#Thmproposition4)applies exactly on the cone\. The reasoning is not the loose “maximum of supermodular functions is supermodular” \(false in general\); it is the constant offset that makes the library maximum feature\-linear\. The sufficient condition stated in the corollary, every featureϕd\\phi\_\{d\}itself supermodular andw≥0w\\geq 0, is immediate: each termwd​Δ​ϕd​\(a,b\)w\_\{d\}\\,\\Delta\\phi\_\{d\}\(a,b\)is then nonnegative\.

### C\.6Proof of Proposition[6](https://arxiv.org/html/2608.11658#Thmproposition6)

Assume the transition kernel factorizes per agent,si′=fi​\(si,ai\)s^\{\\prime\}\_\{i\}=f\_\{i\}\(s\_\{i\},a\_\{i\}\), and suppose first that the features also decompose per agent, so the per\-agent successor featureψik​\(s,ai\)\\psi^\{k\}\_\{i\}\(s,a\_\{i\}\)is the discounted feature stream of agentii’s own dynamics\. Because the dynamics of agentiinever depend on the teammates,ψik\\psi^\{k\}\_\{i\}remains a valid description of agentii’s feature stream under any recomposition: whoever the other agents are, agentii’s marginal process is the same function of its own actions\. Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)therefore holds by construction, for every library and every recomposition, not only at the test objective\. Requirement[1](https://arxiv.org/html/2608.11658#Thmrequirement1)is then governed by the structural condition of Proposition[4](https://arxiv.org/html/2608.11658#Thmproposition4), and the value comparison follows as in that proposition:Vπind​\(s\)≥maxk⁡Vπk​\(s\)=Vπsync​\(s\)V^\{\\pi^\{\\mathrm\{ind\}\}\}\(s\)\\geq\\max\_\{k\}V^\{\\pi^\{k\}\}\(s\)=V^\{\\pi^\{\\mathrm\{sync\}\}\}\(s\)\.

For coupled rewards, the cross\-feature components of the per\-agent values are measured against the library’s teammate behavior, and under recomposition they are stale: the per\-agent value is a marginalized quantity whose validity is no longer exact, so the guarantee need not extend beyond the decomposed\-reward case\. The channels are therefore not independent: factorization pays off exactly where the reward decomposes\.

## Appendix DMA\-USFA: Training and Deployment

This appendix gives the full training and deployment procedure of MA\-USFA \(Section[4](https://arxiv.org/html/2608.11658#S4)\), stated independently of any experimental domain\. It collects the two\-phase protocol, the pseudocode for both training and the deployment forward pass, and the two design choices that keep the composer small, and it closes by placing MA\-USFA next to the two composition rules it is analyzed against\.

### D\.1The two training phases

The two phases of the MA\-USFA protocol are summarized in Table[3](https://arxiv.org/html/2608.11658#A4.T3); the per\-team\-size budgets are reported with the controlled\-domain setup \(Appendix[E](https://arxiv.org/html/2608.11658#A5)\)\. Phase 1 trains the lower per\-agent value layerψ~i\\tilde\{\\psi\}\_\{i\}of \([11](https://arxiv.org/html/2608.11658#S4.E11)\), sampling tasks at training set \(tasks from the homogeneous and heterogeneous scenarios\) with the teammate\-context conditioning, and freezes it; Phase 2 trains the upper\-layer composer on top\. Both phases build components of MA\-USFA itself: the first produces the frozen value layer, and the second produces the composer stacked on top of it\. The two phases correspond one\-to\-one with the two layers of Section[4](https://arxiv.org/html/2608.11658#S4)\.

Table 3:The two\-phase training protocol of MA\-USFA\. Each phase builds one layer of the method: Phase 1 the frozen per\-agent value layer, Phase 2 the composer on top of it\.
### D\.2Pseudocode

Algorithm[1](https://arxiv.org/html/2608.11658#alg1)states the training procedure and Algorithm[2](https://arxiv.org/html/2608.11658#alg2)the deployment\-time forward pass, making concrete the two\-phase protocol of Section[4](https://arxiv.org/html/2608.11658#S4)and the notation of \([11](https://arxiv.org/html/2608.11658#S4.E11)\)\. Training produces two artifacts that are never adapted per objective: the frozen per\-agent value layerψ~i\(s,ai∣zi,w−i\)\\tilde\{\\psi\}\_\{i\}\(s,a\_\{i\}\\mid z\_\{i\},w\_\{\-i\}\)and the composerΥθ=\(Υ1θ,…,ΥNθ\)\\Upsilon^\{\\theta\}=\(\\Upsilon^\{\\theta\}\_\{1\},\\dots,\\Upsilon^\{\\theta\}\_\{N\}\)\. Deployment runs the composer on every test objectivewtest=\(w1,…,wN\)w\_\{\\mathrm\{test\}\}=\(w\_\{1\},\\dots,w\_\{N\}\): because it is initialized at the independent transfer policy and trained only in value\-increasing directions with the value layer frozen, on every objective it is at least as good as that policy and improves on it wherever a cross\-agent correction helps\. The composer is always the deciding rule; the fixed rules take no part in deployment\.

Algorithm 1MA\-USFA training \(run once before deployment\)1:feature map

ϕ\\phi; training tasks

Wtrain=Whomo∪WheteroW\_\{\\mathrm\{train\}\}=W\_\{\\mathrm\{homo\}\}\\cup W\_\{\\mathrm\{hetero\}\}; correction tasks

WcorrW\_\{\\mathrm\{corr\}\}\(coupled dynamics or weights outside

KϕK\_\{\\phi\}\); discount

γ\\gamma
2:Phase 1 — per\-agent context\-conditioned value layer\(lower layer, Eq\.[11](https://arxiv.org/html/2608.11658#S4.E11)\)

3:foreach

w=\(w1,…,wN\)w=\(w\_\{1\},\\dots,w\_\{N\}\)sampled at random from

WtrainW\_\{\\mathrm\{train\}\}do

4:sample policy encodings

zi∼Dz\(⋅∣wi\)z\_\{i\}\\sim D\_\{z\}\(\\cdot\\mid w\_\{i\}\); form the teammate context

w−i=\(wj\)j≠iw\_\{\-i\}=\(w\_\{j\}\)\_\{j\\neq i\}
5:update each

ψ~i\(s,ai∣zi,w−i\)\\tilde\{\\psi\}\_\{i\}\(s,a\_\{i\}\\mid z\_\{i\},w\_\{\-i\}\)toward

ϕi\+γψ~i\(s′,ai′∣zi,w−i\)\\phi\_\{i\}\+\\gamma\\,\\tilde\{\\psi\}\_\{i\}\(s^\{\\prime\},a\_\{i\}^\{\\prime\}\\mid z\_\{i\},w\_\{\-i\}\)
6:endfor

7:freeze the value layer

\{ψ~i\}\\\{\\tilde\{\\psi\}\_\{i\}\\\}
8:Phase 2 — learned composer\(upper layer, Lem\.[3](https://arxiv.org/html/2608.11658#Thmproposition3), Props\.[4](https://arxiv.org/html/2608.11658#Thmproposition4),[6](https://arxiv.org/html/2608.11658#Thmproposition6)\)

9:initialize the composer head

θ\\thetaat zero⊳\\trianglerighttraining starts exactly at the transfer policy

10:foreach

w∈Wcorrw\\in W\_\{\\mathrm\{corr\}\}\(weights outside the cone

KϕK\_\{\\phi\}, or coupled dynamics\)do

11:price candidates

qi​\(zi\)←ψ~i​\(s,⋅,zi\)⊤​wiq\_\{i\}\(z\_\{i\}\)\\leftarrow\\tilde\{\\psi\}\_\{i\}\(s,\\cdot,z\_\{i\}\)^\{\\top\}w\_\{i\}for

zi∈Ciz\_\{i\}\\in C\_\{i\}using the frozen value layer

12:select

gi←Υiθ​\(s,w,\{qi​\(zi\)\}\)g\_\{i\}\\leftarrow\\Upsilon^\{\\theta\}\_\{i\}\\big\(s,\\,w,\\,\\\{q\_\{i\}\(z\_\{i\}\)\\\}\\big\)for all

ii; execute the joint action; observe reward

13:update

θ\\thetaby per\-agent temporal difference \(value layer frozen\)

14:endfor

15:returnfrozen value layer

\{ψ~i\}\\\{\\tilde\{\\psi\}\_\{i\}\\\}and composer

Υθ\\Upsilon^\{\\theta\}

Algorithm 2MA\-USFA deployment \(single forward pass, no gradient updates\)1:test objective

wtest=\(w1,…,wN\)w\_\{\\mathrm\{test\}\}=\(w\_\{1\},\\dots,w\_\{N\}\); frozen

\{ψ~i\}\\\{\\tilde\{\\psi\}\_\{i\}\\\}; composer

Υθ\\Upsilon^\{\\theta\}; candidate sets

\{Ci\}\\\{C\_\{i\}\\\}
2:foreach decision state

ssdo

3:price candidates

qi​\(zi\)←ψ~i​\(s,⋅,zi\)⊤​wiq\_\{i\}\(z\_\{i\}\)\\leftarrow\\tilde\{\\psi\}\_\{i\}\(s,\\cdot,z\_\{i\}\)^\{\\top\}w\_\{i\}for every

zi∈Ciz\_\{i\}\\in C\_\{i\}⊳\\trianglerightone dot product per candidate

4:

ai←a\_\{i\}\\leftarrowaction of entry

gi=Υiθ​\(s,wtest,\{qi​\(zi\)\}\)g\_\{i\}=\\Upsilon^\{\\theta\}\_\{i\}\\big\(s,\\,w\_\{\\mathrm\{test\}\},\\,\\\{q\_\{i\}\(z\_\{i\}\)\\\}\\big\)for all

ii⊳\\trianglerightcomposer selects on every objective

5:execute the joint action

\(a1,…,aN\)\(a\_\{1\},\\dots,a\_\{N\}\)
6:endfor

#### Implementation choices\.

Three choices make the composer small and stable, and they are shared across both experimental domains\. The composer head is initialized at zero, so training starts exactly at the transfer policy; the value layer is frozen while the composer trains, protecting the library from drift; and for large teams the composer attends over the interaction graph rather than the full joint state, a one\-hop graph attention pass per selector\([15](https://arxiv.org/html/2608.11658#bib.bib14)\), which is what makes the196196\-agent traffic network of Appendix[F](https://arxiv.org/html/2608.11658#A6)feasible\. The first two hold in every run; the third is the neighbor\-limited instantiation used at city scale \(Appendix[F](https://arxiv.org/html/2608.11658#A6)\)\.

#### Extension: deployment without a composer\.

One extension lies outside the method proper\. If the composer cannot be trained at all, for instance under a learning budget too small to fit it, deployment can use a fixed rule in its place, and the analysis of Section[3](https://arxiv.org/html/2608.11658#S3)says which one: synchronized composition by default, and the independent rule only where its two requirements hold\. This chooses among the rules we analyze rather than the one we propose; MA\-USFA itself needs no such choice\.

### D\.3Composition rules studied as baselines

MA\-USFA is analyzed against two fixed composition rules, which are objects of study rather than components of the method\. Table[4](https://arxiv.org/html/2608.11658#A4.T4)places the three side by side, listing their mechanism, the set of joint policies each can produce, and the safety status established in Section[3](https://arxiv.org/html/2608.11658#S3)\.

Table 4:The coupling spectrum of composition rules\. Composition space is the set of joint policies a rule can produce\. Safety is with respect to \([6](https://arxiv.org/html/2608.11658#S3.E6)\)\.

## Appendix EControlled Domain: SFWorld

This appendix reports the controlled\-domain experiment in full: the environment and setup, the crossover result behind the main\-body table, and the team\-size and library\-coverage sweeps\.

### E\.1Setup

#### Environment\.

SFWorld is a5×55\\times 5grid withN∈\{2,3,4,5\}N\\in\\\{2,3,4,5\\\}agents, five actions \(four moves and stay\), horizon4040, discountγ=0\.95\\gamma=0\.95\. The featuresϕi​\(s′\)\\phi\_\{i\}\(s^\{\\prime\}\)of agentiiare dense smooth bumps overKKresource cells, shaped after the congestion signals of the traffic domain; the reward of agentiiisri=ϕi​\(s′\)⊤​wi−2\.0⋅blockedir\_\{i\}=\\phi\_\{i\}\(s^\{\\prime\}\)^\{\\top\}w\_\{i\}\-2\.0\\cdot\\mathrm\{blocked\}\_\{i\}, a task weight times the features minus a collision penalty that lives outside the feature basis, so any closed\-form pricingψ⋅w\\psi\\cdot wis structurally blind to it\. The coupling parameterκ\\kappagoverns conflicts: when two agents target the same cell, the conflict blocks all but one of them with probabilityκ\\kappa\. Atκ=0\\kappa=0the dynamics factorize exactly, the free region of Proposition[6](https://arxiv.org/html/2608.11658#Thmproposition6)is in force, and the collision rate is zero at everyκ\\kappaonAdistinctA\_\{\\mathrm\{distinct\}\}; asκ\\kappagrows, each agent’s effective kernel depends on the teammates’ actions, which is transition coupling\. Two task families separate the channels \(Fig\.[2](https://arxiv.org/html/2608.11658#A5.F2)\):AdistinctA\_\{\\mathrm\{distinct\}\}, where the agents’ optimal regions are disjoint so coupling never binds, andBoverlapB\_\{\\mathrm\{overlap\}\}, where the agents contend for a shared region so the same weights create collisions whenever the joint policy hybridizes\.

![Refer to caption](https://arxiv.org/html/2608.11658v1/fig_sfworld.png)Figure 2:The SFWorld scene and its two task families, shown forN=2N=2on the5×55\\times 5grid\. Each agent earns reward by occupying cells in its own resource region, whose value under a task isϕi​\(s′\)⊤​wi\\phi\_\{i\}\(s^\{\\prime\}\)^\{\\top\}w\_\{i\}; a collision penalty, outside the feature basis, is charged whenever two agents target the same cell\. Left \(AdistinctA\_\{\\mathrm\{distinct\}\}\): the two resource regions are disjoint\. Right \(BoverlapB\_\{\\mathrm\{overlap\}\}\): a single contested region is valuable to both agents\. The coupling probabilityκ\\kappascales how often a shared\-cell conflict blocks an agent\.
#### Library\.

The library holdsKKpolicies specialized to corner objectives\. The main configuration uses the four corners of the weight simplex \(K=4K=4\); the library\-content sweep \(Fig\.[5](https://arxiv.org/html/2608.11658#A5.F5)\) varies both the size and the content: the four corners alone \(P4\), the corners plus the contested joint action\(0,0\)\(0,0\)\(P4\+\+\(0,0\)\), plus both\(0,0\)\(0,0\)and\(1,1\)\(1,1\)\(P4\+\+\(0,0\)\+\+\(1,1\)\), the corners plus four copies of one entry \(P4\+\+4 same\), and libraries built around\(0,0\)\(0,0\)alone or with one or two additional entries\. The team\-size sweep usesK=4K=4forN≤4N\\leq 4andK=8K=8forN=5N=5\.

#### Learning\.

Successor features are trained with the USFA protocol: the TD target is the feature vectorϕ\\phi, the weight plays the three roles of behavior anchor, library anchor \(z∼Dz\(⋅∣w\)z\\sim D\_\{z\}\(\\cdot\\mid w\)\), and test\-time pricing vector\. Training budgets scale with the team size:8,0008\{,\}000episodes forN=2N=2,6,0006\{,\}000forN=3N=3,5,0005\{,\}000forN=4N=4,4,0004\{,\}000forN=5N=5; the composer is trained for1,0001\{,\}000episodes atN=2N=2,2,0002\{,\}000atN=3N=3,1,6001\{,\}600atN=4N=4,1,4001\{,\}400atN=5N=5; per\-task retraining runs4,0004\{,\}000episodes\. Evaluation averages120120rollouts per configuration\. The composer is warm\-started from the transfer policy \(zero\-initialized correction head\) and trained with per\-agent temporal\-difference updates with the feature backbone frozen; of the three composer instantiations, an attention head, a message\-passing head, and a QMIX\-style mixing head, the three variants are interchangeable in this domain because the optimal deferral is static, so the paper reports the best of the three\. The coupling sweep usesκ∈\{0,0\.25,0\.5,0\.75,1\.0\}\\kappa\\in\\\{0,0\.25,0\.5,0\.75,1\.0\\\}in the main matrix andκ∈\{0,0\.5,1\.0\}\\kappa\\in\\\{0,0\.5,1\.0\\\}in the team\-size sweep\.

#### Baselines\.

The synchronized rule is the composition rule of \([4](https://arxiv.org/html/2608.11658#S2.E4)\); the independent rule is the composition rule of \([5](https://arxiv.org/html/2608.11658#S2.E5)\); joint\-GPI is the centralized generalized policy improvement rule over the joint action space, representing prior work on multi\-agent GPI \(computed only forN≤3N\\leq 3, where the joint space can be enumerated; the joint\-GPI entries forN≥4N\\geq 4in Table[5](https://arxiv.org/html/2608.11658#A5.T5)are missing by design\); per\-task retraining optimizes the penalty\-inclusive reward from scratch and is the oracle ceiling\. All closed\-form operators use successor features trained on the harvest features only, as theory prescribes; the collision penalty is deliberately outside the feature basis so that no closed\-form rule can price it\. The two\-phase training protocol of MA\-USFA is given in Appendix[D](https://arxiv.org/html/2608.11658#A4)\(Table[3](https://arxiv.org/html/2608.11658#A4.T3)\); the phase budgets per team size are those reported under Learning above\.

### E\.2The crossover

Table[1](https://arxiv.org/html/2608.11658#S5.T1)in the body reports theN=2N=2main matrix\. Fig\.[3](https://arxiv.org/html/2608.11658#A5.F3)plots itsBoverlapB\_\{\\mathrm\{overlap\}\}block, so the crossover of the two fixed rules and the tracking of MA\-USFA against retraining are visible as curves in the coupling parameterκ\\kappa\.

![Refer to caption](https://arxiv.org/html/2608.11658v1/fig1_crossover.png)Figure 3:Crossover experiment onBoverlapB\_\{\\mathrm\{overlap\}\}\(N=2N=2, four\-entry corner library\), theBoverlapB\_\{\\mathrm\{overlap\}\}block of Table[1](https://arxiv.org/html/2608.11658#S5.T1)in visual form\. Curves show team return \(summed over the4040\-step horizon\) of the three composition rules of Section[2](https://arxiv.org/html/2608.11658#S2)\(Synchronized, Independent, MA\-USFA\), the joint\-GPI baseline of prior work, and per\-task retraining, as the transition couplingκ\\kappa\(the probability that two agents targeting the same cell collide\) increases from00to11\. The dotted horizontal line marks the per\-task joint optimum; the shaded strip atκ=0\\kappa=0marks the factorized regime\.
### E\.3Team\-size sweep

Table[5](https://arxiv.org/html/2608.11658#A5.T5)and Fig\.[4](https://arxiv.org/html/2608.11658#A5.F4)sweep the team fromN=2N=2to55on both task families atκ∈\{0,0\.5,1\.0\}\\kappa\\in\\\{0,0\.5,1\.0\\\}\. The paid\-region collapse of the independent rule deepens sharply with team size, from7\.077\.07atN=2N=2to−37\.00\-37\.00atκ=1\.0\\kappa=1\.0as its collision rate approaches0\.60\.6; the synchronized rule stays flat and safe at every size, and MA\-USFA recovers the retraining level at everyNNandκ\\kappa\. OnAdistinctA\_\{\\mathrm\{distinct\}\}the collision rate is zero at all sizes and the independent rule is free, the null control of the design\.

Table 5:Team\-size sweep, corner library \(K=4K=4forN≤4N\\leq 4,K=8K=8forN=5N=5\), all three coupling levels\. Team return over4040steps, mean±\\pmstandard deviation over three evaluation seeds\. The joint\-GPI baseline is omitted \(−\-\) forN≥4N\\geq 4because the joint action space can no longer be enumerated\. The Average row under each team size gives each method’s mean over the six task andκ\\kappasettings at thatNN\.![Refer to caption](https://arxiv.org/html/2608.11658v1/fig3_n_sweep.png)Figure 4:Team\-size sweep onBoverlapB\_\{\\mathrm\{overlap\}\}forN=2N=2to55atκ∈\{0,0\.5,1\}\\kappa\\in\\\{0,0\.5,1\\\}, whereκ\\kappais the collision probability and team return is summed over the4040\-step horizon\. Left: team return of independent composition, one curve per team sizeNN\. Right: MA\-USFA \(solid\) and per\-task retraining \(dashed\), one color perNN\. Synchronized composition is omitted for legibility\.
### E\.4Library\-coverage sweep

Table[6](https://arxiv.org/html/2608.11658#A5.T6)and Fig\.[5](https://arxiv.org/html/2608.11658#A5.F5)vary the library content onBoverlapB\_\{\\mathrm\{overlap\}\}\(N=2N=2\), from a single entry to the corner library augmented with the contested joint action\(0,0\)\(0,0\), and show that the value of coverage is regime\-dependent\. The mechanism is that Proposition[1](https://arxiv.org/html/2608.11658#Thmproposition1)assumes the anchor priceψk​\(s,a\)⊤​wtest\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}equals the true value of entrykkunderwtestw\_\{\\mathrm\{test\}\}, which is exact inside the linear feature model but becomes a transfer\-blind estimate once the deployed reward carries a component outside the feature basis\. In the free region \(κ=0\\kappa=0\) adding the contested vertex is pure gain, lifting the synchronized rule from31\.5231\.52to38\.7238\.72, near the joint optimum; in the paid region \(κ=1\.0\\kappa=1\.0\) the same addition locks the team onto the entry the anchor overprices and crashes it to7\.087\.08while the library still contains entries worth31\.2431\.24, a signed gap of−24\.16\-24\.16, and enlarging the library further does not cure it\. The learned composer is immune to library content, returning the same31\.1831\.18across every row of the paid region\.

Table 6:Library\-content sweep \(N=2N=2,BoverlapB\_\{\\mathrm\{overlap\}\}\)\. Team return over4040steps, mean±\\pmstandard deviation over three evaluation seeds\. P4 is the four\-entry corner library; the other rows add or replace entries around the contested joint action\(0,0\)\(0,0\)\.maxk⁡Vk\\max\_\{k\}V^\{k\}is the value of the best available source and the last column is the signed gap of the synchronized rule to it\. The final row averages each method over all library variants and coupling levels\.#### The synchronized anchor must be valid\.

Proposition[1](https://arxiv.org/html/2608.11658#Thmproposition1)assumes thatψk​\(s,a\)⊤​wtest\\psi^\{k\}\(s,a\)^\{\\top\}w\_\{\\mathrm\{test\}\}equals the true value of entrykkunderwtestw\_\{\\mathrm\{test\}\}; inside the linear feature model this is exact\. When the deployed reward contains a component outside the feature basis, the estimate becomes a transfer\-blind anchor that prices only what the features saw during training\. Table[6](https://arxiv.org/html/2608.11658#A5.T6)and Fig\.[5](https://arxiv.org/html/2608.11658#A5.F5)show the consequence: atκ=1\\kappa=1the synchronized rule locks the team onto the contested entry\(0,0\)\(0,0\)and falls to7\.087\.08while the library still contains entries worth31\.2431\.24, a signed gap of−24\.16\-24\.16, and enlarging the library does not cure it, because the contested entry is exactly the one the anchor overprices\. The learned composer is immune to library content \(31\.1831\.18across every row of the paid region\)\.

![Refer to caption](https://arxiv.org/html/2608.11658v1/fig2_k_coverage.png)Figure 5:Library\-content sweep onBoverlapB\_\{\\mathrm\{overlap\}\}\(N=2N=2\)\. Team return \(summed over the4040\-step horizon\) versus transition couplingκ\\kappafor synchronized composition under two libraries, the base four\-entry corner library and the same library with the contested joint entry\(0,0\)\(0,0\)added, compared against MA\-USFA and per\-task retraining\. The dotted horizontal line marks the per\-task joint optimum; the shaded strip atκ=0\\kappa=0marks the factorized regime\.

## Appendix FCity\-Scale Domain: Traffic Signal Control

This appendix reports the traffic\-signal experiment in full, in the same order as the controlled domain: the environment and setup, the main result, and the robustness sweeps\.

### F\.1Setup

#### Network and coupling\.

The experiment runs on a Manhattan grid of28×728\\times 7intersections,196196signal agents, one per intersection\. Road cells are shared between adjacent intersections, so spillback couples the state of each intersection to the decisions of its upstream neighbors: the transition coupling is endogenous, with no free parameter to control, and the factorization condition of Proposition[6](https://arxiv.org/html/2608.11658#Thmproposition6)fails by construction\. The feature model is the project’s composite traffic reward, which is already of the formϕ⊤​w\\phi^\{\\top\}w:ϕ=\[queue,wait,pressure,speed\]norm\\phi=\[\\mathrm\{queue\},\\mathrm\{wait\},\\mathrm\{pressure\},\\mathrm\{speed\}\]\_\{\\mathrm\{norm\}\}, four normalized congestion features, so the composite reward is literally a successor\-feature target and its weight vector is the task\. All four features keep a fixed physical sign \(queue, wait, and pressure are costs, speed is a gain\); a task is a choice of the relative magnitudes on these four terms\.

#### Homogeneous and heterogeneous tasks\.

The two tasks differ only in whether the target weight is shared across the city or varies by intersection\. In the*homogeneous*task every intersection optimizes one shared weight vector, so the196196agents pursue a single common goal\. In the*heterogeneous*task each intersection draws its own weight independently, keeping the fixed signs but sampling the four magnitudes uniformly in\[0\.5,1\.5\]\[0\.5,1\.5\]times their defaults, so different corners of the city weigh queue, waiting, pressure, and speed differently at the same moment; the closed\-form transfer must then serve every node’s ownwwsimultaneously, and the composer can additionally condition on its neighbors’ weights\. The reported metrics are the task return∑iϕi⊤​wi\\sum\_\{i\}\\phi\_\{i\}^\{\\top\}w\_\{i\}, mean travel time over completed trips, throughput \(completed trips\), mean queue, mean waiting time, and mean speed\.

#### Composer\.

The composer is the neighbor\-limited instantiation of Section[4](https://arxiv.org/html/2608.11658#S4): a one\-hop graph attention selector per intersection,ui=ψi⊤​wi\+ρ​tanh⁡\(head⁡\(GATi​\(context\)\)\)u\_\{i\}=\\psi\_\{i\}^\{\\top\}w\_\{i\}\+\\rho\\tanh\(\\mathrm\{head\}\(\\mathrm\{GAT\}\_\{i\}\(\\mathrm\{context\}\)\)\)withρ=4\.0\\rho=4\.0, zero\-initialized so that training starts exactly at the transfer policy, with the feature backbone frozen; global information reaches each decision only through direct neighbors, the strict locality constraint a196196\-agent network imposes, following the neighbor\-limited cooperative pattern of CoLight\([16](https://arxiv.org/html/2608.11658#bib.bib16)\)\. The composer budget is200200episodes, short relative to the toy but expensive per episode at this scale\.

### F\.2Main result

#### Results\.

Table[7](https://arxiv.org/html/2608.11658#A6.T7)reports the full numbers, and the picture is consistent across both task families: 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, whose fine ordering we do not claim\. On the homogeneous task the composer reaches return21652165against20092009\(independent\) and19931993\(synchronized\), throughput518518against368368and356356, and mean waiting6\.606\.60s against10\.3510\.35and11\.9511\.95s; on the heterogeneous task it reaches return16501650against15151515and15271527, throughput483483against337337and352352, and waiting5\.485\.48s against8\.578\.57and8\.508\.50s\. One entry needs reading with care: the composer’s homogeneous travel time \(288\.2288\.2s, the longest in its block\) is a measurement artifact rather than a regression, since travel time is averaged over completed trips and the composer clears roughly150150extra long\-distance trips that the fixed rules leave stranded, which lengthens the mean it is credited with\.

Table 7:Traffic signal control on the Manhattan28×728\\times 7network \(196196intersections\), on the homogeneous and heterogeneous tasks\. Return is the task objective∑iϕi⊤​wi\\sum\_\{i\}\\phi\_\{i\}^\{\\top\}w\_\{i\}summed over the horizon; the remaining columns are physical traffic metrics\. Bold and underline mark the best and second\-best method within each task family\.

### F\.3Robustness sweeps

Two sweeps on the homogeneous task support the headline numbers \(Table[8](https://arxiv.org/html/2608.11658#A6.T8)\)\. The composer already clears both fixed rules after100100fine\-tuning episodes \(return21562156, throughput456456\), and further episodes buy only small refinements \(21652165at200200,21742174at500500\), so the200200\-episode budget used above sits near the plateau rather than being a compute\-heavy outlier\. Enlarging the synchronized rule’s source library from one to five entries does not help it and eventually hurts: return holds at20322032forK∈\{1,2,3\}K\\in\\\{1,2,3\\\}, dips to20282028atK=4K=4, and falls to19931993atK=5K=5, because added specialists rarely become the winning shared anchor and the last, contested entry drags the team down in the coupled regime, the same coverage liability the controlled domain isolates \(Appendix[E](https://arxiv.org/html/2608.11658#A5)\)\. The independent rule \(20092009\) sits between the small and large synchronized libraries, and the composer clears every configuration\.

Table 8:Supplementary traffic sweeps on the homogeneous task\. Top: the MA\-USFA composer as a function of the fine\-tuning budget in episodes\. Bottom: the synchronized rule as a function of source\-library sizeKK, with the independent rule listed for reference\. Columns are as in Table[7](https://arxiv.org/html/2608.11658#A6.T7)

## Appendix GDiscussions

The proposed MA\-USFA sits inside a lineage whose generality we rely on at three points, and this appendix states the facts precisely\. Universal value function approximators condition the value model directly on the goal,V⁡\(s,g\)V\(s,g\), and interpolate across goals by function approximation\([11](https://arxiv.org/html/2608.11658#bib.bib2)\)\. Universal successor feature approximators combine the two ideas in a modelψ~​\(s,a,z,w\)\\tilde\{\\psi\}\(s,a,z,w\)with a policy axiszzand a task axisww:zzindexes the policies in the library, andwwshapes the behavior distribution during training and prices the library at test time through a dot product\([4](https://arxiv.org/html/2608.11658#bib.bib3)\)\. With a single goal as the candidate set, USFA reduces to UVFA; with a finite library it reduces to successor features with generalized policy improvement\. The operating mode we import into a team is the one USFA was designed for: train once over a distribution of objectives, and at deployment evaluate dot products only, with no per\-task adaptation\.

MA\-USFA uses the same machinery per agent\. Agentii’s value modelψ~i\(s,ai∣zi,w−i\)\\tilde\{\\psi\}\_\{i\}\(s,a\_\{i\}\\mid z\_\{i\},w\_\{\-i\}\)keepsziz\_\{i\}as its own policy axis, whose self\-referential TD targetai′=arg⁡maxb​ψ~i​\(s′,b,zi\)⊤​zia^\{\\prime\}\_\{i\}=\\arg\\max\_\{b\}\\tilde\{\\psi\}\_\{i\}\(s^\{\\prime\},b,z\_\{i\}\)^\{\\top\}z\_\{i\}has as its fixed point the optimal policy for the taskziz\_\{i\}; the task axis is carried by the weights, linear in the value, appearing only at test time\. The conditioning on the teammates’ weightsw−iw\_\{\-i\}is the new ingredient: each teammate’s weight indexes a cluster of teammate policies, so the model learns the expected successor features over the teammate behavior distribution rather than a snapshot against one fixed version of the teammates, which is the architectural answer to Requirement[2](https://arxiv.org/html/2608.11658#Thmrequirement2)of Section[3\.3](https://arxiv.org/html/2608.11658#S3.SS3)\. Two structural facts make the reuse exact rather than approximate\. First, when the features are per\-agent additive, the joint successor feature of a synchronized entry decomposes asψjoint,k=∑iψik\\psi^\{\\mathrm\{joint\},k\}=\\sum\_\{i\}\\psi^\{k\}\_\{i\}, so the same network serves both the synchronized anchor and the per\-agent library; the sum is the value the synchronized rule prices\. Second, the composer is initialized at the independent rule with the value layer frozen, and its correction is trained only to raise team value, so on every objective MA\-USFA is at least as good as per\-agent USFA and coincides with it wherever the independent rule is already optimal, without any runtime test\.