Resumo Técnico: Aprendizado por Reforço com Políticas de Difusão Discreta para Espaços de Ação Combinatórios

1. Declaração do Problema

O Aprendizado por Reforço (RL) enfrenta desafios significativos ao escalar para grandes espaços de ação discretos combinatórios, que são prevalentes em aplicações do mundo real, como planejamento hierárquico com macro-ações, coordenação multiagente e recomendações em blocos (slate) em sistemas de recomendação. Algoritmos padrão de RL lutam com esses espaços devido ao crescimento exponencial do tamanho do espaço de ação, demandando parametrizações de políticas e estratégias de exploração altamente eficientes.

Abordagens anteriores tentaram mitigar essa complexidade por meio de redução de dimensionalidade, treinamento hierárquico ou assumindo propriedades estruturais específicas. Mais recentemente, modelos autoregressivos foram aplicados a ações combinatórias; no entanto, eles sofrem com altos custos computacionais durante a inferência devido à geração sequencial e impõem ordenações causais artificiais de ações que podem restringir a expressividade da política. Embora modelos de difusão tenham mostrado promessa em controle contínuo e tarefas generativas discretas, um framework principiado e eficiente para treinar políticas de difusão discreta via RL online permanece inexplorado.

2. Metodologia: RL-D2

Os autores introduzem o RL-D2, um novo framework para treinar modelos de difusão discreta como políticas para espaços de ação combinatórios. A inovação central reside em um processo de treinamento online eficiente que desacopla a otimização do objetivo de RL da complexa tarefa de aprendizado de representação.

2.1. Alvo de Descida de Espelho da Política (PMD)

O framework reformula a atualização da política como um problema de correspondência distribucional. Em vez de otimizar diretamente o objetivo de RL, o método usa a Descida de Espelho da Política (PMD) para definir uma distribuição de política alvo ideal e regularizada ($\pi_{MD}$). Dada uma política atual $\pi_{old}$ e uma função de vantagem $A_{\pi_{old}}$, a distribuição alvo é derivada analiticamente:
$$\pi_{MD}(a|s) \propto \pi_{old}(a|s) \exp(A_{\pi_{old}}(s, a)/\lambda)$$
onde $\lambda$ é um parâmetro de temperatura. O modelo de difusão expressivo é então treinado para replicar essa distribuição alvo estável.

2.2. Minimização de Divergência

A atualização da política é alcançada minimizando a divergência entre a política de difusão ($\pi_\theta$) e o alvo PMD ($\pi_{MD}$). O artigo analisa duas variantes específicas baseadas na divergência de Kullback-Leibler (KL):

• KL Direto (FKL): Minimiza $d_{KL}(\pi_{MD}, \pi_\theta)$. Este comportamento de "busca pela média" incentiva a política a cobrir os modos da distribuição alvo, promovendo exploração. Os autores derivam uma perda ELBO ponderada tratável para este objetivo, que permite treinamento off-policy e re-pesa ações amostradas com base em seus valores de vantagem.
• KL Reverso (RKL): Minimiza $d_{KL}(\pi_\theta, \pi_{MD})$. Este comportamento de "busca por modos" foca nas ações de maior valor e é teoricamente equivalente à otimização PMD original. Devido à intratabilidade da verossimilhança da difusão, os autores constroem um MDP aumentado para derivar uma razão de amostragem por importância tratável, otimizando o objetivo usando um mecanismo de corte estilo PPO.

2.3. Aprendizado de Difusão On-Policy

Para alinhar a distribuição de treinamento com a distribuição de inferência, os autores propõem Aprendizado de Difusão On-Policy. Em vez de gerar ações ruidosas a partir de um processo direto fixo começando de uma ação limpa, a trajetória de difusão é gerada on-policy amostrando do processo reverso aprendido da política atual. Isso aumenta a estabilidade e a eficiência de amostragem.

3. Contribuições Principais

1. Framework RL-D2: Um novo framework de treinamento online eficiente para usar modelos de difusão discreta como políticas em RL para espaços de ação combinatórios. Ele reformula atualizações de políticas como problemas de correspondência distribucional usando alvos PMD.
2. Derivações Teóricas: A derivação e análise de dois métodos práticos de melhoria de política baseados na minimização das divergências KL Direto e Reverso em relação ao alvo PMD.
3. Validação Empírica: Experimentos extensivos em três domínios desafiadores demonstrando resultados state-of-the-art:
   • Geração de Sequências de DNA: Ajuste fino guiado por recompensa de um modelo de difusão discreto.
   • RL de Longo Horizonte: Planejamento de macro-ações em ambientes MinAtar e Atari.
   • RL Multiagente: Aprendizado cooperativo no domínio de Futebol da Google Research.

4. Resultados Experimentais

O artigo relata desempenho superior e eficiência de amostragem em todos os domínios testados:

• Geração de Sequências de DNA: O RL-D2 alcançou pontuações de recompensa state-of-the-art enquanto mantinha alta verossimilhança logarítmica (naturalidade) das sequências geradas. Demonstrou eficiência computacional significativa, reduzindo o consumo de memória de GPU de 66,4 GB para 10,6 GB e o tempo de treinamento de 268 minutos para 97 minutos em comparação com a linha de base DRAKES.
• Atari (Macro-Ações): O RL-D2 superou linhas de base fortes (DQN, IMPALA, R2D2, PPO) em 36 dos 56 ambientes do Atari. Mostrou força particular em tarefas que exigem estratégias de longo prazo (por exemplo, Breakout, Space Invaders). O método demonstrou escalabilidade, mantendo o desempenho conforme os comprimentos de macro-ações aumentavam (até 16), enquanto linhas de base como DQN-Macro falharam devido ao crescimento exponencial do espaço de ação.
• Google Research Football: Em tarefas cooperativas multiagente (até 11 vs 11), a política de difusão discreta alcançou as maiores taxas médias de vitória, superando linhas de base autoregressivas (MAT, MAPPO) e demonstrando a capacidade de capturar dependências complexas entre agentes sem fatoração restritiva.

Compensações Empíricas: FKL vs. RKL

Os autores destacam uma compensação chave entre as duas variantes de divergência:

• FKL: Demonstra eficiência de amostragem superior e convergência inicial mais rápida, tornando-o adequado para cenários com restrições de dados (por exemplo, Atari). No entanto, é menos estável e requer ajuste cuidadoso da temperatura para evitar colapso.
• RKL: Garante treinamento estável e alcança desempenho assintótico mais alto em tarefas desafiadoras com dados suficientes (por exemplo, Futebol da Google), embora aprenda ligeiramente mais lento inicialmente.

5. Significado e Alegações

O artigo afirma que o RL-D2 fornece uma solução escalável e de alto desempenho para o desafio de longa data do RL em grandes espaços de ação combinatórios. Ao aproveitar o poder expressivo dos modelos de difusão discreta e estabilizar o aprendizado por meio de correspondência distribucional baseada em PMD, o framework lida efetivamente com problemas complexos de tomada de decisão onde métodos tradicionais frequentemente falham.

Os autores enfatizam que sua abordagem oferece uma vantagem distinta sobre solucionadores padrão de caixa preta discretos (por exemplo, algoritmos evolutivos) ao aprender uma política condicionada ao estado que explora dinâmicas de transição e generaliza para estados não vistos, em vez de otimizar objetivos estáticos do zero. Além disso, a natureza desacoplada do método estabiliza o processo de aprendizado, aprimorando significativamente o desempenho em espaços discretos complexos e não estruturados.