Resumo Técnico: Graph-SND: Agregação Esparsa para Diversidade Comportamental em Aprendizado por Reforço Multiagente

1. Declaração do Problema

No Aprendizado por Reforço Multiagente (MARL), a Diversidade Neural Sistêmica (SND) é uma métrica utilizada para medir a heterogeneidade comportamental entre agentes, calculando a média das distâncias de Wasserstein pareadas entre suas distribuições de ação. Embora a SND permita o controle da diversidade (por exemplo, via o algoritmo DiCo), seu cálculo apresenta um gargalo severo de escalabilidade. O cálculo da SND completa exige a avaliação de todos os $\binom{n}{2}$ pares de agentes, resultando em uma complexidade quadrática $O(n^2)$ no número de agentes $n$. Esse custo de agregação torna-se proibitivo para equipes em grande escala, limitando a aplicação prática de treinamento e controle conscientes da diversidade. O artigo identifica a etapa de "agregação de subgrupo para sistema" como o principal desafio aberto, observando que as métricas existentes tratam a média de todos os pares como um requisito fixo e não negociável.

2. Metodologia: Graph-SND

Os autores introduzem o Graph-SND, uma generalização da SND que substitui a média do grafo completo por uma média ponderada sobre as arestas de um grafo arbitrário $G = (A, E, w)$.

Definição

Seja $d(i, j)$ a distância comportamental Monte Carlo entre os agentes $i$ e $j$. O Graph-SND é definido como:
$$\text{SND}_G(D, G) = \frac{1}{W(G)} \sum_{\{i,j\} \in E} w_{ij} d(i, j)$$
onde $W(G) = \sum_{\{i,j\} \in E} w_{ij}$ é o peso total das arestas.

Três Regimes Operacionais

O framework suporta três regimes distintos baseados na escolha do grafo $G$:

1. Recuperação Exata ($G = K_n$): Quando $G$ é o grafo completo com pesos unitários, o Graph-SND recupera a SND original exatamente.
2. Diversidade Localizada (Grafos Esparsos Fixos): Quando $G$ é um grafo esparso fixo (por exemplo, $k$-vizinhos mais próximos, topologia de comunicação), a métrica mede a diversidade apenas sobre interações relevantes para a tarefa. Isso reduz o custo computacional para $O(|E|)$.
3. Estimação Esparsa (Grafos Aleatórios): Quando as arestas são amostradas aleatoriamente (por exemplo, amostragem de Bernoulli), o Graph-SND atua como um estimador esparso da SND completa.
   • Estimação Não Viciada: Usando pesos de Horvitz-Thompson ($w_{ij} = 1/p$), o estimador é incondicionalmente não viciado.
   • Concentração: A média amostral normalizada (pesos uniformes) satisfaz limites de concentração do tipo Hoeffding, convergindo para a SND verdadeira com taxa $O(1/\sqrt{m})$, onde $m$ é o número de arestas amostradas.

Limites Teóricos

• Distorção Determinística: Para grafos conexos fixos, o artigo deriva limites relacionando $\text{SND}_G$ a $\text{SND}$ usando o índice de encaminhamento de arestas $\pi(G)$. Especificamente, $|\text{SND}_G - \text{SND}|$ é limitado por fatores envolvendo $\pi(G)$.
• Grafos Expansores: Para grafos expansores aleatórios $d$-regulares, o índice de encaminhamento escala como $O(n \log n / d)$. Os autores provam que, com $d = \Theta(\log n)$, a distorção relativa no pior caso é $O(\log n)$.
• Refinamento Espectral: Sob estruturas de distância de baixo posto (norma nuclear normalizada controlada), o limite de erro para expansores melhora para $O(\rho^*/\sqrt{d})$, explicando as razões empíricas próximas a unidade.
• Limites Probabilísticos: Para grafos aleatórios $d$-regulares, estabelece-se um limite probabilístico incondicional de $\tilde{O}(D_{\max}/\sqrt{n})$.

3. Contribuições Principais

