Optimal Scalarizations for Sublinear Hypervolume Regret

Authors: richard  zhang
google  deepmind
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 07:13:11

Abstract: 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.

Main paper: 
 introduction: 
 Optimization objectives in modern AI systems are becoming more complex with many different components that must be combined to perform precise tradeoffs in machine learning models. Starting from standard ℓ p regularization objectives in regression problems [Kutner et al., 2005] to increasingly multi-component losses used in reinforcement learning [Sutton et al., 1998 ] and deep learning [LeCun et al., 2015] , many of these single-objective problems are phrased as a scalarized form of an inherently k-objective problem.Scalarization Method. Practitioners often vary the weights of the scalarization method, with the main goal of exploring the entire Pareto frontier, which is the set of optimal objectives that cannot be simultaneously improved. First, one chooses some weights λ ∈ R k and scalarization functions s λ (y) : R k → R that convert k multiple objectives F (a) := (f 1 (a), ..., f k (a)) over some parameter space a ∈ A ⊆ R d into a single-objective scalar. Optimization is then applied to this family of single-objective functions s λ (F (x)) for various λ and since we often choose s λ to be monotonically increasing in all coordinates, x λ = arg max a∈A s λ (F (a)) is on the Pareto frontier and the various choices of λ recovers an approximation to the Pareto frontier [Paria et al., 2018] .Due to its simplicity of use, many have turned to a heuristic-based scalarization strategy to pick the family of scalarizer and weights, which efficiently splits the multi-objective optimization into numerous single "scalarized" optimizations [Roijers et al., 2013] . Linear scalarizations with varying weights are often used in multi-objective optimization problems, such as in multi-objective reinforcement learning to combine task reward with the negative action norm [Abdolmaleki et al., 2021] or in RLHF to align responses with human preferences Ouyang et al. [2022] . However, the appeal of 38th Conference on Neural Information Processing Systems (NeurIPS 2024). using scalarizations in multiobjective optimization declined as linear scalarizations are shown to be provably incapable of exploring the full Pareto frontier [Boyd and Vandenberghe, 2004] .Beyond Linear Scalarization. To address this, some works have proposed piecewise linear scalarizations inspired by economics [Busa-Fekete et al., 2017] , while for multi-armed bandits, scalarized knowledge gradient methods empirically perform better with non-linear scalarizations [Yahyaa et al., 2014] . The classical Chebyshev scalarization has been shown to be effective in many settings, such as evolutionary strategies Qi et al. [2014] , Li et al. [2016] , general blackbox optimization [Kasimbeyli et al., 2019] or reinforcement learning Van Moffaert et al. [2013] . Other works have come up with novel scalarizations that perform better empirically in some settings [Aliano Filho et al., 2019 , Schmidt et al., 2019] . There also have been specific multi-objective algorithms tailored to specific settings such as ParEgo [Knowles, 2006] and MOEAD [Zhang and Li, 2007] for black-box optimization or multivariate iteration for reinforcement learning [Yang et al., 2019] . Furthermore, many adaptive reweighting strategies have been proposed in order to target or explore the full Pareto frontier, which have connections to gradient-based multi-objective optimization [Lin et al., 2019 , Abdolmaleki et al., 2021] . However these adaptive strategies are heuristic-driven and hard to compare, while understanding simple oblivious scalarizations remain very important especially in batched settings where optimizations are done heavily in parallel Gergel and Kozinov [2019] .Hypervolume Regret. To determine optimality, a natural and widely used metric to measure progress of an optimizer is the hypervolume indicator, which is the volume of the dominated portion of the Pareto set [Zitzler and Thiele, 1999] . The hypervolume metric has become a gold standard because it has strict Pareto compliance meaning that if set A is a subset of B and B has at least one Pareto point not in A, then the hypervolume of B is greater than that of A. Unsurprisingly, multiobjective optimizers often use hypervolume related metrics for progress tracking or acquisition function, such as the Expected Hypervolume Improvement (EHVI) or its differentiable counterpart [Daulton et al., 2020 , Hupkens et al., 2015] . Only recently has some works provide sub-linear hypervolume regret bounds which guarantees convergence to the full Pareto frontier; however, they are exponential in k and its analysis only applies to a specially tailored algorithm that requires an unrealistic classification step [Zuluaga et al., 2013] . We draw inspiration on work by [Golovin and Zhang, 2020 ] that introduces random hypervolume scalarizations but their work does not consider the finite-sample regime and their regret bounds are in the blackbox setting, where the convergence rate quantifies the statistical convergence of the Pareto frontier estimation.We show, perhaps surprisingly, that a simple ensemble of nonlinear scalarizations, known as Hypervolume scalarizations, are theoretically optimal to minimize hypervolume regret and are empirically competitive for general multiobjective optimization. Intuitively, we quantify how fast scalarizations can approximate the Pareto frontier under finite samples even with perfect knowledge of the Pareto frontier, which is the white-box setting. Specifically, as the hypervolume scalarization has sharp level curves, they naturally allow for the targeting of a specific part of the Pareto frontier, without any assumptions on the Pareto set or the need for adaptively changing weights. Additionally, we can oblivously explore the Pareto frontier by choosing T maximizers of randomly weighted Hypervolume scalarizations and achieve a sublinear hypervolume regret rate of O(T -1/k ), where T is the number of points sampled.Sublinear Hypervolume Regret. Given any set of objectives Y that are explicitly provided, our goal is to choose points on the Pareto frontier in a way to maximize the hypervolume. In this white-box setting, we introduce the notion of the hypervolume regret convergence rate, which is both a function of both the scalarization and the weight distribution, and show that the maxima of Hypervolume scalarization with uniform i.i.d. weights enjoy O(T -1/k ) hypervolume regret (see Theorem 7). In fact, our derived regret rate of the Hypervolume scalarization holds for all frontiers, regardless of the inherent multiobjective function F or the underlying optimizer. Therefore, we emphasize that analyzing these model-agnostic rates can be a general theoretical tool to compare and analyze the effectiveness of proposed multiobjective algorithms. Although many scalarizers will search the entire Pareto frontier as T → ∞, the rate at which this convergence occurs can differ significantly, implying that this framework paves the road for a theoretical standard by which to judge the effectiveness of advanced strategies, such as adaptively weighted scalarizations.Lower bounds. On the other hand, we show surprisingly that no multiobjective algorithm, whether oblivious or adaptive, can beat the optimal hypervolume regret rates of applying single-objective optimization with the hypervolume scalarization. To accomplish this, we prove novel lower bounds showing one cannot hope for a better convergence rate due to the exponential nature of our regret, for any set of T points. Specifically, we show that the hypervolume regret of any algorithm after T actions is at least Ω(T -1/k ), demonstrating the necessity of the O(T -1/k ) term up to small constants in the denominator. As a corollary, we leverage the sublinear regret properties of hypervolume scalarization to transfer our lower bounds to the more general setting of scalarized Bayes regret. Together, we demonstrate that for general multiobjective optimzation, finding maximas of the hypervolume scalarizations with a uniform weight distribution optimally finds the Pareto frontier asymptotically. Theorem 1 (Informal Restatement of Theorem 7 and Theorem 8). Let Y T = {y 1 , ..., y T } be a set of T points in R k such that y i ∈ arg max y∈Y s HV λi (y) with λ i ∼ S + randomly drawn i.i.d. from an uniform distribution and s HV are hypervolume scalarizations. Then, the hypervolume regret satisfiesHV(Y ⋆ ) -HV(Y T ) = O(T -1 k )where Y ⋆ is the Pareto frontier and HV is the hypervolume function. Furthermore, any algorithm for choosing these T points must suffer hypervolume regret of at least Ω(T -1 k ).Scalarized Algorithm for Linear Bandit. Next, we use a novel non-Euclidean analysis to prove improved hypervolume regret bounds for our theoretical toy model: the classic stochastic linear bandit setting. For any scalarization and weight distribution, we propose a new scalarized algorithm (Algorithm 1) for multiobjective stochastic linear bandit that combines uniform exploration and exploitation via an UCB approach to provably obtain scalarized Bayes regret bounds, which we then combine with the hypervolume scalarization to derive optimal hypervolume regret bounds. Specifically, for any scalarization s λ , we show that our algorithm in the linear bandit setting has a scalarized Bayes regret bound of O(L p k 1/p dT -1/2 + T -1/k ), where L p is the Lipschitz constant of the s λ (•) in the ℓ p norm. Finally, by using hypervolume scalarizations and exploiting their ℓ ∞smoothness, we completely remove the dependence on the number of objectives, k, which had a polynomial dependence in previous regret bound given by Golovin and Zhang [2020] .Theorem 2 (Informal Restatement of Theorem 11). For the multiobjective linear bandit problem, let A T ⊆ A be the actions generated by T rounds of Algorithm 1, then our hypervolume regret is bounded by:HV z (Θ ⋆ A) -HV z (Θ ⋆ A T ) ≤ O(dT -1 2 + T -1 k )Experiments. Guided by our theoretical analysis, we empirically evaluate a diverse combination of scalarizations and weight distributions in multiple natural settings. First, we consider a synthetic optimization that is inspired by our theoretical derivation of hypervolume regret when the entire Pareto front is known and analytically given. Thus we can explicitly calculate hypervolume regret as a function of the number of Pareto points chosen and compare the regret convergence rates of multiple scalarizations with the uniform S + distribution with k = 3 objectives, for easy visualization. This is important since when k = 2, we show that the Chebyshev and Hypervolume scalarizations are in fact equivalent.In our setup, we consider synthetic combinations of concave, convex, and concave/convex Pareto frontiers in each dimension. As expected, non-linear Hypervolume and Chebyshev scalarizations enjoy fast sublinear convergence, while the performance of the Linear scalarization consistently lacks behind, surprisingly even for convex Pareto frontiers. We observe that generally the Hypervolume scalarization does better on concave Pareto frontiers and on some convex-concave frontiers, while the Chebyshev distribution have faster hypervolume convergence in certain convex regimes.For multiobjective linear bandits, our experiments show that for many settings, despite having a convex Pareto frontier, applying linear or Chebyshev scalarizations naively with various weight distributions leads to suboptimal hypervolume progress, especially when the number of objective increase to exceed k ≥ 5. This is because the non-uniform curvature of the Pareto frontier, exaggerated by the curse of dimensionality and combined with a stationary weight distribution, hinders uniform progress in exploring the frontier. Although one can possibly adapt the weight distribution to the varying curvature of the Pareto frontier when it is convex, the use of simple non-linear scalarizations allow for fast parallelization and are theoretically sound.For general multiobjective optimization, we perform empirical comparisons on BBOB benchmarks for bi-ojective functions in a bayesian optimization setting, using classical Gaussian Process models [Williams and Rasmussen, 2006] . When comparing EHVI with hypervolume scalarization approaches, we find that EHVI tends to limit its hypervolume gain by over-focusing on the central portion of the Pareto frontier, whereas the hypervolume scalarization encourages a diverse exploration of the extreme ends.We summarize our contributions as follows:• Show that hypervolume scalarizations optimizes for the full Pareto frontier and enjoys sublinear hypervolume regret bounds of O(T -1/k ), a theoretical measure of characterizing scalarization effectiveness in the white-box setting.• Establish a tight lower bound on the hypervolume regret for any algorithm and Bayes regret of Ω(T -1/k ) by a packing argument on the Pareto set.• Introduce optimization algorithm for multiobjective linear bandits that achieves improved O(dT -1/2 + T -1/k ) hypervolume regret via a novel non-Euclidean regret analysis and metric entropy bounds.• Empirically justify the adoption of hypervolume scalarizations for finding a diverse Pareto frontier in general multiobjective optimization via synthetic, linear bandit, and blackbox optimization benchmarks. 
