CAPO: Counterfactual Credit Assignment in Sequential Cooperative Teams

Título: CAPO: Atribuição de Crédito Contrafactual em Equipes Cooperativas Sequenciais

1. O Problema

O artigo aborda o desafio da atribuição de crédito em sistemas multiagente cooperativos onde:

• Os agentes atuam em uma ordem fixa (sequencial).
• Existe apenas uma recompensa de equipe compartilhada (sinal único).
• Os agentes são atualizados um de cada vez dentro de um mesmo lote de treinamento (atualização sequencial).

Desafios Principais:

1. Ambiguidade: É difícil determinar quanto cada agente contribuiu para a recompensa global.
2. Não Estacionariedade: Ao atualizar um agente "a montante" (upstream), a distribuição de comportamento dos agentes "a jusante" (downstream) muda. Isso torna os dados coletados anteriormente (sob a política antiga) off-policy para os agentes subsequentes no mesmo lote, criando um viés de atualização.
3. Limitações das Abordagens Atuais:
   • Críticos Centralizados: Escalabilidade exponencial com o número de agentes.
   • Métodos de Amostragem por Importância (IS): A variância cresce exponencialmente com o número de agentes já atualizados (ex: HAPPO, HA-GRPO).
   • Replay de Ambiente: Métodos como C3 exigem reavaliação da recompensa no ambiente real para cada contrafactual, o que é custoso (ex: em pipelines de LLMs ou execução de código).

2. Metodologia

Os autores propõem uma nova abordagem baseada em duas inovações teóricas e algorítmicas:

A. Utilidade Aristocrata Sequencial (SeqAU)

Estendendo o trabalho clássico de Wolpert e Tumer (2002) sobre "opacidade" e "aprendibilidade", os autores definem a SeqAU como o sinal de aprendizado único por agente que maximiza a aprendibilidade individual.

• Definição: A SeqAU é dada pela recompensa da equipe menos uma linha de base condicional ao prefixo de ações anteriores:
  $$A^{SeqAU}_k = \mathbb{E}[R | a_{\leq k}] - \mathbb{E}[R | a_{< k}]$$
• Propriedade: É a única linha de base dependente do prefixo que maximiza a razão sinal-ruído (aprendibilidade) para cada agente, independentemente da estrutura da recompensa.

B. Algoritmo CAPO (Counterfactual Advantage Policy Optimization)

O CAPO é um algoritmo de gradiente de política sem crítico (critic-free) que estima a vantagem da SeqAU de forma tratável através de três componentes:

1. Decomposição Aditiva de Recompensa:

   • Assume-se que a recompensa esperada pode ser aproximada por uma soma de contribuições individuais: $f(a) \approx \sum \phi_k(a_k)$.
   • Os componentes $\phi_k$ são estimados via regressão ridge (mínimos quadrados) sobre o lote de dados, permitindo uma atribuição de crédito em forma fechada sem treinar um crítico neural complexo.

2. Identidade de Cancelamento a Montante (Upstream-Cancellation):

   • Ao calcular a diferença entre as expectativas condicionais, as contribuições dos agentes anteriores ao agente atual ($j < k$) cancelam-se exatamente.
   • Isso reduz a vantagem a duas partes:
     • Efeito Direto ($D_k$): A contribuição direta do agente $k$ (calculada em forma fechada).
     • Efeito Indireto ($I_k$): Como a ação de $k$ altera a distribuição de ações dos agentes subsequentes ($j > k$) e, consequentemente, suas contribuições de recompensa.

3. Amostragem Fictícia (Fictitious Sampling):

   • Para estimar o Efeito Indireto sem reexecutar o ambiente (como no C3) ou usar pesos de importância (como no HA-GRPO), o CAPO gera "continuações fictícias".
   • Para cada trajetória real, o algoritmo amostra ações futuras dos agentes downstream diretamente da política atual conjunta $\pi^{(k-1)}$.
   • Isso evita a variância exponencial da amostragem por importância e o custo computacional de chamadas ao ambiente.

3. Contribuições Principais

