Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare

• URL: http://arxiv.org/abs/2605.01961v1
• Date: Sun, 03 May 2026 16:47:24 GMT
• Title: Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare
• Abstract summary: We consider fairness in dueling bandits, a standard framework for online learning from preference data.<n>We adopt the well-established Nash Social Welfare objective, which maximizes the product of user utilities.<n>We present the Fair-Explore-Then-Commit and Fair-$$-Greedy algorithms with a Condorcet winner identification phase.
• Score: 6.353413440036643
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning from human preference data is becoming a useful tool, from fine-tuning large language models to training reinforcement learning agents. However, in most scenarios, the model is trained on the average preference of all human evaluators, which, under large variations of preferences, can be unfair to minority groups. In this work, we consider fairness in dueling bandits, a standard framework for online learning from preference data. We assume that each user has a (potentially distinct) Condorcet winner, which is an arm preferred to every other arm. Using these user-specific Condorcet winners as reference points, we evaluate and score arms according to their performance relative to the corresponding winner. To promote fairness across heterogeneous users, we adopt the well-established Nash Social Welfare objective, which maximizes the product of user utilities, thereby inherently penalizing inequality and preventing the marginalization of any single user. Within this framework, we construct a hard instance to establish a regret lower bound of $Ω(T^{2/3}\min(K,D)^\frac{1}{3})$ for a time horizon $T$, $K$ arms, and $D$ users, which, to the best of our knowledge, is the first result quantifying the cost of fairness in dueling bandits with heterogeneous preferences. We then present the Fair-Explore-Then-Commit and Fair-$ε$-Greedy algorithms with a Condorcet winner identification phase. We further derive their regret upper bounds that match the lower-bound dependence on $T$ up to logarithmic factors.

Related papers

• Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning [8.823317238417834]
  We study a multi-agent multi-armed bandit problem in the competitive setup with two-sided matching markets under a human centric decision making model.<n>We use cumulative prospect theory (CPT) that weighs the actions of the agent in a nonlinear fashion using a ($$-Hlder continuous) weight function.
  arXiv  Detail & Related papers  (2026-06-18T07:43:05Z)
• The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits [6.244816393907942]
  We study best-arm identification in dueling bandits under the sole assumption that a Condorcet winner exists.<n>We introduce a new identification procedure that exploits the full gap matrix $_i,j=q_i,j-tfrac12$.<n>We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones.
  arXiv  Detail & Related papers  (2026-03-16T12:27:14Z)
• Combinatorial Allocation Bandits with Nonlinear Arm Utility [37.64693919880475]
  We propose a novel online learning problem, Combinatorial Allocation Bandits (CAB), which incorporates the notion of *arm satisfaction*.<n>Unlike prior work, the learner's objective is not to maximize the number of positive feedback, but rather to maximize the arm satisfaction.<n>We provide an upper confidence bound algorithm that achieves an approximate regret upper bound, which matches the existing lower bound for the special case.
  arXiv  Detail & Related papers  (2026-03-07T02:57:27Z)
• Neural Dueling Bandits: Preference-Based Optimization with Human Feedback [58.90189511247936]
  We use a neural network to estimate the reward function using preference feedback for the previously selected arms.<n>We also extend our theoretical results to contextual bandit problems with binary feedback, which is in itself a non-trivial contribution.
  arXiv  Detail & Related papers  (2024-07-24T09:23:22Z)
• Robust Reinforcement Learning from Corrupted Human Feedback [86.17030012828003]
  Reinforcement learning from human feedback (RLHF) provides a principled framework for aligning AI systems with human preference data. We propose a robust RLHF approach -- $R3M$, which models the potentially corrupted preference label as sparse outliers. Our experiments on robotic control and natural language generation with large language models (LLMs) show that $R3M$ improves robustness of the reward against several types of perturbations to the preference data.
  arXiv  Detail & Related papers  (2024-06-21T18:06:30Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms [12.368291979686122]
  We propose a model for learning with bandit feedback while accounting for deterministically evolving and unobservable states.<n>The workhorse applications of our model are learning for recommendation systems and learning for online ads.
  arXiv  Detail & Related papers  (2023-07-21T15:43:32Z)
• Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms [75.17357040707347]
  Motivated by online recommendation systems, we propose the problem of finding the optimal policy in contextual bandits. The goal is to robustly learn the policy that maximizes rewards for good users with as few user interactions as possible. We show we can achieve an $tildeO(min(S,A)cdot alpha/epsilon2)$ upper-bound, by employing efficient robust mean estimators.
  arXiv  Detail & Related papers  (2022-01-30T01:45:13Z)
• Linear Speedup in Personalized Collaborative Learning [69.45124829480106]
  Personalization in federated learning can improve the accuracy of a model for a user by trading off the model's bias. We formalize the personalized collaborative learning problem as optimization of a user's objective. We explore conditions under which we can optimally trade-off their bias for a reduction in variance.
  arXiv  Detail & Related papers  (2021-11-10T22:12:52Z)
• Learning the Optimal Recommendation from Explorative Users [38.332330484187395]
  We study the sequential interactions between a recommender system and a user. We show that efficient system learning is still possible but is more difficult.
  arXiv  Detail & Related papers  (2021-10-06T21:01:18Z)
• Competing Bandits: The Perils of Exploration Under Competition [99.68537519404727]
  We study the interplay between exploration and competition on online platforms. We find that stark competition induces firms to commit to a "greedy" bandit algorithm that leads to low welfare. We investigate two channels for weakening the competition: relaxing the rationality of users and giving one firm a first-mover advantage.
  arXiv  Detail & Related papers  (2020-07-20T14:19:08Z)

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.