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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 20 references that are in the map.
- First posted on arXiv 8 Apr 2026.

## Builds on (most cited first, 4 of 4)

- [KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems](https://mlsanity.com/paper/2202.10842/) (2022)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Multi-objective Contextual Bandit Problem with Similarity Information](https://mlsanity.com/paper/1803.04015/) (2018)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)

## Abstract (arXiv)

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^dagger), 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^dagger), until the corresponding Pareto-optimal arm is committed to. We prove that it achieves Pareto regret of (O(nicefraclog Tg^dagger)), where (T) is the horizon, with no dependence on (d). A matching lower bound of (Omega(nicefraclog Tg^dagger)) 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.