Resumo Técnico: Aprender a Buscar e Buscar para Aprender para Generalização em Planejamento

Declaração do Problema

A generalização combinatória permanece um desafio central no Aprendizado por Reforço Profundo (DRL), onde políticas ou funções de valor devem generalizar para cenários fora da distribuição definidos por uma estrutura de problema comum. O planejamento clássico oferece um campo de testes ideal para este problema porque a estrutura relacional subjacente (predicados e esquemas de ação) é fixa e explícita, enquanto as instâncias variam em contagens de objetos, estados iniciais e objetivos.

No entanto, as abordagens padrão de DRL lutam em domínios de planejamento com recompensa esparsa. A busca em tempo real (transições iterativas de estado para estado), típica em algoritmos de RL como LRTA* ou RTDP, é ineficaz para encontrar planos nessas configurações. Por outro lado, planejadores clássicos usam busca em melhor primeiro (por exemplo, A*, WA*), mas dependem de heurísticas criadas manualmente. Embora trabalhos recentes tenham tentado aprender políticas ou heurísticas gerais, os métodos existentes frequentemente dependem de busca em tempo real, aprendizado supervisionado a partir de demonstrações de especialistas ou rerotulagem retrospectiva, falhando em estabelecer um ciclo de autoaperfeiçoamento onde a busca e o aprendizado se reforçam mutuamente para alcançar generalização zero-shot em tamanhos de problema variados.

Metodologia: Busca Generalizada para Planejamento (GSP)

Os autores propõem o GSP, um framework de autoaperfeiçoamento que combina busca em melhor primeiro com Q-learning para aprender funções gerais de valor-ação ($Q_\theta$).

Loop Central

1. Aprendizado Guiado por Busca: Em vez de busca em tempo real, o GSP utiliza WA (A Ponderado)** para resolver instâncias de treinamento. A busca é guiada pelos valores atuais aprendidos de $Q_\theta(s, a)$.
2. Geração de Dados: À medida que o WA* expande nós, ele gera um buffer de replay de transições. Crucialmente, a busca fornece sinais de supervisão que o RL padrão carece:
   • Caminhos para o Objetivo: Quando um objetivo é alcançado, o algoritmo retrocede para atribuir valores reais de retorno até o objetivo aos pares no caminho da solução.
   • Pontos Sem Saída (Dead-Ends): Se um estado é um ponto sem saída (nenhuma ação aplicável), o par pai recebe uma penalidade fixa de retorno.
   • Limites Inferiores: A busca fornece um limite inferior para o retorno ótimo de qualquer par estado-ação encontrado em um caminho de solução.
3. Atualização de Q-Learning: A rede $Q_\theta$ é atualizada usando esses alvos derivados da busca. Para pares de caminho para o objetivo, o alvo é $\max(R, \hat{y})$, onde $R$ é o limite inferior derivado da busca e $\hat{y}$ é o alvo padrão de bootstrap. Isso impede que as estimativas de valor caiam abaixo do que a busca já provou ser alcançável.
4. Seleção de Instâncias: Para otimizar a eficiência do aprendizado, o framework mantém três pools de instâncias (não resolvidas, resolvidas e satisfatórias) e amostra delas com pesos exponencialmente crescentes, priorizando instâncias que fornecem as atualizações mais informativas (por exemplo, aquelas com soluções subótimas).

Representação: GNNs Relacionais

Para garantir generalização através de diferentes números de objetos e objetivos, $Q_\theta$ é representado por uma Rede Neural de Grafos Relacional (R-GNN).

• Entrada: Um estado $s$ e um objetivo $g$ são codificados como um conjunto de átomos fundamentais. As ações aplicáveis são representadas explicitamente introduzindo "objetos de ação" auxiliares e átomos, permitindo que a rede avalie escolhas de ação específicas dentro do contexto do estado.
• Arquitetura: A rede usa passagem de mensagens sobre a estrutura relacional. MLPs específicos de predicado geram mensagens baseadas em papéis de argumentos, que são agregadas por meio de funções invariantes à permutação.
• Saída: Um MLP de leitura compartilhado combina o embedding do objeto de ação específico com um resumo agrupado do estado e do objetivo para produzir o valor Q. Esta arquitetura garante que o modelo aprenda um princípio de pontuação comum para ações fundamentadas, em vez de preditores separados para cada esquema.

Contribuições Principais

