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

• URL: http://arxiv.org/abs/2607.26273v1
• Date: Tue, 28 Jul 2026 21:10:39 GMT
• Title: Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
• Abstract summary: We consider a 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.<n>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.<n>We establish a gap-free regret bound $tildeO(dsqrtnkT)$ that holds on every instance, together with a gap
• Score: 48.83076933238825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \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 $\tilde{O}(d\sqrt{nkT})$ that holds on every instance, together with a gap-dependent bound $\tilde{O}(nk^{2.5}/Δ_{\min})$ 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.

Related papers

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
  In this paper, we revisit the linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process.<n>We propose a novel variance-adaptive algorithm textttVAEE for large action set, which actively explores actions that maximize the information gain.<n>We establish a nearly matching lower bound for the fixed action set setting indicating that emphharmonic-mean dependent rate is unavoidable.
  arXiv  Detail & Related papers  (2026-07-26T14:24:34Z)
• Probe-then-Commit Multi-Objective Bandits: Theoretical Benefits of Limited Multi-Arm Feedback [2.1772197319352498]
  We study an online resource-selection problem motivated by multi-radio access selection and mobile edge computing offloading.<n>In each round, an agent chooses among $K$ candidate links/servers whose performance is $d$-dimensional vector.<n>We develop textscPtC-P-UCB, an optimistic probe-then-commit algorithm.
  arXiv  Detail & Related papers  (2026-02-03T06:44:00Z)
• Heterogeneous Multi-Agent Bandits with Parsimonious Hints [12.709437751500353]
  We study a hinted heterogeneous multi-agent multi-armed bandits problem (HMA2B), where agents can query low-cost observations (hints) in addition to pulling arms.<n>In this framework, each of the $M$ agents has a unique reward distribution over $K$ arms, and in $T$ rounds, they can observe the reward of the arm they pull only if no other agent pulls that arm.<n>The goal is to maximize the total utility by querying the minimal necessary hints without pulling arms, achieving time-independent regret.
  arXiv  Detail & Related papers  (2025-02-22T07:46:41Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection.<n>The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error.<n>We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application to Joint Communications and Sensing [7.0997346625024]
  We propose a generic upper confidence bound (UCB)-based algorithm with change detection to solve this problem. We also formulate an energy-efficient waveform design problem in an integrated communication and sensing system as a toy example.
  arXiv  Detail & Related papers  (2023-02-10T14:10:14Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  We present a reward model that captures set-dependent reward distribution and assumes no total order for arms. We develop a novel regret analysis and show an $Oleft(frack2 n log Tepsilonright)$ gap-dependent regret bound as well as an $Oleft(k2sqrtn T log Tright)$ gap-independent regret bound.
  arXiv  Detail & Related papers  (2021-03-03T23:08:59Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB) We show AMB achieves a gap-dependent regret bound that only scales with the sum of the inverse of the sub-optimality gaps. We also show AMB suffers an additional $frac|Z_mul|Delta_min$ regret, where $Z_mul$ is the set of state-action pairs $(s,a)$'s satisfying $a$ is a non-unique optimal action for
  arXiv  Detail & Related papers  (2021-02-09T07:46:34Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.