Optimal Scalarizations for Sublinear Hypervolume Regret
This provides a theoretically-grounded solution for multiobjective optimization practitioners who need efficient exploration of diverse objectives, though it builds incrementally on scalarization methods.
The paper tackles the problem of exploring concave regions of the Pareto frontier in multiobjective optimization by developing non-linear scalarizations, achieving an optimal sublinear hypervolume regret bound of O(T^{-1/k}) and improved regret bounds for multiobjective stochastic linear bandits.
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 $\tilde{O}( d T^{-1/2} + T^{-1/k})$, removing unnecessary $\text{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.