problem setting and notation: 
 For a scalarization functions λ (x), s λ is L p -Lipschitz with respect to x in the ℓ p norm on X ⊆ R d if for x 1 , x 2 ∈ X , |s λ (x 1 ) -s λ (x 2 )| ≤ L p ∥x 1 -x 2 ∥ p ,and L λ analogously for λ in the Euclidean norm. We let S k-1+ = {y ∈ R k | ∥y∥ = 1, y > 0} be the sphere in the positive orthant and by abuse of notation, we also let y ∼ S k-1 + denote that y is drawn uniformly on S k-1 + . Our usual settings of the weight distribution D = S k-1 + will be uniform, unless otherwise stated.For two outputs y, z ∈ Y ⊆ R k , we say that y is Pareto-dominated by z if y ≤ z and there exists j such that y j < z j , where y ≤ z is defined for vectors element-wise. A point is Paretooptimal if no point in the output space Y can dominates it. Let Y ⋆ denote the set of Pareto-optimal points (objectives) in Y, which is also known as the Pareto frontier. Our main progress metrics for multiobjective optimization is given by the standard hypervolume indicator. For S ⊆ R k compact, let vol(S) be the regular hypervolume of S with respect to the standard Lebesgue measure.Definition 3. For a set Y of points in R k , we define the (dominated) hypervolume indicator of Y with respect to reference point z as:HV z (Y) = vol({x | x ≥ z, x is dominated by some y ∈ Y})We can formally phrase our optimization objective as trying to rapidly minimize the hypervolume (psuedo-)regret. Let A be our action space and for some general multi-objective function F , let Y be the image of A under F . Let A T ∈ R T ×d be any matrix of T actions and let Y T = F (A T ) ∈ R T ×k be the k objectives corresponding. Then, the hypervolume regret of actions A T , with respect to the reference point z, is given by:Hypervolume-Regret(A T ) = HV z (Y ⋆ ) -HV z (Y T )which is 0 for all z if and only if Y T contains all unique points in Y ⋆ .For various scalarizations and weight distributions, an related measure of progress that attempts to capture the requirement of diversity in the Pareto front is scalarized Bayes regret for some scalarization function s λ . For some fixed scalarization with weights λ, s λ : R k → R, we can define the instantaneous scalarized (psuedo-)regret as r(s λ , a t ) = max a∈A s λ (F (a)) -s λ (F (a t )). To capture diversity and progress, we will vary λ ∼ D according to some distribution of non-negative weight vectors and define regret with respect with respect to all past actions A t . Specifically, we define the (scalarized) Bayes regret with respect to a set of actions A t to be:BR(s λ , A t ) = E λ∼D [max a∈A s λ (F (a)) -max a∈At s λ (F (a))] = E λ∼D [ min a∈At r(s λ , a)]Unlike previous notions of Bayes regret in literature, we are actually calculating the Bayes regret of a reward function that is maximized with respect to an entire set of actions A t . Specifically, by maximizing over all previous actions, this captures the notion that during multi-objective optimization our Pareto set is always expanding. We will see later that this novel definition is the right one, as it generalizes to the multi-objective setting in the form of hypervolume regret.For multiobjective optimization, we generally only consider monotone scalarizers that have the property that if y > z, then s λ (y) > s λ (z) for all λ. Note this guarantees that an optimal solution to the scalarized optimization is on the Pareto frontier. A common scalarization used widely in practice is the linear scalarization: s LIN λ (y) = λ ⊤ y for some chosen positive weights λ ∈ R k . By Lagrange duality and hyperplane separation of convex sets, one can show that any convex Pareto frontier can be characterized fully by an optimal solution for some weight settings.However, linear scalarizations cannot recover the non-convex regions of Pareto fronts since the linear level curves can only be tangent to the Pareto front in the protruding convex regions (see Figure 1 ). To overcome this drawback, another scalarization that is proposed is the Chebyshev scalarization: s CS λ (y) = min Right: The dotted red lines represent the level curves of the hypervolume scalarization with λ = v, discovering b, whereas the linear scalarization would prefer a or c. Furthermore, the optima is exactly the Pareto point that is in the direction of v. 
hypervolume scalarizations: 
 In this section, we show the utility and optimality of a related scalarization known as the Hypervolume scalarization, s HV λ (y) = min i (y i /λ i ) k that was introduced in Golovin and Zhang [2020] .To gain intuition, we visualize the non-linear level curves of the scalarization, which shows that our scalarization targets the portion of the Pareto frontier in the direction of λ for any λ > 0 (see Figure 1 ), since the tangent point of the level curves of the scalarization is always on the vector in the direction of λ. This implies that with an uniform distribution on λ, we are guaranteed to have a uniform spread of Pareto points in terms of its angular direction.Metric 1 (higher is better)Metric 2 (higher is better) Dominated Hypervolume (grey)Metric 1 (higher is better)Metric 2 (higher is better) Dominated Hypervolume (grey)Figure 2 : The hypervolume scalarization taken with respect to a direction λ = w corresponds to a differential area element within dominated hypervolume and averaging over random directions is analogous to integrating over the dominated hypervolume in polar coordinates. We exploit this fact to show that by choosing the maximizers of T random hypervolume scalarizers, we quickly converge to the hypervolume of the Pareto frontier at an optimal rate of O(T -1/k ). Figure from [Song et al., 2024] Lemma 5. For any point y ⋆ on the Pareto frontier of any set Y that lies in the positive orthant, there exists λ > 0 such that y ⋆ = arg max y∈Y s HV λ (y). Furthermore, for any α, λ > 0 such that αλ is on the Pareto frontier, then αλ ∈ arg max y∈Y s HV λ (y).This scalarization additionally has the special property that the expected maximized scalarized value under a uniform weight distribution on S k-1 + gives the dominated hypervolume, up to a constant scaling factor. Thus, the optima of the hypervolume scalarization over some static uniform distribution will be provably sufficiently diverse for any Pareto set in expectation. Lemma 6 (Hypervolume in Expectation [Golovin and Zhang, 2020] ). Let Y T = {y 1 , ..., y T } be a set of T points in R k . Then, the hypervolume with respect to a reference point z is given by:HV z (Y T ) = c k E λ∼S k-1 + max y∈Y T s HV λ (y -z) where c k = π k/2 2 k Γ(k/2+1) is a constant depending only on k.While this lemma is useful in the infinite limit, we supplement it by showing that finite-sample bounds on the strongly sublinear hypervolume convergence rate. In fact, many scalarizations will eventually explore the whole Pareto frontier in the infinite limit, but the rate at which the exploration improves the hypervolume is not known, and may be exponentially slow. We show that the optimizing hypervolume scalarizations with a uniform weight distribution enjoys sublinear hypervolume regret, specifically O(T -1/k ) hypervolume regret convergence rates for any Pareto set Y. Note that this rate is agnostic of the underlying optimization algorithm or Pareto set, meaning this is a general property of the scalarization.Our novel proof of convergence uses a generalization argument to connect hypervolume-scalarized Bayes regret and its finite sample form, exploiting the Lipschitz properties of s HV λ to derive metric entropy bounds. Proving smoothness properties of our hypervolume scalarizations for any λ > 0 with λ normalized on the unit sphere is non-obvious as s HV λ (y) depends inversely on λ i so when λ i is small, s HV λ might change wildly. Theorem 7 (Sublinear Hypervolume Regret). Let Y T = {y 1 , ..., y T } be a set of T points in R k such that y i ∈ arg max y∈Y s HV λi (y -z) with respect to a reference point z and B l ≤ y i -z ≤ B u . Then, with probability at least 1 -δ over λ i ∼ S + i.i.d., the hypervolume of Y T with respect to z satisfies sublinear hypervolume regret in T :HV z (Y ⋆ ) -HV z (Y T ) = O(T -1 k+1 + ln(1/δ)T -1 2 )where O hides constant factors in k, B u , B l .For k = 2, this also holds when Chebyshev scalarization is used:y i ∈ arg max y∈Y s CS λi (y -z).We note that the distribution of Pareto points selected by the Chebyshev scalarizer is quite similar to the Hypervolume scalarizer as the formulas are almost identical, except for the inverse weights of the latter. In fact, we show that when k = 2, both scalarizers behave the same and enjoy strong convergence rates; however for k > 2, the Pareto distributions are in fact different under λ ∼ S + and we can empirically observe the suboptimality of the Chebyshev scalarizer. By definition, using the inverse weight distribution with the Chebyshev scalarizer will be equivalent to applying the Hypervolume scalarizer.The dominating factor in our derived convergence rate is the O(T -1/(k+1) ) term and we show that this cannot be improved. Over all subsets Y T ⊆ Y of size T , note that our optimal convergence rate is given by the the subset that maximizes the dominated hypervolume of Y T , although finding this is in fact a NP-hard problem due to reduction to set cover. By constructing a lower bound via a novel packing argument, we show that even this optimal set would incur at least Ω(T -1/k ) regret, implying that our convergence rates, derived from generalization rates when empirically approximating the hypervolume, are optimal.Specifically, we show that for hypervolume regret, any algorithm cannot achieve better than O(T -1/(k-1) ) regret even when using linear objectives, and this matches the dominating factor in our algorithm up to a small constant in the denominator. By using hypervolume scalarizations and its connection to hypervolume regret, we conclude that this also implies a Ω(T -1/(k-1) ) lower bound on the scalarized Bayes regret. Theorem 8 (Hypervolume Regret Lower Bound). There exists a setting of linear objective parameters Θ ⋆ and A = {a : ∥a∥ = 1} such that for any actions A T , the hypervolume regret at z = 0 after T rounds isHV z (Θ ⋆ A) -HV z (Θ ⋆ A T ) = Ω(T -1 k-1 )Corollary 9. There is a setting of objectives Θ ⋆ and A = {a : ∥a∥ = 1} such that for any actions A T , the scalarized Bayes regret after T rounds isBR(s HV λ , A T ) = Ω(T -1 k-1 )Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: All the theorems, formulas, and proofs are given in the paper or appendix and are numbered and cross-referenced. All informal proofs have a formal complement and all assumptions are clearly stated.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
