Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need
Sarkar, Pandey, Chowdhury
Regret in stochastic multi-armed bandits traditionally measures the difference between the highest reward and either the arithmetic mean of accumulated rewards or the final reward. These conventional metrics often fail to address fairness among agents receiving rewards, particularly in settings where rewards are distributed across a population, such as patients in clinical trials. To address this, a recent body of work has introduced Nash regret, which evaluates performance via the geometric mean of accumulated rewards, aligning with the Nash social welfare function known for satisfying fairness axioms.
To minimize Nash regret, existing approaches require specialized algorithm designs and strong assumptions, such as multiplicative concentration inequalities and bounded, non-negative rewards, making them unsuitable for even Gaussian reward distributions. We demonstrate that an initial uniform exploration phase followed by a standard Upper Confidence Bound (UCB) algorithm achieves near-optimal Nash regret, while relying only on additive Hoeffding bounds, and naturally extending to sub-Gaussian rewards. Furthermore, we generalize the algorithm to a broad class of fairness metrics called the $p$-mean regret, proving (nearly) optimal regret bounds uniformly across all $p$ values. This is in contrast to prior work, which made extremely restrictive assumptions on the bandit instances and even then achieved suboptimal regret bounds.
academic
Revisitando el Bienestar Social en Bandidos: UCB es (Casi) Todo lo que Necesitas
Este artículo investiga cuestiones de equidad en el problema de bandidos multiarmados (Multi-Armed Bandits, MAB). La métrica tradicional de arrepentimiento (regret) basada en promedios aritméticos no puede garantizar equidad entre usuarios. Para abordar este problema, la comunidad académica ha introducido la métrica de arrepentimiento de Nash (Nash regret) basada en promedios geométricos. Sin embargo, los métodos existentes para minimizar el arrepentimiento de Nash requieren diseño de algoritmos especializados y suposiciones fuertes (como desigualdades de concentración multiplicativas, recompensas no negativas acotadas), e incluso no son aplicables a distribuciones gaussianas. Este artículo demuestra que, mediante una fase de exploración uniforme inicial adaptativa a los datos, combinada con el algoritmo UCB estándar, se puede lograr arrepentimiento de Nash casi óptimo, dependiendo únicamente de desigualdades aditivas de Hoeffding, extendiéndose naturalmente a recompensas subgaussianas. Además, el artículo generaliza el algoritmo a la categoría amplia de métricas de equidad de p-media, probando límites de arrepentimiento (casi) óptimos para todos los valores de p, sin necesidad de las suposiciones estrictas de trabajos anteriores.
Problema Central: En el problema de bandidos multiarmados, ¿cómo maximizar la recompensa acumulada mientras se garantiza equidad entre pasos de tiempo (correspondientes a diferentes usuarios/pacientes)? El arrepentimiento promedio tradicional (Average Regret) solo se enfoca en la utilidad general, lo que puede resultar en recompensas extremadamente bajas en ciertos pasos de tiempo, careciendo de garantías de equidad.
Importancia: En ensayos clínicos, asignación de recursos y otros escenarios de aplicación, cada paso de tiempo corresponde a un individuo independiente (como un paciente). Optimizar solo la utilidad promedio puede llevar a un trato injusto de algunos individuos, lo cual es inaceptable desde perspectivas éticas y de bienestar social.
Limitaciones de Métodos Existentes:
Barman et al. (2023) propone el algoritmo Nash Confidence Bound (NCB), pero depende de desigualdades de Hoeffding/Chernoff multiplicativas, requiere recompensas acotadas y no negativas, no es aplicable a distribuciones generales como la gaussiana, y requiere implícitamente conocer una cota superior de μ*
Krishna et al. (2025) estudia arrepentimiento de p-media, pero requiere que la recompensa esperada de cada brazo sea al menos Ω̃(√k/T^(1/4)), una suposición extremadamente restrictiva que excluye muchos escenarios prácticos, y produce límites de arrepentimiento subóptimos en ciertos valores de p
Motivación de Investigación: Desarrollar un marco general que utilice el algoritmo UCB clásico para lograr objetivos de equidad, sin necesidad de diseñar límites de confianza especializados, y que sea aplicable a distribuciones subgaussianas generales, sin requerir suposiciones poco realistas sobre medias desconocidas.
Marco de Reducción: Propone reducir la minimización de arrepentimiento de Nash/p-media a exploración uniforme breve adaptativa a los datos + algoritmo de bandido estándar (como UCB), siendo la innovación clave una regla de parada adaptativa a los datos
Diseño de Algoritmo: Diseña el algoritmo Welfarist-UCB mediante una estrategia de dos fases:
Fase I: Exploración uniforme hasta satisfacer la condición de terminación adaptativa
Fase II: Exploración-explotación usando el índice UCB estándar
Garantías Teóricas:
Para arrepentimiento de Nash (p=0): Alcanza un límite order-optimal de Õ(σ√(k/T)), aplicable a recompensas σ-subgaussianas
Para p∈0,1: Alcanza un límite order-optimal de Õ(σ√(k/T))
Para p∈[-1,0): Alcanza Õ(k/√T), mejorando el Õ(k^(3/4)T^(-1/4)) de Krishna et al.
Para p<-1: Alcanza Õ(|p|k^((|p|+1)/2)/√T), estrictamente mejor que trabajos anteriores en rangos de T prácticamente relevantes
Innovación Técnica: Utiliza desigualdades aditivas de Hoeffding en lugar de multiplicativas, evitando restricciones estrictas en la distribución de recompensas, y no requiere cota superior de μ*
Verificación Experimental: Valida el algoritmo mediante simulaciones numéricas en diferentes valores de p, demostrando el principio de "no hay almuerzo gratis": requisitos de equidad más fuertes conducen a mayor arrepentimiento
k brazos, donde cada brazo i tiene distribución de recompensa ρᵢ que es σ-subgaussiana, con media μᵢ≥0 (desconocida)
Rango temporal T
Parámetro de equidad p∈(-∞,1]
Salida: Brazo Iₜ seleccionado en cada ronda t∈T
Objetivo: Minimizar el arrepentimiento de p-media
RTp:=μ∗−(T1∑t=1T(E[μIt])p)1/p
donde μ*=maxᵢμᵢ. En particular, p=0 corresponde a arrepentimiento de Nash (media geométrica).
Innovación: El denominador en la condición de terminación (μ^i−2ni2σ2logT)2 asegura que la Fase I termine después de Θ(1/(μ*)²) rondas, en lugar de un número fijo de Θ(√T) o Θ(1/μ*) rondas.
Justificación:
Cuando μ* es grande, se requiere menos exploración para identificar buenos brazos
Cuando μ* es pequeño, se requiere más exploración para diferenciar entre brazos
Esta adaptabilidad asegura que en la Fase II, para cualquier brazo i que se tire, se garantiza que ξi:=μ∗ni22σ2logT≤1/2, lo cual es clave para controlar el arrepentimiento de Nash
Observación Clave: La estrategia de muestreo de permutaciones en la Fase I es equivalente en distribución marginal al muestreo uniforme independiente en cada ronda, es decir, PrIₜ=i=1/k, por lo tanto 𝔼μ_{Iₜ}≥μ*/k.
Significado Técnico: Este acoplamiento estático (static coupling) simplifica el análisis de la Fase I, permitiendo usar directamente las propiedades del muestreo uniforme.
Efectividad Práctica: Welfarist-UCB demuestra desempeño superior en todos los escenarios de prueba
Robustez de Distribución: El algoritmo es efectivo para diferentes distribuciones de recompensa (Bernoulli, gaussiana), verificando la amplia aplicabilidad de la teoría
Compensación Equidad-Utilidad: Los experimentos demuestran claramente la relación de compensación entre el parámetro de equidad p y el arrepentimiento, proporcionando orientación para seleccionar valores apropiados de p en aplicaciones prácticas
Velocidad de Convergencia: En todos los intervalos de p, la velocidad de disminución del arrepentimiento de Welfarist-UCB coincide con las predicciones teóricas y supera a métodos existentes
Contribución Teórica: Demuestra que el algoritmo UCB clásico combinado con exploración adaptativa a los datos puede lograr garantías de equidad casi óptimas, sin necesidad de diseñar límites de confianza especializados
Significado Práctico: Hace que la toma de decisiones secuencial consciente de la equidad sea más práctica y ampliamente aplicable, especialmente en escenarios que requieren manejar distribuciones generales (como gaussiana)
Principio de "No Hay Almuerzo Gratis": Requisitos de equidad más estrictos aumentan intrínsecamente la dificultad del problema de aprendizaje, requiriendo más muestras para lograr bajo arrepentimiento
El diseño de la condición de terminación adaptativa a los datos es ingenioso, resolviendo el fracaso de UCB en minimizar arrepentimiento de Nash
Usar desigualdades aditivas de Hoeffding en lugar de multiplicativas es un avance técnico clave, expandiendo significativamente el rango de aplicabilidad
El marco para manejar todos los valores de p de manera unificada es elegante y poderoso
Suficiencia Experimental:
Cubre múltiples intervalos de p (p>0, p=0, -1<p<0, p<-1)
Compara múltiples métodos de referencia (NCB, Explore-then-UCB)
Incluye experimentos de ablación verificando la hipótesis de "no hay almuerzo gratis"
Poder Convincente de Resultados:
Los límites teóricos son order-optimal o cercanos a optimal en la mayoría de casos
Los resultados experimentales coinciden altamente con predicciones teóricas
Ensayos Clínicos: Necesidad de explorar tratamientos efectivos mientras se garantiza trato justo a cada paciente
Asignación de Recursos: Asignación en línea de recursos limitados (como recursos computacionales, espacios publicitarios) a diferentes usuarios, necesitando equilibrio entre eficiencia y equidad
Sistemas de Recomendación: Recomendar contenido a usuarios en diferentes períodos de tiempo, necesitando evitar experiencia extremadamente pobre en ciertos períodos
Pruebas A/B: En pruebas de productos necesitando considerar bienestar de participantes, no solo métricas promedio
Asignación de Recursos Educativos: Asignar recursos educativos a estudiantes en diferentes períodos de admisión, necesitando equidad entre cohortes
Escenarios No Aplicables:
Aplicaciones a corto plazo requiriendo equidad Rawlsiana extrema (p→-∞) (límite teórico se vuelve vacío)
Escenarios donde distribución de recompensa es de cola pesada o no subgaussiana
Aplicaciones donde μᵢ puede ser significativamente negativo
Barman et al. (2023): "Fairness and welfare quantification for regret in multi-armed bandits" - Propone por primera vez concepto de arrepentimiento de Nash
Krishna et al. (2025): "p-mean regret for stochastic bandits" - Estudia arrepentimiento de p-media general
Bubeck et al. (2012): "Regret analysis of stochastic and nonstochastic multi-armed bandit problems" - Texto clásico de MAB
Moulin (2004): "Fair division and collective welfare" - Fundamentos axiomáticos de bienestar de p-media
Sawarni et al. (2024): "Nash regret guarantees for linear bandits" - Arrepentimiento de Nash en bandidos lineales
Evaluación General: Este es un artículo de alta calidad en aprendizaje automático teórico, haciendo contribuciones importantes en el campo de algoritmos de bandidos conscientes de equidad. Mediante diseño de algoritmo ingenioso y análisis teórico riguroso, demuestra la efectividad de métodos simples (UCB) en objetivos complejos (equidad). Los resultados teóricos son poderosos, la verificación experimental es suficiente, con impacto significativo en el campo. Las principales insuficiencias están en falta de validación en datos reales y ciertos vacíos teóricos (como límites inferiores para p<-1). Se recomienda que trabajos posteriores se enfoquen en validación de aplicación práctica y perfeccionamiento teórico.