🤖 machine learning

CAPO: Counterfactual Credit Assignment in Sequential Cooperative Teams

Dit paper introduceert CAPO, een critic-vrije policy-gradient-algoritme dat gebruikmaakt van de Sequential Aristocrat Utility om credit assignment in sequentiële coöperatieve teams te optimaliseren door per-agent beloningen te decomponeren zonder extra omgevingsooproepen.

Oorspronkelijke auteurs: Shripad Deshmukh, Jayakumar Subramanian, Raghavendra Addanki, Nikos Vlassis

Gepubliceerd 2026-04-21

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Shripad Deshmukh, Jayakumar Subramanian, Raghavendra Addanki, Nikos Vlassis

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een reusachtig, goed georganiseerd team hebt dat samenwerkt aan één grote taak. Denk aan een groepje mensen die een complex recept maken, of een team van AI's die samen een verhaal schrijven.

In dit team werken ze niet tegelijk, maar achter elkaar:

De eerste persoon doet een stap.
De tweede persoon kijkt wat de eerste heeft gedaan en doet zijn stap.
De derde kijkt naar de eerste twee, enzovoort.

Aan het einde krijgen ze één enkele prijs (of straf) voor het hele team. Maar hier zit het probleem: Wie heeft nu precies de prijs verdiend?

Was het de eerste persoon die een goede basis legde?
Was het de tweede die een foutje herstelde?
Of was het de laatste die alles perfect afmaakte?

Dit noemen onderzoekers krediettoewijzing (credit assignment). Het is als proberen te raden wie de beste bakker was in een team dat samen een taart bakte, terwijl je alleen de smaak van de hele taart proeft.

Het oude probleem: Chaos en gokken

In het verleden hadden teams twee manieren om dit op te lossen, maar beide hadden grote nadelen:

De "Alwetende Ouder" (Centrale Critic): Je bouwt een supercomputer die precies weet wat iedereen had moeten doen. Maar naarmate het team groter wordt, wordt deze computer zo complex dat hij het niet meer redt (hij "explodeert" in complexiteit).
Het "Gokken met IS" (Importance Sampling): Je probeert te rekenen wat er zou zijn gebeurd als iemand anders had gehandeld, door oude data te herschalen. Maar als het team groot is, worden deze berekeningen zo onbetrouwbaar dat de resultaten volledig uit de hand lopen (de variance wordt exponentieel).

Bovendien is er een extra twist: als je het team één voor één bijstelt (eerst persoon 1, dan persoon 2, etc.), verandert de situatie voor de volgende persoon. De data die je hebt verzameld is dan al "oud" en past niet meer bij de nieuwe situatie. Het is alsof je een recept aanpast terwijl je al aan het bakken bent, en je probeert te raden hoe de oude bakker het had gedaan.

De oplossing: CAPO (De Slimme Rekenaar)

De auteurs van dit paper hebben een nieuwe methode bedacht genaamd CAPO. Ze noemen het de "Counterfactual Advantage Policy Optimization". Laten we het uitleggen met een analogie:

Stel je voor dat je een rekenmachine hebt die het teamrecept in stukjes kan opbreken.

1. De "Aristocraat" (De eerlijke score)

De auteurs hebben een nieuwe manier bedacht om te berekenen wat ieders bijdrage was. Ze noemen dit de Sequential Aristocrat Utility.

Hoe werkt het? Ze kijken naar het teamresultaat en trekken daar een "verwachte gemiddelde" van af.
De analogie: Stel je voor dat je een taart bakt. De prijs is €100. De "Aristocraat" zegt: "Oké, als we dit recept gemiddeld nemen, krijgen we meestal €80. De extra €20 die we vandaag kregen, komt waarschijnlijk door de specifieke keuzes die we vandaag maakten."
Ze doen dit voor elke persoon in het team, rekening houdend met wat de mensen voor hen hebben gedaan. Dit zorgt ervoor dat elke persoon een eerlijke, schone score krijgt, zonder ruis van de anderen.

2. De "Twee Delen" Strategie (Direct en Indirect)

CAPO splitst de bijdrage van een persoon in twee delen:

Het Directe Effect: "Hoeveel beter werd de taart door mijn specifieke keuze?" (Dit is makkelijk te berekenen).
Het Indirecte Effect: "Hoeveel beter werd de taart omdat mijn keuze de volgende persoon in het team hielp om een betere keuze te maken?"
- Voorbeeld: Als jij deeg goed kneedt, kan de volgende persoon het makkelijker uitrollen. Jij krijgt credit voor je kneedwerk, maar ook voor het feit dat je de volgende persoon hielp.

