Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks

Título: Justiça para Trabalhadores que "Puxam os Braços": Uma Política Baseada em Índice para Alocação de Tarefas de Bandit Inquieto

1. Problema e Motivação

O artigo aborda o problema de planejamento de intervenção em processos estocásticos sob restrições de recursos, modelado tradicionalmente como Bandits Inquietos Multi-Armados (RMAB - Restless Multi-Armed Bandits). No cenário clássico, um planejador aloca recursos de intervenção limitados entre $N$ braços (tarefas) para maximizar a recompensa de longo prazo, assumindo que todos os recursos são homogêneos e intercambiáveis.

No entanto, o artigo identifica uma lacuna crítica: em aplicações do mundo real (como patrulhas anti-patrulha, manutenção de máquinas ou monitoramento de saúde), os recursos de intervenção são trabalhadores humanos heterogêneos. Cada trabalhador possui:

• Custos heterogêneos: O custo de intervir em um braço específico varia dependendo do trabalhador (ex.: distância percorrida, especialização).
• Orçamentos individuais: Cada trabalhador tem um limite de custo (orçamento) que não pode ser excedido.
• Restrições de carga de trabalho: É necessário garantir justiça (fairness) na distribuição da carga de trabalho entre os trabalhadores, evitando que alguns fiquem sobrecarregados enquanto outros ficam ociosos.

O problema proposto é chamado de Multi-Worker Restless Multi-Armed Bandits (MWRMAB). O objetivo é maximizar a recompensa esperada total, respeitando os orçamentos individuais de cada trabalhador e garantindo que a disparidade nos custos incorridos entre qualquer par de trabalhadores não ultrapasse um limiar de justiça $\epsilon$.

2. Metodologia

Os autores propõem um framework de três etapas para resolver o MWRMAB, que é computacionalmente difícil (PSPACE-difícil) devido à dimensionalidade combinatória.

Etapa 1: Decomposição e Cálculo de Índices Whittle

O problema combinatório é relaxado para restrições de orçamento médias no tempo, permitindo a decomposição em $N \times M$ subproblemas independentes (onde $N$ é o número de braços e $M$ o número de trabalhadores).

• Para cada par (braço $i$, trabalhador $j$), calcula-se um Índice de Whittle ($\lambda^*_{ij}$).
• O índice representa o "custo de oportunidade" ou a carga mínima necessária para tornar a ação de intervenção tão valiosa quanto a inação.
• Teorema 1: Os autores provam que, se dois trabalhadores têm probabilidades de transição idênticas mas custos diferentes, seus índices de Whittle são inversamente proporcionais aos seus custos ($\lambda_{ij} \cdot c_{ij} = \text{constante}$).

Etapa 2: Ajuste dos Índices (Inter-Ação)

Os índices calculados na Etapa 1 são "desacoplados" e não consideram que a eficácia de um trabalhador pode depender das ações de outros trabalhadores em passos de tempo futuros (efeitos de interação).

• Exemplo: Em um cenário de patrulha, um trabalhador pode limpar a vegetação (tornando o braço acessível), permitindo que outro trabalhador detecte armadilhas. Se calculado isoladamente, o primeiro trabalhador teria um índice baixo.
• Solução: Os autores definem um Índice Ajustado ($\lambda^{adj}_{ij}$). Eles calculam o índice de um trabalhador $j$ considerando que os outros trabalhadores $j'$ estão ativos com seus respectivos índices de Whittle pré-calculados. Isso captura o valor de longo prazo das interações entre trabalhadores.
• O algoritmo utiliza uma busca binária para encontrar o valor de carga que torna o planejador indiferente entre agir com $j$ ou não agir, dado que as outras ações estão disponíveis.

Etapa 3: Algoritmo de Alocação Balanceada (Balanced Allocation)

Para alocar os braços aos trabalhadores respeitando orçamentos e justiça, os autores propõem o algoritmo Balanced Allocation (BA):

1. Ordena os trabalhadores com base em seus melhores índices de Whittle disponíveis.
2. Atribui os braços (tarefas) de forma rotativa (round-robin) aos trabalhadores na ordem de prioridade.
3. Se a alocação do melhor braço disponível violar o orçamento de um trabalhador, tenta-se o próximo melhor braço.
4. Se nenhum braço puder ser alocado a um trabalhador sem violar o orçamento, ele é removido da rodada atual.

• Teorema 3: Em cenários onde os trabalhadores são homogêneos, este algoritmo garante a política ótima e justiça perfeita (diferença de alocação de no máximo 1 tarefa entre trabalhadores).

3. Contribuições Principais

1. Formalização do MWRMAB: Primeira introdução e formalização do problema de Bandits Inquietos com múltiplos trabalhadores heterogêneos e restrições de justiça centradas no trabalhador.
2. Extensão do Índice de Whittle: Desenvolvimento de uma extensão do índice de Whittle para lidar com custos heterogêneos e orçamentos por trabalhador, incluindo um método para ajustar os índices considerando efeitos de interação entre trabalhadores.
3. Política de Alocação Justa: Criação de um algoritmo de alocação que equilibra a maximização de recompensa com a equidade na carga de trabalho.
4. Análise Empírica: Demonstração de que a solução proposta supera as abordagens de base (baselines) em termos de justiça, mantendo a eficiência de recompensa.

4. Resultados Empíricos

Os autores avaliaram o método em três domínios: custos unitários constantes, trabalhadores ordenados (heterogeneidade de eficiência) e domínio de especialistas (interações críticas).

• Recompensa vs. Justiça: O método proposto (CWI+BA - Combined Whittle Index + Balanced Allocation) alcançou recompensas comparáveis às soluções ótimas (OPT) e ao método de Hawkins (que maximiza recompensa sem justiça), com uma redução máxima de apenas 18,95% na recompensa em relação ao ótimo.
• Desempenho em Justiça: Enquanto algoritmos focados apenas em recompensa (Hawkins, OPT) falharam consistentemente em garantir justiça (0% de passos de tempo justos em alguns casos), o CWI+BA alcançou alocação justa na grande maioria dos passos de tempo.
• Escalabilidade:
  • Algoritmos ótimos (OPT-fair) tornam-se intratáveis (esgotam memória) para instâncias com $N \ge 10$ braços.
  • O CWI+BA escala bem, resolvendo instâncias com $N=150$ braços em segundos.
  • Em instâncias maiores ($N=150$), o método mostrou uma melhoria de 374,92% na justiça em comparação com soluções que maximizam apenas a recompensa, com uma redução mínima de 6,06% na recompensa.

5. Significado e Conclusão

Este trabalho é significativo porque preenche a lacuna entre a teoria de Bandits Inquietos e a realidade da gestão de força de trabalho humana. Ao reconhecer que os trabalhadores não são recursos homogêneos e que a equidade na carga de trabalho é um requisito operacional crucial, o paper oferece uma solução prática e escalável.

A abordagem demonstra que é possível integrar restrições complexas de orçamento individual e justiça sem sacrificar drasticamente a eficiência global do sistema. Isso tem implicações diretas para otimização de recursos em segurança pública, manutenção industrial e saúde pública, onde a sustentabilidade da força de trabalho é tão importante quanto a eficácia da intervenção.

O artigo conclui que o problema de alocação balanceada com trabalhadores heterogêneos permanece um desafio teórico aberto para limites de aproximação, mas a solução proposta oferece um framework robusto e eficaz para aplicações práticas.