Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?

Multi-objective bandits have attracted increasing attention for their broad applicability, with $d$-dimensional reward vectors inducing Pareto regret. There has been a subtle debate over whether this added structure makes the problem fundamentally harder than single-objective bandits. We answer this by showing that, in terms of Pareto regret, it is surprisingly no harder: Pareto regret scales inversely with $g^{†}$, the largest objective-wise suboptimality gap, and thus matches the smallest objective-wise classical regret. We formalize this idea via a novel method with upper and lower confidence-bound estimators for every arm-objective pair. It uses top-two races to compare arms within each objective and an uncertainty-greedy rule to allocate exploration toward the largest objective-wise gap $g^{†}$, until the corresponding Pareto-optimal arm is committed to. We prove that it achieves Pareto regret of $O(\text{nicefrac}\log T{g}^{†})$, where $T$ is the horizon, with \emph{no dependence on $d$}. A matching lower bound of $\mathrm{\Omega }(\text{nicefrac}\log T{g}^{†})$ implies optimality. We evaluate the method on synthetic and real-world datasets, confirming the theory and achieving order-of-magnitude reductions in Pareto regret over baselines. Real-world results further show that our method commits to a Pareto optimal arm, possibly at the cost of empirical fairness, suggesting a potential hardness absent in single-objective bandits.