Resumen Técnico: Optimización de Política Primal-Dual para CMDPs Lineales con Pérdidas Adversarias

Configuración del Problema

Este artículo aborda el desafío del Aprendizaje por Refuerzo (RL) Seguro en entornos donde las restricciones de seguridad deben satisfacerse a pesar de perturbaciones adversarias. Específicamente, los autores consideran Procesos de Decisión de Markov (CMDP) Lineales Confinados a Horizonte Finito con Pérdidas Adversarias.

La configuración se define mediante la tupla $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$, donde:

• Pérdidas Adversarias: Las funciones de pérdida $f^k = \{f^k_h\}$ son elegidas arbitrariamente por un adversario al inicio de cada episodio $k$ (retroalimentación de información completa). Estas pérdidas no se extraen de una distribución fija.
• Costos Estocásticos: Las funciones de costo $g^k = \{g^k_h\}$ se muestrean de forma independiente e idénticamente (i.i.d.) desde una distribución fija $G$ (retroalimentación tipo bandido), representando restricciones de seguridad.
• Estructura Lineal: Los núcleos de transición, las funciones de pérdida y las funciones de costo poseen una estructura lineal con respecto a una mapeo de características conocido $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$.
• Objetivo: El agente busca una política que minimice la pérdida esperada acumulada, asegurando al mismo tiempo que el costo acumulado esperado no exceda un presupuesto $b$.

El rendimiento se mide mediante Arrepentimiento (diferencia de pérdida acumulada en comparación con la política óptima) y Violación de Restricciones (exceso de costo acumulado sobre el presupuesto). El objetivo es lograr cotas sublineales para ambas métricas.

Metodología

Los autores proponen un algoritmo de Optimización de Política Primal-Dual (Algoritmo 1) diseñado para manejar la interacción entre pérdidas adversarias y restricciones estocásticas en un entorno de aproximación de funciones lineales. El algoritmo integra cuatro componentes principales:

1. Inicialización de Época y Contracción de Características:
   El algoritmo opera en épocas. Una época comienza cuando el determinante de la matriz de diseño $\Lambda^k_h$ aumenta en un factor multiplicativo. Al inicializar, la política se reinicia a una política uniforme y la variable dual se reinicia a cero. Crucialmente, el algoritmo emplea contracción de características, reduciendo la característica original $\phi$ mediante una función sigmoidea para evitar que las estimaciones de la función Q se expandan sin control. Esta técnica, adaptada de Cassel & Rosenberg (2024), simplifica la representación de la política para argumentos de número de cobertura.

2. Ejecución de Política y Estimación:
   En cada episodio, el agente ejecuta acciones basadas en la política actual, observa la pérdida adversaria y el costo estocástico, y actualiza la matriz de diseño. Luego, estima los parámetros para las funciones de pérdida y costo y calcula estimaciones de la función Q ($\hat{Q}$) y estimaciones de la función de valor ($\hat{V}$) utilizando las características contraídas y bonificaciones optimistas.

3. Mezcla de Políticas Periódica:
   Una innovación central es la mezcla de políticas periódica. En lugar de mezclar la política (perturbándola hacia una política uniforme) en cada episodio, el algoritmo aplica la mezcla solo una vez cada $K^B$ episodios (donde $B=3/4$).

   • Motivación: La mezcla frecuente es necesaria para acotar la variable dual (mediante análisis de deriva) pero aumenta la complejidad de la clase de políticas (número de cobertura). La mezcla periódica equilibra estos requisitos competitivos.
   • Mecanismo: Cada $K^{3/4}$ episodios, la política actual $\hat{\pi}^k$ se mezcla con la política uniforme $\pi_{unif}$ mediante una combinación convexa: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. Actualización Dual Regularizada:
   La variable dual $Y^k$ (asociada a la restricción de costo) se actualiza utilizando un paso de ascenso de gradiente regularizado:
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   Los términos de regularización ($-4\alpha\eta H^3 Y^k$ y constantes) están diseñados para atraer la variable dual hacia cero, permitiendo un análisis de deriva de Lyapunov para acotar $Y^k$ sin depender de las suposiciones de dualidad fuerte que fallan en entornos adversarios.

