Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?
Published in arXiv preprint arXiv:2604.07096, 2026
Changkun Guan, Mengfan Xu. "Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?" arXiv preprint arXiv:2604.07096, 2026.
Do multiple objectives make stochastic bandits fundamentally harder? This paper shows that Pareto regret scales inversely with the largest objective-wise suboptimality gap and matches classical single-objective regret performance. The proposed algorithm pairs confidence-bound estimators with a top-two racing mechanism, achieving O(log T / g†) Pareto regret with no dependence on the number of objectives, and matching lower bounds confirm optimality. Experiments on synthetic and real datasets show order-of-magnitude regret improvements, while also revealing a potential fairness–hardness tradeoff absent in single-objective settings.
Our follow-up paper studies adversarial multi-objective bandits.