3. De "Fictieve Simulatie" (Zonder extra kosten)

Dit is het slimste deel. Om het "Indirecte Effect" te meten, hoeven ze niet echt te gaan bakken (wat tijd en geld kost).

In plaats daarvan laten ze de AI dromen (fictieve sampling). Ze zeggen: "Stel dat persoon 2 iets anders had gedaan, hoe zou persoon 3 dan hebben gereageerd?"
Ze doen dit door de huidige strategie van het team te gebruiken om nieuwe, denkbeeldige scenario's te genereren.
Het voordeel: Ze hoeven geen extra proefbakkers in te huren (geen extra omgevingstests) en ze hoeven geen ingewikkelde statistische correcties te doen die de resultaten verstoren. Het is alsof je een simulatie draait op je computer in plaats van een nieuw restaurant te openen.

Waarom is dit geweldig?

Het werkt voor grote teams: Terwijl andere methoden falen als het team groter wordt (de berekeningen worden te chaotisch), blijft CAPO stabiel. Hoe groter het team, hoe beter het werkt ten opzichte van de oude methoden.
Het is eerlijk: Het geeft elke persoon de juiste credit, zelfs als ze achter elkaar werken en de situatie voortdurend verandert.
Het is snel en goedkoop: Het kost geen extra tijd om de echte wereld te testen; het doet al het zware rekenwerk met slimme wiskunde en simulaties.

Samenvatting in één zin

CAPO is een slimme methode om in een team dat achter elkaar werkt, precies te berekenen wie wat heeft bijgedragen aan het succes, zonder dat je duizenden extra proefrondes hoeft te doen, door gebruik te maken van slimme simulaties en eerlijke wiskunde.

Dit is vooral handig voor moderne AI-systemen (zoals grote taalmodellen die samenwerken), waar het belangrijk is om te weten welke AI-component precies de juiste beslissing nam.

Probleemstelling

In coöperatieve multi-agent systemen waar agenten in een vaste volgorde handelen en slechts één gedeelde teambeloning ontvangen, is het moeilijk om bij te dragen (credit assignment) aan individuele agenten. Dit probleem wordt verergerd in settings waar agenten sequentieel worden bijgewerkt (één voor één binnen een trainingsbatch).

De kernuitdagingen zijn:

Credit Assignment: Het toewijzen van een gezamenlijke beloning aan individuele acties is onderbepaald.
Niet-stationariteit: Wanneer een upstream-agent (een agent die eerder in de volgorde zit) wordt bijgewerkt, verandert de verdeling van het gedrag van downstream-agenten. Data die eerder is verzameld onder het oude beleid is dus "off-policy" voor de latere updates binnen dezelfde batch.
Bestaande beperkingen:
- Gecentraliseerde critics (zoals COMA) hebben een exponentiële complexiteit in de teamgrootte.
- Cumulatieve importance sampling (zoals HAPPO/HA-GRPO) leidt tot een variantie die exponentieel groeit met het aantal reeds bijgewerkte agenten.
- Replay-methode (zoals C3) vereist dure heruitvoeringen van de omgeving voor elke contrafactuele schatting.

Methodologie

De auteurs introduceren CAPO (Counterfactual Advantage Policy Optimization), een critic-vrij algoritme dat gebaseerd is op een nieuwe theoretische uitbreiding.

1. Sequential Aristocrat Utility (SeqAU)

De auteurs breiden het werk van Wolpert en Tumer (2002) uit van gelijktijdige naar sequentiële teams. Ze definiëren SeqAU als het unieke per-agent leersignaal dat de "leerbaarheid" (learnability) maximaliseert.

Definitie: $U_k^{SeqAU}(a) = R(a) - D^*(a_{<k})$ , waarbij $D^*$ de verwachte teambeloning is onder het huidige beleid, gegeven alleen de prefix van acties $a_{<k}$ .
Voordeel: Dit is de enige baseline die de variatie in het signaal minimaliseert door de "ruis" van teamgenoten te elimineren, zonder structurele aannames over de beloningsfunctie.

2. De CAPO Algoritme Stappen

Om de SeqAU praktisch toepasbaar te maken zonder dure critics of heruitvoeringen, gebruikt CAPO drie kerncomponenten:

A. Additieve Beloningsdecompositie (Ridge Regression):
In plaats van een gecentraliseerde critic te leren, wordt de verwachte teambeloning gemodelleerd als een som van per-agent componenten: $f(a) = \sum \phi_k(a_k)$ .
- De parameters $\phi_k$ worden geschat via een ridge-regressie op de verzamelde batch data.
- Dit maakt het mogelijk om per-agent bijdragen in gesloten vorm te berekenen zonder gradienten voor een critic.
B. Upstream-Cancellatie:
Door de additieve structuur en de autoregressieve factorisatie van het beleid, blijken termen van upstream-agenten in de contrafactuele vergelijking exact te cancelen.
- Het voordeel ( $\hat{A}_k$ $\hat{A}_{k}$ ) reduceert tot twee delen:
  1. Direct Effect: De directe bijdrage van agent $k$ (geschat via de regressie).
  2. Indirect Effect: Hoe de actie van agent $k$ de verdeling van downstream-agenten beïnvloedt.
C. Fictitious Sampling (Voor het Indirecte Effect):
Om het indirecte effect te schatten zonder de omgeving opnieuw aan te roepen, trekt CAPO fictieve continuaties (counterfactuals) uit het huidige gezamenlijke beleid $\pi^{(k-1)}$ .
- Voor elke rollout worden downstream-acties gesimuleerd onder het nieuwe beleid.
- Dit vermijdt de exponentiële variantie van importance sampling (IS) en de kosten van echte omgevingsreplays.

Belangrijkste Bijdragen

Theoretisch Kader (SeqAU): Bewijs dat de prefix-afhankelijke baseline $E[R|a_{<k}]$ uniek is voor het maximaliseren van leerbaarheid in sequentiële teams (Stelling 1).
CAPO Algoritme: Een critic-vrij, policy-gradient algoritme dat per-agent voordelen schat via regressie en fictieve sampling.
Analytische Bounds:
- Bias: Lineair in de residual van de additiviteits-aanname.
- Variantie: Past zich aan aan de koppeling tussen agenten. In het geval van gefactoreerde beleidsplannen is de variantie onafhankelijk van de teamgrootte ( $K$ ). In het slechtste geval is het $O(K-k)$ , wat veel beter is dan de $\Theta(K)$ van gedeelde baselines of $O(\exp K)$ van cumulatieve IS-methoden.
Geen Importance Sampling Ratio Inflatie: De gradient MSE heeft geen inflatie door IS-ratio's, wat stabiliteit garandeert bij grote teams.

Resultaten

De auteurs valideren hun theorie op een gecontroleerde sequentiële bandit-testomgeving:

Schatting van Kwaliteit: De Mean Squared Error (MSE) van CAPO's voordeelsschatting blijft vlak naarmate de teamgrootte ( $K$ ) toeneemt. In tegenstelling hiermee neemt de MSE van MA-GRPO lineair toe en die van HA-GRPO sneller dan lineair.
Robuustheid: CAPO presteert goed zelfs bij niet-additieve beloningen (interacties tussen agenten), hoewel de bias toeneemt met de sterkte van de interactie, zoals voorspeld door de theorie.
End-to-End Optimalisatie: In vergelijking met baselines (MA-GRPO, HA-GRPO, C3):
- Bij kleine teams ( $K=2$ ) presteren simpele methoden goed.
- Bij grotere teams ( $K \geq 6$ ) overtreft CAPO alle andere methoden aanzienlijk in termen van regret.
- HA-GRPO degradeert snel door de cumulatieve IS-variantie.
- C3 presteert slecht door de hoge kosten van heruitvoering (replay).
Ablatie-studie: Een versie zonder het "indirecte effect" (alleen direct effect) werkt goed bij lage niet-stationariteit, maar faalt bij hoge niet-stationariteit. Dit bevestigt dat het fictieve sampling van het indirecte effect essentieel is voor sequentiële updates.

Significantie

CAPO biedt een schaalbaar en theoretisch onderbouwd alternatief voor credit assignment in coöperatieve multi-agent systemen, specifiek gericht op sequentiële pipelines (zoals die vaak voorkomen bij Large Language Models en tool-using agents).

Efficiëntie: Het elimineert de noodzaak voor dure gecentraliseerde critics of omgevingsreplays.
Stabiliteit: Het voorkomt de exponentiële variantie-explosie die optreedt bij sequentiële updates met importance sampling.
Toepasbaarheid: Het kader is direct toepasbaar op moderne multi-LLM pipelines waar agenten sequentieel werken en een gezamenlijk resultaat produceren, een domein waar eerdere methoden vaak tekortschoten.

Kortom, CAPO lost het fundamentele probleem van "off-policy drift" in sequentiële coöperatieve teams op door een slimme combinatie van regressie en contrafactuele simulatie binnen het huidige beleid.