Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

Resumen Técnico: Aprendizaje de Políticas de Respuesta Ordinal en Juegos de Recolección de Premios Estocásticos Basados en Rango

1. Definición del Problema

El artículo aborda las limitaciones del Problema de Orientación de Equipos (TOP, por sus siglas en inglés) en sistemas multiagente. Aunque el TOP proporciona un marco unificado para la navegación cooperativa (por ejemplo, entrega de última milla, vigilancia) donde los agentes maximizan una utilidad colectiva bajo presupuestos de viaje, no logra modelar escenarios que involucran agentes con intereses propios compitiendo en entornos de recursos escasos. En tales entornos, los agentes (por ejemplo, flotas de entrega competidoras o conductores de economía colaborativa) priorizan las recompensas individuales sobre la ganancia colectiva, y sus interacciones están gobernadas por transiciones estocásticas y restricciones de energía.

Para cerrar esta brecha, los autores proponen el Juego de Orientación de Recolección de Premios Estocásticos (SPCOG, por sus siglas en inglés). En un SPCOG:

• Los agentes operan en un grafo ponderado con distribuciones de premios estocásticas en los nodos.
• Los agentes tienen presupuestos de viaje individuales y buscan maximizar sus propias recompensas acumuladas.
• Resolución de Conflictos: Cuando múltiples agentes visitan el mismo nodo simultáneamente, se aplica una regla basada en el rango: el agente con el rango global más alto (índice más bajo) reclama el premio por completo; los demás reciben cero.
• Objetivo: Encontrar políticas convergentes para agentes independientes que maximicen las recompensas individuales, reconociendo que la recompina total del equipo puede ser menor que el óptimo del TOP cooperativo debido a la competencia.

2. Metodología

Análisis Teórico de Equilibrios
Los autores analizan primero la existencia de un Equilibrio de Nash Puro (PNE) en los SPCOGs:

• Grafos Completos: Demuestran que para grafos completos, existe un PNE único bajo la resolución de conflictos basada en el rango. En este equilibrio, el $i$-ésimo agente clasificado selecciona el $i$-ésimo premio más grande disponible. La recompensa total en este PNE coincide con la solución óptima de un TOP cooperativo equivalente.
• Grafos en Estrella: Existe un PNE único similar donde los agentes se mueven hacia el $i$-ésimo premio más grande en etapas alternas.
• Grafos Arbitrarios: El artículo demuestra mediante un contraejemplo (un escenario específico de dos agentes) que un PNE no necesariamente existe para estructuras de grafos arbitrarias cuando los agentes se mueven simultáneamente, resaltando la complejidad de resolver estos juegos en comparación con las formulaciones de Stackelberg (líder-seguidor).

Concepto de Rango Ordinal (OR)
Para abordar el desafío de la observabilidad parcial y el espacio de estados exponencial en grafos generales, los autores introducen el Rango Ordinal (OR):

• Oponentes Inmediatos: Los agentes se agrupan en "juegos de etapa localizados" basados en un "grafo separador" donde las aristas conectan a agentes con conjuntos alcanzables superpuestos.
• Definición: El OR de un agente se define como $1 +$ el número de agentes con un rango global superior (índice más bajo) dentro de su vecindad inmediata (componente conectada).
• Significado: El OR resume la competencia local más influyente. Los autores hipotetizan que condicionar las políticas al OR, en lugar del estado global o el rango global, actúa como un fuerte sesgo inductivo, permitiendo a los agentes aprender respuestas ópticas a sus oponentes inmediatos sin requerir información global.

Aprendizaje de Respuesta Ordinal Ficticia (FORL)
Los autores proponen FORL, un algoritmo de aprendizaje regulado por entropía diseñado para el aprendizaje por refuerzo multiagente independiente (MARL):

