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

Resumo Técnico: Desconto de Passado para Aprendizado de Equidade Markoviana com Horizontes Longos

1. Definição do Problema

A alocação dinâmica de recursos em sistemas multiagentes exige o equilíbrio entre eficiência e equidade ao longo de horizontes temporais longos. As abordagens existentes enfrentam um dilema fundamental:

• Equidade Miope (Instantânea): Avalia a equidade baseando-se apenas na etapa de alocação atual. Embora computacionalmente simples, ignora o contexto histórico, levando a inequidades cumulativas ao longo do tempo.
• Equidade de Memória Perfeita (Perfect-Recall): Rastreia a soma completa de todas as utilidades passadas para garantir equidade a longo prazo. Embora teoricamente equitativa, esta abordagem introduz um modo de falha crítico: o espaço de estados aumentado necessário para rastrear a utilidade cumulativa cresce de forma ilimitada com o horizonte temporal. Essa explosão de estados torna os algoritmos de aprendizado por reforço (RL) computacionalmente intratáveis e impede a convergência para políticas justas em configurações de horizonte longo.

O desafio central é projetar um mecanismo de memória que preserve a propriedade de Markov (permitindo aprendizado tratável) enquanto mantém um espaço de estados limitado e independente do horizonte, sem sacrificar a capacidade de raciocinar sobre desigualdades históricas.

2. Metodologia

Os autores propõem a Equidade com Desconto de Passado (Past-Discounted Fairness), um framework inspirado pela economia comportamental e psicologia moral, que postulam que os julgamentos humanos de equidade naturalmente descontam eventos distantes. A metodologia envolve três componentes principais:

A. Mecanismos de Memória de Recall com Desconto
Em vez de somar todas as utilidades passadas ($Z_t = \sum u_\tau$), o framework aplica um fator de desconto ajustável $\gamma_p \in [0, 1]$ às utilidades históricas. Duas formulações específicas são definidas:

1. Recall de Desconto Aditivo: O estado de memória é atualizado como $Z_t = \gamma_p Z_{t-1} + u_t$. Aqui, $\gamma_p=0$ reduz-se à equidade instantânea, e $\gamma_p=1$ recupera o recall perfeito.
2. Recall de Desconto Médio: Tanto a utilidade acumulada quanto o denominador do tempo efetivo são descontados, garantindo que o estado de memória permaneça limitado mesmo ao realizar a média.

B. Análise Teórica do Espaço de Estados
O artigo fornece provas rigorosas comparando as propriedades do espaço de estados de diferentes paradigmas:

• Recall Perfeito (Aditivo): O Teorema 3 prova que o espaço de estados cresce linearmente com o horizonte temporal $t$ por coordenada e exponencialmente com o número de agentes $n$. Isso leva a um espaço de estados ilimitado, tornando impossível a discretização de resolução fixa para horizontes longos.
• Recall Perfeito (Médio): O Teorema 5 mostra que, embora o valor da utilidade média seja limitado, manter a propriedade de Markov exige carregar o índice de tempo $t$ (ou um denominador equivalente) como parte do estado, o que ainda é ilimitado.
• Desconto de Passado (Aditivo e Médio): Os Teoremas 4 e 6 provam que, com $\gamma_p < 1$, o estado de memória $Z_t$ é uniformemente limitado por $u_{max} / (1 - \gamma_p)$. Crucialmente, o tamanho do espaço de estados aumentado torna-se independente do horizonte temporal, satisfazendo as condições para aprendizado tratável.

C. Conexão com a Teoria do Controle
Os autores estendem a análise modelando a memória de equidade como um sistema Linear Invariante no Tempo (LTI). Eles demonstram que, para o estado de memória permanecer limitado, o raio espectral da matriz de transição de memória deve ser menor que um ($\rho(A) < 1$). O recall perfeito corresponde a uma matriz identidade ($\rho=1$), que é instável, enquanto o desconto de passado corresponde a uma identidade escalonada ($\rho = \gamma_p < 1$), garantindo estabilidade.

