Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values

• URL: http://arxiv.org/abs/2605.00762v1
• Date: Fri, 01 May 2026 16:20:43 GMT
• Title: Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values
• Abstract summary: We propose a new framework for meritocratic fairness in budgeted multi-armed bandits with full-bandit feedback.<n>We first extend the Shapley value, a classical solution concept from cooperative game theory, to the $K$-Shapley value.<n>We propose K-SVFair-FBF, a fairness-aware algorithm that adaptively estimates $K$-Shapley value with unknown valuation function.
• Score: 0.3823356975862005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new framework for meritocratic fairness in budgeted combinatorial multi-armed bandits with full-bandit feedback (BCMAB-FBF). Unlike semi-bandit feedback, the contribution of individual arms is not received in full-bandit feedback, making the setting significantly more challenging. To compute arm contributions in BCMAB-FBF, we first extend the Shapley value, a classical solution concept from cooperative game theory, to the $K$-Shapley value, which captures the marginal contribution of an agent restricted to a set of size at most $K$. We show that $K$-Shapley value is a unique solution concept that satisfies Symmetry, Linearity, Null player, and efficiency properties. We next propose K-SVFair-FBF, a fairness-aware bandit algorithm that adaptively estimates $K$-Shapley value with unknown valuation function. Unlike standard bandit literature on full bandit feedback, K-SVFair-FBF not only learns the valuation function under full feedback setting but also mitigates the noise arising from Monte Carlo approximations. Theoretically, we prove that K-SVFair-FBF achieves $O(T^{3/4})$ regret bound on fairness regret. Through experiments on federated learning and social influence maximization datasets, we demonstrate that our approach achieves fairness and performs more effectively than existing baselines.

Related papers

• MARBLE: Multi-Aspect Reward Balance for Diffusion RL [71.6241143519038]
  Reinforcement learning has become the dominant approach for aligning diffusion models with human preferences.<n>Existing practice deal with multiple rewards by training one specialist model per reward.<n>We propose MARBLE, a gradient-space optimization framework that maintains independent advantage estimators for each reward.
  arXiv  Detail & Related papers  (2026-05-07T16:20:42Z)
• Creator Incentives in Recommender Systems: A Cooperative Game-Theoretic Approach for Stable and Fair Collaboration in Multi-Agent Bandits [18.15244869689104]
  We analyze collaboration as a multi-agent linear bandit problem with a transferable utility (TU) cooperative game formulation.<n>We show that, for identical (homogenous) agents with fixed action sets, the induced TU game is convex under mild algorithmic conditions.<n>We propose a simple regret-based payout rule that satisfies three out of the four Shapley axioms and also lies in the core.
  arXiv  Detail & Related papers  (2026-04-09T17:45:15Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  We study episodic RL from emphmulti-source imperfect preferences through a cumulative imperfection budget.<n>We propose a unified algorithm with regret $tildeO(sqrtK/M+)$, which exhibits a best-of-both-regimes behavior.
  arXiv  Detail & Related papers  (2026-03-20T19:34:53Z)
• Antithetic Sampling for Top-k Shapley Identification [19.221081896134567]
  The Shapley value's popularity in and outside of explainable AI stems from its axiomatic uniqueness.<n>Most works investigate the uniform approximation of all features' Shapley values, needlessly consuming samples for insignificant features.<n>In contrast, identifying the $k$ most important features can already be sufficiently insightful and yields the potential to leverage algorithmic opportunities connected to the field of multi-armed bandits.
  arXiv  Detail & Related papers  (2025-04-02T15:38:32Z)
• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback.<n>This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc.<n>Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
  We consider a multi-armed bandit problem for maximum value reward function under maximum value and index feedback. We propose an algorithm and provide a regret bound for problem instances with arm outcomes according to arbitrary distributions with finite supports. Our algorithm achieves a $O((k/Delta)log(T))$ distribution-dependent and a $tildeO(sqrtT)$ distribution-independent regret.
  arXiv  Detail & Related papers  (2023-05-25T14:02:12Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  We present the first algorithm with provably vanishing regret for Contextual Bandits with Concave Rewards (CBCR) We derive a novel reduction from the CBCR regret to the regret of a scalar-reward problem. Motivated by fairness in recommendation, we describe a special case of CBCR with rankings and fairness-aware objectives.
  arXiv  Detail & Related papers  (2022-10-18T16:11:55Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  We study the semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we propose a BCUCB-T algorithm with variance-aware confidence intervals. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition.
  arXiv  Detail & Related papers  (2022-08-31T13:09:39Z)
• A One-Size-Fits-All Solution to Conservative Bandit Problems [32.907883501286]
  We study a family of conservative bandit problems (CBPs) with sample-path reward constraints. We propose a One-Size-Fits-All solution to CBPs and present its applications to three encompassed problems.
  arXiv  Detail & Related papers  (2020-12-14T08:50:23Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

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.