Resumen Técnico: Bandidos Duelistas Multi-Usuario: Un Enfoque Justo utilizando el Bienestar Social de Nash

Definición del Problema

El artículo aborda el problema del Bandido Duelista Multi-Usuario Justo, un escenario donde un agente aprende de datos de preferencias pareadas proporcionados por $D$ usuarios distintos durante un horizonte de tiempo $T$ con $K$ brazos. A diferencia de los bandidos duelistas estándar que asumen un único modelo de preferencia o agregan las preferencias en una única matriz, este trabajo considera un escenario en el que cada usuario $d$ posee una matriz de preferencia $P_d$ potencialmente distinta.

El desafío central es aprender una política que equilibre los intereses de estos usuarios heterogéneos sin marginar a los grupos minoritarios. Los enfoques estándar que optimizan para el bienestar promedio (utilitario) suelen favorecer a la mayoría estadística, lo que conduce a resultados injustos para los usuarios con preferencias divergentes. Para abordar esto, los autores definen el objetivo utilizando el Bienestar Social de Nash (NSW), que maximiza el producto de las utilidades de los usuarios. Este objetivo penaliza inherentemente la desigualdad, asegurando que la utilidad de ningún usuario sea llevada a cero.

Un obstáculo técnico crítico en este entorno es la falta de recompensas absolutas; la retroalimentación es puramente relativa (resultados binarios que indican qué brazo es preferido entre dos). Para definir la utilidad en este entorno relativo, los autores asumen la existencia de un ganador de Condorcet para cada usuario (un brazo que vence a todos los demás brazos con una probabilidad $>0.5$). La utilidad del usuario se define entonces como una puntuación derivada de la probabilidad de que un brazo venza al ganador de Condorcet específico de ese usuario.

Metodología

Marco Teórico

Los autores formalizan el problema definiendo una función de puntuación $s_d(i) = 2P_{d, i, a^*_d}$, donde $a^*_d$ es el ganador de Condorcet para el usuario $d$. La utilidad de una política $\pi$ para el usuario $d$ es la esperanza de la puntuación $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$. El objetivo global es el Bienestar Social de Nash:
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
El objetivo es minimizar el arrepentimiento (regret) esperado respecto a la política óptima $\pi^*$ que maximiza este producto.

Análisis de Dificultad (Hardness)

El artículo establece un límite inferior de arrepentimiento fundamental de $\Omega(T^{2/3} \min(K, D)^{1/3})$. Este resultado demuestra que el requisito de maximizar el NSW entre usuarios con ganadores de Condorcet en conflicto introduce una dificultad significativa en comparación con los bandidos duelistas estándar (que típicamente logran un arrepentimiento de $O(\log T)$). La dificultad surge porque el algoritmo debe jugar "malos" ganadores de Condorcet (óptimos para un usuario pero que producen una utilidad cercana a cero para otros) para distinguirlos de los ganadores "buenos", creando un compromiso entre los costos de exploración y el arrepentimiento instantáneo.

Algoritmos

Se proponen dos algoritmos para lograr este objetivo, ambos incorporando una fase de identificación del ganador de Condorcet:

1. Fair-Explore-Then-Commit (Fair-ETC):

   • Fase 1 (Identificación): Utiliza un algoritmo de torneo Dvoretzky-Kiefer-Wolfowitz (DKWT) modificado para identificar el conjunto de ganadores de Condorcet $\hat{A}^*$ para todos los $D$ usuarios. Esta fase aprovecha las interacciones compartidas para actualizar simultáneamente los márgenes empíricos para todos los usuarios.
   • Fase 2 (Exploración): Estima las puntuaciones de todos los brazos en relación con los ganadores de Condorcet identificados.
   • Fase 3 (Compromiso): Calcula la política $\hat{\pi}$ que maximiza el NSW empírico y se compromete con ella durante el resto del horizonte.

2. Fair-$\epsilon$-Greedy:

   • Este algoritmo intercala exploración y explotación a lo largo del horizonte.
   • Comienza con la misma fase de identificación del ganador de Condorcet.
   • En cada paso $t$, con una probabilidad $\epsilon_t$, explora jugando pares que involucran a los ganadores de Condorcet estimados (usando un esquema de round-robin) para refinar las estimaciones de las puntuaciones.
   • Con una probabilidad $1-\epsilon_t$, explota jugando la política que maximiza el NSW empírico actual.
   • La tasa de exploración $\epsilon_t$ decae con el tiempo para asegurar la convergencia.

