Improved Algorithms for Nash Welfare in Linear Bandits

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.

Many learning systems make decisions by trying different options over time and using the results to improve future choices. For example, such a system might choose treatments, recommendations, or resource allocations. Standard methods usually focus on getting the best average outcome, but this can hide unfair behavior: some people or cases may receive very poor outcomes as long as the overall average remains high. This paper studies how to make these learning systems fairer. We focus on settings with many possible choices, where each choice has known features but its true benefit is initially unknown. We design a new method that first explores carefully to learn about the choices while avoiding options that could lead to very poor outcomes. After this initial stage, the method can use standard learning techniques more safely and effectively. Our results show that this approach achieves strong fairness guarantees without sacrificing statistical efficiency. It improves over previous methods for the same problem and also handles a broader family of fairness goals, allowing users to choose how strongly the system should prioritize protecting worse-off individuals versus improving overall performance. Experiments on datasets derived from real-world ranking tasks support the theoretical findings.