Papers › p-Mean Regret for Stochastic Bandits
p-Mean Regret for Stochastic Bandits
Anand Krishna, Philips George John, Adarsh Barik, Vincent Y. F. Tan
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 Õ(√(k/(T^(1/(2|p|))))) for all p ≤-1, where k represents the number of arms and T the time horizon. When -1<p<0, we achieve a regret bound of Õ(√((k^(1.5))/(T^(1/2)))). For the range 0< p ≤1, we achieve a p-mean regret scaling as Õ(√(k/T)), 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 ≤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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections