Resumen Técnico: Aprendizaje por Refuerzo de Recompensa Promedio Robusto Libre de Modelo con Análisis de Complejidad de Muestreo

1. Formulación del Problema

El artículo aborda el desafío del Aprendizaje por Refuerzo (RL) Robusto bajo el criterio de recompensa promedio. Aunque el RL ha logrado el éxito en entornos controlados, el despliegue en el mundo real suele sufrir de la brecha "Sim-to-Real" debido a desajustes del modelo, perturbaciones ambientales o ataques adversarios. El RL robusto mitiga esto optimizando el rendimiento en el peor de los casos dentro de un conjunto de incertidumbre de las dinámicas de transición.

El enfoque específico son los MDP de Recompensa Promedio Distribucionalmente Robustos (RAMDPs). A diferencia de los entornos de recompensa con descuento, el criterio de recompensa promedio es esencial para el rendimiento en estado estacionario a largo plazo en aplicaciones como el control de colas y la optimación de carteras. Sin embargo, el RL de recompensa promedio robusto es significativamente más desafiante que su contraparte con descuento debido a:

1. Operadores no contractivos: El operador de Bellman robusto es generalmente no expansivo en lugar de contractivo, lo que invalida las garantías de convergencia iterativa estándar.
2. Incógnitas duales: La ecuación de Bellman robusta involucra dos variables desconocidas: la función de valor (o sesgo) $Q$ y la recompensa promedio óptima $g^*_P$.
3. No linealidad: Estimar la expectativa del peor caso (función de soporte) a partir de muestras nominales introduce sesgo, particularmente en entornos libres de modelo (model-free).

La literatura existente se basa mayoritariamente en garantías asintóticas, enfoques basados en modelos que requieren conocimiento previo de los parámetros del problema (como el span de sesgo $H$), o métodos de reducción que sufren de una complejidad de muestreo subóptima o requieren supuestos estructurales fuertes (por ejemplo, irreducibilidad con coeficientes de contracción específicos).

2. Metodología: Iteración de Halpern Robusta (RHI)

Los autores proponen la Iteración de Halpern Robusta (RHI), un algoritmo libre de modelo diseñado para resolver la ecuación de Bellman robusta sin requerir conocimiento previo de los parámetros del MDP.

2.1. Núcleo Algorítmico

El algoritmo RHI está inspirado en la Iteración de Halpern de la literatura de optimización, adaptada para manejar los desafíos específicos del RL de recompensa promedio robusto:

• Formulación de Espacio Cociente: Para abordar la "maldición de las variables duales" (la incógnita $g^*_P$), los autores embeben el problema en un espacio cociente $\mathbb{R}^{SA} / \sim$, donde los vectores que difieren solo por un desplazamiento constante son equivalentes. Esto permite al algoritmo resolver la ecuación proximal $T_P(Q) - Q = ce$ sin conocer explícitamente $g^*_P$.
• Actualización de Halpern: En lugar de la iteración de valor estándar, RHI utiliza una combinación convexa de la inicialización y la actualización del operador:
  $$[Q_{k+1}] = [(1 - \beta_{k+1})Q_0 + \beta_{k+1} T_P(Q_k)]$$
  donde $\beta_k = k/(k+2)$. Este enfoque proporciona garantías de convergencia para operadores no expansivos sin depender de coeficientes de contracción.

2.2. Oráculo de Muestreo de Caja Negra (R-SAMPLE)

Dado que el operador robusto $T_P$ es no lineal e involucra una expectativa del peor caso, los autores introducen un oráculo de muestreo de caja negra, R-SAMPLE. Este oráculo estima la diferencia entre las funciones de soporte robustas en iteraciones consecutivas utilizando únicamente muestras del núcleo nominal.

• El oráculo devuelve un incremento aleatorio $D_k$ tal que su esperanza aproxima la diferencia en los valores del operador de Bellman robusto.
• La complejidad de muestreo del algoritmo se deriva basándose en las propiedades de este oráculo (constante de Lipschitz, sesgo y costo de muestra).

2.3. Estimador de Monte Carlo de Niveles Múltiples de Orden K (K-Order MLMC)

Para implementar concretamente el oráculo R-SAMPLE con bajo sesgo, los autores proponen un estimador MLMC de orden K.

• Motivación: Los estimadores de inserción (plug-in) estándar y los estimadores MLMC vanilla para funciones de soporte robustas sufren de un sesgo de $O(1/N)$, lo que conduce a una complejidad de muestreo de $\tilde{O}(\epsilon^{-3})$.
• Mecanismo: El estimador de orden K construye una combinación lineal de estimadores de un solo nivel en diferentes tamaños de muestra ($N_\ell = 2^\ell N_0$). Al elegir cuidadosamente los pesos $w^{(K)}_\ell$, el estimador cancela los primeros $K$ términos de la expansión del sesgo.
• Resultado: Esto reduce el sesgo a $\tilde{O}(N_0^{-(K+1)})$, permitiendo una complejidad de muestreo total mucho más ajustada.

