Taming Pareto Regret with Marginal Regret in Stochastic Multi-objective Bandits

Stochastic multi-objective bandits generalize bandits to $d$-dimensional reward vectors. Performance is commonly measured by Pareto regret, which sums the Pareto gaps of the selected arms, where each gap is the smallest uniform lift that makes the arm nondominated. As this measure is defined through the Pareto front, existing methods typically minimize it by estimating the front and thus inherit the difficulties of doing so. However, we find a direct link between Pareto regret and marginal regret in bandits that bypasses Pareto-front estimation. Beyond this, under regularity conditions, it even reaches the smaller scale of marginal regret. We formalize this idea through a width-guided method that maintains upper and lower confidence bounds for each arm and objective, races the top two arms within each objective, and commits once an objective has a strictly separated unique winner. For bounded i.i.d. instances with largest objective-wise suboptimality gap $g^{†}>0$, the method achieves Pareto regret $O(K\log T/g^{†})$ over horizon $T$ with $K$ arms, with no explicit multiplicative dependence on $d$ in the leading gap-dependent term. We further construct an explicit subclass on which every uniformly good policy incurs $\Omega (K\log T/g^{†})$ regret asymptotically, establishing optimality. Experiments on synthetic and real-world datasets support the theory. Across the data families, our method reduces Pareto regret by orders of magnitude relative to the baselines. Moreover, these results empirically expose what Pareto regret omits: Pareto front recovery and fairness remain distinct goals and call for further study.