5. Políticas Softmax LogSumExp Ponderadas:
   La clase de políticas resultante es un softmax LogSumExp ponderado. Debido a la mezcla periódica, la política no es una exponencial simple de la suma de funciones Q, sino una suma ponderada de exponenciales de sumas parciales de estimaciones de funciones Q. Esta estructura permite que la política se adapte a pérdidas elegidas adversariamente mientras mantiene un número de cobertura tratable.

Contribuciones Clave

1. Primeras Cotas Sublineales para CMDPs Lineales Adversarios:
   El artículo presenta el primer algoritmo que logra cotas sublineales de arrepentimiento y violación de restricciones en el escenario de CMDPs lineales con pérdidas adversarias y costos estocásticos. Las cotas son $\tilde{O}(K^{3/4})$, donde $K$ es el número de episodios.

2. Nuevo Argumento de Número de Cobertura:
   Los autores establecen un argumento novedoso de número de cobertura para las políticas softmax LogSumExp ponderadas. A diferencia de las políticas softmax estándar donde los pesos son uniformes, el proceso de mezcla introduce parámetros de peso variables $\zeta_i$. Los autores demuestran que el logaritmo del número de cobertura para esta clase crece como $\tilde{O}(n^2 d^2)$, donde $n$ es el número de pasos de mezcla y $d$ es la dimensión de las características. Este resultado no es trivial porque los parámetros de peso dependen tanto del parámetro de mezcla como de las estimaciones de la función Q.

3. Componentes Algorítmicos para el Control:
   El artículo introduce dos componentes novedosos para controlar conjuntamente el número de cobertura y la variable dual:

   • Mezcla de Políticas Periódica: Regula la frecuencia de la mezcla para evitar que el número de cobertura crezca demasiado (lo cual ocurriría con $O(K)$ pasos de mezcla) mientras sigue ocurriendo con la frecuencia suficiente para acotar la variable dual.
   • Actualización Dual Regularizada: Una nueva regla de actualización que incorpora un término de regularización para facilitar el análisis basado en deriva, permitiendo la acotación de la variable dual en ausencia de dualidad fuerte.

Resultados

Garantías Teóricas:
Bajo la condición de Slater (Suposición 1) y asumiendo $H^2 \leq K$, con probabilidad al menos $1-\delta$, el algoritmo logra:

• Arrepentimiento: $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• Violación de Restricciones: $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

Ambas métricas escalan sublinealmente con $K$ (específicamente $K^{3/4}$), lo que indica que el arrepentimiento promedio y la violación promedio de restricciones convergen a cero a medida que aumenta el número de episodios.

Experimentos Numéricos:
El algoritmo fue evaluado en un CMDP de programación de trabajos modificado con pérdidas adversarias. Durante $100,000$ episodios:

• Arrepentimiento: Creció sublinealmente, confirmando la cota teórica.
• Violación de Restricciones: Creció rápidamente al principio pero convergió a cero después de aproximadamente 45,000 episodios, validando la capacidad del algoritmo para satisfacer las restricciones de seguridad a largo plazo.

Significado y Afirmaciones

El artículo afirma ser el primer algoritmo demostrablemente eficiente para RL seguro con aproximación de funciones lineales en entornos adversarios. Su importancia radica en cerrar la brecha entre:

1. CMDPs Adversarios Tabulares: Trabajos anteriores (por ejemplo, Qiu et al., 2020) manejaron entornos adversarios pero se limitaron a espacios de estados pequeños y finitos.
2. CMDPs Lineales Estocásticos: Trabajos anteriores (por ejemplo, Ghosh et al., 2022) manejaron espacios de estados grandes pero asumieron entornos estacionarios (estocásticos).

Mediante la introducción de la política softmax LogSumExp ponderada y la estrategia de mezcla periódica, los autores demuestran que es posible manejar espacios de estados grandes (mediante aproximación lineal) y pérdidas adversarias simultáneamente. El artículo nota modestamente que, aunque se logra $\tilde{O}(K^{3/4})$, la cota óptima $\tilde{O}(\sqrt{K})$ sigue siendo una pregunta abierta para este escenario específico, particularmente en lo que respecta a la compensación entre pasos de mezcla y números de cobertura. El trabajo también destaca la dificultad de extender las actualizaciones duales basadas en medidas de ocupación a métodos basados en políticas en CMDPs lineales adversarios, justificando el enfoque propuesto de optimización de política primal-dual.