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

Sintesi Tecnica: Sconto del Passato per l'Apprendimento della Equità Markoviana con Orizzonti Lunghi

1. Definizione del Problema

L'allocazione dinamica delle risorse nei sistemi multi-agente richiede un equilibrio tra efficienza ed equità su orizzonti temporali lunghi. Gli approcci esistenti affrontano un dilemma fondamentale:

• Equità Miopica (Istantanea): Valuta l'equità basandosi esclusivamente sul passo di allocazione corrente. Sebbene sia computazionalmente semplice, ignora il contesto storico, portando a iniquità cumulative nel tempo.
• Equità con Memoria Perfetta (Perfect-Recall): Monitora la somma completa di tutte le utilità passate per garantire l'equità a lungo termine. Sebbene sia teoricamente equo, questo approccio introduce un modo critico di fallimento: lo spazio degli stati aumentato, necessario per tracciare le utilità cumulative, cresce in modo illimitato con l'orizzonte temporale. Questa esplosione dello stato rende gli algoriti di apprendimento per rinforzo (RL) computazionalmente intrattabili e impedisce la convergenza verso politiche eque in contesti con orizzonti lunghi.

La sfida centrale consiste nel progettare un meccanismo di memoria che preservi la proprietà di Markov (permettendo un apprendimento trattabile) mantenendo al contempo uno spazio di stato limitato e indipendente dall'orizzonte, senza sacrificare la capacità di ragionare sulle disuguaglianze storiche.

2. Metodologia

Gli autori propongono la Equità con Sconto del Passato (Past-Discounted Fairness), un framework ispirato all'economia comportamentale e alla psicologia morale, i quali postulano che i giudizi umani sull'equità scostino naturalmente gli eventi distanti. La metodologia prevede tre componenti chiave:

A. Meccanismi di Memoria con Sconto del Richiamo (Discounted-Recall)
Invece di sommare tutte le utilità passate ($Z_t = \sum u_\tau$), il framework applica un fattore di sconto regolabile $\gamma_p \in [0, 1]$ alle utilità storiche. Sono definite due formulazioni specifiche:

1. Richiamo Additivo con Sconto (Additive Discounted Recall): Lo stato della memoria viene aggiornato come $Z_t = \gamma_p Z_{t-1} + u_t$. Qui, $\gamma_p=0$ si riduce all'equità istantanea, mentre $\gamma_p=1$ recupera la memoria perfetta.
2. Richiamo con Sconto Mediato (Averaged Discounted Recall): Sia l'utilità accumulata che il denominatore temporale effettivo vengono scontati, garantendo che lo stato della memoria rimanga limitato anche durante la media.

B. Analisi Teorica dello Spazio degli Stati
Il documento fornisce prove rigorose confrontando le proprietà dello spazio degli stati di diversi paradigmi:

• Memoria Perfetta (Additiva): Il Teorema 3 dimostra che lo spazio degli stati cresce linearmente con l'orizzonte temporale $t$ per coordinata ed esponenzialmente con il numero di agenti $n$. Ciò porta a uno spazio degli stati illimitato, rendendo impossibile la discretizzazione a risoluzione fissa per orizzonti lunghi.
• Memoria Perfetta (Mediata): Il Teorema 5 mostra che, sebbene il valore dell'utilità media sia limitato, mantenere la proprietà di Markov richiede l'inserimento dell'indice temporale $t$ (o un denominatore equivalente) come parte dello stato, il quale è comunque illimitato.
• Equità con Sconto del Passato (Additiva e Mediata): I Teoremi 4 e 6 dimostrano che con $\gamma_p < 1$, lo stato della memoria $Z_t$ è uniformemente limitato da $u_{max} / (1 - \gamma_p)$. Fondamentalmente, la dimensione dello spazio degli stati aumentato diventa indipendente dall'orizzonte temporale, soddisfacendo le condizioni per un apprendimento trattabile.

C. Connessione con la Teoria del Controllo
Gli autori estendono l'analisi modellando la memoria dell'equità come un sistema Lineare Tempo-Invariante (LTI). Dimostrano che, affinché lo stato della memoria rimanga limitato, il raggio spettrale della matrice di transizione della memoria deve essere minore di uno ($\rho(A) < 1$). La memoria perfetta corrisponde a una matrice identità ($\rho=1$), che è instabile, mentre lo sconto del passato corrisponde a una identità scalata ($\rho = \gamma_p < 1$), garantendo la stabilità.

