Meritocratic Fairness In Budgeted Combinatorial Multi-armed Bandits Via Shapley Values

Abstract

arXiv:2605.00762v1 Announce Type: new 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 und

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keysharma2026meritocratic

Related papers

• Online Learning For Cooperative Multi-player Multi-armed Bandits (2021)5.24
• Trading Off Rewards And Errors In Multi-armed Bandits (2026)0.00
• Unified Framework Of Distributional Regret In Multi-armed Bandits And Reinforcement Learning (2026)0.00
• Concave Statistical Utility Maximization Bandits Via Influence-function Gradients (2026)0.00
• Near-optimal Collaborative Learning In Bandits (2022)0.00
• Pure Exploration Under Mediators' Feedback (2023)0.00
• Flickering Multi-armed Bandits (2026)0.00
• One Good Source Is All You Need: Near-optimal Regret For Bandits Under Heterogeneous Noise (2026)0.00