💻 computer science

Distributionally Robust Markov Games with Average Reward

Este artículo establece la existencia teórica de equilibrios de Nash estacionarios para juegos de Markov distributivamente robustos tanto en entornos irreducibles como débilmente comunicantes bajo criterios de recompensa promedio, al tiempo que propone algoritios convergentes y demuestra su aproximación mediante contrapartes descontadas.

Autores originales: Zachary Roch, Yue Wang

Publicado 2026-06-23

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Zachary Roch, Yue Wang

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina a un grupo de amigos intentando navegar por un laberinto juntos. En un mundo perfecto, conocen exactamente dónde está cada pared y a dónde lleva cada puerta. Pero en el mundo real, el mapa que tienen puede ser ligeramente erróneo. Tal vez una pared se movió, o una puerta está trabada. Este es el problema del desajuste del modelo (model mismatch): el plan que hicieron no coincide con la realidad en la que se encuentran realmente.

Este artículo presenta una nueva forma para que estos amigos tomen decisiones que funcione incluso cuando su mapa es incorrecto, y cuando están jugando durante mucho tiempo (no solo una carrera rápida).

Aquí está el desgido de su solución utilizando analogías simples:

1. El Problema: "¿Qué pasa si el mapa está mal?"

Normalmente, cuando se enseña a las computadoras a jugar juegos o a tomar decisiones (como robots en un almacén o coches en una autopista), se asume que las reglas son fijas. Pero en la realidad, las cosas cambian.

La forma antigua: La mayoría de los métodos anteriores se centraban en objetivos a corto plazo (como "llegar a la salida en 10 pasos") o utilizaban un "descuento" (valorando una recompensa hoy más que una recompensa mañana). Esto es como un corredor que corre una carrera corta; no le importa el desgaste a largo plazo de sus zapatillas.
El nuevo desafío: Los autores querían resolver el problema de la Recompensa Promedio (Average Reward). Esto es como un corredor de maratón que necesita mantener un ritmo constante y sostenible para siempre. Le importa la velocidad promedio de toda la carrera, no solo de la primera milla.
El giro: También querían ser Distribucionalmente Robustos (Distributionally Robust). Esto significa que los jugadores asumen el "peor escenario posible" para el mapa. No solo esperan que el mapa sea correcto; planean como si un "duende travieso" estuviera constantemente intentando cambiar las paredes para hacerles la vida lo más difícil posible.

2. El Gran Obstáculo: "El laberinto es demasiado complicado"

Los autores explican que mezclar "objetivos de promedio a largo plazo" con "planificación para el peor de los casos" es increíblemente difícil.

La analogía: Imagina intentar encontrar el mejor camino en un laberinto donde las paredes se mueven cada vez que das un paso, y tienes que seguir caminando para siempre. En juegos más simples (carreras cortas), puedes trabajar hacia atrás desde la meta. Pero en un maratón interminable, no hay una meta desde la cual trabajar hacia atrás.
El descubrimiento: Demostraron que sin ciertas reglas (como que el laberinto esté "conectado", de modo que puedas ir de cualquier habitación a cualquier otra), es posible que ni siquiera exista una estrategia perfecta y estable. Es como intentar encontrar un único "mejor movimiento" en un juego donde las reglas cambian tan salvajemente que ningún movimiento es realmente seguro.

3. La Solución: Encontrar un "Acuerdo Estable"

El artículo demuestra que si el entorno está "bien conectado" (puedes llegar eventualmente a cualquier lugar), existe un Equilibrio de Nash.

¿Qué es un Equilibrio de Nash? Piensa en ello como un "armisticio estable". Es un conjunto de estrategias donde ningún jugador individual puede mejorar su puntuación promedio cambiando su propio plan, asumiendo que todos los demás mantienen el suyo. Incluso con los cambios de mapa del peor de los casos, todos acuerdan una estrategia que es lo mejor que pueden hacer dado el caos.
El gran avance: Los autores mostraron cómo demostrar matemáticamente que este acuerdo existe, incluso cuando el "duende" intenta romper el juego. Lo hicieron creando una ecuación especial (una "ecuación de Bellman") que equilibra la recompensa inmediata con el promedio a largo plazo, teniendo en cuenta los cambios del mapa en el peor de los casos.

4. Las Herramientas: Dos Nuevos Algoritmos

Para encontrar realmente este "armisticio estable", los autores construyeron dos nuevas herramientas (algoritmos):

