Resumen: Las máquinas de recompensas (RMS) son estructuras de autómata que codifican las funciones de recompensa (no markovianas) para el aprendizaje de refuerzo (RL). Los RM pueden recompensar cualquier comportamiento representable en idiomas regulares y, cuando se combina con algoritmos RL que explotan la estructura RM, se ha demostrado que mejora significativamente la eficiencia de la muestra en muchos dominios. En este trabajo, presentamos Máquinas de recompensa Pushdown (PDRMS), una extensión de máquinas de recompensa basadas en autómatas de pushdown deterministas. Los PDRM pueden reconocer y recompensar comportamientos extendidos temporalmente representables en idiomas deterministas libres de contexto, haciéndolos más expresivos que las máquinas de recompensa. Introducimos dos variantes de políticas basadas en PDRM, una que tiene acceso a la pila completa del PDRM, y una que solo puede acceder a los símbolos de $ K $ (para una constante $ K $) de la pila. Proponemos un procedimiento para verificar cuándo los dos tipos de políticas (para un entorno determinado, PDRM y $ K $) logramos la misma recompensa esperada óptima. Luego proporcionamos resultados teóricos que establecen el poder expresivo de las PDRM y los resultados de la complejidad espacial sobre los problemas de aprendizaje propuestos. Finalmente, proporcionamos resultados experimentales que muestran cómo se pueden capacitar a los agentes para realizar tareas representables en idiomas deterministas libres de contexto utilizando PDRM.
Publicado Originalme en export.arxiv.org El 11 de agosto de 2025.
Ver Fuente Original
