Algoritmos Justos con Sondeo para Bandidos Multi-Agente Multi-Brazo

Información Básica

• ID del Artículo: 2506.14988
• Título: Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits
• Autores: Tianyi Xu, Jiaxin Liu, Nicholas Mattei, Zizhan Zheng
• Instituciones: Tulane University, University of Illinois Urbana-Champaign
• Clasificación: cs.LG, cs.AI
• Fecha de Publicación: preprint arXiv, versión del 26 de noviembre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2506.14988v4

Resumen

Este artículo propone un marco de bandidos multi-brazo multi-agente (MA-MAB) diseñado para garantizar equidad entre agentes mientras se maximiza el desempeño general del sistema. Ante el desafío de decisiones con información limitada sobre recompensas de brazos, se introduce un mecanismo novedoso de sondeo que recopila estratégicamente información de brazos seleccionados antes de la asignación. En la configuración sin conexión (con distribuciones de recompensas conocidas), se diseña un algoritmo de sondeo codicioso con garantías de aproximación de factor constante utilizando propiedades submodulares. En la configuración en línea, se desarrolla un algoritmo que logra arrepentimiento sublineal mientras mantiene equidad. Experimentos extensos en conjuntos de datos sintéticos y del mundo real demuestran que el método supera a los métodos de referencia tanto en equidad como en eficiencia.

Antecedentes y Motivación de la Investigación

Problema Central

Los problemas tradicionales de bandidos multi-brazo típicamente optimizan el bienestar utilitarista (es decir, la suma total de recompensas), pero esto conduce a fenómenos graves de inequidad. Por ejemplo, en escenarios de transporte compartido, cuando un sistema central de despacho asigna conductores a diferentes regiones geográficas, optimizar el ingreso total puede resultar en que algunos conductores no reciban ningún pedido, causando un fenómeno de "inanición" (starvation).

Importancia del Problema

La asignación justa de recursos es crucial en muchas aplicaciones prácticas:

1. Plataformas de Transporte Compartido: Los conductores necesitan acceso justo a zonas rentables
2. Sistemas de Recomendación de Contenido: La exposición de creadores no debe ser monopolizada
3. Programación de Redes Inalámbricas: Los dispositivos cliente necesitan asignación justa de ancho de banda

Limitaciones de Métodos Existentes

1. Falta de Equidad: Los métodos MA-MAB existentes se enfocaban principalmente en maximizar recompensas totales, ignorando la equidad individual
2. Dependencia de Información: Dependen de retroalimentación inmediata para actualizar estimaciones, con mal desempeño en entornos con información incompleta o ruidosa
3. Exploración Insuficiente: Carecen de mecanismos de recopilación de información activa, causando que errores de estimación en brazos inciertos se propaguen a decisiones de asignación

Motivación de la Investigación

Este artículo cierra la brecha entre métodos multi-agente justos y estrategias de exploración activa introduciendo mecanismos de sondeo y objetivos de Bienestar Social de Nash (NSW), permitiendo que la información obtenida a través de exploración activa se traduzca directamente en resultados justos para todos los agentes.

Contribuciones Principales

1. Nuevo Marco: Extiende el marco MA-MAB introduciendo mecanismos de sondeo para probar brazos seleccionados antes de la asignación, asegurando equidad a través de optimización NSW
2. Algoritmo Sin Conexión: Desarrolla una estrategia de sondeo codicioso simple pero efectiva con garantías de desempeño comprobables para patrones de recompensas conocidos
3. Algoritmo En Línea: Propone un algoritmo que equilibra exploración con equidad, demostrando que el sondeo y la asignación justa no comprometen el desempeño asintótico (arrepentimiento sublineal)
4. Verificación Experimental: Demuestra en datos sintéticos y reales que el método supera a los métodos de referencia en equidad y eficiencia

Explicación Detallada del Método

Definición de la Tarea

Configuración Básica:

• Agentes: M agentes, denotados como j ∈ M
• Brazos: A brazos, denotados como a ∈ A
• Distribuciones de Recompensas: Cada par agente-brazo (j,a) tiene una distribución desconocida D_{j,a} con media μ_{j,a} ∈ 0,1

Proceso de Decisión (cada ronda t):

1. Fase de Sondeo: Selecciona conjunto de sondeo S_t ⊆ A, obteniendo nuevas muestras de recompensa R_{j,a,t} para cada a ∈ S_t
2. Fase de Asignación: Basada en recompensas observadas y estimaciones actuales, asigna brazos a agentes mediante política π_t

Objetivo de Equidad: Maximizar Bienestar Social de Nash (NSW) $\text{NSW}(S_t, R_t, \mu, \pi_t) = \prod_{j \in [M]} \left( \sum_{a \in S_t} \pi_{j,a,t} R_{j,a,t} + \sum_{a \notin S_t} \pi_{j,a,t} \mu_{j,a} \right)$

Costo de Sondeo: La recompensa efectiva es $R^{\text{total}}_t = (1 - \alpha(|S_t|)) \mathbb{E}_{R_t}[\text{NSW}(S_t, R_t, \mu, \pi_t)]$ donde α(·) es una función de costo no decreciente, con α(0)=0, α(I)=1

Definición de Arrepentimiento: $R_{\text{regret}}(T) = \sum_{t=1}^T \left[ (1-\alpha(|S^*_t|)) \mathbb{E}[\text{NSW}(S^*_t, R_t, \mu, \pi^*_t)] - R^{\text{total}}_t \right]$

Configuración Sin Conexión: Algoritmo de Sondeo Codicioso

Descomposición del Objetivo de Optimización

Se definen dos funciones de utilidad:

1. Utilidad de Sondeo g(S): NSW óptima esperada usando solo brazos sondeados $g(S) = \max_{\pi \in \Delta^A_S} \mathbb{E}\left[ \prod_{j \in [M]} \left( \sum_{a \in S} \pi_{j,a} R_{j,a} \right) \right]$
2. Utilidad de No-Sondeo h(S): NSW óptima usando solo brazos no sondeados $h(S) = \max_{\pi \in \Delta^A_{[A]\backslash S}} \prod_{j \in [M]} \left( \sum_{a \notin S} \pi_{j,a} \mu_{j,a} \right)$

Construcción de Cota Superior Lineal por Segmentos

Dado que log(g(S)) no es submodular, la optimización directa es difícil. Se adopta una aproximación de envolvente lineal por segmentos:

• Se divide el intervalo 0, x_max en segmentos finos con puntos de quiebre τ_0, τ_1, ..., τ_L
• En cada punto de quiebre se construye una línea tangente T_{τ_i}(z) = log(τ_i) + (z - τ_i)/τ_i
• Se define φ(z) = max_{0≤i<L} T_{τ_i}(z), satisfaciendo φ(z) ≥ log(z)
• Se establece f_upper(S) = φ(g(S))

Propiedades Submodulares

Los Lemas 1-5 establecen propiedades clave:

• Lema 1: g(S) es monótonamente creciente
• Lema 2: f_upper(S) es monótonamente creciente
• Lema 3: f_upper(S) es submodular (propiedad central)
• Lema 4: h(S) es monótonamente decreciente
• Lema 5: R(S) ≤ (1-α(|S|))(g(S) + h(S))

Algoritmo 1: Sondeo Codicioso Sin Conexión

Entrada: Distribuciones {F_{m,a}}, función de costo α(·), presupuesto I, parámetro ζ≥1
Salida: Conjunto de sondeo S_pr

1. Inicializar S_0 = ∅
2. Para i = 1 hasta I:
   - Seleccionar brazo con máxima ganancia marginal:
     a = argmax_{a∉S_{i-1}} [f_upper(S_{i-1}∪{a}) - f_upper(S_{i-1})]
   - S_i = S_{i-1} ∪ {a}
