Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits

• URL: http://arxiv.org/abs/2206.03883v1
• Date: Wed, 8 Jun 2022 13:28:29 GMT
• Title: Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits
• Authors: Dexun Li and Pradeep Varakantham
• Abstract summary: Restless Multi-Armed Bandits (RMAB) is an apt model to represent decision-making problems in public health interventions. In this paper, we are interested in ensuring that RMAB decision making is also fair to different arms while maximizing expected value.
• Score: 8.140037969280716
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Restless Multi-Armed Bandits (RMAB) is an apt model to represent decision-making problems in public health interventions (e.g., tuberculosis, maternal, and child care), anti-poaching planning, sensor monitoring, personalized recommendations and many more. Existing research in RMAB has contributed mechanisms and theoretical results to a wide variety of settings, where the focus is on maximizing expected value. In this paper, we are interested in ensuring that RMAB decision making is also fair to different arms while maximizing expected value. In the context of public health settings, this would ensure that different people and/or communities are fairly represented while making public health intervention decisions. To achieve this goal, we formally define the fairness constraints in RMAB and provide planning and learning methods to solve RMAB in a fair manner. We demonstrate key theoretical properties of fair RMAB and experimentally demonstrate that our proposed methods handle fairness constraints without sacrificing significantly on solution quality.

Related papers

• Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
  We introduce a novel framework of multi-armed bandits (CMAB) with multivariant and probabilistically triggering arms (CMAB-MT) Compared with existing CMAB works, CMAB-MT not only enhances the modeling power but also allows improved results by leveraging distinct statistical properties for multivariant random variables. Our framework can include many important problems as applications, such as episodic reinforcement learning (RL) and probabilistic maximum coverage for goods distribution.
  arXiv  Detail & Related papers  (2024-06-03T14:48:53Z)
• Chain-of-Thought Prompting for Demographic Inference with Large Multimodal Models [58.58594658683919]
  Large multimodal models (LMMs) have shown transformative potential across various research tasks. Our findings indicate LMMs possess advantages in zero-shot learning, interpretability, and handling uncurated 'in-the-wild' inputs. We propose a Chain-of-Thought augmented prompting approach, which effectively mitigates the off-target prediction issue.
  arXiv  Detail & Related papers  (2024-05-24T16:26:56Z)
• A Bayesian Approach to Online Learning for Contextual Restless Bandits with Applications to Public Health [36.83063109531146]
  We present Bayesian Learning for Contextual RMABs (BCoR), an online RL approach for RMABs with unknown underlying transition dynamics. BCoR's key strength is the ability to leverage shared information within and between arms to learn the unknown RMAB transition dynamics quickly.
  arXiv  Detail & Related papers  (2024-02-07T15:11:37Z)
• Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints [17.403031677689427]
  We introduce a new RMAB model with "long-term fairness constraints" For the online RMAB-F setting, the underlying MDPs associated with each arm are unknown to the DM. We prove that Fair-UCRL ensures probabilistic sublinear bounds on both the reward regret and the fairness violation regret.
  arXiv  Detail & Related papers  (2023-12-16T03:35:56Z)
• Deep Reinforcement Learning for Efficient and Fair Allocation of Health Care Resources [47.57108369791273]
  Scarcity of health care resources could result in the unavoidable consequence of rationing. There is no universally accepted standard for health care resource allocation protocols. We propose a transformer-based deep Q-network to integrate the disease progression of individual patients and the interaction effects among patients.
  arXiv  Detail & Related papers  (2023-09-15T17:28:06Z)
• Equitable Restless Multi-Armed Bandits: A General Framework Inspired By Digital Health [23.762981395335217]
  Restless multi-armed bandits (RMABs) are a popular framework for algorithmic decision making in sequential settings with limited resources. RMABs are increasingly being used for sensitive decisions such as in public health, treatment scheduling, anti-poaching, and -- the motivation for this work -- digital health. We study equitable objectives for RMABs for the first time. We consider two equity-aligned objectives from the fairness literature, minimax reward and max Nash welfare. We develop efficient algorithms for solving each -- a water filling algorithm for the former, and a greedy algorithm with theoretically motivated nuance to balance disparate group sizes
  arXiv  Detail & Related papers  (2023-08-17T13:00:27Z)
• Mimicking Better by Matching the Approximate Action Distribution [48.95048003354255]
  We introduce MAAD, a novel, sample-efficient on-policy algorithm for Imitation Learning from Observations. We show that it requires considerable fewer interactions to achieve expert performance, outperforming current state-of-the-art on-policy methods.
  arXiv  Detail & Related papers  (2023-06-16T12:43:47Z)
• Causal Fairness for Outcome Control [68.12191782657437]
  We study a specific decision-making task called outcome control in which an automated system aims to optimize an outcome variable $Y$ while being fair and equitable. In this paper, we first analyze through causal lenses the notion of benefit, which captures how much a specific individual would benefit from a positive decision. We then note that the benefit itself may be influenced by the protected attribute, and propose causal tools which can be used to analyze this.
  arXiv  Detail & Related papers  (2023-06-08T09:31:18Z)
• Limited Resource Allocation in a Non-Markovian World: The Case of Maternal and Child Healthcare [27.812174610119452]
  We consider the problem of scheduling interventions in low resource settings to increase adherence and/or engagement. Past works have successfully developed several classes of Restless Multi-armed Bandit (RMAB) based solutions for this problem. We demonstrate significant deviations from the Markov assumption on real-world data on a maternal health awareness program from our partner NGO, ARMMAN. To tackle the generalised non-Markovian RMAB setting we (i) model each participant's trajectory as a time-series, (ii) leverage the power of time-series forecasting models to predict future states, and (iii) propose the Time
  arXiv  Detail & Related papers  (2023-05-22T02:26:29Z)
• Towards Soft Fairness in Restless Multi-Armed Bandits [8.140037969280716]
  Restless multi-armed bandits (RMAB) is a framework for allocating limited resources under uncertainty. To avoid starvation in the executed interventions across individuals/regions/communities, we first provide a soft fairness constraint. We then provide an approach to enforce the soft fairness constraint in RMABs.
  arXiv  Detail & Related papers  (2022-07-27T07:56:32Z)
• Collapsing Bandits and Their Application to Public Health Interventions [45.45852113386041]
  Collpasing Bandits is a new restless multi-armed bandit (RMAB) setting in which each arm follows a binary-state Markovian process. We build on the Whittle index technique for RMABs to derive conditions under which the Collapsing Bandits problem is indexable. Our algorithm achieves a 3-order-of-magnitude speedup compared to state-of-the-art RMAB techniques.
  arXiv  Detail & Related papers  (2020-07-05T00:33:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.