Laplacian Representations for Decision-Time Planning

Planteamiento del Problema
El aprendizaje por refuerzo (RL) basado en modelos ofrece ventajas potenciales en eficiencia de muestreo, generalización y adaptación en comparación con los enfoques sin modelo. Sin embargo, un desafío central sigue siendo: la planificación con un modelo aprendido en entornos que requieren aproximación de funciones se ve obstaculizada por el problema del error acumulativo. Cuando un agente simula trayectorias de largo horizonte utilizando un modelo imperfecto, los pequeños errores de predicción se acumulan, causando que las trayectorias imaginadas diverjan significativamente de la realidad. Este problema es particularmente agudo en la planificación en tiempo de decisión, donde las representaciones de estado deben soportar simultáneamente el cálculo de costos locales y preservar estructuras temporales de largo horizonte. Si bien la planificación jerárquica puede desacoplar las acciones de bajo nivel de los objetivos de largo horizonte, requiere un espacio latente capaz de representar distancias del espacio de estados a través de múltiples escalas temporales para descomponer tareas en subobjetivos de manera efectiva.

Metodología
El artículo propone que la representación Laplaciana proporciona un espacio latente efectivo para la planificación en tiempo de decisión. Esta representación incrusta los estados en un espacio definido por los autovectores del Laplaciano del grafo inducido por la dinámica del entorno. Las propiedades clave de esta representación incluyen:

• Estructura multiescala: Los autovectores están ordenados por escala de tiempo; los autovectores tempranos codifican la estructura global (ej. regiones), mientras que los posteriores capturan distinciones locales.
• Alcanzabilidad y Geometría: La distancia euclidiana en el espacio Laplaciano escalado aproxima la Distancia de Tiempo de Conmutación (CTD), que mide el número esperado de pasos para viajar entre dos estados y volver mediante un paseo aleatorio. Esto hace que el espacio sea isométrico a la CTD, proporcionando una geometría bien adecuada para la planificación.
• Descubrimiento de Subobjetivos: La representación particiona naturalmente el entorno en regiones bien conectadas, lo que la hace ideal para el agrupamiento espectral (spectral clustering) para identificar subobjetivos en cuellos de botella.

Basándose en estas propiedades, los autores introducen ALPS (Augmented Laplacian Planning with Subgoals), un algoritmo de planificación jerárquica en tiempo de decisión. ALPS opera en dos fases:

1. Pre-entrenamiento:
   • Aprendizaje Laplaciano: Utiliza el Objetivo Laplaciano de Lagrangiano Aumentado (ALLO) para aprender autovectores y autovalores de un conjunto de datos offline, evitando el costo computacional de $O(|S|^3)$ de la descomposición de autovalores exacta.
   • Modelo de Propagación (Forward Model): Aprende un modelo de propagación autorregresivo de múltiples pasos en el espacio de estados original para reducir la acumulación de error.
   • Prior de Comportamiento: Aprende una política determinista condicionada a la meta ($\pi_{prior}$) para sesgar el muestreo de acciones, acelerando la convergencia.
   • Grafo de Clústeres: Realiza un agrupamiento k-means en el espacio Laplaciano escalado ($\psi$-space) para definir subobjetivos (centros de clúster) y construye un grafo de transiciones entre clústeres.
2. Planificación en Tiempo de Decisión:
   • Alto Nivel: Dado un estado inicial y un estado meta, el algoritmo identifica sus respectivos clústeres y utiliza el algoritmo de Dijkstra en el grafo de clústeres para encontrar un camino de subobjetivos.
   • Bajo Nivel: Para cada subobjetivo, un planificador de Método de la Contramensura (CEM) genera una secuencia de acciones. El CEM se inicializa usando el prior de comportamiento y se optimiza minimizando una función de costo basada en la distancia en el $\psi$-space (aproximando la CTD) y la magnitud de la acción.

Contribuciones Clave

• Representación Laplaciana para la Planificación: El artículo demuestra que la representación Laplaciana captura efectivamente las distancias del espacio de estados en múltiples escalas de tiempo, descomponiendo naturalmente los problemas de largo horizonte en subobjetivos y mitigando los errores de acumulación.
• Algoritmo ALPS: Un nuevo algoritmo de planificación jerárquica en tiempo de decisión que integra la identificación de subobjetivos basada en el Laplaciano con la optimización de trayectoria basada en modelos (CEM) y un prior de comportamiento.
• Validación Empírica: Los autores evalúan ALPS en el OGBench (Banco de Pruebas de RL Condicionado a la Meta Offline), una suite de tareas previamente dominadas por métodos sin modelo.

Resultados
Los experimentos se realizaron en entornos Maze2D—PointMass y un conjunto diverso de tareas de OGBench que involucran locomoción (pointmaze, antmaze, humanoidmaze) y manipulación (cube, scene) con observaciones basadas tanto en estados como en píxeles.

• Desempeño: ALPS supera significativamente a los baselines comunes sin modelo (incluyendo variantes de GCBC, IQL, QRL, CRL e HIQL) en la mayoría de las tareas de OGBench, con significancia estadística ($p < 0.001$).
• Robustez: ALPS demuestra robustez ante el tamaño del laberinto y la calidad del conjunto de datos offline. Sobresale particularmente en conjuntos de datos de "exploración" con datos de baja calidad pero alta cobertura, donde la descomposición jerárquica permite al planificador de alto nivel compensar un horizonte de bajo nivel limitado.
• Comparación con PcLast: En tareas de Maze2D, ALPS (usando la representación Laplaciana) supera a PcLast (usando estados latentes contrastivos), resaltando la utilidad de la métrica Laplaciana tanto para la estimación de distancia como para la identificación de subobjetivos.
• Limitaciones: El artículo señala que ALPS tiene dificultades con laberintos de "teletransporte" donde la simetrización inherente al objetivo Laplaciano causa que las entradas y salidas de los teletransportadores se agrupen, lo que potencialmente conduce al agente hacia regiones inevitables. Además, el desempeño decae en tareas de manipulación de múltiples objetos (ej. doble cubo) debido a que la naturaleza global de la representación Laplaciana no logra capturar la independencia condicional entre los estados de los objetos.

Significancia
El artículo afirma que la representación Laplaciana sirve como un bloque de construcción útil para una planificación exitosa con modelos aprendidos, abordando el desafío central de los errores de acumulación en tareas de largo horizonte. Al proporcionar un espacio latente que captura intrínsecamente la estructura temporal y la conectividad, ALPS permite una planificación jerárquica efectiva en espacios de estado continuos y de alta dimensión utilizando únicamente conjuntos de datos offline pre-recolectados. El trabajo sugiere que aprovechar las propiedades espectrales de la dinámica del entorno puede superar la dificultad histórica de aplicar métodos basados en modelos a problemas complejos de RL condicionado a la meta de largo horizonte.