Se demuestra que ambos algoritmos logran un límite superior de arrepentimiento de $\tilde{O}(T^{2/3})$, igualando la dependencia del límite inferior respecto al horizonte de tiempo $T$ salvo por factores logarítmicos.

Contribuciones Clave

1. Formulación del Problema: La primera formalización del problema del Bandido Duelista Multi-Usuario Justo, modelando utilidades de usuario distintas basadas en sus ganadores de Condorcet individuales y adoptando el NSW como el objetivo de justicia.
2. Límite Inferior de Arrepentimiento: La derivación de un límite inferior de arrepentimiento de $\Omega(T^{2/3} \min(K, D)^{1/3})$, que los autores afirman es el primer resultado que cuantifica el costo de la justicia en los bandidos duelistas con preferencias heterogéneas.
3. Soluciones Algorítmicas: La propuesta de los algoritmos Fair-ETC y Fair-$\epsilon$-Greedy, acompañados de límites superiores de arrepentimiento teóricos que coinciden con la dependencia del límite inferior respecto a $T$.
4. Validación Empírica: Simulaciones extensas que demuestran que los algoritmos propuestos superan a las bases utilitarias en métricas de justicia (coeficiente de Gini, bienestar mínimo del usuario) mientras mantienen un arrepentimiento acumulado competitivo.

Resultados Experimentales

Los autores evaluaron sus algoritmos tanto en preferencias generadas aleatoriamente como en datos del mundo real (el conjunto de datos Sushi, agrupado en usuarios macroscópicos).

• Preferencias Aleatorias: En varias configuraciones de usuarios ($D$) y brazos ($K$), tanto Fair-ETC como Fair-$\epsilon$-Greedy demostraron un arrepentimiento sublineal, superando consistentemente a las bases utilitarias y a la base de uniforme sobre usuarios.
• Métricas de Justicia: Los algoritmos propuestos lograron el mayor Bienestar Social de Nash y coeficientes de Gini significativamente más bajos en comparación con los enfoques utilitarios. También mantuvieron un bienestar mínimo de usuario más alto, lo que indica una mejor protección de las preferencias minoritarias.
• Preferencias Agrupadas (Clustered): En escenarios con distintos grupos de mayoría y minoría (simulando preferencias polarizadas), los algoritmos utilitarios favorecieron a la mayoría, provocando una alta desigualdad. Los algoritmos justos propuestos equilibraron con éxito los intereses, manteniendo bajos los coeficientes de Gini y un alto bienestar mínimo.
• Conjunto de Datos Sushi: En datos del mundo real, los métodos propuestos lograron el menor arrepentimiento acumulado tanto en la configuración de $D=5$ como en la de $D=10$ agrupaciones. Si bien una base uniforme mostró una justicia ligeramente mejor en el caso altamente fragmentado de $D=10$, sufrió un arrepentimiento notablemente inferior.

Significado y Reivindicaciones

El artículo afirma ser el primero en cuantificar el costo de la justicia en los bandidos duelistas con preferencias heterogéneas, estableciendo un límite inferior de arrepentimiento fundamental de $\Omega(T^{2/3})$. Los autores posicionan su trabajo como un paso necesario hacia el aprendizaje automático centrado en el ser humano, donde optimizar la preferencia promedio es insuficiente y potencialmente perjudicial para los grupos minoritarios.

Al integrar el objetivo del Bienestar Social de Nash en el marco de los bandidos duelistas, el trabajo proporciona una base teórica y algorítmica para aprender políticas que equilibren la eficiencia con la justicia. Los autores señalan que su enfoque es distinto del trabajo previo sobre bandidos multi-agente (por ejemplo, Hossain et al., 2021; Jones et al., 2023) porque opera en un entorno de preferencia relativa en lugar de uno con recompensas absolutas, lo que requiere técnicas de estimación de utilidad fundamentalmente diferentes.

El artículo concluye de manera modesta, reconociendo que trabajos futuros podrían extender este marco a bandidos duelistas contextuales, espacios de acción continuos y escenarios donde la suposición del ganador de Condorcet no se cumple (posiblemente utilizando puntuaciones de Copeland o Borda).