🤖 AI

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

This paper introduces a multi-worker restless bandit framework that extends the Whittle index to allocate intervention tasks among heterogeneous workers, optimizing reward while simultaneously satisfying individual budget constraints and ensuring fair workload distribution.

Original authors: Arpita Biswas, Jackson A. Killian, Paula Rodriguez Diaz, Susobhan Ghosh, Milind Tambe

Published 2026-02-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arpita Biswas, Jackson A. Killian, Paula Rodriguez Diaz, Susobhan Ghosh, Milind Tambe

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a team of Park Rangers tasked with protecting a vast national park. The park is full of different "zones" (like a forest, a riverbank, or a mountain trail). Each zone has a problem that changes over time: sometimes it's just overgrown with weeds, sometimes it has hidden traps (snares), and sometimes it's clear and safe.

Your goal is to keep the park as safe as possible (maximize the "reward"). To do this, you have a team of Rangers (workers) who can patrol these zones.

The Old Way vs. The New Problem

The Old Way (The "One-Pool" Model):
In the past, computer scientists treated all rangers as identical clones. They assumed:

Every ranger costs the same amount of energy to send out.
Every ranger can fix any problem equally well.
You just have a "bucket" of total energy, and you hand out patrols however you want.

The Real World Problem:
In reality, rangers are different!

Ranger Alice is an expert at clearing thick brush but has a bad knee, so she can't walk far.
Ranger Bob has a metal detector for finding snares but is terrible at clearing brush.
Ranger Charlie is fast but gets tired easily.

If you treat them all the same, you might send Alice to walk 20 miles (breaking her budget) or send Bob to clear brush (wasting his time). Worse, if you just send the "best" rangers to the "best" zones every day, Alice might end up doing all the heavy lifting while Bob sits on his hands. That's unfair, and your team will burn out.

The Paper's Solution: "Fairness for the Pullers"

This paper introduces a new way to plan these patrols, called Multi-Worker Restless Bandits. Think of it as a smart scheduling app that balances doing the most good with keeping the team happy.

Here is how their solution works, broken down into three simple steps:

1. The "Scorecard" (Whittle Indices)

First, the computer calculates a "Score" for every possible combination of Zone + Ranger.

Example: "If we send Ranger Bob to the Riverbank, the score is 90." "If we send Ranger Alice to the Riverbank, the score is 10."
This score tells you how valuable that specific action is.

2. The "Teamwork Adjustment" (The Secret Sauce)

This is the paper's biggest innovation. In the old math, if you calculated Bob's score, it assumed Bob was the only ranger in the world. But in reality, Bob might need Alice to clear the brush first so Bob can find the snares.

The Analogy: Imagine a relay race. If you only look at the runner's speed in isolation, you miss the fact that they need a good handoff from the previous runner to win.
The authors created a new math trick that says: "Hey, when calculating Bob's score, let's pretend Alice is also there helping out in the future." This ensures they don't undervalue a ranger who needs a teammate to be effective.

3. The "Fairness Round-Robin" (Balanced Allocation)

Now that we have the best scores, how do we hand out the tasks?

The Greedy Trap: A greedy approach would just give the top 5 tasks to the 5 "best" rangers, leaving the others with nothing.
The Fair Approach: The authors use a "Round-Robin" system (like dealing cards).
1. They line up the rangers based on who has the highest potential score right now.
2. They give the best available task to the first ranger.
3. They give the next best task to the second ranger.
4. They keep cycling through the team.
The Result: Everyone gets a fair share of the work. No one is overworked, and no one is underutilized. If a task is too expensive for a specific ranger's "energy budget," the system skips them and moves to the next person, ensuring no one breaks their limit.

Why Does This Matter?

The researchers tested this on computers with thousands of different scenarios (like machine repair, health monitoring, and anti-poaching).

The Result: Their method (called CWI+BA) was almost as good as the "perfect" solution at getting rewards (keeping the park safe).
The Win: But unlike the "perfect" solution (which takes forever to calculate and is too slow for real life) or the "greedy" solution (which is unfair), their method was fast, scalable, and fair.

The Big Takeaway

This paper teaches us that when managing a team of humans (or robots with different skills), you can't just look at the "best" option in a vacuum. You have to:

Understand that Teamwork changes the value of an action (Alice + Bob > Alice alone).
Spread the load so that the people doing the work don't get burned out.

It's the difference between a boss who just screams "Get the job done!" and a boss who says, "Let's figure out who is best for which job, make sure we all help each other, and let's make sure everyone goes home with the same amount of energy."

1. Problem Definition: Multi-Worker Restless Multi-Armed Bandits (MWRMAB)

The paper addresses a gap in the existing literature on Restless Multi-Armed Bandits (RMABs). While classical RMABs model sequential decision-making where a planner allocates a limited pool of resources to $N$ independent arms (Markov Decision Processes) to maximize long-term rewards, they assume all resources are homogeneous (interchangeable) and drawn from a single global budget.

The authors introduce the Multi-Worker Restless Multi-Armed Bandit (MWRMAB) problem, which reflects real-world constraints where intervention resources are heterogeneous human workers.

