Stochastic Multi-objective Bandits
In multi-objective bandits, each arm’s reward is a vector rather than a scalar, and performance is measured by Pareto regret. Whether the multi-objective setting is fundamentally harder than the classical one has been an open question in the stochastic regime.
In this work (joint with Mengfan Xu), we show that Pareto regret is governed by the largest objective-wise suboptimality gap g†, so the multi-objective problem is surprisingly no harder than the single-objective one. Our algorithm keeps upper and lower confidence-bound estimators for every arm-objective pair, uses top-two races within each objective, and applies an uncertainty-greedy rule that steers exploration toward g†. It achieves O(log T / g†) Pareto regret with no dependence on the number of objectives, and a matching Ω(log T / g†) lower bound shows this is optimal.
Key contributions:
- Optimal upper and lower Pareto-regret bounds for stochastic multi-objective bandits
- An efficient algorithm with order-of-magnitude empirical regret improvements on synthetic and real datasets
- Evidence of a fairness–hardness tradeoff that has no single-objective analogue
Our follow-up studies the adversarial setting.