Herramienta A: Iteración de Nash Robusta (La "Negociación Iterativa")
- Cómo funciona: Imagina a los jugadores sentados alrededor de una mesa. Se turnan para decir: "Si todos ustedes mantienen su plan actual, este es el mejor movimiento para mí". Siguen actualizando sus planes basándose en lo que hacen los demás.
- El inconveniente: Este método funciona perfectamente pero requiere una "supercomputadora" para resolver un complejo acertijo matemático en cada paso. Es como necesitar a un genio matemático para resolver un Sudoku cada vez que das un paso en el laberinto.
Herramienta B: Descenso TD Robusto (El "Ascenso Suavizado")
- Cómo funciona: Este es un método más inteligente y práctico. En lugar de resolver un acertijo difícil cada vez, los jugadores dan pequeños pasos cuesta abajo en una "colina de felicidad". Miden qué tan "equivocado" está su plan actual (el error) y ajustan suavemente su estrategia para reducir ese error.
- El truco: Debido a que las matemáticas son dentadas y accidentadas (debido a la planificación del peor de los casos), primero "suavizaron" la colina, como si lijaran una pieza de madera rugosa. Esto les permite deslizarse hacia la mejor solución sin quedarse atrapados en un bulto. Este método es mucho más rápido y no necesita una supercomputadora.

5. El Puente: Conectando Corto y Largo

Finalmente, los autores mostraron un atajo ingenioso.

La analogía: Demostraron que si juegas el juego con un "descuento" (valorando el presente ligeramente más que el futuro) pero haces que ese factor de descuento sea extremadamente cercano a 1 (lo que significa que te importa casi exactamente tanto el futuro como el presente), obtienes casi el mismo resultado que un plan perfecto de promedio a largo plazo.
Por qué es importante: Esto significa que podemos usar herramientas ya existentes y bien comprendidas, diseñadas para juegos de corto plazo, para aproximar la solución de estos complejos escenarios de largo plazo y de peor de los casos. Es como usar una brújula estándar para navegar en un maratón si solo ajustas la aguja ligeramente.

Resumen

En resumen, este artículo proporciona una garantía matemática y un conjunto de herramientas prácticas para que grupos de agentes (como robots o IA) cooperen o compitan eficazmente a largo plazo, incluso cuando no conocen las reglas exactas del juego y esperan que el entorno intente engañarlos. Demostraron que existe una solución estable y dieron dos formas de encontrarla: una precisa pero pesada, y otra práctica y suave.

Resumen Técnico: Juegos de Markov Distribucionalmente Robustos con Recompensa Promedio

Formulación del Problema

Este artículo aborda el desafío de la toma de decisiones multiagente en entornos caracterizados por la incertidumbre del modelo y horizontes operativos extendidos. Mientras que los Juegos de Markov (MG) proporcionan un marco para sistemas multiagentes competitivos, las formulaciones estándar a menudo no logran considerar la brecha "Sim-to-Real", donde el modelo de transición asumido diverge del entorno real debido a la no estacionariedad, errores de modelado o perturbaciones adversarias.

Para mitigar esto, los autores estudian los Juegos de Markov Distribucionalmente Robustos (DR-MGs), donde los agentes optimizan para el desempeño en el peor de los casos sobre un conjunto de incertidumbre predefinido de núcleos de transición. Crucialmente, este trabajo se centra en el criterio de recompensa promedio en lugar de los entornos más comúnmente estudiados de horizonte finito o de recompensa descontada. El criterio de recompensa promedio es esencial para sistemas que operan en horizontes de tiempo indefinidos (por ejemplo, robótica de almacenes, redes de comunicación), pero presenta obstáculos teóricos significativos:

Fallo de la Dualidad Min-Max: En entornos robustos, el núcleo de transición del peor caso para un agente puede diferir del de otro, rompiendo la estructura de punto de silla incluso en juegos de suma cero.
Complejidad Estructural: A diferencia de los entornos descontados, la correspondencia entre políticas estacionarias y frecuencias de estado-acción se rompe en los entornos de recompensa promedio sin supuestos estructurales restrictivos.
Falta de Soluciones Existentes: Los métodos previos para DR-MGs de recompensa descontada o MG de recompensa promedio no robustos no pueden extenderse directamente al entorno de recompensa promedio robusto debido a la no contracción de los operadores de Bellman y la no unicidad de las soluciones.

El artículo demuestra que, sin supuestos estructurales, los DR-MGs de recompensa promedio pueden no admitir un Equilibrio de Nash (NE) estacionario, como lo muestra un contraejemplo construido de un juego de dos jugadores de suma cero.

Metodología

1. Fundamentos Teóricos: Existencia de Equilibrio

Los autores establecen la existencia de un equilibrio de Nash robusto y estacionario bajo dos supuestos estructurales distintos:

Entorno Irreducible: Asumiendo que para cualquier política conjunta estacionaria y cualquier núcleo admisible, la cadena de Markov inducida es irreducible (todos los estados pertenecen a una única clase recurrente).
- Los autores derivan una correspondencia entre las políticas óptimas y las soluciones de la ecuación de Bellman robusta.
- Demuestran que la ecuación de Bellman robusta admite una solución única (salvo un vector constante) para la ganancia y el sesgo (bias).
- Utilizando estos resultados, muestran que el mapeo de mejor respuesta es no vacío, convexo y semicontinuo superior. Al aplicar el teorema del punto fijo de Kakutani, demuestran la existencia de un NE robusto estacionario.
Entorno Débilmente Comunicante: Un entorno más general donde el espacio de estados puede descomponerse en estados transitorios y una unión de clases recurrentes.
- En este entorno, la correspondencia directa entre políticas y soluciones de Bellman falla.
- Los autores construyen un mapeo de conjunto valorado proxy basado en el operador de Bellman robusto de ganancia constante.
- Demuestran que este mapeo proxy es un subconjunto del verdadero mapeo de mejor respuesta y satisface las condiciones del teorema del punto fijo de Kakutani, estableciendo así la existencia de un NE robusto estacionario incluso en este contexto más amplio.

