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

Resumen Técnico: Descuento del Pasado para el Aprendizaje de Equidad Markoviana en Horizontes Largos

1. Planteamiento del Problema

La asignación dinámica de recursos en sistemas multiagente requiere equilibrar la eficiencia con la equidad a lo largo de horizontes temporales largos. Los enfoques existentes enfrentan un dilema fundamental:

• Equidad Miope (Instantánea): Evalúa la equidad basándose únicamente en el paso de asignación actual. Aunque es computacionalmente simple, ignora el contexto histórico, lo que conduce a inequidades acumulativas a lo largo del tiempo.
• Equidad de Memoria Perfecta (Perfect-Recall): Rastrea la suma completa de todas las utilidades pasadas para asegurar la equidad a largo plazo. Aunque es teóricamente equitativa, este enfoque introduce un modo de falla crítico: el espacio de estados aumentado requerido para rastrear las utilidades acumuladas crece de forma ilimitada con el horizonte temporal. Esta explosión del espacio de estados hace que los algoritmos de aprendizaje por refuerzo (RL) sean computacionalmente intratables y evita la convergencia de políticas justas en entornos de horizonte largo.

El desafío central es diseñar un mecanismo de memoria que preserve la propiedad de Markov (permitiendo un aprendizaje tratable) mientras mantiene un espacio de estados acotado e independiente del horizonte, sin sacrificar la capacidad de razonar sobre las desigualdades históricas.

2. Metodología

Los autores proponen la Equidad con Descuento del Pasado (Past-Discounted Fairness), un marco inspirado en la economía conductual y la psicología moral, que postulan que los juicios de equidad humanos descuentan naturalmente los eventos distantes. La metodología involucra tres componentes clave:

A. Mecanismos de Memoria de Recuerdo con Descuento
En lugar de sumar todas las utilidades pasadas ($Z_t = \sum u_\tau$), el marco aplica un factor de descuento ajustable $\gamma_p \in [0, 1]$ a las utilidades históricas. Se definen dos formulaciones específicas:

1. Recuerdo con Descuento Aditivo: El estado de la memoria se actualiza como $Z_t = \gamma_p Z_{t-1} + u_t$. Aquí, $\gamma_p=0$ reduce al caso de equidad instantánea, y $\gamma_p=1$ recupera la memoria perfecta.
2. Recuerdo con Descuento Promediado: Tanto la utilidad acumulada como el denominador del tiempo efectivo se descuentan, asegurando que el estado de la memoria permanezca acotado incluso al promediar.

B. Análisis Teórico del Espacio de Estados
El artículo proporciona pruebas rigurosas comparando las propiedades del espacio de estados de diferentes paradigmas:

• Memoria Perfecta (Aditiva): El Teorema 3 demuestra que el espacio de estados crece linealmente con el horizonte temporal $t$ por coordenada y exponencialmente con el número de agentes $n$. Esto conduce a un espacio de estados ilimitado, haciendo imposible la discretización de resolución fija para horizontes largos.
• Memoria Perfecta (Promediada): El Teorema 5 muestra que, si bien el valor de la utilidad promedio está acotado, mantener la propiedad de Markov requiere portar el índice de tiempo $t$ (o un denominador equivalente) como parte del estado, lo cual sigue siendo ilimitado.
• Descuento del Pasado (Aditivo y Promediado): Los Teoremas 4 y 6 demuestran que con $\gamma_p < 1$, el estado de la memoria $Z_t$ está uniformemente acotado por $u_{max} / (1 - \gamma_p)$. Crucialmente, el tamaño del espacio de estados aumentado se vuelve independiente del horizonte temporal, satisfaciendo las condiciones para un aprendizaje tratable.

C. Conexión con la Teoría de Control
Los autores extienden el análisis modelando la memoria de equidad como un sistema Lineal e Invariante en el Tiempo (LTI). Demuestran que para que el estado de la memoria permanezca acotado, el radio espectral de la matriz de transición de la memoria debe ser menor que uno ($\rho(A) < 1$). La memoria perfecta corresponde a una matriz identidad ($\rho=1$), la cual es inestable, mientras que el descuento del pasado corresponde a una identidad escalada ($\rho = \gamma_p < 1$), garantizando la estabilidad.

