# Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling

arXiv: https://arxiv.org/abs/2607.23772 · HTML: https://mlsanity.com/paper/2607.23772/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 21 references that are in the map.
- First posted on arXiv 26 Jul 2026.

## Builds on (most cited first, 10 of 10)

- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [Deadline Scheduling as Restless Bandits](https://mlsanity.com/paper/1610.00399/) (2016)
- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits](https://mlsanity.com/paper/2007.12933/) (2020)
- [Towards Soft Fairness in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2207.13343/) (2022)
- [Lagrangian Index Policy for Restless Bandits with Average Reward](https://mlsanity.com/paper/2412.12641/) (2024)
- [Constrained Restless Bandits for Dynamic Scheduling in Cyber-Physical Systems](https://mlsanity.com/paper/1904.08962/) (2019)
- [Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks](https://mlsanity.com/paper/2303.00799/) (2023)
- [On an Information and Control Architecture for Future Electric Energy Systems](https://mlsanity.com/paper/2206.00160/) (2022)
- [Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy](https://mlsanity.com/paper/2305.00410/) (2023)

## Abstract (arXiv)

We study a restless multi-armed bandit (RMAB) problem for a stochastic deadline scheduling application. RMAB problems are solved using the Whittle index policy. The goal in RMAB is to maximize the expected cumulative discounted reward maximization. The Whittle index policy maximizes reward, but is not fair among two classes. In this paper, we introduce fairness criteria and study an outcome-fair model for RMAB which allows fairness for jobs and users structurally disadvantaged demographic classes. We formulate an outcome fair stochastic deadline scheduling problem as RMAB, and we develop the outcome fair Whittle index policy. We define a virtual queue mechanism that dynamically enforces long-term completion rate guaranties across demographic groups. We analyze a standard Whittle index policy and the outcome-fair index policy. We demonstrate the performance of our algorithms with numerical examples. We compare policies---Whittle index policy (no fairness), input-fairness Whittle index policy, outcome fair Whittle index policy. We observe that the outcome-fair Whittle index policy provides better fairness among classes compared to other policies. We demonstrate a trade off between fairness and profit. This decreases as the server capacity increases.