Top- Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
arXiv:2607.26273
The paper studies stochastic multi‑objective bandits where a slate of k arms is chosen each round, and proposes an optimistic algorithm (THV-UCB) that greedily selects arms to maximize the hypervolume of the Pareto front approximation, providing regret bounds for this setting.
Abstract
We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of arms and observes their -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- subset achievable in hindsight, where reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce \textit{THV-UCB}, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound that holds on every instance, together with a gap-dependent bound that becomes polylogarithmic in 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.
21 pages, 7 figures, 7 tables