# Optimal Scalarizations for Sublinear Hypervolume Regret

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 45 references that are in the map.
- First posted on arXiv 6 Jul 2023.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Pareto Multi-Task Learning](https://mlsanity.com/paper/1912.12854/) (2019)
- [Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2006.05078/) (2020)
- [A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation](https://mlsanity.com/paper/1908.08342/) (2019)
- [A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations](https://mlsanity.com/paper/1805.12168/) (2018)
- [Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization](https://mlsanity.com/paper/2006.04655/) (2020)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Multi-Objective Generalized Linear Bandits](https://mlsanity.com/paper/1905.12879/) (2019)
- [Adaptive Metric Dimensionality Reduction](https://mlsanity.com/paper/1302.2752/) (2013)
- [Using Well-Understood Single-Objective Functions in Multiobjective Black-Box Optimization Test Suites](https://mlsanity.com/paper/1604.00359/) (2016)

## Built on by (most cited first, 7 of 7)

- [The Vizier Gaussian Process Bandit Algorithm](https://mlsanity.com/paper/2408.11527/) (2024)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [Thompson Sampling for Multi-Objective Linear Contextual Bandit](https://mlsanity.com/paper/2512.00930/) (2025)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection](https://mlsanity.com/paper/2607.26273/) (2026)
- [Converge Then Diversify: Decoupling Convergence and Diversity in Multi-Objective Bayesian Optimisation](https://mlsanity.com/paper/2609.13396/) (2026)
- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)

## Abstract (arXiv)

Scalarization is a general, parallizable technique that can be deployed in any multiobjective setting to reduce multiple objectives into one, yet some have dismissed this versatile approach because linear scalarizations cannot explore concave regions of the Pareto frontier. To that end, we aim to find simple non-linear scalarizations that provably explore a diverse set of k objectives on the Pareto frontier, as measured by the dominated hypervolume. We show that hypervolume scalarizations with uniformly random weights achieves an optimal sublinear hypervolume regret bound of O(T-1/k), with matching lower bounds that preclude any algorithm from doing better asymptotically. For the setting of multiobjective stochastic linear bandits, we utilize properties of hypervolume scalarizations to derive a novel non-Euclidean analysis to get regret bounds of tildeO( d T-1/2 + T-1/k), removing unnecessary poly(k) dependencies. We support our theory with strong empirical performance of using non-linear scalarizations that outperforms both their linear counterparts and other standard multiobjective algorithms in a variety of natural settings.