• Actualizaciones Secuenciales: Los agentes actualizan sus políticas secuencialmente según su rango. Los agentes de mayor rango se actualizan primero, asumiendo que los agentes de menor rango siguen políticas aleatorias o estacionarias.
• Bootstrapping: El agente de mayor rango aprende primero para resolver el problema estocástico de un solo agente subyacente. Una vez que su política alcanza un umbral de confianza (medido por la entropía), sus parámetros se comparten con los demás.
• Juego Ficticio: Los agentes subsiguientes actualizan sus políticas jugando contra las políticas "estacionarias" de los agentes de mayor rango.
• Regulación de la Entropía: El algoritmo utiliza un umbral de entropía decreciente ($H_{stop}$) para asegurar la convergencia. Si existe un PNE, el algoritmo converge a una estrategia pura (entropía $\to$ 0); de lo contrario, proporciona límites de confianza sobre la calidad de la política de estrategia mixta.
• Arquitectura de la Política: Las políticas se modelan utilizando una arquitectura basada en Transformers (TRXL-I) y están condicionadas por observaciones locales aumentadas con el OR. Se utiliza el enmascaramiento de acciones para imponer las restricciones del grafo.

3. Contribuciones Clave

1. Formulación SPCOG: Introducción de una variante de teoría de juegos del TOP para agentes con intereses propios en entornos estocásticos y con restricciones de energía.
2. Garantías Teóricas: Prueba de un PNE único en grafos completos y en estrella que se alinea con la solución óptima del TOP, y un contraejemplo que muestra la no existencia de PNEs en grafos arbitrarios.
3. Rango Ordinal (OR): Propuesta del OR como una representación local concisa de la posición competitiva de un agente, que sirve como un fuerte sesgo inductivo para el aprendizaje.
4. Algoritmo FORL: Desarrollo de un algoritmo inspirado en el juego ficticio y regulado por la entropía que produce políticas convergentes en entornos de aprendizaje independiente.
5. Validación Empírica: Demostración de que las políticas condicionadas por OR superan a las políticas condicionadas por el rango global en términos de generalización, escalabilidad y eficiencia de entrenamiento.

4. Resultados Experimentales

Los experimentos se realizaron en redes de carreteras del mundo real (Estocolmo y Manhattan) con distribuciones de premios estáticas y dinámicas.

• Desempeño vs. TOP: En grafos completos, las políticas condicionadas por OR alcanzaron el 95% de la recompensa óptima del TOP. En grafos incompletos, el peor caso del equilibrio alcanzó el 87% de la solución óptima.
• Generalización: Las políticas entrenadas con FORL y el condicionamiento por OR demostraron capacidades superiores de transferencia "zero-shot" a distribuciones de premios desequilibradas y basadas en la demanda, en comparación con el Aprendizaje de Política Independiente (IPL) y los métodos de uso compartido de parámetros condicionados al estado global.
• Escalabilidad: Al escalar a equipos de hasta 25 agentes, las políticas condicionadas por OR (PS-OR) mostraron un escalamiento lineal en la recompensa total con baja varianza. En contraste, las políticas condicionadas por el rango global (PS-GR) exhibieron ganancias sublineales y una varianza significativamente mayor.
• Eficiencia: El método FORL requirió entre 1.56x y 2.2x menos tiempo de entrenamiento para alcanzar perfiles de recompensa comparables en comparación con los modelos base de uso compartido de parámetros e aprendizaje independiente.

5. Significado y Reivindicaciones

El artículo sostiene que el concepto de Rango Ordinal desacopla efectivamente la necesidad de información del estado global en juegos de navegación multiagente. Al centrarse en los "oponentes inmediatos" locales y sus rangos relativos, los agentes pueden aprender estrategias robustas que se generalizan bien a tamaños de equipo más grandes y entornos no vistos.

Los autores afirman que FORL proporciona un mecanismo práctico para obtener políticas convergentes en juegos de navegación competitivos y estocásticos donde las suposiciones cooperativas tradicionales fallan. El trabajo sugiere que, en escenarios de conflicto basados en el rango, la información local condicionada por la posición ordinal es una señal de aprendizaje más efectiva que el estado global o el rango global, ofreciendo una solución escalable para flotas robóticas heterogéneas y con intereses propios.