Paper deep dive
Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
Nicolas Gutowski, Fabien Chhel, Alexandre Letard, Sylvain Lamprier
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/4/2026, 10:23:55 AM
Summary
This paper introduces the Top-k Pareto Bandits problem, addressing multi-objective slate selection where an agent selects a subset of k arms to approximate the Pareto frontier. The authors propose THV-UCB, an algorithm that greedily maximizes marginal hypervolume using optimistic confidence bounds. They provide theoretical regret bounds (gap-free and gap-dependent) and demonstrate empirical superiority over existing methods in approximating Pareto fronts.
Entities (8)
Relation Signals (7)
Nicolas Gutowski → authored → Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
confidence 99% · Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection Nicolas Gutowski
Fabien Chhel → authored → Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
confidence 99% · Nicolas Gutowski1, Fabien Chhel2,1
Alexandre Letard → authored → Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
confidence 99% · Alexandre Letard4,3,1
Sylvain Lamprier → authored → Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
confidence 99% · Sylvain Lamprier1
THV-UCB → solves → Top-k Pareto Bandits
confidence 95% · To address this problem, we introduce THV-UCB... We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of k arms
THV-UCB → usesmetric → Hypervolume
confidence 92% · THV-UCB, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions.
THV-UCB → achievesregretbound → O~(d*sqrt(nkT))
confidence 90% · We establish a gap-free regret bound O~(d*sqrt(nkT)) that holds on every instance
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of $k$ arms and observes their $d$-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an $\alpha$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight, where $\alpha = 1 - 1/e$ reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce \textit{THV-UCB}, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound $\tilde{O}(d\sqrt{nkT})$ that holds on every instance, together with a gap-dependent bound $\tilde{O}(nk^{2.5}/\Delta_{\min})$ that becomes polylogarithmic in $T$ once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications.
Tags
Links
- Source: https://arxiv.org/abs/2607.26273v1
- Canonical: https://arxiv.org/abs/2607.26273v1
Trouble viewing inline? Open PDF directly →
Full Text
93,275 characters extracted from source content.
Expand or collapse full text
Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection Nicolas Gutowski1, Fabien Chhel2,1, Alexandre Letard4,3,1, Sylvain Lamprier1 Abstract We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of k arms and observes their d-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an α-approximate hypervolume regret with respect to the best size-k subset achievable in hindsight, where α=1−1/eα=1-1/e reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce THV-UCB, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound O~(dnkT) O(d nkT) that holds on every instance, together with a gap-dependent bound O~(nk2.5/Δmin) O(nk^2.5/ _ ) that becomes polylogarithmic in T once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications. 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 (Tian et al. 2021; Fromer and Coley 2023). 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 (Letard et al. 2024; Zaizi et al. 2025), profit vs. inventory in market making (Fernández Vicente et al. 2026), efficacy vs. toxicity in clinical trials (KONE et al. 2023; Kone et al. 2025a). Three complementary aims drive contemporary research: 1) approximating the Pareto front faithfully and uniformly (KONE et al. 2023; Kone et al. 2025b, a; Shahverdikondori et al. 2025), 2) doing so under the noisy, sample-limited feedback that characterizes online and bandit settings to minimize Pareto regret (Mandow et al. 2023; Xu and Klabjan 2023; Cao et al. 2025; Hüyük and Tekin 2021; Xue et al. 2025), and 3) measuring progress through unary, preference-free indicators such as the dominated hypervolume (Guerreiro et al. 2021). This third line formalizes MOO progress through the dominated hypervolume (HV) (Guerreiro et al. 2021), 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 (Zhang et al. 2023; Zhang 2024) and in multi-objective reinforcement learning (Liu et al. 2025a, b; Lee et al. 2026; Röpke et al. 2025; Song et al. 2025; Fernández Vicente et al. 2026; Letard et al. 2024). Previous works, however, either operate in continuous black-box domains, query a single point per round, do not scale with the number of objective d>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 introducing THV-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 round t, the agent selects a slate StS_t of k arms from a set of n candidates and observes their d−d-dimensional reward vectors under semi-bandit feedback. The performance of StS_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 size k. Our main contributions can be summarized as follows : 1. We introduce the Top-k Pareto bandit setting and define an α-approximation hypervolume regret with respect to the best size-k subset of the Pareto frontier, more suited for many real-world scenarios ; 2. We extend previous competitive works (Drugan and Nowe 2013; Deb et al. 2002; Yahyaa and Manderick 2015; Mandow et al. 2023; Auer et al. 2002; Paria et al. 2020; Zhang and Golovin 2020; Zhang 2024) from Pareto optimization and scalarization methods to this setting and empirically evaluate them for hypervolume maximization in top-k semi-bandit setting considering 1) four synthetic fronts (linear, convex, concave and clusters) ; 2) d∈ℤ∩[2,5]d ∩[2,5] conflicting objectives (dimensions of the Pareto front) and associated top-k∈ℤ∩[3,6]k ∩[3,6] (slates-length - arms to be selected at each round) ; 3. We propose THV-UCB, an optimistic algorithm using coordinate-wise ℓ∞ _∞ confidence boxes and greedy selection on optimistic marginal HV gains. The construction differs from the random HV scalarizations of (Zhang and Golovin 2020; Zhang et al. 2024) by directly exploiting the submodularity of HV in a discrete k-armed slate setting. Empirically, THV-UCB achieves the lowest cumulative α-regret and the highest hypervolume in all four front geometries and dimensions by a margin increasing with d. Theoretically, we prove a gap-free regret bound O~(dnkT) O\! (d nkT ), and a gap-dependent regret bound O~(nk2.5Δmin) O\! ( nk^2.5 _ ) that are polylogarithmic in T. The paper is organized as follows: Related Work reviews prior literature. Problem Setting depicts the problem setting and regret definition, while Top-k HyperVolume 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 (Tian et al. 2021; Ghanbarzadeh et al. 2026; Jiju and Manemaran 2025; Chen et al. 2025; He et al. 2026; Zaizi et al. 2025), 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 (Zhang et al. 2023; Cai et al. 2023; Chen et al. 2023; Lee et al. 2026; Fernández Vicente et al. 2026). More specifically, HV-driven Pareto Set Learning methods maximizes HV via gradient descent on a neural preference-conditioned model (Zhang et al. 2023; Zhang 2024), while HV-based MORL embeds HV in policy optimization (Röpke et al. 2025; Song et al. 2025). However, as stated by Zhang et al. (Zhang et al. 2024), 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 to d=4d=4 objectives, 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; Q. Yahyaa et al. 2014; Yahyaa and Manderick 2015; Roijers et al. 2017; Xu and Klabjan 2023). Following them, several works extend regret-minimizing MOMAB through various scalarization techniques like : Chebyshev (Mandow et al. 2023), lexicographic priorities (Hüyük and Tekin 2021), lexicographic linear bandits (Xue et al. 2025), and preference-aware customization (Cao et al. 2025). A parallel line studies pure exploration goals, such as identifying feasible arms or approximating the Pareto set up to a relaxation tolerance, including ε -relaxed Pareto set identification, constrained variants, and best-group Identification (Katz-Samuels and Scott 2018; KONE et al. 2023; Kone et al. 2025b; Shahverdikondori et al. 2025). These works typically aim to recover a large fraction of the Pareto set rather than maintaining a small representative subset of fixed size k. Scalarization methods, considering either a single aggregated utility function (Busa-Fekete et al. 2017; Roijers et al. 2013, 2017; Mandow et al. 2023) or several different trade-offs (Zhang and Golovin 2020; Letard et al. 2024; Zhang 2024; Cao et al. 2025; Liu et al. 2025a, b), are often most convenient for the online bandit setup. However these methods involve a fixed distribution of preferences (Roijers et al. 2013, 2017; Zhang 2024) and do not directly address set-level hypervolume of a size-k slate 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) with O~(T) O( T) HV-regret bounds for UCB/TS Bayesian optimization. Later, these bounds were further refined by (Zhang 2024), who establish an optimal hypervolume regret bound of O(T−1/k)O(T^-1/k) The problems studied by Kone et al. (KONE et al. 2023; Kone et al. 2025b) and (Zhang 2024) 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 (Zhang et al. 2023) and (Zhang et al. 2024) from MORL literature. However, these works do not adress the discrete k-armed slate bandit setting we study. Problem Setting Arms, horizon, and rewards. We consider n arms indexed by [n]=1,…,n[n]=\1,…,n\ over a horizon of T rounds, with [T]=1,…,T[T]=\1,…,T\. Pulling arm i at round t yields a d-dimensional random reward vector i,t∈[0,1]dX_i,t∈[0,1]^d with unknown mean i=[i,t] μ_i=E[X_i,t]. We assume (i,t)t∈[T](X_i,t)_t∈[T] are independent across t and i, and each coordinate is η-sub-Gaussian (used for concentration); η also serves as the confidence parameter of the algorithm. Top-k actions and semi-bandit feedback. At each round t∈[T]t∈[T], the agent selects a subset St⊆[n]S_t [n] of size |St|=k|S_t|=k (a slate) and observes the vectors i,t:i∈St\X_i,t:i∈ S_t\ (semi-bandit feedback). Dominance and Pareto front. For ,∈ℝda,b ^d, write ⪯a if aj≤bja_j≤ b_j for all j∈[d]j∈[d], and ≺a if in addition at least one inequality is strict. Arm i Pareto-dominates arm j if i⪰j μ_i μ_j and i≠j μ_i≠ μ_j. The Pareto front P is the set of undominated mean vectors i:i∈[n]\ μ_i:i∈[n]\. Reference point and dominated hypervolume. Fix a reference point ∈ℝdr ^d such that ⪯ir μ_i for all i∈[n]i∈[n] (e.g., =r=0 when rewards lie in [0,1]d[0,1]^d). For any subset S⊆[n]S [n], its dominated hypervolume is HV(S)=λd(⋃i∈S[r1,μi1]×⋯×[rd,μid])HV(S)= _d\! ( _i∈ S[r_1, _i1]×·s×[r_d, _id] ) (1) where λd _d is the d-dimensional Lebesgue measure. The dominated hypervolume is a standard performance indicator in multi-objective optimization (Zitzler et al. 2003).111Any equivalent definition of dominated hypervolume can be used. Our analysis only relies on monotonicity and submodularity of HV(⋅)HV(·) 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). Let S⋆∈argmax|S|=kHV(S)S ∈ _|S|=kHV(S) denote a best subset of size k in hindsight, and V⋆=HV(S⋆)V =HV(S ) its hypervolume. The (ideal) instantaneous regret and cumulative regret are rt=V⋆−HV(St),RT=∑t=1Trt.r_t=V -HV(S_t), R_T= _t=1^Tr_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α=1-1/e, our guarantees are stated for the α-approximation regret r¯t=αV⋆−HV(St),R¯T=∑t=1Tr¯t. r_t=α V -HV(S_t), R_T= _t=1^T r_t. (2) This benchmark cleanly separates computational approximation (the α factor, unavoidable for any polynomial-time algorithm) from statistical learning (the gap between HV(St)HV(S_t) and what the algorithm could achieve with known means). Additional notation. We write log for the natural logarithm and O~(⋅) O(·) to hide polylogarithmic factors. Vectors are bold lowercase, sets uppercase, and ∥⋅∥∞\|·\|_∞ denotes the ℓ∞ _∞ norm. For any arm i, let Ni(t)N_i(t) be the number of times i has been selected up to (and including) round t, and let ^i(t) μ_i(t) denote its empirical mean vector. Table 7 in the appendix. Top-k HyperVolume UCB (THV-UCB) We now present THV-UCB, an optimistic algorithm that maintains coordinate-wise UCB boxes for each arm’s mean vector and constructs at every round a size-k subset by greedily maximizing the optimistic marginal hypervolume gain. UCB boxes (coordinate-wise optimism). At round t, for every arm i and objective j, we form an upper confidence bound ui,j(t)=μ^i,j(t−1)+βi(t)u_i,j(t)= μ_i,j(t-1)\;+\; _i(t) with βi(t)=2ηlog(ndt2/δ)max1,Ni(t−1) _i(t)= 2η \!(nd\,t^2/δ) \1,N_i(t-1)\ where η>0η>0 is a confidence parameter and δ∈(0,1)δ∈(0,1) is the target failure probability. This yields an optimistic vector i(t)=(ui,1(t),…,ui,d(t))u_i(t)=(u_i,1(t),…,u_i,d(t)). Optionally, since rewards lie in [0,1]d[0,1]^d, we clip i(t)u_i(t) coordinate-wise to [0,1][0,1]. THV-UCB: Greedy Subset Construction. Algorithm 1 describes our proposed method THV-UCB222The code of THV-UCB is available in our GitHub repository https://github.com/ngutowski/topk-pareto-bandits, which aims to maximize the hypervolume defined in (1) via a greedy construction of the subset StS_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 set AtA_t of arms that are not confidently dominated, i.e., arms that may still contribute to an optimal solution. The optimistic hypervolume HVtUCB(S)HV_t^UCB(S) is obtained by replacing the unknown means μi,j _i,j in (1) with their UCB counterparts ui,j(t)u_i,j(t). For any set S⊆[n]S [n] and arm i∉Si∉ S, we define the marginal UCB hypervolume gain as ΔHV,tUCB(i∣S)=HVtUCB(S∪i)−HVtUCB(S). ^UCB_HV,t(i S)=HV_t^UCB(S∪\i\)-HV_t^UCB(S). The subset StS_t is then constructed greedily: starting from S=∅S= , arms are sequentially added by maximizing ΔHV,tUCB(i∣S) ^UCB_HV,t(i S). This procedure yields a (1−1/e)(1-1/e)-approximation of max|S|=kHVtUCB(S), _|S|=kHV_t^UCB(S), by standard results on monotone submodular maximization. The selected arms in StS_t are then pulled and the statistics updated. From a computational perspective, computing ΔHV,tUCB(i∣S) ^UCB_HV,t(i S) for all candidates at each greedy step leads to a per-round complexity of O(kn⋅costHV)O(kn·costHV), where costHVcostHV denotes the cost of updating the hypervolume. In practice, incremental updates, dominance pruning, and the regime k≪nk n make the greedy selection efficient. Algorithm 1 THV-UCB: Top-k HyperVolume UCB 1: Input: subset size k, reference point r, confidence parameter η, failure level δ, horizon T, minimum pulls m0≥1m_0≥ 1 (default: m0=2m_0=2) 2: Init: Ni(0)←0N_i(0)← 0, ^i(0)← μ_i(0) 0 for all i∈[n]i∈[n]; set t←1t← 1 3: while ∃i∈[n]∃\,i∈[n] s.t. Ni(t−1)<m0N_i(t-1)<m_0 do 4: St←S_t← the k arms with smallest Ni(t−1)N_i(t-1) (ties broken arbitrarily) 5: Play all arms in StS_t, observe i,t:i∈St\X_i,t:i∈ S_t\, update Ni(t)N_i(t), ^i(t) μ_i(t) 6: t←t+1t← t+1 7: end while 8: for t to T do 9: for each arm i∈[n]i∈[n] do 10: βi(t)←2ηlog(ndt2/δ)max1,Ni(t−1) _i(t)← 2η (nd\,t^2/δ) \1,N_i(t-1)\ 11: i(t)←^i(t−1)+βi(t) 1du_i(t)← μ_i(t-1)+ _i(t)\,1_d 12: i(t)←^i(t−1)−βi(t) 1dL_i(t)← μ_i(t-1)- _i(t)\,1_d 13: end for 14: Safe pruning: 15: At←i∈[n]:∀j≠i,i(t)⋠j(t)A_t←\i∈[n]:∀\,j≠ i,\ u_i(t) _j(t)\ 16: if |At|<k|A_t|<k, set At←[n]A_t←[n] 17: S←∅S← 18: while |S|<k|S|<k do 19: Select i⋆∈argmaxi∈At∖SΔHV,tUCB(i∣S)i ∈ _i∈ A_t S ^UCB_HV,t(i S) 20: S←S∪i⋆S← S∪\i \ 21: end while 22: Play all arms in S, observe i,t:i∈S\X_i,t:i∈ S\, update Ni(t)N_i(t), ^i(t) μ_i(t) for i∈Si∈ S 23: end for Regret Analysis We establish two complementary guarantees on the α-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 in T as 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 α-regret R¯T R_T with α=1−1/eα=1-1/e . Benchmark and separation quantity. Recall S⋆∈argmax|S|=kHV(S)S ∈ _|S|=kHV(S) and V⋆=HV(S⋆)V =HV(S ) defined in (2). For the gap-dependent analysis, we introduce a second, purely proof-internal benchmark: let G⋆=i1⋆,…,ik⋆G =\i _1,…,i _k\ be built by greedy maximization of the true marginal gains Δ(i∣S)=HV(S∪i)−HV(S) (i S)=HV(S∪\i\)-HV(S), i.e. iℓ⋆∈argmaxi∉Gℓ−1⋆Δ(i∣Gℓ−1⋆)i _ ∈ _i∉ G _ -1 (i G _ -1), with Gℓ⋆=Gℓ−1⋆∪iℓ⋆G _ =G _ -1∪\i _ \ and G0⋆=∅G _0= . Assuming the greedy maximizer is unique at every stage, define the stage-ℓ gaps and the minimum gap Δℓ(i)=Δ(iℓ⋆∣Gℓ−1⋆)−Δ(i∣Gℓ−1⋆),Δmin=minℓ∈[k]mini≠iℓ⋆Δℓ(i) _ (i)= (i _ G _ -1)- (i G _ -1), _ = _ ∈[k] _i≠ i _ _ (i). Note that G⋆G never appears in the regret definition: the regret is always measured against V⋆V ; G⋆G only serves to track the algorithm’s stage-wise greedy progress in the analysis. We write ℰ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, see the appendix) , ℙ(ℰ)≥1−δP(E)≥ 1-δ. Finally, CdC_d denotes the coordinate-wise Lipschitz constant of the hypervolume; one may take Cd≤dC_d≤ d when rewards lie in [0,1]d[0,1]^d and r=0r=0. (Lemma 3, see the appendix). Theorem 1 (Gap-free bound (short version)). Assume each reward coordinate is η-sub-Gaussian and bounded in [0,1][0,1]. On ℰE, R¯T=O(CdnkTlogT). R_T\;=\;O\! (C_d nkT T ). Theorem 2 (Gap-dependent bound (short version)). Under the same assumptions, if the greedy maximizer of G⋆G is unique at every stage and the safe-pruning step never eliminates an arm of G⋆G , then on ℰE, R¯T=O(nk2.5logTΔmin). R_T\;=\;O\! ( nk^2.5 T _ ). Theorem 3 (Regret of THV-UCB (short version)). With δ=1/Tδ=1/T, [R¯T]≤ [ R_T ]≤ minO(nkTlogT), \O ( nkT T ), O(nk2.5logTΔmin)+O(1). O ( nk^2.5 T _ ) \+O(1). In particular [R¯T]/T→0E[ R_T]/T→ 0: THV-UCB achieves sublinear α-approximation regret on every instance. Proof sketch. Both bounds share the same reduction, then diverge. (1) Optimism reduction. On ℰE, coordinate-wise optimism gives HV(S)≤HVtUCB(S)HV(S) ^UCB_t(S) for every S. Since HVtUCBHV^UCB_t is itself monotone submodular, the greedy construction of StS_t is a (1−1/e)(1-1/e)-approximation of its maximizer, hence HVtUCB(St)≥αHVtUCB(S⋆)HV^UCB_t(S_t)≥α\,HV^UCB_t(S ), and r¯t≤HVtUCB(St)−HV(St). r_t\;≤\;HV^UCB_t(S_t)-HV(S_t). (2) Lipschitz control. The hypervolume is coordinate-wise Lipschitz, so the optimism error is at most Cd∑i∈Stβi(t)C_d _i∈ S_t _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)=kT _iN_i(T)=kT, yields Theorem 1. This step is blind to the selection mechanism: it only uses |St|=k|S_t|=k and βi(t)=Θ(1/Ni(t−1)) _i(t)= (1/ N_i(t-1)). (3b) Gap-dependent control. We instead track, at each round, the first stage ℓ at which the algorithm’s greedy chain departs from G⋆G . On matched rounds (St=G⋆S_t=G ) the α-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-ℓ deviations at O(nℓ2logT/Δmin2)O(n ^2 T/ _ ^2); applying the Cauchy–Schwarz argument of (3a) locally to these rounds converts this 1/Δmin21/ _ ^2 count into a 1/Δmin1/ _ regret contribution. Summing over stages yields Theorem 2. A discussion and the detailed versions of Theorems 1, 2 and 3 together with their full proofs, with all supporting lemmas and the corollary invoked above, are given in the appendix and in our GitHub repository https://github.com/ngutowski/topk-pareto-bandits. Experiments We empirically evaluate THV-UCB on controlled synthetic multi-objective bandit instances across four Pareto front geometries and four dimensions (d∈2,3,4,5d∈\2,3,4,5\, with slate size k∈3,4,5,6k∈\3,4,5,6\ and correspondingly varying total number of available arms n and horizon T), and compare it to representative baselines from the MO-bandit literature as well as scalarization-based methods adapted to the top-k semi-bandit setting. Experiments are conducted for d∈2,3,4,5d∈\2,3,4,5\ objectives. The dominated hypervolume (Zitzler et al. 2003) is computed exactly via inclusion-exclusion over the k-point slate, which remains tractable for small k. Figure 1 to 4 and Table 1 report results for d=2d=2; full results for d∈3,4,5d∈\3,4,5\, along with the grid search over the confidence parameter η are provided in the appendix and in our GitHub repository https://github.com/ngutowski/topk-pareto-bandits (Tables 2, 3, 4, and 5, Figures 5, 6, and 7). 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 for d=2d=2 and k=3k=3 Unless stated otherwise, experiments use d=2d=2, n=36n=36, k=3k=3, horizon T=2000T=2000, Gaussian noise level σ=0.05σ=0.05, reference point =∈ℝdr=0 ^d, and results are averaged over 1010 random seeds. Computing the benchmark V⋆V . For d=2d=2, V⋆V is computed by exhaustive enumeration over all (nk) nk candidate subsets. For d≥3d≥ 3, exhaustive enumeration becomes intractable, so we report HV(G⋆)≥αV⋆HV(G )≥α V (see Fact 1 in the appendix), a valid conservative proxy that does not affect relative comparisons between methods. At each round, we evaluate the selected slate StS_t using the pseudo-hypervolume HV(i:i∈St)HV(\ μ_i:i∈ S_t\) computed from the true means, to remove observation noise from the metrics. We report two complementary metrics: (i) the cumulative α-regret ∑t=1T(αV⋆−HV(St)) _t=1^T (α V -HV(S_t) ), where α=1−1/eα=1-1/e, which can be negative when a method consistently attains hypervolume above αV⋆α V ; and (i) the hypervolume trajectory HV(St)HV(S_t), plotted as a moving average (window w=50w=50) with 95%95\% confidence intervals across seeds. Synthetic Environments We generate instances by mixing a structured Pareto frontier with dominated distractors. A fraction nfront=max10,⌊0.35n⌋n_front= \10, 0.35n \ arms lie on a parametric frontier defined via the angular parameterization of DTLZ (Deb et al. 2005), while the remaining ndom=n−nfrontn_dom=n-n_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)N(0,σ^2) and clipped to [0,1]d[0,1]^d. The frontier is parameterized by d−1d-1 angles θj∼[0,π/2] _j [0,π/2], with coordinates: xi=(∏j=0i−1sinα(θj))⋅cosα(θi)if i<d−1,1if i=d−1, [rgb]0,0,0x_i= ( _j=0^i-1 ^α( _j) )· cases [rgb]0,0,0 ^α( _i)& [rgb]0,0,0if i<d-1,\\ [rgb]0,0,01& [rgb]0,0,0if i=d-1, cases where the shape exponent α controls the front geometry. We consider four geometries: concave (α=1.0α=1.0, spherical front with ∑ixi2=1 _ix_i^2=1, following DTLZ2 (Deb et al. 2005)); convex (α=0.5α=0.5, outward-bulging front with ∑ixi4=1 _ix_i^4=1); linear (α=2.0α=2.0, simplex-like front); and clusters (α=1.0α=1.0, spherical front with two disjoint angular regions, θ1∈[0,π/5] _1∈[0,π/5] for cluster 1 and θ1∈[3π/10,π/2] _1∈[3π/10,π/2] for cluster 2, with remaining angles free in [0,π/2][0,π/2]). For the linear geometry, the raw simplex coordinates collapse toward zero as d grows, making the dominated hypervolume uninformative. We therefore rescale the frontier points by a factor s=min(0.45d, 2.5)s= (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-k semi-bandit setting, plus a non-learning baseline: 1) Pareto-layer UCB methods (ParetoUCB, ParetoUCB-Div, ParetoUCB-Crowd (Drugan and Nowe 2013; Deb et al. 2002)); 2) Pareto-layer Thompson Sampling methods (ParetoTS, ParetoTS+ (Yahyaa and Manderick 2015)); 3) Chebyshev scalarization methods (ChebyshevUCB, ChebyshevUCB+ (Mandow et al. 2023)); 4) linear and hypervolume scalarization methods (ScalarUCB (Auer et al. 2002), ScalarUCB-RandW (Paria et al. 2020), HVScalarUCB (Zhang and Golovin 2020), HVScalarUCB+ (Zhang 2024)); 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 least min_pulls times) to avoid degenerate early behavior. Implementation details, including UCB bonuses, posterior parameterizations, and tie-breaking rules, are as follows: 1. ParetoUCB family • ParetoUCB (Drugan and Nowe 2013) computes UCB vectors Ui=μ^i+βiU_i= μ_i+ _i1 and selects k arms by iterating Pareto layers on U, using a ∑jUij _jU_ij tie-break within each layer. The faithful variant (ParetoUCB) uses the original confidence term βi=2log(t⋅(d⋅|ℱ^|)1/4)/Ni _i= 2 (t·(d·| F|)^1/4)/N_i where |ℱ^|| F| is the empirical Pareto front size, with uniform random selection within each layer. • ParetoUCB-Div (Drugan and Nowe 2013) extends ParetoUCB by replacing the ∑UΣ U tie-break with a farthest-point (maximin ℓ∞ _∞) diversity criterion: each slot greedily picks the candidate maximally distant from already-selected arms in UCB space. • ParetoUCB-Crowd (Drugan and Nowe 2013; Deb et al. 2002) replaces the tie-break with a crowding distance (Deb et al. 2002): within each Pareto layer, arms are ranked by their normalized inter-neighbor gap across objectives, favoring spread along the frontier. 2. ParetoTS family • ParetoTS (Yahyaa and Manderick 2015) maintains a Gaussian posterior per arm and coordinate. At each round it samples θi∼(μ^i,σi2) _i ( μ_i, _i^2I) with posterior standard deviation σi=σobs/Ni _i= _obs/ N_i (conjugate Gaussian), builds Pareto layers on the sampled vectors, and selects k arms by uniform random sampling within each layer. The only change from the original is the top-k extension. • ParetoTS+ (Yahyaa and Manderick 2015) uses a heuristic posterior σi2=(σprior2+σobs2)/Ni _i^2=( _prior^2+ _obs^2)/N_i that decays more slowly, combined with a ∑jθij _j _ij tie-break to encourage diversity within each Pareto layer. 3. ChebyshevUCB family • ChebyshevUCB (Mandow et al. 2023) follows Algorithm C2 of (Mandow et al. 2023): a set of S scalarization functions with weights spread uniformly on the simplex is precomputed, a function fjf^j is drawn uniformly at each round, and arms are scored by minℓwℓj(Uiℓ−zℓ) _ \w^j_ (U_i -z_ )\ where z is an estimated nadir point and Ui=μ^i+βiU_i= μ_i+ _i1 is the UCB vector. • ChebyshevUCB+ (Mandow et al. 2023) fixes w=/dw=1/d uniformly instead of drawing fjf^j randomly, and uses the standard UCB bonus βi=ηlog(ndT2)/(2Ni) _i= η (ndT^2)/(2N_i). 4. ScalarUCB family • ScalarUCB (Auer et al. 2002) reduces the vector reward to a scalar via a fixed uniform linear scalarization w=/dw=1/d, maintains a scalar mean estimate per arm, and selects the top-k arms by UCB index μ^i+βi μ_i+ _i where βi=ηlog(nT2)/(2Ni) _i= η (nT^2)/(2N_i). • ScalarUCB-RandW (Paria et al. 2020) draws a fresh weight vector w∼Dirichlet()w (1) at each round, computes UCB vectors Ui=μ^i+βiU_i= μ_i+ _i1 coordinate-wise, and selects the top-k arms by score w⊤Uiw U_i. • HVScalarUCB (Zhang and Golovin 2020) draws λ∼S+d−1λ S^d-1_+ (positive unit sphere) at each round and scores arms by the hypervolume scalarization sλ(Ui)=(minℓmax(0,Uiℓ/λℓ))ds_λ(U_i)= ( _ (0,U_i / _ ) )^d (Lemma 5 of (Zhang and Golovin 2020)), selecting the top-k arms by score. • HVScalarUCB+ (Zhang 2024) draws k independent directions λ(1),…,λ(k)∼S+d−1λ^(1),…,λ^(k) S^d-1_+ per round and assigns one arm per direction: a(j)=argmaxi∉a(1),…,a(j−1)minℓ(Uiℓ−rℓ)/λℓ(j)a^(j)= _i∉\a^(1),…,a^(j-1)\ _ (U_i -r_ )/λ^(j)_ , where r is the reference point. This top-k adaptation is our own extension of the directional intuition of Lemma 5 in (Zhang 2024). 5. RandomK selects a slate of k arms uniformly at random each round, without any learning. Results Overall, THV-UCB achieves the lowest cumulative α-regret and the highest hypervolume in all four front geometries (linear, convex, concave, and clusters) and all dimensions from d=2d=2 to d=5d=5, with a margin that generally increases with d (See Tables 1, Figures 1, 2, 3, 4, and all the results (for d>2d>2) in the appendix and in our GitHub repository https://github.com/ngutowski/topk-pareto-bandits). Figures 1 to 4, report hypervolume HV(St)HV(S_t) trajectories (moving average, w=50w=50) with 95%95\% CIs across 1010 seeds, comparing THV-UCB (ours) against the best representative per baseline family, for each synthetic Pareto front geometry. Clusters Concave Convex Linear Algorithm Fid. HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret THV-UCB (ours) — 0.6556± 0.001 5.5<0.001<0.001 0.6638± 0.002 6.2<0.001<0.001 0.8536± 0.002 7.2<0.001<0.001 0.2879± 0.002 2.7<0.001<0.001 ParetoUCB (Drugan and Nowe 2013) ∙ 0.4438± 0.082 130.0± 108.3 0.4711± 0.072 105.0± 98.5 0.7169± 0.059 38.8± 43.2 0.1515± 0.040 107.1± 64.7 ParetoUCB+ (Drugan and Nowe 2013) ∘ 0.6330± 0.005 28.4± 5.6 0.5770± 0.023 31.3± 5.2 0.8170± 0.015 7.2<0.001<0.001 0.1620± 0.037 69.5± 46.2 ParetoUCB-Div (Drugan and Nowe 2013) ∘ 0.6502± 0.007 9.4± 2.1 0.6064± 0.006 6.6± 0.7 0.8281± 0.006 7.2<0.001<0.001 0.2115± 0.009 5.8± 4.8 ParetoUCB-Crowd (Drugan and Nowe 2013; Deb et al. 2002) ∘ 0.6384± 0.011 19.8± 7.8 0.5712± 0.015 18.0± 7.7 0.8290± 0.006 7.3<0.001<0.001 0.1303± 0.008 99.5± 19.1 ParetoTS (Yahyaa and Manderick 2015) ∙ 0.4871± 0.069 51.8± 55.7 0.5180± 0.056 33.4± 38.0 0.7528± 0.044 9.4± 3.8 0.1901± 0.035 40.0± 40.0 ParetoTS+ (Yahyaa and Manderick 2015) ∘ 0.6293± 0.015 12.5± 8.9 0.5788± 0.025 12.5± 8.9 0.7836± 0.025 8.4± 2.0 0.1623± 0.040 85.6± 61.1 ChebyshevUCB (Mandow et al. 2023) ∙ 0.4763± 0.066 72.0± 62.7 0.5017± 0.063 48.1± 47.7 0.7185± 0.033 23.7± 16.4 0.2016± 0.027 38.4± 34.5 ChebyshevUCB+ (Mandow et al. 2023) ∘ 0.6286± 0.002 10.3± 2.0 0.5514± 0.012 24.2± 3.2 0.7527± 0.014 7.3<0.001<0.001 0.2266± 0.005 10.0± 5.1 HVScalarUCB (Zhang and Golovin 2020) ∙ 0.4898± 0.083 86.7± 88.6 0.5086± 0.082 80.1± 82.3 0.7216± 0.039 13.8± 5.5 0.2105± 0.035 46.8± 49.3 HVScalarUCB+ (Zhang 2024) ∙ 0.5728± 0.050 15.6± 16.7 0.5863± 0.043 14.0± 13.1 0.7647± 0.047 8.9± 3.1 0.2463± 0.017 6.7± 6.6 ScalarUCB (Auer et al. 2002) ∘ 0.6340± 0.005 10.9± 6.1 0.5733± 0.025 27.2± 20.7 0.7731± 0.022 14.0± 8.1 0.1584± 0.040 95.0± 62.1 ScalarUCB-RandW (Paria et al. 2020) ∘ 0.4536± 0.069 66.4± 42.5 0.4734± 0.056 50.1± 22.9 0.7347± 0.036 7.3<0.001<0.001 0.0733± 0.040 180.1± 62.8 RandomK — 0.2225± 0.105 424.0± 181.6 0.2361± 0.111 405.7± 190.6 0.3878± 0.165 411.2± 256.6 0.0922± 0.037 185.9± 69.3 Table 1: Summary over four synthetic fronts (d=2d=2, n=36n=36, k=3k=3, σ=0.05σ=0.05, T=2000T=2000, 10 seeds). Fid. indicates fidelity to the cited work: ∙ = faithful top-k adaptation (core mechanism unchanged); ∘ = 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 α-regret ± 95% CI. The linear front is the most discriminative, with THV-UCB’s advantage over the closest baseline widening from +27% at d=2d=2 to +79% at d=5d=5: linear fronts require uniform simplex coverage, which single-direction scalarization methods increasingly fail to achieve at higher d, while THV-UCB’s greedy hypervolume gain naturally spreads the slate across the entire front (See Table 1 and Figure 1). 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 and Figure 2). 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 at d=3,4d=3,4, while ScalarUCB and ParetoTS+ are competitive on convex across dimensions (See Table 1, and Figures 3 and 4). Figure 3: HV trajectories, concave front. Figure 4: HV trajectories, convex front. Among baselines, no single method dominates across all settings. ChebyshevUCB+ (Mandow et al. 2023) is the strongest competitor at d=3d=3 and 44, particularly on concave and linear fronts. HVScalarUCB+ (Zhang 2024) becomes increasingly competitive on linear as d grows, reaching second place at d=4d=4 (0.05320.0532) and d=5d=5 (0.00530.0053). ParetoUCB+ (Drugan and Nowe 2013) and ScalarUCB (Auer et al. 2002) perform well on smooth fronts (convex, concave) at low d but degrade on linear and clusters. ParetoUCB-Div (Drugan and Nowe 2013) and ParetoUCB-Crowd (Deb et al. 2002; Drugan and Nowe 2013) add diversity heuristics that help on clusters at d=2d=2 but loose their advantage at higher d. ScalarUCB-RandW (Paria et al. 2020) 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/10 seeds, Cohen’s d from 1.91.9 to 44.544.5, See Table 6 in the appendix). Conclusion We introduced Top-k Pareto Bandits, where an agent repeatedly selects a size-k slate under semi-bandit feedback, evaluated by dominated hypervolume coverage of the Pareto boundary, and proposed THV-UCB, which greedily maximizes optimistic marginal hypervolume gain under safe coordinate-wise pruning. We established a gap-free O~(dnkT) O\! (d nkT ) bound valid on every instance and a gap-dependent O~(nk2.5/Δmin) O\! (nk^2.5/ _ ) bound that is polylogarithmic in T on well-separated instances; tightening these dependencies and establishing matching lower bounds remain open. Empirically, THV-UCB outperforms state-of-the-art baselines across all tested geometries and dimensions d∈2,…,5d∈\2,…,5\, with the margin widening as d increases, 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 Cited by: Table 3, Table 4, Table 5, item 2, 1st item, Baselines, Results, Results. S. Bubeck and N. Cesa-Bianchi (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends Mach. Learn. 5, p. 1–122. External Links: Link Cited by: Performance metric: (approximation) hypervolume regret.. R. Busa-Fekete, B. Szörényi, P. Weng, and S. Mannor (2017) Multi-objective bandits: optimizing the generalized Gini index. In Proceedings 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).. X. Cai, P. Zhang, L. Zhao, J. Bian, M. Sugiyama, and A. Llorens (2023) Distributional pareto-optimal multi-objective reinforcement learning. In Advances 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).. L. Cao, M. Shi, and N. B. Shroff (2025) Provably efficient multi-objective bandit algorithms under preference-centric customization. External Links: 2502.13457, Link Cited by: Introduction, Multi-Objective Multi-Armed Bandits (MOMAB).. J. Chen, Z. Zhang, Z. Cao, Y. Wu, Y. Ma, T. Ye, and J. Wang (2023) Neural multi-objective combinatorial optimization with diversity enhancement. In Advances 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).. 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 Science 11. External Links: Document Cited by: Multi-Objective Optimization (MOO).. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan (2002) A fast and elitist multiobjective genetic algorithm: nsga-i. IEEE Transactions on Evolutionary Computation 6 (2). External Links: Document Cited by: Table 3, Table 4, Table 5, item 2, 3rd item, Baselines, Results, Results. K. Deb, L. Thiele, M. Laumanns, and E. Zitzler (2005) Scalable test problems for evolutionary multiobjective optimization. In Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, p. 105–145. External Links: ISBN 978-1-84628-137-2, Document Cited by: Synthetic Environments, Synthetic Environments. M. M. Drugan and A. Nowe (2013) Designing multi-objective multi-armed bandits algorithms: a study. In The 2013 International Joint Conference on Neural Networks (IJCNN), Vol. . External Links: Document Cited by: Table 3, Table 3, Table 3, Table 3, Table 4, Table 4, Table 4, Table 4, Table 5, Table 5, Table 5, Table 5, item 2, Multi-Objective Multi-Armed Bandits (MOMAB)., 1st item, 2nd item, 3rd item, Baselines, Results, Results, Results, Results, Results. Ó. 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 Applications 295. External Links: ISSN 0957-4174, Document Cited by: Introduction, Introduction, Multi-Objective Optimization (MOO).. J. C. Fromer and C. W. Coley (2023) Computer-aided multi-objective optimization in small molecule discovery. Patterns 4 (2). External Links: Document, ISSN 2666-3899 Cited by: Introduction. 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 Review 59 (5). External Links: ISSN 1573-7462, Document Cited by: Multi-Objective Optimization (MOO).. 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 Cited by: Introduction, Introduction. 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 Engineering 33 (2). External Links: ISSN 1886-1784, Document Cited by: Multi-Objective Optimization (MOO).. A. Hüyük and C. Tekin (2021) Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning 110 (6). External Links: ISSN 1573-0565, Document Cited by: Introduction, Multi-Objective Multi-Armed Bandits (MOMAB).. D. Jiju and S. Manemaran (2025) AI-driven hyperheuristics for dynamic multiobjective optimization: a comprehensive review.. IAENG International Journal of Applied Mathematics 55 (12). Cited by: Multi-Objective Optimization (MOO).. J. Katz-Samuels and C. Scott (2018) Feasible arm identification. In Proceedings 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).. C. KONE, E. Kaufmann, and L. Richert (2023) Adaptive algorithms for relaxed pareto set identification. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Cited by: Introduction, Introduction, Multi-Objective Multi-Armed Bandits (MOMAB)., Dominated Hypervolume (HV) in MOMAB.. C. Kone, E. Kaufmann, and L. Richert (2025a) Bandit pareto set identification in a multi-output linear model. In Proceedings 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, Introduction. C. Kone, E. Kaufmann, and L. Richert (2025b) Constrained pareto set identification with bandit feedback. In Proceedings 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, p. 31342–31378. Cited by: Introduction, Multi-Objective Multi-Armed Bandits (MOMAB)., Dominated Hypervolume (HV) in MOMAB.. 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 Applications 296. External Links: ISSN 0957-4174, Document Cited by: Introduction, Multi-Objective Optimization (MOO).. 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 Applications 246. External Links: ISSN 0957-4174, Document Cited by: Introduction, Introduction, Multi-Objective Multi-Armed Bandits (MOMAB).. E. Liu, Y. Wu, X. Huang, C. Gao, R. Wang, K. Xue, and C. Qian (2025a) Pareto set learning for multi-objective reinforcement learning. In Proceedings 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 Cited by: Introduction, Multi-Objective Multi-Armed Bandits (MOMAB).. 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. In International Conference on Learning Representations, Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (Eds.), Vol. 2025. Cited by: Introduction, Multi-Objective Multi-Armed Bandits (MOMAB).. 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, Table 3, Table 4, Table 4, Table 5, Table 5, item 2, Introduction, Multi-Objective Multi-Armed Bandits (MOMAB)., 1st item, 2nd item, Baselines, Results, Results, Results. B. Paria, K. Kandasamy, and B. Póczos (2020) A flexible framework for multi-objective bayesian optimization using random scalarizations. In Proceedings 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, Table 4, Table 5, item 2, 2nd item, Baselines, Results, Results. S. Q. Yahyaa, M. M. Drugan, and B. Manderick (2014) Knowledge gradient for multi-objective multi-armed bandit algorithms. In Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1, ICAART 2014. External Links: ISBN 9789897580154, Document Cited by: Multi-Objective Multi-Armed Bandits (MOMAB).. D. M. Roijers, P. Vamplew, S. Whiteson, and R. Dazeley (2013) A survey of multi-objective sequential decision-making. Journal of Artificial Intelligence Research 48, p. 67–113. Cited by: Multi-Objective Multi-Armed Bandits (MOMAB).. D. M. Roijers, L. M. Zintgraf, and A. Nowé (2017) Interactive thompson sampling for multi-objective multi-armed bandits. In Algorithmic Decision Theory, J. Rothe (Ed.), External Links: ISBN 978-3-319-67504-6 Cited by: Multi-Objective Multi-Armed Bandits (MOMAB).. 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. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’25. External Links: ISBN 9798400714269 Cited by: Introduction, Multi-Objective Optimization (MOO).. M. Shahverdikondori, M. R. Badri, and N. Kiyavash (2025) Best group identification in multi-objective bandits. External Links: 2505.17869, Link Cited by: Introduction, Multi-Objective Multi-Armed Bandits (MOMAB).. 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. ArXiv abs/2510.19325. External Links: Link Cited by: Introduction, Multi-Objective Optimization (MOO).. 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 Cited by: Introduction, Multi-Objective Optimization (MOO).. M. Xu and D. Klabjan (2023) Pareto regret analyses in multi-objective multi-armed bandit. In Proceedings 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, Multi-Objective Multi-Armed Bandits (MOMAB).. 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 Intelligence 39 (20). External Links: Document Cited by: Introduction, Multi-Objective Multi-Armed Bandits (MOMAB).. S. Yahyaa and B. Manderick (2015) Thompson sampling for multi-objective multi-armed bandits problem. In European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, p. 47–52. Cited by: Table 3, Table 3, Table 4, Table 4, Table 5, Table 5, item 2, Multi-Objective Multi-Armed Bandits (MOMAB)., 1st item, 2nd item, Baselines, Results, Results. 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 Retrieval 14. External Links: Link Cited by: Introduction, Multi-Objective Optimization (MOO).. Q. (. Zhang (2024) Optimal scalarizations for sublinear hypervolume regret. In Advances 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 Cited by: Table 3, Table 4, Table 5, item 2, Introduction, Multi-Objective Optimization (MOO)., Multi-Objective Multi-Armed Bandits (MOMAB)., Dominated Hypervolume (HV) in MOMAB., 4th item, Baselines, Results, Results. R. Zhang and D. Golovin (2020) Random hypervolume scalarizations for provable multi-objective black box optimization. In Proceedings of the 37th International Conference on Machine Learning, H. D. I and A. Singh (Eds.), Proceedings of Machine Learning Research, Vol. 119, p. 11096–11105. Cited by: Table 3, Table 4, Table 5, item 2, item 3, Multi-Objective Multi-Armed Bandits (MOMAB)., Dominated Hypervolume (HV) in MOMAB., 3rd item, Baselines, Results. X. Zhang, G. Li, X. Lin, Y. Zhang, Y. Chen, and Q. Zhang (2024) Gliding over the pareto front with uniform designs. In Advances 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 Cited by: item 3, Multi-Objective Optimization (MOO)., Dominated Hypervolume (HV) in MOMAB.. X. Zhang, X. Lin, B. Xue, Y. Chen, and Q. Zhang (2023) Hypervolume maximization: a geometric view of pareto set learning. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Cited by: Introduction, Multi-Objective Optimization (MOO)., Dominated Hypervolume (HV) in MOMAB.. 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 Computation 7 (2). External Links: Document Cited by: Reference point and dominated hypervolume., Experiments. This appendix provides the full proofs of Theorems 1–3 (Upper-bound Proofs, below), additional experimental results for d∈3,4,5d∈\3,4,5\ (Experimental details), and a summary of notation (Notation summary). Appendix A Upper-bound Proofs This appendix establishes the sublinear α-regret guarantee for THV-UCB announced in the Regret Analysis section. We prove two complementary statements: • a gap-free bound (Theorem 1), of order O~(nkT) O( nkT), valid on every instance regardless of how close the arms are to each other; • a gap-dependent bound (Theorem 2), of order O~(nk2.5/Δmin) O(nk^2.5/ _ ), which becomes polylogarithmic in T as soon as the instance is well separated. Both proofs share the same first steps (Preliminaries through Lipschitz control of the optimism error), which reduce R¯T R_T to a sum of confidence radii, in (5). 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) _t^UCB(· 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 about THV-UCB in the discussion at the end of this appendix. Preliminaries Lemma 1 (Monotonicity and submodularity of hypervolume). For any fixed reference point r dominated by all achievable means, the set function S↦HV(S)S (S) is monotone (non-decreasing) and submodular. Proof. Recall HV(S)=λd(⋃i∈S∏j=1d[rj,μi,j])HV(S)= _d ( _i∈ S _j=1^d[r_j, _i,j] ). Monotonicity. If S⊆TS T, the union of boxes only grows, so HV(S)≤HV(T)HV(S) (T). Submodularity. Let A⊆BA B and i∉Bi∉ B. Write VA=⋃j∈A∏ℓ[rℓ,μj,ℓ]V_A= _j∈ A _ [r_ , _j, ] and Vi=∏ℓ[rℓ,μi,ℓ]V_i= _ [r_ , _i, ]. Then HV(A∪i)−HV(A)=λd(Vi∖VA),HV(B∪i)−HV(B)=λd(Vi∖VB).HV(A∪\i\)-HV(A)= _d(V_i V_A), (B∪\i\)-HV(B)= _d(V_i V_B). Since VA⊆VBV_A V_B, Vi∖VB⊆Vi∖VAV_i V_B V_i V_A, hence submodularity. ∎ Remark. The same argument, applied verbatim with ui,j(t)u_i,j(t) in place of μi,j _i,j (the proof never uses anything about μi,j _i,j beyond it being a real number), shows that for every fixed t, S↦HVtUCB(S)S _t^UCB(S) is also monotone and submodular. Lemma 2 (Coordinate-wise concentration). Assume each coordinate is η-sub-Gaussian. Then with probability at least 1−δ1-δ, for all i,j,ti,j,t, |μ^i,j(t)−μi,j|≤βi(t)=2ηlog(ndt2/δ)max1,Ni(t−1). | μ_i,j(t)- _i,j |≤ _i(t)= 2η (ndt^2/δ) \1,N_i(t-1)\. Proof. Fix i,ji,j and a pull count s=Ni(t−1)≥1s=N_i(t-1)≥ 1. By the sub-Gaussian Hoeffding bound, ℙ(|μ^i,j(t)−μi,j|>2ηlog(x)/s)≤2/xP (| μ_i,j(t)- _i,j|> 2η (x)/s )≤ 2/x. Taking x=ndt2/δx=ndt^2/δ and a union bound over i∈[n]i∈[n], j∈[d]j∈[d], and t∈[T]t∈[T] (using ∑t≥1t−2≤2 _t≥ 1t^-2≤ 2) gives total failure probability O(δ)O(δ); absorbing the constant into δ yields the stated bound. ∎ We write ℰE for the event on which Lemma 2 holds, so ℙ(ℰ)≥1−δP(E)≥ 1-δ. After the initialization phase of Algorithm 1 (which lasts at most t0=⌈nm0/k⌉t_0= nm_0/k rounds), every arm has Ni(t−1)≥m0≥1N_i(t-1)≥ m_0≥ 1, so the max1,⋅ \1,·\ in βi(t) _i(t) is never active for t>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). Let f:2[n]→ℝf:2^[n] be monotone and submodular, and let G=g1,…,gkG=\g_1,…,g_k\ be built by greedy maximization of marginal f-gain under the cardinality constraint k (i.e. gℓ∈argmaxi∉Gℓ−1f(Gℓ−1∪i)−f(Gℓ−1)g_ ∈ _i∉ G_ -1f(G_ -1∪\i\)-f(G_ -1), Gℓ=Gℓ−1∪gℓG_ =G_ -1∪\g_ \, G0=∅G_0= , G=GkG=G_k). Then f(G)≥(1−1e)max|S|=kf(S)=αmax|S|=kf(S).f(G)\;≥\; (1- 1e ) _|S|=kf(S)\;=\;α _|S|=kf(S). We will apply Fact 1 to two different functions: • f=HVtUCBf=HV_t^UCB (monotone submodular by the previous remark, with G=StG=S_t the set actually built by THV-UCB at round t — this yields Corollary 1 below, used in the reduction step; • f=HVf=HV directly on the true means — a purely deterministic statement requiring no concentration event — with G=G⋆G=G , a benchmark sequence introduced in Section A gap-dependent bound and distinct from the regret’s true optimum S⋆S . Corollary 1 (Greedy approximation under optimism). For every round t, HVtUCB(St)≥αHVtUCB(Stopt)HV_t^UCB(S_t)≥α\,HV_t^UCB(S^opt_t), where Stopt∈argmax|S|=kHVtUCB(S)S^opt_t∈ _|S|=kHV_t^UCB(S). Optimism and reduction to optimism error Recall ui,j(t)=μ^i,j(t−1)+βi(t)u_i,j(t)= μ_i,j(t-1)+ _i(t) and HVtUCB(S)=λd(⋃i∈S[r1,ui,1(t)]×⋯×[rd,ui,d(t)]).HV_t^UCB(S)= _d ( _i∈ S[r_1,u_i,1(t)]×·s×[r_d,u_i,d(t)] ). On ℰE, μi,j≤ui,j(t) _i,j≤ u_i,j(t) for all i,ji,j, so by monotonicity HV(S)≤HVtUCB(S)HV(S) _t^UCB(S) for every S. Let S⋆∈argmax|S|=kHV(S)S ∈ _|S|=kHV(S), with V⋆=HV(S⋆)V =HV(S ) — this is the benchmark appearing in the regret definition (2), and the only role S⋆S plays in this appendix. Since StoptS^opt_t maximizes HVtUCBHV_t^UCB over all size-k sets, it dominates S⋆S under this score, so by Corollary 1, HVtUCB(St)≥αHVtUCB(Stopt)≥αHVtUCB(S⋆).HV_t^UCB(S_t)\;≥\;α\,HV_t^UCB(S^opt_t)\;≥\;α\,HV_t^UCB(S ). Therefore, on ℰE, r¯t=αV⋆−HV(St)≤αHVtUCB(S⋆)−HV(St)≤HVtUCB(St)−HV(St). r_t=α\,V -HV(S_t)\;≤\;α\,HV_t^UCB(S )-HV(S_t)\;≤\;HV_t^UCB(S_t)-HV(S_t). (3) Summing over t∈[T]t∈[T], R¯T≤∑t=1T(HVtUCB(St)−HV(St))on ℰ. R_T\;≤\; _t=1^T (HV_t^UCB(S_t)-HV(S_t) ) E. (4) Lipschitz control of the optimism error Lemma 3 (Lipschitz bound for hypervolume under coordinate-wise shifts). There is a constant CdC_d (one may take Cd≤dC_d≤ d when rewards lie in [0,1]d[0,1]^d and =r=0) such that, on ℰE, for every round t and every finite set S⊆[n]S [n] (not necessarily StS_t), HVtUCB(S)−HV(S)≤Cd∑i∈Sβi(t).HV_t^UCB(S)-HV(S)\;≤\;C_d _i∈ S _i(t). Proof. Write S=i1,…,imS=\i_1,…,i_m\. Define the intermediate hypervolume AℓA_ where arms i1,…,iℓi_1,…,i_ use optimistic vectors ip(t)u_i_p(t) and arms iℓ+1,…,imi_ +1,…,i_m use true means ip μ_i_p, so HVtUCB(S)−HV(S)=∑ℓ=1m(Aℓ−Aℓ−1)HV_t^UCB(S)-HV(S)= _ =1^m(A_ -A_ -1). Each term changes only arm iℓi_ from iℓ μ_i_ to iℓ(t)=iℓ+iℓu_i_ (t)= μ_i_ + δ_i_ with 0≤δiℓ,j≤βiℓ(t)0≤ _i_ ,j≤ _i_ (t). The added hypervolume is contained in a union of d axis-aligned slabs of width at most βiℓ(t) _i_ (t) in one coordinate and at most 11 in the others, so Aℓ−Aℓ−1≤dβiℓ(t)A_ -A_ -1≤ d\, _i_ (t). Summing over ℓ gives the claim with Cd=dC_d=d. Crucially, this argument never uses |S|=k|S|=k nor any property of how S was selected, hence it holds for an arbitrary finite S. ∎ Combining (4) with Lemma 3 applied to S=StS=S_t, R¯T≤Cd∑t=1T∑i∈Stβi(t)on ℰ. R_T\;≤\;C_d _t=1^T _i∈ S_t _i(t) E. (5) The rest of the proof bounds the right-hand side of (5) in two ways. A gap-free bound Let Ni(T)=∑t=1Ti∈StN_i(T)= _t=1^T1\i∈ S_t\. Reordering (5) by arm, ∑t=1T∑i∈Stβi(t)=∑i=1n∑s=1Ni(T)2ηlog(ndT2/δ)s≤ 22ηlog(ndT2/δ)∑i=1nNi(T), _t=1^T _i∈ S_t _i(t)= _i=1^n _s=1^N_i(T) 2η (ndT^2/δ)s\;≤\;2 2η (ndT^2/δ) _i=1^n N_i(T), using ∑s=1ms−1/2≤2m _s=1^ms^-1/2≤ 2 m. Since exactly k arms are pulled per round, ∑iNi(T)=kT _iN_i(T)=kT, and Cauchy–Schwarz gives ∑iNi(T)≤nkT _i N_i(T)≤ nkT. Hence, on ℰE, R¯T≤O(CdnkTlogT) R_T≤ O (C_d nkT T ). Theorem 1 (Gap-free bound (detailed version)). On ℰE, R¯T=O(CdnkTlogT) R_T=O (C_d nkT T ). Remark. This argument never used that StS_t is built by comparing marginal gains ΔtUCB(i∣S) _t^UCB(i S) across candidates: it only used |St|=k|S_t|=k and the parametric decay βi(t)=Θ(1/Ni(t−1)) _i(t)= (1/ N_i(t-1)). It is "gap-free" precisely because it is blind to how close arms are, hence to the selection mechanism itself. A gap-dependent bound The key idea: the algorithm’s own greedy construction at round t progressively learns a stage-by-stage benchmark sequence. At stage ℓ , it must identify the best arm conditionally on the previously identified greedy prefix. The greedy optimal set Let G⋆=i1⋆,…,ik⋆G =\i_1 ,…,i_k \ be a greedy construction of an optimal size-k set for the true hypervolume: iℓ⋆∈argmaxi∉Gℓ−1⋆Δ(i∣Gℓ−1⋆),Gℓ⋆=Gℓ−1⋆∪iℓ⋆,G0⋆=∅,i_ ∈ _i∉ G _ -1 (i G _ -1), G _ =G _ -1∪\i_ \, G _0= , with Δ(i∣S)=HV(S∪i)−HV(S) (i S)=HV(S∪\i\)-HV(S). Assume the greedy maximizer is unique at every stage of G⋆G ’s construction, and define the stage-ℓ gaps relative to this benchmark: Δℓ(i)=Δ(iℓ⋆∣Gℓ−1⋆)−Δ(i∣Gℓ−1⋆)>0,i≠iℓ⋆,Δmin=minℓ∈[k]mini≠iℓ⋆Δℓ(i). _ (i)= (i_ G _ -1)- (i G _ -1)>0, i≠ i_ , _ = _ ∈[k] _i≠ i_ _ (i). Remark. By submodularity (Lemma 1), the sequence of greedy values vℓ:=Δ(iℓ⋆∣Gℓ−1⋆)v_ := (i_ G _ -1) is non-increasing: for i∉Gℓ⋆i∉ G _ , Gℓ−1⋆⊆Gℓ⋆G _ -1 G _ gives Δ(i∣Gℓ⋆)≤Δ(i∣Gℓ−1⋆) (i G _ )≤ (i G _ -1), so vℓ+1≤vℓv_ +1≤ v_ . This only constrains the best marginal gain at each stage, not the runner-up: it does not imply that the gap sequence γℓ:=mini≠iℓ⋆Δℓ(i) _ := _i≠ i_ _ (i) is monotonic in ℓ . We therefore use the safe, uniform bound Δmin _ rather than a stage-wise one. Deviation of optimistic marginal gains For S⊆[n]S [n] and i∉Si∉ S, write ΔtUCB(i∣S)=HVtUCB(S∪i)−HVtUCB(S) _t^UCB(i S)=HV_t^UCB(S∪\i\)-HV_t^UCB(S). Lemma 4 (Deviation of optimistic marginal gains). On ℰE, for every S⊆[n]S [n] and i∉Si∉ S, ΔtUCB(i∣S)≤Δ(i∣S)+Cd∑j∈S∪iβj(t),ΔtUCB(i∣S)≥Δ(i∣S)−Cd∑j∈Sβj(t). _t^UCB(i S)≤ (i S)+C_d _j∈ S∪\i\ _j(t), _t^UCB(i S)≥ (i S)-C_d _j∈ S _j(t). Proof. By Lemma 3 applied to S∪iS∪\i\ and to S, HVtUCB(S∪i)≤HV(S∪i)+Cd∑j∈S∪iβj(t)HV_t^UCB(S∪\i\) (S∪\i\)+C_d _j∈ S∪\i\ _j(t), while optimism gives HVtUCB(S)≥HV(S)HV_t^UCB(S) (S); subtracting gives the upper bound. Symmetrically, HVtUCB(S∪i)≥HV(S∪i)HV_t^UCB(S∪\i\) (S∪\i\) and HVtUCB(S)≤HV(S)+Cd∑j∈Sβj(t)HV_t^UCB(S) (S)+C_d _j∈ S _j(t) give the lower bound. ∎ Per-round deviation stage Write the algorithm’s own greedy construction at round t as a chain S^t,0=∅⊂S^t,1⊂⋯⊂S^t,k=St S_t,0= ⊂ S_t,1⊂·s⊂ S_t,k=S_t, where S^t,ℓ=S^t,ℓ−1∪ı^t,ℓ S_t, = S_t, -1∪\ _t, \ and ı^t,ℓ∈argmaxi∈At∖S^t,ℓ−1ΔtUCB(i∣S^t,ℓ−1) _t, ∈ _i∈ A_t S_t, -1 _t^UCB(i S_t, -1).333We assume G⋆⊆AtG 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 benchmark G⋆G : ℓ†(t)=minℓ∈[k]:S^t,ℓ≠Gℓ⋆, (t)= \ ∈[k]: S_t, ≠ G _ \, with ℓ†(t)=+∞ (t)=+∞ if S^t,ℓ=Gℓ⋆ S_t, =G _ for every ℓ∈[k] ∈[k] (i.e. St=G⋆S_t=G exactly). This partitions [T][T] into Match=t:ℓ†(t)=∞,Devℓ=t:ℓ†(t)=ℓ(ℓ∈[k]),[T]=Match⊔⨆ℓ=1kDevℓ.Match=\t: (t)=∞\, _ =\t: (t)= \\ ( ∈[k]), [T]=Match _ =1^kDev_ . By construction, t∈Devℓt _ means S^t,ℓ−1=Gℓ−1⋆ S_t, -1=G _ -1 — this is built into the partition, no induction over earlier rounds is needed. Since R¯T=∑t=1Tr¯t R_T= _t=1^T r_t exactly by (2), this partition refines the same per-round sum bounded pointwise in (3): rather than controlling every term r¯t r_t uniformly via Lemma 3 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, R_T\;=\; _t r_t\;+\; _ =1^k _t _ 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). If t∈Matcht , then St=G⋆S_t=G . By Fact 1 with f=HVf=HV, G=G⋆G=G , r¯t=αV⋆−HV(St)=αV⋆−HV(G⋆)≤αV⋆−αV⋆=0. r_t=α\,V -HV(S_t)=α\,V -HV(G )\;≤\;α\,V -α\,V =0. Witness-counting bound on deviation rounds Fix ℓ and t∈Devℓt _ , and write i:=ı^t,ℓ≠iℓ⋆i:= _t, ≠ i_ . Since i was chosen over iℓ⋆i_ at stage ℓ of round t, ΔtUCB(i∣Gℓ−1⋆)≥ΔtUCB(iℓ⋆∣Gℓ−1⋆) _t^UCB(i G _ -1)≥ _t^UCB(i_ G _ -1). Applying Lemma 4 at S=Gℓ−1⋆S=G _ -1, Δ(i∣Gℓ−1⋆)+Cd∑j∈Gℓ−1⋆∪iβj(t)≥Δ(iℓ⋆∣Gℓ−1⋆)−Cd∑j∈Gℓ−1⋆βj(t), (i G _ -1)+C_d _j∈ G _ -1∪\i\ _j(t)\;≥\; (i_ G _ -1)-C_d _j∈ G _ -1 _j(t), so, using |Gℓ−1⋆|=ℓ−1|G _ -1|= -1, Δℓ(i)≤Cd(2∑j∈Gℓ−1⋆βj(t)+βi(t))≤Cd(2ℓ−1)maxj∈Gℓ−1⋆∪iβj(t). _ (i)\;≤\;C_d (2 _j∈ G _ -1 _j(t)+ _i(t) )\;≤\;C_d(2 -1) _j∈ G _ -1∪\i\ _j(t). Hence there exists a witness w(t)∈Gℓ−1⋆∪iw(t)∈ G _ -1∪\i\ (at most ℓ candidates) with βw(t)(t)≥Δℓ(i)Cd(2ℓ−1)≥ΔminCd(2ℓ−1), _w(t)(t)\;≥\; _ (i)C_d(2 -1)\;≥\; _ C_d(2 -1), soNw(t)(t−1)≤mℓ:=2ηCd2(2ℓ−1)2log(ndT2/δ)Δmin2=O(ℓ2logTΔmin2).so N_w(t)(t-1)\;≤\;m_ := 2η C_d^2(2 -1)^2 (ndT^2/δ) _ ^2=O\! ( ^2 T _ ^2 ). Since Gℓ−1⋆∪i=S^t,ℓ⊆StG _ -1∪\i\= S_t, S_t, the witness w(t)w(t) is pulled at round t. Group DevℓDev_ by witness identity: for fixed w∈[n]w∈[n], every t∈Devℓt _ with w(t)=w(t)=w increments NwN_w by exactly 11 while Nw(t−1)≤mℓN_w(t-1)≤ m_ ; there are at most mℓ+1m_ +1 such rounds. Summing over w∈[n]w∈[n], |Devℓ|≤n(mℓ+1)=O(nℓ2logTΔmin2).|Dev_ |\;≤\;n\,(m_ +1)\;=\;O\! ( n ^2 T _ ^2 ). (7) Bounding total regret on deviation rounds We now bound the second term of (6), ∑ℓ=1k∑t∈Devℓr¯t _ =1^k _t _ r_t. A naive approach would bound r¯t≤1 r_t≤ 1 on every round of DevℓDev_ and multiply by the count |Devℓ|=O(nℓ2logT/Δmin2)|Dev_ |=O(n ^2 T/ _ ^2) from (7), giving a regret scaling as 1/Δmin21/ _ ^2. We avoid this by bounding the total regret over DevℓDev_ directly, via the same Cauchy–Schwarz idea as in the gap-free bound Section above — applied locally to DevℓDev_ rather than to the full horizon. Since that argument scales as the square root of the number of rounds involved, it converts the 1/Δmin21/ _ ^2 scale of the count into a 1/Δmin1/ _ contribution to regret. On ℰE, the pointwise bound (3) together with Lemma 3 gives, for every round t, r¯t≤HVtUCB(St)−HV(St)≤Cd∑i∈Stβi(t). r_t\;≤\;HV_t^UCB(S_t)-HV(S_t)\;≤\;C_d _i∈ S_t _i(t). Fix ℓ∈[k] ∈[k], and for i∈[n]i∈[n] let Di=t∈Devℓ:i∈StD_i=\t _ :i∈ S_t\ be the (possibly empty) set of rounds, among those at which the trajectory first departs from G⋆G at stage ℓ , where arm i happens to be pulled. The pull count Ni(t−1)N_i(t-1) increases by exactly 11 at each pull of i, so as t ranges over DiD_i (a set of pulls of i), the values Ni(t−1)N_i(t-1) are pairwise distinct; hence their j-th smallest value is at least j−1j-1. Since βi(t)∝Ni(t−1)−1/2 _i(t) N_i(t-1)^-1/2 is decreasing, this bounds the sum by the worst case where DiD_i consists of arm i’s earliest |Di||D_i| pulls: ∑t∈Diβi(t)≤∑s=1|Di|2ηlog(ndT2/δ)s≤ 22ηlog(ndT2/δ)|Di|=O(|Di|logT), _t∈ D_i _i(t)\;≤\; _s=1^|D_i| 2η (ndT^2/δ)s\;≤\;2 2η (ndT^2/δ)\, |D_i|\;=\;O ( |D_i| T ), using ∑s=1ms−1/2≤2m _s=1^ms^-1/2≤ 2 m and log(ndT2/δ)=O(logT) (ndT^2/δ)=O( T) — the same argument as in the gap-free bound Section, restricted to Di⊆D_i \pulls of ii\ instead of all of i’s pulls over [T][T]. Hence ∑t∈Devℓ∑i∈Stβi(t)=∑i=1n∑t∈Diβi(t)=O(logT∑i=1n|Di|). _t _ _i∈ S_t _i(t)= _i=1^n _t∈ D_i _i(t)=O ( T _i=1^n |D_i| ). Since |St|=k|S_t|=k for every t, we have ∑i=1n|Di|=∑t∈Devℓ∑i=1ni∈St=∑t∈Devℓ|St|=k|Devℓ| _i=1^n|D_i|= _t _ _i=1^n1\i∈ S_t\= _t _ |S_t|=k|Dev_ |. Next, by Cauchy–Schwarz (with ai=1a_i=1, bi=|Di|b_i= |D_i|), ∑i=1n|Di|≤n∑i=1n|Di|=nk|Devℓ|. _i=1^n |D_i|\;≤\; n\, _i=1^n|D_i|\;=\; nk|Dev_ |. Therefore ∑t∈Devℓr¯t≤Cd∑t∈Devℓ∑i∈Stβi(t)=O(nk|Devℓ|logT)=O(nℓklogTΔmin), _t _ r_t\;≤\;C_d _t _ _i∈ S_t _i(t)\;=\;O ( nk|Dev_ | T )\;=\;O\! ( n k\, T _ ), using (7) in the last step. Summing over ℓ∈[k] ∈[k] (using ∑ℓ=1kℓ=O(k2) _ =1^k =O(k^2)) and combining with (6) and the non-positive first term, R¯T≤∑ℓ=1kO(nℓklogTΔmin)=O(nk2.5logTΔmin)on ℰ. R_T\;≤\; _ =1^kO\! ( n k T _ )\;=\;O\! ( nk^2.5 T _ ) E. Theorem 2 (Gap-dependent bound (detailed version)). On ℰE, R¯T=O(nk2.5logT/Δmin) R_T=O (nk^2.5 T/ _ ). Combining both bounds Since rewards lie in [0,1]d[0,1]^d, r¯t∈[0,1] r_t∈[0,1] and R¯T≤T R_T≤ T always (on or off ℰE). Hence [R¯T]=[R¯Tℰ]+[R¯Tℰc]≤minO(CdnkTlogT),O(nk2.5logT/Δmin)+Tℙ(ℰc).E[ R_T]=E[ R_T1_E]+E[ R_T1_E^c]≤ \O (C_d nkT T ),\,O (nk^2.5 T/ _ ) \+T\,P(E^c). Choosing δ=1/Tδ=1/T gives Tℙ(ℰc)≤1T\,P(E^c)≤ 1, so: Theorem 3 (Regret of THV-UCB (detailed version)). With δ=1/Tδ=1/T, [R¯T]≤minO(nkTlogT),O(nk2.5logT/Δmin)+O(1).E[ R_T]\;≤\; \O ( nkT T ),\;O (nk^2.5 T/ _ ) \+O(1). In particular [R¯T]/T→0E[ R_T]/T→ 0: THV-UCB achieves sublinear α-approximation regret. Discussion: what does each bound use from the algorithm? The two guarantees of Theorem 3 are not in competition; they cover complementary regimes, exactly as the minimax and gap-dependent bounds do for classical K-armed UCB. The gap-free bound (Theorem 1) is algorithm-agnostic: its proof only uses that k arms are pulled per round and that confidence widths shrink at rate 1/Ni(t−1)1/ N_i(t-1); it never degrades, even as Δmin→0 _ → 0, the regime where the gap-dependent bound diverges. Conversely, the gap-dependent bound (Theorem 2) is mechanism-aware: it tracks, round by round, the exact comparisons ΔtUCB(⋅∣Gℓ−1⋆) _t^UCB(· G _ -1) that the greedy step of THV-UCB performs against the benchmark trajectory G⋆G — note that G⋆G , unlike S⋆S , 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 from G⋆G at each stage (see (7)), and a Cauchy–Schwarz argument bounding the total regret accrued on those rounds. Appendix B Experimental details Optimal values (Grid search) d=2d=2 d=3d=3 d=4d=4 d=5d=5 Algorithm Clust. Conc. Conv. Lin. Clust. Conc. Conv. Lin. Clust. Conc. Conv. Lin. Clust. Conc. Conv. Lin. THV-UCB (ours) 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 ParetoUCB+ 1.0 1.0 1.0 1.0 0.01 0.1 0.1 0.3 0.01 0.1 0.3 0.3 0.01 0.01 0.01 0.1 ParetoUCB-Div 0.3 0.1 1.0 0.01 1.0 0.3 0.3 0.3 0.01 0.01 0.01 0.3 0.01 0.01 1.0 0.1 ParetoUCB-Crowd 1.0 1.0 1.0 0.3 1.0 0.01 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 ChebyshevUCB 0.01 0.01 1.0 0.01 0.01 0.01 1.0 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 ChebyshevUCB+ 0.3 1.0 1.0 0.3 0.1 0.3 1.0 0.01 0.01 0.01 0.3 0.01 0.01 0.01 0.1 0.3 HVScalarUCB 0.01 0.01 1.0 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.3 0.01 0.01 0.01 0.01 HVScalarUCB+ 0.01 0.01 0.3 0.01 0.01 0.01 0.01 0.01 0.1 0.01 0.01 0.01 0.01 0.01 0.01 0.01 ScalarUCB 0.3 1.0 1.0 1.0 0.01 0.1 0.1 0.1 0.01 0.1 0.3 0.1 0.01 0.01 0.01 0.01 ScalarUCB-RandW 1.0 1.0 1.0 1.0 1.0 0.01 1.0 1.0 0.01 0.01 0.01 1.0 0.01 0.01 0.01 0.01 Table 2: Optimal confidence parameter η⋆η 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\ (maximizing HVlast100HV_last100). All detailed results are available in https://ngutowski.fr/gridsearch/gridsearch.html Additional results for d=3d=3 and k=4k=4 Clusters Concave Convex Linear Algorithm Fid. HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret THV-UCB (ours) — 0.2955± 0.001 2.8<<0.001 0.2894± 0.002 2.2<<0.001 0.5895± 0.003 2.5<<0.001 0.1592± 0.001 1.9± 0.1 ParetoUCB (Drugan and Nowe 2013) ∙ 0.1577± 0.034 141.1± 80.8 0.1757± 0.034 104.9± 78.5 0.4648± 0.043 45.4± 55.1 0.0610± 0.020 133.9± 55.1 ParetoUCB+ (Drugan and Nowe 2013) ∘ 0.2844± 0.008 2.8<<0.001 0.2755± 0.005 3.2± 1.3 0.5476± 0.011 24.3± 2.0 0.0934± 0.018 59.4± 40.1 ParetoUCB-Div (Drugan and Nowe 2013) ∘ 0.2083± 0.025 71.9± 52.2 0.1988± 0.018 33.2± 36.5 0.5161± 0.012 6.1± 1.3 0.0786± 0.014 93.8± 46.6 ParetoUCB-Crowd (Drugan and Nowe 2013; Deb et al. 2002) ∘ 0.1694± 0.021 62.1± 39.0 0.1290± 0.008 135.7± 41.8 0.4755± 0.038 4.6± 3.4 0.0251± 0.006 184.3± 28.6 ParetoTS (Yahyaa and Manderick 2015) ∙ 0.1708± 0.031 93.5± 63.4 0.1883± 0.030 60.4± 55.2 0.4836± 0.038 15.4± 20.9 0.0743± 0.020 91.7± 50.4 ParetoTS+ (Yahyaa and Manderick 2015) ∘ 0.2690± 0.011 12.4± 10.4 0.2678± 0.008 7.4± 6.8 0.5465± 0.009 3.0± 0.8 0.0868± 0.019 73.4± 45.1 ChebyshevUCB (Mandow et al. 2023) ∙ 0.1296± 0.055 246.0± 113.3 0.1968± 0.026 50.2± 26.6 0.4322± 0.035 23.0± 30.6 0.0980± 0.020 62.2± 32.8 ChebyshevUCB+ (Mandow et al. 2023) ∘ 0.2639± 0.008 3.7± 0.9 0.2727± 0.004 4.4± 1.3 0.5437± 0.008 9.0± 4.0 0.1401± 0.001 1.9± 0.1 HVScalarUCB (Zhang and Golovin 2020) ∙ 0.2046± 0.036 76.7± 62.1 0.2294± 0.027 33.2± 37.7 0.4526± 0.044 41.4± 55.7 0.1252± 0.017 27.9± 29.0 HVScalarUCB+ (Zhang 2024) ∙ 0.2500± 0.018 9.6± 10.8 0.2448± 0.018 9.1± 10.7 0.4956± 0.032 7.7± 8.8 0.1357± 0.010 6.8± 7.3 ScalarUCB (Auer et al. 2002) ∘ 0.2807± 0.010 2.8<<0.001 0.2757± 0.005 3.9± 2.1 0.5472± 0.007 2.6± 0.1 0.0891± 0.019 68.5± 43.7 ScalarUCB-RandW (Paria et al. 2020) ∘ 0.1484± 0.028 136.8± 59.9 0.1644± 0.030 91.6± 59.2 0.4483± 0.038 32.5± 32.9 0.0544± 0.017 132.7± 46.4 RandomK — 0.1035± 0.038 267.2± 104.2 0.1110± 0.042 231.3± 111.7 0.3151± 0.091 275.9± 208.8 0.0403± 0.018 183.8± 53.8 Table 3: Summary over four synthetic fronts (d=3d=3, n=60n=60, k=4k=4, σ=0.035σ=0.035, T=3000T=3000, 10 seeds). Fid. indicates fidelity to the cited work: ∙ = faithful top-k adaptation (core mechanism unchanged); ∘ = 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 α-regret ± 95% CI. Additional results for d=4d=4 and k=5k=5 Clusters Concave Convex Linear Algorithm Fid. HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret THV-UCB (ours) — 0.0854± 0.000 1.5± 0.0 0.1051± 0.000 1.6± 0.0 0.3709± 0.002 3.6± 0.0 0.0677± 0.000 1.4± 0.1 ParetoUCB (Drugan and Nowe 2013) ∙ 0.0255± 0.009 153.4± 44.6 0.0390± 0.012 150.9± 57.5 0.2369± 0.035 150.1± 123.6 0.0129± 0.007 150.5± 32.3 ParetoUCB+ (Drugan and Nowe 2013) ∘ 0.0791± 0.001 1.6± 0.1 0.0947± 0.002 4.9± 3.1 0.3384± 0.006 9.4± 1.4 0.0403± 0.006 44.2± 25.9 ParetoUCB-Div (Drugan and Nowe 2013) ∘ 0.0407± 0.003 80.2± 20.8 0.0492± 0.003 95.4± 19.7 0.2564± 0.009 19.9± 20.6 0.0199± 0.007 123.2± 35.2 ParetoUCB-Crowd (Drugan and Nowe 2013; Deb et al. 2002) ∘ 0.0109± 0.003 168.5± 22.6 0.0157± 0.006 215.0± 28.5 0.2388± 0.019 55.1± 41.9 0.0026± 0.002 170.3± 11.7 ParetoTS (Yahyaa and Manderick 2015) ∙ 0.0302± 0.010 121.3± 44.7 0.0468± 0.012 112.2± 53.0 0.2456± 0.033 98.2± 93.1 0.0218± 0.008 108.0± 35.4 ParetoTS+ (Yahyaa and Manderick 2015) ∘ 0.0749± 0.003 14.1± 9.6 0.0916± 0.003 10.6± 8.1 0.3365± 0.006 4.5± 1.5 0.0390± 0.007 48.7± 27.6 ChebyshevUCB (Mandow et al. 2023) ∙ 0.0211± 0.015 183.7± 57.1 0.0556± 0.008 73.2± 24.0 0.2349± 0.020 76.4± 27.9 0.0279± 0.005 81.5± 20.1 ChebyshevUCB+ (Mandow et al. 2023) ∘ 0.0800± 0.000 1.5<<0.001 0.0989± 0.000 1.6<<0.001 0.3503± 0.004 5.5± 1.4 0.0510± 0.001 1.9± 0.5 HVScalarUCB (Zhang and Golovin 2020) ∙ 0.0384± 0.011 115.8± 50.0 0.0539± 0.012 103.0± 50.7 0.2510± 0.029 77.9± 68.3 0.0290± 0.008 91.1± 36.9 HVScalarUCB+ (Zhang 2024) ∙ 0.0639± 0.006 24.3± 19.9 0.0852± 0.006 5.4± 5.6 0.3041± 0.020 13.2± 15.7 0.0532± 0.005 9.7± 9.1 ScalarUCB (Auer et al. 2002) ∘ 0.0791± 0.000 1.7± 0.2 0.0946± 0.002 5.8± 3.5 0.3379± 0.006 7.7± 4.1 0.0386± 0.007 41.8± 25.4 ScalarUCB-RandW (Paria et al. 2020) ∘ 0.0353± 0.011 100.7± 47.3 0.0444± 0.014 118.9± 58.9 0.2597± 0.030 67.9± 73.1 0.0206± 0.007 116.6± 31.9 RandomK — 0.0168± 0.008 186.6± 41.9 0.0255± 0.012 203.0± 58.7 0.1529± 0.048 427.7± 222.2 0.0098± 0.006 164.4± 29.6 Table 4: Summary over four synthetic fronts (d=4d=4, n=100n=100, k=5k=5, σ=0.025σ=0.025, T=5000T=5000, 10 seeds). Fid. indicates fidelity to the cited work: ∙ = faithful top-k adaptation (core mechanism unchanged); ∘ = 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 α-regret ± 95% CI. Additional results for d=5d=5 and k=6k=6 Clusters Concave Convex Linear Algorithm Fid. HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret HVlast100_last100 Final Regret THV-UCB (ours) — 0.0266<<0.001 0.7± 0.0 0.0202<<0.001 0.6± 0.0 0.1841± 0.001 3.7<<0.001 0.0095<<0.001 0.3± 0.0 ParetoUCB (Drugan and Nowe 2013) ∙ 0.0042± 0.002 64.7± 10.6 0.0032± 0.002 48.6± 8.0 0.0774± 0.018 229.0± 86.2 0.0010± 0.001 26.1± 3.1 ParetoUCB+ (Drugan and Nowe 2013) ∘ 0.0254<<0.001 0.8± 0.1 0.0197<<0.001 0.6± 0.1 0.1789<<0.001 3.7<<0.001 0.0051± 0.001 8.6± 4.6 ParetoUCB-Div (Drugan and Nowe 2013) ∘ 0.0141± 0.001 18.8± 5.8 0.0094± 0.001 22.3± 4.7 0.1144± 0.012 65.3± 29.6 0.0020± 0.001 21.4± 4.0 ParetoUCB-Crowd (Drugan and Nowe 2013; Deb et al. 2002) ∘ 0.0025± 0.001 64.4± 5.3 0.0015± 0.001 51.4± 4.9 0.0779± 0.010 176.9± 48.1 0.0015± 0.001 24.7± 2.3 ParetoTS (Yahyaa and Manderick 2015) ∙ 0.0057± 0.003 56.8± 12.3 0.0046± 0.002 41.1± 9.0 0.0853± 0.017 171.8± 76.6 0.0016± 0.001 23.3± 3.9 ParetoTS+ (Yahyaa and Manderick 2015) ∘ 0.0234± 0.001 8.1± 4.0 0.0173± 0.001 7.3± 3.7 0.1716± 0.004 7.5± 3.9 0.0050± 0.001 11.3± 5.0 ChebyshevUCB (Mandow et al. 2023) ∙ 0.0033± 0.003 69.9± 10.7 0.0092± 0.001 19.4± 3.2 0.0983± 0.008 111.9± 18.1 0.0047± 0.001 7.9± 2.9 ChebyshevUCB+ (Mandow et al. 2023) ∘ 0.0208<<0.001 0.7<<0.001 0.0150± 0.002 5.9± 3.2 0.1737± 0.003 6.3± 1.9 0.0016<<0.001 24.0± 2.3 HVScalarUCB (Zhang and Golovin 2020) ∙ 0.0194± 0.003 9.5± 9.4 0.0123± 0.002 13.2± 9.1 0.1334± 0.017 46.1± 47.0 0.0029± 0.001 17.1± 5.5 HVScalarUCB+ (Zhang 2024) ∙ 0.0218± 0.002 2.6± 2.5 0.0151± 0.002 4.3± 3.9 0.1434± 0.011 12.4± 12.5 0.0053± 0.001 8.1± 4.8 ScalarUCB (Auer et al. 2002) ∘ 0.0254<<0.001 0.8± 0.1 0.0197<<0.001 0.6± 0.1 0.1790<<0.001 3.7± 0.0 0.0049± 0.001 9.0± 4.6 ScalarUCB-RandW (Paria et al. 2020) ∘ 0.0103± 0.004 38.9± 16.6 0.0077± 0.003 31.0± 12.3 0.1222± 0.020 73.4± 57.5 0.0027± 0.001 18.8± 5.7 RandomK — 0.0028± 0.002 69.9± 9.3 0.0026± 0.002 51.5± 7.4 0.0473± 0.019 351.6± 93.0 0.0008± 0.001 27.0± 2.8 Table 5: Summary over four synthetic fronts (d=5d=5, n=150n=150, k=6k=6, σ=0.02σ=0.02, T=5000T=5000, 10 seeds). Fid. indicates fidelity to the cited work: ∙ = faithful top-k adaptation (core mechanism unchanged); ∘ = 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 α-regret ± 95% CI. (a) Clusters (b) Concave (c) Convex (d) Linear Figure 5: Hypervolume HV(St)HV(S_t) trajectories (moving average, w=50w=50) with 95%95\% CIs, over four synthetic Pareto front geometries (d=3d=3, n=60n=60, k=4k=4, σ=0.035σ=0.035, T=3000T=3000, 10 seeds). Each panel shows the best representative per algorithm family against THV-UCB (ours). (a) Clusters (b) Concave (c) Convex (d) Linear Figure 6: Hypervolume HV(St)HV(S_t) trajectories (moving average, w=50w=50) with 95%95\% CIs, over four synthetic Pareto front geometries (d=4d=4, n=100n=100, k=5k=5, σ=0.025σ=0.025, T=5000T=5000, 10 seeds). Each panel shows the best representative per algorithm family against THV-UCB (ours). (a) Clusters (b) Concave (c) Convex (d) Linear Figure 7: Hypervolume HV(St)HV(S_t) trajectories (moving average, w=50w=50) with 95%95\% CIs, over four synthetic Pareto front geometries (d=5d=5, n=150n=150, k=6k=6, σ=0.02σ=0.02, T=5000T=5000, 10 seeds). Each panel shows the best representative per algorithm family against THV-UCB (ours). Statistical tests Setting Baseline Bootstrap 95% CI Cohen’s d Wilcoxon p Wins d=2d=2, clusters ParetoUCB-Div +0.0048+0.0048 [+0.0034,+0.0063][+0.0034,\,+0.0063] 1.921.92 <0.001<0.001 10/1010/10 d=3d=3, concave ChebyshevUCB+ +0.0169+0.0169 [+0.0161,+0.0177][+0.0161,\,+0.0177] 12.3212.32 <0.001<0.001 10/1010/10 d=3d=3, convex ParetoTS+ +0.0430+0.0430 [+0.0418,+0.0442][+0.0418,\,+0.0442] 20.4520.45 <0.001<0.001 10/1010/10 d=4d=4, clusters ChebyshevUCB+ +0.0054+0.0054 [+0.0053,+0.0055][+0.0053,\,+0.0055] 31.7731.77 <0.001<0.001 10/1010/10 d=4d=4, concave ChebyshevUCB+ +0.0062+0.0062 [+0.0061,+0.0063][+0.0061,\,+0.0063] 44.4844.48 <0.001<0.001 10/1010/10 d=4d=4, linear HVScalarUCB+ +0.0145+0.0145 [+0.0141,+0.0148][+0.0141,\,+0.0148] 22.8422.84 <0.001<0.001 10/1010/10 d=5d=5, clusters ScalarUCB +0.0012+0.0012 [+0.0012,+0.0012][+0.0012,\,+0.0012] 29.9829.98 <0.001<0.001 10/1010/10 d=5d=5, concave ScalarUCB +0.0005+0.0005 [+0.0005,+0.0005][+0.0005,\,+0.0005] 8.098.09 <0.001<0.001 10/1010/10 d=5d=5, convex ScalarUCB +0.0051+0.0051 [+0.0049,+0.0053][+0.0049,\,+0.0053] 14.9714.97 <0.001<0.001 10/1010/10 d=5d=5, linear HVScalarUCB+ +0.0042+0.0042 [+0.0041,+0.0044][+0.0041,\,+0.0044] 19.5519.55 <0.001<0.001 10/1010/10 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). Δ denotes the mean difference in HVlast100HV_last100 (THV-UCB −- baseline). Bootstrap 95% CIs are computed over B=10,000B=10,000 resamples. 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 C Notation summary Symbol Meaning n Number of arms T Time horizon (rounds) d Number of objectives (reward dimensions) k Subset size selected each round [n][n] 1,…,n\1,…,n\ [T][T] 1,…,T\1,…,T\ St⊆[n]S_t [n] Slate (set) of k arms chosen at round t i,t∈[0,1]dX_i,t∈[0,1]^d Reward vector of arm i at round t i=[i,t] μ_i=E[X_i,t] Mean reward vector of arm i ^i(t) μ_i(t) Empirical mean of arm i up to round t Ni(t)N_i(t) Number of times arm i was selected up to round t ℱtF_t Filtration generated by observations up to round t ∈ℝdr ^d Reference point for hypervolume (dominated by all means) HV(S)HV(S) Dominated hypervolume of set S P Pareto front (set of undominated means) ⪯,≺ , (Strict) Pareto dominance relations η Confidence parameter; also governs sub-Gaussianity of reward coordinates βi(t) _i(t) Confidence radius for arm i at round t S⋆∈argmax|S|=kHV(S)S ∈ _|S|=kHV(S) Best size-k subset in hindsight V⋆=HV(S⋆)V =HV(S ) Benchmark hypervolume value G⋆=i1⋆,…,ik⋆G =\i _1,…,i _k\ Greedy benchmark on true means Gℓ⋆G _ Length-ℓ prefix of the greedy benchmark G⋆G Δ(i∣S)=HV(S∪i)−HV(S) (i S)=HV(S∪\i\)-HV(S) True marginal hypervolume gain Δℓ(i) _ (i) Stage-ℓ gap of arm i relative to G⋆G Δmin=minℓ∈[k]mini≠iℓ⋆Δℓ(i) _ = _ ∈[k] _i≠ i _ _ (i) Minimum stage-wise gap CdC_d Coordinate-wise Lipschitz constant of HVHV (Cd≤dC_d≤ d) ℰE High-probability event on which all confidence intervals hold rt=V⋆−HV(St)r_t=V -HV(S_t) Instantaneous regret w.r.t. V⋆V RT=∑t=1TrtR_T= _t=1^Tr_t Cumulative regret α Greedy approximation factor (1−1/e1-1/e) r¯t=αV⋆−HV(St) r_t=α V -HV(S_t) Instantaneous α-regret R¯T=∑t=1Tr¯t R_T= _t=1^T r_t Cumulative α-regret ∥⋅∥∞\|·\|_∞ ℓ∞ _∞ norm Table 7: Notation summary.