Por qué una sola estrategia no basta: carteras de políticas adaptativas para MDP robustos
Los procesos de decisión de Markov (MDP) clásicos asumen que la dinámica del entorno se conoce con exactitud. En la práctica, esto casi nunca es así: solo podemos delimitar un conjunto de escenarios plausibles. Los MDP robustos abordan esto de forma radical: buscan una única política que funcione lo suficientemente bien ante la peor de las transiciones posibles. Pero este enfoque tiene un coste oculto: está ajustado al peor caso y, por tanto, suele resultar excesivamente conservador.
Esto se nota especialmente en situaciones en las que la incertidumbre disminuye con el tiempo. El entorno se despliega ante el agente y parte de su dinámica se vuelve observable y parcialmente identificable. La política óptima calculada antes del despliegue no aprovecha esta nueva información. En esencia, seguimos jugando al peor caso incluso allí donde ya sabemos que no se ha materializado. Investigadores de la Universidad de Twente y de Amberes — Kasper Engelen, Sebastian Junges, Guillermo A. Pérez y Marnix Suilen — en su trabajo «Adaptive Policy Portfolios for Robust Markov Decision Processes» (arXiv:2608.17929, cs.AI/cs.LO) proponen un enfoque más flexible.
Carteras adaptativas: un conjunto de políticas en lugar de una sola
En lugar de una única política robusta, los autores consideran una cartera de políticas: un conjunto finito de políticas aleatorizadas sin memoria que se sintetizan de antemano, fuera de línea. Además, se utiliza un selector en línea ligero que, durante el funcionamiento, elige la política más adecuada de la cartera. Esto recuerda a un conjunto de modelos en aprendizaje automático, pero con una formulación teórica clara.
La métrica clave de calidad de dicha cartera es el regret robusto. Para cada entorno concreto del conjunto de escenarios plausibles, mide en qué medida la política elegida por el selector en línea se queda corta respecto a la política ideal que habríamos construido si hubiéramos conocido ese entorno de antemano. En otras palabras, una cartera se considera buena si su mejor miembro está lo bastante cerca del óptimo para cualquier entorno. Esta visión desplaza el énfasis de las garantías en el peor caso al coste de la adaptación.
Ideas similares fueron desarrolladas anteriormente por Ghavamzadeh et al. (2016), pero con el foco en métodos aproximados y relajaciones para la mejora segura de políticas. El nuevo trabajo avanza sustancialmente los fundamentos teóricos de este campo.
Complejidad de la certificación y la síntesis
La cartera no es solo una heurística de ingeniería. Los autores ofrecen un análisis teórico-computacional cuidadoso de los problemas que surgen al trabajar con carteras.
El primer problema es la certificación de una cartera dada: ¿se puede garantizar que, para todos los entornos plausibles, exista una política con un regret aceptable? Resulta que este problema es ∀R-completo ya para carteras deterministas en RMDP acíclicos con rectangularidad (s,a). Esto significa que verificar la calidad incluso de un pequeño conjunto de políticas es una tarea computacionalmente difícil, comparable en complejidad a resolver sistemas de desigualdades reales.
Aún más difícil es el problema de síntesis de una cartera de tamaño acotado (unary-bounded). Para politopos racionales generales resulta ser ∃∀R-completo — incluso con un factor de descuento fijo y dinámica acíclica. Esta complejidad indica que aquí no existen algoritmos combinatorios simples: el problema combina tanto la búsqueda discreta como la complejidad algebraica. Es notable que incluso el caso de una única política sea no trivial y «costoso» en ambos ejes.
¿Cómo acercar esto a la práctica?
Los resultados sobre complejidad pueden intimidar, pero los autores no se detienen en conclusiones negativas. Proponen una construcción concreta de cartera fuera de línea que admite especialización en tiempo de ejecución. La idea es preparar de antemano un conjunto de políticas y, ya durante la interacción con el entorno, ajustar rápidamente la selección a la observación actual. Este enfoque permite combinar garantías rigurosas con flexibilidad práctica.
La conclusión es simple: en tareas donde la incertidumbre se revela parcialmente con el tiempo, una estrategia fija es necesariamente más débil que un conjunto adaptativo. La cartera de políticas paga una mayor complejidad computacional, pero a cambio ofrece margen de error y la capacidad de cambiar según llegan los datos. Es un paso importante en el camino desde los métodos puramente conservadores hacia sistemas inteligentes de toma de decisiones en condiciones de incertidumbre.
