Resumen Técnico: Método de Lagrangiano Aumentado para la Convergencia en la Última Iteración para MDPs Constrained

Formulación del Problema

El artículo aborda el problema de la optimización de políticas para Procesos de Decisión de Markov (MDPs) Constrained de horizonte infinito y con descuento. En este escenario, un agente debe maximizar una recompensa acumulada $V^\pi_r(\rho)$ mientras asegura que las recompensas acumuladas de restricción $V^\pi_{c_i}(\rho)$ satisfagan umbrales prescritos $b_i$ para $m$ restricciones. A diferencia de los MDPs estándar, donde las políticas óptimas son deterministas, las políticas óptimas para los MDPs con restricciones (CMDPs) son generalmente estocásticas.

Un desafío práctico significativo surge de las limitaciones de los métodos Primal-Dual (PD) existentes. Si bien existen garantías teóricas para los métodos PD, estas típicamente aplican solo a una política de mezcla (un promedio uniforme de todas las políticas intermedias generadas durante el entrenamiento). Desplegar dicha mezcla es computacional y de memoria intensivo, ya que requiere almacenar todas las políticas intermedias. Además, en aplicaciones críticas para la seguridad, confiar en una mezcla es riesgoso porque una política muestreada aleatoriamente de la mezcla puede violar las restricciones significativamente, incluso si la mezcla las satisface en expectativa. En consecuencia, los practicantes a menudo despliegan la política de última iteración (la política final generada), pero los métodos PD estándar carecen de garantías teóricas para esta política específica, exhibiendo a menudo comportamiento oscilatorio y fallando en converger a una solución factible.

Trabajos recientes que intentan probar la convergencia en la última iteración se han limitado en gran medida a entornos tabulares o dependen de variantes algorítmicas (por ejemplo, regularización pesada) que son difíciles de implementar o poco prácticas para problemas a gran escala.

Metodología

Los autores proponen un marco general basado en el método del Lagrangiano Aumentado (AL), un enfoque clásico en optimización con restricciones, para lograr una convergencia demostrable en la última iteración para CMDPs.

1. El Marco del Lagrangiano Aumentado

En lugar del Lagrangiano estándar utilizado en los métodos PD, el marco optimiza la función Lagrangiana Aumentada $L_\beta(\pi, \lambda)$:
$$L_\beta(\pi, \lambda) := V^\pi_r(\rho) + \frac{\beta}{2} \sum_{i=1}^m \left( -\min\left\{ V^\pi_{c_i}(\rho) - b_i - \frac{\lambda_i}{\beta}, 0 \right\}^2 + \frac{\lambda_i^2}{\beta^2} \right)$$
donde $\beta > 0$ es un parámetro de penalización y $\lambda$ son los multiplicadores de Lagrange. El término de penalización cuadrática desalienta las violaciones de restricciones. El algoritmo actualiza iterativamente la política (variable primal) para maximizar aproximadamente esta función y actualiza las variables duales (multiplicadores de Lagrange) basándose en las violaciones de restricciones.

2. Resolución del Subproblema AL

El desafío central es que $L_\beta(\pi, \lambda)$ es no cóncava con respecto a la política $\pi$, lo que hace difícil resolver el subproblema. Los autores descomponen la solución en dos escenarios:

• Escenario Tabular: Los autores proponen resolver el subproblema AL utilizando Ascenso de Q Proyectado (PQA). Derivan el gradiente de la política para el subproblema AL, que involucra una pseudo-recompensa no estacionaria $\Gamma(\pi)$ que depende del nivel de satisfacción de restricciones de la política actual. Al utilizar PQA, establecen garantías de convergencia global en la última iteración para el subproblema.
• Aproximación de Funciones (Políticas Log-Lineales): Para manejar grandes espacios de estado-acción, el marco se extiende a políticas paramétricas (específicamente políticas log-lineales). Los autores derivan un gradiente de política AL que se descompone linealmente en los componentes originales de recompensa y restricción, permitiendo emplear herramientas de estimación estándar (como las utilizadas en PPO o SPMA). Introducen una actualización de PQA Proyectado (PPQA), que implica:
  1. Calcular una actualización de política idealizada (paso PQA).
  2. Proyectar esta actualización sobre la clase de políticas factibles utilizando la divergencia KL hacia adelante, formulada como un problema de optimización sustituto (regresión logística multiclase con etiquetas suaves).

3. Análisis de Convergencia

Los autores proporcionan un análisis modular:

1. Primero prueban que el método AL inexacto converge a una solución $\epsilon$-óptima para el CMDP si el solucionador del subproblema logra una precisión específica ($O(1/\epsilon^2)$ iteraciones para el bucle externo).
2. Luego analizan los solucionadores específicos (PQA y PPQA) para demostrar que pueden lograr la precisión requerida para el subproblema.
3. Combinando estos resultados, prueban que el algoritmo general logra convergencia global en la última iteración con una complejidad de muestra de $O(1/\epsilon^6)$ evaluaciones de gradiente tanto para escenarios tabulares como log-lineales.

Contribuciones Clave

1. Marco Genérico de AL Inexacto: El artículo introduce un marco modular para resolver CMDPs utilizando el método AL inexacto. Separa el análisis de las iteraciones AL de la elección del solucionador del subproblema, demostrando que $O(1/\epsilon^2)$ iteraciones externas son suficientes para encontrar una política $\epsilon$-óptima, siempre que el subproblema se resuelva con precisión suficiente.
2. Convergencia en la Última Iteración Tabular: Al instanciar el marco con Ascenso de Q Proyectado (PQA) para el escenario tabular, los autores establecen una convergencia global en la última iteración con una complejidad de $O(1/\epsilon^6)$. Esto aborda la no estacionariedad de la pseudo-recompensa en el subproblema AL.
3. Extensión a Aproximación de Funciones: El marco se generaliza a políticas log-lineales. Los autores derivan el gradiente de política AL y proponen una variante proyectada (PPQA) que logra garantías de convergencia comparables de $O(1/\epsilon^6)$. A diferencia de trabajos anteriores, este método no requiere modificaciones algorítmicas no estándar (como proyectar sobre símplices restringidos) ni suposiciones estructurales restrictivas (como aproximación de funciones compatible) y soporta múltiples restricciones.
4. Validación Empírica: El marco se instancia utilizando PPO y SPMA (un algoritmo reciente de optimización de políticas) y se evalúa en tareas de control continuo a gran escala de Safety-Gymnasium. Los resultados demuestran que el enfoque propuesto tiene un rendimiento comparable a líneas base altamente ingenierizadas como PPO-Lag y CPO, mientras ofrece garantías teóricas para la política final.

Resultados

• Teóricos: El artículo prueba que el algoritmo propuesto devuelve una política estocástica que es una solución $\epsilon$-aproximada al problema CMDP después de $O(1/\epsilon^6)$ evaluaciones de gradiente. Esto se cumple tanto para clases de políticas tabulares como log-lineales.
• Empíricos (Tabular): En entornos tabulares (Mundo de Acantilados Constrained, Tesoro de Mar Profundo Constrained), los métodos propuestos PQA-ALM y PPQA-ALM convergen suavemente a la política óptima con oscilación mínima, superando o igualando a otros métodos de última iteración como RPG-PD y ReLOAD.
• Empíricos (Control Continuo): En tareas de Safety-Gymnasium (SafetyAntVelocity, SafetyHalfCheetahVelocity, SafetyHopperVelocity), las variantes SPMA-ALM y PPO-ALM logran retornos y violaciones de restricciones comparables a PPO-Lag y CPO. Cabe destacar que los métodos basados en AL exhiben menos comportamiento oscilatorio y una satisfacción de restricciones más consistente (menores violaciones medias y de cola) en comparación con las líneas base.

Significado y Afirmaciones

El artículo afirma cerrar la brecha entre las garantías teóricas y el despliegue práctico en el aprendizaje por refuerzo con restricciones.

• Practicidad: A diferencia de trabajos anteriores de convergencia en la última iteración que están limitados a entornos tabulares o dependen de regularizaciones poco prácticas, este marco está diseñado para ser eficiente y escalable a problemas grandes utilizando aproximación de funciones estándar.
• Seguridad: Al garantizar la convergencia para la política de última iteración en lugar de una mezcla, el método asegura que la política desplegada en sí misma satisfaga las restricciones, lo cual es crítico para aplicaciones críticas para la seguridad donde el muestreo aleatorio de una mezcla es inaceptable.
• Enfoque Principiado: El método se basa en el clásico método del Lagrangiano Aumentado, proporcionando una base teórica clara sin la necesidad de heurísticas ad hoc que a menudo se encuentran en implementaciones prácticas de RL con restricciones (por ejemplo, escalar objetivos por multiplicadores).

Los autores reconocen limitaciones, específicamente la fuerte dependencia de la probabilidad mínima de visita a estados ($\rho_{min}$) en el escenario tabular y el término de sesgo ($\epsilon_{bias}$) para políticas log-lineales, sugiriendo estos como direcciones para trabajo futuro. También señalan que las direcciones futuras incluyen incorporar métodos actor-critic o fuera de política en el marco teórico.