CS Paper Radar

Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes

Xiaohui Tu, Yossiri Adulyasak, Erick Delage

cs.LG ·submitted 2026-09-28 19:44 UTC · v1
theory

Abstract

We consider fair resource allocation in sequential decision-making environments modeled as major-minor weakly coupled Markov decision processes (M2WCMDP). In this framework, resource constraints couple the action spaces of a major sub-Markov decision process (sub-MDP) and a population of minor sub-MDPs that would otherwise operate independently. Instead of using the traditional utilitarian (total-sum) objective, we optimize a general class of monotone, concave, permutation-invariant, normalized fairness functions. With homogeneous minor sub-MDPs, we prove that the problem under symmetry reduces to optimizing the platform-plus-mean-participant utilitarian objective over the class of \textit{permutation-invariant} policies, which allows us to exploit efficient algorithms that optimize the utilitarian-based objective to solve this fairness-aware problem. For more general settings, we introduce a count-proportion-based deep reinforcement learning approach with a priority-based sampler that generates feasible count actions. The generality of our framework means that the proposed algorithms and theoretical guarantees transfer to any domain with a symmetric M2WCMDP structure. We consider two applications: the machine replacement problem and the joint control of pricing and taxi relocation problem on a New York City-calibrated dataset. We validate our theoretical findings with comprehensive experiments, confirming the effectiveness of our proposed method in achieving strong fairness-aware performance while remaining scalable.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Learning in Fairness-Aware Contextual Bandits

cs.LG math.STstat.MEstat.ML ·2026-10-31 ·Gengyu Xue, Fan Wang, Feiyu Jiang, Zifeng Zhao, Yi Yu
theory similarity 0.67
Abstract

Mitigating unfair disparities in sequential decision-making is a growing concern in machine learning. We study contextual bandits under a global covariate-based Lipschitz fairness constraint, pioneered by \cite{dwork2012fairness}, requiring individuals with similar contexts to receive similar action distributions. We show that this constraint induces a randomisation region near the decision boundary and explicitly quantify the population level cost of fairness. We further establish a canonical representation of the optimal fair policy, which reduces the fair policy design to a lower-dimensional boundary optimisation problem. We develop a lazy fair greedy algorithm that exploits fairness-induced covariate diversity under continuous contexts, with policy updates computed via finite-dimensional linear programming. For general context distributions, including discrete and mixed contexts, we propose a lazy polyhedral upper confidence bound (UCB) algorithm, whose optimistic optimisation reduces to finitely many linear programs over confidence-set vertices. Both methods satisfy fairness at every round and achieve regret of order $O(\sqrt{T} + T^{(d-2)/(d-1)}{\indc\{d\geq 4\}})$ up to poly-logarithmic factors, where $d$ is the dimension of the contexts. A matching minimax lower bound for $\ell_1$-based fairness establishes optimality, and reveals an unavoidable nonparametric cost of learning the decision boundary, which dominates the parametric learning cost when $d \geq 4$. Experiments on synthetic and real data support our theoretical findings and demonstrate the practical effectiveness of our methods.

0.12

Learning to Harvest Without Collapse in a Regenerative Commons: A Lagrangian Framework

cs.AI cs.GT ·2026-09-29 ·Jose Tupayachi, Xueping Li, Soham Das
theory similarity 0.64
Abstract

The tragedy of the commons poses a multi-agent safety problem: reward-seeking agents can deplete a shared resource, and cooperation among its users does not itself specify how much must be preserved. We make preservation an explicit requirement by formulating a regenerative commons as a constrained Markov game or a constrained multi-agent MDP with a designer-specified depletion budget. We develop a nonstationary Lagrangian framework that constructs a policy sequence from solutions of unconstrained games or cooperative control problems. Extending earlier time-average constructions, we introduce average-epoch solution concepts for reset episodes with discounted rewards and terminal costs. We prove a reward-independent feasibility certificate, cooperative feasibility and approximate optimality against feasible policy mixtures, and an extension to unbiased sampled costs. For self-interested agents, a constrained Nash certificate quantifies the price-dispersion term introduced by deviations that redistribute budget across epochs. Under the stated assumptions on solver accuracy and multiplier updates, these results give constrained policy-sequence guarantees using solutions of unconstrained problems. Experiments with constrained IPPO and MAPPO in a Gordon-Schaefer fishery examine how depletion budgets shape stock retention, harvest rewards, and price adaptation.

