Improved Algorithms for Nash Welfare in Linear Bandits

AI summary

Overview

Research area: Fairness-aware sequential decision making, specifically Nash Social Welfare objectives in stochastic linear bandits (a machine learning / online learning subfield).

Technical level: Advanced. The paper assumes familiarity with linear bandit theory, sub-Gaussian concentration, D-optimal design, the John ellipsoid, and power-mean welfare functions.

Scope in one sentence: The paper resolves a stated open problem by giving the first order-optimal Nash regret bound for linear bandits, and introduces and analyzes a generalized "p-means regret" objective via a generic meta-algorithm called FairLinBandit.

What This Paper Is About

Standard bandit algorithms optimize the arithmetic mean of rewards, which can leave some agents (e.g., patients, users, resources) with almost nothing as long as total utility is high. Nash regret, based on the geometric mean of expected rewards, penalizes such disparities, but the only prior analysis for linear bandits (Sawarni et al., 2023) had a suboptimal dependence on the ambient dimension d, scaling as Õ(d^{5/4}/√T) against a known Ω(d/√T) lower bound. This paper's goal is to close that gap and to extend the fairness framework to the more general p-means regret, which interpolates between fully fairness-oriented (small or negative p) and fully utility-oriented (large p) objectives.

Key Contributions

1. Resolves the open problem of Sawarni et al. (2023). The authors introduce FairLinBandit, a meta-algorithm achieving order-optimal Nash regret O(σ d log T / √T), improving on the previous Õ(d^{5/4}/√T) and matching the Ω(d/√T) lower bound of Dani et al. (2008) up to polylogarithmic factors.

2. New analytical technique: data-adaptive stopping. Prior Nash regret analysis required reward-estimate-dependent confidence intervals (Nash confidence bounds) and restrictive multiplicative concentration inequalities, which caused the d^{5/4} bottleneck. FairLinBandit instead uses a novel variable-length exploration phase with a data-adaptive termination rule, permitting UCB-style, estimate-independent confidence intervals.

3. Initiates the study of p-means regret in linear bandits. The paper is, to the authors' knowledge, the first to study p-means regret minimization in linear bandits, proving sublinear regret for the entire range of p and showing Nash regret is the special case p = 0.

4. A generic reduction framework plus empirical validation. FairLinBandit works as a meta-algorithm on top of any optimistic linear bandit strategy; the authors instantiate it with Linear Phased Elimination (LinPE) and Linear UCB (LinUCB), and test both on instances derived from MSLR-WEB10K and Yahoo! Learning to Rank Challenge datasets, reporting consistent improvements over the LinNash baseline of Sawarni et al. (2023).

Main Findings

• Order-optimal Nash regret: Theorem 4.1 states that under Assumption 2.1, FairLinBandit instantiated with either LinPE or LinUCB (with regularizer α = O(1)) achieves NR_T = O(σ d log T / √T). This matches the Ω(d/√T) lower bound (Dani et al., 2008) up to polylogarithmic factors.

• p-means regret bound: Theorem 4.2 gives R_T^p = O(σ d log T / √T) for p ≥ 0, and R_T^p = O((σ d log T / √T) · d^{|p|/2} · max(1,|p|)) for p < 0.

• Fairness–performance trade-off: For p ∈ [0,1] the bound is order-optimal. For p ∈ [−1, 0) the worst-case bound scales as Õ(d^{3/2}/√T). For p < −1 the bound grows exponentially with |p|, and becomes vacuous as p → −∞ unless T ≥ Ω(p² d^{|p|}). The authors describe this as an intrinsic "no free lunch" phenomenon: stronger fairness requires a substantially longer horizon. Whether the bound is tight for p < −1 is left open.

• Comparison with the finite-armed special case: Treating a k-armed bandit as a d = k linear bandit, the best known p-means bounds are Õ(√(k/T)) for p ≥ 0 and Õ(√(k/T) · k^{|p|/2} · max{1,|p|}) for p < 0 (Sarkar et al., 2025b). The paper's bounds carry an additional √k factor, which the authors attribute to the more general infinite-armed setting where rewards are coupled through a common θ*.

• Broader reward model: Unlike prior work, the analysis does not require non-negative realized rewards and applies to sub-Gaussian reward distributions rather than only non-negative (e.g., sub-Poisson) rewards. Non-negative expected rewards ⟨x, θ*⟩ ≥ 0 are still assumed, since the geometric and power means require it.

• Plug-in flexibility: The reduction framework extends to other algorithms if an arm-independent confidence width bound, a time-uniform per-round regret bound, and a modified stopping rule are available. LinTS yields a larger Phase I length Θ̃(σ²d³/⟨θ*,x*⟩²) and suboptimal Nash regret Õ(σ d^{3/2}/√T); SupLinUCB in the finite-arm case yields Nash regret O(σ √(d/T) log(kT)), matching a known lower bound. The authors conjecture this could extend to non-linear rewards such as logistic.

• Not reported in the provided content: Specific experimental numbers, regret values, dataset sizes, and figures are not included in the truncated text. The proof sketch section is cut off immediately after defining the two good events 𝒢₁ and 𝒢₂.

