Fair Resource Allocation in Weakly Coupled Markov Decision Processes

• URL: http://arxiv.org/abs/2411.09804v1
• Date: Thu, 14 Nov 2024 20:40:55 GMT
• Title: Fair Resource Allocation in Weakly Coupled Markov Decision Processes
• Authors: Xiaohui Tu, Yossiri Adulyasak, Nima Akbarzadeh, Erick Delage,
• Abstract summary: We consider fair resource allocation in sequential decision-making environments modeled as weakly coupled Markov decision processes. We adopt a fairness definition using the generalized Gini function instead of the traditional utilitarian (total-sum) objective.
• Score: 3.824858358548714
• License:
• Abstract: We consider fair resource allocation in sequential decision-making environments modeled as weakly coupled Markov decision processes, where resource constraints couple the action spaces of $N$ sub-Markov decision processes (sub-MDPs) that would otherwise operate independently. We adopt a fairness definition using the generalized Gini function instead of the traditional utilitarian (total-sum) objective. After introducing a general but computationally prohibitive solution scheme based on linear programming, we focus on the homogeneous case where all sub-MDPs are identical. For this case, we show for the first time that the problem reduces to optimizing the utilitarian objective over the class of "permutation invariant" policies. This result is particularly useful as we can exploit Whittle index policies in the restless bandits setting while, for the more general setting, we introduce a count-proportion-based deep reinforcement learning approach. Finally, we validate our theoretical findings with comprehensive experiments, confirming the effectiveness of our proposed method in achieving fairness.

Related papers

• Burning RED: Unlocking Subtask-Driven Reinforcement Learning and Risk-Awareness in Average-Reward Markov Decision Processes [7.028778922533688]
  Average-reward Markov decision processes (MDPs) provide a foundational framework for sequential decision-making under uncertainty. We study a unique structural property of average-reward MDPs and utilize it to introduce Reward-Extended Differential (or RED) reinforcement learning.
  arXiv  Detail & Related papers  (2024-10-14T14:52:23Z)
• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric. We propose a single framework built on their equivalence in learning scenarios. Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
  arXiv  Detail & Related papers  (2024-05-09T12:52:22Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Beyond Average Return in Markov Decision Processes [49.157108194438635]
  We prove that only generalized means can be optimized exactly, even in the more general framework of Distributional Reinforcement Learning (DistRL). We provide error bounds on the resulting estimators, and discuss the potential of this approach as well as its limitations.
  arXiv  Detail & Related papers  (2023-10-31T08:36:41Z)
• Domain Generalization via Rationale Invariance [70.32415695574555]
  This paper offers a new perspective to ease the challenge of domain generalization, which involves maintaining robust results even in unseen environments. We propose treating the element-wise contributions to the final results as the rationale for making a decision and representing the rationale for each sample as a matrix. Our experiments demonstrate that the proposed approach achieves competitive results across various datasets, despite its simplicity.
  arXiv  Detail & Related papers  (2023-08-22T03:31:40Z)
• Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation [9.732863739456036]
  We show that existing methods for allocating inducing points severely hamper optimisation performance. By exploiting the quality-diversity decomposition of Determinantal Point Processes, we propose the first inducing point allocation strategy for use in BO.
  arXiv  Detail & Related papers  (2023-01-24T16:43:29Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• A unified algorithm framework for mean-variance optimization in discounted Markov decision processes [7.510742715895749]
  This paper studies the risk-averse mean-variance optimization in infinite-horizon discounted Markov decision processes (MDPs) We introduce a pseudo mean to transform the untreatable MDP to a standard one with a redefined reward function in standard form. We propose a unified algorithm framework with a bilevel optimization structure for the discounted mean-variance optimization.
  arXiv  Detail & Related papers  (2022-01-15T02:19:56Z)
• Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound [15.557653926558638]
  We investigate a counterpart of majority votes over finite ensembles of classifiers, and study its generalization properties. We instantiate it with Dirichlet distributions: this allows for a closed-form and differentiable expression for the expected risk. The resulting majority vote learning algorithm achieves state-of-the-art accuracy and benefits from (non-vacuous) tight bounds.
  arXiv  Detail & Related papers  (2021-06-23T16:57:23Z)
• Stein Variational Model Predictive Control [130.60527864489168]
  Decision making under uncertainty is critical to real-world, autonomous systems. Model Predictive Control (MPC) methods have demonstrated favorable performance in practice, but remain limited when dealing with complex distributions. We show that this framework leads to successful planning in challenging, non optimal control problems.
  arXiv  Detail & Related papers  (2020-11-15T22:36:59Z)

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.