Technical Summary: Price of Fairness in Bandits

Problem Definition

The paper addresses the stochastic multi-armed bandit (MAB) problem under a strictly fair welfare objective. In standard MAB settings, algorithms minimize cumulative average regret, treating early exploration as an amortized cost that may unfairly penalize early rounds (e.g., patients in a clinical trial). To address this, the authors study the generalized $p$-mean regret, defined for a sequence of ex-ante expected rewards $(m_1, \dots, m_T)$ as:
$$M_p(m_1, \dots, m_T) = \left( \frac{1}{T} \sum_{t=1}^T m_t^p \right)^{1/p}$$
The paper focuses on the strictly fair regime where $p < 0$. By setting $q = -p > 0$, the objective becomes the $(-q)$-mean, which heavily penalizes rounds with low expected rewards. Specifically, if any $m_t$ is close to zero, the welfare metric collapses. The core challenge is that standard exploration strategies (like uniform sampling) assign low probability to the optimal arm in early rounds, driving $m_t$ toward zero and incurring massive welfare losses that cannot be recovered by later rounds.

The authors investigate the minimax regret for this regime over the class of $\sigma$-sub-Gaussian distributions with non-negative means. The central question is: What is the intrinsic polynomial dependence on the number of arms $k$ for negative-power welfare, and how much of the existing $k^{(q+1)/2}$ dependence is due to algorithmic inefficiency versus information-theoretic necessity?

Methodology

1. Lower Bound Construction

To establish the fundamental limits, the authors employ a "needle-in-haystack" construction. They define a set of $k$ instances where exactly one arm has a positive mean $\mu$ and all others have mean 0.

• Information-Cost Inequality: The proof relies on a novel, algorithm-independent inequality (Lemma 4.7) that relates the cumulative cost of a fairness-sensitive objective to the rate of information acquisition.
• Mechanism: The negative-power objective penalizes low success probabilities ($s_t$) via a cost function $c(s) \approx s^{-q}$. To increase $s_t$ from the random guessing baseline ($1/k$) to a constant, the learner must accumulate mutual information about the optimal arm. However, information can only be gained when the optimal arm is pulled.
• Result: The authors prove that the cost of raising the success probability scales with the integral of the penalty function against the information requirement. This yields a lower bound of $\Omega(\sigma \sqrt{k^{\max(1,q)}/T})$. Crucially, for $q > 1$, the rate lifts from the classical $\sqrt{k/T}$ to $\sqrt{k^q/T}$, proving that the $k^{q/2}$ penalty is information-theoretically unavoidable.

2. Algorithm: UCB-HARE

To match this lower bound, the authors propose UCB-HARE (Harmonic Anchored Rank Exploration). This algorithm abandons the uniform exploration strategy used in prior work (e.g., Welfarist-UCB) in favor of a two-phase approach:

• Phase I: Preparation (Shielded Exploration):

  • Harmonic Schedule: Instead of pulling all arms uniformly, the algorithm explores arms based on a harmonic rank schedule. Arms are assigned a random rank $r \in [k]$, and the schedule pulls rank $r$ with frequency proportional to $1/r$. This ensures that higher-ranked arms (which are more likely to be the optimal arm or have positive means) are pulled more frequently early on.
  • Anchoring: The algorithm operates in 2-round blocks. One round is a "Scheduled Slot" for exploration, and the other is an "Auxiliary Slot." In the Auxiliary Slot, the algorithm pulls the arm with the highest Lower Confidence Bound (LCB). If this LCB is positive, that arm is certified as an anchor.
  • Safety: By pairing risky exploration with a safe anchor pull, the algorithm ensures the ex-ante reward $m_t$ never drops below a critical floor, preventing the welfare collapse associated with negative-power means.
  • Termination: Phase I ends once an anchor is found and all arms have been sufficiently sampled to shrink their confidence intervals.

• Phase II: Exploitation:

  • Once the stopping condition is met, the algorithm switches to standard UCB (Upper Confidence Bound) exploitation, leveraging the safety guarantees established in Phase I.

Key Contributions

1. Tight Minimax Characterization: The paper closes the gap between upper and lower bounds for the $(-q)$-mean regret.
   • Lower Bound: Proves $\Omega(\sigma \sqrt{k^{\max(1,q)}/T})$. For $q > 1$, this establishes that the dependence on $k$ is $k^{q/2}$, not $k^{(q+1)/2}$.
   • Upper Bound: Shows that UCB-HARE achieves $\tilde{O}(\sigma \sqrt{k^{\max(1,q)}/T})$, matching the lower bound up to logarithmic factors.
2. Information-Theoretic Necessity: The work demonstrates that the polynomial penalty $k^{q/2}$ for $q > 1$ is not an artifact of uniform exploration but a fundamental limit imposed by the inverse-power nature of the welfare function.
3. Algorithmic Innovation: Introduces UCB-HARE, which utilizes a harmonic rank schedule and dynamic anchoring to avoid the inefficiencies of uniform exploration. This allows the algorithm to secure a positive welfare floor quickly without waiting for global optimality.
4. General Information-Cost Principle: The authors derive a general lemma (Lemma 4.7) bounding the cumulative cost of any objective penalizing low success probabilities based on information acquisition rates, applicable beyond just bandit problems.

Results

• Regret Regimes:
  • For $0 < q \le 1$: The regret scales as $\tilde{O}(\sqrt{k/T})$, consistent with classical average regret.
  • For $q > 1$: The regret scales as $\tilde{O}(\sqrt{k^q/T})$. This represents a significant improvement over the previous best bound of $\tilde{O}(k^{(q+1)/2}/\sqrt{T})$ achieved by Welfarist-UCB.
• Experimental Validation:
  • Experiments on synthetic instances confirm that UCB-HARE outperforms Welfarist-UCB and Explore-Then-UCB.
  • The advantage of UCB-HARE grows as $q$ increases.
  • Analysis of the ex-ante reward sequence shows that UCB-HARE improves welfare in steps (as new anchors are discovered), whereas uniform exploration maintains a flat, low welfare floor until the optimal arm is identified.
  • In the "strongly fair" regime (large $q$), Welfarist-UCB's regret flattens at a high level determined by the uniform exploration floor ($\mu^*/k$), while UCB-HARE sustains improvement over a longer horizon.

Significance and Claims

The paper claims to resolve the open question regarding the price of strict fairness in bandit problems. It establishes that while fairness constraints (parameterized by $q$) inevitably increase the cost of learning, the penalty is strictly bounded by $k^{q/2}$ for $q > 1$.

The authors emphasize that:

1. Uniform exploration is suboptimal for strictly fair objectives because it unnecessarily suppresses the probability of the optimal arm, triggering the inverse-power penalty.
2. Efficient exploration is possible without sacrificing fairness guarantees by using a rank-based schedule and safety anchors.
3. The derived information-cost inequality provides a theoretical framework for understanding the trade-off between fairness and information acquisition in sequential decision-making, suggesting that the "price" of fairness is fundamentally tied to how quickly an agent can identify a non-zero reward source.

The work does not claim to solve all fairness problems in bandits but specifically characterizes the minimax limits for the generalized $p$-mean regret in the negative regime, providing both a theoretical lower bound and a matching algorithm.