Learning in Matching Games with Bandit Feedback

Resumen Técnico: Aprendizaje en Juegos de Emparejamiento con Retroalimentación de Bandidos

Formulación del Problema
Este artículo introduce un nuevo problema de aprendizaje situado en la intersección de los mercados de emparejamiento de dos lados y la teoría de juegos. El entorno involucra un mercado generalizado con dos conjuntos distintos de agentes, $P$ y $A$, que son emparejados por una plataforma central a lo largo de un horizonte temporal $T$. A diferencia de los problemas de emparejamiento tradicionales donde los agentes poseen preferencias estáticas y conocidas, o de los entornos estándar de Bandidos Multibrazo (MAB) donde los agentes reciben pagos estocásticos directos, este marco postula que, una vez emparejados, los agentes participan en un juego de suma cero de dos jugadores (ZSG) con una matriz de pagos inicialmente desconocida.

En este escenario, los agentes deben aprender simultáneamente la dinámica subyacente del juego y derivar sus preferencias a partir de los resultados de estas interacciones. En cada paso de tiempo $t$:

1. Una plataforma central genera un emparejamiento $m_t$ basado en las preferencias estimadas de los agentes.
2. Los agentes emparejados seleccionan estrategias (acciones mixtas) y muestrean acciones específicas.
3. Los agentes reciben retroalimentación de bandidos estocástica (recompensas) y observan las acciones de su compañero emparejado.
4. Los agentes actualizan sus estimaciones de las matrices de pagos y sus preferencias para la siguiente ronda.

El desafío central es aprender un Equilibrio de Emparejamiento, un concepto de solución definido por [10] donde el emparejamiento es estable (sin pares bloqueantes) y los agentes juegan un Equilibrio de Nash (NE) con sus parejas asignadas. La dificultad surge porque los agentes no conocen las matrices de juego a priori y deben explorar para formar preferencias, mientras que el mecanismo de emparejamiento (típicamente Gale-Shapley) depende de esas preferencias para asegurar la estabilidad.

Metodología y Algoritmo
Para abordar esto, los autores proponen UCB-MG, un algoritmo basado en el principio de "optimismo ante la incertidumbre". La metodología opera de la siguiente manera:

• Estimaciones Optimistas: Los agentes mantienen límites superiores de confianza (UCB) para las matrices de pagos de posibles emparejamientos. Específicamente, para un par $(p, a)$, la matriz de pagos estimada $\bar{A}_{p,a}$ se construye añadiendo un bono de confianza a la media empírica de las recompensas observadas.
• Formación de Preferencias: Basándose en estas matrices de pagos optimistas, los agentes computan el valor optimista del juego ($\bar{V}^*$) asumiendo un juego óptimo (estrategias minimax) contra cada posible compañero. Los agentes entonces clasifican sus preferencias de acuerdo con estos valores de juego optimistas.
• Emparejamiento: La plataforma central recolecta estas preferencias reportadas y ejecuta el algoritmo de Gale-Shapley (GS) para generar un emparejamiento estable para la ronda actual.
• Ejecución de Estrategia: Una vez emparejados, los agentes seleccionan acciones basadas en las estrategias minimax derivadas de sus matrices de pagos optimistas, muestrean acciones y reciben retroalimentación para actualizar sus estimaciones.

Formulación del Regret: Inestabilidad de Emparejamiento
Una contribución crítica del artículo es la definición de una métrica de regret apropiada, denominada Inestabilidad de Emparejamiento (MI). Las definiciones de regret estándar de MAB o teoría de juegos son insuficientes porque el objetivo es converger a un equilibrio conjunto de emparejamiento y estrategia.

Los autores definen la MI como el subsidio total mínimo requerido para estabilizar el mercado dado un emparejamiento actual $m$ y un perfil de estrategia $X$. Matemáticamente, es la solución a un programa lineal que minimiza los subsidios $s_a$ sujeto a:

