Active Reward Machine Inference From Raw State Trajectories

Resumen Técnico: Inferencia Activa de Máquinas de Recompensa

1. Planteamiento del Problema

El artículo aborda el desafío de aprender Máquinas de Recompensa (Reward Machines - RMs) directamente a partir de trayectorias de estados crudos, en un escenario de escasez de información.

• Contexto: Las tareas multi-etapa en robótica a menudo requieren estructuras jerárquicas que las RMs pueden modelar mediante autómatas finitos. Sin embargo, especificar manualmente la RM (incluyendo la función de etiquetado que mapea estados de bajo nivel a proposiciones de alto nivel) es laborioso y propenso a errores.
• Limitaciones de trabajos previos: La literatura existente generalmente asume la disponibilidad de:
  1. Etiquetas de estado verdaderas (ground-truth labels).
  2. Observaciones de recompensas.
  3. Nodos de la máquina o funciones de etiquetado predefinidas.
• El problema central: Este trabajo asume ninguna de las anteriores. El algoritmo solo tiene acceso a:
  1. Un modelo de Proceso de Decisión de Markov (MDP) sin recompensa.
  2. Una política de historia ($\pi_h$) inducida por un agente experto (que captura el comportamiento del agente basado en la secuencia de estados observables).
  3. No se observan recompensas, etiquetas, ni nodos de la máquina.

El objetivo es inferir simultáneamente la función de transición de la RM ($\delta_u$) y la función de etiquetado ($L$) que hacen que la política observada sea óptima, identificando la estructura lógica latente de la tarea.

2. Metodología

La propuesta se divide en dos componentes principales: una formulación basada en SAT (Satisfacibilidad Booleana) y una estrategia de Aprendizaje Activo.

A. Formulación SAT para la Inferencia de RM Etiquetada

El problema se formula como un problema de satisfacción de restricciones booleanas para encontrar la función de transición $\delta_u$ y la función de etiquetado $L$.

• Codificación: Las funciones se codifican mediante variables binarias.
• Ejemplos Negativos: La clave del método son los "ejemplos negativos". Si dos trayectorias de estado $\tau$ y $\tau'$ llevan a la misma acción óptima en un estado $s$ pero la política de historia difiere ($\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$), entonces estas trayectorias deben llevar a la RM a nodos diferentes.
• Restricciones del SAT:
  1. $\delta_u$ y $L$ deben ser funciones bien definidas.
  2. Compatibilidad: Para cada par de ejemplos negativos, la trayectoria de etiquetas resultante debe llevar a nodos distintos en la RM.
  3. Anclaje: Se fija un estado inicial y una etiqueta inicial para evitar permutaciones triviales.
  4. No titubeo (Opcional): Se puede imponer que las transiciones no se repitan bajo la misma proposición si la tarea es invariante a la duración.

B. Profundidad Suficiente y Teorema de Identificabilidad

Los autores demuestran teóricamente que existe una profundidad suficiente ($l^*$) de la restricción de la política de historia necesaria para recuperar una RM mínima equivalente a la verdadera.

• Proposición 1: Si $l^* = |S| \cdot u_{max}^2$ (donde $|S|$ es el número de estados del MDP y $u_{max}$ es el límite superior de nodos de la RM), entonces cualquier solución válida para una profundidad $l \geq l^*$ también es válida para profundidades mayores. Esto garantiza que no se necesita información infinita.

C. Extensión Activa de la Política de Historia

Dado que enumerar todas las trayectorias posibles hasta la profundidad $l^*$ es computacionalmente inviable (crecimiento exponencial), se propone un algoritmo de aprendizaje activo:

1. Muestreo Inicial: Se resuelve el problema SAT con una profundidad de "burn-in" baja para obtener un conjunto de soluciones candidatas.
2. Selección de Consultas (Queries): En lugar de explorar todas las trayectorias, el algoritmo busca pares de trayectorias $\{\tau, \tau'\}$ que maximicen la reducción del espacio de hipótesis.
   • Se busca un par donde aproximadamente la mitad de los modelos candidatos predicen que las trayectorias llevan al mismo nodo, y la otra mitad a nodos diferentes.
   • Al consultar la política de historia real para este par, se elimina rápidamente la mitad de los candidatos incorrectos.
3. Iteración: Se añaden los nuevos ejemplos negativos al problema SAT y se refina el conjunto de soluciones hasta converger a una única estructura (salvo renombrado).

3. Contribuciones Clave

1. Inferencia sin Etiquetas ni Recompensas: Es el primer marco que aprende tanto la estructura de la RM como la función de etiquetado desde cero, utilizando únicamente trayectorias de estado y la política inducida, sin conocimiento simbólico previo.
2. Garantía Teórica de Profundidad Suficiente: Se establece un límite superior teórico ($l^*$) que garantiza que la inferencia es posible y que la información adicional más allá de este punto no es necesaria para la equivalencia de políticas.
3. Algoritmo de Extensión Activa: Se introduce una estrategia eficiente que evita la explosión combinatoria de trayectorias, seleccionando inteligentemente qué datos consultar para reducir el espacio de hipótesis con el mínimo costo computacional y de memoria.
4. Identificabilidad: Se demuestra que es posible recuperar la estructura lógica subyacente de tareas multi-etapa en un régimen de información extremadamente limitado.

4. Resultados Experimentales

Los experimentos se realizaron en entornos de mundo de cuadrícula (Grid World) con dos tareas:

• Pick and Drop: Recoger un objeto y llevarlo a un destino evitando zonas peligrosas.
• PatrolABCD: Patrullar habitaciones en un orden secuencial específico (A $\to$ B $\to$ C $\to$ D).

Hallazgos principales:

• Recuperación Correcta: El algoritmo recuperó exitosamente la RM de ground-truth y la función de etiquetado (hasta permutaciones de nombres) en ambos escenarios.
• Eficiencia de Muestreo Activo:
  • En la tarea PatrolABCD, el método exhaustivo requería almacenar 414 millones de ejemplos negativos, consumiendo 24.76 GB de memoria.
  • El método activo, con un presupuesto de consultas limitado, logró la misma convergencia utilizando solo 0.292 millones de ejemplos negativos y 0.147 GB de memoria (una reducción de dos órdenes de magnitud).
• Tiempo de Ejecución: El método activo redujo el tiempo total de ejecución en aproximadamente un 2x (3544s vs 7185s) en comparación con la búsqueda exhaustiva, principalmente al evitar la resolución de problemas SAT masivos con datos redundantes.
• Convergencia: Con una profundidad activa de 13, el algoritmo convergió a la solución correcta en el 96.6% de las pruebas (con $N_{active}=200$), mientras que una línea base aleatoria falló en encontrar restricciones útiles incluso a profundidades mayores.

5. Significado y Conclusión

Este trabajo representa un paso fundamental hacia la automatización de la especificación de tareas complejas en robótica. Al eliminar la necesidad de que un experto humano defina manualmente las proposiciones lógicas y la estructura de la máquina de recompensa, el método permite que los robots descubran la estructura temporal de sus tareas a partir de la observación de comportamientos exitosos.

• Impacto: Resuelve el cuello de botella de la especificación manual en entornos complejos y demuestra que la memoria necesaria para tareas secuenciales puede ser inferida directamente de datos de política.
• Futuro: Los autores sugieren que el siguiente paso es integrar la estimación de la política de historia a partir de trayectorias de estado-acción ruidosas y escalar el enfoque a espacios de estado continuos o representaciones perceptuales (usando modelos pre-entrenados), acercándose así a aplicaciones robóticas del mundo real.

En resumen, el artículo presenta un marco robusto y teóricamente fundamentado para la inferencia de estructuras de recompensa complejas en condiciones de información limitada, superando las barreras computacionales mediante estrategias de aprendizaje activo.