A Distributed Primal-Dual Method for Constrained Multi-agent Reinforcement Learning with General Parameterization

Resumo Técnico: Um Método Primal-Dual Distribuído para Aprendizado por Reforço Multiagente Constrained com Parametrização Geral

Formulação do Problema
Este artigo aborda o desafio do Aprendizado por Reforço Multiagente Cooperativo e Constrained (CMARL) em um ambiente de rede. O problema é enquadrado como um Jogo de Markov Constrained (CMG) envolvendo $N$ agentes operando em um ambiente compartilhado. Os agentes cooperativamente visam minimizar uma função objetivo global, definida como a média dos custos esperados locais, sujeita a $K$ restrições globais. Essas restrições também são formuladas como a média dos custos de restrição locais entre todos os agentes.

Uma distinção crítica deste trabalho é a exigência de aprendizado online totalmente descentralizado. Diferentemente do treinamento centralizado ou de métodos que exigem coordenação durante a execução, a abordagem proposta assume que os agentes atuam independentemente, utilizando apenas informações locais e comunicação local com vizinhos. O problema é complicado pelo fato de que, diferentemente do RL constrained de agente único, o CMARL cooperativo frequentemente exibe uma lacuna de dualidade não nula, particularmente ao usar aproximação de função geral (políticas parametrizadas). Essa lacuna introduz complexidade inerente em satisfazer restrições globais enquanto se otimiza o objetivo global.

Metodologia
Os autores propõem um algoritmo primal-dual distribuído baseado na estrutura ator-crítico. A inovação central reside em como os agentes lidam com os multiplicadores de Lagrange associados às restrições globais.

1. Estimação Local dos Multiplicadores: Em vez de depender de um coordenador central para calcular multiplicadores de Lagrange globais, cada agente $n$ mantém uma estimativa local $\hat{\lambda}_n$ do vetor de multiplicadores global $\lambda$.
2. Objetivo Decomposto: O Lagrangiano global é reformulado usando essas estimativas locais. Os agentes otimizam um objetivo Lagrangiano local que depende de seus próprios parâmetros de política $\theta_n$ e de suas estimativas locais de multiplicadores $\hat{\lambda}_n$.
3. Atualização em Três Escalas de Tempo: O algoritmo opera em três escalas de tempo distintas para garantir convergência:
   • Escala de Tempo Mais Rápida (Crítico): Os agentes atualizam seus aproximadores locais de função valor (críticos) usando Aprendizado por Diferença Temporal (TD) para estimar o custo Lagrangiano local.
   • Escala de Tempo Intermediária (Ator): Os agentes atualizam seus parâmetros de política (atores) usando um teorema de gradiente de política adaptado para o cenário multiagente, utilizando a função vantagem estimada.
   • Escala de Tempo Mais Lenta (Dual/Multiplicadores): Os agentes atualizam suas estimativas locais de multiplicadores de Lagrange. Essa atualização envolve dois passos: um passo de consenso onde os agentes mediam suas estimativas com os vizinhos (usando uma matriz de comunicação duplamente estocástica) e um passo de ascensão baseado na violação local da restrição.
4. Mecanismo de Consenso: O algoritmo impõe consenso entre as estimativas locais de multiplicadores $\hat{\lambda}_n$ através da rede. A análise teórica prova que essas estimativas locais convergem para um valor comum, efetivamente reconstruindo o multiplicador global sem coordenação centralizada.

Principais Contribuições
O artigo faz quatro contribuições primárias:

1. Formulação Distribuída: Introduz uma formulação distribuída inovadora para multiplicadores de Lagrange em CMARL cooperativo, onde cada agente mantém e atualiza suas próprias estimativas locais usando apenas informações locais e comunicação com vizinhos.
2. Desenvolvimento do Algoritmo: Desenvolve um algoritmo primal-dual online distribuído utilizando métodos ator-crítico com aproximação de função geral (críticos lineares e políticas parametrizadas).
3. Garantias de Convergência: Os autores fornecem provas teóricas demonstrando que os multiplicadores de Lagrange locais alcançam consenso quase certamente e que o algoritmo geral converge para um ponto de equilíbrio do sistema dinâmico projetado.
4. Análise de Sub-otimalidade e Viabilidade: O artigo analisa a viabilidade das restrições no equilíbrio e quantifica a sub-otimalidade da solução. Deriva um limite superior para a lacuna de dualidade do problema parametrizado, contabilizando erros introduzidos pela parametrização da política e pelo processo de consenso.

Resultados Experimentais
Para validar a abordagem, os autores avaliaram o algoritmo em um jogo de Cournot cooperativo e constrained com dinâmicas estocásticas. Neste cenário, os agentes atuam como produtores em um mercado, escolhendo níveis de produção para maximizar o lucro (minimizar o custo) enquanto aderem a restrições baseadas em preços.

• Consenso: Os resultados da simulação (Figura 1) demonstram que os multiplicadores de Lagrange estimados localmente para diferentes agentes convergem para um valor de consenso.
• Desempenho: As curvas de treinamento (Figura 2) mostram que o algoritmo minimiza com sucesso o custo global da função objetivo, mantendo as violações de restrições globais próximas de zero.

Significado e Alegações
O artigo alega abordar uma lacuna na literatura onde poucos métodos lidam com problemas gerais de CMARL com custos locais acoplados e restrições globais de maneira totalmente descentralizada. Enquanto trabalhos existentes frequentemente dependem de treinamento centralizado, compartilhamento de parâmetros com agentes homogêneos ou comunicação no momento da execução, este método permite aprendizado online totalmente descentralizado.

Os autores enquadram modestamente sua contribuição como uma extensão constrained de métodos existentes de ator-crítico distribuído sem restrições (referenciando especificamente trabalhos anteriores sobre MARL sem restrições). Eles reconhecem que, devido à lacuna de dualidade não nula em configurações cooperativas parametrizadas, o algoritmo converge para um ponto de equilíbrio que pode ser sub-ótimo em comparação com a solução exata do problema não parametrizado. No entanto, o método proposto fornece uma solução escalável e descentralizada que garante satisfação de restrições em cenários complexos do mundo real, como redes inteligentes e sistemas autônomos, sem os gargalos de escalabilidade das abordagens centralizadas.