# Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 28 Jul 2026.

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

- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations](https://mlsanity.com/paper/1805.12168/) (2018)
- [Computer-Aided Multi-Objective Optimization in Small Molecule Discovery](https://mlsanity.com/paper/2210.07209/) (2022)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement](https://mlsanity.com/paper/2310.15195/) (2023)
- [Optimal Scalarizations for Sublinear Hypervolume Regret](https://mlsanity.com/paper/2307.03288/) (2023)
- [Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customization](https://mlsanity.com/paper/2502.13457/) (2025)
- [Balancing Rewards in Text Summarization: Multi-Objective Reinforcement Learning via HyperVolume Optimization](https://mlsanity.com/paper/2510.19325/) (2025)
- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)
- [Constrained Pareto Set Identification with Bandit Feedback](https://mlsanity.com/paper/2506.08127/) (2025)
- [Bandit Pareto Set Identification in a Multi-Output Linear Model](https://mlsanity.com/paper/2507.04255/) (2025)

## Abstract (arXiv)

We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of k arms and observes their d-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an α-approximate hypervolume regret with respect to the best size-k subset achievable in hindsight, where α = 1 - 1/e reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce textitTHV-UCB, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound tildeO(d√nkT) that holds on every instance, together with a gap-dependent bound tildeO(nk2.5/Deltamin) that becomes polylogarithmic in T once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications.