Answer-Set-Programming-based Abstractions for Reinforcement Learning

Planteamiento del Problema
El Aprendizaje por Refuerzo (RL, por sus siglas en inglés) permite que los agentes aprendan políticas mediante la interacción, pero las aplicaciones realistas a menudo sufren de espacios de estados y acciones enormes, lo que hace que los enfoques de aprendizaje ingenuos sean intratables. Aunque los métodos de aproximación como el Deep Q-Learning ofrecen generalización, frecuentemente requieren vastas cantidades de datos de entrenamiento y pueden exhibir inestabilidad. El Aprendizaje por Refuerzo Relacional (RRL) aborda estas limitaciones utilizando la lógica de primer orden para razonar sobre objetos y sus relaciones, facilitando la generalización a través de estados similares. Específicamente, el marco CARCASS (Abstracción Compacta mediante Conjunciones Relacionales para la Agregación de Espacios de Estado-Acción) de van Otterlo (2004) modela los Procesos de Decisión de Markov (MDPs) utilizando abstracciones lógicas. Sin embargo, la implementación original de CARCASS depende de Prolog y la resolución SLDNF, la cual, aunque es declarativa en principio, a menudo requiere características procedimentales (como el orden de las reglas o cortes) para ser eficiente y carece de soporte nativo para la inferencia no monotónica, la optimización y el manejo de preferencias.

Metodología
Los autores proponen un método general para re-implementar el marco CARCASS utilizando Programación de Conjuntos de Respuestas (ASP). ASP es un lenguaje de representación de conocimiento basado en lógica totalmente declarativo que soporta el razonamiento no monotónico, la optimización y las restricciones.

1. Codificación ASP de CARCASS: Los autores definen una función de etiquetado para mapear estados abstractos y pares estado-acción a términos de base. Construyen una codificación modular que comprende:

   • Programas ($P_{\hat{s}_i}$) que codifican estados abstractos individuales como reglas donde el cuerpo consiste en los literales que definen el estado abstracto.
   • Programas ($P_{\hat{s}_i, \hat{a}_{i,j}}$) que codifican la relación de cobertura para pares estado-acción abstractos, vinculando acciones concretas con abstractas a través de átomos aCov.
   • Un mecanismo de lista de decisión ($P_{\hat{C}}$) utilizando una regla de elección para seleccionar exactamente un estado de cobertura abstracto por cada estado concreto y una restricción para asegurar que la selección siga la lista ordenada (priorizando el índice más bajo).
   • Un estado abstracto "vacío" ($\hat{s}_\infty$) con el índice más alto que cubre todos los estados no cubiertos por reglas específicas, asegurando un retorno por defecto.

2. Integración de Aprendizaje en Línea: Los autores integran esta codificación en un bucle de Q-learning en línea (Algoritmo 2). Para un estado concreto dado, el solver de ASP computa un conjunto de respuestas óptimo para determinar el estado de cobertura abstracto y el conjunto de acciones abstractas admisibles. El agente selecciona entonces una acción concreta del conjunto cubierto por la acción abstracta elegida y actualiza el valor Q del par estado-acción abstracto.

3. Conocimiento de Fondo: El marco permite la inclusión de conocimiento de fondo ($P_B$) para inferir propiedades complejas (por ejemplo, búsqueda de rutas, completitud de torres) directamente dentro del proceso de abstracción, en lugar de requerir que sean pre-computadas o implementadas procedimentalmente.

Contribuciones Clave

1. Método de Codificación General: El artículo introduce un método sistemático para codificar abstracciones CARCASS en ASP, demostrando cómo un lenguaje totalmente declarativo puede realizar abstracciones de estado-acción relacionales.
2. Adaptación de Aprendizaje en Línea: Los autores muestran cómo utilizar las abstracciones CARCASS basadas en ASP dentro de un entorno de Q-learning en línea, manejando la selección dinámica de estados y acciones abstractas.
3. Evaluación Empírica: La implementación se evalúa en dos dominios distintos:
   • Mundo de Bloques (Blocks World): Una tarea de apilamiento de $n$-bloques donde la abstracción reduce el espacio estado-acción a un tamaño constante independientemente de $n$.
   • MiniGrid: Una suite de tareas de navegación en mundos de rejilla (ej. Puerta Llave, Multi Habitación) donde el conocimiento de fondo se utiliza para inferir la disposición de las habitaciones y las rutas más cortas, construyendo estados abstractos basados en el siguiente nodo en la ruta.

Resultados
La evaluación empírica compara el Q-learning abstracto contra el Q-learning concreto en un mundo de 20 bloques y tres entornos de MiniGrid.

• Estabilidad: El Q-learning abstracto demostró una estabilidad consistente, con retornos medianos e intervalos intercuartílicos que permanecen altos tras el aprendizaje inicial, mientras que el Q-learning concreto mostró fluctuaciones significativas o fallo en la convergencia en entornos complejos.
• Calidad: El Q-learning abstracto logró altas tasas de éxito (por ejemplo, cerca del 100% en los últimos 500 episodios para las tareas de MiniGrid), superando significativamente al Q-learning concreto, que a menudo no logró retornos positivos en el mismo periodo de tiempo.
• Eficiencia de Muestreo: El enfoque abstracto requirió significativamente menos episodios para aprender políticas de alta calidad en comparación con el enfoque concreto. Por ejemplo, en el mundo de 20 bloques, el aprendizaje abstracto logró retornos medianos positivos para el episodio 376, mientras que el aprendizaje concreto permaneció en el retorno negativo de la línea base.
• Diferencias de Modelado: En el caso de estudio de MiniGrid, la codificación ASP permitió una especificación compacta y declarativa de la búsqueda de rutas y las restricciones, mientras que la implementación equivalente en Prolog requería una búsqueda algorítmica explícita (búsqueda en anchura), resaltando la ventaja de ASP para separar la especificación del problema de la lógica de control.

Significancia y Reivindicaciones
El artículo concluye que CARCASS implementado con ASP proporciona un enfoque prometedor para la construcción de abstracciones en RL, particularmente cuando se dispone de conocimiento del dominio. Los autores afirman que las abstracciones basadas en ASP ofrecen una alternativa flexible a CARCASS basado en Prolog al soportar:

• Generalización: A través de representaciones relacionales.
• Restricciones de Acción: Mediante restricciones declarativas.
• Descomposición de Problemas: Al codificar patrones de razonamiento complejos (como búsqueda de rutas o análisis de torres) directamente en las reglas.
• Razonamiento Avanzado: Incluyendo inferencia no monotónica, optimización y razonamiento bajo conocimiento incompleto.

Los autores señalan modestamente que, si bien las políticas aprendidas son de una calidad aceptable y se aprenden con menos muestras, no existe una garantía de convergencia a una política óptima en general, y la abstracción misma puede no preservar la política óptima para problemas de planificación NP-duros (como se observa en el caso de Blocks World, donde la abstracción sacrifica la optimalidad por la tractabilidad). El trabajo se posiciona como un paso hacia marcos de trabajo impulsados por el conocimiento para el aprendizaje por refuerzo relacional que soporten el aprendizaje de políticas tolerantes a la elaboración.