# Fairness of Exposure in Online Restless Multi-armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 9 Feb 2024.

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

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Thompson Sampling in Non-Episodic Restless Bandits](https://mlsanity.com/paper/1910.05654/) (2019)
- [Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting](https://mlsanity.com/paper/2106.07677/) (2021)
- [Equitable Restless Multi-Armed Bandits: A General Framework Inspired By Digital Health](https://mlsanity.com/paper/2308.09726/) (2023)
- [Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem](https://mlsanity.com/paper/1302.3268/) (2013)

## Built on by (most cited first, 1 of 1)

- [Fair Resource Allocation in Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2411.09804/) (2024)

## Abstract (arXiv)

Restless multi-armed bandits (RMABs) generalize the multi-armed bandits where each arm exhibits Markovian behavior and transitions according to their transition dynamics. Solutions to RMAB exist for both offline and online cases. However, they do not consider the distribution of pulls among the arms. Studies have shown that optimal policies lead to unfairness, where some arms are not exposed enough. Existing works in fairness in RMABs focus heavily on the offline case, which diminishes their application in real-world scenarios where the environment is largely unknown. In the online scenario, we propose the first fair RMAB framework, where each arm receives pulls in proportion to its merit. We define the merit of an arm as a function of its stationary reward distribution. We prove that our algorithm achieves sublinear fairness regret in the single pull case O(√Tln T), with T being the total number of episodes. Empirically, we show that our algorithm performs well in the multi-pull scenario as well.