3. Contribuciones Clave

1. Un Algoritmo Universal Libre de Modelo: RHI es el primer algoritmo libre de modelo para el RL de recompensa promedio robusto que no requiere conocimiento previo del span óptimo robusto $H$ o del tiempo de mezcla, superando las limitaciones de los enfoques basados en reducción.
2. Estimador MLMC de Orden K: Los autores diseñan un estimador novedoso que reduce significativamente el sesgo en comparación con métodos MLMC previos. Esto es crucial para lograr una complejidad de muestreo cercana a la óptima en presencia de funciones de soporte robustas no lineales.
3. Análisis de Complejidad de Muestreo de Muestra Finita: El artículo proporciona un análisis riguro de muestra finita para RHI bajo un entorno de modelo generativo.
   • Para conjuntos de incertidumbre de divergencia KL y $\chi^2$, la complejidad de muestreo para encontrar una política $\epsilon$-óptima es $\tilde{O}\left(SAH^2 \epsilon^{-(2+o(1))}\right)$.
   • Para conjuntos de norma-$\ell_p$ y contaminación, la complejidad es $\tilde{O}\left(SAH^2 \epsilon^{-2}\right)$.
   • Aquí, $S$ y $A$ son el número de estados y acciones, y $H$ es el span de sesgo óptimo robusto.
4. Variante Libre de Parámetros (PF-RHI): Los autores proponen una variante de RHI que utiliza un truco de duplicación (doubling trick) para determinar el número de iteraciones dinámicamente, eliminando la necesidad de preespecificar el horizonte basado en el parámetro desconocido $H$, manteniendo la misma complejidad de muestreo.

4. Resultados y Garantías Teóricas

• Convergencia: Se demuestra que el algoritmo RHI exacto converge asintóticamente, con el span del residuo de Bellman y la brecha de sub-optimalidad desvaneciéndose a medida que aumentan las iteraciones.
• Complejidad de Muestreo: La complejidad de muestreo derivada para conjuntos KL y $\chi^2$ coincide asintóticamente con los mejores límites conocidos para enfoques basados en modelos (ej., Roch et al., 2025; Chen et al., 2025). El término $o(1)$ en el exponente representa una penalización sub-polinomial que desaparece cuando $\epsilon \to 0$, distinguiéndose de la complejidad $\epsilon^{-3}$ de los métodos que utilizan MLMC estándar.
• Validación Experimental: Experimentos numéricos en el problema de Garnet y diversos conjuntos de incertidumbre (contaminación, $\ell_\infty$, $\ell_2$) demuestran que RHI converge a la recompensa promedio robusta óptima y que el estimador MLMC de orden K reduce eficazmente el sesgo en comparación con métodos estándar.

5. Significado y Reivindicaciones

El artículo afirma establecer a RHI como el algoritmo de vanguardia (SOTA) libre de modelo para el RL de recompensa promedio robusto. Su importancia radica en:

• Cerrar la Brecha: Cierra la brecha entre las garantías asintóticas y el análisis de muestra finita en el RL de recompensa promedio robusto.
• Practicidad: Al ser libre de modelo y no requerir conocimiento previo de $H$, el algoritmo es más práctico para el despliegue en el mundo real donde tales parámetros son desconocidos.
• Optimalidad: La complejidad de muestreo coincide asintóticamente con los límites más ajustados conocidos para métodos basados en modelos, demostrando que los enfoques libres de modelo pueden lograr una eficiencia similar sin la sobrecarga de la construcción del modelo.
• Reducción de Sesgo: El diseño de MLMC de orden K ofrece una mejora fundamental sobre los estimadores de RL robusto anteriores, resolviendo el problema de la alta complejidad de muestreo causada por el sesgo no mitigado en la estimación de funciones no lineales.

Los autores señalan que su análisis asume un modelo generativo (acceso a un simulador) para aislar la complejidad estadística. Las extensiones a entornos de exploración-explotación (online) o de datos históricos (offline) se identifican como trabajo futuro. Además, la brecha sub-polinomial en la complejidad de muestreo para los conjuntos KL/$\chi^2$ se atribuye al compromiso inherente entre sesgo y varianza en la estimación de funcionales no lineales, lo cual sigue siendo un desafío abierto para eliminarlo completamente en entornos libres de modelo.