1. Definição de Graph-SND: Uma camada de agregação esparsa que recupera a SND em grafos completos e custa $O(|E|)$ em grafos pré-computados.
2. Garantias Teóricas: Provas de recuperação, não negatividade, invariância a automorfismos de grafo, não viciado de Horvitz-Thompson e desigualdades de concentração (Hoeffding/Serfling). O artigo também estabelece limites de distorção determinística para grafos fixos e limites probabilísticos incondicionais para grafos regulares aleatórios.
3. Validação Empírica:
   • Recuperação e Não Viciado: Verificado em ambientes VMAS, mostrando recuperação exata em $K_4$ e não viciado do estimador de Horvitz-Thompson em $n=8$.
   • Escalabilidade: Demonstrou acelerações de tempo de relógio escalando linearmente com $1/p$ (probabilidade de amostragem) até $n=500$.
   • Controle em Malha Fechada: Integrou Graph-SND no controlador de diversidade DiCo. Em $n=50$, o Graph-SND Bernoulli-0.1 rastreou os pontos de ajuste com erro relativo sub-1% e produziu diferenças de recompensa indistinguíveis de zero em comparação com a SND completa, reduzindo o custo da métrica por chamada em $\sim 9.5\times$.
   • Desempenho de Expansores: Expansores aleatórios $d$-regulares alcançaram $\text{SND}_G/\text{SND} \in [0.9987, 1.0013]$ em $\Theta(n \log n)$ arestas, superando significativamente outras bases esparsas em razões de distorção para custo.

4. Resultados

• Eficiência: Em uma execução PPO de 500 iterações com $n=100$, o Graph-SND Bernoulli-0.1 rastreou a SND completa enquanto reduzia o tempo da métrica por chamada em aproximadamente $10\times$.
• Escalabilidade: O cronometramento em GPU com política congelada até $n=500$ confirmou a aceleração prevista de $\binom{n}{2}/|E|$, reduzindo o tempo da métrica de ~15,5 segundos para ~1,5 segundos em $n=500$ com densidade de arestas de 10%.
• Estabilidade de Controle: Em experimentos DiCo em $n=50$, o controlador esparso manteve o rastreamento do ponto de ajuste e produziu diferenças de recompensa pareadas centradas próximas a zero em nove células correspondentes, com uma diferença média de recompensa de $-6.2 \times 10^{-4}$.
• Robustez: O método transferiu-se para configurações não gaussianas (PettingZoo MPE com políticas categóricas e Distância de Variação Total), mantendo viés pequeno e reduções de custo.

5. Significado e Alegações

O artigo alega que o Graph-SND remove com sucesso o gargalo de agregação da SND sem alterar a semântica da métrica ou exigir mudanças nas arquiteturas de política ou algoritmos de treinamento.

• Alternativa "Plug-and-Play": Fornece uma "alternativa esparsa plug-and-play" que escala além da SND de grafo completo, suportando tanto medição passiva quanto controle de diversidade em malha fechada.
• Flexibilidade Semântica: O grafo $G$ é apresentado não como um parâmetro incômodo, mas como uma escolha deliberada que determina o alvo da medição:
  • Use amostragem de Bernoulli para estimar a diversidade total do sistema.
  • Use grafos locais fixos (por exemplo, comunicação, $k$-NN) para medir a diversidade relevante para estruturas de interação específicas.
  • Use grafos expansores para proxies esparsos determinísticos, quase lineares, com fortes garantias estruturais no pior caso.
• Limitações Modestas: Os autores reconhecem que, embora os limites teóricos para expansores sejam $O(\log n)$, as razões observadas próximas a unidade dependem dos dados e são parcialmente explicadas pelas propriedades espectrais das matrizes de distância do MARL. Eles também observam que os experimentos atuais focam no PPO Independente, deixando algoritmos com crítico centralizado para trabalhos futuros.

Em resumo, o Graph-SND reestrutura a agregação de diversidade como um problema de seleção de grafo, oferecendo um framework unificado que equilibra eficiência computacional com garantias teóricas para diversidade comportamental em MARL.