Past-Discounting is Key for Learning Markovian Fairness with Long Horizons

Technische Samenvatting: Past-Discounting voor het leren van Markoviaanse rechtvaardigheid met lange horizonten

1. Probleemstelling

Dynamische toewijzing van middelen in multi-agent systemen vereist een balans tussen efficiëntie en rechtvaardigheid over lange tijdshorizonten. Bestaande benaderingen kampen met een fundamenteel dilemma:

• Myope (instantane) rechtvaardigheid: Evalueert rechtvaardigheid uitsluitend op basis van de huidige toewijzingsstap. Hoewel computationeel eenvoudig, negeert dit de historische context, wat leidt tot cumulatieve ongelijkheid over tijd.
• Perfect-Recall rechtvaardigheid: Houdt de volledige som van alle eerdere nutten bij om langetermijngelijkheid te waarborgen. Hoewel theoretisch rechtvaardig, introduceert deze aanpak een kritieke foutmodus: de uitgebreide toestandsruimte die nodig is om cumulatieve nutten bij te houden, groeit onbegrensd met de tijdshorizon. Deze staatsexplosie maakt reinforcement learning (RL) algoritmen computationeel onuitvoerbaar en verhindert convergentie naar rechtvaardige beleidsregels in scenario's met lange horizonten.

De kernuitdaging is het ontwerpen van een geheugenmechanisme dat de Markov-eigenschap behoudt (waardoor leerbare processen handelbaar blijven) terwijl het een begrensde, horizon-onafhankelijke toestandsruimte behoudt, zonder het vermogen om over historische ongelijkheden te redeneren op te offeren.

2. Methodologie

De auteurs stellen Past-Discounted Fairness voor, een framework geïnspireerd door gedragseconomie en morele psychologie, die stellen dat menselijke oordelen over rechtvaardigheid van nature verre gebeurtenissen minder zwaar laten wegen (discounten). De methodologie bestaat uit drie belangrijke componenten:

A. Discounted-Recall Geheugenmechanismen
In plaats van alle eerdere nutten op te tellen ($Z_t = \sum u_\tau$), past het framework een aanpasbare discountfactor $\gamma_p \in [0, 1]$ toe op historische nutten. Twee specifieke formuleringen worden gedefinieerd:

1. Additive Discounted Recall: De geheenstoestand wordt bijgewerkt als $Z_t = \gamma_p Z_{t-1} + u_t$. Hierbij reduceert $\gamma_p=0$ tot instantane rechtvaardigheid, en $\gamma_p=1$ herstelt perfect recall.
2. Averaged Discounted Recall: Zowel de geaccumuleerde nutswaarde als de effectieve tijdsdenominator worden gediscount, waardoor de geheenstoestand begrensd blijft, zelfs wanneer er gemiddelden worden gevormd.

B. Theoretische Analyse van de Toestandsruimte
Het artikel biedt rigoureuze bewijzen die de eigenschappen van de toestandsruimte van verschillende paradigma's vergelijken:

• Perfect Recall (Additive): Stelling 3 bewijst dat de toestandsruimte lineair groeit met de tijdshorizon $t$ per coördinaat en exponentieel met het aantal agenten $n$. Dit leidt tot een onbegrensde toestandsruimte, waardoor vaste resolutie discretisering onmogelijk is voor lange horizonten.
• Perfect Recall (Averaged): Stelling 5 laat zien dat hoewel de gemiddelde nutswaarde begrensd is, het behouden van de Markov-eigenschap vereist dat de tijdindex $t$ (of een equivalente denominator) als onderdeel van de toestand wordt meegevoerd, wat nog steeds onbegrensd is.
• Past-Discounted (Additive & Averaged): Stellingen 4 en 6 bewijzen dat met $\gamma_p < 1$, de geheenstoestand $Z_t$ uniform begrensd is door $u_{max} / (1 - \gamma_p)$. Cruciaal is dat de grootte van de uitgebreide toestandsruimte onafhankelijk wordt van de tijdshorizon, wat voldoet aan de voorwaarden voor handelbare leerprocessen.

C. Connectie met Regeltechniek
De auteurs breiden de analyse uit door het rechtvaardigheidsgeheugen te modelleren als een Lineair Tijd-Invariant (LTI) systeem. Ze demonstreren dat voor de geheenstoestand begrensd te blijven, de spectrale radius van de geheen-transitiematrix kleiner dan één moet zijn ($\rho(A) < 1$). Perfect recall komt overeen met een identiteitsmatrix ($\rho=1$), wat instabiel is, terwijl past-discounting overeenkomt met een geschaalde identiteitsmatrix ($\rho = \gamma_p < 1$), wat stabiliteit garandeert.

