Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

Resumen Técnico: Aprendizaje por Refuerzo Disperso No Convexo mediante Inclusiones No Monótonas

Planteamiento del Problema
El aprendizaje por refuerzo (RL) a menudo se enfrenta a la "maldición de la dimensionalidad" al aproximar las funciones Q en espacios de estados de alta dimensión. Si bien la aproximación de funciones lineales es un remedio estándar, introduce un compromiso entre la precisión de la aproximación y la complejidad computacional. La selección de características mediante modelado disperso (sparse modeling) es una estrategia común para mitigar esto, pero los enfoques convencionales que dependen de la regularización de la norma $\ell_1$ (por ejemplo, LARS-TD, LSTD con $\ell_1$) sufren de sesgo de estimación, subestimando sistemáticamente los componentes de gran amplitud. Además, en entornos de RL por lotes (batch RL) donde los datos son fijos y potencialmente ruidosos, la robustez ante características irrelevantes y valores atípicos es crítica. Aunque se han propuesto penalizaciones no convexas como la penalización de Minimax Concave (MC) en la regresión dispersa para reducir el sesgo, su aplicación al RL sigue sin explorarse debido a la no convexidad resultante del problema de optimización, lo que rompe los supuestos de monotonía requeridos para las garantías de convergencia estándar en los métodos de división de operadores (operator splitting).

Metodología
El artículo propone un nuevo algoritmo por lotes para la selección de características en RL que integra la penalización proyectiva de Minimax Concave (PMC) en la formulación de Diferencia Temporal de Mínimos Cuadrados (LSTD).

1. Reformulación del Problema: Los autores formulan el problema de evaluación de la política como la búsqueda de un punto fijo de un mapeo que minimiza un error de diferencia temporal de mínimos cuadrados regularizado por la penalización PMC. A diferencia del LSTD estándar, este objetivo es no convexo.
2. División de Operadores (Operator Splitting): Al explotar la convexidad débil de la penalización PMC, el problema de punto fijo se reformula como la búsqueda del cero de la suma de dos operadores: un operador Lipschitz monótono y un operador hipomonótono. Esto sitúa el problema dentro de la clase de inclusiones no monótonas.
3. Solución Algorítmica: Los autores emplean el método de División hacia Adelante-Reflejada-Hacia Atrás (Forward-Reflected-Backward Splitting, FRBS) para resolver este problema de inclusión. Una contribución técnica clave es la derivación de una expresión de forma cerrada para el resolvente de la parte hipomonótona (que involucra el operador de contracción suave o soft-shrinkage), lo que hace que el algoritmo sea tratable sin variables auxiliares.
4. Ajuste de Hiperparámetros: El método introduce un hiperparámetro ajustable $q$ que controla el subespacio $M$ sobre el cual se confina el efecto de reducción de sesgo de la penalización PMC. Esto generaliza la definición original de PMC, permitiendo la optimización del rendimiento de la penalización incluso cuando la matriz de Gram de entrada tiene autovalores positivos muy pequeños.

Contribuciones Clave
El artículo realiza cuatro contribaciones primarias:

• Algoritmo de RL: Introduce un método eficiente de selección de características por lotes para RL que incorpora la penalización no convexa PMC en LSTD. Esto aborda el sesgo de estimación inherente a los métodos regularizados con $\ell_1$.
• Extensión Teórica: Extiende el análisis de convergencia del método FRBS a una clase más amplia de problemas de inclusión no monótona. Específicamente, establece:
  • Estabilidad de Lyapunov: Bajo condiciones leves, se demuestra que las iteraciones son cuasi-Fejér monótonas, lo que asegura la existencia de un punto límite y estabilidad.
  • Convergencia Exacta: Bajo el supuesto de la desigualdad de Variación de Minty (MVI) débil, se prueba que la secuencia converge exactamente a una solución.
• Penalización PMC Generalizada: El artículo generaliza la penalización PMC al permitir que el subespacio $M$ sea controlado por un parámetro ajustable $q$, en lugar de estar fijado al complemento ortogonal del espacio nulo. Esto evita la degradación del rendimiento en configuraciones mal condicionadas.
• Límites de Error: Se proporciona un límite de error para las políticas generadas por el esquema de Iteración de Política Aproximada (API) propuesto, vinculando el error de aproximación con el error de estimación de la función Q.

Resultados
Se realizaron pruebas numéricas en tres tareas de referencia de RL: el paseo de cadena de 50 estados (50-state chain walk), el auto de montaña (mountain car) y el acróbata (acrobot). El método propuesto se comparó con métodos de selección de características por lotes de vanguardia, incluyendo LSTD, LARS-TD y Basis Pursuit Denoising (BPDN).

• Rendimiento: El método propuesto superó sustancialmente a sus competidores, particularmente en escenarios con numerosas características ruidosas o irrelevantes. En las tareas de mountain car y acrobot, alcanzó las tasas de éxito más altas y el menor número promedio de pasos hacia la meta.
• Mitigación del Sesgo: Los resultados demostraron que el método propuesto mitiga eficazmente el sesgo de estimación asociado con la regularización de la norma $\ell_1$, lo que conduce a estimaciones de la función Q más precisas.
• Sensibilidad de los Hiperparámetros: Los experimentos en el paseo de cadena de 50 estados mostraron que el hiperparámetro $q$ influye significativamente en el rendimiento. Un rango moderado de $q$ produjo el menor Error Cuadrático Medio Normalizado (NMSE), mientras que los valores extremos degradaron el rendimiento, ya sea al no reducir el sesgo lo suficiente o al forzar a la penalización a aproximarse a la norma $\ell_1$ sesgada.

Significancia
El artículo afirma proporcionar una base teórica rigurosa para la aplicación de penalizaciones no convexas en RL, un dominio donde tales métodos han sido evitados previamente debido a preocupaciones de convergencia. Al establecer garantías de convergencia para FRBS en entornos no monótonos, este trabajo cierra la brecha entre la teoría de modelado disperso no convexo y las aplicaciones prácticas de RL. Los autores sostienen que su enfoque ofrece una alternativa robusta a la regularización convexa, entregando una selección de características y un rendimiento de política superiores en entornos de alta dimensión y con ruido, sin sacrificar las garantías de convergencia teórica. El trabajo extiende una versión preliminar de conferencia al proporcionar pruebas completas de convergencia bajo supuestos de MVI débil y una validación numérica extensa.