Resumo Técnico: Grafos de Coordenação para Aprendizado por Reforço Multiagente com Restrições (CG-CMARL)

1. Formulação do Problema

O artigo aborda o Aprendizado por Reforço Multiagente com Restrições (CMARL), um domínio onde múltiplos agentes cooperativos devem maximizar um objetivo primário enquanto satisfazem restrições de segurança (ex: evitar colisões, orçamentos de energia). Os autores identificam dois desafios interligados:

1. Escalabilidade: O espaço de ações conjuntas cresce exponencialmente com o número de agentes ($N$), tornando abordagens centralizadas intratáveis para tamanhos de equipe moderados.
2. Acoplamento de Restrições: As restrições de segurança frequentemente acoplam agentes de formas que as estruturas de recompensa sozinhas não capturam. Aprendizes independentes que otimizam seus próprios multiplicadores de Lagrange podem, coletivamente, violar restrições globais, enquanto métodos primal-dual centralizados exigem acesso ao estado global e ao espaço de ação conjunta, negando os benefícios de abordagens fatoradas.

O problema é formalizado como um Processo de Decisão de Markov com Restrições (CMDP) onde o objetivo é maximizar a recompensa primária descontada esperada $V^\pi_0$ sujeito a recompensas de restrição $V^\pi_j$ que excedam limiares específicos. Os autores assumem transições independentes (os próximos estados dos agentes dependem apenas de suas próprias ações) e fatoração de recompensa aditiva sobre um grafo de coordenação, onde as recompensas se decompõem em componentes regionais (especificamente regiões de pares).

2. Metodologia: CG-CMARL

O framework proposto, CG-CMARL, integra Grafos de Coordenação (CG) com dualidade de Lagrange para alcançar a satisfação de restrições de forma escalável e descentralizada. O método opera sob um paradigma de Treinamento Centralizado, Execução Descentralizada (CTDE).

2.1 Arquitetura de Função Q de Duas Cabeças

Em vez de aprender uma única função Q para um sinal de recompensa combinado (o que exigiria retreinamento para diferentes compensações), o CG-CMARL mantém duas funções Q separadas por região:

• Cabeça Primária ($Q_{prim}$): Aprende a função Q regional ótima para o objetivo primário usando Q-learning padrão.
• Cabeça de Custo ($Q_{cost}$): Aprende a recompensa de restrição esperada (ex: custo de colisão) sob a política gananciosa induzida pela cabeça primária. Crucialmente, a cabeça de custo não maximiza seu próprio valor; ela avalia as consequências das decisões do agente primário. Isso garante uma composição coerente no momento da seleção de ações.

2.2 Troca de Lagrange e Varredura de Pareto

No momento da execução, as duas cabeças são combinadas via um multiplicador de Lagrange $\lambda$:
$$Q_{aug, R}(s_R, a_R) = Q_{prim, R}(s_R, a_R) + \lambda Q_{cost, R}(s_R, a_R)$$

• Treinamento: Os agentes mantêm multiplicadores locais $\lambda_i$ atualizados via ascensão dual projetada baseada nas violações de restrição observadas. O multiplicador médio $\bar{\lambda}$ é usado durante a seleção de ações.
• Avaliação: Ao varrer $\lambda$ sobre um intervalo em um único modelo treinado, o sistema traça a fronteira de Pareto completa entre objetivo e restrição sem necessidade de retreinamento. Isso desacopla a compensação da restrição do processo de aprendizado.

2.3 Passagem de Mensagens Max-Sum

Para coordenar ações através do grafo de fatores sem computação centralizada, o método emprega passagem de mensagens Max-Sum:

• Agentes (nós de variável) e funções Q regionais (nós de fator) trocam mensagens para resolver a otimização combinatória $\max_a \sum_R Q_{aug, R}(s_R, a_R)$.
• Amortecimento (Damping): Como os grafos de coordenação de pares contêm ciclos para $N \ge 3$, o amortecimento de mensagem é aplicado para estabilizar a convergência.
• Complexidade: A complexidade por etapa é polinomial em $N$ ($O(N^2 |A| K)$), uma melhoria significativa em relação à busca exaustiva exponencial $O(|A|^N)$.

2.4 Compartilhamento de Parâmetros