multiobjective stochastic linear bandits: 
 We propose a simple scalarized algorithm for linear bandits and provide a novel ℓ p analysis of the hypervolume regret that removes the polynomial dependence on k in the scalarized regret bounds.When combined with the ℓ ∞ sharpness of the hypervolume scalarization, this analysis gives an optimal O(d/ √ T ) bound on the scalarized regret, up to log(k) factors. This log dependence on k is perhaps surprising but is justified information theoretically since each objective is observed separately. Note that our scalarized algorithm works despite of noise in the observations, which makes it difficult to even statistically infer measures of hypervolume progress. Our setup and algorithm is given in the Appendix (see Section A).By using the confidence ellipsoids given by the UCB algorithm, we can determine each objective parameter Θ ⋆ i , up to a small error. To bound the scalarized regret, we utilize the ℓ p smoothness of s λ , L p , to reduce the dependence on k to be O(k 1/p ), which effectively removes the polynomial dependence on k when p → ∞. This is perhaps not surprising, since each objective is observed independently and fully, so the information gain scales with the number of objectives.Lemma 10. Consider running EXPLOREUCB (Algorithm 1) for T > max(k, d) iterations and for T even, let a T be the action that maximizes the scalarized UCB in iteration T /2. Then, with probability at least 1 -δ, the instantaneous scalarized regret can be bounded byr(s λ , a T ) ≤ 10k 1 p L p d log(k/δ) + log(T ) Twhere L p is the ℓ p -Lipschitz constant for s λ (•).Finally, we connect the expected Bayes regret with the empirical average of scalarized regret via uniform convergence properties of all functions of the form f (λ) = max a∈A s λ (Θ ⋆ a). By using s HV λ and setting p = ∞, we derive our final fast hypervolume regret rates for stochastic linear bandits, which is the combination of the scalarized regret rates and the hypervolume regret rates. Theorem 11 (HyperVolume Regret of EXPLOREUCB). Let z ∈ R k be a reference point such that over all a ∈ A, B l ≤ Θ ⋆ a -z ≤ B u . Then, with constant probability, running Algorithm 1 with s HV λ (y) and D = S + gives hypervolume regret bound, for k constant,HV z (Θ ⋆ A) -HV z (Θ ⋆ A T ) ≤ O d log(T ) T + 1 T 1 k+1Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: The hypervolume scalarization is easy to code up and try on a wide variety of benchmarks. All the code is released and all data is generated synthetic or via open-sourced benchmarks. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