2. Soluciones Algorítmicas

El artículo propone dos algoritmos para computar el NE robusto:

Iteración de Nash Robusta (Robust Nash-Iteration): Una extensión de la iteración de valor de Nash estándar. Mantiene estimaciones de sesgo y resuelve para un Equilibrio de Nash de un juego de etapa definido por valores Q robustos en cada paso.
- Convergencia: Se demuestra que converge a un NE robusto bajo el supuesto de irreducibilidad y un supuesto adicional respecto a la selección de los equilibrios del juego de etapa (por ejemplo, optimalidad global o selección de punto de silla).
- Limitación: Requiere un oráculo para computar el NE del juego de etapa, lo cual es PPAD-completo en entornos de suma general.
Descenso de TD Robusto (Robust TD Descent): Un algoritmo actor-crítico de dos escalas de tiempo diseñado para evitar la necesidad de un oráculo de NE.
- Mecanismo: Caracteriza el NE robusto mediante la minimización de una brecha de Diferencia Temporal (TD) global robusta. El algoritmo minimiza una versión suavizada de esta brecha (usando un envolvente de Moreau) para manejar la falta de suavidad.
- Convergencia: Se demuestra que el algoritmo converge débilmente a un punto estacionario del objetivo suavizado. Aunque no garantiza la convergencia al NE exacto sin supuestos adicionales (como la dominación de gradiente local), proporciona el primer método con convergencia demostrable para DR-MGs de recompensa promedio que no depende de un oráculo de NE.

3. Conexión con Equilibrios Descontados

Los autores establecen un puente teórico entre los DR-MGs de recompensa promedio y los de recompensa descontada. Demuestran que, a medida que el factor de descuento $\gamma \to 1$ , el NE robusto del juego descontado converge al NE robusto del juego de recompensa promedio. Esto permite la aproximación del desafiante problema de recompensa promedio utilizando las formulaciones de recompensa descontada, que son más tratables.

Resultados Clave

Existencia de NE: El artículo demuestra la existencia de un Equilibrio de Nash robusto estacionario para DR-MGs de recompensa promedio bajo supuestos de irreducibilidad y comunicación débil, abordando una cuestión fundamental de solvencia dejada abierta por la literatura previa.
Solvabilidad de las Ecuaciones de Bellman Robustas: Los autores proporcionan resultados fundacionales sobre la solvabilidad y unicidad (salvo constantes) de la ecuación de Bellman robusta para MDPs de recompensa promedio, corrigiendo vacíos previos en la literatura.
Algoritmos Convergentes: Se introducen dos algoritmos. La Iteración de Nash Robusta ofrece convergencia bajo supuestos estructurales específicos, mientras que el Descenso de TD Robusto ofrece un enfoque práctico, libre de oráculo, con convergencia demostrable hacia puntos estacionarios.
Aproximación mediante Descuento: El artículo valida que los equilibrios de recompensa promedio pueden ser efectivamente aproximados por equilibrios descontados con factores de descuento suficientemente grandes, ofreciendo una vía computacional práctica.

Significado y Reivindicaciones

El artículo afirma proporcionar una base teórica y algorítmica integral para la toma de decisiones en entornos multiagente complejos, inciertos y de larga duración. Específicamente:

Resuelve la cuestión fundamental de si existen equilibrios robustos en entornos multiagentes de recompensa promedio, un problema donde las técnicas estándar fallan.
Introduce los primeros algoritmos con garantías de convergencia demostrables para resolver DR-MGs de recompensa promedio, yendo más allá de las limitaciones de las aproximaciones de horizonte finito o de recompensa descontada.
Destaca la necesidad de supuestos estructurales (irreducibilidad o comunicación débil) para la existencia de equilibrios estacionarios, demostrando mediante contraejemplos que tales supuestos no son meramente técnicos, sino esenciales.

Los autores señalan que, si bien su marco proporciona una base sólida, encontrar equilibrios exactos en juegos de suma general sigue siendo un desafío, y su algoritmo basado en TD converge a puntos estacionarios que sirven como un primer paso necesario hacia el hallazgo de NE robustos exactos. Se sugiere como trabajo futuro explorar la dominación de gradiente local para obtener garantías de convergencia más fuertes y extender el marco más allá de los conjuntos de incertidumbre $(s, a)$ -rectangulares.