D. Semivida y Ventana Efectiva
Para ayudar a los profesionales en la selección de $\gamma_p$, el artículo introduce el concepto de "semivida" ($t_{1/2}$) y "ventana efectiva" ($W_{eff} = 1/(1-\gamma_p)$). Estas métricas cuantifican cuántos pasos pasados influyen significativamente en la evaluación actual de la equidad, permitiendo un compromiso principiado entre la profundidad de la memoria y la viabilidad computacional.

3. Resultados Experimentales

Los autores validan empíricamente su teoría utilizando una configuración de Aprendizaje por Refuerzo Multiagente (MARL) con un agente de Optimización de Política de Proximidad (PPO) en un entorno de asignación de recursos dinámicos (10 agentes, 2 recursos por paso).

• Configuración: Los agentes fueron entrenados sobre horizontes variables ($T=100$ a $T=10,000$) bajo tres configuraciones de memoria: Miope ($\gamma_p=0$), Memoria Perfecta ($\gamma_p=1$), y Descuento del Pasado ($\gamma_p \in \{0.9, 0.99, 0.999\}$).
• Hallazgos:
  • Agentes Míopes: No lograron aprender políticas justas, resultando en una alta desigualdad (coeficiente de Gini alto) debido a la falta de contexto histórico.
  • Agentes de Memoria Perfecta: Funcionaron bien en horizontos cortos ($T \le 500$), pero sufrieron un colapso catastrófico de rendimiento a medida que el horizonte aumentaba. En $T=10,000$, su capacidad para mantener la equidad se degradó al nivel de los agentes míopes, confirmando la predicción teórica de que la explosión del espacio de estados impide la convergencia.
  • Agentes con Descuento del Pasado: Lograron aprender políticas justas robustas en todos los horizontes. La representación de estado acotada permitió que el algoritmo PPO convergiera.
  • Sensibilidad de Parámetros: El $\gamma_p$ óptimo dependió de la densidad de la señal de equidad. Para señales densas (Bienestar de Nash), una memoria más corta ($\gamma_p=0.9$) fue suficiente. Para señales dispersas (Bienestar Igualitario), se requirió una memoria más larga ($\gamma_p=0.99$) para acumular información suficiente.

4. Contribuciones Clave

1. Identificación de un Modo de Falla: El artículo identifica y demuestra formalmente que la equidad de memoria perfecta causa un crecimiento ilimitado del espacio de estados, haciendo que el aprendizaje en horizontes largos sea intratable.
2. Nuevo Marco de Trabajo: Propone la Equidad con Descuento del Pasado, un marco fundamentado en el comportamiento que interpola entre la equidad instantánea y la de memoria perfecta mediante un peso de decaimiento geométrico.
3. Garantías Teóricas: Proporciona pruebas de que el descuento del pasado garantiza un espacio de estados aumentado acotado e independiente del horizonte, restaurando así la propiedad de Markov y asegurando la tratabilidad computacional.
4. Validación Empírica: Demuestra que los agentes de RL que utilizan el descuento del pasado pueden aprender políticas justas en horizontes arbitrariamente largos, mientras que los agentes con memoria perfecta fallan a medida que el horizonte se extiende.

5. Significado y Reivindicaciones

El artículo sostiene que el descuento del pasado no es simplemente un heurístico, sino una necesidad práctica para construir sistemas de asignación de recursos escalables y equitativos. Al asegurar que el espacio de estados permanezca acotado e independiente del horizonte, el marco permite el aprendizaje de políticas justas de manera tratable en entornos de horizonte largo donde los métodos tradicionales de memoria perfecta fallan.

Los autores posicionan este trabajo como un "tercer paradigma" que ocupa el punto medio práctico entre la simplicidad computacional de la equidad miope y la equidad teórica (pero computacionalmente inviable) de la memoria perfecta. El significado reside en proporcionar un mecanismo principiado para gestionar el compromiso entre los resultados inmediatos y el contexto histórico, fundamentado tanto en la visión conductual como en las condiciones de estabilidad de la teoría de control.