p-Mean Regret for Stochastic Bandits

Anand Krishna, Philips George John, Adarsh Barik, Vincent Y. F. Tan

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:

  1. 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.
  2. 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:

Table 1: Summary of results
  • 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, EUCB significantly 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

Abstract

In this work, we extend the concept of the $p$-mean welfare objective from social choice theory (Moulin 2004) to study $p$-mean regret in stochastic multi-armed bandit problems. The $p$-mean regret, defined as the difference between the optimal mean among the arms and the $p$-mean of the expected rewards, offers a flexible framework for evaluating bandit algorithms, enabling algorithm designers to balance fairness and efficiency by adjusting the parameter $p$. Our framework encompasses both average cumulative regret and Nash regret as special cases. We introduce a simple, unified UCB-based algorithm (Explore-Then-UCB) that achieves novel $p$-mean regret bounds. Our algorithm consists of two phases: a carefully calibrated uniform exploration phase to initialize sample means, followed by the UCB1 algorithm of Auer, Cesa-Bianchi, and Fischer (2002). Under mild assumptions, we prove that our algorithm achieves a $p$-mean regret bound of $\tilde{O}\left(\sqrt{\frac{k}{T^{\frac{1}{2|p|}}}}\right)$ for all $p \leq -1$, where $k$ represents the number of arms and $T$ the time horizon. When $-1<p<0$, we achieve a regret bound of $\tilde{O}\left(\sqrt{\frac{k^{1.5}}{T^{\frac{1}{2}}}}\right)$. For the range $0< p \leq 1$, we achieve a $p$-mean regret scaling as $\tilde{O}\left(\sqrt{\frac{k}{T}}\right)$, which matches the previously established lower bound up to logarithmic factors (Auer et al. 1995). This result stems from the fact that the $p$-mean regret of any algorithm is at least its average cumulative regret for $p \leq 1$. In the case of Nash regret (the limit as $p$ approaches zero), our unified approach differs from prior work (Barman et al. 2023), which requires a new Nash Confidence Bound algorithm. Notably, we achieve the same regret bound up to constant factors using our more general method.
BibTeX
@inproceedings{krishna2025p,
  author = {Anand Krishna and Philips George John and Adarsh Barik and Vincent Y. F. Tan},
  title = {{p-Mean Regret for Stochastic Bandits}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i17.33976},
}
Figure