Learning to Contest: Decentralized Robust Fairness in Cooperative MARL via Cross-Attention

Este artigo introduz o CAN, uma política de atenção cruzada descentralizada para aprendizagem por reforço multiagente cooperativa que alcança justiça robusta e alta eficiência ao inferir dinamicamente o número de caronas (free-riders) e contestá-los proporcionalmente, superando assim as vulnerabilidades dos atuais aprendizes justos sem exigir um alocador centralizado.

O essencial

Imagine um grupo de amigos tentando dividir uma pizza. Todos concordam em ser justos: se alguém estiver com muita fome, recebe uma fatia maior para que ninguém vá para casa passando fome. Este é o objetivo do "Aprendizado por Reforço Multiagente Justo" (Fair Multi-Agent Reinforcement Learning — MARL) — ensinar programas de computador a cooperar e compartilhar recursos de forma igualitária.

No entanto, há um problema. Se um dos amigos decidir ser egoísta e pegar a maior fatia para si, os amigos justos ficam travados. Porque são programados para serem legais, eles podem simplesmente deixar o amigo egoísta pegar a fatia, pensando: "Bem, eu não quero brigar". Ou, se tentarem lutar, podem acabar colidindo uns com os outros, estragando a pizza para todo mundo.

Este artigo, intitulado "Learning to Contest" (Aprendendo a Contestar), faz uma pergunta difícil: Um grupo de amigos justos consegue se defender de um amigo egoísta sem que um chefe diga o que fazer?

Aqui está a história de como eles resolveram isso, usando analogias simples.

1. O Probleso Antigo: A Pizza "Tudo ou Nada"

Na antiga forma de pensar, os recursos eram como um jogo de "o vencedor leva tudo".

• O Cenário: Duas pessoas querem a última fatia.
• A Regra: Se ambas tentarem agarrá-la, a fatia é esmagada e jogada fora (0% restante). Se uma agarrar e a outra soltar, quem agarrou fica com 100%.
• O Resultado: Uma pessoa justa não tem incentivo para lutar. Se ela lutar, não ganha nada. Se desistir, não ganha nada. Então, ela simplesmente desiste. O amigo egoísta ganha tudo.

2. A Nova Regra: A Pizza "Graduada"

Os autores mudaram ligeiramente as regras do jogo. Eles introduziram a "Contestação Graduada".

• A Nova Regra: Se duas pessoas agarrarem a fatia, ela não é destruída. Em vez disso, ela é levemente amassada (talvez 20% seja desperdiçado), mas os 80% restantes são divididos entre elas.
• A Magia: Agora, se uma pessoa justa lutar contra uma pessoa egoísta, ela não ganha nada; ela ganha algo (um pequeno pedaço da pizza amassada). A pessoa egoísta ganha menos do que se tivesse agarrado a fatia sozinha.
• A Lição: Lutar agora é melhor do que desistir! Isso dá aos amigos justos uma "alavanca" para reagir.

3. O Novo Desafio: O "Jogo de Adivinhação"

Ter apenas a alavanca não é suficiente. A equipe justa enfrenta um problema de coordenação complexo:

• Cenário A: Ninguém está sendo egoísta. Se a equipe justa lutar de qualquer maneira, eles desperdiçam a pizza amassada sem motivo.
• Cenário B: Alguém está sendo egoísta. Se a equipe justa não lutar, a pessoa egoísta come tudo.
• O Dilema: A equipe justa não sabe quantos pessoas egoístas há na sala. Eles precisam de uma maneira de olhar ao redor, contar os encrenqueiros e decidir: "Nós lutamos ou apenas compartilhamos pacificamente?"

4. A Solução: CAN (O "Observador Inteligente")

Os autores criaram um novo sistema chamado CAN (Redes de Atenção Cruzada — Cross-Attention Networks). Pense no CAN como um capitão de equipe super inteligente que usa um par de óculos especiais.

• Como funciona: Em vez de um chefe dizer a todos o que fazer, cada agente (amigo) observa o que todos os outros estão fazendo.
• O Truque da "Atenção Cruzada": Imagine que cada agente tem um holofote. Eles brilham seus holofotes no comportamento dos outros.
  • Se veem que todos estão calmos, o holofote diz: "Relaxe, vamos compartilhar".
  • Se veem alguém agindo com ganância, o holofote diz: "Ei, aquela pessoa está agarrando! Vamos reagir apenas o suficiente para impedi-la, mas não tão forte que desperdicemos a pizza".
• O Treinamento: Eles ensinaram este sistema fazendo-o jogar contra uma "liga" de diferentes tipos de jogadores egoístas. O sistema aprendeu a reconhecer padrões e a adaptar sua estratégia sobre a marcha.

5. Os Resultados: O Melhor dos Dois Mundos

O artigo testou este sistema contra outros métodos e descobriu que o CAN é o único que acerta:

• Métodos Justos Antigos:
  • A Equipe "Legal": Sempre desiste. Eles são eficientes quando todos são legais, mas um amigo egoísta rouba tudo deles.
  • A Equipe "Agressiva": Sempre luta. Eles param o amigo egoísta, mas desperdiçam tanta pizza lutando que todos ficam com fome, mesmo quando ninguém está sendo mau.
• A Equipe CAN:
  • Quando todos são legais: Eles compartilham perfeitamente. Quase zero desperdício.
  • Quando um amigo egoísta aparece: Eles lutam apenas o suficiente para deter o ladrão, mas não tanto que estraguem a pizza.
  • O Resultado: Eles conseguem quase tanta justiça quanto se um humano chefe estivesse lá distribuindo as fatias, mas fizeram tudo sozinhos, sem um chefe.

6. Os Limites: Onde o Sistema Falha

Os autores são muito honestos sobre onde este sistema falha. Não é mágica; depende das regras do jogo.

• Se as regras forem muito severas: Se o jogo voltar para o "vencedor leva tudo" (onde a luta destrói completamente o recurso), o sistema falha. A alavanca desaparece.
• Se o grupo for grande demais: Se você pegar uma equipe treinada para 6 pessoas e de repente colocá-la em uma sala com 24 pessoas, elas ficam confusas em níveis altos de conflito. Elas não conseguem contar os encrenqueiros tão bem em uma multidão.
• Se o prêmio for grande demais: Se a "pizza" for um jackpot massivo pelo qual só vale a pena lutar se você ganhar 100%, o sistema fica com medo de lutar porque o risco de desperdiçar é muito alto.

Resumo

Este artigo mostra que a justiça descentralizada é possível, mas apenas se as regras do jogo permitirem um pouco de "meio termo" quando as pessoas lutam. Ao ensinar agentes de computador a observar uns aos outros e adaptar seu comportamento (usando a técnica de Atenção Cruzada), eles podem se proteger de membros egoístas sem precisar de uma autoridade central para microgerenciá-los. Eles aprenderam a ser durões quando necessário, mas educados quando é seguro.

Resumo técnico

Resumo Técnico: Aprendendo a Contestar: Equidade Robusta Descentralizada em MARL Cooperativo via Atenção Cruzada

1. Definição do Problema

O Aprendizado por Reforço Multiagente (MARL) cooperativo frequentemente otimiza para a equidade (ex: Gini Generalizado de Bem-Estar) para evitar a inanição dos agentes. No entanto, essas equipes "equitativas" são inerentemente exploráveis na presença de agentes autointeressados (caronas/free-riders). Quando uma equipe cooperator sacrifica a utilidade individual para elevar o agente com o pior desempenho, um agente autointeressado pode tirar proveito desse excedente.

Em uma disputa de recursos estritamente rival (tudo ou nada), essa exploração é difícil de combater ao nível da política. Se um cooperator contesta um carona por um recurso, o recurso é ganho por um ou totalmente desperdiçado (colisão). Consequentemente, uma equipe de bem-estar social é indiferente entre ceder ou contestar, tornando a defesa descentralizada fútil. Trabalhos anteriores sugerem que apenas um alocador centralizado, baseado em necessidades, pode resolver isso, deixando em aberto a questão de se políticas descentralizadas podem alcançar uma equidade robusta.

Este artigo aborda essa lacuna introduzindo um modelo de contencioso graduado. Neste modelo, os recursos contestados não são inteiramente desperdiçados; se $m \ge 2$ agentes reivindicarem um recurso, eles dividem uma fração $1-c$ (onde $c$ é o fator de desperdício), em vez de destruí-lo. O desafio central torna-se um problema de coordenação sob incerteza: o número de caronas ($D$) é desconhecido e variável. Uma política fixa falha porque "sempre contestar" desperdiça recursos quando ninguém defeta, enquanto "sempre ceder" colapsa quando um defector aparece.

2. Metodologia: CAN (Redes de Atenção Cruzada)

Os autores propõem o CAN, uma política descentralizada projetada para inferir a presença de caronas e responder proporcionalmente.

• Fundamentação Teórica (Proposição 1): O artigo prova que, sob contencioso graduado ($c < 1$), um cooperator com o pior desempenho melhora estritamente seu resultado ao contestar um único carona em vez de ceder. Contestar rende $(1-c)/2 > 0$ em vez de $0$, enquanto reduz o ganho do carona. Isso estabelece a existência de alavancagem descentralizada.
• Arquitetura:
  • Entrada: Cada agente observa um token de características do estado público: utilidade atual ($u_i$), desvio da média da equipe ($u_i - \bar{u}$), desvio da utilidade mínima ($u_i - u_{min}$), um indicador de ser o pior colocado, uma taxa de reivindicação corrente ($cc_i$) e o passo de tempo.
  • Mecanismo: O CAN emprega um bloco de autoatenção de cabeça única e permutação-equivariante. Os agentes prestam atenção aos tokens de comportamento observados de todos os outros agentes. Isso permite que a política infira o número de reivindicantes (contencioso) sem depender de identidades fixas de agentes.
  • Saída: A política gera logits para REIVINDICAR (CLAIM) ou CEDER (YIELD).
