Laplacian Representations for Decision-Time Planning

Enunciado do Problema
O aprendizado por reforço (RL) baseado em modelos oferece potenciais vantagens em eficiência de amostragem, generalização e adaptação em comparação com abordagens sem modelo (model-free). No entanto, um desafio central permanece: o planejamento com um modelo aprendido em ambientes que exigem aproximação de função é dificultado pelo problema do erro de composição. Quando um agente simula trajetórias de longo horizonte usando um modelo imperfeito, pequenos erros de previsão se acumulam, fazendo com que as trajetórias imaginadas divirjam significamente da realidade. Este problema é particularmente agudo no planejamento em tempo de decisão, onde as representações de estado devem suportar simultaneamente o cálculo de custo local e preservar estruturas temporais de longo horizonte. Embora o planejamento hierárquico possa desacoplar ações de baixo nível de objetivos de longo horizonte, ele requer um espaço latente capaz de representar distâncias do espaço de estados através de múltiplas escalas de tempo para decompor tarefas em submetas de forma eficaz.

Metodologia
O artigo propõe que a representação Laplaciana fornece um espaço latente eficaz para o planejamento em tempo de decisão. Esta representação incorpora estados em um espaço definido pelos autovetores do Laplaciano do grafo induzido pela dinâmica do ambiente. As propriedades principais desta representação incluem:

• Estrutura Multi-escala: Os autovetores são ordenados por escala de tempo; autovetores iniciais codificam a estrutura global (ex: regiões), enquanto os posteriores capturam distinções locais.
• Alcance e Geometria: A distância euclidiana no espaço Laplaciano escalonado aproxima a Distância de Tempo de Comutação (CTD), que mede o número esperado de passos para viajar entre dois estados e retornar via uma caminhada aleatória. Isso torna o espaço isométrico à CTD, fornecendo uma geometria adequada para o planejamento.
• Descoberta de Submetas: A representação particiona naturalmente o ambiente em regiões bem conectadas, sendo ideal para o agrupamento espectral (spectral clustering) para identificar submetas em gargalos.

Com base nessas propriedades, os autores introduzem o ALPS (Augmented Laplacian Planning with Subgoals), um algoritmo de planejamento hierárquico em tempo de decisão. O ALPS opera em duas fases:

1. Pré-treinamento:
   • Aprendizado Laplaciano: Utiliza o Objetivo Laplaciano de Lagrange Aumentado (ALLO) para aprender autovetores e autovalores a partir de um conjunto de dados offline, evitando o custo computacional de $O(|S|^3)$ da decomposição de autovalores exata.
   • Modelo de Forward: Aprende um modelo de forward autorregressivo de múltiplos passos no espaço de estado original para reduzir a acumulação de erro.
   • Prior de Comportamento: Aprende uma política determinística condicionada a objetivos ($\pi_{prior}$) para enviesar a amostragem de ações, acelerando a convergência.
   • Grafo de Clusters: Realiza o agrupamento k-means no espaço Laplaciano escalonado ($\psi$-space) para definir submetas (centros de clusters) e constrói um grafo de transições entre clusters.
2. Planejamento em Tempo de Decisão:
   • Alto Nível: Dado um estado inicial e um estado objetivo, o algoritmo identifica seus respectivos clusters e utiliza o algoritmo de Dijkstra no grafo de clusters para encontrar um caminho de submetas.
   • Baixo Nível: Para cada submeta, um planejador de Método de Cruzamento de Entropia (CEM) gera uma sequência de ações. O CEM é inicializado usando o prior de comportamento e otimizado minimizando uma função de custo baseada na distância no $\psi$-space (aproximando a CTD) e na magnitude da ação.

Principais Contribuições

• Representação Laplaciana para Planejamento: O artigo demonstra que a representação Laplaciana captura efetivamente as distâncias do espaço de estados em múltiplas escalas de tempo, decompondo naturalmente problemas de longo horizonte em submetas e mitigando erros de composição.
• Algoritmo ALPS: Um novo algoritmo de planejamento hierárquico que integra a identificação de submetas baseada em Laplaciano com otimização de trajetória baseada em modelo (CEM) e um prior de comportamento.
• Validação Empírica: Os autores avaliam o ALPS no OGBench (Avaliação de RL Condicionada a Objetivos Offline), um conjunto de tarefas anteriormente dominadas por métodos sem modelo.

Resultados
Experimentos foram conduzidos nos ambientes Maze2D—PointMass e em um conjunto diversificado de tarefas do OGBench envolvendo locomoção (pointmaze, antmaze, humanoidmaze) e manipulação (cube, scene) com observações baseadas em estados e em pixels.

• Desempenho: O ALPS supera significativamente as bases comuns sem modelo (incluindo variantes de GCBC, IQL, QRL, CRL e HIQL) na maioria das tarefas do OGBench, com significância estatística ($p < 0.001$).
• Robustez: O ALPS demonstra robustez ao tamanho do labirinto e à qualidade do conjunto de dados offline. Ele se destaca particularmente em conjuntos de dados "explore" com dados de baixa qualidade e alta cobertura, onde a decomposição hierárquica permite que o planejador de alto nível compense um horizonte de baixo nível limitado.
• Comparação com PcLast: Nas tarefas Maze2D, o ALPS (usando representação Laplaciana) supera o PcLast (usando estados latentes contrastivos), destacando a utilidade da métrica Laplaciana tanto para estimativa de distância quanto para identificação de submetas.
• Limitações: O artigo observa que o ALPS tem dificuldades com labirintos de "teleporte" onde a simetrização inerente ao objetivo Laplaciano faz com que entradas e saídas de teletransportadores sejam agrupadas juntas, potencialmente levando o agente a regiões inescapáveis. Além disso, o desempenho degrada em tarefas de manipulação de múltiplos objetos (ex: double-cube) devido à natureza global da representação Laplaciana, que falha em capturar a independência condicional entre os estados dos objetos.

Significância
O artigo afirma que a representação Laplaciana serve como um bloco de construção útil para um planejamento bem-sucedido com modelos aprendidos, abordando o desafio central dos erros de composição em tarefas de longo horizonte. Ao fornecer um espaço latente que captura intrinsecamente a estrutura temporal e a conectividade, o ALPS permite um planejamento hierárquico eficaz em espaços de estado contínuos e de alta dimensão usando apenas conjuntos de dados offline pré-coletados. O trabalho sugere que aproveitar as propriedades espectrais da dinâmica do ambiente pode superar a dificuldade histórica de aplicar métodos baseados em modelo a problemas complexos de RL condicionado a objetivos de longo horizonte.