Methodology in Plain English

The algorithm has two phases and sits on top of any existing linear bandit algorithm.

Phase I (exploration and warm-up): The learner alternates between two strategies with equal probability (a fair coin flip at each round). One strategy pulls arms according to a D-optimal design — a fixed mix of at most d(d+1)/2 arms chosen to maximize information about the unknown parameter θ*, implemented round-robin so the empirical design matrix V satisfies V ⪰ (T̃/3)U(λ*). The other strategy samples arms from a distribution ρ derived from the John ellipsoid of the action set's convex hull; by Carathéodory's theorem the ellipsoid center can be written as a convex combination of d+1 arms, guaranteeing an expected reward of at least ⟨x*, θ*⟩/(d+1). The purpose of this second strategy is to keep the geometric mean of rewards from collapsing toward zero.

The key innovation — a data-adaptive stopping rule: Instead of running Phase I for a fixed number of rounds, Phase I continues while the current time t and the least-squares estimate θ̂ satisfy an inequality (Equation 1) that involves 48σ²d²log T and 900p²σ²d²log T in the numerators. Because the D-optimal design round-robin scheme normally needs to know the exploration length in advance, the authors use a doubling schedule: Phase I starts with ⌈72 log T⌉ rounds and proceeds in epochs of geometrically increasing length, never restarting, always accumulating the sufficient statistics V and s. The stopping condition is checked only at the end of each epoch. The result is that Phase I terminates after τ = Θ̃(d²/⟨θ*, x*⟩²) rounds — long enough that the UCB interval width Õ(d/√τ) does not exceed ⟨x*, θ*⟩, which is exactly the concern that previously forced the use of the looser, reward-dependent Nash confidence bounds.

Phase II (exploit): The remaining T − τ rounds are handled by a standard linear bandit algorithm initialized with Phase I's statistics. With LinUCB, arms are selected using the standard optimistic rule ⟨x, θ̂⟩ + β‖x‖ over a confidence ellipsoid with radius roughly O(σ√(d log t)). With LinPE, the algorithm first restricts to a surviving set of arms within 8√(d²σ² log T / τ) of the empirical leader, then runs episodic D-optimal designs on the shrinking set with doubling episode lengths. LinUCB updates estimates every round and typically converges faster; LinPE discards history each episode but has lower time complexity.

For p ≥ −1, the fairness parameter is normalized to p = 1 in the stopping rule, because the Phase I stopping condition turns out to be independent of p in that regime.

Why This Matters

Impact on research: The paper closes an explicitly posed open question, replaces a dimension-dependent analytical bottleneck (d^{5/4}) with an order-optimal bound, and opens a new subfield — p-means regret in linear bandits — with a reusable reduction framework that can host other optimistic algorithms. It also relaxes the reward assumptions from non-negative realized rewards to sub-Gaussian rewards, which the authors argue is more realistic.

Real-world applications:

• Clinical trials, where a policy allocating nearly all resources to one patient group with slightly higher expected reward may look fine under arithmetic regret but is unacceptable in practice.
• Resource allocation across individuals or regions, where the non-negativity assumption on expected rewards naturally matches pre-screened beneficial interventions.
• Recommendation and ranking systems, given the use of MSLR-WEB10K and Yahoo! Learning to Rank Challenge data in the experiments.
• Settings with adverse outcomes, since negative realized rewards (e.g., a treatment that helps on average but causes side effects) are now permitted.

Industry relevance: Any deployed sequential decision system balancing aggregate utility against equitable treatment of users — advertising, content recommendation, healthcare triage, or allocation of compute/bandwidth — could in principle use the FairLinBandit meta-algorithm, since it wraps around existing production linear bandit methods. The p parameter gives practitioners an explicit dial for the fairness–utility trade-off, and the negative-p results warn that demanding strong fairness guarantees requires correspondingly longer deployment horizons.

Future Directions

1. Tightness for p < −1. The paper explicitly states that whether the regret upper bound is tight in the p < −1 regime remains an open question.

2. Closing the √k gap. The paper's bounds carry an extra √k factor relative to the finite-armed results of Sarkar et al. (2025b); the authors attribute this to reward coupling through θ* in the infinite-armed setting, but it is not shown to be unavoidable.

3. Extending beyond linear rewards. The authors conjecture that the reduction framework could be extended to more general non-linear reward models such as logistic rewards.

4. Plug-in algorithms and stopping rules. The framework requires a confidence-width bound, a per-round regret bound, and a corresponding modification of the stopping condition; systematically characterizing which algorithms admit order-optimal Nash regret through this route (and which, like LinTS, do not) is a natural next step.

Target Audience

Researchers and graduate students in online learning, bandit theory, and algorithmic fairness; theoretical machine learning practitioners interested in welfare-based objectives; and applied scientists working on fair sequential decision systems (clinical trials, resource allocation, ranking, recommendation) who want a principled generalization of Nash regret with a tunable fairness parameter. Reading requires comfort with linear bandit regret analysis and concentration inequalities.

Authors’ abstract

Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension $d$, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of $p$-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear $p$-means regret for the entire range of $p$. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.