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

Probleemdefinitie: Multi-Worker Restless Bandits (MWRMAB)

Het paper introduceert en formaliseert een nieuw variant van het Restless Multi-Armed Bandit (RMAB) probleem, genaamd Multi-Worker Restless Multi-Armed Bandits (MWRMAB).

• Context: Traditionele RMAB-modellen gaan ervan uit dat interventieressourcen (werkkrachten) homogeen en uitwisselbaar zijn uit één uniforme pool. In real-world scenario's (zoals anti-bosbrandpatrouilles, machineonderhoud of gezondheidszorg) zijn werknemers echter heterogeen. Elke werknemer heeft:
  • Eigen kostenstructuren (bijv. afgelegde afstand, tijd).
  • Eigen budgetten (maximale kosten per werknemer).
  • Verschillende effectiviteit bij interventies op specifieke taken (armen).
• Het Doel: Het plannen van een interventieschema dat de verwachte totale beloning maximaliseert, terwijl er tegelijkertijd wordt voldaan aan:
  1. Per-werknemer budgetbeperkingen: De totale kosten van een werknemer mogen een vast bedrag $B$ niet overschrijden.
  2. Werknemer-gerichte eerlijkheid (Fairness): De lastverdeling (kosten) tussen werknemers moet gebalanceerd zijn. De dispariteit in kosten tussen elke paar werknemers mag op elk tijdstip een bepaalde drempel $\epsilon$ niet overschrijden.
• Complexiteit: Het probleem is PSPACE-hard. Het combinatorische karakter (toewijzen van $N$ taken aan $M$ werknemers met budget- en eerlijkheidsbeperkingen) maakt een exacte oplossing onmogelijk voor grotere instanties.

Methodologie

De auteurs stellen een drie-staps raamwerk voor om dit probleem op te lossen, gebaseerd op Whittle-indexen, maar aangepast voor heterogeniteit en eerlijkheid.

Stap 1: Decompositie en Berekening van Whittle-indexen

Het probleem wordt ontbonden in $N \times M$ subproblemen. Voor elk paar (arm $i$, werknemer $j$) wordt een Whittle-index $\lambda^*_{ij}$ berekend.

• Dit gebeurt door de budgetbeperkingen te verzwakken naar tijd-gemiddelde beperkingen en Lagrange-multiplicatoren te gebruiken.
• Stelling 1: Als twee werknemers dezelfde overgangswaarschijnlijkheden hebben maar verschillende kosten, zijn hun Whittle-indexen omgekeerd evenredig met hun kosten ($\lambda^*_{ij} / \lambda^*_{ij'} = c_{ij'} / c_{ij}$). Dit vereenvoudigt de berekening in bepaalde structuren.

Stap 2: Aanpassing voor Interactie-effecten (Adjusted Indices)

Een cruciale innovatie is de aanpassing van de indexen om rekening te houden met de interactie tussen werknemers.

• Het probleem: In een standaard RMAB wordt aangenomen dat de waarde van een actie alleen afhangt van die actie. In MWRMAB hangt de waarde van een actie van werknemer $j$ vaak af van wat andere werknemers $j'$ in de toekomst doen (bijv. werknemer 1 moet struikgewas verwijderen voordat werknemer 2 een val kan detecteren).
• Oplossing: De auteurs definiëren een aangepaste index ($\lambda^{adj,*}$). In plaats van alleen te kijken naar de actie van $j$ versus "geen actie", wordt de index berekend in een uitgebreid MDP waar alle andere werknemers $j'$ ook actief zijn met hun eigen kosten.
• Strategie: De kosten (charges) $\lambda_{j'}$ voor andere werknemers worden vastgesteld op hun reeds berekende decoupled Whittle-indexen ($\lambda^*_{j'}$). Dit voorkomt dat de indexen kunstmatig laag worden (wat zou gebeuren als men andere acties als gratis zou beschouwen) en zorgt voor een realistische inschatting van de langdurige waarde van een actie binnen een team.

Stap 3: Gebalanceerde Toewijzing (Balanced Allocation)

Om de eerlijkheid en budgetbeperkingen te waarborgen, wordt een Balanced Allocation (BA) algoritme gebruikt.

