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

Résumé Technique : L'Escompte du Passé pour l'Apprentissage de l'Équité Markovienne à Longue Horizon

1. Énoncé du Problème

L'allocation dynamique de ressources dans les systèmes multi-agents nécessite un équilibre entre efficacité et équité sur de longs horizons temporels. Les approches existantes sont confrontées à un dilemme fondamental :

• Équité Myope (Instantanée) : Évalue l'équité en se basant uniquement sur l'étape d'allocation actuelle. Bien que la simplicité de calcul soit grande, elle ignore le contexte historique, ce qui entraîne des inégalités cumulatives au fil du temps.
• Équité à Rappel Parfait : Suit la somme complète de toutes les utilités passées pour garantir une équité à long terme. Bien que théoriquement équitable, cette approche introduit un mode de défaillance critique : l'espace d'état augmenté requis pour suivre les utilités cumulées croît de manière illimitée avec l'horizon temporel. Cette explosion de l'espace d'état rend les algorithmes d'apprentissage par renforcement (RL) computationnellement intraitables et empêche la convergence vers des politiques équitables dans des contextes à long horizon.

Le défi central consiste à concevoir un mécanisme de mémoire qui préserve la propriété de Markov (permettant un apprentissage traitable) tout en maintenant un espace d'état borné et indépendant de l'horizon, sans sacrifier la capacité à raisonner sur les inégalités historiques.

2. Méthodologie

Les auteurs proposent l'Équité à Escompte du Passé (Past-Discounted Fairness), un cadre inspiré de l'économie comportementale et de la psychologie morale, qui postulent que les jugements humains sur l'équité escompte naturellement les événements lointains. La méthodologie comprend trois composantes clés :

A. Mécanismes de Mémoire à Rappel Escompté
Au lieu de sommer toutes les utilités passées ($Z_t = \sum u_\tau$), le cadre applique un facteur d'escompte ajustable $\gamma_p \in [0, 1]$ aux utilités historiques. Deux formulations spécifiques sont définies :

1. Rappel Escompté Additif : L'état de la mémoire est mis à jour selon $Z_t = \gamma_p Z_{t-1} + u_t$. Ici, $\gamma_p=0$ revient à l'équité instantanée, et $\gamma_p=1$ revient au rappel parfait.
2. Rappel Escompté Moyenné : L'utilité accumulée ainsi que le dénominateur temporel effectif sont tous deux escomptés, garantissant que l'état de la mémoire reste borné, même lors de l'application d'une moyenne.

B. Analyse Théorique de l'Espace d'État
L'article fournit des preuves rigoureuses comparant les propriétés de l'espace d'état de différents paradigmes :

• Rappel Parfait (Additif) : Le Théorème 3 prouve que l'espace d'état croît linéairement avec l'horizon temporel $t$ par coordonnée et exponentiellement avec le nombre d'agents $n$. Cela conduit à un espace d'état non borné, rendant impossible une discrétisation à résolution fixe pour de longs horizons.
• Rappel Parfait (Moyenné) : Le Théorème 5 montre que bien que la valeur de l'utilité moyenne soit bornée, le maintien de la propriété de Markov nécessite de porter l'indice temporel $t$ (ou un dénominateur équivalent) comme faisant partie de l'état, ce qui est toujours non borné.
• Équité à Escompte du Passé (Additif et Moyenné) : Les Théorèmes 4 et 6 prouvent qu'avec $\gamma_p < 1$, l'état de la mémoire $Z_t$ est uniformément borné par $u_{max} / (1 - \gamma_p)$. Crucialement, la taille de l'espace d'état augmenté devient indépendante de l'horizon temporel, satisfaisant les conditions pour un apprentissage traitable.

C. Connexion avec la Théorie du Contrôle
Les auteurs étendent l'analyse en modélisant la mémoire de l'équité comme un système Linéaire Invariant Temporel (LTI). Ils démontrent que pour que l'état de la mémoire reste borné, le rayon spectral de la matrice de transition de la mémoire doit être inférieur à un ($\rho(A) < 1$). Le rappel parfait correspond à une matrice identité ($\rho=1$), qui est instable, tandis que l'escompte du passé correspond à une identité mise à l'échelle ($\rho = \gamma_p < 1$), garantissant la stabilité.

