Resumen Técnico: Equidad para Trabajadores que Manejan los Brazos: Una Política Basada en Índices para la Asignación de Tareas de Banditos Inquietos

1. Introducción y Definición del Problema

El artículo aborda la planificación de intervenciones en procesos estocásticos bajo restricciones de recursos, un problema tradicionalmente modelado como Banditos Inquietos Multi-brazo (RMAB). En los modelos clásicos de RMAB, se asume que todos los recursos de intervención (trabajadores) provienen de un único pool homogéneo e intercambiable.

Sin embargo, los autores identifican una limitación crítica en aplicaciones del mundo real (como patrullaje anti-caza furtiva, mantenimiento de máquinas o monitoreo de proyectos): la fuerza laboral es heterogénea. Cada trabajador tiene:

• Costos de intervención distintos (ej. distancia recorrida, tiempo).
• Restricciones presupuestarias individuales (presupuesto por trabajador).
• Efectos de intervención diferentes (probabilidades de transición de estado distintas).
• Necesidad de equidad en la carga de trabajo (evitar que algunos trabajadores realicen mucho más trabajo que otros).

Para abordar esto, los autores formalizan el problema de Banditos Inquietos Multi-trabajador (MWRMAB). El objetivo es maximizar la recompensa esperada a largo plazo mientras se satisfacen dos tipos de restricciones:

1. Presupuesto por trabajador: La suma de costos de las tareas asignadas a un trabajador $j$ no debe exceder un umbral $B$.
2. Equidad: La disparidad en los costos incurridos entre cualquier par de trabajadores no debe exceder un umbral de equidad $\epsilon$ en cada paso de tiempo.

Este problema es computacionalmente difícil (al menos PSPACE-duro) debido a la maldición de la dimensionalidad al combinar múltiples MDPs y restricciones de presupuesto individuales.

2. Metodología Propuesta

Los autores proponen un marco de trabajo de tres pasos para resolver el MWRMAB de manera escalable y justa:

Paso 1: Descomposición y Cálculo de Índices de Whittle

Se relajan las restricciones de presupuesto por paso de tiempo a restricciones de promedio temporal. El problema se descompone en $N \times M$ subproblemas independientes (donde $N$ es el número de brazos/tareas y $M$ el número de trabajadores).

• Se calculan los Índices de Whittle ($\lambda^*_{ij}$) para cada par (brazo $i$, trabajador $j$).
• Teorema 1: Se demuestra que si dos trabajadores tienen las mismas probabilidades de transición pero diferentes costos, sus índices de Whittle son inversamente proporcionales a sus costos. Esto permite simplificar el cálculo en ciertas estructuras.

Paso 2: Ajuste por Efectos de Interacción (Novedad Clave)

Los índices calculados en el Paso 1 asumen que los trabajadores actúan de forma independiente, lo cual es subóptimo en escenarios donde la acción de un trabajador afecta la viabilidad de la acción de otro (ej. un ranger limpia la maleza para que otro pueda detectar trampas).

• Se introduce un Índice Ajustado ($\lambda^{adj,*}_{j}$).
• En lugar de considerar solo la acción "pasiva" vs. "activa" para un trabajador, el nuevo índice calcula la carga mínima necesaria para hacer que la acción del trabajador $j$ sea tan valiosa como la acción de cualquier otro trabajador $j'$ en un MDP combinado.
• Algoritmo 1: Utiliza una búsqueda binaria sobre una función de valor aumentada, fijando las cargas de los otros trabajadores en sus índices de Whittle desacoplados precalculados. Esto evita subestimar artificialmente el valor de una acción cuando otros trabajadores están disponibles.

Paso 3: Algoritmo de Asignación Equilibrada (Balanced Allocation)

Una vez obtenidos los índices ajustados, se utiliza un algoritmo heurístico para asignar las tareas:

• Algoritmo 2 (Asignación Equilibrada): Ordena a los trabajadores basándose en sus mejores índices disponibles.
• Asigna las tareas a los trabajadores de forma rotativa (round-robin) según este orden, seleccionando el mejor brazo disponible para cada trabajador.
• Si la asignación del mejor brazo viola el presupuesto del trabajador, se intenta con el siguiente mejor.
• Si un trabajador no puede recibir más tareas debido al presupuesto, se le asigna su paquete actual y se excluye de rondas futuras hasta que se reinicie el ciclo.
• Teorema 3: Se demuestra que, en el caso de trabajadores homogéneos, este enfoque produce una política óptima y perfectamente equitativa.

3. Contribuciones Principales

1. Formalización del MWRMAB: Son los primeros en definir y formalizar el problema de banditos inquietos con múltiples trabajadores heterogéneos y restricciones de equidad centradas en el trabajador.
2. Extensión de Índices de Whittle: Desarrollan una extensión de los índices de Whittle que maneja costos heterogéneos y presupuestos por trabajador.
3. Mecanismo de Ajuste de Índices: Proponen un método novedoso para ajustar los índices considerando los efectos de interacción entre diferentes tipos de trabajadores, superando las limitaciones de los enfoques desacoplados.
4. Política de Asignación Justa: Crean un algoritmo de asignación que garantiza la equidad en la carga de trabajo sin sacrificar significativamente la recompensa total.

4. Resultados Empíricos

Los autores evaluaron su método (denominado CWI+BA: Combined Whittle Index + Balanced Allocation) en tres dominios: costos unitarios constantes, trabajadores ordenados (por habilidad) y dominio de especialistas.

• Recompensa vs. Equidad:
  • CWI+BA logra recompensas comparables a las soluciones óptimas (OPT) y baselines de maximización de recompensa (Hawkins), con una reducción máxima de recompensa de solo ~18.95% en casos difíciles.
  • En términos de equidad, CWI+BA supera drásticamente a los baselines. Mientras que algoritmos como Hawkins y OPT a menudo fallan en mantener la equidad (0% de pasos de tiempo justos en algunos casos), CWI+BA logra asignaciones justas en la gran mayoría de los pasos de tiempo.
• Escalabilidad:
  • Las soluciones óptimas (OPT y OPT-fair) son exponenciales y agotaron la memoria para instancias con $N \ge 10$ brazos.
  • CWI+BA es significativamente más rápido (mejora del 33% al 83% en tiempo de ejecución para $N=5$) y escala bien hasta $N=150$ brazos, ejecutándose en segundos.
  • En instancias grandes ($N=150$), CWI+BA mostró una mejora de hasta el 374.92% en equidad con una reducción de recompensa de solo el 6.06% comparado con soluciones que solo maximizan recompensa.

5. Significancia y Conclusión

Este trabajo es fundamental porque cierra la brecha entre la teoría de los banditos inquietos y la realidad de la gestión de fuerzas laborales humanas.

• Modelado Realista: Permite modelar escenarios donde los recursos no son fungibles (intercambiables) y tienen limitaciones individuales, algo que los modelos anteriores ignoraban.
• Viabilidad Práctica: Ofrece una solución computacionalmente viable para problemas que de otro modo serían intratables (NP-duro/PSPACE-duro) al introducir restricciones de equidad.
• Impacto Social: Al garantizar la equidad en la carga de trabajo, el método es directamente aplicable a contextos críticos como la protección de la vida silvestre (donde los guardabosques deben tener cargas de trabajo justas) y el mantenimiento industrial, asegurando la sostenibilidad de la fuerza laboral mientras se mantiene la eficiencia operativa.

En resumen, el enfoque propuesto demuestra que es posible lograr un equilibrio óptimo entre la eficiencia (recompensa) y la equidad (carga de trabajo) en sistemas de decisión secuencial complejos, superando las limitaciones de los métodos de asignación tradicionales.