Resumo Técnico: Grafos de Coordenação com Gargalo de Informação Heterogêneo para Aprendizado por Reforço Multiagente

1. Declaração do Problema

O Aprendizado por Reforço Multiagente Cooperativo (MARL) depende da troca de informações relevantes para a tarefa entre os agentes para coordenar decisões locais em direção a um objetivo compartilhado. Os grafos de coordenação (CGs) facilitam isso ao especificar quais pares de agentes trocam informações, reduzindo assim a agregação de ruído e os custos computacionais. No entanto, os aprendizes de grafos esparsos existentes enfrentam duas limitações fundamentais:

1. Falta de Fundamentação Teórica para a Existência de Arestas: Os métodos atuais dependem de critérios heurísticos (por exemplo, limiares fixos, seleção top-k, pontuações de atenção) para determinar a existência de arestas. Essas abordagens tratam todas as ligações de forma homogênea, não oferecendo garantia formal sobre a topologia aprendida, particularmente quando os agentes formam subequipes funcionais com necessidades distintas de coordenação intra-grupo e inter-grupo.
2. Ausência de Capacidade de Comunicação Estruturalmente Controlada: Mesmo quando uma topologia é aprendida, os métodos existentes carecem de um mecanismo principista para alocar diferentes larguras de banda de mensagem a relacionamentos estruturalmente distintos entre agentes. Eles falham em aprender conjuntamente quais arestas devem existir e quanto de informação cada aresta deve carregar.

O desafio central é aprender uma topologia de grafo que seja fiel à estrutura de coordenação subjacente da tarefa, ao mesmo tempo em que controla a largura de banda de características carregada nesse grafo.

2. Metodologia: HIBCG

Os autores propõem os Grafos de Coordenação com Gargalo de Informação Heterogêneo (HIBCG), um quadro que enquadra a coordenação MARL como um problema de aprendizado de grafo heterogêneo. O HIBCG acopla dois mecanismos de controle usando o princípio do Gargalo de Informação do Grafo (GIB):

1. Aprendizado de Topologia (AIB): Aprendizado de um grafo esparso por camada onde a retenção de arestas é determinada por um prior de bloco-diagonal alinhado ao grupo.
2. Controle de Mensagem (XIB): Regulação da largura de banda de características por agente na topologia aprendida para comprimir mensagens, retendo apenas o conteúdo relevante para a tarefa.

2.1 Fundamentação Teórica

O HIBCG é construído sobre cinco proposições-chave derivadas da regra da cadeia do GIB:

• Decomposição de Duplo Caminho (Prop. 4.1): O fluxo total de informação decompõe-se em um caminho estrutural (AIB: quais arestas manter) e um caminho de mensagem condicional (XIB: o que flui nas arestas sobreviventes). Estes não são regularizadores paralelos, mas termos de uma única decomposição.
• Limite Mais Apertado via Priors Condicionais ao Grupo (Prop. 4.2): Um prior de bloco-diagonal alinhado ao grupo apertar estritamente o limite variacional no aprendizado de topologia em comparação com um prior plano (isotrópico). A melhoria é proporcional à qualidade da estrutura de grupo; se os grupos forem não triviais, o limite é estritamente mais apertado. Isso fornece uma garantia de "sem arrependimento": injetar informações de grupo nunca prejudica o desempenho.
• Decomposição em Blocos (Prop. 4.3): O prior estrutural permite que a perda se decomponha aditivamente através dos blocos de grupo (intra-grupo vs. inter-grupo). Isso permite pesos de capacidade independentes para diferentes blocos de arestas.
• Relevância via Perda TD (Prop. 4.4): A perda padrão de Diferença Temporal (TD) em MARL de decomposição de valor (por exemplo, QMIX) maximiza implicitamente o termo de relevância do IB. Assim, o HIBCG não requer um estimador separado de informação mútua para relevância.
• Alocação Ótima de Capacidade (Prop. 4.5): A alocação do orçamento de compressão através dos canais segue um princípio de preenchimento de água (water-filling). A utilidade marginal é equalizada através dos canais ativos, o que significa que ligações de alta utilidade (por exemplo, coordenação intra-grupo crítica) retêm mais capacidade, enquanto ligações de baixa utilidade (por exemplo, arestas inter-grupo redundantes) são podadas ou comprimidas agressivamente.

2.2 Arquitetura

O HIBCG opera em três etapas (Figura 2):