3. Ordenar conjunto candidato por (1-α(|S_j|))f_upper(S_j) en orden descendente
4. Iterar sobre conjunto ordenado:
   - Si (1-α(|S_j|))f_upper(S_j) < h(∅), retornar ∅
   - Si (1-α(|S_j|))f_upper(S_j) > ζR(S_j), continuar
   - En caso contrario, retornar S_j

Teorema 1 (Garantía de Aproximación): Para cualquier ζ≥1, el conjunto S_pr retornado por el algoritmo satisface $R(S_{pr}) \geq \frac{e-1}{2e-1} \cdot \frac{1}{\zeta} \cdot R(S^*)$ Esta garantía se deriva del factor de aproximación (1-1/e) para maximización submodular.

Configuración En Línea: Algoritmo OFMUP

Algoritmo 2: UCB Multi-Agente Justo En Línea con Sondeo (OFMUP)

Fase de Inicialización (t = 1 hasta MA):

• Cada par agente-brazo se explora al menos una vez
• Se construyen CDF empíricas F̂_{j,a,t} y estimaciones de media μ̂_{j,a,t}

Fase de Bucle Principal (t > MA):

1. Selección de Conjunto de Sondeo: Se invoca el Algoritmo 1 basado en estimaciones actuales F̂_{j,a,t} para seleccionar S_t
2. Actualización de Sondeo: Se muestrean brazos en S_t, actualizando estadísticas y cotas de confianza superiores $U_{j,a,t} = \min(\hat{\mu}_{j,a,t} + w_{j,a,t}, 1)$ donde w_{j,a,t} es el ancho de confianza basado en la desigualdad de Freedman
3. Optimización de Política: $\pi_t = \arg\max_{\pi_t \in \Delta^A} (1-\alpha(|S_t|)) \mathbb{E}_{R_t}[\text{NSW}(S_t, R_t, U_t, \pi_t)]$
4. Extracción de Brazos: Cada agente j extrae brazos según π_t, observa recompensas y actualiza

Construcción de Cotas de Confianza

Lema 7 (Cota de Concentración): Con probabilidad al menos 1-δ/2, para todo t>A, a∈A, j∈M: $|\mu_{j,a} - \hat{\mu}_{j,a,t}| \leq \sqrt{\frac{2(\hat{\mu}_{j,a,t} - \hat{\mu}^2_{j,a,t}) \ln(\frac{2MAT}{\delta})}{N_{j,a,t}}} + \frac{\ln(\frac{2MAT}{\delta})}{3N_{j,a,t}} = w_{j,a,t}$

Puntos de Innovación Técnica

1. Combinación de Sondeo y Equidad: Primera combinación de mecanismos de sondeo activo con objetivos de equidad NSW, diferente de trabajos previos que solo optimizan recompensas totales
2. Técnica de Aproximación Submodular: Transforma problemas no submodulares en optimización submodular mediante cotas superiores lineales por segmentos, manteniendo tratabilidad
3. Fusión UCB-NSW: El algoritmo en línea combina ingeniosamente cotas de confianza UCB con optimización NSW, equilibrando exploración-explotación con equidad
4. Análisis de Arrepentimiento Estratificado: Divide rondas en categorías de "γ grande" y "γ pequeño", manejando separadamente casos de alta y baja incertidumbre

Configuración Experimental

Conjuntos de Datos

Datos Sintéticos:

• Pequeña Escala: M=12 agentes, A=8 brazos
• Escala Media: M=20 agentes, A=10 brazos
• Distribuciones de Recompensas:
  • Distribución Bernoulli (recompensas 0 o 1, medias en 0.3, 0.8)
  • Distribución Discreta (recompensas muestreadas de {0.3, 0.4, 0.5, 0.6, 0.7, 0.8})

Datos del Mundo Real: Conjunto de datos NYYellowTaxi 2016