• Regime de Treinamento:
  • Objetivo: Cooperadores maximizam uma função de bem-estar $W_{coop} = \text{média}(u) - \text{desvio\_padrão}(u)$, recompensando tanto a recuperação de utilidade quanto a distribuição equitativa.
  • Treinamento Adversário: Para garantir a robustez, o CAN é treinado contra uma liga adversária (PSRO). Em vez de treinar contra um único defector que evolui em cooperação, o sistema alterna entre treinar cooperadores contra um pool congelado de defectores de melhor resposta passados e adicionar novos exploradores de melhor resposta ao pool. Isso evita que a política sofra overfitting a uma estratégia específica de adversário.

3. Resultados Principais

O artigo avalia o CAN contra baselines de bem-estar (GGF, FEN, SOTO) e um oráculo centralizado através de vários níveis de contencioso ($c \in \{0.3, \dots, 0.9\}$) e tamanhos de equipe ($N=6$).

• Troca entre Robustez e Eficiência:
  • Baselines: Aprendizes de bem-estar falham em um dos eixos. O GGF aprende a ceder (eficiente, mas maximamente explorável, $\rho \approx N$). O SOTO aprende a sempre contestar (robusto, mas dispendioso, eficiência $\approx 1-c$). O FEN é instável.
  • CAN: Alcança tanto robustez quanto eficiência. Mantém baixa explorabilidade de melhor resposta ($\rho \approx 1.2\text{--}1.5$) em todos os níveis de contencioso, mantendo eficiência quase perfeita ($\approx 1.0$) quando nenhum carona está presente.
• Validação do Mecanismo:
  • Comportamento Adaptativo: O CAN aprende a "revezar" (ceder) quando $D=0$ para evitar desperdício, e "contestar o suficiente" quando $D \ge 1$.
  • Esquema de Treinamento: O treinamento em liga é crítico. O co-treinamento vanilla contra um adversário estático resulta em maior explorabilidade ($\rho \approx 2.0$) e deriva para cima, enquanto o treinamento em liga mantém $\rho$ baixo e estável.
  • Arquitetura: A atenção cruzada é superior ao pooling simples (mean-pool, deep-sets) e mais estável que GRUs bidirecionais, particularmente em altos níveis de contencioso ($c=0.9$).
• Generalização e Limites:
  • Tamanho da Equipe: O CAN realiza transferência zero-shot para equipes maiores ($N=12, 24$) em baixo contencioso, mas degrada em alto contencioso, indicando uma fragilidade na escala da inferência de contencioso.
  • Escopo do Ambiente: O CAN permanece eficiente e domina o Pareto sobre os baselines em jogos de congestionamento e "stakes" (valor variável). No entanto, sua robustez é limitada pela alavancagem fornecida pelas regras do jogo. Em regras de "vencedor leva tudo" (Matthew), onde o agente mais rico vence independentemente do contencioso, a alavancagem desaparece e o CAN é explorado.

4. Significância e Alegações

O artigo alega fornecer um mapa controlado e honesto dos limites da equidade robusta descentralizada, em vez de alegar que a lacuna de descentralização foi totalmente fechada.

• Refutação da Futilidade: Os autores demonstram que a futilidade da defesa descentralizada é um artefato do contencioso "tudo ou nada". Ao introduzir o contencioso graduado, eles provam que a alavancagem descentralizada existe.
• Aproximação do Oráculo: O CAN aproxima-se do desempenho de um oráculo centralizado baseado em necessidades (que é o limite teórico superior) sem exigir um alocador central. Ele faz isso aprendendo a condicionar suas ações à observação do comportamento de outros para inferir o número de defectores.
• Escopo de Aplicabilidade: O artigo afirma explicitamente que a robustez não é universal. Ela ocorre apenas em proporção à "alavancagem de contestação" que um jogo fornece. Se as regras do jogo não permitem que um contestador capture uma parte positiva do recurso (ex: vencedor leva tudo), a abordagem falha.
• Contribuição: O trabalho desloca o paradigma de ver a equidade em MARL como inerentemente explorável para vê-la como um alvo tratável e mensurável, desde que o ambiente permita contencioso graduado e a política seja treinada contra uma história diversificada de adversários.

Os autores concluem que, embora a equidade robusta descentralizada seja alcançável, ela é limitada por condições específicas: a existência de alavancagem de contencioso graduado, a capacidade de inferir contagens de adversários via atenção e o uso de treinamento de liga adversária para estabilizar a política.