1. Etapa 1 (Inicialização): Um módulo de Grafo de Coordenação Consciente de Grupo (GACG) produz um grafo inicial consciente de grupo $A^{(0)}$ e uma partição de grupo $\mathcal{G}$ a partir das observações dos agentes.
2. Etapa 2 (Poda Estrutural Heterogênea): Em cada camada GNN $l$, um codificador estrutural Gaussiano refina a topologia. Um prior de bloco-diagonal alinhado ao grupo aplica pressão KL assimétrica: uma variância maior $\sigma^2_{0, \text{intra}}$ preserva arestas intra-grupo densas, enquanto uma variância menor $\sigma^2_{0, \text{inter}}$ poda agressivamente arestas inter-grupo. Isso resulta em um grafo esparso com blocos densos e ligações seletivas entre blocos.
3. Etapa 3 (Compressão de Mensagem + Decisão): Após $L$ camadas, um codificador variacional por agente comprime a representação agregada em um código de baixa largura de banda. Este código é concatenado com entradas locais para o cálculo do valor-Q.

A perda de treinamento final combina o erro TD, um regularizador de partição de grupo e penalidades KL de forma fechada tanto para a poda de arestas (AIB) quanto para a compressão de mensagens (XIB), ponderadas por parâmetros de capacidade que aproximam a alocação de preenchimento de água.

3. Contribuições Chave

1. Primeiro Aprendizado de Grafo de Coordenação Heterogêneo: O HIBCG é o primeiro método a aprender conjuntamente a existência de arestas (com controle de densidade consciente de grupo por bloco) e a capacidade de informação da aresta (com alocação de largura de banda por agente) usando penalidades KL Gaussianas de forma fechada, por camada.
2. Garantias Teóricas: O artigo estabelece propriedades formais do grafo aprendido, incluindo a decomposição do objetivo, o apertamento provável do limite variacional por priores alinhados ao grupo e a natureza de preenchimento de água da alocação de capacidade.
3. Validação Empírica: Experimentos extensivos demonstram desempenho state-of-the-art com sobrecarga mínima (3,8% de tempo de relógio).

4. Resultados Experimentais

O HIBCG foi avaliado em SMACv1, SMACv2 e MAgent Battle (até 100 agentes), comparando-se com seis baselines externos (incluindo QMIX, CommFormer, MAGI e GACG) e ablações internas.

• Desempenho em Tarefas Heterogêneas: O HIBCG alcança ganhos significativos em mapas ricos em funções e heterogêneos. No MMM2 do SMACv1 (3 tipos de unidades), o HIBCG alcança uma taxa de vitória de 81,4%, superando o CommFormer (77,4%) e o HIB-flat (54,2%).
• Escalabilidade: No MAgent Battle, o HIBCG é o único método a convergir e alcançar retornos positivos em $n=100$ agentes. Métodos existentes como GACG e CommFormer falham em convergir ou colapsam nessa escala. O HIBCG mantém uma razão consistente de perda AIB cruzada/intra de $\approx 906\times$ através das escalas ($n=36, 64, 100$), demonstrando invariância arquitetônica.
• Controle Negativo: No mapa homogêneo 25m (25 fuzileiros idênticos), o HIBCG desempenha de forma comparável ao HIB-flat, confirmando que o prior de grupo não adiciona custo quando a partição é trivial, conforme previsto pela Proposição 4.2.
• Estudos de Ablação: Remover qualquer um dos caminhos estrutural (AIB) ou de mensagem (XIB) degrada o desempenho em mapas heterogêneos, confirmando que a compressão estrutural e de mensagem fornecem benefícios complementares. Reverter o prior (tornando arestas inter-grupo mais densas que intra-grupo) em mapas heterogêneos prejudica significativamente o desempenho, validando o papel do prior alinhado ao grupo.

5. Significado e Alegações

O artigo alega que o HIBCG fornece um quadro principista para aprender grafos de coordenação que respeitam a heterogeneidade estrutural das tarefas multiagente. Ao alinhar o prior estrutural com a partição de grupo dos agentes, o HIBCG:

• Desacopla Topologia e Conteúdo: Separa o aprendizado de "quem comunica" de "o que é comunicado", permitindo controle diferencial sobre a densidade de arestas e a largura de banda de mensagens.
• Fornece Segurança Teórica: O prior alinhado ao grupo oferece uma garantia de "sem arrependimento"; é provadamente não pior que um prior plano e estritamente melhor quando estruturas de grupo existem.
• Habilita Escalabilidade: O método escala com sucesso para 100 agentes, um regime onde aprendizes de grafos esparsos existentes falham, podando efetivamente as arestas candidatas $O(n^2)$ para uma estrutura esparsa relevante para a tarefa.

Os autores notam uma limitação: em observações de alta dimensionalidade (por exemplo, MAgent), o caminho de compressão de mensagens (XIB) pode colapsar para seu prior, reduzindo efetivamente o HIBCG a um aprendiz apenas de topologia. No entanto, as garantias do lado da topologia permanecem inalteradas. Sugere-se trabalho futuro para seleção de grupo totalmente baseada em dados e extensões de fator-grafo dinâmico.