Research map / Bandits and online learning / Multi-armed bandits
Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RMAB-F, an RMAB variant with long-term minimum activation fairness constraints, and Fair-UCRL, a model-based online RL algorithm using an extended LP and a fair index policy, with sublinear reward and fairness-violation regret bounds.
Problem
Online restless multi-armed bandits must maximize long-term reward under a per-epoch activation budget while guaranteeing each arm a minimum long-term activation fraction, with unknown arm MDPs.
Approach
Relax the instantaneous activation constraint to a long-term one, solve an extended LP over state-action-state occupancy measures inside optimistic UCRL confidence sets, then derive a fair index policy (activation probability per state) that always meets the per-epoch budget.
Key results
- Fair-UCRL is claimed to achieve reward regret of Õ(√(SANT)) and per-arm fairness violation regret Õ(√T) with high probability.
- In simulations (3 arm classes, 100 duplicates each, 1,000 trials), Fair-UCRL achieves the lowest accumulated reward regret among compared methods.
- Fair-UCRL's per-arm minimum activation fraction is satisfied after a transient period in simulations, CPAP, PASCAL and satellite experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Fair-UCRL instead of FaWT-U or Soft Fairness | Simulated RMAB · Simulated environments | accumulated reward regret | Helped |
| Use Fair-UCRL instead of FaWT-U | Simulated RMAB · Simulated environments, arms 1 and 2 | fairness constraint violation | Helped |
| Use Fair-UCRL | CPAP therapy · CPAP therapy | reward regret | Helped |
| Use Fair-UCRL | CPAP therapy · CPAP therapy | fairness constraint satisfaction | Helped |
| Use Fair-UCRL or G-Fair-UCRL instead of the two baselines | PASCAL textual entailment task · PASCAL recognizing textual entailment | reward regret | Helped |
| Use Fair-UCRL instead of the considered baselines | Land mobile satellite system · Land mobile satellite system | reward regret | Helped |
| Use Fair-UCRL | Land mobile satellite system · Land mobile satellite system | long-term average fairness | Helped |
| Greedily enforce fairness satisfaction at the beginning of each episode (ablation) | Fair-UCRL (G-Fair-UCRL) · Simulated environments | accumulated reward regret | Mixed |
Surprising findings
- Randomized initialization can cause short-term fairness violations even though the constraint is met on average.
Limitations
- Assumes all arm MDPs are unichain and feasible; regret bounds rely on mixing-time constants.
- Fairness guarantees hold only on average, with short-term violations possible.
- Experiments are on small simulated or semi-simulated problems rather than large-scale deployments.
Experimental setup
Datasets: simulated birth-and-death arms CPAP adherence Markov model PASCAL recognizing textual entailment worker data land mobile satellite system channel model
Benchmarks: simulated RMAB environments CPAP therapy PASCAL RTE worker annotation land mobile satellite system
Metrics: accumulated reward regret fairness constraint violation (activation fraction)
Baselines: FaWT-U Soft Fairness G-Fair-UCRL
Builds on: UCRL2 colored-UCRL2 LP-based RMAB index policy Whittle index
Closest papers by meaning
- Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback (ICML 2024 · similarity 0.89)
- DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback (ICLR 2025 · similarity 0.89)
- Global Rewards in Restless Multi-Armed Bandits (NeurIPS 2024 · similarity 0.89)
- Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation (NeurIPS 2025 · similarity 0.87)
- The Bandit Whisperer: Communication Learning for Restless Bandits (AAAI 2025 · similarity 0.86)
- Reinforcement learning with combinatorial actions for coupled restless bandits (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.