Setup: There are $N$ arms (tasks) and $M$ workers. Each arm $i$ follows an MDP.
Heterogeneity: Each worker $j$ has specific costs ( $c_{ij}$ ) and intervention effects (transition probabilities $P_{ij}$ ) when acting on arm $i$ .
Constraints:
1. Per-Worker Budget: Each worker $j$ has a strict cost budget $B$ per time step.
2. Fairness: The disparity in costs incurred by any pair of workers at any time step must not exceed a threshold $\epsilon$ (i.e., $\max_j C_j(t) - \min_j C_j(t) \leq \epsilon$ ).
Objective: Maximize the expected long-term reward while satisfying individual budget constraints and ensuring load fairness among workers.

The problem is shown to be PSPACE-hard due to the combinatorial explosion of states and actions when $M > 1$ .

2. Methodology

The authors propose a three-step framework to solve the MWRMAB problem efficiently:

Step 1: Decomposition and Decoupled Index Computation

The authors relax the per-timestep budget constraints to time-averaged constraints to decompose the global problem into $N \times M$ independent subproblems.

They compute Whittle Indices ( $\lambda^*_{ij}$ ) for each arm-worker pair.
Theorem 1 establishes a relationship between indices and costs: If two workers have identical transition probabilities but different costs, their Whittle indices are inversely proportional to their costs ( $\lambda^*_{ij} / \lambda^*_{ij'} = c_{ij'} / c_{ij}$ ).
This step assumes workers act independently, which is an approximation.

Step 2: Adjusted Index Computation (Handling Inter-Action Effects)

The decoupled indices from Step 1 are insufficient because the value of a worker's action often depends on the actions of other workers (e.g., one worker clears brush, another detects snares).

Problem: A decoupled index for Worker A might be zero if Worker A cannot reach a reward state alone, even if Worker A is essential when combined with Worker B.
Solution: The authors define an Adjusted Index ( $\lambda^{adj,*}_{j}$ ). This index represents the minimum charge that makes an intervention by worker $j$ as valuable as any other worker $j'$ in a combined MDP with $M+1$ actions.
Algorithm: They use a binary search to find the adjusted index, setting the charges ( $\lambda$ $λ$ ) of other workers to their pre-computed decoupled indices ( $\lambda^*$ $λ^{*}$ ).
- Rationale: Using decoupled indices as charges for other workers provides a realistic lower bound on their value, preventing the artificial suppression of indices (a flaw identified in Theorem 2 where setting other charges to 0 leads to poor policies).

Step 3: Balanced Allocation Algorithm

To ensure fairness and budget feasibility, the authors propose a Balanced Allocation (BA) heuristic:

Ranking: Workers are ordered based on their highest available Whittle index for any unallocated arm.
Round-Robin Assignment: Arms are allocated to workers in a round-robin fashion based on this order.
Budget Check: If an arm violates a worker's budget, the algorithm attempts the next best arm. If no arms can be allocated to a worker due to budget constraints, that worker is temporarily removed from the rotation.
Fairness Guarantee: In homogeneous settings, this algorithm is proven to be optimal and perfectly fair (Theorem 3).

3. Key Contributions

Formalization of MWRMAB: First to formalize the RMAB problem with heterogeneous workers, per-worker budgets, and explicit fairness constraints on workload distribution.
Novel Indexing Framework: Developed a method to compute Adjusted Whittle Indices that account for inter-worker dependencies (inter-action effects), moving beyond the limitations of standard decoupled indices.
Fair Allocation Policy: Introduced a scalable, index-based scheduling policy (Balanced Allocation) that guarantees fairness without significantly sacrificing total reward.
Theoretical Insights: Proved that for homogeneous workers, the proposed framework yields optimal and perfectly fair solutions.

4. Empirical Results

The authors evaluated their method (CWI+BA: Combined Whittle Index + Balanced Allocation) against several baselines:

Baselines:
- PWI+BA: Uses decoupled indices (skips Step 2).
- CWI+GA: Uses adjusted indices but with a Greedy Allocation (skips Step 3).
- Hawkins / OPT / OPT-fair: Optimal or near-optimal solvers (exponential complexity, limited to small instances).
- Random: Random allocation.
Domains Tested: Constant unitary costs, Ordered workers (heterogeneous effectiveness), and Specialist domains (complementary skills).
Performance Metrics:
- Reward: CWI+BA achieves rewards comparable to the optimal baselines (OPT/Hawkins), with a maximum reduction of only 18.95% in the most challenging "ordered worker" scenario.
- Fairness: CWI+BA achieves significantly higher fairness (fraction of time steps with balanced load) than reward-maximizing baselines. In large-scale instances ( $N=150$ ), it showed up to 374.92% improvement in fairness with only a 6.06% reduction in reward compared to reward-maximizing solutions.
- Scalability: While optimal solvers (OPT-fair) run out of memory for $N \geq 10$ , CWI+BA scales linearly and runs in seconds even for $N=150$ .

5. Significance

This work is significant for several reasons:

Real-World Applicability: It bridges the gap between theoretical RMAB models and practical applications involving human workforces (e.g., anti-poaching patrols, machine maintenance, healthcare interventions) where workers have different skills, costs, and workload limits.
Fairness in AI: It addresses a critical, often overlooked aspect of AI planning: fairness among the agents (workers) executing the plan, rather than just fairness among the beneficiaries (arms).
Scalability: It provides a computationally tractable solution to a problem that is theoretically intractable (PSPACE-hard) for optimal solvers, making it viable for real-time deployment in large-scale systems.
Generalization: The approach generalizes the concept of Whittle indices to handle complex interactions between multiple heterogeneous agents, offering a new direction for research in constrained sequential decision-making.