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

# Hypervolume Regret for Multi-Objective Slate Selection
Source: [https://arxiv.org/html/2607.26273](https://arxiv.org/html/2607.26273)
## Top\-kkPareto Bandits: Hypervolume Regret for Multi\-Objective Slate Selection

###### Abstract

We consider a stochastic multi\-objective bandit problem where, at each round, the agent selects a slate ofkkarms and observes theirdd\-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α\\alpha\-approximate hypervolume regret with respect to the best size\-kksubset achievable in hindsight, whereα=1−1/e\\alpha=1\-1/ereflects the approximation guarantee of greedy maximization for monotone submodular functions\. To address this problem, we introduceTHV\-UCB, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions\. We establish a gap\-free regret boundO~​\(d​n​k​T\)\\tilde\{O\}\(d\\sqrt\{nkT\}\)that holds on every instance, together with a gap\-dependent boundO~​\(n​k2\.5/Δmin\)\\tilde\{O\}\(nk^\{2\.5\}/\\Delta\_\{\\min\}\)that becomes polylogarithmic inTTonce the arms are sufficiently well separated\. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi\-objective applications\.

## Introduction

Most real\-world decision problems involve balancing several conflicting criteria, and the corresponding paradigm of Multi\-Objective Optimization \(MOO\) seeks not a single optimum but a Pareto\-optimal set of trade\-off solutions\(Tianet al\.[2021](https://arxiv.org/html/2607.26273#bib.bib3); Fromer and Coley[2023](https://arxiv.org/html/2607.26273#bib.bib25)\)\. This challenge extends to the multi\-armed bandit \(MAB\) framework where each pull yields not a scalar but a vector of rewards that captures competing criteria: accuracy vs\. diversity in recommender systems\(Letardet al\.[2024](https://arxiv.org/html/2607.26273#bib.bib11); Zaiziet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib17)\), profit vs\. inventory in market making\(Fernández Vicenteet al\.[2026](https://arxiv.org/html/2607.26273#bib.bib12)\), efficacy vs\. toxicity in clinical trials\(KONEet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib19); Koneet al\.[2025a](https://arxiv.org/html/2607.26273#bib.bib29)\)\.

Three complementary aims drive contemporary research: 1\) approximating the Pareto front faithfully and uniformly\(KONEet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib19); Koneet al\.[2025b](https://arxiv.org/html/2607.26273#bib.bib30),[a](https://arxiv.org/html/2607.26273#bib.bib29); Shahverdikondoriet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib8)\), 2\) doing so under the noisy, sample\-limited feedback that characterizes online and bandit settings to minimize Pareto regret\(Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10); Xu and Klabjan[2023](https://arxiv.org/html/2607.26273#bib.bib28); Caoet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib9); Hüyük and Tekin[2021](https://arxiv.org/html/2607.26273#bib.bib18); Xueet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib1)\), and 3\) measuring progress through unary, preference\-free indicators such as the dominated hypervolume\(Guerreiroet al\.[2021](https://arxiv.org/html/2607.26273#bib.bib4)\)\.

This third line formalizes MOO progress through the dominated hypervolume \(HV\)\(Guerreiroet al\.[2021](https://arxiv.org/html/2607.26273#bib.bib4)\), the only preference\-free indicator that is strictly Pareto\-compliant\. Hypervolume maximization emerges as a more natural quality criterion in scenarios where the coverage of the Pareto front matters most\. HV has been frequently used as a training signal in Pareto Set Learning\(Zhanget al\.[2023](https://arxiv.org/html/2607.26273#bib.bib21); Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)and in multi\-objective reinforcement learning\(Liuet al\.[2025a](https://arxiv.org/html/2607.26273#bib.bib2),[b](https://arxiv.org/html/2607.26273#bib.bib14); Leeet al\.[2026](https://arxiv.org/html/2607.26273#bib.bib13); Röpkeet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib5); Songet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib15); Fernández Vicenteet al\.[2026](https://arxiv.org/html/2607.26273#bib.bib12); Letardet al\.[2024](https://arxiv.org/html/2607.26273#bib.bib11)\)\.

Previous works, however, either operate in continuous black\-box domains, query a single point per round, do not scale with the number of objectived\>2d\>2, lack theoretical foundations or focus on a specific kind of problem \(e\.g\. concave or convex\), lacking applicability and robustness\.

To the best of our knowledge, no previous work has addressed these challenges in a cross\-domain online setting\. We bridge the three main lines of research in the multi\-objective optimization field by introducingTHV\-UCB\. This algorithm leverages optimistic reward vectors to greedily maximize marginal hypervolume gains, while utilizing coordinate\-wise confidence boxes to safely prune dominated arms and perform initial forced exploration\.

Hence, we formalize a stochastic multi\-objective bandit problem where, at each roundtt, the agent selects a slateStS\_\{t\}ofkkarms from a set ofnncandidates and observes theird−d\-dimensional reward vectors under semi\-bandit feedback\. The performance ofStS\_\{t\}is evaluated by the dominated hypervolume it covers relative to a reference point, with our theoretical analysis comparing this performance against the optimal hypervolume achievable by any subset of sizekk\.

Our main contributions can be summarized as follows :

1. 1\.We introduce the Top\-kkPareto bandit setting and define anα\\alpha\-approximation hypervolume regret with respect to the best size\-kksubset of the Pareto frontier, more suited for many real\-world scenarios ;
2. 2\.We extend previous competitive works\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31); Debet al\.[2002](https://arxiv.org/html/2607.26273#bib.bib32); Yahyaa and Manderick[2015](https://arxiv.org/html/2607.26273#bib.bib42); Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10); Aueret al\.[2002](https://arxiv.org/html/2607.26273#bib.bib33); Pariaet al\.[2020](https://arxiv.org/html/2607.26273#bib.bib34); Zhang and Golovin[2020](https://arxiv.org/html/2607.26273#bib.bib27); Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)from Pareto optimization and scalarization methods to this setting and empirically evaluate them for hypervolume maximization in top\-kksemi\-bandit setting considering 1\) four synthetic fronts \(linear, convex, concave and clusters\) ; 2\)d∈ℤ∩\[2,5\]d\\in\\mathbb\{Z\}\\cap\[2,5\]conflicting objectives \(dimensions of the Pareto front\) and associated top\-k∈ℤ∩\[3,6\]k\\in\\mathbb\{Z\}\\cap\[3,6\]\(slates\-length \- arms to be selected at each round\) ;
3. 3\.We proposeTHV\-UCB, an optimistic algorithm using coordinate\-wiseℓ∞\\ell\_\{\\infty\}confidence boxes and greedy selection on optimistic marginal HV gains\. The construction differs from the random HV scalarizations of\(Zhang and Golovin[2020](https://arxiv.org/html/2607.26273#bib.bib27); Zhanget al\.[2024](https://arxiv.org/html/2607.26273#bib.bib23)\)by directly exploiting the submodularity of HV in a discretekk\-armed slate setting\. Empirically,THV\-UCBachieves the*lowest cumulativeα\\alpha\-regret*and the*highest hypervolume*in all four front geometries and dimensions by a margin increasing withdd\. Theoretically, we prove a gap\-free regret boundO~​\(d​n​k​T\)\\tilde\{O\}\\\!\\left\(d\\sqrt\{nkT\}\\right\), and a gap\-dependent regret boundO~​\(n​k2\.5Δmin\)\\tilde\{O\}\\\!\\left\(\\frac\{nk^\{2\.5\}\}\{\\Delta\_\{\\min\}\}\\right\)that are polylogarithmic inTT\.

The paper is organized as follows: Related Work reviews prior literature\. Problem Setting depicts the problem setting and regret definition, while Top\-kkHyperVolume UCB presents the proposed algorithm THV\-UCB\. Regret Analysis exposes our theoretical analysis of the method and establishes upper bounds on the regret\. Finally, Experiments describes our experimental evaluation\.

## Related Work

##### Multi\-Objective Optimization \(MOO\)\.

MOO has a long history of study, with a continued stream of recent work\(Tianet al\.[2021](https://arxiv.org/html/2607.26273#bib.bib3); Ghanbarzadehet al\.[2026](https://arxiv.org/html/2607.26273#bib.bib7); Jiju and Manemaran[2025](https://arxiv.org/html/2607.26273#bib.bib16); Chenet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib26); Heet al\.[2026](https://arxiv.org/html/2607.26273#bib.bib6); Zaiziet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib17)\), extending many research fields\. Comparable recent works in deep reinforcement learning made use of hypervolume both as a quality criterion and an optimization mean to reduce the computation cost of learning the whole Pareto Front\(Zhanget al\.[2023](https://arxiv.org/html/2607.26273#bib.bib21); Caiet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib20); Chenet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib22); Leeet al\.[2026](https://arxiv.org/html/2607.26273#bib.bib13); Fernández Vicenteet al\.[2026](https://arxiv.org/html/2607.26273#bib.bib12)\)\. More specifically, HV\-driven Pareto Set Learning methods maximizes HV via gradient descent on a neural preference\-conditioned model\(Zhanget al\.[2023](https://arxiv.org/html/2607.26273#bib.bib21); Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\), while HV\-based MORL embeds HV in policy optimization\(Röpkeet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib5); Songet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib15)\)\. However, as stated by Zhang et al\.\(Zhanget al\.[2024](https://arxiv.org/html/2607.26273#bib.bib23)\), a major drawback of gradient\-based methods for hypervolume maximization is the high computational complexity in obtaining the hypervolume gradient\. While showing good results up tod=4d=4objectives, these approaches remain unpractical for an online setup\.

##### Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.

Multi\-objective multi\-armed bandits extend the classical bandit framework to vector\-valued rewards and Pareto\-based notions of optimality\. Early work introduced the setting and adapted UCB/TS principles to the multi\-objective scenario considering Pareto regret\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31); Q\. Yahyaaet al\.[2014](https://arxiv.org/html/2607.26273#bib.bib35); Yahyaa and Manderick[2015](https://arxiv.org/html/2607.26273#bib.bib42); Roijerset al\.[2017](https://arxiv.org/html/2607.26273#bib.bib38); Xu and Klabjan[2023](https://arxiv.org/html/2607.26273#bib.bib28)\)\. Following them, several works extend regret\-minimizing MOMAB through various scalarization techniques like : Chebyshev\(Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10)\), lexicographic priorities\(Hüyük and Tekin[2021](https://arxiv.org/html/2607.26273#bib.bib18)\), lexicographic linear bandits\(Xueet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib1)\), and preference\-aware customization\(Caoet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib9)\)\. A parallel line studies*pure exploration*goals, such as identifying feasible arms or approximating the Pareto set up to a relaxation tolerance, includingε\\varepsilon\-relaxed Pareto set identification, constrained variants, and best\-group Identification\(Katz\-Samuels and Scott[2018](https://arxiv.org/html/2607.26273#bib.bib36); KONEet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib19); Koneet al\.[2025b](https://arxiv.org/html/2607.26273#bib.bib30); Shahverdikondoriet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib8)\)\. These works typically aim to recover a large fraction of the Pareto set rather than maintaining a small representative*subset*of fixed sizekk\. Scalarization methods, considering either a single aggregated utility function\(Busa\-Feketeet al\.[2017](https://arxiv.org/html/2607.26273#bib.bib37); Roijerset al\.[2013](https://arxiv.org/html/2607.26273#bib.bib39),[2017](https://arxiv.org/html/2607.26273#bib.bib38); Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10)\)or several different trade\-offs\(Zhang and Golovin[2020](https://arxiv.org/html/2607.26273#bib.bib27); Letardet al\.[2024](https://arxiv.org/html/2607.26273#bib.bib11); Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24); Caoet al\.[2025](https://arxiv.org/html/2607.26273#bib.bib9); Liuet al\.[2025a](https://arxiv.org/html/2607.26273#bib.bib2),[b](https://arxiv.org/html/2607.26273#bib.bib14)\), are often most convenient for the online bandit setup\. However these methods involve a fixed distribution of preferences\(Roijerset al\.[2013](https://arxiv.org/html/2607.26273#bib.bib39),[2017](https://arxiv.org/html/2607.26273#bib.bib38); Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)and do not directly address*set\-level*hypervolume of a*size\-kkslate*under semi\-bandit feedback which is complementary to our goal of*preference\-free*coverage of the frontier\.

##### Dominated Hypervolume \(HV\) in MOMAB\.

To the best of our knowledge, little work made use of the dominated hypervolume as a learning target in MOMAB problems\. In black\-box multi\-objective optimization, random hypervolume scalarizations provide provable guarantees for exploring Pareto trade\-offs\(Zhang and Golovin[2020](https://arxiv.org/html/2607.26273#bib.bib27)\)withO~​\(T\)\\tilde\{O\}\(\\sqrt\{T\}\)HV\-regret bounds for UCB/TS Bayesian optimization\. Later, these bounds were further refined by\(Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\), who establish an optimal hypervolume regret bound ofO​\(T−1/k\)O\(T^\{\-1/k\}\)The problems studied by Kone et al\.\(KONEet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib19); Koneet al\.[2025b](https://arxiv.org/html/2607.26273#bib.bib30)\)and\(Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)are the closest to ours\. Nevertheless, despite the added diversity in arm selection decomposition methods are mainly relevant for Pareto Front Identification, with lower performance for hypervolume maximization \(see the Experiments section\)\. In terms of concept, the closest existing methods to our proposed THV\-UCB algorithm are the HV\-based approaches proposed by\(Zhanget al\.[2023](https://arxiv.org/html/2607.26273#bib.bib21)\)and\(Zhanget al\.[2024](https://arxiv.org/html/2607.26273#bib.bib23)\)from MORL literature\. However, these works do not adress the discretekk\-armed slate bandit setting we study\.

## Problem Setting

##### Arms, horizon, and rewards\.

We considernnarms indexed by\[n\]=\{1,…,n\}\[n\]=\\\{1,\\dots,n\\\}over a horizon ofTTrounds, with\[T\]=\{1,…,T\}\[T\]=\\\{1,\\dots,T\\\}\. Pulling armiiat roundttyields add\-dimensional random reward vector𝐗i,t∈\[0,1\]d\\mathbf\{X\}\_\{i,t\}\\in\[0,1\]^\{d\}with unknown mean𝝁i=𝔼​\[𝐗i,t\]\\boldsymbol\{\\mu\}\_\{i\}=\\mathbb\{E\}\[\\mathbf\{X\}\_\{i,t\}\]\. We assume\(𝐗i,t\)t∈\[T\]\(\\mathbf\{X\}\_\{i,t\}\)\_\{t\\in\[T\]\}are independent acrossttandii, and each coordinate isη\\eta\-sub\-Gaussian \(used for concentration\);η\\etaalso serves as the confidence parameter of the algorithm\.

##### Top\-kkactions and semi\-bandit feedback\.

At each roundt∈\[T\]t\\in\[T\], the agent selects a subsetSt⊆\[n\]S\_\{t\}\\subseteq\[n\]of size\|St\|=k\|S\_\{t\}\|=k\(a*slate*\) and observes the vectors\{𝐗i,t:i∈St\}\\\{\\mathbf\{X\}\_\{i,t\}:i\\in S\_\{t\}\\\}\(semi\-bandit feedback\)\.

##### Dominance and Pareto front\.

For𝐚,𝐛∈ℝd\\mathbf\{a\},\\mathbf\{b\}\\in\\mathbb\{R\}^\{d\}, write𝐚⪯𝐛\\mathbf\{a\}\\preceq\\mathbf\{b\}ifaj≤bja\_\{j\}\\leq b\_\{j\}for allj∈\[d\]j\\in\[d\], and𝐚≺𝐛\\mathbf\{a\}\\prec\\mathbf\{b\}if in addition at least one inequality is strict\. Armii*Pareto\-dominates*armjjif𝝁i⪰𝝁j\\boldsymbol\{\\mu\}\_\{i\}\\succeq\\boldsymbol\{\\mu\}\_\{j\}and𝝁i≠𝝁j\\boldsymbol\{\\mu\}\_\{i\}\\neq\\boldsymbol\{\\mu\}\_\{j\}\. The Pareto front𝒫\\mathcal\{P\}is the set of undominated mean vectors\{𝝁i:i∈\[n\]\}\\\{\\boldsymbol\{\\mu\}\_\{i\}:i\\in\[n\]\\\}\.

##### Reference point and dominated hypervolume\.

Fix a reference point𝐫∈ℝd\\mathbf\{r\}\\in\\mathbb\{R\}^\{d\}such that𝐫⪯𝝁i\\mathbf\{r\}\\preceq\\boldsymbol\{\\mu\}\_\{i\}for alli∈\[n\]i\\in\[n\]\(e\.g\.,𝐫=𝟎\\mathbf\{r\}=\\mathbf\{0\}when rewards lie in\[0,1\]d\[0,1\]^\{d\}\)\. For any subsetS⊆\[n\]S\\subseteq\[n\], its dominated hypervolume is

HV​\(S\)=λd​\(⋃i∈S\[r1,μi​1\]×⋯×\[rd,μi​d\]\)\\mathrm\{HV\}\(S\)=\\lambda\_\{d\}\\\!\\left\(\\bigcup\_\{i\\in S\}\[r\_\{1\},\\mu\_\{i1\}\]\\times\\cdots\\times\[r\_\{d\},\\mu\_\{id\}\]\\right\)\(1\)whereλd\\lambda\_\{d\}is thedd\-dimensional Lebesgue measure\.The dominated hypervolume is a standard performance indicator in multi\-objective optimization\(Zitzleret al\.[2003](https://arxiv.org/html/2607.26273#bib.bib40)\)\.111Any equivalent definition of dominated hypervolume can be used\. Our analysis only relies on monotonicity and submodularity ofHV​\(⋅\)\\mathrm\{HV\}\(\\cdot\)as a set function over mean vectors\.

##### Performance metric: \(approximation\) hypervolume regret\.

We evaluate performance in terms of pseudo\-regret with respect to the mean rewards\(Bubeck and Cesa\-Bianchi[2012](https://arxiv.org/html/2607.26273#bib.bib44)\)\. LetS⋆∈arg⁡max\|S\|=k⁡HV​\(S\)S^\{\\star\}\\in\\arg\\max\_\{\|S\|=k\}\\mathrm\{HV\}\(S\)denote a best subset of sizekkin hindsight, andV⋆=HV​\(S⋆\)V^\{\\star\}=\\mathrm\{HV\}\(S^\{\\star\}\)its hypervolume\. The \(ideal\) instantaneous regret and cumulative regret are

rt=V⋆−HV​\(St\),RT=∑t=1Trt\.r\_\{t\}=V^\{\\star\}\-\\mathrm\{HV\}\(S\_\{t\}\),\\quad R\_\{T\}=\\sum\_\{t=1\}^\{T\}r\_\{t\}\.Since maximizing a monotone submodular function under a cardinality constraint is NP\-hard and typically addressed by greedy selection, which achieves approximation factorα=1−1/e\\alpha=1\-1/e, our guarantees are stated for theα\\alpha\-approximation regret

r¯t=α​V⋆−HV​\(St\),R¯T=∑t=1Tr¯t\.\\bar\{r\}\_\{t\}=\\alpha V^\{\\star\}\-\\mathrm\{HV\}\(S\_\{t\}\),\\quad\\bar\{R\}\_\{T\}=\\sum\_\{t=1\}^\{T\}\\bar\{r\}\_\{t\}\.\(2\)This benchmark cleanly separates computational approximation \(theα\\alphafactor, unavoidable for any polynomial\-time algorithm\) from statistical learning \(the gap betweenHV​\(St\)\\mathrm\{HV\}\(S\_\{t\}\)and what the algorithm could achieve with known means\)\.

##### Additional notation\.

We writelog\\logfor the natural logarithm andO~​\(⋅\)\\tilde\{O\}\(\\cdot\)to hide polylogarithmic factors\. Vectors are bold lowercase, sets uppercase, and∥⋅∥∞\\\|\\cdot\\\|\_\{\\infty\}denotes theℓ∞\\ell\_\{\\infty\}norm\. For any armii, letNi​\(t\)N\_\{i\}\(t\)be the number of timesiihas been selected up to \(and including\) roundtt, and let𝝁^i​\(t\)\\widehat\{\\boldsymbol\{\\mu\}\}\_\{i\}\(t\)denote its empirical mean vector\. Table[7](https://arxiv.org/html/2607.26273#A3.T7)in the appendix\.

## Top\-kkHyperVolume UCB \(THV\-UCB\)

We now presentTHV\-UCB, an optimistic algorithm that maintains coordinate\-wise UCB boxes for each arm’s mean vector and constructs at every round a size\-kksubset by greedily maximizing the*optimistic*marginal hypervolume gain\.

##### UCB boxes \(coordinate\-wise optimism\)\.

At roundtt, for every armiiand objectivejj, we form an upper confidence bound

ui,j​\(t\)=μ^i,j​\(t−1\)\+βi​\(t\)u\_\{i,j\}\(t\)=\\widehat\{\\mu\}\_\{i,j\}\(t\-1\)\\;\+\\;\\beta\_\{i\}\(t\)with

βi​\(t\)=2​η​log⁡\(n​d​t2/δ\)max⁡\{1,Ni​\(t−1\)\}\\beta\_\{i\}\(t\)=\\sqrt\{\\frac\{2\\eta\\log\\\!\(nd\\,t^\{2\}/\\delta\)\}\{\\max\\\{1,N\_\{i\}\(t\-1\)\\\}\}\}whereη\>0\\eta\>0is a confidence parameter andδ∈\(0,1\)\\delta\\in\(0,1\)is the target failure probability\. This yields an optimistic vector𝐮i​\(t\)=\(ui,1​\(t\),…,ui,d​\(t\)\)\\mathbf\{u\}\_\{i\}\(t\)=\(u\_\{i,1\}\(t\),\\dots,u\_\{i,d\}\(t\)\)\. Optionally, since rewards lie in\[0,1\]d\[0,1\]^\{d\}, we clip𝐮i​\(t\)\\mathbf\{u\}\_\{i\}\(t\)coordinate\-wise to\[0,1\]\[0,1\]\.

##### THV\-UCB: Greedy Subset Construction\.

Algorithm[1](https://arxiv.org/html/2607.26273#alg1)describes our proposed methodTHV\-UCB222The code ofTHV\-UCBis available in our GitHub repositoryhttps://github\.com/ngutowski/topk\-pareto\-bandits, which aims to maximize the hypervolume defined in \([1](https://arxiv.org/html/2607.26273#Sx3.E1)\) via a greedy construction of the subsetStS\_\{t\}based on optimistic estimates\. After an initialization phase, the algorithm computes UCB\-based confidence intervals for each arm and applies a safe pruning step to form a candidate setAtA\_\{t\}of arms that are not confidently dominated, i\.e\., arms that may still contribute to an optimal solution\.

The optimistic hypervolumeH​VtUCB​\(S\)HV\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)is obtained by replacing the unknown meansμi,j\\mu\_\{i,j\}in \([1](https://arxiv.org/html/2607.26273#Sx3.E1)\) with their UCB counterpartsui,j​\(t\)u\_\{i,j\}\(t\)\. For any setS⊆\[n\]S\\subseteq\[n\]and armi∉Si\\notin S, we define the marginal UCB hypervolume gain asΔHV,tUCB​\(i∣S\)=H​VtUCB​\(S∪\{i\}\)−H​VtUCB​\(S\)\.\\Delta^\{\\mathrm\{UCB\}\}\_\{\\mathrm\{HV\},t\}\(i\\mid S\)=HV\_\{t\}^\{\\mathrm\{UCB\}\}\(S\\cup\\\{i\\\}\)\-HV\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)\.

The subsetStS\_\{t\}is then constructed greedily: starting fromS=∅S=\\emptyset, arms are sequentially added by maximizingΔHV,tUCB​\(i∣S\)\\Delta^\{\\mathrm\{UCB\}\}\_\{\\mathrm\{HV\},t\}\(i\\mid S\)\. This procedure yields a\(1−1/e\)\(1\-1/e\)\-approximation ofmax\|S\|=k⁡H​VtUCB​\(S\),\\max\_\{\|S\|=k\}HV\_\{t\}^\{\\mathrm\{UCB\}\}\(S\),by standard results on monotone submodular maximization\. The selected arms inStS\_\{t\}are then pulled and the statistics updated\.

From a computational perspective, computingΔHV,tUCB​\(i∣S\)\\Delta^\{\\mathrm\{UCB\}\}\_\{\\mathrm\{HV\},t\}\(i\\mid S\)for all candidates at each greedy step leads to a per\-round complexity ofO​\(k​n⋅costHV\)O\(kn\\cdot\\mathrm\{costHV\}\), wherecostHV\\mathrm\{costHV\}denotes the cost of updating the hypervolume\. In practice, incremental updates, dominance pruning, and the regimek≪nk\\ll nmake the greedy selection efficient\.

Algorithm 1THV\-UCB: Top\-kkHyperVolume UCB1:Input:subset size

kk, reference point

𝐫\\mathbf\{r\}, confidence parameter

η\\eta, failure level

δ\\delta, horizon

TT, minimum pulls

m0≥1m\_\{0\}\\geq 1\(default:

m0=2m\_\{0\}=2\)

2:Init:

Ni​\(0\)←0N\_\{i\}\(0\)\\leftarrow 0,

𝝁^i​\(0\)←𝟎\\widehat\{\\boldsymbol\{\\mu\}\}\_\{i\}\(0\)\\leftarrow\\mathbf\{0\}for all

i∈\[n\]i\\in\[n\]; set

t←1t\\leftarrow 1
3:while

∃i∈\[n\]\\exists\\,i\\in\[n\]s\.t\.

Ni​\(t−1\)<m0N\_\{i\}\(t\-1\)<m\_\{0\}do

4:

St←S\_\{t\}\\leftarrowthe

kkarms with smallest

Ni​\(t−1\)N\_\{i\}\(t\-1\)\(ties broken arbitrarily\)

5:Play all arms in

StS\_\{t\}, observe

\{𝐗i,t:i∈St\}\\\{\\mathbf\{X\}\_\{i,t\}:i\\in S\_\{t\}\\\}, update

Ni​\(t\)N\_\{i\}\(t\),

𝝁^i​\(t\)\\widehat\{\\boldsymbol\{\\mu\}\}\_\{i\}\(t\)
6:

t←t\+1t\\leftarrow t\+1
7:endwhile

8:for

ttto

TTdo

9:foreach arm

i∈\[n\]i\\in\[n\]do

10:

βi​\(t\)←2​η​log⁡\(n​d​t2/δ\)max⁡\{1,Ni​\(t−1\)\}\\beta\_\{i\}\(t\)\\leftarrow\\sqrt\{\\dfrac\{2\\eta\\log\(nd\\,t^\{2\}/\\delta\)\}\{\\max\\\{1,N\_\{i\}\(t\-1\)\\\}\}\}
11:

𝐮i​\(t\)←𝝁^i​\(t−1\)\+βi​\(t\)​1d\\mathbf\{u\}\_\{i\}\(t\)\\leftarrow\\widehat\{\\boldsymbol\{\\mu\}\}\_\{i\}\(t\-1\)\+\\beta\_\{i\}\(t\)\\,\\mathbf\{1\}\_\{d\}
12:

𝐋i​\(t\)←𝝁^i​\(t−1\)−βi​\(t\)​1d\\mathbf\{L\}\_\{i\}\(t\)\\leftarrow\\widehat\{\\boldsymbol\{\\mu\}\}\_\{i\}\(t\-1\)\-\\beta\_\{i\}\(t\)\\,\\mathbf\{1\}\_\{d\}
13:endfor

14:Safe pruning:

15:

At←\{i∈\[n\]:∀j≠i,𝐮i​\(t\)⋠𝐋j​\(t\)\}A\_\{t\}\\leftarrow\\\{i\\in\[n\]:\\forall\\,j\\neq i,\\ \\mathbf\{u\}\_\{i\}\(t\)\\npreceq\\mathbf\{L\}\_\{j\}\(t\)\\\}
16:if

\|At\|<k\|A\_\{t\}\|<k, set

At←\[n\]A\_\{t\}\\leftarrow\[n\]
17:

S←∅S\\leftarrow\\emptyset
18:while

\|S\|<k\|S\|<kdo

19:Select

i⋆∈arg⁡maxi∈At∖S⁡ΔHV,tUCB​\(i∣S\)i^\{\\star\}\\in\\arg\\max\_\{i\\in A\_\{t\}\\setminus S\}\\Delta^\{\\mathrm\{UCB\}\}\_\{\\mathrm\{HV\},t\}\(i\\mid S\)
20:

S←S∪\{i⋆\}S\\leftarrow S\\cup\\\{i^\{\\star\}\\\}
21:endwhile

22:Play all arms in

SS, observe

\{𝐗i,t:i∈S\}\\\{\\mathbf\{X\}\_\{i,t\}:i\\in S\\\}, update

Ni​\(t\)N\_\{i\}\(t\),

𝝁^i​\(t\)\\widehat\{\\boldsymbol\{\\mu\}\}\_\{i\}\(t\)for

i∈Si\\in S
23:endfor

## Regret Analysis

We establish two complementary guarantees on theα\\alpha\-approximation hypervolume regret of THV\-UCB: a*gap\-free*bound, valid on every instance regardless of how close the arms are to each other, and a*gap\-dependent*bound, which becomes polylogarithmic inTTas soon as the instance is well separated\. Since maximizing hypervolume under a cardinality constraint is NP\-hard, THV\-UCB relies on greedy maximization of a monotone submodular optimistic objective, and both guarantees are stated for theα\\alpha\-regretR¯T\\bar\{R\}\_\{T\}withα=1−1/e\\alpha=1\-1/e\.

##### Benchmark and separation quantity\.

RecallS⋆∈arg⁡max\|S\|=k⁡HV​\(S\)S^\{\\star\}\\in\\arg\\max\_\{\|S\|=k\}\\mathrm\{HV\}\(S\)andV⋆=HV​\(S⋆\)V^\{\\star\}=\\mathrm\{HV\}\(S^\{\\star\}\)defined in \(2\)\. For the gap\-dependent analysis, we introduce a second, purely proof\-internal benchmark: letG⋆=\{i1⋆,…,ik⋆\}G^\{\\star\}=\\\{i^\{\\star\}\_\{1\},\\dots,i^\{\\star\}\_\{k\}\\\}be built by greedy maximization of the*true*marginal gainsΔ​\(i∣S\)=HV​\(S∪\{i\}\)−HV​\(S\)\\Delta\(i\\mid S\)=\\mathrm\{HV\}\(S\\cup\\\{i\\\}\)\-\\mathrm\{HV\}\(S\), i\.e\.iℓ⋆∈arg⁡maxi∉Gℓ−1⋆⁡Δ​\(i∣Gℓ−1⋆\)i^\{\\star\}\_\{\\ell\}\\in\\arg\\max\_\{i\\notin G^\{\\star\}\_\{\\ell\-1\}\}\\Delta\(i\\mid G^\{\\star\}\_\{\\ell\-1\}\), withGℓ⋆=Gℓ−1⋆∪\{iℓ⋆\}G^\{\\star\}\_\{\\ell\}=G^\{\\star\}\_\{\\ell\-1\}\\cup\\\{i^\{\\star\}\_\{\\ell\}\\\}andG0⋆=∅G^\{\\star\}\_\{0\}=\\emptyset\. Assuming the greedy maximizer is unique at every stage, define the stage\-ℓ\\ellgaps and the minimum gapΔℓ​\(i\)=Δ​\(iℓ⋆∣Gℓ−1⋆\)−Δ​\(i∣Gℓ−1⋆\),Δmin=minℓ∈\[k\]⁡mini≠iℓ⋆⁡Δℓ​\(i\)\\Delta\_\{\\ell\}\(i\)=\\Delta\(i^\{\\star\}\_\{\\ell\}\\mid G^\{\\star\}\_\{\\ell\-1\}\)\-\\Delta\(i\\mid G^\{\\star\}\_\{\\ell\-1\}\),\\Delta\_\{\\min\}=\\min\_\{\\ell\\in\[k\]\}\\min\_\{i\\neq i^\{\\star\}\_\{\\ell\}\}\\Delta\_\{\\ell\}\(i\)\.

Note thatG⋆G^\{\\star\}never appears in the regret definition: the regret is always measured againstV⋆V^\{\\star\};G⋆G^\{\\star\}only serves to track the algorithm’s stage\-wise greedy progress in the analysis\.

We writeℰ\\mathcal\{E\}for the event on which all coordinate\-wise confidence intervals are valid simultaneously; by a standard sub\-Gaussian concentration argument and a union bound \(Lemma[2](https://arxiv.org/html/2607.26273#Thmlemma2), see the appendix\) ,ℙ​\(ℰ\)≥1−δ\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-\\delta\. Finally,CdC\_\{d\}denotes the coordinate\-wise Lipschitz constant of the hypervolume; one may takeCd≤dC\_\{d\}\\leq dwhen rewards lie in\[0,1\]d\[0,1\]^\{d\}andr=0r=0\. \(Lemma[3](https://arxiv.org/html/2607.26273#Thmlemma3), see the appendix\)\.

###### Theorem 1\(Gap\-free bound \(short version\)\)\.

Assume each reward coordinate isη\\eta\-sub\-Gaussian and bounded in\[0,1\]\[0,1\]\. Onℰ\\mathcal\{E\},

R¯T=O​\(Cd​n​k​T​log⁡T\)\.\\bar\{R\}\_\{T\}\\;=\\;O\\\!\\left\(C\_\{d\}\\sqrt\{nkT\\log T\}\\right\)\.

###### Theorem 2\(Gap\-dependent bound \(short version\)\)\.

Under the same assumptions, if the greedy maximizer ofG⋆G^\{\\star\}is unique at every stage and the safe\-pruning step never eliminates an arm ofG⋆G^\{\\star\}, then onℰ\\mathcal\{E\},

R¯T=O​\(n​k2\.5​log⁡TΔmin\)\.\\bar\{R\}\_\{T\}\\;=\\;O\\\!\\left\(\\frac\{nk^\{2\.5\}\\log T\}\{\\Delta\_\{\\min\}\}\\right\)\.

###### Theorem 3\(Regret of THV\-UCB \(short version\)\)\.

Withδ=1/T\\delta=1/T,

𝔼​\[R¯T\]≤\\displaystyle\\mathbb\{E\}\\big\[\\bar\{R\}\_\{T\}\\big\]\\leq\{\}min\{O\(n​k​T​log⁡T\),\\displaystyle\\min\\Bigl\\\{O\\left\(\\sqrt\{nkT\\log T\}\\right\),O\(n​k2\.5​log⁡TΔmin\)\}\+O\(1\)\.\\displaystyle O\\left\(\\frac\{nk^\{2\.5\}\\log T\}\{\\Delta\_\{\\min\}\}\\right\)\\Bigr\\\}\+O\(1\)\.
In particular𝔼​\[R¯T\]/T→0\\mathbb\{E\}\[\\bar\{R\}\_\{T\}\]/T\\to 0: THV\-UCB achieves sublinearα\\alpha\-approximation regret on every instance\.

##### Proof sketch\.

Both bounds share the same reduction, then diverge\.

*\(1\) Optimism reduction\.*Onℰ\\mathcal\{E\}, coordinate\-wise optimism givesHV​\(S\)≤HVtUCB​\(S\)\\mathrm\{HV\}\(S\)\\leq\\mathrm\{HV\}^\{\\mathrm\{UCB\}\}\_\{t\}\(S\)for everySS\. SinceHVtUCB\\mathrm\{HV\}^\{\\mathrm\{UCB\}\}\_\{t\}is itself monotone submodular, the greedy construction ofStS\_\{t\}is a\(1−1/e\)\(1\-1/e\)\-approximation of its maximizer, henceHVtUCB​\(St\)≥α​HVtUCB​\(S⋆\)\\mathrm\{HV\}^\{\\mathrm\{UCB\}\}\_\{t\}\(S\_\{t\}\)\\geq\\alpha\\,\\mathrm\{HV\}^\{\\mathrm\{UCB\}\}\_\{t\}\(S^\{\\star\}\), andr¯t≤HVtUCB​\(St\)−HV​\(St\)\.\\bar\{r\}\_\{t\}\\;\\leq\\;\\mathrm\{HV\}^\{\\mathrm\{UCB\}\}\_\{t\}\(S\_\{t\}\)\-\\mathrm\{HV\}\(S\_\{t\}\)\.

*\(2\) Lipschitz control\.*The hypervolume is coordinate\-wise Lipschitz, so the optimism error is at mostCd​∑i∈Stβi​\(t\)C\_\{d\}\\sum\_\{i\\in S\_\{t\}\}\\beta\_\{i\}\(t\), reducing the regret to a sum of confidence radii\.

*\(3a\) Gap\-free control\.*Reordering the double sum by arm and applying Cauchy–Schwarz over the whole horizon, using∑iNi​\(T\)=k​T\\sum\_\{i\}N\_\{i\}\(T\)=kT, yields Theorem[1](https://arxiv.org/html/2607.26273#Thmtheorem1)\. This step is blind to the selection mechanism: it only uses\|St\|=k\|S\_\{t\}\|=kandβi​\(t\)=Θ​\(1/Ni​\(t−1\)\)\\beta\_\{i\}\(t\)=\\Theta\(1/\\sqrt\{N\_\{i\}\(t\-1\)\}\)\.

*\(3b\) Gap\-dependent control\.*We instead track, at each round, the first stageℓ\\ellat which the algorithm’s greedy chain departs fromG⋆G^\{\\star\}\. On*matched*rounds \(St=G⋆S\_\{t\}=G^\{\\star\}\) theα\\alpha\-regret is non\-positive\. On*deviation*rounds, a witness\-counting argument shows that some arm in the current prefix must still have a large confidence radius, which caps the number of stage\-ℓ\\elldeviations atO​\(n​ℓ2​log⁡T/Δmin2\)O\(n\\ell^\{2\}\\log T/\\Delta\_\{\\min\}^\{2\}\); applying the Cauchy–Schwarz argument of \(3a\)*locally*to these rounds converts this1/Δmin21/\\Delta\_\{\\min\}^\{2\}count into a1/Δmin1/\\Delta\_\{\\min\}regret contribution\. Summing over stages yields Theorem[2](https://arxiv.org/html/2607.26273#Thmtheorem2)\.

A discussion and the detailed versions of Theorems[1](https://arxiv.org/html/2607.26273#Thmtheorem1),[2](https://arxiv.org/html/2607.26273#Thmtheorem2)and[3](https://arxiv.org/html/2607.26273#Thmtheorem3)together with their full proofs, with all supporting lemmas and the corollary invoked above, are given in the appendix and in our GitHub repositoryhttps://github\.com/ngutowski/topk\-pareto\-bandits\.

## Experiments

We empirically evaluateTHV\-UCBon controlled synthetic multi\-objective bandit instancesacross four Pareto front geometries and four dimensions \(d∈\{2,3,4,5\}d\\in\\\{2,3,4,5\\\}, with slate sizek∈\{3,4,5,6\}k\\in\\\{3,4,5,6\\\}and correspondingly varying total number of available armsnnand horizonTT\),and compare it to representative baselines from the MO\-bandit literature as well as scalarization\-based methodsadapted to the top\-kksemi\-bandit setting\.

Experiments are conducted ford∈\{2,3,4,5\}d\\in\\\{2,3,4,5\\\}objectives\. The dominated hypervolume\(Zitzleret al\.[2003](https://arxiv.org/html/2607.26273#bib.bib40)\)is computed exactly via inclusion\-exclusion over thekk\-point slate, which remains tractable for smallkk\. Figure[1](https://arxiv.org/html/2607.26273#Sx6.F1)to[4](https://arxiv.org/html/2607.26273#Sx6.F4)and Table[1](https://arxiv.org/html/2607.26273#Sx6.T1)report results ford=2d=2; full results ford∈\{3,4,5\}d\\in\\\{3,4,5\\\}, along with the grid search over the confidence parameterη\\etaare provided in the appendix and in our GitHub repositoryhttps://github\.com/ngutowski/topk\-pareto\-bandits\(Tables[2](https://arxiv.org/html/2607.26273#A2.T2),[3](https://arxiv.org/html/2607.26273#A2.T3),[4](https://arxiv.org/html/2607.26273#A2.T4), and[5](https://arxiv.org/html/2607.26273#A2.T5), Figures[5](https://arxiv.org/html/2607.26273#A2.F5),[6](https://arxiv.org/html/2607.26273#A2.F6), and[7](https://arxiv.org/html/2607.26273#A2.F7)\)\. Moreover, note that all experiments were run on CPU only \(Intel Xeon E5\-2695 v4, 2\.10 GHz, 45 MB cache\), using Python 3\.11\.2, NumPy 1\.24\.2, and Matplotlib 3\.6\.3 for figure generation\.

### Protocol and Metrics ford=2d=2andk=3k=3

Unless stated otherwise, experiments used=2d=2,n=36n=36,k=3k=3, horizonT=2000T=2000, Gaussian noise levelσ=0\.05\\sigma=0\.05, reference point𝐫=𝟎∈ℝd\\mathbf\{r\}=\\mathbf\{0\}\\in\\mathbb\{R\}^\{d\}, and results are averaged over1010random seeds\.

##### Computing the benchmarkV⋆V^\{\\star\}\.

Ford=2d=2,V⋆V^\{\\star\}is computed by exhaustive enumeration over all\(nk\)\\binom\{n\}\{k\}candidate subsets\. Ford≥3d\\geq 3, exhaustive enumeration becomes intractable, so we reportHV​\(G⋆\)≥α​V⋆\\mathrm\{HV\}\(G^\{\\star\}\)\\geq\\alpha V^\{\\star\}\(see Fact[1](https://arxiv.org/html/2607.26273#Thmfact1)in the appendix\), a valid conservative proxy that does not affect relative comparisons between methods\.

At each round, we evaluate the selected slateStS\_\{t\}using the pseudo\-hypervolumeHV​\(\{𝝁i:i∈St\}\)\\mathrm\{HV\}\(\\\{\\boldsymbol\{\\mu\}\_\{i\}:i\\in S\_\{t\}\\\}\)computed from the true means, to remove observation noise from the metrics\. We report two complementary metrics: \(i\) the cumulativeα\\alpha\-regret∑t=1T\(α​V⋆−HV​\(St\)\)\\sum\_\{t=1\}^\{T\}\\bigl\(\\alpha V^\{\\star\}\-\\mathrm\{HV\}\(S\_\{t\}\)\\bigr\), whereα=1−1/e\\alpha=1\-1/e, which can be negative when a method consistently attains hypervolume aboveα​V⋆\\alpha V^\{\\star\}; and \(ii\) the hypervolume trajectoryHV​\(St\)\\mathrm\{HV\}\(S\_\{t\}\), plotted as a moving average \(windoww=50w=50\) with95%95\\%confidence intervals across seeds\.

### Synthetic Environments

We generate instances by mixing a structured Pareto frontier with dominated distractors\. A fractionnfront=max⁡\{10,⌊0\.35​n⌋\}n\_\{\\mathrm\{front\}\}=\\max\\\{10,\\lfloor 0\.35n\\rfloor\\\}arms lie on a parametric frontier defined via the angular parameterization of DTLZ\(Debet al\.[2005](https://arxiv.org/html/2607.26273#bib.bib43)\), while the remainingndom=n−nfrontn\_\{\\mathrm\{dom\}\}=n\-n\_\{\\mathrm\{front\}\}arms are strictly dominated points sampled uniformly in\[0,0\.3\]d\[0,0\.3\]^\{d\}\. Rewards are observed with additive Gaussian noise𝒩​\(0,σ2\)\\mathcal\{N\}\(0,\\sigma^\{2\}\)and clipped to\[0,1\]d\[0,1\]^\{d\}\.

The frontier is parameterized byd−1d\-1anglesθj∼𝒰​\[0,π/2\]\\theta\_\{j\}\\sim\\mathcal\{U\}\[0,\\pi/2\], with coordinates:

xi=\(∏j=0i−1sinα⁡\(θj\)\)⋅\{cosα⁡\(θi\)if​i<d−1,1if​i=d−1,\{\\color\[rgb\]\{0,0,0\}x\_\{i\}=\\left\(\\prod\_\{j=0\}^\{i\-1\}\\sin^\{\\alpha\}\(\\theta\_\{j\}\)\\right\)\\cdot\}\\begin\{cases\}\{\\color\[rgb\]\{0,0,0\}\\cos^\{\\alpha\}\(\\theta\_\{i\}\)\}&\{\\color\[rgb\]\{0,0,0\}\\text\{if \}i<d\-1,\}\\\\ \{\\color\[rgb\]\{0,0,0\}1\}&\{\\color\[rgb\]\{0,0,0\}\\text\{if \}i=d\-1,\}\\end\{cases\}where the shape exponentα\\alphacontrols the front geometry\. We consider four geometries: concave \(α=1\.0\\alpha=1\.0, spherical front with∑ixi2=1\\sum\_\{i\}x\_\{i\}^\{2\}=1, following DTLZ2\(Debet al\.[2005](https://arxiv.org/html/2607.26273#bib.bib43)\)\); convex \(α=0\.5\\alpha=0\.5, outward\-bulging front with∑ixi4=1\\sum\_\{i\}x\_\{i\}^\{4\}=1\); linear \(α=2\.0\\alpha=2\.0, simplex\-like front\); and clusters \(α=1\.0\\alpha=1\.0, spherical front with two disjoint angular regions,θ1∈\[0,π/5\]\\theta\_\{1\}\\in\[0,\\pi/5\]for cluster 1 andθ1∈\[3​π/10,π/2\]\\theta\_\{1\}\\in\[3\\pi/10,\\pi/2\]for cluster 2, with remaining angles free in\[0,π/2\]\[0,\\pi/2\]\)\.

For the linear geometry, the raw simplex coordinates collapse toward zero asddgrows, making the dominated hypervolume uninformative\. We therefore rescale the frontier points by a factors=min⁡\(0\.45​d,2\.5\)s=\\min\(0\.45d,\\,2\.5\)and clip to\[0\.01,1\]d\[0\.01,1\]^\{d\}, which preserves a non\-degenerate HV across dimensions while keeping coordinates in\[0,1\]d\[0,1\]^\{d\}\.

### Baselines

THV\-UCB is compared against four learning\-based families of baselines adapted to the top\-kksemi\-bandit setting, plus a non\-learning baseline: 1\) Pareto\-layer UCB methods \(ParetoUCB,ParetoUCB\-Div,ParetoUCB\-Crowd\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31); Debet al\.[2002](https://arxiv.org/html/2607.26273#bib.bib32)\)\); 2\) Pareto\-layer Thompson Sampling methods \(ParetoTS,ParetoTS\+\(Yahyaa and Manderick[2015](https://arxiv.org/html/2607.26273#bib.bib42)\)\); 3\) Chebyshev scalarization methods \(ChebyshevUCB,ChebyshevUCB\+\(Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10)\)\); 4\) linear and hypervolume scalarization methods \(ScalarUCB\(Aueret al\.[2002](https://arxiv.org/html/2607.26273#bib.bib33)\),ScalarUCB\-RandW\(Pariaet al\.[2020](https://arxiv.org/html/2607.26273#bib.bib34)\),HVScalarUCB\(Zhang and Golovin[2020](https://arxiv.org/html/2607.26273#bib.bib27)\),HVScalarUCB\+\(Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)\); and 5\)RandomK, which selects a slate uniformly at random\. The\+suffix marks our extension when both versions share a citation\.All methods share the same initialization scheme \(forced round\-robin sampling until each arm has been pulled at leastmin\_pullstimes\) to avoid degenerate early behavior\.

Implementation details, including UCB bonuses, posterior parameterizations, and tie\-breaking rules, are as follows:

1. 1\.ParetoUCBfamily - •ParetoUCB\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31)\)computes UCB vectorsUi=μ^i\+βi​𝟏U\_\{i\}=\\hat\{\\mu\}\_\{i\}\+\\beta\_\{i\}\\mathbf\{1\}and selectskkarms by iterating Pareto layers onUU, using a∑jUi​j\\sum\_\{j\}U\_\{ij\}tie\-break within each layer\. The faithful variant \(ParetoUCB\) uses the original confidence termβi=2​log⁡\(t⋅\(d⋅\|ℱ^\|\)1/4\)/Ni\\beta\_\{i\}=\\sqrt\{2\\log\(t\\cdot\(d\\cdot\|\\hat\{\\mathcal\{F\}\}\|\)^\{1/4\}\)/N\_\{i\}\}where\|ℱ^\|\|\\hat\{\\mathcal\{F\}\}\|is the empirical Pareto front size, with uniform random selection within each layer\. - •ParetoUCB\-Div\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31)\)extendsParetoUCBby replacing the∑U\\sum Utie\-break with a farthest\-point \(maximinℓ∞\\ell\_\{\\infty\}\) diversity criterion: each slot greedily picks the candidate maximally distant from already\-selected arms in UCB space\. - •ParetoUCB\-Crowd\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31); Debet al\.[2002](https://arxiv.org/html/2607.26273#bib.bib32)\)replaces the tie\-break with a crowding distance\(Debet al\.[2002](https://arxiv.org/html/2607.26273#bib.bib32)\): within each Pareto layer, arms are ranked by their normalized inter\-neighbor gap across objectives, favoring spread along the frontier\.
2. 2\.ParetoTSfamily - •ParetoTS\(Yahyaa and Manderick[2015](https://arxiv.org/html/2607.26273#bib.bib42)\)maintains a Gaussian posterior per arm and coordinate\. At each round it samplesθi∼𝒩​\(μ^i,σi2​𝐈\)\\theta\_\{i\}\\sim\\mathcal\{N\}\(\\hat\{\\mu\}\_\{i\},\\sigma\_\{i\}^\{2\}\\mathbf\{I\}\)with posterior standard deviationσi=σobs/Ni\\sigma\_\{i\}=\\sigma\_\{\\mathrm\{obs\}\}/\\sqrt\{N\_\{i\}\}\(conjugate Gaussian\), builds Pareto layers on the sampled vectors, and selectskkarms by uniform random sampling within each layer\. The only change from the original is the top\-kkextension\. - •ParetoTS\+\(Yahyaa and Manderick[2015](https://arxiv.org/html/2607.26273#bib.bib42)\)uses a heuristic posteriorσi2=\(σprior2\+σobs2\)/Ni\\sigma\_\{i\}^\{2\}=\(\\sigma\_\{\\mathrm\{prior\}\}^\{2\}\+\\sigma\_\{\\mathrm\{obs\}\}^\{2\}\)/N\_\{i\}that decays more slowly, combined with a∑jθi​j\\sum\_\{j\}\\theta\_\{ij\}tie\-break to encourage diversity within each Pareto layer\.
3. 3\.ChebyshevUCBfamily - •ChebyshevUCB\(Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10)\)follows Algorithm C2 of\(Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10)\): a set ofSSscalarization functions with weights spread uniformly on the simplex is precomputed, a functionfjf^\{j\}is drawn uniformly at each round, and arms are scored byminℓ⁡\{wℓj​\(Ui​ℓ−zℓ\)\}\\min\_\{\\ell\}\\\{w^\{j\}\_\{\\ell\}\(U\_\{i\\ell\}\-z\_\{\\ell\}\)\\\}wherezzis an estimated nadir point andUi=μ^i\+βi​𝟏U\_\{i\}=\\hat\{\\mu\}\_\{i\}\+\\beta\_\{i\}\\mathbf\{1\}is the UCB vector\. - •ChebyshevUCB\+\(Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10)\)fixesw=𝟏/dw=\\mathbf\{1\}/duniformly instead of drawingfjf^\{j\}randomly, and uses the standard UCB bonusβi=η​log⁡\(n​d​T2\)/\(2​Ni\)\\beta\_\{i\}=\\sqrt\{\\eta\\log\(ndT^\{2\}\)/\(2N\_\{i\}\)\}\.
4. 4\.ScalarUCBfamily - •ScalarUCB\(Aueret al\.[2002](https://arxiv.org/html/2607.26273#bib.bib33)\)reduces the vector reward to a scalar via a fixed uniform linear scalarizationw=𝟏/dw=\\mathbf\{1\}/d, maintains a scalar mean estimate per arm, and selects the top\-kkarms by UCB indexμ^i\+βi\\hat\{\\mu\}\_\{i\}\+\\beta\_\{i\}whereβi=η​log⁡\(n​T2\)/\(2​Ni\)\\beta\_\{i\}=\\sqrt\{\\eta\\log\(nT^\{2\}\)/\(2N\_\{i\}\)\}\. - •ScalarUCB\-RandW\(Pariaet al\.[2020](https://arxiv.org/html/2607.26273#bib.bib34)\)draws a fresh weight vectorw∼Dirichlet​\(𝟏\)w\\sim\\mathrm\{Dirichlet\}\(\\mathbf\{1\}\)at each round, computes UCB vectorsUi=μ^i\+βi​𝟏U\_\{i\}=\\hat\{\\mu\}\_\{i\}\+\\beta\_\{i\}\\mathbf\{1\}coordinate\-wise, and selects the top\-kkarms by scorew⊤​Uiw^\{\\top\}U\_\{i\}\. - •HVScalarUCB\(Zhang and Golovin[2020](https://arxiv.org/html/2607.26273#bib.bib27)\)drawsλ∼S\+d−1\\lambda\\sim S^\{d\-1\}\_\{\+\}\(positive unit sphere\) at each round and scores arms by the hypervolume scalarizationsλ​\(Ui\)=\(minℓ⁡max⁡\(0,Ui​ℓ/λℓ\)\)ds\_\{\\lambda\}\(U\_\{i\}\)=\\bigl\(\\min\_\{\\ell\}\\max\(0,U\_\{i\\ell\}/\\lambda\_\{\\ell\}\)\\bigr\)^\{d\}\(Lemma 5 of\(Zhang and Golovin[2020](https://arxiv.org/html/2607.26273#bib.bib27)\)\), selecting the top\-kkarms by score\. - •HVScalarUCB\+\(Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)drawskkindependent directionsλ\(1\),…,λ\(k\)∼S\+d−1\\lambda^\{\(1\)\},\\ldots,\\lambda^\{\(k\)\}\\sim S^\{d\-1\}\_\{\+\}per round and assigns one arm per direction:a\(j\)=arg⁡maxi∉\{a\(1\),…,a\(j−1\)\}⁡minℓ⁡\(Ui​ℓ−rℓ\)/λℓ\(j\)a^\{\(j\)\}=\\arg\\max\_\{i\\notin\\\{a^\{\(1\)\},\\ldots,a^\{\(j\-1\)\}\\\}\}\\min\_\{\\ell\}\(U\_\{i\\ell\}\-r\_\{\\ell\}\)/\\lambda^\{\(j\)\}\_\{\\ell\}, whererris the reference point\. This top\-kkadaptation is our own extension of the directional intuition of Lemma 5 in\(Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)\.
5. 5\.RandomKselects a slate ofkkarms uniformly at random each round, without any learning\.

### Results

Overall,THV\-UCBachieves the lowest cumulativeα\\alpha\-regret and the highest hypervolume in all four front geometries \(linear, convex, concave, and clusters\) and all dimensions fromd=2d=2tod=5d=5, with a margin that generally increases withdd\(See Tables[1](https://arxiv.org/html/2607.26273#Sx6.T1), Figures[1](https://arxiv.org/html/2607.26273#Sx6.F1),[2](https://arxiv.org/html/2607.26273#Sx6.F2),[3](https://arxiv.org/html/2607.26273#Sx6.F3),[4](https://arxiv.org/html/2607.26273#Sx6.F4), and all the results \(ford\>2d\>2\) in the appendix and in our GitHub repositoryhttps://github\.com/ngutowski/topk\-pareto\-bandits\)\.

Figures[1](https://arxiv.org/html/2607.26273#Sx6.F1)to[4](https://arxiv.org/html/2607.26273#Sx6.F4), report hypervolumeHV​\(St\)\\mathrm\{HV\}\(S\_\{t\}\)trajectories \(moving average,w=50w=50\) with95%95\\%CIs across1010seeds, comparing THV\-UCB \(ours\) against the best representative per baseline family, for each synthetic Pareto front geometry\.

Table 1:Summary over four synthetic fronts \(d=2d=2,n=36n=36,k=3k=3,σ=0\.05\\sigma=0\.05,T=2000T=2000, 10 seeds\)\.Fid\.indicates fidelity to the cited work:∙\\bullet= faithful top\-kkadaptation \(core mechanism unchanged\);∘\\circ= our extension \(modified core, tie\-break, or diversity mechanism not in the original\)\.\+denotes our variant when both versions share a citation\. Final Regret values are cumulativeα\\alpha\-regret±\\pm95% CI\.
The linear front is the most discriminative, with THV\-UCB’s advantage over the closest baseline widening from \+27% atd=2d=2to \+79% atd=5d=5: linear fronts require uniform simplex coverage, which single\-direction scalarization methods increasingly fail to achieve at higherdd, while THV\-UCB’s greedy hypervolume gain naturally spreads the slate across the entire front \(See Table[1](https://arxiv.org/html/2607.26273#Sx6.T1)and Figure[1](https://arxiv.org/html/2607.26273#Sx6.F1)\)\.

![Refer to caption](https://arxiv.org/html/2607.26273v1/x1.png)Figure 1:HV trajectories, linear front\.On the clusters front, THV\-UCB consistently outperforms all baselines, confirming that the set\-level hypervolume objective is essential when the front has disconnected regions: no single\-direction scalarization can reliably cover both clusters within a single round \(See Table[1](https://arxiv.org/html/2607.26273#Sx6.T1)and Figure[2](https://arxiv.org/html/2607.26273#Sx6.F2)\)\.

![Refer to caption](https://arxiv.org/html/2607.26273v1/x2.png)Figure 2:HV trajectories, clusters front\.On the concave and convex fronts, THV\-UCB leads throughout but faces stronger competition: ChebyshevUCB\+is the closest competitor on concave atd=3,4d=3,4, while ScalarUCB and ParetoTS\+are competitive on convex across dimensions \(See Table[1](https://arxiv.org/html/2607.26273#Sx6.T1), and Figures[3](https://arxiv.org/html/2607.26273#Sx6.F3)and[4](https://arxiv.org/html/2607.26273#Sx6.F4)\)\.

![Refer to caption](https://arxiv.org/html/2607.26273v1/x3.png)Figure 3:HV trajectories, concave front\.![Refer to caption](https://arxiv.org/html/2607.26273v1/x4.png)Figure 4:HV trajectories, convex front\.Among baselines, no single method dominates across all settings\. ChebyshevUCB\+\(Mandowet al\.[2023](https://arxiv.org/html/2607.26273#bib.bib10)\)is the strongest competitor atd=3d=3and44, particularly on concave and linear fronts\. HVScalarUCB\+\(Zhang[2024](https://arxiv.org/html/2607.26273#bib.bib24)\)becomes increasingly competitive on linear asddgrows, reaching second place atd=4d=4\(0\.05320\.0532\) andd=5d=5\(0\.00530\.0053\)\. ParetoUCB\+\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31)\)and ScalarUCB\(Aueret al\.[2002](https://arxiv.org/html/2607.26273#bib.bib33)\)perform well on smooth fronts \(convex, concave\) at lowddbut degrade on linear and clusters\. ParetoUCB\-Div\(Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31)\)and ParetoUCB\-Crowd\(Debet al\.[2002](https://arxiv.org/html/2607.26273#bib.bib32); Drugan and Nowe[2013](https://arxiv.org/html/2607.26273#bib.bib31)\)add diversity heuristics that help on clusters atd=2d=2but loose their advantage at higherdd\. ScalarUCB\-RandW\(Pariaet al\.[2020](https://arxiv.org/html/2607.26273#bib.bib34)\)is consistently among the weakest baselines due to the high variance induced by random scalarization weights, and RandomK performs worst in all settings as expected\.

### Statistical tests

Paired Wilcoxon tests on the tightest margins confirm significance \(p<0\.001p<0\.001,10/1010/10seeds, Cohen’sddfrom1\.91\.9to44\.544\.5, See Table[6](https://arxiv.org/html/2607.26273#A2.T6)in the appendix\)\.

## Conclusion

We introduced*Top\-kkPareto Bandits*, where an agent repeatedly selects a size\-kkslate under semi\-bandit feedback, evaluated by dominated hypervolume coverage of the Pareto boundary, and proposedTHV\-UCB, which greedily maximizes optimistic marginal hypervolume gain under safe coordinate\-wise pruning\. We established a gap\-freeO~​\(d​n​k​T\)\\tilde\{O\}\\\!\\left\(d\\sqrt\{nkT\}\\right\)bound valid on every instance and a gap\-dependentO~​\(n​k2\.5/Δmin\)\\tilde\{O\}\\\!\\left\(nk^\{2\.5\}/\\Delta\_\{\\min\}\\right\)bound that is polylogarithmic inTTon well\-separated instances; tightening these dependencies and establishing matching lower bounds remain open\. Empirically,THV\-UCBoutperforms state\-of\-the\-art baselines across all tested geometries and dimensionsd∈\{2,…,5\}d\\in\\\{2,\\dots,5\\\}, with the margin widening asddincreases, supporting hypervolume\-driven slate selection for applications such as recommender systems, portfolio management, or automated decision support\.

## References

- P\. Auer, N\. Cesa\-Bianchi, and P\. Fischer \(2002\)Finite\-time analysis of the multiarmed bandit problem\.Mach\. Learn\.47\(2–3\)\.External Links:ISSN 0885\-6125,[Document](https://dx.doi.org/10.1023/A%3A1013689704352)Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.111.111.111.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.111.111.111.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.111.111.111.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[1st item](https://arxiv.org/html/2607.26273#Sx6.I2.i4.I1.i1.p1.4),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.111.111.111.111.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.p6.13.13)\.
- S\. Bubeck and N\. Cesa\-Bianchi \(2012\)Regret analysis of stochastic and nonstochastic multi\-armed bandit problems\.Found\. Trends Mach\. Learn\.5,pp\. 1–122\.External Links:[Link](https://api.semanticscholar.org/CorpusID:264638630)Cited by:[Performance metric: \(approximation\) hypervolume regret\.](https://arxiv.org/html/2607.26273#Sx3.SS0.SSS0.Px5.p1.3)\.
- R\. Busa\-Fekete, B\. Szörényi, P\. Weng, and S\. Mannor \(2017\)Multi\-objective bandits: optimizing the generalized Gini index\.InProceedings of the 34th International Conference on Machine Learning,D\. Precup and Y\. W\. Teh \(Eds\.\),Proceedings of Machine Learning Research, Vol\.70\.Cited by:[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- X\. Cai, P\. Zhang, L\. Zhao, J\. Bian, M\. Sugiyama, and A\. Llorens \(2023\)Distributional pareto\-optimal multi\-objective reinforcement learning\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36\.Cited by:[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- L\. Cao, M\. Shi, and N\. B\. Shroff \(2025\)Provably efficient multi\-objective bandit algorithms under preference\-centric customization\.External Links:2502\.13457,[Link](https://arxiv.org/abs/2502.13457)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- J\. Chen, Z\. Zhang, Z\. Cao, Y\. Wu, Y\. Ma, T\. Ye, and J\. Wang \(2023\)Neural multi\-objective combinatorial optimization with diversity enhancement\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36\.Cited by:[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- Y\. Chen, W\. Chan, E\. Su, and Q\. Diao \(2025\)Multi\-objective optimization for smart cities: a systematic review of algorithms, challenges, and future directions\.PeerJ Computer Science11\.External Links:[Document](https://dx.doi.org/10.7717/peerj-cs.3042)Cited by:[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- K\. Deb, A\. Pratap, S\. Agarwal, and T\. Meyarivan \(2002\)A fast and elitist multiobjective genetic algorithm: nsga\-ii\.IEEE Transactions on Evolutionary Computation6\(2\)\.External Links:[Document](https://dx.doi.org/10.1109/4235.996017)Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.48.48.48.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.48.48.48.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.48.48.48.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[3rd item](https://arxiv.org/html/2607.26273#Sx6.I2.i1.I1.i3.p1.1),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.48.48.48.48.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.p6.13.13)\.
- K\. Deb, L\. Thiele, M\. Laumanns, and E\. Zitzler \(2005\)Scalable test problems for evolutionary multiobjective optimization\.InEvolutionary Multiobjective Optimization: Theoretical Advances and Applications,pp\. 105–145\.External Links:ISBN 978\-1\-84628\-137\-2,[Document](https://dx.doi.org/10.1007/1-84628-137-7%5F6)Cited by:[Synthetic Environments](https://arxiv.org/html/2607.26273#Sx6.SSx2.p1.5.5),[Synthetic Environments](https://arxiv.org/html/2607.26273#Sx6.SSx2.p2.12.10)\.
- M\. M\. Drugan and A\. Nowe \(2013\)Designing multi\-objective multi\-armed bandits algorithms: a study\.InThe 2013 International Joint Conference on Neural Networks \(IJCNN\),Vol\.\.External Links:[Document](https://dx.doi.org/10.1109/IJCNN.2013.6707036)Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.21.21.21.10),[Table 3](https://arxiv.org/html/2607.26273#A2.T3.30.30.30.10),[Table 3](https://arxiv.org/html/2607.26273#A2.T3.39.39.39.10),[Table 3](https://arxiv.org/html/2607.26273#A2.T3.48.48.48.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.21.21.21.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.30.30.30.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.39.39.39.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.48.48.48.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.21.21.21.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.30.30.30.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.39.39.39.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.48.48.48.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3),[1st item](https://arxiv.org/html/2607.26273#Sx6.I2.i1.I1.i1.p1.6),[2nd item](https://arxiv.org/html/2607.26273#Sx6.I2.i1.I1.i2.p1.2),[3rd item](https://arxiv.org/html/2607.26273#Sx6.I2.i1.I1.i3.p1.1),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.21.21.21.21.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.30.30.30.30.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.39.39.39.39.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.48.48.48.48.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.p6.13.13)\.
- Ó\. Fernández Vicente, J\. García, and F\. Fernández \(2026\)Optimizing market\-making strategies: a multi\-objective reinforcement learning approach with pareto fronts\.Expert Systems with Applications295\.External Links:ISSN 0957\-4174,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.eswa.2025.128867)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p1.1),[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- J\. C\. Fromer and C\. W\. Coley \(2023\)Computer\-aided multi\-objective optimization in small molecule discovery\.Patterns4\(2\)\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.patter.2023.100678),ISSN 2666\-3899Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p1.1)\.
- R\. Ghanbarzadeh, I\. Ahadi Akhlaghi, M\. Ghafarian Gholamhossein, M\. Najeeb Khan, and S\. Mirjalili \(2026\)Systematic literature review of multi\-objective hyper\-heuristics: a human\-in\-the\-loop large language model methodology\.Artificial Intelligence Review59\(5\)\.External Links:ISSN 1573\-7462,[Document](https://dx.doi.org/10.1007/s10462-026-11531-8)Cited by:[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- A\. P\. Guerreiro, C\. M\. Fonseca, and L\. Paquete \(2021\)The hypervolume indicator: computational problems and algorithms\.ACM Comput\. Surv\.54\(6\)\.External Links:ISSN 0360\-0300,[Document](https://dx.doi.org/10.1145/3453474)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1)\.
- K\. He, C\. Chen, S\. Chen, B\. Chen, A\. Zhang, P\. Chen, Z\. Wang, and Z\. Wu \(2026\)Reinforcement learning for multi\-objective optimization: a review\.Archives of Computational Methods in Engineering33\(2\)\.External Links:ISSN 1886\-1784,[Document](https://dx.doi.org/10.1007/s11831-025-10389-3)Cited by:[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- A\. Hüyük and C\. Tekin \(2021\)Multi\-objective multi\-armed bandit with lexicographically ordered and satisficing objectives\.Machine Learning110\(6\)\.External Links:ISSN 1573\-0565,[Document](https://dx.doi.org/10.1007/s10994-021-05956-1)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- D\. Jiju and S\. Manemaran \(2025\)AI\-driven hyperheuristics for dynamic multiobjective optimization: a comprehensive review\.\.IAENG International Journal of Applied Mathematics55\(12\)\.Cited by:[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- J\. Katz\-Samuels and C\. Scott \(2018\)Feasible arm identification\.InProceedings of the 35th International Conference on Machine Learning,J\. Dy and A\. Krause \(Eds\.\),Proceedings of Machine Learning Research, Vol\.80\.Cited by:[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- C\. KONE, E\. Kaufmann, and L\. Richert \(2023\)Adaptive algorithms for relaxed pareto set identification\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36\.Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p1.1),[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3),[Dominated Hypervolume \(HV\) in MOMAB\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px3.p1.3)\.
- C\. Kone, E\. Kaufmann, and L\. Richert \(2025a\)Bandit pareto set identification in a multi\-output linear model\.InProceedings of The 28th International Conference on Artificial Intelligence and Statistics,Y\. Li, S\. Mandt, S\. Agrawal, and E\. Khan \(Eds\.\),Proceedings of Machine Learning Research, Vol\.258\.Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p1.1),[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1)\.
- C\. Kone, E\. Kaufmann, and L\. Richert \(2025b\)Constrained pareto set identification with bandit feedback\.InProceedings of the 42nd International Conference on Machine Learning,A\. Singh, M\. Fazel, D\. Hsu, S\. Lacoste\-Julien, F\. Berkenkamp, T\. Maharaj, K\. Wagstaff, and J\. Zhu \(Eds\.\),Proceedings of Machine Learning Research, Vol\.267,pp\. 31342–31378\.Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3),[Dominated Hypervolume \(HV\) in MOMAB\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px3.p1.3)\.
- S\. Lee, M\. H\. Lee, and J\. Moon \(2026\)Weight vector selection methods by hypervolume maximization in the pareto front for single policy multi\-objective reinforcement learning\.Expert Systems with Applications296\.External Links:ISSN 0957\-4174,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.eswa.2025.129070)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- A\. Letard, N\. Gutowski, O\. Camp, and T\. Amghar \(2024\)Bandit algorithms: a comprehensive review and their dynamic selection from a portfolio for multicriteria top\-k recommendation\.Expert Systems with Applications246\.External Links:ISSN 0957\-4174,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.eswa.2024.123151)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p1.1),[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- E\. Liu, Y\. Wu, X\. Huang, C\. Gao, R\. Wang, K\. Xue, and C\. Qian \(2025a\)Pareto set learning for multi\-objective reinforcement learning\.InProceedings of the Thirty\-Ninth AAAI Conference on Artificial Intelligence and Thirty\-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence,AAAI’25/IAAI’25/EAAI’25\.External Links:ISBN 978\-1\-57735\-897\-8,[Document](https://dx.doi.org/10.1609/aaai.v39i18.34068)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- R\. Liu, Y\. Pan, L\. Xu, L\. Song, P\. You, Y\. Chen, and J\. Bian \(2025b\)Efficient discovery of pareto front for multi\-objective reinforcement learning\.InInternational Conference on Learning Representations,Y\. Yue, A\. Garg, N\. Peng, F\. Sha, and R\. Yu \(Eds\.\),Vol\.2025\.Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- L\. Mandow, S\. Martín\-Albo, and J\. Perez\-de\-la Cruza \(2023\)Multi\-objective bandit algorithms with chebyshev scalarization\.Multi\-objective Decision Making Workshop \(MODeM \- ECAI\)\.Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.75.75.75.10),[Table 3](https://arxiv.org/html/2607.26273#A2.T3.84.84.84.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.75.75.75.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.84.84.84.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.75.75.75.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.84.84.84.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3),[1st item](https://arxiv.org/html/2607.26273#Sx6.I2.i3.I1.i1.p1.5),[2nd item](https://arxiv.org/html/2607.26273#Sx6.I2.i3.I1.i2.p1.4),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.75.75.75.75.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.84.84.84.84.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.p6.13.13)\.
- B\. Paria, K\. Kandasamy, and B\. Póczos \(2020\)A flexible framework for multi\-objective bayesian optimization using random scalarizations\.InProceedings of The 35th Uncertainty in Artificial Intelligence Conference,R\. P\. Adams and V\. Gogate \(Eds\.\),Proceedings of Machine Learning Research, Vol\.115\.Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.120.120.120.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.120.120.120.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.120.120.120.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[2nd item](https://arxiv.org/html/2607.26273#Sx6.I2.i4.I1.i2.p1.4),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.120.120.120.120.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.p6.13.13)\.
- S\. Q\. Yahyaa, M\. M\. Drugan, and B\. Manderick \(2014\)Knowledge gradient for multi\-objective multi\-armed bandit algorithms\.InProceedings of the 6th International Conference on Agents and Artificial Intelligence \- Volume 1,ICAART 2014\.External Links:ISBN 9789897580154,[Document](https://dx.doi.org/10.5220/0004796600740083)Cited by:[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- D\. M\. Roijers, P\. Vamplew, S\. Whiteson, and R\. Dazeley \(2013\)A survey of multi\-objective sequential decision\-making\.Journal of Artificial Intelligence Research48,pp\. 67–113\.Cited by:[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- D\. M\. Roijers, L\. M\. Zintgraf, and A\. Nowé \(2017\)Interactive thompson sampling for multi\-objective multi\-armed bandits\.InAlgorithmic Decision Theory,J\. Rothe \(Ed\.\),External Links:ISBN 978\-3\-319\-67504\-6Cited by:[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- W\. Röpke, M\. Reymond, P\. Mannion, D\. M\. Roijers, A\. Nowé, and R\. Rădulescu \(2025\)Divide and conquer: provably unveiling the pareto front with multi\-objective reinforcement learning\.InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems,AAMAS ’25\.External Links:ISBN 9798400714269Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- M\. Shahverdikondori, M\. R\. Badri, and N\. Kiyavash \(2025\)Best group identification in multi\-objective bandits\.External Links:2505\.17869,[Link](https://arxiv.org/abs/2505.17869)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- J\. Song, Y\. Liu, D\. Li, Y\. Sun, S\. Fu, S\. Chen, and Y\. Cao \(2025\)Balancing rewards in text summarization: multi\-objective reinforcement learning via hypervolume optimization\.ArXivabs/2510\.19325\.External Links:[Link](https://api.semanticscholar.org/CorpusID:282272197)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- Y\. Tian, L\. Si, X\. Zhang, R\. Cheng, C\. He, K\. C\. Tan, and Y\. Jin \(2021\)Evolutionary large\-scale multi\-objective optimization: a survey\.ACM Comput\. Surv\.54\(8\)\.External Links:ISSN 0360\-0300,[Document](https://dx.doi.org/10.1145/3470971)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p1.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- M\. Xu and D\. Klabjan \(2023\)Pareto regret analyses in multi\-objective multi\-armed bandit\.InProceedings of the 40th International Conference on Machine Learning,A\. Krause, E\. Brunskill, K\. Cho, B\. Engelhardt, S\. Sabato, and J\. Scarlett \(Eds\.\),Proceedings of Machine Learning Research, Vol\.202\.Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- B\. Xue, X\. Lin, X\. Zhang, and Q\. Zhang \(2025\)Multiple trade\-offs: an improved approach for lexicographic linear bandits\.Proceedings of the AAAI Conference on Artificial Intelligence39\(20\)\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v39i20.35491)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p2.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3)\.
- S\. Yahyaa and B\. Manderick \(2015\)Thompson sampling for multi\-objective multi\-armed bandits problem\.InEuropean Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning,pp\. 47–52\.Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.57.57.57.10),[Table 3](https://arxiv.org/html/2607.26273#A2.T3.66.66.66.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.57.57.57.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.66.66.66.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.57.57.57.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.66.66.66.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3),[1st item](https://arxiv.org/html/2607.26273#Sx6.I2.i2.I1.i1.p1.4),[2nd item](https://arxiv.org/html/2607.26273#Sx6.I2.i2.I1.i2.p1.3),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.57.57.57.57.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.66.66.66.66.10)\.
- F\. E\. Zaizi, S\. Abakarim, S\. Qassimi, and S\. Rakrak \(2025\)Multi\-objective reinforcement learning for recommender systems: a comprehensive survey of methods, challenges, and future directions\.International Journal of Multimedia Information Retrieval14\.External Links:[Link](https://api.semanticscholar.org/CorpusID:281836486)Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p1.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1)\.
- Q\. \(\. Zhang \(2024\)Optimal scalarizations for sublinear hypervolume regret\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37\.External Links:[Document](https://dx.doi.org/10.52202/079017-1262)Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.102.102.102.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.102.102.102.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.102.102.102.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3),[Dominated Hypervolume \(HV\) in MOMAB\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px3.p1.3),[4th item](https://arxiv.org/html/2607.26273#Sx6.I2.i4.I1.i4.p1.6),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.102.102.102.102.10),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.p6.13.13)\.
- R\. Zhang and D\. Golovin \(2020\)Random hypervolume scalarizations for provable multi\-objective black box optimization\.InProceedings of the 37th International Conference on Machine Learning,H\. D\. III and A\. Singh \(Eds\.\),Proceedings of Machine Learning Research, Vol\.119,pp\. 11096–11105\.Cited by:[Table 3](https://arxiv.org/html/2607.26273#A2.T3.93.93.93.10),[Table 4](https://arxiv.org/html/2607.26273#A2.T4.93.93.93.10),[Table 5](https://arxiv.org/html/2607.26273#A2.T5.93.93.93.10),[item 2](https://arxiv.org/html/2607.26273#Sx1.I1.i2.p1.3),[item 3](https://arxiv.org/html/2607.26273#Sx1.I1.i3.p1.7),[Multi\-Objective Multi\-Armed Bandits \(MOMAB\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px2.p1.3),[Dominated Hypervolume \(HV\) in MOMAB\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px3.p1.3),[3rd item](https://arxiv.org/html/2607.26273#Sx6.I2.i4.I1.i3.p1.3),[Baselines](https://arxiv.org/html/2607.26273#Sx6.SSx3.p1.1.1),[Results](https://arxiv.org/html/2607.26273#Sx6.SSx4.93.93.93.93.10)\.
- X\. Zhang, G\. Li, X\. Lin, Y\. Zhang, Y\. Chen, and Q\. Zhang \(2024\)Gliding over the pareto front with uniform designs\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37\.External Links:[Document](https://dx.doi.org/10.52202/079017-0072)Cited by:[item 3](https://arxiv.org/html/2607.26273#Sx1.I1.i3.p1.7),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1),[Dominated Hypervolume \(HV\) in MOMAB\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px3.p1.3)\.
- X\. Zhang, X\. Lin, B\. Xue, Y\. Chen, and Q\. Zhang \(2023\)Hypervolume maximization: a geometric view of pareto set learning\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36\.Cited by:[Introduction](https://arxiv.org/html/2607.26273#Sx1.p3.1),[Multi\-Objective Optimization \(MOO\)\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px1.p1.1),[Dominated Hypervolume \(HV\) in MOMAB\.](https://arxiv.org/html/2607.26273#Sx2.SS0.SSS0.Px3.p1.3)\.
- E\. Zitzler, L\. Thiele, M\. Laumanns, C\.M\. Fonseca, and V\.G\. da Fonseca \(2003\)Performance assessment of multiobjective optimizers: an analysis and review\.IEEE Transactions on Evolutionary Computation7\(2\)\.External Links:[Document](https://dx.doi.org/10.1109/TEVC.2003.810758)Cited by:[Reference point and dominated hypervolume\.](https://arxiv.org/html/2607.26273#Sx3.SS0.SSS0.Px4.p1.8.1),[Experiments](https://arxiv.org/html/2607.26273#Sx6.p2.6)\.

> This appendix provides the full proofs of Theorems[1](https://arxiv.org/html/2607.26273#Thmtheorem1)–[3](https://arxiv.org/html/2607.26273#Thmtheorem3)\(Upper\-bound Proofs, below\), additional experimental results ford∈\{3,4,5\}d\\in\\\{3,4,5\\\}\(Experimental details\), and a summary of notation \(Notation summary\)\.

## Appendix AUpper\-bound Proofs

This appendix establishes the sublinearα\\alpha\-regret guarantee forTHV\-UCBannounced in the Regret Analysis section\. We prove two complementary statements:

- •a*gap\-free*bound \(Theorem[1](https://arxiv.org/html/2607.26273#Thmtheorem1a)\), of orderO~​\(n​k​T\)\\tilde\{O\}\(\\sqrt\{nkT\}\), valid on*every*instance regardless of how close the arms are to each other;
- •a*gap\-dependent*bound \(Theorem[2](https://arxiv.org/html/2607.26273#Thmtheorem2a)\), of orderO~​\(n​k2\.5/Δmin\)\\tilde\{O\}\(nk^\{2\.5\}/\\Delta\_\{\\min\}\), which becomes polylogarithmic inTTas soon as the instance is well separated\.

Both proofs share the same first steps \(Preliminaries through Lipschitz control of the optimism error\), which reduceR¯T\\bar\{R\}\_\{T\}to a sum of confidence radii, in \([5](https://arxiv.org/html/2607.26273#A1.E5)\)\. They diverge only in*how*this sum is controlled: the gap\-free bound \(see Section*A gap\-free bound*\) treats every pull anonymously via Cauchy–Schwarz over the whole horizon; the gap\-dependent bound \(See Section*A gap\-dependent bound*\) opens up the greedy construction stage by stage, tracks the actual comparisonsΔtUCB\(⋅∣S\)\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(\\cdot\\mid S\)performed by the algorithm, and applies the same Cauchy–Schwarz idea*locally*, to each stage’s deviation rounds\. We discuss what each proof technique does, and does not, use aboutTHV\-UCBin the discussion at the end of this appendix\.

### Preliminaries

###### Lemma 1\(Monotonicity and submodularity of hypervolume\)\.

For any fixed reference point𝐫\\mathbf\{r\}dominated by all achievable means, the set functionS↦HV​\(S\)S\\mapsto\\mathrm\{HV\}\(S\)is monotone \(non\-decreasing\) and submodular\.

###### Proof\.

RecallHV​\(S\)=λd​\(⋃i∈S∏j=1d\[rj,μi,j\]\)\\mathrm\{HV\}\(S\)=\\lambda\_\{d\}\\bigl\(\\bigcup\_\{i\\in S\}\\prod\_\{j=1\}^\{d\}\[r\_\{j\},\\mu\_\{i,j\}\]\\bigr\)\.

*Monotonicity\.*IfS⊆TS\\subseteq T, the union of boxes only grows, soHV​\(S\)≤HV​\(T\)\\mathrm\{HV\}\(S\)\\leq\\mathrm\{HV\}\(T\)\.

*Submodularity\.*LetA⊆BA\\subseteq Bandi∉Bi\\notin B\. WriteVA=⋃j∈A∏ℓ\[rℓ,μj,ℓ\]V\_\{A\}=\\bigcup\_\{j\\in A\}\\prod\_\{\\ell\}\[r\_\{\\ell\},\\mu\_\{j,\\ell\}\]andVi=∏ℓ\[rℓ,μi,ℓ\]V\_\{i\}=\\prod\_\{\\ell\}\[r\_\{\\ell\},\\mu\_\{i,\\ell\}\]\. Then

HV​\(A∪\{i\}\)−HV​\(A\)=λd​\(Vi∖VA\),HV​\(B∪\{i\}\)−HV​\(B\)=λd​\(Vi∖VB\)\.\\mathrm\{HV\}\(A\\cup\\\{i\\\}\)\-\\mathrm\{HV\}\(A\)=\\lambda\_\{d\}\(V\_\{i\}\\setminus V\_\{A\}\),\\qquad\\mathrm\{HV\}\(B\\cup\\\{i\\\}\)\-\\mathrm\{HV\}\(B\)=\\lambda\_\{d\}\(V\_\{i\}\\setminus V\_\{B\}\)\.SinceVA⊆VBV\_\{A\}\\subseteq V\_\{B\},Vi∖VB⊆Vi∖VAV\_\{i\}\\setminus V\_\{B\}\\subseteq V\_\{i\}\\setminus V\_\{A\}, hence submodularity\. ∎

###### Lemma 2\(Coordinate\-wise concentration\)\.

Assume each coordinate isη\\eta\-sub\-Gaussian\. Then with probability at least1−δ1\-\\delta, for alli,j,ti,j,t,

\|μ^i,j​\(t\)−μi,j\|≤βi​\(t\)=2​η​log⁡\(n​d​t2/δ\)max⁡\{1,Ni​\(t−1\)\}\.\\bigl\|\\widehat\{\\mu\}\_\{i,j\}\(t\)\-\\mu\_\{i,j\}\\bigr\|\\leq\\beta\_\{i\}\(t\)=\\sqrt\{\\frac\{2\\eta\\log\(ndt^\{2\}/\\delta\)\}\{\\max\\\{1,N\_\{i\}\(t\-1\)\\\}\}\}\.

###### Proof\.

Fixi,ji,jand a pull counts=Ni​\(t−1\)≥1s=N\_\{i\}\(t\-1\)\\geq 1\. By the sub\-Gaussian Hoeffding bound,ℙ​\(\|μ^i,j​\(t\)−μi,j\|\>2​η​log⁡\(x\)/s\)≤2/x\\mathbb\{P\}\\bigl\(\|\\widehat\{\\mu\}\_\{i,j\}\(t\)\-\\mu\_\{i,j\}\|\>\\sqrt\{2\\eta\\log\(x\)/s\}\\bigr\)\\leq 2/x\. Takingx=n​d​t2/δx=ndt^\{2\}/\\deltaand a union bound overi∈\[n\]i\\in\[n\],j∈\[d\]j\\in\[d\], andt∈\[T\]t\\in\[T\]\(using∑t≥1t−2≤2\\sum\_\{t\\geq 1\}t^\{\-2\}\\leq 2\) gives total failure probabilityO​\(δ\)O\(\\delta\); absorbing the constant intoδ\\deltayields the stated bound\. ∎

We writeℰ\\mathcal\{E\}for the event on which Lemma[2](https://arxiv.org/html/2607.26273#Thmlemma2)holds, soℙ​\(ℰ\)≥1−δ\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-\\delta\. After the initialization phase of Algorithm[1](https://arxiv.org/html/2607.26273#alg1)\(which lasts at mostt0=⌈n​m0/k⌉t\_\{0\}=\\lceil nm\_\{0\}/k\\rceilrounds\), every arm hasNi​\(t−1\)≥m0≥1N\_\{i\}\(t\-1\)\\geq m\_\{0\}\\geq 1, so themax⁡\{1,⋅\}\\max\\\{1,\\cdot\\\}inβi​\(t\)\\beta\_\{i\}\(t\)is never active fort\>t0t\>t\_\{0\}; we drop it below for readability\.

### A shared greedy\-approximation theorem

The following classical fact \(Nemhauser, Wolsey & Fisher, 1978\) is invoked twice in this appendix, for two different monotone submodular functions; we state it once to avoid duplicating the argument and, crucially, to keep visually distinct the two objects it produces\.

###### Fact 1\(Greedy approximation for monotone submodular maximization\)\.

Letf:2\[n\]→ℝf:2^\{\[n\]\}\\to\\mathbb\{R\}be monotone and submodular, and letG=\{g1,…,gk\}G=\\\{g\_\{1\},\\dots,g\_\{k\}\\\}be built by greedy maximization of marginalff\-gain under the cardinality constraintkk\(i\.e\.gℓ∈arg⁡maxi∉Gℓ−1⁡f​\(Gℓ−1∪\{i\}\)−f​\(Gℓ−1\)g\_\{\\ell\}\\in\\arg\\max\_\{i\\notin G\_\{\\ell\-1\}\}f\(G\_\{\\ell\-1\}\\cup\\\{i\\\}\)\-f\(G\_\{\\ell\-1\}\),Gℓ=Gℓ−1∪\{gℓ\}G\_\{\\ell\}=G\_\{\\ell\-1\}\\cup\\\{g\_\{\\ell\}\\\},G0=∅G\_\{0\}=\\emptyset,G=GkG=G\_\{k\}\)\. Then

f​\(G\)≥\(1−1e\)​max\|S\|=k⁡f​\(S\)=α​max\|S\|=k⁡f​\(S\)\.f\(G\)\\;\\geq\\;\\Bigl\(1\-\\tfrac\{1\}\{e\}\\Bigr\)\\max\_\{\|S\|=k\}f\(S\)\\;=\\;\\alpha\\max\_\{\|S\|=k\}f\(S\)\.

We will apply Fact[1](https://arxiv.org/html/2607.26273#Thmfact1)to two different functions:

- •f=HVtUCBf=\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(monotone submodular by the previous remark, withG=StG=S\_\{t\}the set actually built byTHV\-UCBat roundtt— this yields Corollary[1](https://arxiv.org/html/2607.26273#Thmcorollary1)below, used in the reduction step;
- •f=HVf=\\mathrm\{HV\}directly on the true means— a purely deterministic statement requiring no concentration event — withG=G⋆G=G^\{\\star\}, a benchmark sequence introduced in Section*A gap\-dependent bound*anddistinct from the regret’s true optimumS⋆S^\{\\star\}\.

###### Corollary 1\(Greedy approximation under optimism\)\.

For every roundtt,HVtUCB​\(St\)≥α​HVtUCB​\(Stopt\)\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\_\{t\}\)\\geq\\alpha\\,\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S^\{\\mathrm\{opt\}\}\_\{t\}\), whereStopt∈arg⁡max\|S\|=k⁡HVtUCB​\(S\)S^\{\\mathrm\{opt\}\}\_\{t\}\\in\\arg\\max\_\{\|S\|=k\}\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)\.

### Optimism and reduction to optimism error

Recallui,j​\(t\)=μ^i,j​\(t−1\)\+βi​\(t\)u\_\{i,j\}\(t\)=\\widehat\{\\mu\}\_\{i,j\}\(t\-1\)\+\\beta\_\{i\}\(t\)and

HVtUCB​\(S\)=λd​\(⋃i∈S\[r1,ui,1​\(t\)\]×⋯×\[rd,ui,d​\(t\)\]\)\.\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)=\\lambda\_\{d\}\\Bigl\(\\bigcup\_\{i\\in S\}\[r\_\{1\},u\_\{i,1\}\(t\)\]\\times\\cdots\\times\[r\_\{d\},u\_\{i,d\}\(t\)\]\\Bigr\)\.Onℰ\\mathcal\{E\},μi,j≤ui,j​\(t\)\\mu\_\{i,j\}\\leq u\_\{i,j\}\(t\)for alli,ji,j, so by monotonicityHV​\(S\)≤HVtUCB​\(S\)\\mathrm\{HV\}\(S\)\\leq\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)for everySS\. LetS⋆∈arg⁡max\|S\|=k⁡HV​\(S\)S^\{\\star\}\\in\\arg\\max\_\{\|S\|=k\}\\mathrm\{HV\}\(S\), withV⋆=HV​\(S⋆\)V^\{\\star\}=\\mathrm\{HV\}\(S^\{\\star\}\)— this is the benchmark appearing in the regret definition \([2](https://arxiv.org/html/2607.26273#Sx3.E2)\), and the only roleS⋆S^\{\\star\}plays in this appendix\. SinceStoptS^\{\\mathrm\{opt\}\}\_\{t\}maximizesHVtUCB\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}over*all*size\-kksets, it dominatesS⋆S^\{\\star\}under this score, so by Corollary[1](https://arxiv.org/html/2607.26273#Thmcorollary1),

HVtUCB​\(St\)≥α​HVtUCB​\(Stopt\)≥α​HVtUCB​\(S⋆\)\.\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\_\{t\}\)\\;\\geq\\;\\alpha\\,\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S^\{\\mathrm\{opt\}\}\_\{t\}\)\\;\\geq\\;\\alpha\\,\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S^\{\\star\}\)\.Therefore, onℰ\\mathcal\{E\},

r¯t=α​V⋆−HV​\(St\)≤α​HVtUCB​\(S⋆\)−HV​\(St\)≤HVtUCB​\(St\)−HV​\(St\)\.\\bar\{r\}\_\{t\}=\\alpha\\,V^\{\\star\}\-\\mathrm\{HV\}\(S\_\{t\}\)\\;\\leq\\;\\alpha\\,\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S^\{\\star\}\)\-\\mathrm\{HV\}\(S\_\{t\}\)\\;\\leq\\;\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\_\{t\}\)\-\\mathrm\{HV\}\(S\_\{t\}\)\.\(3\)Summing overt∈\[T\]t\\in\[T\],

R¯T≤∑t=1T\(HVtUCB​\(St\)−HV​\(St\)\)on​ℰ\.\\bar\{R\}\_\{T\}\\;\\leq\\;\\sum\_\{t=1\}^\{T\}\\bigl\(\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\_\{t\}\)\-\\mathrm\{HV\}\(S\_\{t\}\)\\bigr\)\\qquad\\text\{on \}\\mathcal\{E\}\.\(4\)

### Lipschitz control of the optimism error

###### Lemma 3\(Lipschitz bound for hypervolume under coordinate\-wise shifts\)\.

There is a constantCdC\_\{d\}\(one may takeCd≤dC\_\{d\}\\leq dwhen rewards lie in\[0,1\]d\[0,1\]^\{d\}and𝐫=𝟎\\mathbf\{r\}=\\mathbf\{0\}\) such that, onℰ\\mathcal\{E\}, for every roundttandevery finite setS⊆\[n\]S\\subseteq\[n\]\(not necessarilyStS\_\{t\}\),

HVtUCB​\(S\)−HV​\(S\)≤Cd​∑i∈Sβi​\(t\)\.\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)\-\\mathrm\{HV\}\(S\)\\;\\leq\\;C\_\{d\}\\sum\_\{i\\in S\}\\beta\_\{i\}\(t\)\.

###### Proof\.

WriteS=\{i1,…,im\}S=\\\{i\_\{1\},\\dots,i\_\{m\}\\\}\. Define the intermediate hypervolumeAℓA\_\{\\ell\}where armsi1,…,iℓi\_\{1\},\\dots,i\_\{\\ell\}use optimistic vectors𝐮ip​\(t\)\\mathbf\{u\}\_\{i\_\{p\}\}\(t\)and armsiℓ\+1,…,imi\_\{\\ell\+1\},\\dots,i\_\{m\}use true means𝝁ip\\boldsymbol\{\\mu\}\_\{i\_\{p\}\}, soHVtUCB​\(S\)−HV​\(S\)=∑ℓ=1m\(Aℓ−Aℓ−1\)\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)\-\\mathrm\{HV\}\(S\)=\\sum\_\{\\ell=1\}^\{m\}\(A\_\{\\ell\}\-A\_\{\\ell\-1\}\)\. Each term changes only armiℓi\_\{\\ell\}from𝝁iℓ\\boldsymbol\{\\mu\}\_\{i\_\{\\ell\}\}to𝐮iℓ​\(t\)=𝝁iℓ\+𝜹iℓ\\mathbf\{u\}\_\{i\_\{\\ell\}\}\(t\)=\\boldsymbol\{\\mu\}\_\{i\_\{\\ell\}\}\+\\boldsymbol\{\\delta\}\_\{i\_\{\\ell\}\}with0≤δiℓ,j≤βiℓ​\(t\)0\\leq\\delta\_\{i\_\{\\ell\},j\}\\leq\\beta\_\{i\_\{\\ell\}\}\(t\)\. The added hypervolume is contained in a union ofddaxis\-aligned slabs of width at mostβiℓ​\(t\)\\beta\_\{i\_\{\\ell\}\}\(t\)in one coordinate and at most11in the others, soAℓ−Aℓ−1≤d​βiℓ​\(t\)A\_\{\\ell\}\-A\_\{\\ell\-1\}\\leq d\\,\\beta\_\{i\_\{\\ell\}\}\(t\)\. Summing overℓ\\ellgives the claim withCd=dC\_\{d\}=d\. Crucially, this argument never uses\|S\|=k\|S\|=knor any property of howSSwas selected, hence it holds for an arbitrary finiteSS\. ∎

Combining \([4](https://arxiv.org/html/2607.26273#A1.E4)\) with Lemma[3](https://arxiv.org/html/2607.26273#Thmlemma3)applied toS=StS=S\_\{t\},

R¯T≤Cd​∑t=1T∑i∈Stβi​\(t\)on​ℰ\.\\bar\{R\}\_\{T\}\\;\\leq\\;C\_\{d\}\\sum\_\{t=1\}^\{T\}\\sum\_\{i\\in S\_\{t\}\}\\beta\_\{i\}\(t\)\\qquad\\text\{on \}\\mathcal\{E\}\.\(5\)The rest of the proof bounds the right\-hand side of \([5](https://arxiv.org/html/2607.26273#A1.E5)\) in two ways\.

### A gap\-free bound

LetNi​\(T\)=∑t=1T𝟏​\{i∈St\}N\_\{i\}\(T\)=\\sum\_\{t=1\}^\{T\}\\mathbf\{1\}\\\{i\\in S\_\{t\}\\\}\. Reordering \([5](https://arxiv.org/html/2607.26273#A1.E5)\) by arm,

∑t=1T∑i∈Stβi​\(t\)=∑i=1n∑s=1Ni​\(T\)2​η​log⁡\(n​d​T2/δ\)s≤2​2​η​log⁡\(n​d​T2/δ\)​∑i=1nNi​\(T\),\\sum\_\{t=1\}^\{T\}\\sum\_\{i\\in S\_\{t\}\}\\beta\_\{i\}\(t\)=\\sum\_\{i=1\}^\{n\}\\sum\_\{s=1\}^\{N\_\{i\}\(T\)\}\\sqrt\{\\frac\{2\\eta\\log\(ndT^\{2\}/\\delta\)\}\{s\}\}\\;\\leq\\;2\\sqrt\{2\\eta\\log\(ndT^\{2\}/\\delta\)\}\\sum\_\{i=1\}^\{n\}\\sqrt\{N\_\{i\}\(T\)\},using∑s=1ms−1/2≤2​m\\sum\_\{s=1\}^\{m\}s^\{\-1/2\}\\leq 2\\sqrt\{m\}\. Since exactlykkarms are pulled per round,∑iNi​\(T\)=k​T\\sum\_\{i\}N\_\{i\}\(T\)=kT, and Cauchy–Schwarz gives∑iNi​\(T\)≤n​k​T\\sum\_\{i\}\\sqrt\{N\_\{i\}\(T\)\}\\leq\\sqrt\{nkT\}\. Hence, onℰ\\mathcal\{E\},R¯T≤O​\(Cd​n​k​T​log⁡T\)\\bar\{R\}\_\{T\}\\leq O\\bigl\(C\_\{d\}\\sqrt\{nkT\\log T\}\\bigr\)\.

###### Theorem 1\(Gap\-free bound \(detailed version\)\)\.

Onℰ\\mathcal\{E\},R¯T=O​\(Cd​n​k​T​log⁡T\)\\bar\{R\}\_\{T\}=O\\bigl\(C\_\{d\}\\sqrt\{nkT\\log T\}\\bigr\)\.

### A gap\-dependent bound

The key idea: the algorithm’s own greedy construction at roundttprogressively learns a stage\-by\-stage benchmark sequence\. At stageℓ\\ell, it must identify the best arm conditionally on the previously identified greedy prefix\.

#### The greedy optimal set

LetG⋆=\{i1⋆,…,ik⋆\}G^\{\\star\}=\\\{i\_\{1\}^\{\\star\},\\dots,i\_\{k\}^\{\\star\}\\\}be a greedy construction of an optimal size\-kkset for the*true*hypervolume:

iℓ⋆∈arg⁡maxi∉Gℓ−1⋆⁡Δ​\(i∣Gℓ−1⋆\),Gℓ⋆=Gℓ−1⋆∪\{iℓ⋆\},G0⋆=∅,i\_\{\\ell\}^\{\\star\}\\in\\arg\\max\_\{i\\notin G^\{\\star\}\_\{\\ell\-1\}\}\\Delta\(i\\mid G^\{\\star\}\_\{\\ell\-1\}\),\\qquad G^\{\\star\}\_\{\\ell\}=G^\{\\star\}\_\{\\ell\-1\}\\cup\\\{i\_\{\\ell\}^\{\\star\}\\\},\\quad G^\{\\star\}\_\{0\}=\\emptyset,withΔ​\(i∣S\)=HV​\(S∪\{i\}\)−HV​\(S\)\\Delta\(i\\mid S\)=\\mathrm\{HV\}\(S\\cup\\\{i\\\}\)\-\\mathrm\{HV\}\(S\)\.

Assume the greedy maximizer is unique at every stage ofG⋆G^\{\\star\}’s construction, and define the stage\-ℓ\\ellgaps relative to this benchmark:

Δℓ​\(i\)=Δ​\(iℓ⋆∣Gℓ−1⋆\)−Δ​\(i∣Gℓ−1⋆\)\>0,i≠iℓ⋆,Δmin=minℓ∈\[k\]⁡mini≠iℓ⋆⁡Δℓ​\(i\)\.\\Delta\_\{\\ell\}\(i\)=\\Delta\(i\_\{\\ell\}^\{\\star\}\\mid G^\{\\star\}\_\{\\ell\-1\}\)\-\\Delta\(i\\mid G^\{\\star\}\_\{\\ell\-1\}\)\>0,\\quad i\\neq i\_\{\\ell\}^\{\\star\},\\qquad\\Delta\_\{\\min\}=\\min\_\{\\ell\\in\[k\]\}\\min\_\{i\\neq i\_\{\\ell\}^\{\\star\}\}\\Delta\_\{\\ell\}\(i\)\.

#### Deviation of optimistic marginal gains

ForS⊆\[n\]S\\subseteq\[n\]andi∉Si\\notin S, writeΔtUCB​\(i∣S\)=HVtUCB​\(S∪\{i\}\)−HVtUCB​\(S\)\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(i\\mid S\)=\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\\cup\\\{i\\\}\)\-\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)\.

###### Lemma 4\(Deviation of optimistic marginal gains\)\.

Onℰ\\mathcal\{E\}, for everyS⊆\[n\]S\\subseteq\[n\]andi∉Si\\notin S,

ΔtUCB​\(i∣S\)≤Δ​\(i∣S\)\+Cd​∑j∈S∪\{i\}βj​\(t\),ΔtUCB​\(i∣S\)≥Δ​\(i∣S\)−Cd​∑j∈Sβj​\(t\)\.\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(i\\mid S\)\\leq\\Delta\(i\\mid S\)\+C\_\{d\}\\sum\_\{j\\in S\\cup\\\{i\\\}\}\\beta\_\{j\}\(t\),\\qquad\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(i\\mid S\)\\geq\\Delta\(i\\mid S\)\-C\_\{d\}\\sum\_\{j\\in S\}\\beta\_\{j\}\(t\)\.

###### Proof\.

By Lemma[3](https://arxiv.org/html/2607.26273#Thmlemma3)applied toS∪\{i\}S\\cup\\\{i\\\}and toSS,HVtUCB​\(S∪\{i\}\)≤HV​\(S∪\{i\}\)\+Cd​∑j∈S∪\{i\}βj​\(t\)\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\\cup\\\{i\\\}\)\\leq\\mathrm\{HV\}\(S\\cup\\\{i\\\}\)\+C\_\{d\}\\sum\_\{j\\in S\\cup\\\{i\\\}\}\\beta\_\{j\}\(t\), while optimism givesHVtUCB​\(S\)≥HV​\(S\)\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)\\geq\\mathrm\{HV\}\(S\); subtracting gives the upper bound\. Symmetrically,HVtUCB​\(S∪\{i\}\)≥HV​\(S∪\{i\}\)\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\\cup\\\{i\\\}\)\\geq\\mathrm\{HV\}\(S\\cup\\\{i\\\}\)andHVtUCB​\(S\)≤HV​\(S\)\+Cd​∑j∈Sβj​\(t\)\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\)\\leq\\mathrm\{HV\}\(S\)\+C\_\{d\}\\sum\_\{j\\in S\}\\beta\_\{j\}\(t\)give the lower bound\. ∎

#### Per\-round deviation stage

Write the algorithm’s own greedy construction at roundttas a chainS^t,0=∅⊂S^t,1⊂⋯⊂S^t,k=St\\hat\{S\}\_\{t,0\}=\\emptyset\\subset\\hat\{S\}\_\{t,1\}\\subset\\cdots\\subset\\hat\{S\}\_\{t,k\}=S\_\{t\}, whereS^t,ℓ=S^t,ℓ−1∪\{ı^t,ℓ\}\\hat\{S\}\_\{t,\\ell\}=\\hat\{S\}\_\{t,\\ell\-1\}\\cup\\\{\\hat\{\\imath\}\_\{t,\\ell\}\\\}andı^t,ℓ∈arg⁡maxi∈At∖S^t,ℓ−1⁡ΔtUCB​\(i∣S^t,ℓ−1\)\\hat\{\\imath\}\_\{t,\\ell\}\\in\\arg\\max\_\{i\\in A\_\{t\}\\setminus\\hat\{S\}\_\{t,\\ell\-1\}\}\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(i\\mid\\hat\{S\}\_\{t,\\ell\-1\}\)\.333We assumeG⋆⊆AtG^\{\\star\}\\subseteq A\_\{t\}, i\.e\. that the safe\-pruning step never removes an arm that the true\-objective greedy benchmark would have selected; this is the intended behavior of the pruning rule but is not separately proved here\.Define the*first deviation stage*, comparing the algorithm’s trajectory to the benchmarkG⋆G^\{\\star\}:

ℓ†​\(t\)=min⁡\{ℓ∈\[k\]:S^t,ℓ≠Gℓ⋆\},\\ell^\{\\dagger\}\(t\)=\\min\\\{\\ell\\in\[k\]:\\hat\{S\}\_\{t,\\ell\}\\neq G^\{\\star\}\_\{\\ell\}\\\},withℓ†​\(t\)=\+∞\\ell^\{\\dagger\}\(t\)=\+\\inftyifS^t,ℓ=Gℓ⋆\\hat\{S\}\_\{t,\\ell\}=G^\{\\star\}\_\{\\ell\}for everyℓ∈\[k\]\\ell\\in\[k\]\(i\.e\.St=G⋆S\_\{t\}=G^\{\\star\}exactly\)\. This partitions\[T\]\[T\]into

Match=\{t:ℓ†​\(t\)=∞\},Devℓ=\{t:ℓ†​\(t\)=ℓ\}​\(ℓ∈\[k\]\),\[T\]=Match⊔⨆ℓ=1kDevℓ\.\\mathrm\{Match\}=\\\{t:\\ell^\{\\dagger\}\(t\)=\\infty\\\},\\qquad\\mathrm\{Dev\}\_\{\\ell\}=\\\{t:\\ell^\{\\dagger\}\(t\)=\\ell\\\}\\ \(\\ell\\in\[k\]\),\\qquad\[T\]=\\mathrm\{Match\}\\sqcup\\bigsqcup\_\{\\ell=1\}^\{k\}\\mathrm\{Dev\}\_\{\\ell\}\.By construction,t∈Devℓt\\in\\mathrm\{Dev\}\_\{\\ell\}meansS^t,ℓ−1=Gℓ−1⋆\\hat\{S\}\_\{t,\\ell\-1\}=G^\{\\star\}\_\{\\ell\-1\}— this is built into the partition, no induction over earlier rounds is needed\.

SinceR¯T=∑t=1Tr¯t\\bar\{R\}\_\{T\}=\\sum\_\{t=1\}^\{T\}\\bar\{r\}\_\{t\}exactly by \([2](https://arxiv.org/html/2607.26273#Sx3.E2)\), this partition refines the same per\-round sum bounded pointwise in \([3](https://arxiv.org/html/2607.26273#A1.E3)\): rather than controlling every termr¯t\\bar\{r\}\_\{t\}uniformly via Lemma[3](https://arxiv.org/html/2607.26273#Thmlemma3)and a single global Cauchy–Schwarz step \(as in the gap\-free bound above \), we now split

R¯T=∑t∈Matchr¯t\+∑ℓ=1k∑t∈Devℓr¯t,\\bar\{R\}\_\{T\}\\;=\\;\\sum\_\{t\\in\\mathrm\{Match\}\}\\bar\{r\}\_\{t\}\\;\+\\;\\sum\_\{\\ell=1\}^\{k\}\\sum\_\{t\\in\\mathrm\{Dev\}\_\{\\ell\}\}\\bar\{r\}\_\{t\},\(6\)and bound the two kinds of terms separately: we show below that the first sum is non\-positive; the remainder of this subsection bounds the second\.

#### Regret on matched rounds is non\-positive

We bound the first term of \([6](https://arxiv.org/html/2607.26273#A1.E6)\)\. Ift∈Matcht\\in\\mathrm\{Match\}, thenSt=G⋆S\_\{t\}=G^\{\\star\}\. By Fact[1](https://arxiv.org/html/2607.26273#Thmfact1)withf=HVf=\\mathrm\{HV\},G=G⋆G=G^\{\\star\},

r¯t=α​V⋆−HV​\(St\)=α​V⋆−HV​\(G⋆\)≤α​V⋆−α​V⋆=0\.\\bar\{r\}\_\{t\}=\\alpha\\,V^\{\\star\}\-\\mathrm\{HV\}\(S\_\{t\}\)=\\alpha\\,V^\{\\star\}\-\\mathrm\{HV\}\(G^\{\\star\}\)\\;\\leq\\;\\alpha\\,V^\{\\star\}\-\\alpha\\,V^\{\\star\}=0\.

#### Witness\-counting bound on deviation rounds

Fixℓ\\ellandt∈Devℓt\\in\\mathrm\{Dev\}\_\{\\ell\}, and writei:=ı^t,ℓ≠iℓ⋆i:=\\hat\{\\imath\}\_\{t,\\ell\}\\neq i\_\{\\ell\}^\{\\star\}\. Sinceiiwas chosen overiℓ⋆i\_\{\\ell\}^\{\\star\}at stageℓ\\ellof roundtt,ΔtUCB​\(i∣Gℓ−1⋆\)≥ΔtUCB​\(iℓ⋆∣Gℓ−1⋆\)\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(i\\mid G^\{\\star\}\_\{\\ell\-1\}\)\\geq\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(i\_\{\\ell\}^\{\\star\}\\mid G^\{\\star\}\_\{\\ell\-1\}\)\. Applying Lemma[4](https://arxiv.org/html/2607.26273#Thmlemma4)atS=Gℓ−1⋆S=G^\{\\star\}\_\{\\ell\-1\},

Δ​\(i∣Gℓ−1⋆\)\+Cd​∑j∈Gℓ−1⋆∪\{i\}βj​\(t\)≥Δ​\(iℓ⋆∣Gℓ−1⋆\)−Cd​∑j∈Gℓ−1⋆βj​\(t\),\\Delta\(i\\mid G^\{\\star\}\_\{\\ell\-1\}\)\+C\_\{d\}\\sum\_\{j\\in G^\{\\star\}\_\{\\ell\-1\}\\cup\\\{i\\\}\}\\beta\_\{j\}\(t\)\\;\\geq\\;\\Delta\(i\_\{\\ell\}^\{\\star\}\\mid G^\{\\star\}\_\{\\ell\-1\}\)\-C\_\{d\}\\sum\_\{j\\in G^\{\\star\}\_\{\\ell\-1\}\}\\beta\_\{j\}\(t\),so, using\|Gℓ−1⋆\|=ℓ−1\|G^\{\\star\}\_\{\\ell\-1\}\|=\\ell\-1,

Δℓ​\(i\)≤Cd​\(2​∑j∈Gℓ−1⋆βj​\(t\)\+βi​\(t\)\)≤Cd​\(2​ℓ−1\)​maxj∈Gℓ−1⋆∪\{i\}⁡βj​\(t\)\.\\Delta\_\{\\ell\}\(i\)\\;\\leq\\;C\_\{d\}\\Bigl\(2\\sum\_\{j\\in G^\{\\star\}\_\{\\ell\-1\}\}\\beta\_\{j\}\(t\)\+\\beta\_\{i\}\(t\)\\Bigr\)\\;\\leq\\;C\_\{d\}\(2\\ell\-1\)\\max\_\{j\\in G^\{\\star\}\_\{\\ell\-1\}\\cup\\\{i\\\}\}\\beta\_\{j\}\(t\)\.Hence there exists a*witness*w​\(t\)∈Gℓ−1⋆∪\{i\}w\(t\)\\in G^\{\\star\}\_\{\\ell\-1\}\\cup\\\{i\\\}\(at mostℓ\\ellcandidates\) with

βw​\(t\)​\(t\)≥Δℓ​\(i\)Cd​\(2​ℓ−1\)≥ΔminCd​\(2​ℓ−1\),\\beta\_\{w\(t\)\}\(t\)\\;\\geq\\;\\frac\{\\Delta\_\{\\ell\}\(i\)\}\{C\_\{d\}\(2\\ell\-1\)\}\\;\\geq\\;\\frac\{\\Delta\_\{\\min\}\}\{C\_\{d\}\(2\\ell\-1\)\},soNw​\(t\)​\(t−1\)≤mℓ:=2​η​Cd2​\(2​ℓ−1\)2​log⁡\(n​d​T2/δ\)Δmin2=O​\(ℓ2​log⁡TΔmin2\)\.\\text\{so\}\\qquad N\_\{w\(t\)\}\(t\-1\)\\;\\leq\\;m\_\{\\ell\}:=\\frac\{2\\eta C\_\{d\}^\{2\}\(2\\ell\-1\)^\{2\}\\log\(ndT^\{2\}/\\delta\)\}\{\\Delta\_\{\\min\}^\{2\}\}=O\\\!\\left\(\\frac\{\\ell^\{2\}\\log T\}\{\\Delta\_\{\\min\}^\{2\}\}\\right\)\.SinceGℓ−1⋆∪\{i\}=S^t,ℓ⊆StG^\{\\star\}\_\{\\ell\-1\}\\cup\\\{i\\\}=\\hat\{S\}\_\{t,\\ell\}\\subseteq S\_\{t\}, the witnessw​\(t\)w\(t\)is pulled at roundtt\. GroupDevℓ\\mathrm\{Dev\}\_\{\\ell\}by witness identity: for fixedw∈\[n\]w\\in\[n\], everyt∈Devℓt\\in\\mathrm\{Dev\}\_\{\\ell\}withw​\(t\)=ww\(t\)=wincrementsNwN\_\{w\}by exactly11whileNw​\(t−1\)≤mℓN\_\{w\}\(t\-1\)\\leq m\_\{\\ell\}; there are at mostmℓ\+1m\_\{\\ell\}\+1such rounds\. Summing overw∈\[n\]w\\in\[n\],

\|Devℓ\|≤n​\(mℓ\+1\)=O​\(n​ℓ2​log⁡TΔmin2\)\.\|\\mathrm\{Dev\}\_\{\\ell\}\|\\;\\leq\\;n\\,\(m\_\{\\ell\}\+1\)\\;=\\;O\\\!\\left\(\\frac\{n\\ell^\{2\}\\log T\}\{\\Delta\_\{\\min\}^\{2\}\}\\right\)\.\(7\)

#### Bounding total regret on deviation rounds

We now bound the second term of \([6](https://arxiv.org/html/2607.26273#A1.E6)\),∑ℓ=1k∑t∈Devℓr¯t\\sum\_\{\\ell=1\}^\{k\}\\sum\_\{t\\in\\mathrm\{Dev\}\_\{\\ell\}\}\\bar\{r\}\_\{t\}\. A naive approach would boundr¯t≤1\\bar\{r\}\_\{t\}\\leq 1on every round ofDevℓ\\mathrm\{Dev\}\_\{\\ell\}and multiply by the count\|Devℓ\|=O​\(n​ℓ2​log⁡T/Δmin2\)\|\\mathrm\{Dev\}\_\{\\ell\}\|=O\(n\\ell^\{2\}\\log T/\\Delta\_\{\\min\}^\{2\}\)from \([7](https://arxiv.org/html/2607.26273#A1.E7)\), giving a regret scaling as1/Δmin21/\\Delta\_\{\\min\}^\{2\}\. We avoid this by bounding the*total*regret overDevℓ\\mathrm\{Dev\}\_\{\\ell\}directly, via the same Cauchy–Schwarz idea as in the*gap\-free bound*Section above — applied*locally*toDevℓ\\mathrm\{Dev\}\_\{\\ell\}rather than to the full horizon\. Since that argument scales as the*square root*of the number of rounds involved, it converts the1/Δmin21/\\Delta\_\{\\min\}^\{2\}scale of the count into a1/Δmin1/\\Delta\_\{\\min\}contribution to regret\.

Onℰ\\mathcal\{E\}, the pointwise bound \([3](https://arxiv.org/html/2607.26273#A1.E3)\) together with Lemma[3](https://arxiv.org/html/2607.26273#Thmlemma3)gives, for every roundtt,

r¯t≤HVtUCB​\(St\)−HV​\(St\)≤Cd​∑i∈Stβi​\(t\)\.\\bar\{r\}\_\{t\}\\;\\leq\\;\\mathrm\{HV\}\_\{t\}^\{\\mathrm\{UCB\}\}\(S\_\{t\}\)\-\\mathrm\{HV\}\(S\_\{t\}\)\\;\\leq\\;C\_\{d\}\\sum\_\{i\\in S\_\{t\}\}\\beta\_\{i\}\(t\)\.
Fixℓ∈\[k\]\\ell\\in\[k\], and fori∈\[n\]i\\in\[n\]letDi=\{t∈Devℓ:i∈St\}D\_\{i\}=\\\{t\\in\\mathrm\{Dev\}\_\{\\ell\}:i\\in S\_\{t\}\\\}be the \(possibly empty\) set of rounds, among those at which the trajectory first departs fromG⋆G^\{\\star\}at stageℓ\\ell, where armiihappens to be pulled\. The pull countNi​\(t−1\)N\_\{i\}\(t\-1\)increases by exactly11at each pull ofii, so asttranges overDiD\_\{i\}\(a set of pulls ofii\), the valuesNi​\(t−1\)N\_\{i\}\(t\-1\)are pairwise distinct; hence theirjj\-th smallest value is at leastj−1j\-1\. Sinceβi​\(t\)∝Ni​\(t−1\)−1/2\\beta\_\{i\}\(t\)\\propto N\_\{i\}\(t\-1\)^\{\-1/2\}is decreasing, this bounds the sum by the worst case whereDiD\_\{i\}consists of armii’s*earliest*\|Di\|\|D\_\{i\}\|pulls:

∑t∈Diβi​\(t\)≤∑s=1\|Di\|2​η​log⁡\(n​d​T2/δ\)s≤2​2​η​log⁡\(n​d​T2/δ\)​\|Di\|=O​\(\|Di\|​log⁡T\),\\sum\_\{t\\in D\_\{i\}\}\\beta\_\{i\}\(t\)\\;\\leq\\;\\sum\_\{s=1\}^\{\|D\_\{i\}\|\}\\sqrt\{\\frac\{2\\eta\\log\(ndT^\{2\}/\\delta\)\}\{s\}\}\\;\\leq\\;2\\sqrt\{2\\eta\\log\(ndT^\{2\}/\\delta\)\}\\,\\sqrt\{\|D\_\{i\}\|\}\\;=\\;O\\bigl\(\\sqrt\{\|D\_\{i\}\|\\log T\}\\bigr\),using∑s=1ms−1/2≤2​m\\sum\_\{s=1\}^\{m\}s^\{\-1/2\}\\leq 2\\sqrt\{m\}andlog⁡\(n​d​T2/δ\)=O​\(log⁡T\)\\log\(ndT^\{2\}/\\delta\)=O\(\\log T\)— the same argument as in the*gap\-free bound*Section, restricted toDi⊆\{D\_\{i\}\\subseteq\\\{pulls ofi\}i\\\}instead of all ofii’s pulls over\[T\]\[T\]\.

Hence

∑t∈Devℓ∑i∈Stβi​\(t\)=∑i=1n∑t∈Diβi​\(t\)=O​\(log⁡T​∑i=1n\|Di\|\)\.\\sum\_\{t\\in\\mathrm\{Dev\}\_\{\\ell\}\}\\sum\_\{i\\in S\_\{t\}\}\\beta\_\{i\}\(t\)=\\sum\_\{i=1\}^\{n\}\\sum\_\{t\\in D\_\{i\}\}\\beta\_\{i\}\(t\)=O\\Bigl\(\\sqrt\{\\log T\}\\sum\_\{i=1\}^\{n\}\\sqrt\{\|D\_\{i\}\|\}\\Bigr\)\.
Since\|St\|=k\|S\_\{t\}\|=kfor everytt, we have∑i=1n\|Di\|=∑t∈Devℓ∑i=1n𝟏​\{i∈St\}=∑t∈Devℓ\|St\|=k​\|Devℓ\|\\sum\_\{i=1\}^\{n\}\|D\_\{i\}\|=\\sum\_\{t\\in\\mathrm\{Dev\}\_\{\\ell\}\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{i\\in S\_\{t\}\\\}=\\sum\_\{t\\in\\mathrm\{Dev\}\_\{\\ell\}\}\|S\_\{t\}\|=k\|\\mathrm\{Dev\}\_\{\\ell\}\|\. Next, by Cauchy–Schwarz \(withai=1a\_\{i\}=1,bi=\|Di\|b\_\{i\}=\\sqrt\{\|D\_\{i\}\|\}\),

∑i=1n\|Di\|≤n​∑i=1n\|Di\|=n​k​\|Devℓ\|\.\\sum\_\{i=1\}^\{n\}\\sqrt\{\|D\_\{i\}\|\}\\;\\leq\\;\\sqrt\{n\}\\,\\sqrt\{\\sum\_\{i=1\}^\{n\}\|D\_\{i\}\|\}\\;=\\;\\sqrt\{nk\|\\mathrm\{Dev\}\_\{\\ell\}\|\}\.
Therefore

∑t∈Devℓr¯t≤Cd​∑t∈Devℓ∑i∈Stβi​\(t\)=O​\(n​k​\|Devℓ\|​log⁡T\)=O​\(n​ℓ​k​log⁡TΔmin\),\\sum\_\{t\\in\\mathrm\{Dev\}\_\{\\ell\}\}\\bar\{r\}\_\{t\}\\;\\leq\\;C\_\{d\}\\sum\_\{t\\in\\mathrm\{Dev\}\_\{\\ell\}\}\\sum\_\{i\\in S\_\{t\}\}\\beta\_\{i\}\(t\)\\;=\\;O\\bigl\(\\sqrt\{nk\|\\mathrm\{Dev\}\_\{\\ell\}\|\\log T\}\\bigr\)\\;=\\;O\\\!\\left\(\\frac\{n\\ell\\sqrt\{k\}\\,\\log T\}\{\\Delta\_\{\\min\}\}\\right\),using \([7](https://arxiv.org/html/2607.26273#A1.E7)\) in the last step\. Summing overℓ∈\[k\]\\ell\\in\[k\]\(using∑ℓ=1kℓ=O​\(k2\)\\sum\_\{\\ell=1\}^\{k\}\\ell=O\(k^\{2\}\)\) and combining with \([6](https://arxiv.org/html/2607.26273#A1.E6)\) and the non\-positive first term,

R¯T≤∑ℓ=1kO​\(n​ℓ​k​log⁡TΔmin\)=O​\(n​k2\.5​log⁡TΔmin\)on​ℰ\.\\bar\{R\}\_\{T\}\\;\\leq\\;\\sum\_\{\\ell=1\}^\{k\}O\\\!\\left\(\\frac\{n\\ell\\sqrt\{k\}\\log T\}\{\\Delta\_\{\\min\}\}\\right\)\\;=\\;O\\\!\\left\(\\frac\{nk^\{2\.5\}\\log T\}\{\\Delta\_\{\\min\}\}\\right\)\\qquad\\text\{on \}\\mathcal\{E\}\.
###### Theorem 2\(Gap\-dependent bound \(detailed version\)\)\.

Onℰ\\mathcal\{E\},R¯T=O​\(n​k2\.5​log⁡T/Δmin\)\\bar\{R\}\_\{T\}=O\\bigl\(nk^\{2\.5\}\\log T/\\Delta\_\{\\min\}\\bigr\)\.

### Combining both bounds

Since rewards lie in\[0,1\]d\[0,1\]^\{d\},r¯t∈\[0,1\]\\bar\{r\}\_\{t\}\\in\[0,1\]andR¯T≤T\\bar\{R\}\_\{T\}\\leq Talways \(on or offℰ\\mathcal\{E\}\)\. Hence

𝔼​\[R¯T\]=𝔼​\[R¯T​𝟏ℰ\]\+𝔼​\[R¯T​𝟏ℰc\]≤min⁡\{O​\(Cd​n​k​T​log⁡T\),O​\(n​k2\.5​log⁡T/Δmin\)\}\+T​ℙ​\(ℰc\)\.\\mathbb\{E\}\[\\bar\{R\}\_\{T\}\]=\\mathbb\{E\}\[\\bar\{R\}\_\{T\}\\mathbf\{1\}\_\{\\mathcal\{E\}\}\]\+\\mathbb\{E\}\[\\bar\{R\}\_\{T\}\\mathbf\{1\}\_\{\\mathcal\{E\}^\{c\}\}\]\\leq\\min\\Bigl\\\{O\\bigl\(C\_\{d\}\\sqrt\{nkT\\log T\}\\bigr\),\\,O\\bigl\(nk^\{2\.5\}\\log T/\\Delta\_\{\\min\}\\bigr\)\\Bigr\\\}\+T\\,\\mathbb\{P\}\(\\mathcal\{E\}^\{c\}\)\.Choosingδ=1/T\\delta=1/TgivesT​ℙ​\(ℰc\)≤1T\\,\\mathbb\{P\}\(\\mathcal\{E\}^\{c\}\)\\leq 1, so:

###### Theorem 3\(Regret ofTHV\-UCB\(detailed version\)\)\.

Withδ=1/T\\delta=1/T,

𝔼​\[R¯T\]≤min⁡\{O​\(n​k​T​log⁡T\),O​\(n​k2\.5​log⁡T/Δmin\)\}\+O​\(1\)\.\\mathbb\{E\}\[\\bar\{R\}\_\{T\}\]\\;\\leq\\;\\min\\Bigl\\\{O\\bigl\(\\sqrt\{nkT\\log T\}\\bigr\),\\;O\\bigl\(nk^\{2\.5\}\\log T/\\Delta\_\{\\min\}\\bigr\)\\Bigr\\\}\+O\(1\)\.In particular𝔼​\[R¯T\]/T→0\\mathbb\{E\}\[\\bar\{R\}\_\{T\}\]/T\\to 0: THV\-UCB achieves sublinearα\\alpha\-approximation regret\.

### Discussion: what does each bound use from the algorithm?

The two guarantees of Theorem[3](https://arxiv.org/html/2607.26273#Thmtheorem3a)are not in competition; they cover complementary regimes, exactly as the minimax and gap\-dependent bounds do for classicalKK\-armed UCB\. The gap\-free bound \(Theorem[1](https://arxiv.org/html/2607.26273#Thmtheorem1a)\) is*algorithm\-agnostic*: its proof only uses thatkkarms are pulled per round and that confidence widths shrink at rate1/Ni​\(t−1\)1/\\sqrt\{N\_\{i\}\(t\-1\)\}; it never degrades, even asΔmin→0\\Delta\_\{\\min\}\\to 0, the regime where the gap\-dependent bound diverges\. Conversely, the gap\-dependent bound \(Theorem[2](https://arxiv.org/html/2607.26273#Thmtheorem2a)\) is*mechanism\-aware*: it tracks, round by round, the exact comparisonsΔtUCB\(⋅∣Gℓ−1⋆\)\\Delta\_\{t\}^\{\\mathrm\{UCB\}\}\(\\cdot\\mid G^\{\\star\}\_\{\\ell\-1\}\)that the greedy step ofTHV\-UCBperforms against the benchmark trajectoryG⋆G^\{\\star\}— note thatG⋆G^\{\\star\}, unlikeS⋆S^\{\\star\}, never appears in the regret’s definition; it is purely an internal proof device for tracking the algorithm’s stage\-wise progress\. Its proof combines two ingredients: a witness\-counting argument bounding how many rounds can deviate fromG⋆G^\{\\star\}at each stage \(see \([7](https://arxiv.org/html/2607.26273#A1.E7)\)\), and a Cauchy–Schwarz argument bounding the*total*regret accrued on those rounds\.

## Appendix BExperimental details

### Optimal values \(Grid search\)

Table 2:Optimal confidence parameterη⋆\\eta^\{\\star\}per algorithm and front geometry, selected by grid search over\{0\.01,0\.1,0\.3,1\.0\}\\\{0\.01,0\.1,0\.3,1\.0\\\}\(maximizingHVlast100\\mathrm\{HV\}\_\{\\mathrm\{last100\}\}\)\. All detailed results are available inhttps://ngutowski\.fr/gridsearch/gridsearch\.html
### Additional results ford=3d=3andk=4k=4

Table 3:Summary over four synthetic fronts \(d=3d=3,n=60n=60,k=4k=4,σ=0\.035\\sigma=0\.035,T=3000T=3000, 10 seeds\)\.Fid\.indicates fidelity to the cited work:∙\\bullet= faithful top\-kkadaptation \(core mechanism unchanged\);∘\\circ= our extension \(modified core, tie\-break, or diversity mechanism not in the original\)\.\+denotes our variant when both versions share a citation\. Final Regret values are cumulativeα\\alpha\-regret±\\pm95% CI\.
### Additional results ford=4d=4andk=5k=5

Table 4:Summary over four synthetic fronts \(d=4d=4,n=100n=100,k=5k=5,σ=0\.025\\sigma=0\.025,T=5000T=5000, 10 seeds\)\.Fid\.indicates fidelity to the cited work:∙\\bullet= faithful top\-kkadaptation \(core mechanism unchanged\);∘\\circ= our extension \(modified core, tie\-break, or diversity mechanism not in the original\)\.\+denotes our variant when both versions share a citation\. Final Regret values are cumulativeα\\alpha\-regret±\\pm95% CI\.
### Additional results ford=5d=5andk=6k=6

Table 5:Summary over four synthetic fronts \(d=5d=5,n=150n=150,k=6k=6,σ=0\.02\\sigma=0\.02,T=5000T=5000, 10 seeds\)\.Fid\.indicates fidelity to the cited work:∙\\bullet= faithful top\-kkadaptation \(core mechanism unchanged\);∘\\circ= our extension \(modified core, tie\-break, or diversity mechanism not in the original\)\.\+denotes our variant when both versions share a citation\. Final Regret values are cumulativeα\\alpha\-regret±\\pm95% CI\.![Refer to caption](https://arxiv.org/html/2607.26273v1/x5.png)\(a\)Clusters
![Refer to caption](https://arxiv.org/html/2607.26273v1/x6.png)\(b\)Concave
![Refer to caption](https://arxiv.org/html/2607.26273v1/x7.png)\(c\)Convex
![Refer to caption](https://arxiv.org/html/2607.26273v1/x8.png)\(d\)Linear

Figure 5:HypervolumeHV​\(St\)\\mathrm\{HV\}\(S\_\{t\}\)trajectories \(moving average,w=50w=50\) with95%95\\%CIs, over four synthetic Pareto front geometries \(d=3d=3,n=60n=60,k=4k=4,σ=0\.035\\sigma=0\.035,T=3000T=3000, 10 seeds\)\. Each panel shows the best representative per algorithm family against THV\-UCB \(ours\)\.![Refer to caption](https://arxiv.org/html/2607.26273v1/x9.png)\(a\)Clusters
![Refer to caption](https://arxiv.org/html/2607.26273v1/x10.png)\(b\)Concave
![Refer to caption](https://arxiv.org/html/2607.26273v1/x11.png)\(c\)Convex
![Refer to caption](https://arxiv.org/html/2607.26273v1/x12.png)\(d\)Linear

Figure 6:HypervolumeHV​\(St\)\\mathrm\{HV\}\(S\_\{t\}\)trajectories \(moving average,w=50w=50\) with95%95\\%CIs, over four synthetic Pareto front geometries \(d=4d=4,n=100n=100,k=5k=5,σ=0\.025\\sigma=0\.025,T=5000T=5000, 10 seeds\)\. Each panel shows the best representative per algorithm family against THV\-UCB \(ours\)\.![Refer to caption](https://arxiv.org/html/2607.26273v1/x13.png)\(a\)Clusters
![Refer to caption](https://arxiv.org/html/2607.26273v1/x14.png)\(b\)Concave
![Refer to caption](https://arxiv.org/html/2607.26273v1/x15.png)\(c\)Convex
![Refer to caption](https://arxiv.org/html/2607.26273v1/x16.png)\(d\)Linear

Figure 7:HypervolumeHV​\(St\)\\mathrm\{HV\}\(S\_\{t\}\)trajectories \(moving average,w=50w=50\) with95%95\\%CIs, over four synthetic Pareto front geometries \(d=5d=5,n=150n=150,k=6k=6,σ=0\.02\\sigma=0\.02,T=5000T=5000, 10 seeds\)\. Each panel shows the best representative per algorithm family against THV\-UCB \(ours\)\.
### Statistical tests

Table 6:Paired statistical comparisons between THV\-UCB and the second\-best baseline on the settings with the tightest margins \(10 random seeds, paired by environment seed\)\.Δ\\Deltadenotes the mean difference inHVlast100\\mathrm\{HV\}\_\{\\text\{last100\}\}\(THV\-UCB−\-baseline\)\. Bootstrap 95% CIs are computed overB=10,000B=10\{,\}000resamples\. Wilcoxon signed\-rank tests are one\-sided \(H1H\_\{1\}: THV\-UCB\>\>baseline\);Wins= number of seeds \(out of 10\) on which THV\-UCB outperforms the baseline\.

## Appendix CNotation summary

Table 7:Notation summary\.