TL;DR
This paper introduces $p$-mean regret, a flexible framework that bridges social choice theory and online learning to balance fairness and efficiency in stochastic multi-armed bandits. The authors propose a simple, two-phase algorithm (EXPLORE-THEN-UCB) that achieves optimal or novel regret bounds across the entire spectrum of fairness preferences, unifying previous specialized approaches like Nash regret under a single method.
What Problem Does This Paper Address?
Standard multi-armed bandit (MAB) algorithms are designed to maximize total cumulative rewards, which corresponds to a purely utilitarian objective. However, in real-world applications like healthcare allocation, personalized education, or distributing renewable energy resources, each "round" often represents a different human agent.
Maximizing the average reward can lead to highly unfair outcomes where early users are treated as mere test subjects who receive poor rewards so the algorithm can learn. While specific fairness metrics like Nash regret have been studied to address this, the field lacked a unified framework to smoothly tune the trade-off between maximizing total efficiency and ensuring equitable treatment across all rounds over time.
Methods
The authors introduce $p$-mean regret, which replaces the standard arithmetic mean of rewards with a generalized power mean parameterized by $p \le 1$.
To minimize this regret, they propose a surprisingly simple algorithm called EXPLORE-THEN-UCB. It operates in two distinct phases:
- Calibrated Uniform Exploration: For an initial period $\tilde{T}$, the algorithm samples arms uniformly at random to establish a baseline empirical mean for every arm.
- Standard UCB1: After round $\tilde{T}$, it switches entirely to the classic UCB1 algorithm.
The key innovation isn't a complex new confidence bound, but rather the realization that a carefully sized initial exploration phase, combined with a mild assumption that all arms have a non-zero minimum expected reward, is sufficient to overcome the fairness blind spots of standard UCB.
Datasets
The algorithm was evaluated using synthetic stochastic bandit instances with $k = 50$ arms across four distribution types:
- Bernoulli: Arm means chosen uniformly from $[0.005, 1)$.
- Triangular: Rewards drawn from a triangular distribution on $(0,1)$ with randomly selected modes.
- Beta: Parameters $\alpha_i, \beta_i$ chosen independently from $[0.005, 0.995)$.
- Uniform: Support intervals $[l_i, u_i]$ generated randomly.
Experiments were run for $T = 20,000$ rounds ($T = 100,000$ for Bernoulli) and averaged over 30 trials.
Key Insights and Ideas
- A Spectrum of Fairness: By adjusting $p$, algorithm designers can target specific ethical frameworks: $p=1$ yields traditional average regret (utilitarian), $p \to 0$ yields Nash regret (balancing equity and efficiency), and $p \to -\infty$ approaches Rawlsian egalitarianism (protecting the worst-off rounds).
- Simplicity Wins: Previous work argued that standard UCB fails miserably for fairness metrics like Nash regret, necessitating complex new algorithms (like Nash Confidence Bounds). This paper shows that standard UCB can work perfectly well if you simply give it a short, uniform head start.
- The Cost of Equity: For highly negative values of $p$ (strict fairness), the algorithm requires a shorter exploration phase to avoid harming early participants, revealing a fundamental tension between learning efficiency and immediate fairness.
Key Results
The theoretical regret bounds achieved by EXPLORE-THEN-UCB vary by the range of $p$, as summarized below:
- Positive and Nash Range ($0 < p \le 1$ and $p \to 0$): The algorithm achieves a regret scaling of $\tilde{O}(\sqrt{k/T})$, matching known minimax lower bounds up to logarithmic factors.
- Negative Range ($p < 0$): The paper establishes novel bounds that scale gracefully based on the strictness of the fairness parameter $|p|$.
- Empirical Performance: In simulations,
EUCBsignificantly outperformed standard UCB1 and the specialized Nash Confidence Bound (NCB) algorithm when $p$ was negative (e.g., $p = -0.5, -1, -2$), particularly on the Bernoulli dataset. Conversely, standard UCB1 performed best when $p$ was positive, where uniform exploration acts as a performance handicap.
Limitations and Future Work
- Positivity Assumption: The theoretical guarantees rely on the assumption that every arm must have a strictly positive minimum expected reward. While reasonable asymptotically, it may not hold in settings with completely dead or zero-reward arms.
- Known Time Horizon: The current exploration period $\tilde{T}$ depends on knowing the total time horizon $T$ in advance.
- Future Directions: The authors suggest extending $p$-mean regret to more complex bandit structures (such as linear and contextual bandits) and developing "anytime" variants that do not require knowing $T$ beforehand.
Summary updated