Resumo Técnico: Aprendizado por Reforço Multiagente Cooperativo Condicionado por Autômatos (ACC-MARL)

1. Definição do Problema

O artigo aborda o desafio de aprender políticas multi-tarefa e multiagente para equipes cooperativas operando sob treinamento centralizado e execução descentralizada (CTDE). O cenário específico envolve agentes designados com tarefas temporais desconhecidas a priori em tempo de execução, as quais devem completar sem comunicação explícita.

A dificuldade central reside em generalizar para essas tarefas dinâmicas enquanto satisfaz objetivos complexos de longo horizonte. As abordagens existentes que utilizam especificações formais (como Autômatos de Estados Finitos Determinísticos, DFAs) para representar tarefas são frequentemente ineficientes em termos de amostra e limitadas a cenários de tarefa única, exigindo retreinamento para novos objetivos. Além disso, em um contexto multiagente, três desafios primários impedem a viabilidade:

1. Dependência de Histórico: As políticas devem rastrear o progresso da tarefa (histórico) para tomar decisões, quebrando a propriedade de Markov e levando a políticas subótimas.
2. Atribuição de Crédito: A recompensa do nível da equipe é esparsa (concedida apenas após a conclusão total da tarefa), tornando difícil para os agentes discernirem como ações individuais contribuem para o objetivo global.
3. Gargalo de Representação: Aprender simultaneamente representações latentes de DFAs e políticas de controle cria um problema de escalabilidade, particularmente para equipes maiores que dois agentes.

2. Metodologia: Estrutura ACC-MARL

Os autores propõem o Aprendizado por Reforço Multiagente Cooperativo Condicionado por Autômatos (ACC-MARL), uma estrutura que condiciona políticas descentralizadas em representações de tarefas derivadas de DFAs. A abordagem aborda os três desafios através dos seguintes mecanismos:

A. Mitigação da Dependência de Histórico via Reformulação Markoviana

Em vez de condicionar as políticas no histórico bruto de observações, a estrutura aumenta o espaço de estados com o estado atual do DFA mínimo para cada agente.

• Mecanismo: Em cada etapa, o estado do ambiente é rotulado e os DFAs atribuídos são progredidos (atualizados) com base nesses rótulos. As observações dos agentes são aumentadas com as representações mínimas de DFA mais recentes.
• Resultado: Isso transforma o jogo não-Markoviano em um jogo Markoviano sobre o espaço do produto de estados do ambiente e estados de DFA ($S \times D^n$). Os autores provam (Teorema 3.1) que maximizar o retorno neste jogo Markoviano reformulado é equivalente a maximizar a probabilidade de satisfazer os objetivos temporais originais conforme o fator de desconto $\gamma \to 1$.

B. Abordagem da Atribuição de Crédito via Modelagem de Recompensa Baseada em Potencial (PBRS)

Para superar recompensas esparsas, os autores aplicam Modelagem de Recompensa Baseada em Potencial (PBRS).

• Mecanismo: Uma função de potencial $\Phi_i$ é definida para cada agente $i$, retornando 1 se o seu DFA atribuído for satisfeito e 0 caso contrário. A recompensa é modelada pela diferença no potencial entre o estado atual e o próximo: $R_{PBRS} = R_{base} + \gamma \Phi_i(next) - \Phi_i(current)$.
• Resultado: Os agentes recebem feedback positivo denso por completarem suas sub-tarefas específicas, mantendo a garantia teórica de que a política ótima para a recompensa modelada permanece ótima para o objetivo original.

C. Resolução do Gargalo de Representação com Embeddings RAD

Para evitar aprender representações latentes de DFA do zero durante o treinamento (o que causa degradação de desempenho em equipes maiores), a estrutura utiliza Embeddings RAD (ReachAvoidDerived) pré-treinados.

• Mecanismo: Um codificador de Rede de Atenção de Grafo (GATv2) congelado mapeia DFAs para vetores latentes (Embeddings RAD). Esses embeddings são treinados para representar unicamente DFAs minimizados distintos e codificar similaridades semânticas através de uma vasta classe de tarefas temporais.
• Resultado: As políticas condicionam-se a esses embeddings fixos em vez de DFAs brutos ou representações aprendidas. Isso desacopla o aprendizado de representação do aprendizado de controle, permitindo a escalabilidade eficiente para equipes maiores (ex: 4 agentes).

