Resumo Técnico: ACPO: Otimização de Política em Cadeia de Agentes para Aprendizado por Reforço Multiagente

Problema

O Aprendizado por Reforço Multiagente (MARL) cooperativo visa encontrar políticas descentralizadas que maximizem conjuntamente um retorno compartilhado. Sob o paradigma de Treinamento Centralizado com Execução Descentralizada (CTDE), um desafio fundamental permanece: computar o gradiente da política conjunta diretamente é difícil. As abordagens existentes geralmente se dividem em duas categorias, ambas com limitações significativas:

1. Otimização de Política Independente (ex: MAPPO, MADDPG): Os agentes atualizam suas políticas de forma independente usando críticos centralizados. Embora escaláveis, esses métodos carecem de garantias gerais de melhoria da política conjunta porque não levam em conta a não-estacionaridade introduzida pelas políticas mutáveis de outros agentes. A convergência só é garantida sob fortes suposições estruturais, como a decomposição de valor.
2. Otimização de Melhor Resposta Alternada (ex: HAPPO, HATRRO): Os agentes atualizam sequencialmente, tratando as políticas dos outros como fixas. Embora isso garanta a melhoria monotônica do retorno conjunto em cada etapa, o ponto fixo é um Equilíbrio de Nash (NE). Em configurações cooperativas, um NE pode ser arbitrariamente subótimo em comparação ao verdadeiro ótimo social, e os agentes não possuem mecanismo para escapar desses equilíbrios subótimos.

O artigo postula que nenhuma das abordagens atinge efetivamente a política conjunta ótima do MMDP subjacente sem suposições restritivas ou convergência para equilíbrios subótimos.

Metodologia: Otimização de Política em Cadeia de Agentes (ACPO)

A principal contribuição do artigo é a derivação de uma decomposição descentralizada exata do gradiente da política conjunta. Isso é alcançado através da introdução de um novo formalismo, o MDP de Crença em Cadeia de Agentes (AC-BMDP), que transforma o problema de decisão conjunta simultânea em um processo de decisão serializado com informação imperfeita.

1. O Agent-Chained Belief MDP (AC-BMDP)

Motivado por resultados da teoria dos jogos que afirmam que jogos simultâneos podem ser recapitulados como processos serializados com informação imperfeita, os autores decompõem cada passo de tempo do ambiente $t$ em $N$ micro-passos, um para cada agente $i \in \{1, \dots, N\}$.

• Serialização: Os agentes assumem ações sequencialmente dentro de um único passo de tempo. O agente $i$ age após os agentes $1$ até $i-1$.
• Aumento de Estado: O estado para o agente $i$ é aumentado com uma crença $b^{(i)}_t$ sobre as ações realizadas pelos agentes precedentes ($\vec{a}^{<i}_t$).
• Execução Descentralizada: Como as ações realizadas dos agentes precedentes não são observadas durante a execução, a crença é construída a partir das distribuições de ação ($\phi^{(j)}_t$) dos agentes precedentes. Essas distribuições são funções determinísticas do estado compartilhado e das políticas dos agentes, tornando-as acessíveis sem comunicação.
• Operadores de Bellman em Cadeia: A função de valor para o agente $i$, $Q^{(i)}$, é definida recursivamente. O valor do agente $i$ depende do valor do agente $i+1$ (o próximo agente na cadeia). Apenas o último agente ($N$) recebe a recompensa do ambiente e faz o bootstrap para o valor do primeiro agente no próximo passo de tempo. Essa "encadeamento" permite a atribuição de crédito sem assumir uma função de valor conjunta decomponível.

2. Fundamentos Teóricos

O artigo estabelece dois teoremas fundamentais:

• Teorema do Gradiente de Política em Cadeia de Agentes: O gradiente da política para o AC-BMDP pode ser computado usando uma função de score padrão e um crítico descentralizado $Q^{(i)}$ que condiciona apenas no próprio estado do agente e na crença sobre as ações precedentes.
• Teorema de Decomposição do Gradiente de Política Multiagente: Mostra-se que o gradiente da política conjunta do MMDP original é exatamente equivalente a uma soma de $N$ termos independentes por agente derivados do AC-BMDP.
  $$\nabla_\theta J(\vec{\pi}_\theta) = \frac{1}{(\gamma')^{N-1}} \sum_{i=1}^N \mathbb{E} \left[ \nabla_\theta \log \pi^{(i)}_\theta(a^{(i)} | s, b^{(i)}) \cdot Q^{(i)}([s, b^{(i)}], a^{(i)}) \right]$$
  Crucialmente, esta decomposição não requer suposições estruturais na função de valor conjunta (ao contrário de VDN ou QMIX) e evita os pontos fixos subótimos de atualizações alternadas.

3. Instanciações Algorítmicas

Os autores instanciam o ACPO em duas formas práticas:

• ACPPO (On-Policy): Um algoritmo baseado em PPO onde cada agente otimiza um objetivo substituto clipado usando as estimativas de vantagem em cadeia. A vantagem é computada via Estimativa de Vantagem Generalizada (GAE) que soma os resíduos de Diferença Temporal (TD) em cadeia através da cadeia de agentes.
• ACTD3 (Off-Policy): Um algoritmo baseado em TD3 para controle contínuo, onde os agentes mantêm críticos gêmeos seguindo a estrutura de Bellman em cadeia.

Aproximação de Crença:

• Em configurações de Observabilidade Total (MMDP), os agentes computam crenças exatamente consultando as redes de política dos agentes precedentes.
• Em configurações de Observabilidade Parcial (Dec-POMDP), os agentes utilizam uma Rede de Crença de Ação para prever as distribuições de ação dos agentes precedentes com base em seu próprio histórico local, treinada via perda de divergência KL contra o alvo centralizado.

Principais Contribuições

1. Formalização do AC-BMDP: A introdução de um framework formal que combina serialização com aumento de crença, permitindo o aprendizado de política conjunta ótima sob CTDE sem suposições de decomposição de valor.
2. Decomposição Exata de Gradiente: A prova de que o gradiente da política conjunta admite uma decomposição exata em termos por agente, permitindo que atualizações independentes constituam um único passo de gradiente no objetivo conjunto.
3. Convergência para a Política Conjunta Ótima: Ao contrário de métodos alternados que convergem para Equilíbrios de Nash, o artigo prova que, em configurações tabulares, a Iteração de Política em Cadeia de Agentes (ACPI) converge para a política conjunta ótima do MMDP subjacente.
4. Algoritmos Escaláveis: O desenvolvimento de ACPPO e ACTD3, que demonstram que o encadeamento de agentes pode ser aplicado tanto a algoritmos de RL on-policy quanto off-policy.

Resultados Experimentais

Os autores avaliaram o ACPO em três benchmarks padrão: Multi-Robot Warehouse (RWARE), SMACv2 e MA-MuJoCo.

• Desempenho: O ACPO (especificamente o ACPPO) superou consistentemente as bases fortes, incluindo MAPPO (otimização independente), HAPPO/HATRPO (otimização alternada) e métodos de decomposição de valor (VDN, QMIX).
• Escalabilidade com Agentes: Uma descoberta crítica é que a lacuna de desempenho entre o ACPO e as bases aumenta conforme o número de agentes cresce. No RWARE, a vantagem foi mais pronunciada nos cenários de 8 e 12 agentes, sugerindo que o ACPO é particularmente eficaz em ambientes de alta coordenação e densos.
• Desempenho Off-Policy: A variante off-policy, ACTD3, também superou as bases (MADDPG, HATD3) no MA-MuJoCo, demonstrando a generalidade do mecanismo de encadeamento de agentes.
• Estudos de Ablação: Remover o mecanismo de encadeamento de agentes (reduzindo o ACPPO para MAPPO com entradas de crença) resultou em desempenho semelhante ao MAPPO, confirmando que os ganhos se devem ao cálculo de vantagem em cadeia, e não meramente à adição de estados de crença.
• Eficiência: Embora o ACPO exija o cálculo sequencial de crença, o tempo de treinamento (wall-clock) permanece comparável ao MAPPO e é substancialmente mais rápido que os métodos alternados (HAPPO/HATRPO), que exigem atualizações sequenciais de agentes durante o treinamento.

Significância e Alegações

O artigo alega que o ACPO fornece uma solução fundamentada para o problema de MARL cooperativo sob CTDE. Sua significância reside em:

• Unificação de Benefícios: Ele une os benefícios das atualizações independentes (escalabilidade) e das atualizações alternadas (garantias de melhoria monotônica) enquanto evita seus respectivos problemas (não-estacionaridade e equilíbrios de Nash subótimos).
• Rigor Teórico: Oferece a primeira decomposição exata do gradiente da política conjunta que não depende de suposições de decomposição de valor, garantindo teoricamente a convergência para o ótimo social em configurações tabulares.
• Eficácia Prática: Resultados empíricos sugerem que a coordenação explícita via encadeamento de crença é um mecanismo superior para lidar com tarefas complexas de coordenação multiagente em comparação aos métodos atuais de estado da arte, particularmente conforme a complexidade da população de agentes cresce.

Os autores notam modestamente as limitações, especificamente que o cálculo da crença escala linearmente com o número de agentes (levando a $O(N^2)$ passagens de ida/forward passes) e que as garantias teóricas atuais dependem de observabilidade total (MMDP), deixando a extensão para Dec-POMDPs gerais como um trabalho futuro.