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

In multi-objective optimization, the goal is often to identify a set of solutions that approximate the Pareto frontier rather than finding a single optimal point. This paper addresses the challenge of selecting a slate of k arms in a stochastic multi-armed bandit setting to maximize the dominated hypervolume (HV) of the selected arms. The authors aim to provide a theoretically grounded, computationally efficient approach that scales to multiple objectives (d > 2) and handles the inherent trade-off between exploration and exploitation in an online, semi-bandit feedback environment.

The authors propose THV-UCB, an algorithm that maintains coordinate-wise upper confidence bounds (UCBs) for each arm's mean reward vector. At each round, the algorithm performs a safe pruning step to remove arms that are confidently dominated by others. It then constructs the slate of k arms greedily by maximizing the marginal hypervolume contribution based on optimistic estimates. This approach leverages the submodularity of the hypervolume function to ensure that the greedy selection provides a (1 - 1/e)-approximation of the optimal subset. The authors prove both a gap-free regret bound of O(d*sqrt(nkT)) and a gap-dependent bound of O(nk^2.5/delta_min), demonstrating that the algorithm's regret grows sublinearly over time.

This work bridges the gap between multi-objective optimization and online learning. By using the dominated hypervolume as a preference-free quality indicator, THV-UCB provides a robust way to maintain diverse, high-quality trade-off solutions in applications like recommender systems, clinical trials, and market making. Unlike gradient-based methods that can be computationally prohibitive in online settings, THV-UCB offers a scalable, discrete-action framework that remains effective as the number of objectives increases.