D. Atribuição Ótima de Tarefas

A estrutura aproveita as funções de valor aprendidas para atribuir tarefas de forma ótima em tempo de teste. Ao avaliar o desempenho esperado da equipe (soma das funções de valor) para diferentes permutações de atribuições de tarefas, o sistema pode selecionar uma atribuição Pareto-ótima que maximiza o sucesso geral da equipe, particularmente em ambientes assimétricos.

3. Principais Contribuições

1. Introdução da Estrutura: A proposta do ACC-MARL, uma estrutura para aprender políticas multi-tarefa, multiagente e egocêntricas condicionadas por DFAs.
2. Garantias Teóricas: Prova de que a reformulação Markoviana e a modelagem de recompensa propostas preservam a otimalidade em relação ao problema não-Markoviano original.
3. Solução de Escalabilidade: Demonstração de que o uso de Embeddings RAD pré-treinados supera o gargalo de representação, permitindo o aprendizado eficaz em equipes com mais de dois agentes.
4. Atribuição de Tarefas: Um método para usar funções de valor aprendidas para computar atribuições de tarefas ótimas em tempo de teste.
5. Ferramental: Implementação de uma ferramenta baseada em JAX (DFAx) para operações de DFA paralelizadas e um pacote Python para integrar tarefas de autômatos em aplicações de RL.

4. Resultados Experimentais

A estrutura foi avaliada em um ambiente discreto e totalmente observável chamado TokenEnv, apresentando variantes de dois e quatro agentes com layouts envolvendo botões, portas e tokens.

• Viabilidade e Escalabilidade (Q1 & Q2):
  • Estudos de ablação mostram que, sem as soluções propostas (especificamente PBRS e Embeddings RAD), as políticas falham em convergir ou alcançam baixas taxas de sucesso (<0.5).
  • Em ambientes de 2 agentes, tanto os encoders pré-treinados quanto os não treinados apresentam desempenho semelhante, embora os embeddings pré-treinados ofereçam menor variância.
  • Em ambientes de 4 agentes, as políticas que utilizam Embeddings RAD pré-treinados superam significativamente aquelas que aprendem representações do zero, confirmando que o pré-treinamento é crucial para a escalabilidade.
• Generalização (Q3):
  • Políticas treinadas em RAD DFAs generalizam para classes de tarefas não vistas (Reach e ReachAvoid) e para DFAs fora da distribuição (OOD) com mais estados do que os vistos durante o treinamento.
  • Embeddings pré-treinados melhoram especificamente o desempenho em tarefas que envolvem restrições de "Evitar" (condições irrecuperáveis).
• Atribuição de Tarefas (Q4):
  • Em ambientes simétricos (Buttons), a ordem de atribuição de tarefas teve impacto negligenciável.
  • Em ambientes assimétricos (Rooms), a atribuição de tarefas ótima derivada de funções de valor aprendidas melhorou significamente as probabilidades de sucesso da equipe em comparação com a atribuição aleatória.
• Comportamentos Emergentes (Q5):
  • A análise qualitativa revela habilidades cooperativas emergentes, como agentes segurando portas para colegas para economizar tempo e "encurtar" tarefas (ex: um agente destrancando uma porta para permitir que outro siga um caminho mais curto).

5. Significância e Alegações

O artigo afirma ser o primeiro trabalho a utilizar especificações formais (DFAs) em um cenário de MARL cooperativo multi-tarefa onde as tarefas são atribuídas em tempo de execução. Sua significância reside em:

• Unindo Métodos Formais e MARL: Estende o aprendizado condicionado por autômatos de um cenário de agente único para ambientes multiagente, permitindo a decomposição de objetivos de equipe complexos em sub-tarefas.
• Resolvendo o Desafio de Escalabilidade: Ao desacoplar o aprendizado de representação via embeddings pré-treinados, aborda os gargalos de desempenho que anteriormente limitavam o MARL condicionado por autômatos a equipes pequenas.
• Otimização: Fornece uma abordagem teoricamente fundamentada que garante o comportamento de equipe ótimo enquanto permite a atribuição de crédito eficiente e a generalização.

Os autores observam limitações, incluindo a suposição de funções de rotulagem fixas, observabilidade total e o custo computacional de enumerar atribuições de tarefas para equipes muito grandes. Eles sugerem trabalhos futuros em observabilidade parcial, rotulagem dinâmica e domínios contínuos.