Resumo Técnico: History Matters: Meta-Policy Delegation with Heterogeneous Multi-Agent Reinforcement Learning

1. Formulação do Problema

O artigo aborda o desafio da delegação de tarefas em Sistemas Multiagentes (MAS) heterogêneos, especificamente aqueles compostos por agentes de IA (ex: Large Language Models) com capacidades, estruturas de propriedade e custos operacionais variados. O problema central é determinar qual agente deve executar uma etapa específica de uma tarefa e como os agentes devem delegar tarefas entre si para minimizar os custos totais de execução, mantendo uma execução de tarefa eficaz.

Os autores modelam isso como um Jogo de Markov Colaborativo (MG) construído sobre uma camada de políticas de tarefa pré-treinadas ($\mu_i$). Diferente de abordagens existentes que dependem de roteadores centralizados ou cascatas de modelos estáticos, este trabalho trata a delegação como uma camada de decisão sequencial explícita, onde os agentes escolhem executar, delegar ou permanecer inativos. O sistema deve navegar por três restrições estruturais específicas:

1. Restrições de Gerenciamento: Controle hierárquico e unidirecional, onde superiores podem ordenar a delegação para subordinados.
2. Restrições de Delegação: Um grafo direcionado geral que permite que qualquer agente delegue para qualquer outro, removendo a hierarquia estrita.
3. Troca de Dinheiro: Um mecanismo onde agentes incentivam seus pares a aceitar tarefas delegadas dispendiosas por meio de moeda interna transferível.

Uma lacuna teórica crítica identificada é que o Aprendizado por Reforço Multiagente (MARL) tradicional em ambientes totalmente observáveis frequentemente restringe as políticas a dependerem apenas do estado atual (políticas de Markov). O artigo argumenta que políticas dependentes de histórico — que condicionam ações em ações conjuntas passadas e interações — são necessárias para sustentar reciprocidade, confiança e incentivos intertemporais, mesmo quando o estado do ambiente é totalmente observável.

2. Metodologia

2.1. Estruturas para Colaboração

O artigo propõe duas novas estruturas para facilitar a delegação:

A. Formulação de Política Dependente de Histórico
Em vez de políticas de Markov padrão $\pi(s)$, os autores definem políticas $\pi(h_t)$ que dependem do histórico público $h_t = (x_1, a_1, \dots, x_t)$, incluindo ações conjuntas anteriores.

• Motivação: Em um exemplo de jogo de dois passos, os autores demonstram que políticas dependentes de histórico podem alcançar um equilíbrio de Nash com retornos maiores (ex: o Agente A incorre em um custo precocemente, e o Agente B retribui posteriormente) que é impossível sob restrições de Markov.
• Algoritmo: Um Algoritmo de Iteração de Valor de Nash de Dois Passos é desenvolvido para encontrar equilíbrios de Nash determinísticos e de subjogo perfeito que favoreçam agentes específicos. Isso é estendido para jogos de $n$ passos via indução.

B. Mecanismo de Transferência de Dinheiro Virtual
Para tornar as políticas dependentes de histórico práticas em MARL sem depender de normas sociais complexas, os autores introduzem um sistema de transferência de dinheiro.

• Aumento de Estado: O estado de cada agente é aumentado com um saldo de dinheiro $w_i$, formando $\tilde{s}_i = (s, w_i)$.
• Separação de Preocupações: O "dinheiro" é distinto da recompensa ambiental. O dinheiro serve como um livro de registro interno que registra interações passadas e facilita a delegação, enquanto o objetivo permanece maximizar as recompensas ambientais.
• Mecanismo: Os agentes escolhem ações físicas e ações de transferência de dinheiro ($p_{ij}$). As transferências são limitadas pelo saldo atual do agente. Se um agente não possui fundos, a ação conjunta desejada torna-se inviável. Isso cria um ambiente com restrição de orçamento que naturalmente incentiva o comportamento cooperativo ao longo do tempo.

2.2. Configuração Experimental

Os autores validam sua abordagem usando o benchmark GSM8K (problemas matemáticos de nível escolar) com uma "pilha de solucionadores congelada" (frozen solver stack):

• Agentes: Três solucionadores de LLM heterogêneos com diferentes custos e capacidades:
  • Solver A: Nemotron 3 Ultra (Alta capacidade, alto custo).
  • Solver B: Llama 3.2 3B (Capacidade média, custo médio).
  • Solver C: Llama 3.2 1B (Baixa capacidade, baixo custo).
• Treinamento: Um coordenador DQN centralizado é treinado para gerenciar a delegação, enquanto os solucionadores permanecem congelados. O sistema utiliza cache offline de respostas para garantir a reprodutibilidade e eliminar a variância de custo de API durante o treinamento.
• Baselines: Comparações são feitas contra um baseline "Always-Ultra" (enviar todas as tarefas para o agente mais capaz) e um baseline de "Gerenciamento" (delegação hierárquica).

