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

1. Introduzione e Definizione del Problema

Il paper affronta il problema della pianificazione di interventi su processi stocastici sotto vincoli di risorse, un contesto comune in applicazioni come la manutenzione di macchinari, il monitoraggio di progetti e la pattugliamento anti-bracconaggio.

Il Problema: Multi-Worker Restless Multi-Armed Bandits (MWRMAB)
La letteratura esistente sui Restless Multi-Armed Bandits (RMAB) assume tipicamente che le risorse di intervento provengano da un unico pool omogeneo. Tuttavia, nel mondo reale, gli interventi sono eseguiti da un insieme di lavoratori eterogenei, ciascuno con:

• Costi specifici (es. distanza percorsa, tempo impiegato).
• Vincoli di budget individuali (es. un ranger non può percorrere più di $X$ km al giorno).
• Effetti di intervento diversi (es. un ranger esperto con un metal detector è più efficace di un altro in certe situazioni).

Il problema MWRMAB introduce una nuova sfida: allocare $N$ bracci (task) a $M$ lavoratori in modo da massimizzare la ricompensa attesa a lungo termine, rispettando contemporaneamente:

1. Vincoli di budget per lavoratore: Il costo totale sostenuto da ogni lavoratore non deve superare un limite $B$.
2. Equità (Fairness): La disparità nei costi sostenuti tra qualsiasi coppia di lavoratori non deve superare una soglia $\epsilon$ in ogni istante temporale.

Il problema è formalizzato come un processo decisionale di Markov (MDP) accoppiato debolmente, che è intrattabile ottimalmente (almeno PSPACE-hard) a causa della "maledizione della dimensionalità".

2. Metodologia Proposta

Gli autori propongono un framework basato su indici (Index-Based Policy) che si articola in tre fasi principali per gestire l'eterogeneità e l'equità:

Fase 1: Decomposizione e Calcolo degli Indici di Whittle Decouplati

Il problema combinatorio viene rilassato trasformando i vincoli di budget per istante in vincoli medi temporali. Questo permette di decomporre il problema globale in $N \times M$ sottoproblemi indipendenti.
Per ogni coppia (braccio $i$, lavoratore $j$), viene calcolato l'Indice di Whittle ($\lambda^*_{ij}$). Questo indice rappresenta il "carico" minimo (charge) tale che l'azione di intervento sia equivalente all'azione di non intervento.

• Teorema 1: Viene dimostrato che se due lavoratori hanno le stesse probabilità di transizione ma costi diversi, i loro indici di Whittle sono inversamente proporzionali ai loro costi.

Fase 2: Aggiustamento degli Indici per gli Effetti di Interazione

Gli indici calcolati nella Fase 1 sono "decouplati" e non tengono conto del fatto che l'efficacia di un lavoratore può dipendere dalle azioni di altri lavoratori in momenti successivi (es. un ranger deve prima pulire la vegetazione affinché un altro possa rilevare le trappole).

• Viene introdotta una nuova nozione di indice aggiustato ($\lambda^{adj,*}_{j, \lambda_{-j}}$).
• L'idea chiave è calcolare l'indice per un lavoratore $j$ considerando che gli altri lavoratori $j'$ agiranno nel futuro con i loro rispettivi indici pre-calcolati.
• Si utilizza una ricerca binaria per trovare il valore di $\lambda$ che rende indifferente il pianificatore tra l'azione $j$ e l'azione migliore tra gli altri lavoratori (o l'inerzia), all'interno di un MDP ampliato che include tutte le azioni possibili.
• Questo passaggio evita che gli indici vengano artificialmente ridotti ignorando le sinergie tra lavoratori.

Fase 3: Algoritmo di Allocazione Bilanciata (Balanced Allocation - BA)

Una volta ottenuti gli indici aggiustati, è necessario assegnare i bracci ai lavoratori rispettando i vincoli di budget e di equità.

• L'algoritmo Balanced Allocation ordina i lavoratori in base ai loro indici di Whittle massimi disponibili.
• Assegna i bracci in modo "round-robin" (ciclico) ai lavoratori secondo questo ordine, selezionando il braccio con l'indice più alto disponibile che non violi il budget del lavoratore corrente.
• Se un lavoratore non può ricevere alcun braccio a causa del budget, viene temporaneamente escluso dal ciclo, garantendo che i vincoli di budget siano sempre soddisfatti.
• Teorema 3: In caso di lavoratori omogenei, questo approccio garantisce sia l'ottimalità della ricompensa che l'equità perfetta.

3. Contributi Chiave

1. Formalizzazione del MWRMAB: Prima introduzione e formalizzazione del problema dei "Restless Multi-Armed Bandits" con lavoratori multipli ed eterogenei, includendo vincoli di budget individuali e di equità.
2. Estensione degli Indici di Whittle: Sviluppo di un'estensione degli indici di Whittle per gestire costi eterogenei e budget per lavoratore, inclusa una teoria per l'aggiustamento degli indici per catturare gli effetti di interazione tra lavoratori.
3. Politica di Allocazione Equa: Sviluppo di un algoritmo euristico (Balanced Allocation) che garantisce l'equità nella distribuzione del carico di lavoro senza sacrificare significativamente la ricompensa totale.
4. Valutazione Empirica: Dimostrazione che il metodo proposto supera le basi di riferimento (baselines) in termini di equità, mantenendo prestazioni di ricompensa comparabili alle soluzioni ottimali (ma non scalabili).

4. Risultati Sperimentali

Gli autori hanno valutato il loro metodo (denominato CWI+BA: Combined Whittle Index + Balanced Allocation) su tre domini: costi unitari costanti, lavoratori ordinati (eterogeneità di efficacia) e dominio "specialista" (interazioni complesse).

• Ricompensa: CWI+BA ottiene una ricompensa molto vicina alle soluzioni ottimali (OPT) e all'algoritmo di Hawkins (che massimizza la ricompensa senza equità). La riduzione massima di ricompensa rispetto all'ottimo è stata del 18,95% nel caso peggiore.
• Equità: CWI+BA supera drasticamente le baselines. Mentre algoritmi come Hawkins e OPT ottengono equità in una frazione molto bassa di istanti temporali (spesso 0 o < 0.7), CWI+BA mantiene l'equità nella maggior parte degli istanti temporali.
• Scalabilità:
  • Gli algoritmi ottimali (OPT e OPT-fair) falliscono per istanze di dimensioni moderate ($N \ge 10$) a causa dell'esplosione combinatoria (out of memory).
  • CWI+BA scala bene fino a $N=150$ bracci, con tempi di esecuzione di pochi secondi.
  • Su istanze grandi ($N=150$), CWI+BA mostra un miglioramento dell'equità fino al 374,92% rispetto alla soluzione che massimizza solo la ricompensa, con una riduzione della ricompensa di soli il 6,06%.

5. Significato e Conclusioni

Questo lavoro è significativo perché colma un divario critico tra la teoria dei banditi e le applicazioni reali che coinvolgono risorse umane.

• Modellazione Realistica: Riconosce che i lavoratori non sono intercambiabili e che l'equità nel carico di lavoro è un requisito fondamentale, non solo un'ottimizzazione secondaria.
• Soluzione Pratica: Fornisce un approccio scalabile per problemi che, in forma esatta, sono intrattabili.
• Impatto: Il metodo è direttamente applicabile a scenari come la pattugliamento anti-bracconaggio (dove i ranger hanno competenze e limiti fisici diversi) e la manutenzione industriale, permettendo di pianificare interventi efficienti ed equi.

In sintesi, gli autori dimostrano che è possibile ottenere un alto livello di equità tra i lavoratori senza compromettere drasticamente l'efficacia complessiva del sistema di intervento, offrendo un framework robusto per la gestione di risorse eterogenee in ambienti stocastici.