1. Ciclo de Busca-Aprendizado de Autoaperfeiçoamento: O artigo introduz um framework onde a busca em melhor primeiro (WA*) gera dados de treinamento de alta qualidade (incluindo limites inferiores e sinais de pontos sem saída) para atualizar uma heurística aprendida, que por sua vez guia buscas futuras mais eficientes.
2. Generalização Zero-Shot: As funções Q aprendidas funcionam como políticas gerais capazes de resolver instâncias com significativamente mais objetos e objetivos diferentes do que visto durante o treinamento, sem exigir busca no momento do teste em muitos casos.
3. Framework Unificado: A abordagem aplica-se uniformemente a diversos domínios, desde os benchmarks da Competição Internacional de Planejamento (IPC) de 2023 até quebra-cabeças combinatórios (Sokoban, The Witness) e o domínio PushWorld, usando uma única arquitetura e conjunto de hiperparâmetros.
4. Superioridade sobre Busca em Tempo Real: O trabalho demonstra que substituir a busca em tempo real por busca em melhor primeiro no loop de aprendizado é crítico para o sucesso em domínios de planejamento com recompensa esparsa e alto fator de ramificação.

Resultados Experimentais

Os autores avaliaram o GSP em três categorias de benchmarks:

• Track de Aprendizado da IPC 2023:

  • Execução Gananciosa ($GSP_\pi$): Alcançou 100% de cobertura em Blocksworld, Miconic e Spanner, superando bases como Lifted HER, LAMA e políticas estilo AlphaZero.
  • Guiado por Busca ($GSP_{WA^*}$): Mostrou resultados mistos; embora tenha melhorado a cobertura em quebra-cabeças como Sokoban (14% $\to$ 32%), às vezes reduziu a cobertura em domínios com fatores de ramificação massivos (por exemplo, Blocksworld), onde a heurística aprendida, embora boa para classificação local, carecia de calibração global.
  • Escala: Heurísticas treinadas em instâncias de Blocksworld com <30 blocos resolveram com sucesso instâncias com 488 blocos sem busca.

• Quebra-Cabeças Combinatórios (Sokoban, The Witness, 24-Puzzle):

  • Em Sokoban, o $GSP_{WA^*}$ resolveu 100% das instâncias com uma média de 207 expansões, superando significativamente o WA* com heurísticas padrão (3298 expansões) e o DeepCubeA (1050 expansões).
  • Em The Witness, o método resolveu todas as instâncias, demonstrando o valor do treinamento em estados de ponto sem saída.
  • Em 24-Puzzle, o método falhou em encontrar soluções durante o treinamento, destacando que a abordagem requer a capacidade de encontrar pelo menos uma solução para inicializar o aprendizado, o que é difícil em quebra-cabeças fixos extremamente difíceis sem heurísticas informadas iniciais.

• PushWorld:

  • Treinado no Nível 0, o modelo generalizou para o Nível 1. O $GSP_{WA^*}$ resolveu 48/63 instâncias do Nível 1 com planos mais curtos e ~30$\times$ menos expansões do que o planejador clássico LAMA.
  • Como política gananciosa, superou significativamente as bases de RL sem modelo (DQN, PPO).

Significado e Alegações

O artigo alega que a busca em melhor primeiro é um mecanismo de exploração superior para aprendizado por reforço generalizado quando o modelo de transição é conhecido, particularmente em domínios de recompensa esparsa onde a busca em tempo real falha em descobrir trajetórias informativas.

O significado primário reside na demonstração de um ciclo de auto-reforço: a busca fornece os alvos de treinamento (limites inferiores, pontos sem saída) que permitem que a heurística melhore, e a heurística aprimorada torna as buscas subsequentes mais eficientes. Isso permite que o sistema aprenda políticas gerais que podem resolver problemas de tamanho e complexidade arbitrários sem busca, ou heurísticas altamente eficientes que guiam a busca para soluções ótimas.

Os autores notam modestamente limitações: a função Q aprendida frequentemente atua como um forte mecanismo de classificação local de ações, mas pode carecer de calibração global em toda a fronteira de busca, o que pode levar a desempenho subótimo no WA* em domínios com fatores de ramificação extremamente grandes. Eles sugerem que trabalhos futuros poderiam focar em melhorar a generalização de valor entre estados e combinar a busca em melhor primeiro com as forças complementares da busca em tempo real e da rerotulagem retrospectiva de experiência.