3. Contribuições Principais

1. Delegação como um Problema de Decisão Sequencial: O trabalho formula a delegação não como uma regra de roteamento estática, mas como um problema de decisão multiagente sequencial onde agentes com capacidades pré-treinadas heterogêneas escolhem dinamicamente caminhos de execução ou delegação.
2. Teoria de Política Dependente de Histórico: O artigo introduz e valida teoricamente uma formulação de política dependente de histórico para ambientes totalmente observáveis. Demonstra que condicionar em ações conjuntas passadas pode sustentar equilíbrios de reciprocidade com retornos maiores do que políticas de Markov padrão.
3. Estrutura de Dinheiro Virtual: Uma mecânica prática é proposta onde um saldo de dinheiro transferível e com restrição de orçamento atua como um resumo compacto do histórico de interação. Isso permite que os agentes incentivem a cooperação e a delegação sem alterar a função de recompensa primária do ambiente.
4. Validação Empírica: O estudo fornece evidências numéricas de que as políticas de delegação aprendidas superam significativamente os baselines estáticos em termos de eficiência de custo e retorno.

4. Resultados

4.1. Restrições de Gerenciamento (Hierárquico)

No cenário hierárquico (A $\to$ B $\to$ C):

• Desempenho: O coordenador aprendido via MARL alcançou um retorno de 27,56 comparado ao baseline "Always-Ultra" de 23,90.
• Custo: A política aprendida reduziu o custo por episódio para $0,033 (aprox. $31,1 cumulativo sobre 1000 episódios) versus $0,063 para o baseline (aprox. $60,8 cumulativo).
• Precisão: A política aprendida manteve alta precisão (0,982) em comparação ao baseline (0,971).
• Comportamento: A política aprendeu a depender fortemente do Solver B de custo médio, usando o Solver A apenas quando necessário, e raramente utilizando o Solver C, que é o mais barato.

4.2. Restrições de Delegação (Baseado em Grafo)

No cenário de grafo irrestrito (qualquer agente pode delegar para qualquer outro):

• Desempenho: O coordenador de grafo alcançou um retorno de 25,20, superando o "Always-Ultra" (23,31), mas sendo ligeiramente inferior à política hierárquica congelada (28,70).
• Custo: O custo caiu para $0,043 por episódio (cumulativo $45,5), uma redução de ~37% em relação ao "Always-Ultra" ($66,7).
• Trade-off: A política de grafo utilizou o Solver C com mais frequência e permitiu que múltiplos agentes respondessem simultaneamente. Embora isso tenha aumentado a flexibilidade, resultou em uma precisão ligeiramente menor (0,961) em comparação com a política hierárquica (0,986), sugerindo um trade-off entre redução de custo e otimização estrita de desempenho na ausência de hierarquia.

4.3. Mecanismo de Transferência de Dinheiro

Em um jogo sequencial sintético de dois agentes:

• Sem Dinheiro: Agentes de Q-learning independente falharam em cooperar, resultando em um retorno ambiental de 0, pois ambos os agentes escolheram "Null" (não cooperação).
• Com Dinheiro: A introdução de saldos transferíveis permitiu um equilíbrio totalmente cooperativo. Os agentes transferiram fundos com sucesso para incentivar a ação "Yes", alcançando um retorno ambiental de 990 por episódio.

5. Significância e Alegações

O artigo afirma que sistemas multiagentes eficazes devem ir além do roteamento estático e de políticas simples baseadas em estado. Ao enquadrar a delegação como um jogo sequencial e introduzir políticas dependentes de histórico e dinheiro virtual, os autores demonstram que os agentes podem aprender a coordenar, confiar e alocar recursos de forma eficiente, mesmo em cenários com restrição de custos.

A significância reside em:

• Redução de Custos: Demonstrar que a delegação aprendida pode cortar os custos operacionais em aproximadamente metade, mantendo ou até melhorando o desempenho da tarefa.
• Insight Teórico: Mostrar que a dependência de histórico não é apenas para ambientes parcialmente observáveis, mas é crucial para estabelecer reciprocidade e confiança em configurações multiagentes totalmente observáveis.
• Mecanismo Prático: Fornecer um mecanismo de dinheiro concreto, com restrição de orçamento, que facilita a colaboração sem exigir um complexo ajuste de recompensa externa (reward shaping).

Os autores reconhecem modestamente as limitações, observando que o trabalho ainda não aborda a precificação dinâmica de ações conjuntas baseada em histórico e que algoritmos mais eficientes são necessários para encontrar equilíbrios de Nash em espaços maiores e dependentes de histórico.