Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

Resumen Técnico: Redistribución de Recompensas para MDPs de CVaR mediante un Operador de Bellman en $L^\infty$

Planteamiento del Problema
En aplicaciones de seguridad crítica, optimizar el retorno esperado (neutral al riesgo) suele ser insuficiente, ya que puede permitir resultados catastróficos pero poco frecuentes. El Valor en Riesgo Condicional (CVaR) estático es una medida de riesgo coherente utilizada para controlar la cola inferior de la distribución de retornos. Sin embargo, a diferencia de los objetivos neutrales al riesgo, el CVaR estático de un retorno carece de separabilidad recursiva sobre el espacio de estados nominal, lo que impide una descomposición de Bellman de tipo Markoviano estándar.

Los enfoques existentes, notablemente el de Bäurle & Ott (2011), abordan esto aumentando el espacio de estados con una variable de "presupuesto" continua que rastrea las recompensas acumuladas. Aunque es teóricamente sólido, esta formulación sufre dos limitaciones prácticas críticas:

1. Recompensas Dispersas: La información relevante para el CVaR se concentra enteramente en un funcional terminal del estado aumentado. Esto resulta en recompensas por paso nulas en el MDP aumentado, lo que genera una retroalimentación retardada que exacerba los desafíos de exploración y de asignación de crédito temporal, particularmente en entornos de horizonte infinito.
2. Convergencia Restringida: El operador de Bellman asociado con la formulación de Bäurle & Ott solo está garantizado como una contracción en un conjunto altamente restringido de funciones no acotadas. En el espacio más práctico de funciones acotadas ($L^\infty$), el operador admite un punto fijo degenerado (la función cero), lo que hace que la iteración de valor y el Q-learning estándar sean inaplicables sin restricciones de inicialización cuidadosas y, a menudo, infactibles.

Metodología
Los autores proponen una nueva reformulación del objetivo de CVaR estático que resuelve estas limitaciones mediante una transformación algebraica de la función de valor.

1. MDP Aumentado Transformado: Basándose en el aumento de estado de Bäurle & Ott (2011), los autores definen una nueva función de valor $\bar{v}^*(s, z)$ que incorpora un término de desplazamiento $z^-$ (la parte negativa del presupuesto). Esta transformación permite la derivación de un nuevo operador de Bellman, $\bar{T}$, definido en el espacio de funciones acotadas $L^\infty(\bar{S})$.
2. Redistribución de Recompensas: La innovación clave es la definición de una nueva función de recompensa por paso $\tilde{r}(s, z, a) = z^- - (r(s, a) + z)^-$. A diferencia de la formulación anterior que producía recompensas intermedias nulas, esta nueva recompensa es densa e informativa en cada paso, redistribuyendo efectivamente la señal de CVaR a lo largo de la trayectoria.
3. Propiedades de Contracción: Los autores demuestran que el nuevo operador $\bar{T}$ es una contracción-$\gamma$ con respecto a la norma sup en el espacio completo de funciones acotadas. Esto asegura que la iteración de valor converja a un punto fijo único sin requerir las restrictivas condiciones de inicialización del trabajo previo.
4. Discretización y Aproximación: Dado que el estado aumentado $z$ es continuo, los autores emplean un esquema de discretización uniforme. Definen operadores de cota inferior y superior ($\bar{T}^l$ y $\bar{T}^u$) utilizando funciones envolventes para aproximar el operador real. Establecen límites teóricos que muestran que el error entre el CVaR óptimo y la aproximación discretizada escala proporcionalmente con la granularidad de la discretización y el factor de descuento.
5. Algoritmos: Basándose en este marco, el artículo desarrolla:
   • Iteración de Valor de CVaR Estático: Un algoritmo basado en modelo que computa la función Q-óptima para todos los estados iniciales y niveles de presupuesto simultáneamente.
   • Q-Learning de CVaR Estático: Un algoritmo libre de modelo que utiliza una estrategia de actualización por bloques. Aprovechando la naturaleza determinista de la transición del estado aumentado, el algoritmo relabeliza una sola trayectoria para actualizar los valores Q de múltiples hipótesis de presupuesto inicial, mejorando la eficiencia de los datos. La convergencia se demuestra bajo las condiciones estándar de tamaño de paso de Robbins-Monro.

Contribuciones Clave

• Nuevo Operador de Bellman: El artículo introduce un operador de Bellman para el CVaR estático de horizonte infinito que opera en un espacio de estados aumentado, es exacto con respecto al objetivo de control, proporciona recompensas por paso no dispersas y es un mapeo de contracción en funciones acotadas.
• Garantías de Aproximación: Los autores proporcionan límites de error de aproximación rigurosos para el CVaR discretizado, cuantificando la brecha de rendimiento como una función de la resolución de la rejilla.
• Pruebas de Convergencia: El artículo establece condiciones suficientes para la convergencia del algoritmo de Q-learning propuesto hacia la función de valor-acción óptima en el espacio aumentado discretizado.
• Optimalidad Global: Los algoritmos producen soluciones globalmente óptimas para todos los niveles de riesgo (estados aumentados iniciales) en una sola ejecución, en lugar de requerir un entrenamiento separado para cada parámetro de riesgo.

Resultados Empíricos
Los autores validan su enfoque en un entorno de mundo de rejilla estocástico ("Crater Walk") donde un agente debe navegar desde un inicio hasta una meta evitando un cráter (penalización alta) y minimizando el uso de combustible (penalización por paso).

• Sensibilidad al Riesgo: Las políticas aprendidas ajustan con éxito el comportamiento basándose en el parámetro de riesgo $\alpha$. A medida que $\alpha$ disminuye (aumentando la aversión al riesgo), la cola inferior de la distribución de retornos se reduce, y el agente evita el cráter con mayor frecuencia, incluso si esto requiere un camino más largo.
• Desempeño: Tanto el algoritmo de Iteración de Valor como el de Q-learning logran equilibrios efectivos entre desempeño y seguridad. El algoritmo de Q-learning converge dentro de 50,000 iteraciones de entrenamiento.
• Precisión de la Discretización: Los experimentos variando la resolución de la discretización (de 100 a 5000 celdas) demuestran que las curvas de desempeño de los operadores de cota superior e inferior convergen al valor óptimo real a medida que la resolución aumenta, validando empíricamente los límites de error teóricos.

Significado y Reivindicaciones
El artículo sostiene que las limitaciones de las recompensas dispersas y las garantías de convergencia restringidas en los MDP de CVaR estático no son intrínsecas al problema, sino artefactos de elecciones de modelado específicas en la literatura previa. Al proponer una reformulación exacta que redistribuye las recompensas y opera sobre funciones acotadas, los autores permiten la aplicación de técnicas estándar de programación dinámica y aprendizaje por refuerzo libre de modelo a problemas de riesgo sensible estático. Este trabajo sienta las bases para algoritmos de RL con aversión al riesgo escalables que no dependen de topes de recompensa heurísticos o currículos de riesgo especializados. Los autores señalan que, aunque su análisis empírico se centra en entornos tabulares, el marco teórico respalda extensiones futuras hacia la aproximación de funciones (por ejemplo, redes neuronales profundas) para manejar espacios de estados continuos sin restricciones de signo de la recompensa.