1. Sin Pares Bloqueantes: Asegurar que ningún par $(p, a)$ pueda mejorar su utilidad mediante la desviación, dada la estrategia actual.
2. Racionalidad Individual: Asegurar que los agentes prefieran su emparejamiento sobre no estar emparejados.
3. Garantía de Valor: Asegurar que los agentes reciban una utilidad al menos igual al valor minimax de su juego (una relajación de la condición estricta de Nash para facilitar un análisis tratable).

El regret acumulado $R_T$ se define como la suma de la Inestabilidad de Emparejamiento a lo largo del horizonte $T$.

Contribuciones Clave

1. Definición del Problema de Aprendizaje: El artículo formaliza el primer entorno de aprendizaje donde los agentes en un mercado de dos lados deben aprender juegos de suma cero desconocidos para formar preferencias para el emparejamiento.
2. Métrica de Regret: Introduce la Inestabilidad de Emparejamiento, extendiendo el concepto de Inestabilidad de Subconjuntos [8, 17] a entornos donde los agentes emparejados juegan juegos. Esta métrica cuantifica la distancia hacia un Equilibrio de Emparejamiento.
3. Diseño de Algoritmo: Los autores proponen un algoritmo basado en UCB (UCB-MG) que integra la estimación optimista del valor del juego con el mecanismo de Gale-Shapley.
4. Garantías Teóricas: El artículo demuestra que el algoritmo propuesto logra un límite de regret sublineal e independiente de la instancia de $\tilde{O}(\sqrt{Tmkpa})$, donde $T$ es el horizonte, $m$ y $k$ son el número de acciones por agente, y $p$ y $a$ son el número de agentes en cada lado.
5. Generalización: El límite teórico unifica resultados existentes. Cuando $m=k=1$, recupera el límite para el emparejamiento clásico de dos lados ($\tilde{O}(\sqrt{Tpa})$). Cuando $p=a=1$, recupera el límite para el auto-juego en juegos de suma cero ($\tilde{O}(\sqrt{Tmk})$).

Resultos y Evidencia Empírica
Los autores proporcionan validación empírica utilizando instancias sintéticas donde las matrices de pago se muestrean de una distribución normal. Comparan tres escenarios:

• Auto-Juego (Self-Play): Ambos lados siguen el algoritmo UCB-MG.
• Respuesta-Nash (Nash-Response): Un lado conoce las matrices de juego reales y juega la estrategia de Equilibrio de Nash, mientras que el otro aprende.
• Mejor-Respuesta (Best-Response): Un lado conoce las matrices reales y las estrategias del oponente, jugando la mejor respuesta.

Los resultados indican que el sistema aprende un resultado estable en todos los escenarios, exhibiendo un crecimiento de regret sublineal. Como era de esperar, el escenario de Respuesta-Nash produce el regret más bajo. Curiosamente, aunque el escenario de Mejor-Respuesta supera inicialmente al Auto-Juego, su rendimiento se degrada a medida que el tamaño del mercado (número de agentes y acciones) aumenta, probablemente debido a la complejidad introducida por un lado que explota al otro.

Significancia y Direcciones Futuras
El artículo afirma su importancia como un paso inicial hacia la comprensión del aprendizaje en entornos donde los agentes reciben pagos solo después de interactuar mediante acciones en un juego, en lugar de recibir señales de preferencia directas. Demuestra que los resultados estables pueden aprenderse eficientemente en tales entornos complejos y acoplados.

Los autores plantean este trabajo modestamente como una base para investigaciones futuras. Identifican varias direcciones abiertas:

• Extender el modelo de juegos de suma cero a juegos de suma general.
• Integrar algoritmos de aprendizaje sin regret (como Exp3) en el marco de emparejamiento para manejar la dinámica de suma no cero.
• Relajar la suposición de que los agentes observan las acciones de su compañero.
• Explorar modelos de juego alternativos (juegos de Markov, juegos de Stackelberg) y estructuras de emparejamiento (mercados de muchos a uno).
• Investigar entornos descentralizados donde los agentes seleccionan tanto los emparejamientos como las estrategias sin un coordinador central.