experiments: 
 In this section, we empirically justify our theoretical results by comparing hypervolume convergence curves for multiobjective optimization in synthetic, linear bandit and blackbox optimization environments with multiple scalarizations and weight distributions. Our empirical results highlight the advantage of the hypervolume scalarization with uniform weights in maximizing the diversity and hypervolume of the resulting Pareto front when compared with other scalarizations and weight distributions, especially when there are a mild number of output objectives k. Our experiments are not meant to show that scalarizations is the best way to solve multiobjective optimization; rather, it is a simple yet competitive baseline that is easily parallelized in a variety of settings. Also, we use slightly altered form of our hypervolume scalarization as s λ (y) = min i y i /λ i , which is a simply a monotone transform and does not inherently affect the optimization. All error bars are given between the 30 to 70 percentile over independent repeats.Our synthetic optimization benchmarks assume the knowledge of Y and the Pareto frontier and thus we can compute the total hypervolume and compare the hypervolume regret of multiple scalarizations with the uniform S + distribution. For our experiments, we fix our weight distribution and compare the three widely types of scalarizations that were previously mentioned: the Linear, Chebyshev, and the Hypervolume scalarization. We focus on the k = 3 setting and apply optimization for a diverse set of Pareto frontiers in the region x, y ∈ [0, 1], z > 0. We discretize our region into 30 points per dimension to form a discrete Pareto frontier and set our reference point to be at z = [-ϵ, -ϵ, -ϵ] for ϵ = 1e-4 and run for 10 repeats.The synthetic Pareto frontiers that we are consider are a product of 1-dimensional frontiers and specifically, z = g(x) • g(y), where g(x) = exp(-x), 3 -exp(x), cos(πx) + 1, which form a concave, convex, and concave/convex Pareto frontiers respectively. Now that since the derivatives of these functions are all negative in our feasible region, z is a valid Pareto front. From our combination of functions, we observe that both Hypervolume and Chebyshev scalarizations enjoy fast convergence, while the performance of the Linear scalarization consistently lacks behind, surprisingly even for convex Pareto frontiers (see full plots in C.1). Interestingly, we observe that generally the Hypervolume scalarization does better on concave Pareto frontiers and on some convex-concave frontiers; however since these are static algorithms, it is not surprising that the Chebyshev distribution can perform better in certain convex regimes. However, we still advocate the usage of the hypervolume indicator as it is guaranteed to have a uniform spread especially when the number of objectives is increased, as shown by our later experiments. We run Algorithm 1 and compare scalarization effects for the multiobjective linear bandit setting. We set our reference point to be z = -2 in k dimension space, since our action set of A = {a : ∥a∥ = 1} and our norm bound on Θ ⋆ ensures that our rewards are in [-1, 1].In conjunction with the scalarizer, we use our weight distribution D = S + , which samples vectors uniformly across the unit sphere. In addition, we also compare this with the bounding box distribution methods that were suggested by [Paria et al., 2018] , which samples from the uniform distribution from the min to the max each objective and requires some prior knowledge of the range of each objective [Hakanen and Knowles, 2017] . Given our reward bounds, we use the bounding box of [-1, 1] for each of the k objectives. Following their prescription for weight sampling, we draw our weights for the linear and hypervolume scalarization uniformly in [1, 3] and take an inverse for the Chebyshev scalarization. We name this the boxed distribution for each scalarization, respectively.To highlight the differences between the multiple scalarizations, we configure our linear bandits parameters to be anti-correlated, which creates a convex Pareto front with non-uniform curvature. Note that a perfect anti-correlated Pareto front would be linear, which would cause linear scalarizations to always optimize at the end points. We start with simple k = 2 case and let θ 0 be random and θ 1 = -θ 0 + η, where η is some small random Gaussian perturbation (we set the standard deviation to be about 0.1 times the norm of θ i ). We renormalize after the anti-correlation to ensure ∥Θ ⋆ ∥ = 1. We run our algorithm with inherent dimension d = 4 for T = 100, 200 rounds with k = 2, 6, 10.As expected, we find the hypervolume scalarization consistently outperforms the Chebyshev and linear scalarizations, with linear scalarization as the worst performing (see Figure 4 ). Note that when we increase the output dimension of the problem by setting k = 10, the hypervolume scalarization shows a more distinct advantage. The boxed distribution approach of [Paria et al., 2018] does not seem to fare well and consistently performs worse than its uniform counterpart. While linear scalarization provides relatively good performance when the number of objective k ≤ 5, it appears that as the number of objectives increase in multi-objective optimization, more care needs to be put into the design of scalarization and their weights due to the curse of dimensionality, since the regions of non-uniformity will exponentially increase. We suggest that as more and more objectives are being added to modern machine learning systems, using smart scalarizations is critical to an uniform exploration of the Pareto frontier.We empirically demonstrate the competitiveness of hypervolume scalarizations for Bayesian Optimization by comparing them to the popular BO method of EHVI [Hupkens et al., 2015] . Running our proposed multiobjective algorithms on the Black-Box Optimization Benchmark (BBOB) functions, Figure 4 : Comparisons of the cumulative hypervolume plots with some anti-correlated θ. When the output dimension increase, there is a clearer advantage to using the hypervolume scalarization over the linear and Chebyshev scalarization. We find that the boxed weight distribution does consistently worse than the uniform distribution.which can be paired up into multiple bi-objective optimization problems [Tušar et al., 2016] . Our goal is to use a wide set of non-convex benchmarks to supplement our experiments on our simple toy example of linear bandits. For scalarized approaches, we use hypervolume scalarizations with the scalarized UCB algorithm with a constant standard deviation multiplier of 1.8 and all algorithms with use a Gaussian Process as the underlying model with a standard Matérn kernel that is tuned via ARD Williams and Rasmussen [2006] .Our objectives are given by BBOB functions, which are usually non-negative and are minimized. The input space is always a compact hypercube [-5, 5] n and the global minima is often at the origin. For bi-objective optimization, given two different BBOB functions f 1 , f 2 , we attempt to maximize the hypervolume spanned by (-f 1 (x i ), -f 2 (x i )) over choices of inputs x i with respect to the reference point (-5, -5). We normalize each function due to the drastically different ranges and add random observation noise. We also apply vectorized shifts of the input space of 2, -2 on the two functions respectively, so that the optima of each function do not co-locate at the origin.We run each of our algorithms in dimensions d = 8, 16, 24 and optimize for 160 iterations with 5 repeats. From our results, we see that both EHVI and UCB with hypervolume scalarizations are competitive on the BBOB problems but the scalarized UCB algorithm seems to be able to explore the extreme ends of the Pareto frontier, whereas EHVI tends to favor points in the middle (see Appendix and Figure 5 ). From our experiments, this trend appears to be consistent across different functions and is more prominent as the input dimensions d increase.For theory, we use the classic stochastic linear bandit setting. For the single-objective setting, in round t = 1, 2, ..., T , the and receives a reward y t = ⟨θ ⋆ , a t ⟩ + ξ t where ξ t is i.i.d. 1-sub-Gaussian noise and θ ⋆ ∈ R d is the unknown true parameter vector. In the multi-objective stochastic linear bandit setting, the learner chooses an action a t ∈ R d from the action set A and receives a vectorized reward y t = Θ ⋆ a t + ξ t , where Θ ⋆ ∈ R k×d is now a matrix of k unknown true parameters and ξ t ∈ R k is a vector of independent 1-sub-Gaussian noise. We assume, for sake of normalization, that ∥Θ ⋆ i ∥ ≤ 1 and that ∥a t ∥ ≤ 1, where ∥ • ∥ denotes the ℓ 2 norm unless otherwise stated. Other norms that are used include the classical ℓ p norms ∥ • ∥ p and matrix norms ∥x∥ M = x ⊤ Mx for a positive semi-definite matrix M.We also denote A t ∈ R d×t to be the history action matrix, whose i-th column is a i , the action taken in round i. Similarly, y t is defined analogously. Finally, for sake of analysis, we assume that A contains an isotropic set of actions and specifically, there is E ⊂ A with size |E| = O(d) such that i e i e ⊤ i ⪰ 1 2 I, where ⪰ denotes the PSD ordering on symmetric matrices. This assumption is not restrictive, as it can be relaxed by using optimal design for least squares estimators [Lattimore and Szepesvári, 2020] and the Kiefer-Wolfrowitz Theorem [Kiefer and Wolfowitz, 1960] , which guarantees the existence and construction of an uniform exploration basis of size O(poly(d)). Proof of Lemma 5. Let λ = y ⋆ /∥y ⋆ ∥. Note that λ > 0 since y ⋆ is in the positive orthant and for the sake of contradiction, assume there exists z such that s λ (z) > s λ (y ⋆ ). However, note that for any i, zi λi ≥ min i zi λi > min iy ⋆ i λi = y ⋆ i λi, where the last line follows since y ⋆ i /λ i = ∥y ⋆ ∥ for all i by construction. Therefore, we conclude that y ⋆ < z, contradicting that y ⋆ is Pareto optimal.Finally, note that if αλ is on the Pareto frontier, then we see that min i αλ i /λ i = α and furthermore, this min value is achieved for all i. Therefore, since αλ is on the Pareto frontier, any other point y ∈ Y has some coordinate j such that y j < αλ j , which implies that min i y i /λ i < α.Proof of Theorem 7. Let us denote s λ = s HV λ is the hypervolume scalarization and WLOG let z = 0. Note that we can first decompose our regret asHV z (Y ⋆ ) -HV z (Y T ) ≤ |HV z (Y ⋆ ) -c k T T i=1 max y∈Y s λi (y)| + | c k T T i=1 max y∈Y s λi (y) - HV z (Y T )| ≤ |HV z (Y) -c k T T i=1 s λi (y)| + | c k T T i=1 max y∈Y T s λi (y) -HV z (Y T )|where the second inequality uses the fact that y i ∈ arg max y∈Y s λi (y). We proceed to bound both parts separately and we note that it suffices to prove uniform concentration of the empirical sum to the expectation, as by our choice of scalarization is the hypervolume by Lemma 6. Let f Y (λ i ) = max y∈Y s λi (y). We let F = {f Y : Y ⊆ A} be our class of functions over all possible output sets Y. We will first demonstrate uniform convergence by bounding the complexity of F. Specifically, by generalization bounds from Rademacher complexities Bartlett and Mendelson [2002] , over choices of λ i ∼ D, we know that with probability 1 -δ, for all Y, we have the boundE λ∼D [f Y ] - 1 m m i=1 f Y (λ i ) ≤ R m (F) + 8 ln(2/δ) m where R m (F) = E λi∼D,σi sup f ∈F 2 m i σ i f (λ i ), where σ i are i.i.d. ±1 Rademacher variables.To bound R m (F), we appeal to Dudley's integral formulation that allows us to use the metric entropy of F to boundR m (F) ≤ inf α>0 4α + 12 ∞ α log(N (ϵ, F, ∥ • ∥ 2 )) m dϵwhere N denotes the standard covering number for F under the ℓ 2 function norm metric over λ ∈ D.Since ), so we havelog(N (ϵ, F, ∥ • ∥ 2 )) ≤ log(N (ϵ, F, ∥ • ∥ ∞ )) ≤ (4L λ /ϵ) k log(8/k)Finally, we follow the same Dudley integral computation of Theorem 4.3 of Gottlieb et al. [2016] to get thatR m (F) ≤ inf α>0 4α + 12 2 α (4L λ /ϵ) k log(8/k) T dϵ = O(L λ /m 1/(k+1) )Therefore, we conclude that with probability at least 1 -δ over the independent choices of λ i ∼ D, for all Y and setting m = TE λ∼D max a∈Y s λ (Θ ⋆ a) - 1 T T i=1 max a∈Y s λi (Θ ⋆ a) ≤ O L λ T 1/(k+1) + 8 ln(2/δ) Twhere B is some ℓ ∞ upper bound on the output set Y. Finally, we conclude by using Lemma 6 to replace the expectation by the hypervolume and by setting Y = Y, Y T respectively. Now consider the case when k = 2 and we are using the Chebyshev scalarizer s CS λ . We claim that the distribution Y T = {y 1 , ..., y T } is the same and specifically let Y denote that random variable over the choice of λ ∼ S + that corresponds to y ∈ arg max y∈Y s CS λ (y). Then, note that a standard way to draw a random weight on S + is to draw random absolute Gaussians and then renormalize,so if R 2 = i |X i | 2 , where X i are i.i.d. Gaussian, then Y = arg max y∈Y min( |X1| R y 1 , |X2| R y 2 ).Note that the optimization of the arg-max is unaffected by positive scalar multiples of the objective, so multiplying byR 2 /(|X 1 ||X 2 |) gives Y = arg max y∈Y min( R |X2| y 1 , R |X1| y 2 ). Note since X 1 , X 2 are i.i.d., we conclude that Y is the same distribution as the random variable that is given by y ∈ arg max y∈Y s HV λ (y). Since monotone transforms of the objective does not change the arg-max distribution, we conclude.Again, recall that for a scalarization function s λ (x), s λ is L p -Lipschitz with respect to x in the ℓ p norm on X if for x 1 , x 2 ∈ X , |s λ (x 1 ) -s λ (x 2 )| ≤ L p ∥x 1 -x 2 ∥ p , and analogously for define L λ for p = 2 so |s λ1 (x) -s λ2 (x)| ≤ L λ ∥λ 1 -λ 2 ∥ 2 . We utilize the fact that if s λ is differentiable everywhere except for a finite set, bounding Lipschitz constants is equivalent to bounding the dual norm ∥∇s λ ∥ q , where 1/p + 1/q = 1, which follows from mean value theorem, which we state as Proposition 12. Proposition 12. Let f : X → R be a continuous function that is differentiable everywhere except on a finite set, then if ∥∇f (x)∥ q ≤ L p for all x ∈ X , f (x) is L p -Lipshitz with respect to the ℓ p norm.Lemma 13. Let s λ (y) = λ ⊤ y be the linear scalarization with ∥λ∥ ≤ 1 and ∥y∥ ∞ ≤ 1. Then, we may boundL p ≤ max(1, k 1/2-1/p ) and L λ ≤ √ k and |s λ | ≤ √ k.Proof of Lemma 13. Since ∇ λ s λ (x) = y, we use Proposition 12 to boundL λ ≤ max y ∥y∥ ≤ √ k∥y∥ ∞ = √ k.Similarly, since ∇ y s λ (y) = λ, we may bound for p ≤ 2, L p ≤ ∥λ∥ q ≤ ∥λ∥ ≤ 1 for 1/p + 1/q = 1 and for p ≥ 2, we may use Holder's inequality to bound L p ≤ ∥λ∥ q ≤ k 1/q-1/2 ∥λ∥ ≤ k 1/2-1/p .To bound the absolute value of s λ , notes λ (y) = λ ⊤ y ≤ √ k for all since ∥y∥ 2 ≤ √ k∥y∥ ∞ ≤ √ k.Lemma 14. Let s λ (y) = min i λ i y i be the Chebyshev scalarization with ∥λ∥ ≤ 1 and ∥y∥ ∞ ≤ 1.Then, we may bound L p ≤ 1 and L λ ≤ 1 and|s λ | ≤ 1/ √ k.Proof of Lemma 14. For a specific λ, y, let i ⋆ be the optimal index of the minimization. Then, the gradient ∇ λ s λ (x) is simply zero in every coordinate except at i ⋆ , where it is y i ⋆ . Therefore, since we can only have a finite number of discontinuities due to monotonicity, we use Proposition 12 to bound L λ ≤ y i ⋆ ≤ 1. Similarly, since ∇ y s λ (y) has only one non-zero coordinate except at i ⋆ , which is λ i ⋆ , we may bound for L q ≤ λ i ⋆ ≤ 1.To bound the absolute value of s λ , note that there must exists λ i < 1/ √ k as ∥λ∥ ≤ 1. Thus,min i λ i y i < 1/ √ k for ∥y∥ ∞ ≤ 1.Lemma 15. Let s λ (y) = min i (y i /λ i ) k be the hypervolume scalarization with ∥λ∥ = 1 and0 < B l ≤ y i ≤ B u . Then, we may bound L p ≤ B k u B l k k/2-1 and L λ ≤ B k+1 u B l k (k-1)/2 and |s λ | ≤ B k u k k/2 .Proof of Lemma 15. For a specific λ, y, let i ⋆ be the optimal index of the minimization. Then, the gradient ∇ λ s λ (x) is simply zero in every coordinate except at i ⋆ , which in absolute value isk(y i ⋆ /λ i ⋆ ) k (1/λ i ⋆ ).Let j be the index such that λ j is maximized and since ∥λ∥ = 1, we know that λ j ≥ 1/ √ k. Therefore, we see that sincey i ⋆ /λ i ⋆ ≤ y j /λ j ≤ y j / √ k, we conclude that 1/λ i ⋆ ≤ (B u /B l )/ √ k.Therefore, using Proposition 12, we haveL λ ≤ k(y i ⋆ /λ i ⋆ ) k (1/λ i ⋆ ) ≤ k(B u / √ k) k (Bu/B l ) √ k = B k+1 u B l k (k-1)/2And similarly, since ∇ y s λ (y) has only one non-zero coordinate except at i ⋆ , which is k(y i ⋆ /λ i ⋆ ) k-1 (1/λ i ⋆ ), we may bound forL q ≤ k(y i ⋆ /λ i ⋆ ) k-1 (1/λ i ⋆ ) ≤ k(B u / √ k) k-1 (Bu/B l ) √ k ≤ B k u B l k k/2-1To bound the absolute value of s λ , note that s λ (y) ≤ (yj λj ) k ≤ B k u k k/2 .The following lemma about the UCB ellipsoid is borrowed from the original analysis of linear bandits.Lemma 16 (Abbasi-Yadkori et al. [2011] ). Consider the least squares estimator θ t = (M t ) -1 A ⊤ t y t , where the covariance matrix of the action matrix is M t = A ⊤ t A t + λI, then with probability 1 -δ,∥ θ t -θ * ∥ Mt ≤ √ λ∥θ * ∥ + 2 log( 1 δ ) + d log(T /λ)Proof of Lemma 10. Let Θ T be the least squares estimate of the true parameters after observing (A T , y T ). Since the noise ξ t in each objective is independent and 1-sub-Gaussian, by Lemma 16, if we let M T = A ⊤ T A T + λI, then with regularization λ = 1∥ Θ T i -Θ ⋆ i ∥ M T ≤ 1 + 2 log(k/δ) + d log(T ) := D Tholds with probability at least 1 -δ/k. Note that this describes the confidence ellipsoid,C T i = {θ ∈ R d : ∥ Θ T i -θ i ∥ M T ≤ D T } for Θ T i .By the definition of the UCB maximization of a t , we see a t , Θ t = argmax a∈A max θi∈C T i s λ (Θ ⊤ i a). Note that since Θ ⋆ ∈ C T , we can bound the instantaneous scalarized regret as:r(s λ , a t ) = max a∈A s λ (Θ ⋆ a) -s λ (Θ ⋆ a t ) ≤ s λ ( Θ t a t ) -s λ (Θ ⋆ a t )By the Lipschitz smoothness condition, we conclude that r(s λ , at ) ≤ L p ∥( Θ t -Θ ⋆ )a t ∥ p .To bound the desired ℓ p norm, first note that by triangle inequality, ∥ Θ t -Θ ⋆ ∥ M T ≤ 2D T . Since we apply uniform exploration every other step and i e i e ⊤ i ⪰ 1 2 I for e i ∈ E with size |E| = d, we conclude that M T ⪰ T 5d I. Therefore, we conclude that ∥ Θ T i -Θ ⋆ i ∥ ≤ 5 d/T D T := E T with probability at least 1-δ/k. Since ∥a t ∥ ≤ 1, we conclude by Cauchy-Schwarz, that |( Θ T i -Θ ⋆ i )a t | ≤ E T . Together with our Lipschitz condition, we conclude that r(s λ , a t ) ≤ k 1/p L p E T ≤ 10k 1/p L p d (log(k/δ) + log(T ))/T . Theorem 17. Assume that for any a ∈ A, |s λ (Θ ⋆ a)| ≤ B for some B and s λ is L λ -Lipschitz with respect to the ℓ 2 norm in λ. With constant probability, the Bayes regret of running Algorithm 1 at round T can be bounded byBR(s λ , A T ) ≤ O k 1 p L p d log(kT ) T + BL λ T 1 k+1Proof of Theorem 17. For any set of actions A ⊆ A, we define f A (λ) = max a∈A s λ (Θ ⋆ a). We let F = {f A : A ⊆ A} be our class of functions over all possible action sets and for any Bayes regret bounds, we will first demonstrate uniform convergence by bounding the complexity of F. Specifically, by generalization bounds from Rademacher complexities Bartlett and Mendelson [2002] , over choices of λ i ∼ D, we know that with probability 1 -δ, for all A, we have the boundE λ∼D [f A ] - 1 m m i=1 f A (λ i ) ≤ R m (F) + 8 ln(2/δ) m where R m (F) = E λi∼D,σi sup f ∈F 2 m i σ i f (λ i ), where σ i are i.i.d. ±1 Rademacher variables.To bound R m (F), we appeal to Dudley's integral formulation that allows us to use the metric entropy of F to boundR m (F) ≤ inf α>0 4α + 12 ∞ α log(N (ϵ, F, ∥ • ∥ 2 )) m dϵwhere N denotes the standard covering number for F under the ℓ 2 function norm metric over λ ∈ D.Since D is the uniform distribution over S + , this induces a natural ℓ ∞ function norm metric on F that is ∥f ∥ ∞ = sup λ∈S+ |f (λ)|. Since s λ (Θ ⋆ a) is L λ Lipschitz with respect to the Euclidean norm in λ. Note that since the maximal operator preserves Lipschitzness, f A (λ) is also L λ -Lipschitz with respect to λ ∈ R k . Since F contains L λ -Lipschitz functions in R k , we can bound the metric entropy via a covering of λ via a Lipschitz covering argument (see Lemma 4.2 of Gottlieb et al. [2016] ), so we havelog(N (ϵ, F, ∥ • ∥ 2 )) ≤ log(N (ϵ, F, ∥ • ∥ ∞ )) ≤ (4L λ /ϵ) k log(8/k)Finally, we follow the same Dudley integral computation of Theorem 4.3 of Gottlieb et al. [2016] to get thatR m (F) ≤ inf α>0 4α + 12 2 α (4L λ /ϵ) k log(8/k) m dϵ = O(L λ /m 1/(k+1) )Therefore, we conclude that with probability at least 1 -δ over the independent choices ofλ i ∼ D, for all A, E λ∼D max a∈A s λ (Θ ⋆ a) - 1 m m i=1 max a∈A s λi (Θ ⋆ a) ≤ O BL λ m 1/(k+1) + 8 ln(2/δ) mFinally, note that for T even, with constant probability,BR(s λ , A t ) = E λ∼D [r(s λ , A t )] = E λ∼D [max a∈A s λ (Θ ⋆ a) -max a∈A T s λ (Θ ⋆ a)] ≤ 1 T /2 T /2 i=1 max a∈A s λi (Θ ⋆ a) -max a∈A T s λi (Θ ⋆ a) + O BL λ T 1/(k+1) ≤ 1 T /2 T /2 i=1 max a∈A s λi (Θ ⋆ a) -s λi (Θ ⋆ a 2i ) + O BL λ T 1/(k+1) ≤ 1 T /2 T /2 i=1 r(s λi , a 2i ) + O BL λ T 1/(k+1) ≤ O k 1/p L p d log(kT ) T + BL λ T 1/(k+1)where the last line used Lemma 10 with δ = 1/T 2 and applied a union bound over all O(T ) iterations.Proof of Theorem 11. Note that by Lemma 6, we connect the Bayes regret to the hypervolume regret for D :HV z (Θ ⋆ A) -HV z (Θ ⋆ A t ) = c k E λ∼D [max a∈A s λ (Θ ⋆ a) -max a∈A T s λ (Θ ⋆ a)] where s λ (y) = min i (y i -z i /λ i ) k . Note that since ∥Θ ⋆ a∥ ∞ ≤ 1 for all a ∈ A and B is maximal, we have B ≤ Θ ⋆ a -z ≤ B + 2.Therefore, we conclude by Lemma 15 that s λ is Lipschitz withL p ≤ (B + 2) k Bk k/2-1 , L λ ≤ (B + 2) k+1 Bk (k-1)/2 , |s λ | ≤ (B + 2) k k k/2Finally, we combine this with Theorem 17 with p = ∞ as the optimal choice of p (since L p does not depend on p) to get our desired bound on hypervolume regret.Proof of Theorem 8. We let A = {a : ∥a∥ ≤ 1} be the unit sphere and Θ ⋆ i = e i be the unit vector directions. Note that in this case the Pareto frontier is exactly S k-1 + . Consider a uniform discretization of the Pareto front by taking an ϵ grid with respect to each angular component with respect to the polar coordinates. Let p 1 , ..., p m be the center (in terms of each of the k -1 angular dimensions) in the m = Θ((1/ϵ) k-1 ) grid elements. We consider the output y T = Θ ⋆ A T and assume that for some grid element i, it contains none of the T outputs y T . Since our radial component r = 1, by construction of our grid in the angular component, we deduce that min t ∥y t -p i ∥ ∞ > ϵ/10 by translating polar to axis-aligned coordinates.Let ϵ ′ = ϵ/10. Assume also that 1 k < p i < 1 -1 k . Next, we claim that the hypercube from p i -ϵ ′ /k 2 to p i is not dominated by any points in Y T . Assume otherwise that there exists y t such that y t ≥ p i -ϵ ′ /k 2 . Now, this combined with the fact that since min t ∥y t -p i ∥ ∞ > ϵ ′ implies that there must exist a coordinate such that y tj ≥ p j + ϵ ′ . However, this implies thatk i=1 y 2 ti ≥ i̸ =j (p i -ϵ ′ /k 2 ) 2 + (p j + ϵ ′ ) 2 ≥ i p 2 i -2(ϵ ′ /k 2 ) i̸ =j p i + 2ϵ ′ p j > 1where the last inequality follows since i p i < 1/ √ k and p j > 1 k by assumption. However, this contradicts that ∥y t ∥ ≤ 1, so it follows that p i -ϵ ′ is not dominated.Therefore, for any grid element such that p i > 1/k, if there is no y t in the grid, we must have a hypervolume regret of at least Ω(ϵ ′k ) = Ω(ϵ k ) be simply consider the undominated hypervolume from p i to p i -ϵ ′ , which lies entirely within the grid element. In fact, since there are Θ((1/ϵ) k-1 ) such grid elements satisfying p i > 1/k, we see that if T < O((1/ϵ) k-1 ), by pigeonhole, there must be a hypervolume regret of at least Ω((1/ϵ) k-1 ϵ k ) = Ω(ϵ) Therefore, for any 1/2 > ϵ > 0, HV z (Θ ⋆ A) -HV z (Θ ⋆ A T ) < ϵ implies that T = Ω((1/ϵ) k-1 ).HV z (Θ ⋆ A) -HV z (Θ ⋆ A T ) = Ω(T -1/(k-1) )Here are the relevant full plots from synthetic optimization of Pareto frontiers. Note that the title of each plots explicitly mention the optimized function. Generally, we observe that the hypervolume scalarizer has better performance on more concave curves. We also include a plot of a concave function multiplied by a linear combination of a convex and concave function, given by z = exp(-x)(x exp(-y) + (1 -x)(3 -exp(y))), which demonstrates that hypervolume scalarization performs competitively even with convex frontier regions. Justification: In our introduction, we provide limitations of works given in the beyond linear scalarization and hypervolume regret subsections.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: All the code is released and all data is generated synthetic or via open-sourced benchmarks.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Yes, all experimental details are provided in the core of the paper or in the appendix/code. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Yes error bars are provided and we assume the standard reporting of 30-70 percentile for error bars over independent repeats, as stated. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: This paper proposes a non-linear scalarization with weights chosen uniformly at random to reduce multiple objectives into one. A sublinear hypervolume regret bound of O(T^{-1/k}) is achieved, as well as a matching lower bound. Scalarization in multi-objective optimization is an important problem. The reviewers found the results and techniques interesting and non-trivial.