Todas as regiões de pares compartilham um único conjunto de parâmetros da função Q. Como cada região contém exatamente dois agentes, o número de modelos aprendidos é $O(1)$ independentemente do tamanho da equipe $N$, permitindo a escala para grandes equipes.

3. Contribuições Teóricas

O artigo fornece garantias teóricas rigorosas sob suposições leves (transições independentes, fatoração de recompensa, condição de Slater):

• Convergência: O Q-learning de duas cabeças converge quase certamente para a função Q regional ótima e para o valor da restrição sob a política gananciosa primária. O multiplicador de Lagrange médio converge para a solução dual ótima.
• Limite de Erro de Composição: O artigo deriva um limite para a lacuna entre a solução aprendida e o ótimo real, decompondo o erro em quatro fontes interpretáveis:
  1. Erro Estrutural ($\beta$): Surge da aproximação de fatoração (regiões sobrepostas).
  2. Erro de Coordenação ($\epsilon_{MS}$): Surge da natureza aproximada do Max-Sum em grafos com ciclos.
  3. Erro de Amostragem: Devido a dados finitos ($O(1/\sqrt{n})$).
  4. Erro de Representação: Devido à aproximação de função ($\epsilon_{NN}$).
     O limite quantifica como esses erros se propagam através do backup de Bellman, fornecendo orientação qualitativa para o design do sistema.

4. Resultados Experimentais

O método foi avaliado no benchmark de navegação cooperativa Simple Spread (PettingZoo/MPE) com tamanhos de equipe $N \in \{3, 4, 6, 10\}$.

• Baselines: Comparado contra IQL, QMIX, Deep Coordination Graphs (DCG), MAPPO e MAPPO-Lagrangian.
• Desempenho: O CG-CMARL produz fronteiras de Pareto que dominam todos os baselines. Enquanto outros métodos (QMIX, MAPPO, etc.) exigem execuções de treinamento separadas para razões fixas de modelagem de recompensa (gerando apenas pontos de operação únicos), o CG-CMRL traça toda a curva de compensação a partir de um único modelo.
• Escalabilidade: O método escala para $N=10$ agentes, onde abordagens centralizadas tornam-se intratáveis. A densidade do grafo de coordenação de pares aumenta com $N$, mas o método mantém o desempenho, com o erro estrutural permanecendo pequeno na prática devido ao fraco acoplamento entre as penalidades de colisão em relação às recompensas de marcos (landmarks).
• Segurança: O método equilibra efetivamente cobertura (objetivo primário) e evasão de colisão (restrição), com o multiplicador de Lagrange direcionando com sucesso a política para a viabilidade.

5. Significância e Alegações

O artigo afirma que o CG-CMARL é o primeiro trabalho a combinar a escalabilidade de funções de valor fatoradas (via grafos de coordenação) com as capacidades de tratamento de restrições de métodos de Lagrange em uma arquitetura descentralizada com garantias de convergência.

As principais alegações incluem:

• Desacoplamento do Aprendizado e da Compensação: Ao separar o aprendizado das recompensas primárias e de restrição, o método permite a exploração pós-hoc da fronteira de Pareto sem retreinamento, uma capacidade que falta em abordagens padrão de RL com restrições.
• Descentralização Escalável: O framework alcança complexidade de modelo $O(1)$ e complexidade de seleção de ação polinomial, superando a "maldição da dimensionalidade" nos espaços de ação conjunta multiagente.
• Interpretabilidade: O limite de erro de composição liga explicitamente as lacunas de desempenho a escolhas específicas de design (topologia do grafo, amostragem, capacidade da rede), oferecendo uma maneira fundamentada de analisar e melhorar o sistema.

Os autores reconhecem limitações, observando que o grafo de pares torna-se denso para $N$ grande (aumentando o cálculo do Max-Sum) e que a formulação de duas cabeças envolve uma aproximação conservadora (a cabeça de custo avalia a política gananciosa primária, não a política final). Eles sugerem que trabalhos futuros poderiam explorar topologias de grafos esparsos/dinâmicos e uma formulação aumentada por $\lambda$ (condicionando a função Q diretamente em $\lambda$) para resolver a aproximação conservadora teoricamente, embora ao custo de maior complexidade de amostragem.