0.18

Who Bears the Burden? Learning Responsibility for Shared Constraints in Multi-Agent Reinforcement Learning

cs.LG cs.AIcs.GTcs.MA ·2026-10-05 ·Xiaoyang Cao, Jingqi Li, Zhe Fu, Alexandre M. Bayen
code/data similarity 0.63
Abstract · 20 pages, 2 figures, 4 tables. Project page with code: https://lira-marl.github.io

When multiple agents share a cost budget, a common Lagrange multiplier can enforce the aggregate constraint but does not determine how its penalty should be allocated across agents. Uniform penalties ignore heterogeneity in the rewards agents sacrifice, while agent-specific multipliers may still rely on the same aggregate cost signal. We introduce Lagrangian Responsibility Allocation (LiRA), which learns each agent's share of a common multiplier by optimizing social welfare over a finite training horizon. The multiplier enforces the aggregate budget, while responsibility shares redistribute its influence without modifying the original rewards or constraints. For convex games under standard regularity conditions, varying these shares induces a smooth family of normalized generalized Nash equilibria in which active constraints remain at their budgets while welfare varies. To optimize responsibility before convergence, we derive a welfare gradient that accounts for both learning updates and the induced change in data distribution. Across CityLearn, MABIM, Harvest, and MetaDrive, spanning 3 to 400 agents, LiRA improves average social welfare by up to 29% over uniform and agent-specific multiplier baselines. Grid and driving costs remain within budget, inventory violations decrease, and Harvest makes more effective use of available budget.

0.36

When Maximum Nash Welfare Becomes Strongly Fair: Bi-valued Goods

cs.GT ·2026-09-09 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.61
Abstract

For the fair allocation of indivisible goods, the milestone work of Caragiannis et al. (2019) revolutionized the understanding of Maximum Nash Welfare (MNW) allocations by revealing their "unreasonable" ability to balance fairness (EF1) and efficiency (PO) for general additive functions. Subsequent work established that MNW allocations simultaneously satisfy EFX and GMMS (and consequently MMS and PMMS) for binary instances (Amanatidis et al. 2021 and Barman et al. 2018), and satisfy EFX for bi-valued instances (Amanatidis et al. 2021). In this paper, we revisit the (personalized) bi-valued instances and provide a tight characterization of the approximation guarantees of MNW allocations with respect to EFX, PMMS, and GMMS, showing that these guarantees are significantly stronger than what is known for general valuations. Furthermore, we demonstrate that even for the slightly more general setting of tri-valued instances, the fairness guarantees of MNW deteriorate significantly, which establishes a sharp boundary on the instances for which MNW allocations are strongly fair.

0.18

Dual-Based Weight Selection for Approximate Linear Programming

eess.SY math.OC ·2026-08-25 ·Su Li, Andre A. Cire, Adam Diamant, Vahid Sarhangian
similarity 0.61
Abstract · 20 pages, 9 figures

Approximate Linear Programming (ALP) is widely used for large-scale Markov Decision Processes (MDPs), but its performance can be sensitive to the choice of state-relevance weights, which are typically selected heuristically. Performance bounds suggest aligning these weights with the discounted occupancy measure of the induced policy, and existing primal approaches address this through repeated greedy-policy construction. Nonetheless, they lack convergence guarantees and are computationally expensive. We propose a dual-based method that uses projected occupancy information from the ALP dual solution to construct a smooth stochastic policy and update the state-relevance weights, which avoids separate greedy-action calculations. We establish conditions under which the weights match the discounted occupancy of the induced policy and prove uniqueness and global convergence under appropriate smoothing. We also derive an a posteriori policy-loss bound that separates error from the weighted Bellman residual, occupancy mismatch, and stochastic-versus-greedy disagreement. Experiments on classical queueing and multi-priority scheduling problems show that the proposed approach reduces sensitivity to fixed weights and achieves comparable or better policy quality than primal updates at lower computational cost. Finally, we show that adaptive weighting is most valuable when the basis functions are sufficiently expressive for occupancy information to influence the resulting policy.

