Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Optimal Scalarizations for Sublinear Hypervolume Regret
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that hypervolume scalarizations with uniformly random weights achieve optimal O(T^{-1/k}) hypervolume regret, with matching lower bounds, and uses them in a multiobjective linear bandit algorithm with improved, k-free regret bounds.
Problem
Scalarization methods with linear weights cannot explore concave Pareto frontier regions, and existing hypervolume-regret guarantees are exponential in k or apply only to specialized algorithms; the paper asks how fast oblivious scalarizations can approximate the full Pareto frontier in hypervolume.
Approach
Maximizers of hypervolume scalarizations min_i (y_i/λ_i)^k with i.i.d. uniform weights on the positive unit sphere give a provably optimal O(T^{-1/k}) hypervolume regret for any Pareto set, and a non-Euclidean (ℓ_∞-smoothness) analysis removes poly(k) dependence in multiobjective linear bandits.
Key results
- Hypervolume scalarization with uniform weights gives O(T^{-1/k}) hypervolume regret for any Pareto set, with a matching Omega(T^{-1/k}) lower bound for any algorithm (as stated in the informal theorem; the appendix proof gives Omega(T^{-1/(k-1)})).
- For multiobjective linear bandits, ExploreUCB with hypervolume scalarization achieves hypervolume regret O(d sqrt(log T / T) + T^{-1/(k+1)}) in the main theorem, with the k-dependence in the scalarized bound removed via ℓ_∞ smoothness.
- In linear bandit experiments with k=10, hypervolume scalarization outperforms Chebyshev and linear scalarizations, and the boxed weight distribution performs consistently worse than the uniform one.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Hypervolume instead of Linear scalarization with uniform weights | Synthetic Pareto-front optimization · Synthetic concave, convex, and concave/convex Pareto frontiers | hypervolume regret convergence | Helped |
| Use Hypervolume instead of Chebyshev scalarization with uniform weights | Synthetic Pareto-front optimization · Concave Pareto frontiers | hypervolume regret convergence | Helped |
| Use Chebyshev instead of Hypervolume scalarization with uniform weights | Synthetic Pareto-front optimization · Certain convex regimes | hypervolume convergence | Helped |
| Use Hypervolume instead of Linear or Chebyshev scalarization | ExploreUCB · Multiobjective stochastic linear bandits | cumulative hypervolume | Helped |
| Use boxed weights instead of uniform sphere weights | ExploreUCB scalarizations · Multiobjective stochastic linear bandits | cumulative hypervolume | Hurt |
| Use Hypervolume scalarization instead of EHVI | Bayesian optimization with Gaussian Processes · BBOB bi-objective functions | hypervolume progress | Mixed |
| Use scalarized UCB with Hypervolume scalarization instead of EHVI | Bayesian optimization with Gaussian Processes · BBOB bi-objective functions, especially higher input dimensions | exploration of Pareto-front extremes | Helped |
Surprising findings
- Linear scalarization performs worst even on convex Pareto frontiers in the synthetic experiments.
- EHVI concentrates on the middle of the Pareto frontier while UCB with hypervolume scalarization explores the extremes on BBOB problems.
Limitations
- null
Experimental setup
Datasets: BBOB benchmark functions synthetic Pareto frontiers synthetic linear bandit instances
Benchmarks: BBOB bi-objective functions synthetic Pareto frontiers synthetic multiobjective linear bandit
Metrics: dominated hypervolume hypervolume regret
Baselines: linear scalarization Chebyshev scalarization EHVI boxed weight distribution
Builds on: Chebyshev scalarization UCB for linear bandits random hypervolume scalarization
Closest papers by meaning
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.88)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.87)
- SURF: Steering the Scalarization Weight to Uniformly Traverse the Pareto Front (NeurIPS 2026 · similarity 0.87)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.87)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.87)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.