Technische Samenvatting: $\alpha$-fair Heterogene Agent Reinforcement Learning

Probleemstelling

In Multi-Agent Reinforcement Learning (MARL) wordt samenwerking traditioneel geoptimaliseerd via utilitaire doelstellingen die de som van de nutten van alle agenten maximaliseren. Hoewel dit efficiënt is, verwaarloost deze aanpak vaak de verdeling van beloningen, wat leidt tot onrechtvaardige "leider-volger"-dynamieken waarbij een subset van agenten gemarginaliseerd wordt. Bestaande pogingen om rechtvaardigheid te integreren in MARL vallen over het algemeen in drie categorieën: beloningsvorming (bijv. ongelijkheidsaversie), rechtvaardigheidsbeperkingen en sociale welzijnsdoelstellingen. Deze methoden lijden echter aan kritieke beperkingen:

1. Stationariteitsvraagstukken: Methoden voor beloningsvorming vertrouwen vaak op geschiedenisafhankelijke beloningen, wat de stationaire eigenschap van Markov-spelen doorbreekt.
2. Gebrek aan Theoretische Garanties: Populaire algoritmen zoals Independent PPO (IPPO) of Multi-Agent PPO (MAPPO, zelfs wanneer ze zijn aangepast voor rechtvaardigheid, missen de strikte theoretische convergentiegaranties die worden gevonden in single-agent Trust Region Learning (TRL).
3. Generalisatie en Interpreteerbaarheid: Op beperkingen gebaseerde methoden zijn vaak domeinspecifiek, terwijl sociale welzijnsdoelstellingen (zoals $\alpha$-fairness) vaak vertrouwen op geëxtrapoleerde PPO-doelstellingen zonder theoretische waarborgen of vertrouwen op geïdealiseerde aannames (bijv. convexiteit).

Er bestaat een kloof tussen rechtvaardige doelstellingen en theoretisch veilige leerkaders. Dit artikel beoogt deze kloof te overbruggen door een framework te introduceren dat monotone verbetering en convergentie naar Nash-evenwichten waarborgt terwijl het optimaliseert voor $\alpha$-fairness.

Methodologie

Theoretisch Kader: $\alpha$-fair HATRL

De auteurs stellen een nieuw framework voor dat $\alpha$-fairness combineert met Heterogeneous-Agent Trust Region Learning (HATRL).

1. Globale Rechtvaardige Doelstelling:
   Het framework definieert een globale doelstellingfunctie $J(\vec{\pi})$ voor een volledig coöperatieve setting:
   $$J(\vec{\pi}) = \mathbb{E}_{s_0 \sim \rho_0} \left[ \sum_{i=1}^n U_\alpha(\nu + V_i^{\vec{\pi}}(s_0)) \right]$$
   waarbij $U_\alpha$ de $\alpha$-fair nutfunctie is, $\nu$ een positieve constante is die positiviteit waarborgt, en $V_i^{\vec{\pi}}$ de waardefunctie voor agent $i$ is.

   • Wanneer $\alpha \to 0$, nadert de doelstelling de utilitaire som.
   • Wanneer $\alpha \to +\infty$, nadert het de Rawlsiaanse welvaartsfunctie (max-min).
   • Bij $\alpha = 1$ komt het overeen met proportionele rechtvaardigheid.

2. Rechtvaardige Voordeelfunctie (Fair Advantage Function):
   Om HATRL aan te passen, introduceren de auteurs een rechtvaardige voordeelfunctie $A_F^{\vec{\pi}}(s, \vec{a})$. In tegen tegenstelling tot standaard multi-agent voordeelfuncties, is dit een gewogen som van de individuele voordeelfuncties van agenten, waarbij gewichten dynamisch worden bepaald door de inverse van de verwachte rendementen van de agenten ($1/V_j^{\vec{\pi}}(s)$). Deze weging zorgt ervoor dat agenten met hogere verwachte rendementen minder bijdragen aan de gradiëntupdate, waardoor er ruimte ontstaat voor minder presterende agenten om te verbeteren.

3. Sequentiële Update en Surrogaatfunctie:
   Bouwend op HATRL leiden de auteurs een surrogaatfunctie $L_{\vec{\pi}}(\vec{\pi}')$ af die dient als een ondergrens voor de verbetering van de globale rechtvaardige doelstelling. Ze bewijzen dat het verschil $J(\vec{\pi}') - J(\vec{\pi})$ begrensd wordt door deze surrogaatfunctie minus een KL-divergentie strafterm.
   Cruciaal is dat zij aantonen dat de surrogaatfunctie kan worden gedecomposeerd in $n$ geordende termen. Dit maakt een sequentieel update-schema mogelijk waarbij agenten hun beleid één voor één updaten (in een willekeurige permutatie), waarbij zij hun lokale bijdrage aan de globale rechtvaardige doelstelling maximaliseren terwijl zij de trust region-beperking respecteren.

4. Theoretische Garanties:
   Het artikel biedt bewijzen voor:

   • Monotone Verbetering: De globale rechtvaardige doelstelling $J(\vec{\pi})$ is gegarandeerd dat elke iteratie toeneemt (of gelijk blijft).
   • Convergentie: De reeks gezamenlijke beleidsregels convergeert naar een limietpunt.
   • Nash-evenwicht: De verzameling limietpunten is niet-leeg, en elk limietpunt vormt een Nash-evenwicht voor het volledig coöperatieve spel.

Praktische Algoritmen

Om dit framework te implementeren in hoogdimensionale ruimtes, ontwikkelen de auteurs twee deep reinforcement learning algoritmen:

1. $\alpha$-fair HATRPO: Een uitbreiding van Heterogeneous-Agent Trust Region Policy Optimization. Het vervangt de standaard multi-agent voordeelfunctie door de rechtvaardige voordeelfunctie en lost het beperkte optimalisatieprobleem op met behulp van een KL-constraint en conjugate gradient updates.
2. $\alpha$-fair HAPPO: Een uitbreiding van Heterogeneous-Agent PPO. Het gebruikt een eerste-orde benadering met een clipping-mechanisme om de berekening van de Hessiaan te vermijden, wat het computationeel efficiënter maakt terwijl de sequentiële update-structuur behouden blijft.

Belangrijkste Bijdragen

1. Theoretische Brug: Het artikel introduceert een theoretisch gefundeerd framework dat $\alpha$-fairness integreert in Heterogeneous-Agent Trust Region Learning, wat wiskundige veiligheid (monotone verbetering en convergentiegaranties) biedt voor het leren van pro-sociale gedragingen.
2. Nieuwe Surrogaatfunctie: De definitie van een rechtvaardige voordeelfunctie die de nutten van agenten dynamisch weegt op basis van verwachte rendementen, wat de transitie mogelijk maakt van utilitaire efficiëntie naar $\alpha$-fairness welvaart.
3. Algoritmeontwikkeling: De voorstel van twee praktische algoritmen, $\alpha$-fair HATRPO en $\alpha$-fair HAPPO, die het theoretische framework uitbreiden naar parametrische beleidsinstellingen.
4. Empirische Validatie: Demonstratie dat deze algoritmen hogere sociale uitkomsten (lagere Gini-indices) bereiken terwijl ze de utilitaire efficiëntie evenaren of overtreffen vergeleken met baselines in sequentiële sociale dilemma's.

Experimentele Resultaten

De algoritmen werden geëvalueerd op twee Sequential Social Dilemma (SSD) omgevingen uit de SocialJax-suite: CleanUp en CommonHarvest.

• Baselines: De voorgestelde methoden werden vergeleken met standaard HATRPO/HAPPO (utilitair) en FMAPPO (een PPO-gebaseerde methode die proportionele rechtvaardigheid gebruikt zonder theoretische garanties).
• Metrieken: Prestaties werden gemeten in Total Apples Consumed (TAC) voor efficiëntie en de Gini-index voor rechtvaardigheid.
• Bevindingen:
  • Rechtvaardigheid: Het verhogen van de parameter $\alpha$ leidde over het algemeen tot rechtvaardigere uitkomsten (lagere Gini-indices). De voorgestelde $\alpha$-fair algoritmen behaalden significant lagere Gini-indices dan de utilitaire baselines.
  • Efficiëntie: In de CommonHarvest-omgeving presteerden $\alpha$-fair HATRPO en HAPPO iets beter dan de utilitaire baselines in termen van TAC, terwijl ze betere rechtvaardigheid bereikten. In CleanUp was het efficiëntievoordeel minimaal, en FMAPPO presteerde soms beter dan de voorgestelde methoden in pure efficiëntie, hoewel de voorgestelde methoden nog steeds sociaal superieure resultaten (lagere Gini) behaalden.
  • Vergelijking met FMAPPO: Hoewel FMAPPO goed presteerde, boden de voorgestelde methoden een theoretisch veiliger alternatief met vergelijkbare of betere rechtvaardigheidsuitkomsten.

Betekenis en Beperkingen

Betekenis:
Het artikel beweert een "wiskundig veilige basis" te hebben gelegd voor het trainen van agenten om duurzame, pro-sociale gedragingen aan te nemen. Door monotone verbetering en convergentie naar Nash-evenwichten te garanderen, adresseert het framework het gebrek aan theoretische garanties in bestaande rechtvaardige MARL-benaderingen. Het vult succesvol de kloof tussen rechtvaardige doelstellingen en veilige leerkaders.

Beperkingen:
De auteurs erkennen verschillende beperkingen:

1. Hyperparametergevoeligheid: Hoge waarden van $\alpha$ ($\alpha > 1$) kunnen leiden tot prestatievermindering en instabiliteit tijdens de training. Dit wordt toegeschreven aan het feit dat de rechtvaardige voordeelfunctie de gewichten van hoogpresterende agenten vermindert, waardoor de globale doelstelling overmatig gevoelig wordt voor de "slechtste leerlingen" die in lokale optima kunnen vast komen te zitten.
2. Theoretische Beperkingen: Het framework steunt op de aanname van positieve, begrensde beloningen, wat de toepasbaarheid in bepaalde omgevingen beperkt.
3. Observabiliteit: De algoritmen vereisen volledig observeerbare staten. In real-world scenario's met partiële observabiliteit zouden benaderingen (bijv. via RNN's) noodzakelijk zijn, maar deze zouden de huidige theoretische garanties missen.

Het artikel concludeert door toekomstig werk voor te stellen op het gebied van mechanismen om exploratie te verbeteren (bijv. entropie-normalisatie) of adaptieve beperkingen om het leren te stabiliseren wanneer $\alpha$ hoog is.