Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

Resumen Técnico: Complejidad de Tiempo Fuertemente Polinomial de la Iteración de Políticas para RMDPs con $L_\infty$

Planteamiento del Problema
El artículo aborda un problema fundamental abierto en la toma de decisiones secuenciales bajo incertidumbre: la existencia de algoritmos de tiempo fuertemente polinomial para Procesos de Decisión de Markov Robustos (RMDPs) con conjuntos de incertidumbre $L_\infty$ y un factor de descuento fijo. Mientras que los MDP clásicos admiten algoritmos de tiempo fuertemente polinomial para el cómputo exacto del valor (Ye, 2011), y existen algoritmos de tiempo polinomial para RMDPs mediante programación lineal, la cuestión de si los RMDPs admiten algoritmos fuertemente polinomiales (donde el número de operaciones aritméticas es independiente de la longitud de bits de los coeficientes de entrada) permanecía sin resolver. Específicamente, los intentos previos de reducir RMDPs $(s, a)$-rectangulares a juegos estocásticos de turnos alternos fallaron en producir reducciones de tiempo polinomial debido al número exponencial de acciones requeridas para representar los politopos de incertidumbre $L_\infty$.

Modelo y Definiciones
Los autores se centran en RMDPs $(s, a)$-rectangulares con conjuntos de incertidumbre $L_\infty$.

• $(s, a)$-rectangularidad: El entorno selecciona las probabilidades de transición de forma independiente para cada par estado-acción, preservando una estructura de programación dinámica.
• Incertidumbre $L_\infty$: Para cada par estado-acción $(s, a)$, el vector de transición real se encuentra dentro de una bola $L_\infty$ de radio $\delta_{s,a}$ alrededor de una estimación nominal $\hat{P}_{s,a}$.
• Objetivo: El agente busca una política $\sigma$ que minimice el costo esperado esperado en el peor de los casos contra una política de entorno adversaria $\tau$.
• Tiempo Fuertemente Polinomial: Un algoritmo es fuertemente polinomial si el número de operaciones aritméticas está acotado por un polinomio en el número de variables y restricciones, y el tamaño de los números durante el cómputo es polinomial en el tamaño de la entrada, independientemente de los valores numéricos de los coeficientes.

Metodología
El artículo analiza el algoritmo de Iteración de Políticas Robusta (PI), que alterna entre la Evaluación de la Política y la Mejora de la Política.

1. Cadenas de Markov Robustas (RMCs): Los autores analizan primero el caso más simple donde el agente tiene una única acción por estado (RMC-PI).

   • Mejora de la Política: En lugar de resolver un Programa Lineal (LP) que depende de la precisión de bits, los autores utilizan un Algoritmo de Homotopía (Behzadian et al., 2021) para computar la respuesta óptima del entorno. Este algoritmo se ejecuta en $O(n \log n)$ y produce políticas con una propiedad estructural específica: las probabilidades de transición se ajustan moviendo masa de estados "donantes" a estados "receptores" hasta que se alcanzan los límites (0, 1 o el radio de incertidumbre).
   • Función de Potencial: Se introduce una nueva función de potencial $f_\tau(s, s', s'')$ para rastrear la transferencia de masa de probabilidad permitida por el algoritmo de homotopía. Esta función mide la mejora potencial en el valor al desplazar masa de un estado con un valor menor óptimo a uno con un valor mayor óptimo.
   • Límites Combinatorios: Los autores demuestran que la "discrepancia" entre las probabilidades de transición de la política actual y las óptimas disminuye geométricamente. Crucialmente, establecen un lema combinatorio (Lema 8) relativo al número de Bits Más Significativos (MSB) distintos en sumas de subconjuntos con signo de números reales. Este lema, derivado de un teorema más general (Teorema 20/21), acota el número de posibles MSB por $O(|X| \log |X|)$.
   • Argumento de Convergencia: Al combinar la contracción geométrica del error de valor (Lema 2) con el número finito de MSB posibles para la discrepancia (Lema 8), los autores muestran que el algoritmo no puede realizar actualizaciones arbitrariamente pequeñas indefinidamente. El MSB de la discrepancia debe cambiar un número polinomial de veces.

2. MDPs Robustos (RMDPs): El análisis se extiende al caso general de RMDP (RMDP-PI).

   • El algoritmo resuelve iterativamente el subproblema RMC para la política actual del agente para encontrar la respuesta del entorno en el peor de los casos, luego actualiza la política del agente para minimizar el costo resultante.
   • Se define una función de potencial similar para las acciones, rastreando el costo de desviarse de la acción óptima del agente.
   • La misma lógica se aplica: la acción con el máximo potencial no puede persistir por más de un número logarítmico de iteraciones antes de que la contracción del error de valor fuerce un cambio.

Contribuciones Clave y Resultados

• RMC-PI de Tiempo Fuertemente Polinomial: Los autores demuestran que la Iteración de Políticas Robusta para RMCs con $n$ estados y un factor de descuento constante $\gamma$ termina en $O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ iteraciones. Dado que cada iteración implica operaciones de tiempo polinomial (inversión de matrices y pasos de homotopía), el tiempo de ejecución total es fuertemente polinomial.
• RMDP-PI de Tiempo Fuertemente Polinomial: El resultado se generaliza a RMDPs con $n$ estados y $m$ acciones. El algoritmo termina en $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ iteraciones, estableciendo que RMDP-PI también es fuertemente polinomial.
• Lema Combinatorio: El artículo introduce el Lema 8, un nuevo resultado combinatorio que acota los distintos MSB en sumas de subconjuntos con signo, el cual es central para la prueba de complejidad. Los autores señalan que una versión más fuerte de este teorema fue derivada independientemente por un agente de investigación de IA (Aletheia), destacando una contribución de la IA a las matemáticas.

Significancia y Reivindicaciones
El artículo afirma resolver un problema abierto importante en la teoría de la optimización robusta. Al demostrar que un algoritmo de iteración de políticas para RMDPs con $(s, a)$-rectangularidad e incertidumbre $L_\infty$ es de tiempo fuertemente polinomial, los autores generalizan el resultado seminal de Ye (2011) para los MDP clásicos al entorno robusto. Este resultado es significativo porque:

1. Proporciona una garantía teórica para computar valores exactos (en lugar de aproximaciones) para RMDPs sin dependencia de la longitud de bits de los parámetros de entrada.
2. Supera las limitaciones de las técnicas de reducción previas que fallaron debido al crecimiento exponencial en el número de acciones.
3. Establece que el operador de Bellman robusto, a pesar del conjunto de incertidumbre infinito, puede navegarse eficientemente utilizando propiedades combinatorias del algoritmo de homotopía.

Los autores concluyen que, si bien las bases teóricas están ahora establecidas, el trabajo futuro podría explorar estudios empíricos sobre conjuntos de incertidumbre basados en datos y si estos argumentos basados en potenciales pueden conducir a variantes prácticas mejoradas o criterios de parada. También señalan que la cuestión de los límites polinomiales para las variantes estándar de la iteración de políticas de MDP sigue abierta.