1. SeqAU (Teorema 1): Identificação da linha de base única que maximiza a aprendibilidade em equipes cooperativas sequenciais, estendendo o framework de Aristocrat Utility para o caso sequencial.
2. Algoritmo CAPO: Um método de gradiente de política sem crítico que combina decomposição de recompensa, cancelamento analítico e amostragem fictícia para calcular vantagens contrafactuais.
3. Análise Teórica de Viés e Variância (Teoremas 2-4):
   • Viés: O viés é linear no resíduo de não-aditividade da recompensa. Se a recompensa for estritamente aditiva, o viés é zero.
   • Variância: A variância do CAPO adapta-se à estrutura de acoplamento. No limite de políticas fatoradas, é independente do tamanho da equipe ($K$). No pior caso, escala como $O(K-k)$, muito superior à escala exponencial $O(\exp K)$ de métodos baseados em IS (HAPPO) ou a escala linear $O(K)$ de métodos de base compartilhada (MA-GRPO).
   • Erro Quadrático Médio (MSE) do Gradiente: Não sofre inflação devido a razões de amostragem por importância.
4. Validação Empírica: Demonstração de que o CAPO supera baselines em ambientes de banda controlada sequencial, com ganhos que aumentam conforme o tamanho da equipe cresce.

4. Resultados Experimentais

Os experimentos foram realizados em um teste de "bandit cooperativo sequencial" com recompensas verdadeiras conhecidas (ground-truth).

• Qualidade da Estimativa de Vantagem (MSE):

  • O erro quadrático médio (MSE) do CAPO permanece plano (independente) em relação ao número de agentes $K$.
  • Em comparação, o MA-GRPO cresce linearmente com $K$, e o HA-GRPO cresce superlinearmente (devido ao acúmulo de variância do prefixo).
  • Para $K=16$, o CAPO teve um MSE ~30x menor que o MA-GRPO e ~46x menor que o HA-GRPO.

• Robustez a Recompensas Não-Aditivas:

  • Mesmo quando a recompensa possui interações fortes (não-aditivas), o CAPO mantém o melhor desempenho, embora o viés aumente linearmente com a magnitude da não-aditividade, conforme previsto teoricamente.

• Otimização de Política (Regret):

  • Em equipes pequenas ($K=2$), métodos simples (MA-GRPO) funcionam bem.
  • À medida que $K$ aumenta ($K \geq 6$), o CAPO supera consistentemente todos os baselines (MA-GRPO, HA-GRPO, C3).
  • O HA-GRPO degrada rapidamente com o aumento de $K$ devido à variância exponencial.
  • O C3 (replay real) tem desempenho inferior devido ao alto custo computacional por iteração, limitando o número de atualizações possíveis.

• Ablação (Efeito Indireto):

  • Uma versão do CAPO sem o efeito indireto (CAPO-Direct) funciona bem quando não há não-estacionariedade ($\rho=0$).
  • No entanto, à medida que a não-estacionariedade aumenta, o CAPO-Direct falha, enquanto o CAPO completo (com correção de efeito indireto) mantém o desempenho, provando que a correção do efeito indireto é essencial para lidar com a mudança de distribuição durante a atualização sequencial.

5. Significado e Impacto

O trabalho é altamente relevante para o cenário atual de pipelines de LLMs (Large Language Models) e agentes de ferramentas, onde:

• A execução é inerentemente sequencial (um modelo gera, outro verifica, outro executa).
• A recompensa (ex: verificação de código, avaliação humana) é frequentemente cara ou difícil de obter.
• Atualizar um modelo upstream altera o contexto para os modelos downstream.

O CAPO oferece uma solução escalável e eficiente que:

1. Elimina a necessidade de críticos centralizados complexos.
2. Evita o custo de reavaliação de recompensas no ambiente real para cada passo de atualização.
3. Mitiga o problema de variância exponencial que afeta métodos existentes em grandes equipes.

Em suma, o CAPO fornece um framework teórico e prático robusto para o treinamento de equipes cooperativas sequenciais, especialmente em domínios onde a atribuição de crédito precisa ser precisa e computacionalmente viável.