D. Emivita e Finestra Effettiva
Per aiutare i professionisti nella selezione di $\gamma_p$, il documento introduce il concetto di "emivita" ($t_{1/2}$) e "finestra effettiva" ($W_{eff} = 1/(1-\gamma_p)$). Questi parametri quantificano quanti passi passati influenzano significativamente la valutazione attuale dell'equità, permettendo un compromesso fondato tra profondità della memoria e fattibilità computazionale.

3. Risultati Sperimentali

Gli autori validano empiricamente la loro teoria utilizzando una configurazione di Multi-Agent Reinforcement Learning (MARL) con un agente PPO (Proximal Policy Optimization) in un ambiente di allocazione dinamica delle risorse (10 agenti, 2 risorse per step).

• Configurazione: Gli agenti sono stati addestrati su diversi orizzonti ($T=100$ a $T=10.000$) sotto tre configurazioni di memoria: Miopica ($\gamma_p=0$), Memoria Perfetta ($\gamma_p=1$) e Sconto del Passato ($\gamma_p \in \{0.9, 0.99, 0.999\}$).
• Risultati:
  • Agenti Miopici: Non sono riusciti ad apprendere politiche eque, risultando in un'alta iniquità (alto coefficiente di Gini) a causa della mancanza di contesto storico.
  • Agenti con Memoria Perfetta: Hanno performato bene su orizzonti brevi ($T \le 500$), ma hanno subito un collasso catastrofico delle prestazioni all'aumentare dell'orizzonte. A $T=10.000$, la loro capacità di mantenere l'equità è degradata al livello degli agenti miopici, confermando la previsione teorica dell'esplosione dello spazio degli stati che ostacola la convergenza.
  • Agenti con Sconto del Passato: Hanno appreso con successo politiche eque robuste attraverso tutti gli orizzonti. La rappresentazione limitata dello stato ha permesso all'algoritmo PPO di convergere.
  • Sensibilità ai Parametri: Il $\gamma_p$ ottimale dipendeva dalla densità del segnale di equità. Per segnali densi (Benessere di Nash), una memoria più breve ($\gamma_p=0.9$) era sufficiente. Per segnali sparsi (Benessere Egualitario), era necessaria una memoria più lunga ($\gamma_p=0.99$) per accumulare informazioni sufficienti.

4. Contributi Chiave

1. Identificazione di un Modo di Fallimento: Il documento identifica e dimostra formalmente che l'equità con memoria perfetta causa una crescita illimitata dello spazio degli stati, rendendo l'apprendimento su orizzonti lunghi intrattabile.
2. Nuovo Framework: Propone la Equità con Sconto del Passato, un framework basato sul comportamento che interpola tra l'equità istantanea e quella a memoria perfetta utilizzando un peso che decade geometricamente.
3. Garanzie Teoriche: Fornisce prove che lo sconto del passato garantisce uno spazio degli stati aumentato limitato e indipendente dall'orizzonte, ripristinando la proprietà di Markov e garantendo la trattabilità computazionale.
4. Validazione Empirica: Dimostra che gli agenti RL che utilizzano lo sconto del passato possono apprendere politiche eque su orizzonti arbitrariamente lunghi, mentre gli agenti con memoria perfetta falliscono all'estendersi dell'orizzonte.

5. Significato e Rivendicazioni

Il documento sostiene che lo sconto del passato non è meramente un'euristica, ma una necessità pratica per costruire sistemi di allocazione delle risorse scalabili ed equi. Garantendo che lo spazio degli stati rimanga limitato e indipendente dall'orizzonte, il framework sblocca la possibilità di apprendere politiche eque in modo trattabile in contesti con orizzonti lunghi dove i metodi tradizionali a memoria perfetta falliscono.

Gli autori posizionano questo lavoro come un "terzo paradigma" che occupa la via di mezzo pratica tra la semplicità computazionale dell'equità miopica e l'equità teorica (ma computazionalmente impraticabile) della memoria perfetta. Il significato risiede nel fornire un meccanismo fondato per gestire il compromesso tra risultati immediati e contesto storico, basandosi sia su intuizioni comportamentali che su rigorose condizioni di stabilità della teoria del controllo.