D. Demi-vie et Fenêtre Effective
Pour aider les praticiens à choisir $\gamma_p$, l'article introduit le concept de "demi-vie" ($t_{1/2}$) et de "fenêtre effective" ($W_{eff} = 1/(1-\gamma_p)$). Ces métriques quantifient le nombre d'étapes passées qui influencent de manière significative l'évaluation actuelle de l'équité, permettant un compromis raisonné entre la profondeur de la mémoire et la faisabilité computationnelle.

3. Résultats Expérimentaux

Les auteurs valident empiriquement leur théorie en utilisant une configuration d'apprentissage par renforcement multi-agents (MARL) avec un agent PPO dans un environnement d'allocation de ressources dynamique (10 agents, 2 ressources par étape).

• Configuration : Les agents ont été entraînés sur des horizons variables ($T=100$ à $T=10\,000$) sous trois configurations de mémoire : Myope ($\gamma_p=0$), Rappel Parfait ($\gamma_p=1$), et Équité à Escompte du Passé ($\gamma_p \in \{0.9, 0.99, 0.999\}$).
• Constatations :
  • Agents Myopes : Ont échoué à apprendre des politiques équitables, résultant en une forte inégalité (coefficient de Gini élevé) en raison de l'absence de contexte historique.
  • Agents à Rappel Parfait : Ont performé sur de courts horizons ($T \le 500$) mais ont subi un effondrement catastrophique des performances à mesure que l'horizon augmentait. À $T=10\,000$, leur capacité à maintenir l'équité s'est dégradée au niveau des agents myopes, confirmant la prédiction théorique de l'explosion de l'espace d'état entravant la convergence.
  • Agents à Escompte du Passé : Ont réussi à apprendre des politiques équitables robustes sur tous les horizons. La représentation de l'état bornée a permis à l'algorithme PPO de converger.
  • Sensibilité des Paramètres : L'optimalité de $\gamma_p$ dépendait de la densité du signal d'équité. Pour les signaux denses (Bien-être de Nash), une mémoire plus courte ($\gamma_p=0.9$) suffisait. Pour les signaux épars (Bien-être Égalitaire), une mémoire plus longue ($\gamma_p=0.99$) était nécessaire pour accumuler suffisamment d'informations.

4. Contributions Clés

1. Identification d'un Mode de Défaillance : Le papier identifie et prouve formellement que l'équité à rappel parfait provoque une croissance non bornée de l'espace d'état, rendant l'apprentissage à long horizon intraitable.
2. Nouveau Cadre : Il propose l'Équité à Escompte du Passé, un cadre fondé sur le comportement qui interpole entre l'équité instantanée et l'équité à rappel parfait en utilisant un poids à décroissance géométrique.
3. Garanties Théoriques : Il fournit des preuves que l'escompte du passé garantit un espace d'état augmenté borné et indépendant de l'horizon, restaurant ainsi la propriété de Markov tout en assurant la faisabilité computationnelle.
4. Validation Empirique : Il démontre que les agents de RL utilisant l'escompte du passé peuvent apprendre des politiques équitables sur des horizons arbitrairement longs, là où les agents utilisant le rappel parfait échouent à mesure que l'horizon s'étend.

5. Signification et Revendications

Le papier affirme que l'escompte du passé n'est pas simplement une heuristique, mais une nécessité pratique pour construire des systèmes d'allocation de ressources évolutifs et équitables. En garantissant que l'espace d'état reste borné et indépendant de l'horizon, le cadre permet d'apprendre des politiques équitables de manière traitable dans des contextes à long horizon où les méthodes traditionnelles de rappel parfait échouent.

Les auteurs positionnent ce travail comme un "troisième paradigme" qui occupe le juste milieu pratique entre la simplicité computationnelle de l'équité myope et l'équité théorique (mais d'infaisabilité computationnelle) du rappel parfait. La signification réside dans la fourniture d'un mécanisme fondé pour gérer le compromis entre les résultats immédiats et le contexte historique, ancré à la fois dans les intuitions comportementales et les conditions de stabilité rigoureuses de la théorie du contrôle.