D. Meia-Vida e Janela Efetiva
Para auxiliar os praticantes na seleção de $\gamma_p$, o artigo introduz o conceito de "meia-vida" ($t_{1/2}$) e "janela efetiva" ($W_{eff} = 1/(1-\gamma_p)$). Essas métricas quantificam quantos passos passados influenciam significativamente a avaliação de equidade atual, permitindo um trade-off fundamentado entre profundidade de memória e viabilidade computacional.

3. Resultados Experimentais

Os autores validam empiricamente sua teoria usando uma configuração de Aprendizado por Reforço Multiagente (MARL) com um agente de Otimização de Política Próxima (PPO) em um ambiente de alocação de recursos dinâmicos (10 agentes, 2 recursos por passo).

• Configuração: Os agentes foram treinados sob vários horizontes ($T=100$ a $T=10.000$) sob três configurações de memória: Miope ($\gamma_p=0$), Recall Perfeito ($\gamma_p=1$) e Desconto de Passado ($\gamma_p \in \{0.9, 0.99, 0.999\}$).
• Descobertas:
  • Agentes Míopes: Falharam em aprender políticas justas, resultando em alta desigualdade (alto coeficiente de Gini) devido à falta de contexto histórico.
  • Agentes de Recall Perfeito: Desempenharam-se bem em horizontes curtos ($T \le 500$), mas sofreram um colapso catastrófico de desempenho conforme o horizonte aumentava. Em $T=10.000$, sua capacidade de manter a equidade degradou-se ao nível dos agentes míopes, confirmando a previsão teórica de que a explosão do espaço de estados impede a convergência.
  • Agentes de Desconto de Passado: Aprenderam com sucesso políticas justas robustas em todos os horizontes. A representação de estado limitada permitiu que o algoritmo PPO convergisse.
  • Sensibilidade de Parâmetros: O $\gamma_p$ ideal dependeu da densidade do sinal de equidade. Para sinais densos (Bem-estar de Nash), uma memória mais curta ($\gamma_p=0.9$) foi suficiente. Para sinais esparsos (Bem-estar Igualitário), uma memória mais longa ($\gamma_p=0.99$) foi necessária para acumular informação suficiente.

4. Principais Contribuições

1. Identificação de um Modo de Falha: O artigo identifica e prova formalmente que a equidade de recall perfeito causa crescimento ilimitado do espaço de estados, tornando o aprendizado de longo horizonte intratável.
2. Framework Inovador: Propõe a Equidade com Desconto de Passado, um framework baseado em comportamento que interpola entre a equidade instantânea e a de recall perfeito usando um peso de decaimento geométrico.
3. Garantias Teóricas: Fornece provas de que o desconto de passado garante um espaço de estados aumentado limitado e independente do horizonte, restaurando a propriedade de Markov enquanto assegura a tratabilidade computacional.
4. Validação Empírica: Demonstra que agentes de RL usando desconto de passado podem aprender políticas justas em horizontes arbitrariamente longos, enquanto agentes usando recall perfeito falham conforme o horizonte se estende.

5. Significância e Alegações

O artigo afirma que o desconto de passado não é meramente um heurístico, mas uma necessidade prática para construir sistemas de alocação de recursos escaláveis e equitativos. Ao garantir que o espaço de estados permaneça limitado e independente do horizonte, o framework desbloqueia a capacidade de aprender políticas justas de forma tratável em configurações de longo horizonte onde os métodos tradicionais de recall perfeito falham.

Os autores posicionam este trabalho como um "terceiro paradigma" que ocupa o meio termo prático entre a simplicidade computacional da equidade miope e a equidade teórica (mas computacionalmente inviável) do recall perfeito. A significância reside em fornecer um mecanismo fundamentado para gerenciar o trade-off entre resultados imediatos e contexto histórico, baseado tanto em insights comportamentais quanto em condições de estabilidade rigorosas da teoria de controle.