• Agentes: Vehículos (ubicaciones pre-muestreadas aleatoriamente)
• Brazos: Ubicaciones de recogida discretizadas (cuadrícula 0.01°×0.01°)
• Recompensas: Basadas en distancia Manhattan normalizada del vehículo al punto de recogida (mayor proximidad = mayor recompensa)

Métricas de Evaluación

• Arrepentimiento Acumulado: Calculado según la fórmula (1), con recompensa óptima determinada mediante búsqueda exhaustiva
• Estabilidad Numérica: NSW acumulado agregado usando media geométrica de recompensas por agente
• Verificación de Aproximación: Verifica que la diferencia entre f_upper(S) y log(g(S)) sea ≤0.03

Métodos de Comparación

1. Non-Probing: Algoritmo de MAB justo de Jones et al. (2023), sin capacidad de sondeo, optimiza asignación solo basado en información actual
2. Random P+A: Selecciona aleatoriamente número fijo de brazos para sondeo, luego asignación aleatoria
3. Greedy P+A: Usa la misma estrategia de sondeo codicioso, pero asignación aleatoria después del sondeo

Detalles de Implementación

• Presupuesto de Sondeo: Establecido según tamaño del problema
• Función de Costo: α(|S|) es función creciente, con α(0)=0, α(I)=1
• Parámetro de Confianza: δ establecido para garantizar garantías de alta probabilidad
• Código Abierto: https://github.com/jiaxin26/Fair-MA-MAB-with-Probing

Resultados Experimentales

Resultados Principales

Hallazgos Centrales Mostrados en Figura 1:

1. Escenario Pequeño (M=12, A=8, Bernoulli):
   • OFMUP tiene arrepentimiento 85% menor que Random P+A en T=3000
   • 60% menor que Greedy P+A
   • Significativamente superior a Non-Probing
2. Escenario Escala Media (M=20, A=10, Bernoulli):
   • Ventaja de OFMUP más pronunciada
   • Arrepentimiento 88% menor que Random P+A en T=3000
   • 80% menor que Greedy P+A
   • Demuestra mejor escalabilidad
3. Escenario Distribución Discreta:
   • OFMUP consistentemente supera líneas base
   • La brecha con otros métodos aumenta conforme se aprenden patrones de recompensas
   • 85% menor que Random P+A en T=3000, 65% menor que Non-Probing
4. Fenómeno Anómalo en Random P+A:
   • Arrepentimiento ligeramente superior al esperado en pruebas pequeñas
   • Razón: Cálculo de equidad mediante media geométrica aumenta variabilidad en muestras pequeñas

Análisis de Escalabilidad

Escalabilidad Mostrada en Figura 2:

1. Número de Brazos Fijo (A=8), Variación de Agentes:
   • OFMUP funciona bien con todos los números de agentes
   • La ventaja relativa crece con complejidad del problema
2. Número de Agentes Fijo (M=20), Variación de Brazos:
   • Ventaja de OFMUP más pronunciada conforme aumentan brazos
   • Demuestra que el mecanismo de sondeo es más valioso en espacios de alta dimensión

Hallazgos Experimentales

1. Papel Crítico del Sondeo: El sondeo juega un papel decisivo en recopilación de información y guía de asignación
2. Importancia de Asignación Justa: Greedy P+A funciona mucho peor que OFMUP, demostrando que la asignación justa después del sondeo es crítica
3. Verificación Teórica: Los resultados experimentales validan el análisis teórico—OFMUP equilibra efectivamente exploración-explotación con equidad
4. Aplicabilidad a Datos Reales: El éxito en datos NYYellowTaxi demuestra potencial de aplicación práctica

Trabajo Relacionado

Fundamentos de Bandidos Multi-Brazo

