Multi-Environment POMDPs with Finite-Horizon Objectives

Resumen Técnico: MEPOMDPs con Objetivos de Horizonte Finito

Enunciado del Problema
Este trabajo aborda el problema de calcular valores y políticas óptimos en Procesos de Decisión de Markov Parcialmente Observables Multi-Ambiente (MEPOMDPs) con objetivos de horizonte finito. En un Proceso de Decisión de Markov Parcialmente Observable (POMDP) estándar, un agente interactúa con un entorno estocástico recibiendo solo información parcial del estado. Un MEPOMDP extiende esto asumiendo que el estado inicial es desconocido y elegido de manera adversaria desde un conjunto de $n$ estados iniciales posibles $\{s_1, \dots, s_n\}$. El agente debe calcular una única política que maximice la recompensa esperada mínima a través de todos los entornos iniciales posibles. El objetivo es maximizar la suma de recompensas sobre un horizonte finito $k$.

El artículo se centra en dos problemas computacionales:

1. El Problema del Valor: Calcular el valor óptimo $v = \sup_{\sigma} \min_{i \in [n]} E^k_{s_i}(\sigma)$.
2. El Problema del Umbral: Decidir si $v \ge \lambda$ para un umbral racional $\lambda$ dado.

Una sutileza teórica crítica identificada es que, a diferencia de los POMDPs estándar donde las políticas deterministas son suficientes para la optimalidad, los MEPOMDPs generalmente requieren políticas aleatorizadas para alcanzar el valor óptimo, ya que las estrategias deterministas pueden no satisfacer la restricción del estado inicial en el peor de los casos.

Metodología y Algoritmos
Los autores desarrollan tanto límites de complejidad teórica como algoritmos prácticos para resolver estos problemas.

• Análisis de Complejidad: El artículo establece que el problema del umbral y su versión aproximada son PSPACE-completos. La cota inferior se hereda de la conocida dureza PSPACE de los POMDPs estándar (donde $n=1$). La cota superior se demuestra mediante un algoritmo no determinista que aprovecha el teorema de Carathéodory. Este teorema implica que si existe una política que logra un cierto valor a través de $n$ entornos, existe una "mezcla" de a lo sumo $n$ políticas deterministas que logra la misma garantía. Esto permite reducir el espacio de búsqueda a combinaciones de un número limitado de estrategias deterministas.

• Algoritmo Determinista Eficiente en Espacio (Algoritmo 2): Para evitar los requisitos de espacio exponencial de la determinización estándar (por ejemplo, mediante el teorema de Savitch), los autores presentan un algoritmo determinista que opera dentro de un espacio polinómico. En lugar de adivinar políticas completas, el algoritmo enumera posibles valores de recompensa esperada multi-ambiental y verifica su alcanzabilidad de forma recursiva. Construye sumas parciales de la ecuación de actualización de Bellman, verificando si un valor objetivo puede descomponerse en sub-estrategias válidas. Aunque es teóricamente óptimo en espacio ($O(|S| \cdot |O| \cdot n \cdot k \cdot \pi(N))$), los autores señalan que este enfoque es computacionalmente inviable para la mayoría de las instancias prácticas debido a los bucles anidados.

• Algoritmo Práctico Eficiente en Tiempo (Algoritmo 3): Para la evaluación empírica, los autores proponen un algoritmo de abajo hacia arriba que calcula el conjunto de recompensas esperadas multi-ambientales alcanzables para horizontes crecientes. Este método mantiene un conjunto de vectores de recompensa no dominados (la "frontera"). En cada paso, poda los vectores que están convexamente dominados por otros, ya que estos corresponden a familias de políticas que no requieren mayor exploración. Aunque este algoritmo puede usar espacio exponencial en el peor de los casos, está diseñado para ser escalable en la práctica.

Contribuciones Clave

1. Clasificación de Complejidad: El artículo demuestra que calcular valores en MEPOMDPs con horizontes finitos es PSPACE-completo, igualando la complejidad de los POMDPs estándar a pesar de la restricción añadida del estado inicial adversario.
2. Perspectiva Teórica: Demuestra que las políticas óptimas en MEPOMDPs pueden representarse como mezclas de a lo sumo $n$ políticas deterministas, donde $n$ es el número de entornos iniciales.
3. Avances Algorítmicos:
   • Un algoritmo determinista de espacio polinómico (Algoritmo 2) que proporciona una cota superior teórica sobre la complejidad espacial.
   • Un algoritmo práctico y eficiente en tiempo (Algoritmo 3) que utiliza la poda de vectores de recompensa dominados.
4. Validación Empírica: El algoritmo práctico se evalúa frente al único algoritmo exacto previamente conocido (de Bovy et al. [1]) en tres conjuntos de pruebas: Rock Sample, Navegación de Robots e Identificación (Amigo o Enemigo).

Resultados
Los resultados experimentales indican que el algoritmo práctico propuesto (Algoritmo 3) supera significativamente a la herramienta de última generación de [1].

• Rendimiento: El nuevo método resuelve instancias con hasta 574 estados y horizontes hasta $k=7$ dentro de plazos razonables, mientras que la herramienta base frecuentemente agota el tiempo (límite de 3600s) en instancias mucho más pequeñas.
• Escalabilidad: El tiempo de cálculo escala fuertemente con el horizonte $k$, que se identifica como el principal cuello de botella para la escalabilidad. El número de estados y entornos iniciales tiene un efecto menos dominante en el tiempo de ejecución en comparación con el horizonte.
• Comparación: En las pruebas de Rock Sample, el método propuesto resolvió instancias donde la base agotó el tiempo, logrando a menudo aceleraciones de varias órdenes de magnitud (por ejemplo, resolviendo una instancia de 574 estados en ~784 segundos frente a un agotamiento de tiempo para la base).

Significado y Limitaciones
El artículo reclama importancia al proporcionar los primeros límites de complejidad ajustados para MEPOMDPs y ofrecer un algoritmo práctico que mejora sustancialmente las herramientas existentes. Los autores reconocen un compromiso estándar entre el rendimiento teórico y práctico: el algoritmo eficiente en espacio (Algoritmo 2) es teóricamente sólido pero prácticamente lento, mientras que el algoritmo eficiente en tiempo (Algoritmo 3) es rápido en la práctica pero carece de una garantía de espacio polinómico en el peor de los casos.

El trabajo se limita a objetivos de horizonte finito. Los autores señalan que, aunque el problema exacto para objetivos de suma descontada es indecidible para POMDPs, su algoritmo podría adaptarse potencialmente para objetivos descontados aproximados reduciéndolos a problemas de horizonte finito, aunque esto permanece como trabajo futuro. El artículo no propone nuevas aplicaciones más allá de las pruebas estándar utilizadas para la evaluación.