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

Problem Definition

The paper addresses the Fair Multi-User Dueling Bandit problem, a setting where an agent learns from pairwise preference data provided by $D$ distinct users over a time horizon $T$ with $K$ arms. Unlike standard dueling bandits that assume a single preference model or aggregate preferences into a single matrix, this work considers a scenario where each user $d$ possesses a potentially distinct preference matrix $P_d$.

The core challenge is to learn a policy that balances the interests of these heterogeneous users without marginalizing minority groups. Standard approaches that optimize for average (utilitarian) welfare often favor the statistical majority, leading to unfair outcomes for users with divergent preferences. To address this, the authors define the objective using Nash Social Welfare (NSW), which maximizes the product of user utilities. This objective inherently penalizes inequality, ensuring that no single user's utility is driven to zero.

A critical technical hurdle in this setting is the lack of absolute rewards; feedback is purely relative (binary outcomes indicating which of two arms is preferred). To define utility in this relative setting, the authors assume the existence of a Condorcet winner for each user (an arm that beats every other arm with probability $>0.5$). User utility is then defined as a score derived from the probability of an arm beating that user's specific Condorcet winner.

Methodology

Theoretical Framework

The authors formalize the problem by defining a scoring function $s_d(i) = 2P_{d, i, a^*_d}$, where $a^*_d$ is the Condorcet winner for user $d$. The utility of a policy $\pi$ for user $d$ is the expected score $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$. The global objective is the Nash Social Welfare:
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
The goal is to minimize the expected cumulative regret relative to the optimal policy $\pi^*$ that maximizes this product.

Hardness Analysis

The paper establishes a fundamental regret lower bound of $\Omega(T^{2/3} \min(K, D)^{1/3})$. This result demonstrates that the requirement to maximize NSW among users with conflicting Condorcet winners introduces significant hardness compared to standard dueling bandits (which typically achieve $O(\log T)$ regret). The difficulty arises because the algorithm must play "bad" Condorcet winners (optimal for one user but yielding near-zero utility for others) to distinguish them from "good" winners, creating a trade-off between exploration costs and instantaneous regret.

Algorithms

Two algorithms are proposed to achieve this objective, both incorporating a Condorcet winner identification phase:

1. Fair-Explore-Then-Commit (Fair-ETC):

   • Phase 1 (Identification): Uses a modified Dvoretzky-Kiefer-Wolfowitz Tournament (DKWT) algorithm to identify the set of Condorcet winners $\hat{A}^*$ for all $D$ users. This phase leverages shared interactions to update empirical margins for all users simultaneously.
   • Phase 2 (Exploration): Estimates the scores of all arms relative to the identified Condorcet winners.
   • Phase 3 (Commitment): Computes the policy $\hat{\pi}$ that maximizes the empirical NSW and commits to it for the remainder of the horizon.

2. Fair-$\epsilon$-Greedy:

   • This algorithm interleaves exploration and exploitation throughout the horizon.
   • It begins with the same Condorcet winner identification phase.
   • At each step $t$, with probability $\epsilon_t$, it explores by playing pairs involving the estimated Condorcet winners (using a round-robin schedule) to refine score estimates.
   • With probability $1-\epsilon_t$, it exploits by playing the policy that maximizes the current empirical NSW.
   • The exploration rate $\epsilon_t$ decays over time to ensure convergence.

Both algorithms are proven to achieve a regret upper bound of $\tilde{O}(T^{2/3})$, matching the lower bound's dependence on the time horizon $T$ up to logarithmic factors.

Key Contributions

1. Problem Formulation: The first formalization of the Fair Multi-User Dueling Bandit problem, modeling distinct user utilities based on individual Condorcet winners and adopting NSW as the fairness objective.
2. Regret Lower Bound: The derivation of a regret lower bound of $\Omega(T^{2/3} \min(K, D)^{1/3})$, which the authors claim is the first result quantifying the cost of fairness in dueling bandits with heterogeneous preferences.
3. Algorithmic Solutions: The proposal of Fair-ETC and Fair-$\epsilon$-Greedy algorithms, accompanied by theoretical regret upper bounds that match the lower bound's dependence on $T$.
4. Empirical Validation: Extensive simulations demonstrating that the proposed algorithms outperform utilitarian baselines in fairness metrics (Gini coefficient, minimum user welfare) while maintaining competitive cumulative regret.

Experimental Results

The authors evaluated their algorithms on both randomly generated preferences and real-world data (the Sushi dataset, clustered into macroscopic users).

• Random Preferences: Across various configurations of users ($D$) and arms ($K$), both Fair-ETC and Fair-$\epsilon$-Greedy demonstrated sublinear regret, consistently outperforming utilitarian baselines and a uniform-over-users baseline.
• Fairness Metrics: The proposed algorithms achieved the highest Nash Social Welfare and significantly lower Gini coefficients compared to utilitarian approaches. They also maintained higher minimum user welfare, indicating better protection for minority preferences.
• Clustered Preferences: In scenarios with distinct majority and minority clusters (simulating polarized preferences), utilitarian algorithms favored the majority, leading to high inequality. The proposed fair algorithms successfully balanced interests, maintaining low Gini coefficients and high minimum welfare.
• Sushi Dataset: On real-world data, the proposed methods achieved the lowest cumulative regret in both $D=5$ and $D=10$ cluster settings. While a uniform baseline showed slightly better fairness in the highly fragmented $D=10$ case, it suffered from vastly inferior regret.

Significance and Claims

The paper claims to be the first work to quantify the cost of fairness in dueling bandits with heterogeneous preferences, establishing a fundamental regret lower bound of $\Omega(T^{2/3})$. The authors position their work as a necessary step toward human-centric machine learning, where optimizing for average preference is insufficient and potentially harmful to minority groups.

By integrating the Nash Social Welfare objective into the dueling bandit framework, the work provides a theoretical and algorithmic foundation for learning policies that balance efficiency with fairness. The authors note that their approach is distinct from prior multi-agent bandit work (e.g., Hossain et al., 2021; Jones et al., 2023) because it operates in a relative preference setting rather than one with absolute rewards, requiring fundamentally different utility estimation techniques.

The paper concludes modestly, acknowledging that future work could extend this framework to contextual dueling bandits, continuous action spaces, and settings where the Condorcet winner assumption does not hold (potentially using Copeland or Borda scores).