• MAB Mono-Agente: Lai & Robbins (1985), Garivier & Cappé (2011)
• MAB Multi-Agente: Martínez-Rubio et al. (2019), Hossain et al. (2021)
• Investigación de Equidad: Joseph et al. (2016, 2018), Patil et al. (2021)

Bienestar Social de Nash

• Fundamentos Teóricos: Kaneko & Nakamura (1979)
• Métodos Computacionales: Cole & Gkatzelis (2015)
• Aplicación MA-MAB: Jones, Nguyen & Nguyen (2023)—trabajo directamente extendido por este artículo

Mecanismos de Sondeo

• Origen Económico: Weitzman (1979)
• Bandidos con Sondeo Mono-Agente:
  • Aaron D. Tucker et al. (2023): Observaciones de recompensas costosas, cota Θ(c^{1/3}T^{2/3})
  • Elumar et al. (2024): Sondeo de un brazo por ronda, arrepentimiento Õ(√KT)
  • Zuo et al. (2020): Marco Observe-Before-Play
• Sondeo Submodular: Bhaskara et al. (2020) en problemas de enrutamiento
• Contribución de Este Artículo: Primera combinación de sondeo con equidad multi-agente

Brecha de Investigación

Los trabajos existentes se enfocaban en MAB justo dependiendo de retroalimentación pasiva, o investigaban sondeo ignorando equidad. Este artículo cierra esta brecha.

Análisis Teórico

Garantía de Aproximación Sin Conexión (Teorema 1)

Resultado: R(S_pr) ≥ (e-1)/(2e-1) · 1/ζ · R(S*)

Pasos Clave de Prueba:

1. Utiliza Lema 5: R(S) ≤ (1-α(|S|))(g(S) + h(S))
2. Aplica aproximación (1-1/e) para maximización submodular
3. Relaciona f_upper con R mediante condiciones de selección del algoritmo
4. Obtiene garantía de aproximación de factor constante

Cota de Arrepentimiento En Línea (Teorema 2)

Resultado: Con probabilidad al menos 1-δ, $R_{\text{regret}}(T) = O\left(\zeta(\sqrt{MAT} + MA) \ln^c\left(\frac{MAT}{\delta}\right)\right)$

Marco de Prueba:

1. Suavidad NSW (Lema 6): Propiedad Lipschitz de NSW respecto a matriz de recompensas
2. Cota de Concentración (Lema 7): Cota de confianza basada en desigualdad de Freedman
3. Estratificación de Rondas (Lema 8):
   • Define γ_{j,t} = Σ_a π_{j,a,t}(1-U_{j,a,t})
   • Rondas de γ grande: |Q(t,p)| ≥ 2^p·3lnT, contribuye ≤1/T²
   • Rondas de γ pequeño: Aplica cota de concentración, descompone en término raíz y lineal
4. Cota de Término Raíz: Maneja mediante desigualdad de Young y Lema 8
5. Cota de Término Lineal: Utiliza Lema 4.4 de Jones et al. (2023)
6. Fusión Final: Obtiene término principal O(√MAT) más términos de orden inferior

Técnicas Clave:

• Convierte arrepentimiento de (S*,π*) a (S_t,π_t), utilizando factor del Teorema 1
• Optimismo UCB: U_{j,a,t}≥μ_{j,a} asegura exploración
• Análisis estratificado evita tratar directamente dependencias complejas de todas las rondas

Conclusiones y Discusión

Conclusiones Principales

1. Contribuciones Teóricas:
   • Sin Conexión: Algoritmo computable con garantía de aproximación de factor constante
   • En Línea: Arrepentimiento sublineal O(√MAT), comparable a algoritmos justos sin sondeo, pero con mejor desempeño práctico
2. Valor Práctico:
   • El mecanismo de sondeo mejora significativamente estimación de recompensas
   • Equilibra exploración-explotación con equidad
   • Validado en datos reales de transporte compartido
3. Innovación Metodológica:
   • Primera combinación de sondeo activo con equidad multi-agente
   • Técnica de aproximación submodular para optimización no convexa
   • Marco de aprendizaje en línea que fusiona UCB con NSW

Limitaciones

1. Complejidad Computacional:
   • Algoritmo sin conexión requiere resolver iterativamente optimización NSW (NP-hard)
   • Cada ronda en línea requiere calcular política óptima π_t
   • Escenarios grandes (M,A muy grandes) pueden enfrentar cuello de botella computacional
2. Supuestos Teóricos:
   • Aproximación lineal por segmentos requiere partición suficientemente fina (supuesto d/d'≥τ_i/τ_j)
   • Presupuesto de sondeo I requiere establecerse previamente
   • Forma de función de costo α(·) necesita ser conocida
3. Alcance Experimental:
   • Escala experimental relativamente limitada (máximo M=20, A=10)
   • Datos reales probados solo en escenario de transporte compartido
   • Comparación limitada con métodos MAB justos más recientes
4. Medida de Equidad:
   • Solo considera NSW, no explora otros conceptos de equidad (como max-min, envy-freeness)
   • NSW es sensible a recompensas cero (requiere que todos los agentes obtengan recompensas positivas)

Direcciones Futuras

Aunque no se proponen explícitamente en el artículo, se pueden inferir direcciones:

1. Extensión a Otras Medidas de Equidad: Investigar combinación de mecanismos de sondeo con otros conceptos de equidad
2. Presupuesto de Sondeo Adaptativo: Ajustar dinámicamente cantidad de sondeo en lugar de fijar I
3. Implementación Distribuida: Decisiones de sondeo y asignación descentralizadas
4. Entornos No-Estacionarios: Escenarios donde distribuciones de recompensas cambian con el tiempo
5. Condiciones de Restricción: Incorporar restricciones prácticas como presupuesto y latencia

Evaluación Profunda

Fortalezas

1. Rigor Teórico:
   • Ambas configuraciones sin conexión y en línea tienen garantías teóricas estrictas
   • Pruebas completas y detalladas (apéndice supera 20 páginas)
   • Establecimiento de propiedades submodulares ingenioso y crítico
2. Importancia del Problema:
   • Resuelve puntos débiles reales en aplicaciones prácticas (equidad e incertidumbre)
   • Caso de transporte compartido tiene valor de aplicación directa
   • Cierra brecha de investigación entre MAB justo y exploración activa
3. Innovación del Método:
   • Combinación de mecanismo de sondeo con objetivo NSW es novedosa
   • Técnica de construcción de cota superior lineal por segmentos es ingeniosa
   • Fusión de optimización UCB y NSW es no trivial
4. Suficiencia Experimental:
   • Cubre datos sintéticos y reales
   • Múltiples configuraciones de distribución y escala
   • Análisis de escalabilidad completo
   • Experimentos de ablación claros (mediante comparación con Greedy P+A)
5. Claridad de Escritura:
   • Motivación bien articulada
   • Descripción completa de detalles técnicos
   • Gráficos e ilustraciones efectivas

Insuficiencias

1. Eficiencia Computacional Insuficientemente Discutida:
   • No se reportan tiempos de ejecución del algoritmo
   • Falta análisis de complejidad computacional de optimización NSW
   • Viabilidad en escenarios grandes cuestionable
2. Modelado Simplificado de Costo de Sondeo:
   • Función α(|S|) demasiado abstracta
   • Cómo establecer α en aplicaciones reales no se detalla
   • Diferencias en características de costo entre aplicaciones no exploradas
3. Métodos de Referencia Limitados:
   • Comparación principal con método de Jones et al. (2023)
   • Falta comparación con más algoritmos MAB justos recientes
   • Ausencia de comparación con algoritmos de sondeo eficientes pero no justos
4. Escala Experimental Limitada:
   • Máximo M=20, A=10 relativamente pequeño
   • Solo un conjunto de datos real
   • No prueba escenarios extremadamente desbalanceados (M>>A o A>>M)
5. Brecha Teoría-Práctica:
   • Factor de aproximación del Teorema 1 incluye parámetro ζ, cómo seleccionar ζ en práctica no se especifica
   • Constante c en cota de arrepentimiento del Teorema 2 no se aclara
   • Cómo error real de aproximación lineal por segmentos (0.03) afecta desempeño no se analiza
6. Discusión Insuficiente de Equidad:
   • Limitaciones de NSW (sensibilidad a recompensas cero) insuficientemente discutidas
   • Falta comparación con otras medidas de equidad
   • Racionalidad individual (individual rationality) no considerada

Impacto

Impacto Académico:

• Alto: Cierra brecha de investigación importante, se espera alta tasa de citación
• Proporciona nuevo paradigma de investigación para campo de MAB justo
• La combinación de sondeo con equidad puede inspirar trabajo futuro

Valor Práctico:

• Medio-Alto:
  • Potencial de aplicación directa en plataformas como transporte compartido
  • Pero complejidad computacional puede limitar despliegue a gran escala
  • Requiere optimización de ingeniería adicional

Reproducibilidad:

• Alta: Código abierto disponible, descripción de algoritmo detallada
• Prueba teórica completa, fácil de verificar
• Configuración experimental clara

Escenarios Aplicables

Escenarios Fuertemente Aplicables:

1. Despacho de Transporte Compartido: Ciudades de escala media (10-20 regiones, 10-50 vehículos)
2. Recomendación de Contenido: Plataformas necesitando equilibrar exposición de creadores
3. Programación de Redes Inalámbricas: Escenarios WLAN 60 GHz (mencionado en artículo)
4. Asignación de Recursos: Cualquier escenario requiriendo equidad con incertidumbre

Escenarios Débilmente Aplicables:

1. Sistemas a Gran Escala: M,A>100 puede ser computacionalmente infactible
2. Sistemas en Tiempo Real: Latencia de cálculo de NSW puede ser excesiva
3. Entornos Dinámicos: Distribuciones de recompensas cambiando rápidamente
4. Competencia de Suma Cero: Situaciones con competencia directa entre agentes

Escenarios No Aplicables:

1. Problemas Mono-Agente: Método demasiado complejo
2. Recompensas Conocidas: Mecanismo de sondeo innecesario
3. Requisitos Extremos de Equidad: NSW puede ser insuficientemente "justo" (considerar max-min)

Referencias Clave

1. Jones, Nguyen & Nguyen (2023): "An efficient algorithm for fair multi-agent multi-armed bandit with low regret" - Trabajo base directamente extendido por este artículo
2. Cole & Gkatzelis (2015): "Approximating the Nash social welfare with indivisible items" - Fundamentos teóricos de optimización NSW
3. Zuo, Zhang & Joe-Wong (2020): "Observe Before Play: Multi-Armed Bandit with Pre-Observations" - Trabajo pionero en mecanismos de sondeo
4. Bhaskara et al. (2020): "Adaptive probing policies for shortest path routing" - Aplicación de sondeo submodular
5. Caragiannis et al. (2019): "The unreasonable fairness of maximum Nash welfare" - Teoría de equidad NSW

Resumen

Este artículo realiza contribuciones importantes en el campo de bandidos multi-brazo multi-agente, siendo el primero en combinar sistemáticamente mecanismos de sondeo activo con objetivos de equidad. Teóricamente riguroso (aproximación de factor constante y arrepentimiento sublineal), experimentalmente suficiente (datos sintéticos + reales), e innovador metodológicamente (aproximación submodular + fusión UCB-NSW). Las limitaciones principales radican en complejidad computacional y escala experimental, pero no afectan su valor académico y potencial práctico. Este trabajo abre nuevas direcciones de investigación en aprendizaje justo y toma de decisiones en línea, mereciendo exploración y aplicación adicionales.