# Online Generalized-Mean Welfare Maximization: Achieving Near-Optimal Regret from Samples

arXiv: https://arxiv.org/abs/2602.10469 · HTML: https://mlsanity.com/paper/2602.10469/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2026.

## Abstract (arXiv)

We study online fair allocation of T sequentially arriving items among n agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defined as the p-mean of agents' time-averaged utilities, with p∈ (-∞, 1). We first consider the i.i.d. arrival model and show that the pure greedy algorithm -- which myopically chooses the welfare-maximizing integral allocation -- achieves widetildeO(1/T) average regret. Importantly, in contrast to prior work, our algorithm does not require distributional knowledge and achieves the optimal regret rate using only the online samples. We then go beyond i.i.d. arrivals and investigate a nonstationary model with time-varying independent distributions. In the absence of additional data about the distributions, it is known that every online algorithm must suffer Omega(1) average regret. We show that only a single historical sample from each distribution is sufficient to recover the optimal widetildeO(1/T) average regret rate, even in the face of arbitrary non-stationarity. Our algorithms are based on the re-solving paradigm: they assume that the remaining items will be the ones seen historically in those periods and solve the resulting welfare-maximization problem to determine the decision in every period. Finally, we also account for distribution shifts that may distort the fidelity of historical samples and show that the performance of our re-solving algorithms is robust to such shifts.