D. Half-life en Effectieve Window
Om beoefenaars te helpen bij het selecteren van $\gamma_p$, introduceert het artikel het concept van "half-life" ($t_{1/2}$) en "effective window" ($W_{eff} = 1/(1-\gamma_p)$). Deze metrieken kwantificeren hoeveel eerdere stappen betekenisvol invloed uitoefenen op de huidige rechtvaardigheidsevaluatie, waardoor een gefundeerde afweging kan worden gemaakt tussen de diepte van het geheugen en de computationele haalbaarheid.

3. Experimentele Resultaten

De auteurs valideren hun theorie empirisch met behulp van een Multi-Agent Reinforcement Learning (MARL) setup met een Proximal Policy Optimization (PPO) agent in een dynamische omgeving voor de toewijzing van middelen (10 agenten, 2 middelen per stap).

• Setup: Agenten werden getraind over variërende horizonten ($T=100$ tot $T=10.000$) onder drie geheugenconfiguraties: Myopic ($\gamma_p=0$), Perfect-Recall ($\gamma_p=1$), en Past-Discounted ($\gamma_p \in \{0.9, 0.99, 0.999\}$).
• Bevindingen:
  • Myope Agenten: Faalden in het aanleren van rechtvaardige beleidsregels, wat resulteerde in een hoge ongelijkheid (hoge Gini-coëfficiënt) door het gebrek aan historische context.
  • Perfect-Recall Agenten: Presteerden goed op korte horizonten ($T \le 500$), maar leden onder een catastrofale prestatie-instorting naarmate de horizon toenam. Bij $T=10.000$ degradeerde hun vermogen om rechtvaardigheid te handhaven tot het niveau van myope agenten, wat de theoretische voorspelling van staatsexplosie die convergentie hindert, bevestigt.
  • Past-Discounted Agenten: Leerden succesvol robuuste rechtvaardige beleidsregels over alle horizonten. De begrensde toestandsrepresentatie maakte het mogelijk voor het PPO-algoritme om te convergeren.
  • Parametergevoeligheid: De optimale $\gamma_p$ hing af van de dichtheid van het rechtvaardigheidssignaal. Voor dichte signalen (Nash Welfare) volstond een korter geheugen ($\gamma_p=0.9$). Voor ijle signalen (Egalitarian Welfare) was een langer geheugen ($\gamma_p=0.99$) vereist om voldoende informatie te accumuleren.

4. Belangrijkste Bijdragen

1. Identificatie van een Foutmodus: Het artikel identificeert en bewijst formeel dat perfect-recall rechtvaardigheid zorgt voor onbegrensde groei van de toestandsruimte, waardoor leren over lange horizonten onuitvoerbaar wordt.
2. Nieuw Framework: Het stelt Past-Discounted Fairness voor, een gedragsmatig onderbouwd framework dat tussen instantane en perfect-recall rechtvaardigheid staat via een geometrisch afnemend gewicht.
3. Theoretische Garanties: Het biedt bewijzen dat past-discounting een begrensde, horizon-onafhankelijke uitgebreide toestandsruimte garandeert, waardoor de Markov-eigenschap wordt hersteld en computationele handelbaarheid wordt gewaarborgd.
4. Empirische Validatie: Het demonstreert dat RL-agenten die gebruikmaken van past-discounting rechtvaardige beleidsregels kunnen leren over willekeurig lange horizonten, terwijl agenten met perfect recall falen naarmate de horizon zich uitstrekt.

5. Betekenis en Claims

Het artikel claimt dat past-discounting niet louter een heuristiek is, maar een praktische noodzaak voor het bouwen van schaalbare en rechtvaardige systemen voor de toewijzing van middelen. Door te garanderen dat de toestandsruimte begrensd en horizon-onafhankelijk blijft, ontsluit het framework de mogelijkheid om rechtvaardige beleidsregels handelbaar te leren in scenario's met lange horizonten waar traditionele perfect-recall methoden falen.

De auteurs positioneren dit werk als een "derde paradigma" dat het praktische middenveld inneemt tussen de computationele eenvoud van myope rechtvaardigheid en de theoretische gelijkheid (maar computationele onhaalbaarheid) van perfect recall. De betekenis ligt in het bieden van een principieel mechanisme om de afweging tussen directe uitkomsten en historische context te beheren, gegrond in zowel gedragskundige inzichten als rigoureuze regeltechnische stabiliteitscondities.