Reviews: review: paper_summary: paper_summary: The paper addresses the challenge of exploring the Pareto frontier in multi-objective optimization problems, particularly focusing on minimizing hypervolume regret. Linear scalarizations are often inadequate as they fail to explore certain non-convex regions of the Pareto frontier. The authors propose using non-linear scalarization with weights chosen uniformly at random. Specifically, the scalarization function $s_\lambda(y) =  \min_{i \in [k]} (y_i/\lambda_i)^k$, where $y$ is a $k$-dimensional vector and $\lambda$ is chosen uniformly at random. This achieves optimal sublinear hypervolume regret bounds of $O(T^{-1/k})$ with matching lower bounds.  Furthermore, the authors show that hypervolume scalarization uniformly explores the Pareto frontier in terms of the angular direction, thereby covering the entire Pareto frontier. They further demonstrate the theoretical and empirical performance of these scalarizations across various optimization settings. For multi-objective linear bandits, the authors introduce a scalarized algorithm based on the UCB algorithm and prove that this algorithm achieves a regret bound of $O(d \sqrt{T} + T^{-1/k})$.
strength_weakness: strength_weakness: Please see the questions section.
questions: questions: The paper briefly discusses Chebyshev scalarization (which has a similar form except that $\lambda_i$ is in the numerator), mentioning that it enjoys similar advantages as hypervolume scalarization when dealing with a non-convex Pareto frontier. However, it is not clear how the hypervolume regret would scale for this function. The paper could benefit from a theoretical comparison with other scalarizations as well.

In the case of linear bandits, the UCB extension works for other scalarization functions (Chebyshev, linear) as seen in the algorithm and achieves sublinear regret as shown in the experiments. I wonder if the theoretical guarantees differ significantly for different scalarization functions. What exact properties of the scalarization function impact the regret?
limitations: limitations: This paper does not have any negative social impact.
paper_summary: paper_summary: For multi-objective optimization, a common technique is to use scalarizations to reduce the multi-objective to one single objective. While it is easy to use linear function/scalarizations, it does not fully explore a concave region of Pareto frontier. The paper focuses on non-linear scalarization, in particular, it focuses on hypervolume scalarizations.

The authors propose simple non-linear scalarizations that effectively explore the Pareto frontier and achieve optimal sublinear hypervolume regret bound. 

The main contribution of this paper is to show that hypervolume scalarizations with uniformly random weights achieves a sublinear hypervolume regret bound of order $O(T^{-1/k})$ together with a matching lower bound.

For the special case of multiobjective linear bandits, the paper gives an algorithm that achieves $O(dT^{−1/2} + T^{1/k})$ hypervolume regret.

The paper also empirically justifies the effectiveness of hypervolume scalarizations via synthetic, linear bandit, and blackbox optimization benchmarks.



--------------
I acknowledge that I have read the author's rebuttal.
strength_weakness: strength_weakness: .
questions: questions: .
limitations: limitations: One minor suggestion to improve the readability of this paper is to give some concrete examples on scalarization, and in particular, for hyper volume regret.
paper_summary: paper_summary: This paper shows that the hypervolume scalarization has sublinear hypervolume regret bounds of $O(T^{-1/k})$, and further proves a lower bound of hypervolume regret of $\Omega(T^{-1/k})$. An optimization algorithm for multiobjective linear bandits is proposed. An empirical study is conducted to verify the effectiveness of hypervolume scalarizations.
strength_weakness: strength_weakness: * This paper has a significant overlap with a previous paper (Golovin and Zhang, 2020), which proposed hypervolume scalarization and its hypervolume regret. The main focus of these two papers seems similar, so I suggest the authors summarize the differences and new contributions.
* The authors claim that the concept of the so-called "hypervolume scalarization" originated from (Golovin and Zhang, 2020). However, similar scalarization methods were already proposed in (Qi et al., 2014) and have been widely used in the field of multi-objective optimization (Li et al., 2016).
* The authors regard hypervolume as the gold standard, but I have reservations about this. Hypervolume has two main drawbacks: (1) the hypervolume optimal distribution may not cover the entire Pareto Front, and (2) HV's behavior is highly dependent on the choice of the reference point. Therefore, in practical applications, maximizing HV does not necessarily yield ideal results. Additionally, the paper assumes reference points multiple times, such as in Theorem 8 where it is assumed that $z=0$. Given the characteristics of HV, I would question whether such assumptions may limit the generalizability of these theorems.