• Werking: Op elk tijdstip worden de werknemers gesorteerd op basis van hun hoogste beschikbare index. Vervolgens worden taken in een round-robin patroon toegewezen aan de werknemers volgens deze volgorde.
• Budgetcontrole: Als de toewijzing van de "beste" taak een budgetoverschrijding veroorzaakt, wordt de volgende beste taak geprobeerd.
• Eerlijkheid: Het algoritme zorgt ervoor dat de kostenverdeling tussen werknemers binnen de drempel $\epsilon$ blijft. Als een werknemer zijn budget bereikt, wordt hij tijdelijk uitgesloten van verdere toewijzingen totdat de lasten weer gebalanceerd zijn.

Kernbijdragen

1. Formalisatie van MWRMAB: Het is het eerste werk dat het RMAB-probleem uitbreidt naar heterogene werknemers met per-werknemer budgetten en specifieke eerlijkheidsbeperkingen.
2. Index-uitbreiding: Een nieuwe methode om Whittle-indexen te berekenen voor meerdere werknemers, inclusief een theorie voor het aanpassen van deze indexen om interactie-effecten tussen werknemers te modelleren.
3. Eerlijkheidsalgoritme: Een toewijzingsstrategie die garant staat voor eerlijke lastverdeling zonder de totale beloning significant te verlagen.
4. Theoretische garanties: Bewijs dat voor homogene werknemers het algoritme een optimale oplossing levert die perfect eerlijk is.

Resultaten en Evaluatie

De methode (genaamd CWI+BA: Combined Whittle Index + Balanced Allocation) is getest op drie domeinen:

1. Constante eenheidskosten: Alle werknemers hebben dezelfde kosten, maar verschillende overgangswaarschijnlijkheden.
2. Gesorteerde werknemers: Werknemers hebben een hiërarchie in effectiviteit.
3. Specialist-domein: Werknemers zijn gespecialiseerd (bijv. één verwijdert struikgewas, de andere detecteert vallen), wat sterke interactie-effecten vereist.

Vergelijking met Baselines:
De methode is vergeleken met:

• PWI+BA: Zonder aanpassing voor interactie-effecten.
• CWI+GA: Met interactie-effecten, maar met een "Gierige" (niet-gebalanceerde) toewijzing.
• Hawkins & OPT: Optimalisatie-algoritmen die de eerlijkheidsbeperking negeren of exacte oplossingen zoeken (alleen voor kleine problemen mogelijk).

Belangrijkste bevindingen:

• Eerlijkheid: CWI+BA bereikt een aanzienlijk hoger percentage tijdstippen met eerlijke toewijzing dan reward-maximaliserende baselines (zoals Hawkins en OPT). In sommige scenario's is de verbetering in eerlijkheid tot 374% ten opzichte van de beste reward-georiënteerde oplossing.
• Beloning: CWI+BA behaalt een beloning die vergelijkbaar is met de reward-maximaliserende baselines (maximaal 18,95% lager dan de optimale oplossing, maar vaak veel minder). De aanpassing voor interactie-effecten (Stap 2) is cruciaal; zonder deze (PWI+BA) daalt de beloning.
• Schaalbaarheid: Waar exacte oplossingen (OPT-fair) exponentieel meer geheugen vereisen en falen bij $N > 10$, schaal CWI+BA goed tot $N=150$ en draait binnen enkele seconden.
• Conclusie: De methode biedt een uitstekende afweging: bijna optimale beloning met gegarandeerde eerlijkheid en hoge schaalbaarheid.

Significantie

Dit paper is significant omdat het een brug slaat tussen theoretische optimalisatie (RMAB) en praktische toepassing in menselijk werk. Bestaande modellen negeren vaak de heterogeniteit van menselijke krachten en de noodzaak van eerlijke lastverdeling. Door dit probleem te formaliseren en een schaalbare, index-gebaseerde oplossing te bieden, maakt het paper interventieplanning mogelijk in complexe real-world scenario's zoals:

• Anti-bosbrandpatrouilles: Waar rangers verschillende fysieke capaciteiten en budgetten hebben.
• Machineonderhoud: Waar technici verschillende specialismen en werktijden hebben.
• Gezondheidszorg: Waar zorgverleners verschillende capaciteiten hebben om patiënten te behandelen.

De introductie van "worker-centric fairness" verandert de focus van puur het maximaliseren van output naar het optimaliseren van het systeem binnen de beperkingen en behoeften van het menselijke team.