0.28

Safe Multi-Objective Reinforcement Learning: Zero Constraint Violation and Primal-Averaging Convergence

cs.LG cs.AImath.OCstat.ML ·2026-10-29 ·Chenxi Li, Yao Shu, Siyang Gao, Shuang Qiu, Guangxin Jiang
similarity 0.60
Abstract

Many applications of multi-objective reinforcement learning (MORL) require policies that balance conflicting objectives while satisfying safety constraints. We study safe MORL with zero constraint violation throughout learning, covering both cumulative and stepwise constraints. A key challenge is to explore sufficiently under unknown dynamics and constraint costs without violating the constraints. For a given preference over objectives, we develop an algorithm to learn a safe Pareto optimal policy by combining optimistic reward estimates with pessimistic cost bounds. With high probability, every policy executed over $T$ episodes incurs zero constraint violation. The algorithm returns a safe Markov policy induced by the averaged occupancy measure and achieves an $\widetilde{O}(1/\sqrt{T})$ suboptimality gap under smooth Tchebycheff scalarization. We further develop a preference-free algorithm that first explores safely without a prespecified preference and then computes a safe policy for any given preference without further interaction. Over $T$ exploration episodes and $K$ planning iterations, it retains the same safety guarantee and achieves an $\widetilde{O}(1/\sqrt{T}+1/\sqrt{K})$ suboptimality gap. Both algorithms require knowledge of a policy that strictly satisfies the constraints and its costs. We then relax these requirements, incurring at most constant cumulative violation. To our knowledge, we provide the first sample-efficient MORL algorithms that guarantee safety for every executed policy.

0.15

Inference-Time Nash Alignment

cs.AI ·2026-09-08 ·Hadi Hosseini, Debmalya Mandal, Duohan Zhang
theory similarity 0.60
Abstract

Preference-based fine-tuning methods such as RLHF and DPO require substantial compute and large preference datasets. They also need direct access to the model parameters which are not provided by many state-of-the art models. Inference-time alignment offers a cost-effective alternative without updating model parameters. However, existing inference-time methods rely on a scalar reward model derived under a Bradley-Terry assumption, which cannot represent general preferences. Following recent work on fine-tuning with generalized preferences, in this work, we initiate the study of inference-time alignment under general preferences. We formulate the problem as obtaining a Nash equilibrium of a two-player zero-sum game between policies. We propose two algorithms: Best-of-Nash (BoN) and Nash Mirror Descent (NMD). We prove that both algorithms achieve a duality gap that matches the problem lower bound. Empirically, we implement the two methods on three datasets, which shows that our methods substantially outperform the base policy, converging to the performance of the fine-tuned models. Moreover, our results show that NMD remains robust across the regularization parameter.

0.27

Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

cs.DS cs.LG ·2026-09-14 ·Lars Rohwedder, Rico Zenklusen
similarity 0.60
Abstract

Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an action that should be performed by an agent. Depending on the action and the current state of the agent, the agent collects a reward and randomly transitions into a new state. The goal is to maximize the reward in expectation over a finite time horizon of length $H$. We consider a recently introduced variant that generalizes the traditionally additive reward function in the model to a monotone submodular one, which allows for capturing a range of interesting applications. Without the stochastic component, this problem is equivalent to the Submodular Orienteering problem, where the goal is to find an $s$-$t$ walk in a directed graph maximizing a monotone submodular function under a length constraint. We present a novel LP-based algorithm for Submodular Orienteering using ideas from the Sherali-Adams hierarchy and Round-or-Cut. Our guarantees are comparable to the known quasi-polynomial time logarithmic approximation for Submodular Orienteering, but also extend to the setting of Submodular Markov Decision Processes. In the polynomial time regime, we present an $O(n^{\varepsilon})$-approximation (and $O(H^{\varepsilon})$ for Submodular MDPs) for every $\varepsilon >0$, where $n$ is the number of vertices, which was unknown even for Submodular Orienteering. Prior to our work, the best known approximation guarantee for Submodular MDPs had an approximation ratio linear in $H$. Beyond these algorithmic results, our methods reveal a trade-off between the approximation guarantee and the number of previously visited vertices on which an agent conditions its decision.

0.39