References

Zhang, R., & Golovin, D. (2020). Random hypervolume scalarizations for provable multi-objective black box optimization. In ICML (pp. 11096-11105).

Qi, Y., Ma, X., Liu, F., Jiao, L., Sun, J., & Wu, J. (2014). MOEA/D with adaptive weight adjustment. Evolutionary Computation, 22(2), 231-264.

Li, H., Zhang, Q., & Deng, J. (2016). Biased multiobjective optimization and decomposition algorithm. IEEE Transactions on Cybernetics, 47(1), 52-66.
questions: questions: P2, L74. "maximize the Pareto front"?

P3, L130. Typo: "biojective".
limitations: limitations: No concerns.
paper_summary: paper_summary: This abstract presents a study on non-linear scalarization techniques for multi-objective optimization, specifically focusing on hypervolume scalarizations with random weights. The authors prove that this approach achieves optimal sublinear hypervolume regret bounds and apply it to multiobjective stochastic linear bandits, deriving improved regret bounds. Their theoretical findings are supported by empirical results demonstrating superior performance of non-linear scalarizations compared to linear alternatives and other standard multiobjective algorithms in various settings.
strength_weakness: strength_weakness: First of all, most lemmas are from the reference [1]. The authors should primarily focus on highlighting differences or contributions compared to this reference. Given that the key scalarization method was proposed in [1], simply conducting experiments on synthetic data adds little value, as this was likely already verified in the original proposal.

Besides, the applicability of hypervolume regret to the multi-armed bandit setting is questionable, especially in scenarios with finite action sets. The identification of the optimal arm in such cases needs to be carefully defined.


[1]. Zhang, Richard, and Daniel Golovin. "Random hypervolume scalarizations for provable multi-objective black box optimization." International conference on machine learning. PMLR, 2020.
questions: questions: See the weakness.
limitations: limitations: The authors need to clarify the contribution first.

Comments: comment: Thank you for your response. I have no further questions.
Thank you for your responses and clarification. I changed my rating.
Thank you for the update! We agree that the reference point needs to be set sanely (heuristics is usually set reference to min - 0.1 * range), but for the second point, not sure if the number of solutions matter. Happy to entertain a longer discussion if there's still concern on the latter.
Thank you for your response. I am satisfied with the response, and I have increased my rating. Regarding your response to HV, I think HV covers the full PF only under certain assumptions. First, the reference point is set appropriately. Second, there are infinite solutions.