Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm
Authors: Mansoor Davoodi
Setareh Maghsudi
Venue: Accepted by TMLR ()

Abstract: Multi-armed bandit (MAB) problems are widely applied to online optimization tasks that require balancing exploration and exploitation. In practical scenarios, these tasks often involve multiple conflicting objectives, giving rise to multi-objective multi-armed bandits (MO-MAB). Existing MO-MAB approaches predominantly rely on the Pareto regret metric introduced in \citet{drugan2013designing}. However, this metric has notable limitations, particularly in accounting for all Pareto-optimal arms simultaneously. To address these challenges, we propose a novel and comprehensive regret metric that ensures balanced performance across conflicting objectives. Additionally, we introduce the concept of \textit{Efficient Pareto-Optimal} arms, which are specifically designed for online optimization. Based on our new metric, we develop a two-phase MO-MAB algorithm that achieves sublinear regret for both Pareto-optimal and efficient Pareto-optimal arms.

Published in Transactions on Machine Learning Research (02/2026)
Stochastic Multi-Objective Multi-Armed Bandits: Definition and Algorithm
Regret
Mansoor Davoodi
Monsoor Daasoor-DaooddiMoffoeeedeeee
Faculty of Electrical Engineering and Information Technology, Rubr- University Bochum, Bochum 44801, Germany Deportment of Computer Science and Information Technology, Institute for Advanced Studies Basic Sciences, Prof. Yousef Sobouti Blod. 444, 45137-66731, Zonjan, Iran
HERE Deutschland GmbH Co. KG, Inealidenstraßt 116, 10115 Berlin, Germany
Setarch Maghsudi
Faculty of Electrical Engineering and Information Technology
Ruhr- University Bochum, Bochum 44801, Germany
Reviewed OpenReview: https: https://openrevieew openreview. net/ forum? id= 7N7PX5CFPP
Abstract
Multi-armed bandit. (MAB) problems are widely applied to online optimization tasks that require balancing exploration and exploitation. In practical scenarios, these tasks often involve multiple conflicting objectives, giving rise to multi-objective multi-armed bandits (MO-MAB). Existing MO-MAB approaches predominantly rely the Pareto regret met- ric introduced in Drugan & Nowe (2013). However, this metric has notable limitations, particularly in accounting for all Pareto-optimal arms simultaneously. To address these challenges, we propose a novel and comprehensive regret metric that ensures balanced per- formance across conflicting objectives. Additionally, we introduce the concept of Efficient Pareto- Oatimol arms, which are specifically designed for online optimization. Based on our new metric, we develop (wo-phase MO-MAB algorithm that achieves sublinear regret for both Pareto-optimal and efficient Pareto-optimal arms.
1 Introduction
Multi-armed bandits (MAB) form a loundational framework machine learning with wide-ranging applica- tions in online optimization tasks such as recommendation systems and online advertising [llvkkins] (2019). The objective in MAB problems is to scquentially select actions (arms) that balance exploration (Icarning about unknown arms) and exploitation (maximizing cumulative rewards). In many real-world scenarios, de- cisions involve trade-offs among multiple conflicting objectives, which has led to the study of multi-objective multi-armed bandits (MO-MAB). In MO-MAB, the goal is to identify Pareto-optimal (PO) solutions that represent the best tradc-offs among the objectives, making this problem highly relevant in areas such as multi-criteria decision-making Wei al. (2021)
Despite growing interest in MO-MAB, most existing work relies on the Pareto regret metric introduced by Drugan al. Drugan & Nowé (0013). Although this metric serves as useful starting point and has been widely adopted, it has several significant limitations. Specifically, the metric focuses the minimum distance of an arm's reward vector to the Parcto front in one direction, neglecting the performance across other objectives. This can lead to situations where algorithus optimizing a single objective are evaluated as highly effective, even though they may fail to balance other objectives (e.g., see Xu & Klabjan (2023 Morcover, the metric inadequately penalizes poor performance in unoptimized objectives and fails ensure diversity in the objective space (for a detailed discussion of this metric, see Section 3). Consequently, existing regret. metrics insufficient for fully evaluating the performance of MO-MAB algorithms.

---

Published in Transactions on Machine Learning Research (02/2026)
To address these limitations, more comprehensive regret definition that accounts for multiple objectives is crucial for a more accurate evaluation of algorithms in multi-objective settings. In this paper, we make the following key contributions:
We propose a novel and comprehensive regret metric for MO-MAB that overcomes the limitations of cxisting metrics by simultancously considering all objectives.
We introduce the concept of Efficient Pareto- Pereto-Optimal (EPO) arms, tailored for online optimization scttings, to capture the round-based nature of MO-MAB problems better.
We develop a two-phase explore-exploit algorithm that achieves sublinear regret for both PO and EPO arms. For n arms over T rounds, it offers two implementations: an exponential-time variant with regret O (I (n (ogg and polynomial-time variant achieving (log n T (n log T)))
2 Related Work
Traditional Multi-Armed Bandit (MAB) problems focus on maximizing a single cumulative reward Slivkins (2019), but many real-world applications involve multiple conflicting objectives. This complexity has led to the development of Multi-Obe Alutti-Obeective Aamei Bandits (MO-MAB), where the goal is to simultaneously maximize multiple objectives by pulling Pareto-optimal arms. A key challenge in this area is the evaluation of MO-MAB algorithms, particularly the design of an appropriate regret metric.
Drugan and Nowé 2013 introduced the first Pareto regret framework for MO-MAB, combining scalariza- tion with an exploration-cxplottaaio algorithm called Pareto- Pareto-UCBI, which demonstrated logarithmic regret bounds. Their empirical studies Drugan al. (2014) validated the algorithm on multi-objective Bernoulli distributions. However, challenges remain in balaneing performance across objectives and ensuring diversity along the Pareto front. These limitations of the Pareto regret metric and Pareto-UCBI are discussed in Section 3 Before delving into these issues, we provide an overview of related work and how recent studies have built. on the Pareto regret framework.
Mahdavi et al. 2013 applied stochastic convex optimization techniques to MO-MAB, introducing scalariza- tion functions (e.g., Chebyshev and linear scalarization) to address the complexity of optimizing multiple objectives under uncertainty. Yahyaa et al. 2014 developed the Annealing- Pareto algorithm, which adapts the anncaling concept to MO-MAB, dynamically adjusting exploration intensity to improve the trade-off be- tween exploration and exploitation. Yahyaa and Manderick 2015 applied Thompson sampling to MO-MAB, selecting arms based on their posterior distributions to manage uncertainty.
Busa-Fekete et al. 2017 proposed a MAB framework using the gencralized Gini index, allowing the algorithm to prioritize better trade-offs and balance multiple objectives more effectively. They provided both theoretical analysis and empirical results showing improvements in exploration and exploitation. Öner et al. 2018 extended MAB by studying the combinatorial MO-MAB problem, where multiple arms can be selected each round. Their algorithm combines poplorationccxploitatiio strategies with combinatorial optimization to address conflicting objectives and constraints. Lu et al. developpd framework for generalized linear bandits, applying regret minimization techniques to handle multi-objective settings, offering both theoretical guarantees and empirical validation.
Xu and Klabjan 2023 extended the Pareto regret framework to adversarial settings in MAB, presenting algorithms for both stochastic and adversarial scenarios. However, their focus on optimizing a single objective led to suboptimal solutions in multi-objective contexts, where only one direction of the Pareto front was considered.
Turgay et al. 2018 integrated contextual information into MO-MAB, optimizing the decision-making process by considering contextual relationships between arms and objectives. Hüyük and Tekin 2021 developed an algorithm incorporating lexicographical ordering (prioritizing objectives) and satisfying (ensuring objectives exceod thresholds). Their analysis offered insights into improving the efficiency of MO-MAB. Xue al. 2023 extended this work by generalizing lexicographically ordered MO-MAB from priority- based regret to general regret.
2

---

Published in Transactions on Machine Learning Research (02/2026)
Cheng et al. 2024 proposed an algorithm that hierarchizes Pareto dominance to improve regret minimization by prioritizing objectives and refining exploration strategies. Ararat and Tekin 2023 introduced a frame- work based on a polyhedral ordering cone to define directional preferences among vector rewards, replacing traditional Pareto dominance, and established gap-dependent and worst-case sample complexity bounds for it. Crépon et al. 2024 studied the challenge of learning and identifying Pareto-optimal arms under the stochastic multi-armed bandit framework. They presented an algorithm to guarantee suboptimality relative to the true Pareto front. Building upon this, Karagözlü et al. 22024 addressed the challenge of learning the Pareto-optimal set under incomplete preferences in pure exploration setting, providing an algorithm to identify Pareto-optimal arms.
In general, the approaches aiming to minimize Pareto regret, as defined by Drugan & Nowé (2013), either directly (e.g.. Xu & Klabjan )023)) ) or indirectly (e.g., Drugan et al. (0144)), often focus on optimizing along single objective direction. While this can result in non-dominated solutions one dimension, it fails to capture the entire Pareto front. To address these limitations, we propose a new regret metric that comprehensively evaluates performance across multiple objectives.
3 Analysis of Pareto Regret Used in the Literature
In 2013, Drugan et al. 2013 introduced the first regret metric for evaluating the efficiency of MO-MAB algorithms, known as Pareto regret. This metric quantifics, for each arm a, the distance between its reward vector (la)) and the Pareto-optinal (PO) set A". To do this, virtual reward vector v(a)* is constructed by adding a value to each objective of a until it becomes incomparable (non-dominating) with any arm in A". The regret A(a) is then defined as the difference between v(a)* and the original reward vector p(a), effectively representing the minimum distance to the Pareto front. While this metric is simple and widely adopted, it has several notable limitations. The most signíficant issue that evaluates arms based solely on their distance the Pareto front in one direction, without considering their performance across all objectives. This can lead to situations where algorithms optimizing single objective achieve low regret even if they perform poorly on other objectives. For example, algorithms designed to prioritize one objective (e.g., see Xu & Klabjan (2023) may appear effective under this metric despite failing to achieve a well-balanced multi-objective performance.
Figure D (left panel) illustrates this problem in a MO-MAB instance with three arms. Here, the Pareto UCB algorithm presented in Drugan & Nowé (2013) ropeatedly (and fairly) selocts the suboptimal arm with reward (0, 0), despite it being strictly dominated by arms (1,0) and (0, Indeed, the algorithm only does
8-log (T (DIA*) where
not select this dominated arm in the second round. Although the regret bound End T is the number of plays and D is the number of objectives, claimed by Drugan & Nowé (2013) holds, the choice of A, as a small positive value can lead to poor practical performance. This issue is compounded in higherodimensionall settings, where the number of suboptimal arms grows exponentially with the number of objectives, dramatically reducing the probability of selecting even a PO arm in each round.
Additionally, Drugan et al. introdueed a fairness concept to encourage more balanced performance across the PO arms. However, this metric assumes a uniform distribution of PO solutions along the Pareto front, a condition that is rarely met in real-world problems. For example, Figure | (right panel) shows a non-uniform Pareto front where fairness fails to ensure diversity. When the algorithm plays 'fairly,' as defined by Drugan & Nowé (2013), it may repeatedly select arms clustered near one extreme of the Pareto front, neglecting other promising regions.
These challenges highlight the shortcomings of the existing Pareto regret metric. Although it provides useful insights in certain cases, does not adequately capture the trade-offs inherent in MO-MAB problems. Therefore, there is a clear need for a more comprehensive regret metric that evaluates algorithm performance holistically, accounting for both balance across objectives and diversity along the Pareto front
3

---

Published in Transactions on Machine Learning Research (02/2026)
f2
f2
(0, 1)
(1,0) f
(0, 0)
f1
(a)
(b)
Figure 1: (a) MO-MAB instance with three arms: (1,0), (0,1), and (0,0). (b) PO solutions in bi-object
maximization problem, not uniformly spread.
4 Multi-objective Multi-Armed Bandits
4.1 Domination and Efficient Pareto Optimal Arms
The main objective of solving multi-objective optimization problems to identify a set of solutions that are close to the Pareto-Optimal (PO) solutions, while simultaneously ensuring a high degree of diversity within the objective space. This involves two orthogonal goals: first, to approximate the PO set as closely as possible, guaranteeing that the solutions reflect the best trade-offs among the competing objectives; and second, to maintain sufficient diversity among these solutions, covering various regions of the objective space. Such diversily is crucial for addressing different preferences among prcision-maken elfectively Coello (2007). These goals, and particularly the first one, can be extended naturally to online optimization and stochastic multi-objective multi-armed bandits (MO-MAB). Given an instance of MO-MAB problem with n arms, denoted by A = {a1, 02 Q2,... .... ) and D (maximization) objectives F fe, .e...., fp), let the reward vector of arm a E A at time (or round) & be denoted as:
(a) = (ri(a), r5((), ...., (a))),
where ra)(a) is the reward of arm a in the d-th objective (or dimension) at time the stochastic setting
T
Σ (a)
where pa(a) is the expected reward of arm in dimension d.
In the multi-objective context, an arm a is said to dominate another arm b (denoted as a > b) if and only if a is at least as good as in all objectives, and strictly better in at least one objective. Formally, for two reward vectors ra) (ri) rr)))...... (. (a)) and r' (b) = (b), (i,b),,..,,,.blll, arm a dominates b if:
ra((a) (b) for all d E [D), and
ra((a) > (b) for at least one d E [D],
D}. Similarly, is said to weakly dominate b) if and only if is at least good as b in all objectives, i.e., r ra((a r((b) for all d E [D]. So, an E A is non-dominated, if there does not exist any other arm b E A such that b dominates (i.c., vb A b 34 a). Finally, the set of all non-dominated arms is called the Pareto-optimal (PO) set and denoted by At. The image of PO arms in the objective space is called Pareto Front.
where [D] denotes the first positive integers, [D] =
(denoted
In online optimization and MAB, the iterative nature of the process shifts the objective from single-instance instance optimization to maximizing cumulative rewards over a given number of rounds. Unlike classical optimization, where a single decision made, the picision-maker in this context selects (or pulls) from available choices iteratively over T rounds. Therefore, introduce the concept of the Efficcint Pareto- Optimal (EPO) set.,
4

---

Published in Transactions on Machine Learning Research (02/2026)
which represents efficient subset of the PO set, specifically tailored to maximize cummlative performance in an iterative decision-making setting. To this end, we need to extend the definition of domination to a subset of arms.
Let S = (al ..a....,,a'' a²) be the sequence of arms selected by a decision-makes (arm at at round E [T] is pulled). So, the cumulative reward vector of given by:
F(S) = Σ r(a))
We can restrict the sequence of selected arms to any subset of arms. Let X C A' and Y C A' be two different subsets of PO arms, and Sx and Sy be two sequences of arms selected (only) from X and Y, respectively. We say weakly dominates Y, denoted Y, if for any sequence Sy, there exists a sequence Sx such that the cumulative reward vector of Sx weakly dominates that of Sy. Formally,
X = ASy E Y, xSx E X such that r(Sx) 2 r(Sy).
Since the domination relation between sets involves convex combinations of arms with real-valued weights, while arm selections in each round are discrete (integer-valued), the domination relationship requires sufficiently large number of rounds to achieve the desired weight approximation through integer pulls. More precisely, for the domination to hold, there must exist a threshold To beyond which the integer constraints allow for a sufficiently accurate rational approximation of the required convex weights:
X =
= ASY EY, SSx E X:
To E N, To. F(Sx) 2 F(Sx)
where To depends on the precision required to approximate the optimal convex weights through integer- valued arm pulls. In terms of the domination relation between sets of individual arms, two scenarios are possible: either one set dominates the other, or the sets are non-dominated with respect to each other. Now, we can define EPO set EAAt as
(a' EA'- (a' E A'I A \ (() F((a")))
As an example, assume a simple instance of a MO-MAB problem with three PO arms a, b and e with reward vectors Fn = (1, lb = (0, and re = (e for some small positive value e. In this scenario, when a decision-maker pulls arms a and b iteratively, the average reward vector (the cumulative reward is a similar discussion) achieved is ()) However, if the mecision-maker pulls arm e, the resulting average reward vector would be ec, which is lower than the first case for c < 1.- In this sense, b} > fc).
In this example, the positions of the arms form symmetric configuration. For this symmetry reason, if arms a and b are pulled equally often, the cumulative reward vector {a, b} always dominates the reward of arm c. In the general case, suppose arm a is pulled na times and arm is pulled n, times, where na + n, = T. So, the resulting average reward vector linear combination of the reward vectors of a and b with the weights w. "r and wa = ns respectively. As illustrated in Figure 2 (the left panel), this average vector will dominate any other arm whose reward vector is located within the gray region below and to the left of it. Although adjusting n. and ny can potentially cover the entire area below the line segment the Pareto front between a and b, for any fixed combination of and no, there remain two triangular regions that are not dominated by it. However, on the reverse side, for any arm e below the Pareto segment connecting a and b on the Pareto front, there exists a specific range of values for na and ny such that the average vector f + b dominates a (illustrated in the right panel of Figure
Note that, in this example, {a, b) > {c} holds while lies below the line segment. If lies above it, no pair of na and ny will be able to dominate c. This means that linear combination of a and b can dominate
5

---

Published in Transactions on Machine Learning Research (02/2020)
f2
f2
Waa a + w/b
f
f1
(a)
(b)
Figure 2: Dominance regions in MO-MAB. (a) Dominating region of a linear combination of two PO arms with rewards (1.0) and (0,1). (b) An MO-MAB instance with three arms: a == (1.0), b (0, 1), and (0.2, 0.2). dominated by linear combinations of and b in the gray region.
In general, an arm a at a given time t is weakly dominated by some linear combinations of 01, 02,00..... 0t if and only if, there exist a =< an, 02,.. ag such that aar 2 (a), where Σ 0;
Where, raa))= u(a.) in the stochastic MO-MAB. Thus, the set EA' represents those PO arms that lie in the convex position on the Pareto front. Therefore, after finding A the arms of EA* can be efficiently found in polynomial time using a linear programming approach with n² - variables and D constraints, where n² = [A*), and we do not need to find the convex hull of the arms which has exponential complexity. As result of such a lincar programming problem, if there no feasible solution a = (aj, 022 ...: Qr), arm a belongs to E,A", otherwise, al. least one vector a that Σl= (a,) weakly dominates ra(a) is computed.
A practical example. Multi-objective Vehicle Routing Problems (VRPs) constitute a major operational challenge for large-scale logistics providers such as DHL, Amazon, and national postal services, where 1,000-10.000 10,0000000 daily delivery tasks must be optimized under competing objectives with unknown priority weights. These include minimizing unassigned tasks, travel distance and duration, territorial overlap among routes, and soft-constraint violations (e.g., time-window penalties), while simultaneously maximizing route obnjecttess-oojeetives that span incommensurable scales (monetary costs versus spatial quality concepts). At such scales, exact optimization is computationally prohibitive, rendering metaheuristic methods the only viable solution approach. Contemporary metahouristics primarily employ ruin-and-recreate operators that partially dismantle incumbent solutions and reconstruct them using insertion heuristics. Modern systems combine diverse ruin strategies (e.g., cluster removal, worst-job removal, neighbor removal) with multiple rocreate strategics (o.g., regret-based, cheapest, gap-based insertion), producing more than sixty operator configurations whose performance is highly problem-dependent and shaped by spatial structure, temporal constraints, and regulatory requirements Vidal et al. (2012). Each configuration can be viewed as an arm in multi-armed bandit framework, yielding multi-dimensionn rewards across objectives. Unlike experimental testing phases, each iteration directly impacts operational performance- poor exploration translates to im- mediate costs and service degradation. The solver must therefore maintain diverse efficient strategies while minimizing cumulative regret over thousands of itcrations.
Conventional Pareto-based multi-armed bandit formulations insufficient in this context because they treat all non-dominated arms equivalently. Consequently, configuration offering negligible (e.g., 0.01%) uniform improvements is regarded as equally valuable one delivering substantial progress (c.g., a 0.5% reduction in distance) despite secondary objective trade-ofls. Yet cumulative solution quality over generations depends on achieving meaningful aggregated gains. Two complementary Pareto-efficient strategies that each produce substantial improvements distinct objectives can jointly yield far greater cumulative progress than uni- formly weak Pareto strategies. The notion of efficient Pareto-optimal arms directly addresses this limitation by distinguishing genuinely promising configurations from those providing only trivial non-dominated gains.
6

---

Published in Transactions on Machine Learning Research (02/2026)
4.2 Definition of Regret in MO-MAB
In MO-MAB problems, since there is more than one PO arm, the definition of regrei is more complex. Most studies over the last decade have relied on the definition introduced in Drugan & Nowé (2013), which is discussed in Section 3 In this paper, we propose a more comprehensive definition of regret that is better suited to MO-MAB. Our definition formulated to be applicable to both PO arms and EPO arms.
An algorithm Alg that chooses an arm at time ...,... has regret R compared to an arm a" E A (or alternatively an EPO arm a' E &A*), if
E
ra(aa)
Ers(a) S R. AA E [D].
In the stochastic setting,
with Tpd(a"). Let denote this concept by a (T) < R. Notably, the above definition of regret is stronger than the definition of 'non-domination" used in Drugan & Nowé (2013). Here, RAlg,a (T) guarantees that the outcome is not only non-dominated compared to a" but also dominates it if it is improved by the regret value. Specifically, it is necessary to satisfy the inequality across all objectives, rather than just in one objective.
replace I
Now, let us extend RAlg,a (T) to the case where Alg selects a set of arms A at cach round 1.2,..., and we compare to all PO arms. In this case, we say that Alg is R-regret, and denote by RAI((T) R. if the following regret properties met:
1. Coverage- Roverage-Regret
For any PO arm a" A" (or alternatively EPO arm a" E EA"); there exists arm al E A such that:
E
ra(a")
Σ ra(aa)
R, Ad (D)-
(2)
Tpa(a") -
Σ
ra(aaa)
S R. Vd E [D].
(3)
This property ensures that the algorithm can effectively approximate any PO (EPO) arm in terms of the reward vectors ra across all dimensions d and over T iterations.
2. Cumulative Adjustment Reegeet
The cumulative minimal adjustment required for the arms in A' to weakly dominate some PO arm (or EPO arm) satisfies:
T Σ
Σ
minfe 2 Ba" A a +ez a²) s SLA'R
Alternatively, we can replace A with EAA..
This property bounds the cumulative regret associated with the adjustments needed for the arms selected by the algorithm to weakly dominate the optimal A" (or EA").
Regret Interpretation
We define two complementary regret properties that jointly characterize algorithm performance: coverage- regret ensures completeness by requiring that all PO (or EPO) arms are well-approximatel, while cumulative
7

---

Published in Transactions on Machine Learning Research (02/2026)
adjustment-regret enforces minimality by penalizing unnecessarily large sets of selected arms. These two properties are complementary, as they measure orthogonal aspects of solution quality. The coverage-regret property evaluates how well the algorithm approximates the PO arms in the Pareto front. Specifically, it measures the discrepancy (in terms of rewards across all dimensions d) between a PO arm a" E AA" (or a* EAA') and the nearest arm a' E A'. For each iteration i, the algorithm selects an arm at E A' that minimizes:
6= max (ra(a")-rale dE(D]
Thus, the selected arm a' ensures that the adjusted (virtual) arm a' + weakly dominates a'. The total expected regret over T iterations is bounded by R, indicating the quality of the coverage provided by the algorithm for the Pareto front. As complement, the cumulative adjustment-regret property evaluates the inverse relationship, quantifying the cumulative minimal adjustment required for the arms A to weakly dominate the optimal set A (or EA*). While a larger set A' reduces the coverage-regret, it increases the cumulative adjustment-regret due to the additional adjustments needed to align the selected arms with the optimal arms. This trade-off implies that A should ideally approximate the Pareto front with a size proportional to |A*), ensuring bounded cumulative adjustment-regret.
The interplay between coverage-regre regret and cumulative adjustment-regret highlights the balance required in selecting a representative set A Increasing the size of A improves coverage (reducing the coverage- regret) but may result in higher cumulative adjustment-rogret, To optimize performance, A' should approximate A as closely as possible while maintaining manageable size, leading to a bounded cumulative adjustment-regre of |A* R. For single-objective MAB problems, D = 1, the above definitions reduce to the classical notion of regret: both coverago-regret and cumulative adjustment-regret collapse the r'a') I R, where a" is the unique optimal arm. Our regret framework is comprehensive by design, requiring algorithms to compete against A across all dimensions d = I....,D simultaneously, rather than merely excelling in a subset of objectives. This stringent requirement distinguishes our approach from previous formulations, where superiority in just one dimension suffices for non-domination. While the bound appears
standard formulation EE "(=r"((a)) - - rat')
wwwpusion-indeeeddden in its functional form, the underlying algorithmic complexity scales with D due to the requirement for comprehensive coverage. Furthermore, in multi-objective settings, the regret value in the coverage- property is non-negative when applied to EAA" but may be negative for A' due to the non-convexity of the Pareto front. This behavior arises because the iterative decision decision-making making process in MAB allows selecting subsets of arms that collectively achieve superior rewards compared to individual non-convex PO arms.
5 A simple Multi-Objective MAB Algorithm
We introduce the first MO-MAB algorithm with a sublincar regret bound that satisfics both the coverage- regret and cumulative adjustment-regret properties, achieving regret of R R= O ( [ (n log Addition- ally, we demonstrate that the algorithm's 's outcomes converge to the PO set as T - co. The algorithm is initially explained and analyzed for PO arms, and we later extend the approach to efficiently handle EPO arms as well. This algorithm has two phases: In the exploration phase, each arm is explored by pulling it fixed number of times (T") to estimate the average reward for each arm. In the exploitation phase, the set of a minimum number of arms that cover all arms is identified (B) and pulled until itcration T. The pseudocode of the algorithm is represented below. The notation 2r represents adding the scalar 2r to each dimension of arm a's reward vector.
Complexity. After T' rounds, Algorithm in Step 5, removes all the arms that are clcarly dominated by some other arms. This step lakes O O(D)²) time and is valid because, at this stage, all arms are clean with a radius r, as established in Theorem this step. The primary purpose of Step to improve the algorithm's expected complexity. However, for worst-case analysis, this step can be omitted without affecting the theoretical regret guarantees of the algorithm.
Importantly, no Pareto-optimal (PO) arms are discarded during
8

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm A Simple MO-MAB Algorithm
1: Input: Number of arms n, time horizon T
2: Set 7" = - $ (2 log T)
3: Pull each arm times, and compute the average reward vector jiaa for all arms a E A
4: Set the confidence radius V
2
Remove all arms A if there exists some a' E A such that a' > a 2r for any arm E do Compute list Dom(a) {a' E 8: end for
9: Compute the minimum set of arms B such that USEB Dom(b) = A
to T do 11: Pull all arms E
10: for t= T
12: end for
13: return B
Next, the algorithm computes Dom(a) for each arm a, which represents the set of all arms d' weakly dominated by a + 2r. Following this, the algorithm performs the minimum set cover computation of arms in Step 9. Specifically, identifies the smallest number of improved arms, cach enhanced by factor of 2r, that weakly dominate all other arms. This set is called the minimmm set covering of arms.
The set cover problem a well-known NP-hard problem Vazirani (2003), and in our scenario, it can be solved exactly with a time complexity of O(2 n) in the worst case, assuming no arms are removed in Step 5. Consequently, the overall complexity of Algorithm [ O n). However, in the expected case, the number of PO arms is polylogarithmic in Bentley al. (1978). This means the average running time of Algorithm 1 is O(2(log n)- (log (ogg))-1) even for computing the exact minimum set cover, e.g., O(n logn) time for 2.
To address the worst-case time complexity of Algorithm we can employ an approximation algorithm that achieves an approximation ratio of Ollog n) Vazirani (2003). This allows us reduce the complexity to polynomial time while obtaining solution that is within factor of O n) of the optimal set cover size. Therefore, we have two options:
Compute the optimal set cover in 0(2" .n) time.
2. Utilize an - approxmmaatonn algorithm to obtain a set cover in polynomial time.
It is important to note that the approximate solution guarantees that the size of the set cover will be most O(log n) times larger than the optimal solution. This trade-off between optimality and computational efficiency provides flexibility depending on the specific requirements and constraints of the application.
In the following, we demonstrate the impact of the two computational approaches on the complexity and regret of Algorithm ! The first option, which computes the exact minimum set cover, results an exponential-time algorithm with regret bound of R o (n The sccond option, employ- ing the Ollog n.) approximmaioonnn approach, yields polynomial-tine complexity algorithm with regret bound of R = O [logn- 2 log T)+).
The regret analysis of the proposed algorithm is summarized in the following theorems, with detailed proofs deferred to the Appendix.
Theorem 1. The coverage-regrel of algorithm is R= R ( T)
Theorem 2. The outcome of Algorithm 7 converges to the PO arms A T -
Lemma 1. In case of the clean event C happens, the optimal solution for the minimum set covering of arms, compuled in Slep 9 of Algorithm 7 is bounded by |A*).

---

Published in Transactions on Machine Learning Research (02/2026)
Theorem 3.
The cumulative adjustment-regret is hold for algorithm with the regret R R (n
Theorem 4. In Algorithm 1 if after computing the minimuum arm covering set B, the non-efficient arms are removed, Theorem Theorem 2 and Theorem remain valid for the efficient PO urms, EAA..
Before concluding the theoretical results, we elucidate an additional property of the proposed MO-MAB algorithm, which pertains to the concept of diversity in classical multi-objective optimization problems (MOPs) Coello (2007), and its implications for computing regret in MAB approaches that compare the outcome with only one best arm. While our analysis focuses on all PO arms, the conclusions are equally applicable to EPO arms.
Diversity, critical secondary objective in MOPs, concerns the challenge of identifying representative ive subset of PO solutions that is as diverse as possible within the objective space. Since multi-objective optimization algorithms typically generate a limited subset of solutions from a polentially vast set of PO solutions, ensuring adequate diversity in this subset is crucial. The proposed Algorithm addresses this by selecting the minimal set covering arms, which are improved by a radius r = V log This implies that multiple PO arms exist within specific region of the Pareto front, the algorithm prioritizes a minimun subset of these arms capable of dominating all others in the same region (when improved by a factor of 2r).
[
Consider (maximal) diverse set of PO arms, denoted as DPO, characterized by radius / log /21g5 Define virtual arm b' whose reward is the coordinate-wise average of the arms in DPO:
ra(b")
Σ ra(a"), e'EDPO
Vd E [D].
DPO
The arm b* can be interpreted the expected reward achievable by a decision-maiee who restricts his choices to diverse subset of Pareto-optimal arms within a specified radius This approach an optimal strategy for efficiently covering all regions of the Pareto front. Another interpretation of this best arm b* is the cumulative reward if the decision- maker randomly chooses one Pareto-optimal arm in DPO in each round. Importantly, this definition extends the concept of selecting the 'best' arm from single-objective multi- armed bandit (MAB) problems to multi-objective contexts. Unlike a simple weighted lincar combination of objectives, this formulation focuses on the average reward across the diverse set of PO arms rather than directly aggregating the objective values.
Now, consider version of Algorithm I that, after T' rounds, and computing the minimum covering arms B, only one arm is randomly selected from B and pulled for rounds L = T" + 1,7" + 2,...., Thus, the number of all pulls will be nI" + (T - -T)). In the following, we show that this version of the algorithm is an R=O (T (n log l)g compared to b" introduced above.
Theorem 5. The regret of the single orm pulling version of Algorithm compared to the average best arm b' is R 0 (T3 (n logg))) T)²s)
Proof. The proof is similar to the poof of Theorem Under the clean events, since all the arms are pulled in the first T' rounds, then the regret value in the first T" iteration of the algorithm is at most nI" in total (as Term 1). Now, assume b' is the random arm selected from the computed minimum covering arms B, so,
Term 2 E E Σ minfe 2 0: + 63
As discussed, under the clean event condition, the arms in B are the minimum covering DPO set. That means, improving each arm E with the radius 2r will dominate some Parcto arm in DPO. So, selecting uniformly random arms from B in rounds = T' 7 11,T" T" + 2...., results in the expected sum of difference with ra(b*) does not exceed O(2r) for all d E [D]. Therefore, the total regret be written as
10

---

Published in Transactions on Machine Learning Research (02/2026)
B S nT + O((T- - 22)) S nT + O(T2r),
where is constant. Replacing T' = =z) (2 T) and 22 results in E S O (T (n log TT}
Proposition. When T + 00, so r r 0, and DPD will equal all the Pareto-optimal arms. Thus, Theorem holds for the definition of the best arm, which corresponds to the mcan reward of the Parcto-optimal arms.
6 Experimental Results
While our primary contributions lie in the formal analysis of the proposed multi-objective bandit framework and its regret guarantees, we also provide an empirical assessment to illustrate the algorithm's practical behavior. All code was written in Python and exccuted on a laptop with an Intel Core 17-1165G7 CPU (2.80 GHz) and 16 GB of RAM.
For each problem size (n, D, T), we generate a single sot of "truc" mean vectors (Ma.d)a dd=1..... by sampling uniformly from [0, 1]. During the rounds, we sample stochastic outcomes
R Bernoull((ja.d);
for a a= L......, n, d subroutines. This ensures that both methods operate on identical empirical data. As explained, the exact set cover algorithm exhaustively searches all subsets of candidate set of arms whose union covers all arms. It explores combinations of increasing size, ensuring optimality but requiring exponential time. The greedy approach iteratively selects the set that covers the largest number of uncovered arms until full coverage is achieved. It runs in polynomial time and guarantees optimality with a logarithmic approximation Vazirani (2003).
At round t = T", we run both the exact and greedy set-cover
be set. B in algorithm as the smallest
We conduct experiments for n {20, 50, 100} and E (2,3,5), 5}, and we choose the total horizon T large /2m ensures that
enough so that the confidence radius is approximately 0.02. In theory, adding 2r to each empirical mean yields valid dominance relations, but it can easily produce values near unity- collapcoll the cover set, B, to size onc. To achieve practically meaningful margin (c.g. = 0.02), T' (and thus T) must grow by orders of magnilude. Consequently, one lypically calibrates below its theo- retical bound, accepting slight relaxation of the guarantee in favor of a non-degenerate arm selection. For example, choosing T = 10a yiclds T' x 10t and r z 0.02. Each configuration is repeated independently 10 times to reduce sampling noise. We measure (i) the average true PO size, (ii) the average cover size [B] in the algorithm, and (iii) the average wall-clock time for each case approximation and exact approach to compute the minimum set cover, reporting these values in Table
Table D shows that the number of arms or the number of objectives D increases, the average Pareto- optimal set grows substantially (from roughly 4-5 arms at D = 2 to over 27 arms at = 100, D 5). Both exact and greedy set-cover methods consistently produce cover sets |B] that are somewhat smaller than the true Pareto front, demonstrating effective reduction of candidate arms while preserving coverage. The greedy heuristic typically selects a cover of size within one arm of the exact solver (e.g., 7.5 vs. 7.2 at n 100, 3), at a fraction of the runtime (orders of milliscconds versus scconds when D and n grow). These results confirm that the greedy approximation achieves near-optimal cover sizes in practice, with dramatic savings in computation time problem dimensions scale.
Another notable feature of the algorithm is its economy in the exploitation phase: it identifies a small arm- set B to pull after exploration. For instance, with n = 100, D = 5, and T = 10a the procedure dedicates only T" = 97 295 rounds to exploration, then confines all remaining pulls to B = 15 arms out of 27 true Pareto-optimal candidates. To illustrate this behavior for D = 2, Figure 3 presents a representative trial (for n 20, 50, and 100), plotting true means (black circles), PO arms (red stars), and the final cover set B (blue circles). For example, in the right panel (n 100), although 8 of the 100 arms are Pareto-optimal,
11

---

Published in Transactions on Machine Learning Research (02/2026)
Table 1: Average Pareto-optimal set size, cover size B and runtime for exact and greedy set-cover subrou-
tines, All the instances are reported for T 10 rounds.
Exact set cover
Greedy set cover
72
D
Avg. true PO
[
Time (s)
B
Time (s)
20
3.2
0.0
3.2
0.0
20
7.2
4.8
0.1
4.9
0.0
20
5
14.2
12.6
0.6
12.7
0.0
50
2
4.8
2.6
0.0
2.6
0.0
50
3
10.5
6.0
0.2
6.1
0.0
50
5
18.2
11.2
6.1
11.5
0.1
100
2
5.6
2.2
0.0
2.2
0.0
100
3
14.1
7.2
4.95
7.5
0.0
100
5
26.7
15.1
29.0
15.7
0.2
the algorithm selects only 3 for pulling in the exploitation phase. By adding 2r to the empirical means of these three arms, the reduced cover set suffices to dominate all the other arms in the instance.
1.0
1.0
1.0
0.8
0.8
0.6
0.4
0.2
0.2
0.0
0.2
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(a) n = 20
(b) n 50
(c) n
100
Figure 3: Empiriaal reward distributions and selected cover sets for three problem sizes with D = 2. The axes represent the reward values each dimension. Black circles indicate the true mean rewards of arms, rod stars denote the PO arms, and blue circles highlight the arms selected by the algorithm form B.
7 Conclusion
This paper introduced a novel regret metric for multi-objective multi-armed bandits (MO-MAB) designed to overcome the limitations existing metrics by comprehensively accounting for all objectives simultaneously. We further defined the concept of efficient Pareto-optimal arms as those residing on the convex hull of the Parcto-optimal front Leveraging this metric, we proposod new algorithm proven to achieve sublincar regret for both Pareto-optinal and efficient Pareto-optimal arms in stochastic environments.
While this work presents the first algorithm rigorously evaluated under the proposed regret framework, analysis reveals limitations in its thcoretical regret bound and computational complexity. Future rescarch should prioritize developing algorithms that achieve lighter regret guarantees, potentially through alterna- tive algorithmic designs or refined analytical techniques. Moreover, the regret framework established here provides a formal foundation for extending the analysis the significantly more challenging sctting of adver- sarial MO-MAB, making the development of efficient algorithms robust to non-stochastic rewards critical and promising direction for advancement in multi-objective online decision-making.
12

---

Published in Transactions on Machine Learning Research (02/2026)
References
Cihan Ararat and Cem Tekin. Vector optimization with stochastic bandit feedback. In Proceedings of the International Conference on Artificial Intelligence and Stalistics (AISTATS), pp. 2165 2190, 2023.
Jon Louis Bentley, Hsiang- Tsung Kung, Michael Schkolnick, and Charles D. Thompson. On the average number of maxima in a set vectors and applications. Journal of the ACM, (4):53336 543, 1978.
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-objective bandits: Optimizing the generalized gini index. In Proceedings of the International Conference on Machine Learning (ICML), pp. 625 634, 2017.
Jiachong Cheng, Bo Xuc, Jing Yi, and Qingfu Zhang. Hicrarchize pareto dominance in multi-objective stochastic linear bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11489-11497, 2024.
Carlos A. Coello Coello. Evolutionary Algorithms for Solving Multi- Problems. Springer, New York, NY, USA, 2007.
Madalina M. Drugan and Ann Nowé. Designing multi-objective multi-armed bandits algorithms: A study. In Proceedings of the International Joint Conference on Neural Networks (IJCNN) pp. 1-8, 2013.
Madalina M. Drugan, Ann Nowé, and Bernard Manderick. Parelo upper confidence bounds algorithms: An empirical study. In Proceedings of the IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pp. 1 8, 2014.
Aurélien Garivier, Wouter M. Koolen, et al. Sequential learnnin of the pareto front for multi-objective bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3583 3591, 2024.
Arda Hüyükk and Cem Tekin. Multi-objective multi-armed bandit with lexicographically ordered and satis- ficing objectives. Machine Learning, 110(6):1233 1266, 2021.
Emre M. Karagözlü, Yigit C. Yildrrm, Cihan Ararat, and Cem Tekin. Learning the pareto set under incomplete preferences: Pure exploration in vector bandits. In Proceedings of the International Conference on Artificial Intelligence and Stafistics (AISTATS), pp. 3070-3078, 2024.
Shiliang Lu, Guojing Wang, Yifan Hu, and Lijun Zhang. Multi-objective generalized linear bandits. arXiv preprint arxi::1905. 12879, 2019.
Mehrdad Mahdavi, Tianbao Yang, and Rong Jin. Stochastic convex optimization with multiple objectives. In Advances in Neural Information Processing Systems (NewrIPS), volume 26, 2013.
Aleksandrs Slivkins. Introduction multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1-286, 2019.
Ece Turgay Duygu Öner, and Cem Tekin. Multi-objective contextual bandit problem with similarity infor- mation. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1673-1681, 2018
Vijay V. Vazirani. Approzimation Algorithms. Springer, Berlin, Germany, 2003.
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, and Christian Prins. Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. Europeas Journal of Operational Research, 231 (1):1-21, 2012.
Wei Wei, Ruijuan Yang, Haibo Gu, Wei Zhao, Chun Chen, and Shengwei Wan. Multi-objective optimiza- tion for resource allocation in vehicular cloud computing networks. IEEE Transactions on Intelligent Transportation Systems, 23(12):25536 255554 2021.
13

---

Published in Transactions on Machine Learning Research (02/2026)
Mengqi Xu and Diego Klabjan. Pareto regret analyses in multi-objective multi-armed bandit. In Proceedings of the International Conference on Machine Learning (TCML), pp. 19499-38511 2023.
Bo Xue, Xiaoyue Lin, Xin Zhang, and Qingfu Zhang. Multiobjective stochastic linear bandits under lexico- graphic ordering. arXiv preprint or XxXi:2301.XXXXX 2023.
Samer Q Yahyaa and Bernard Manderick. Thompson sampling for multi-objective multi-armed bandits problem. In Proceedings of the European Symposium on Artificial Neural Networks (ESANN), 2015.
Samer Q Yahyaa, Madalina M. Drugan, and Bernard Manderick. sanealing-pareess multi-objective multi- armed bandit algorithm. In Proceedings of the IEEE Symposium Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pp. 1 8, 2014.
Duygu Öner, Arda Karakurt, Arif Eryilmaz, and Cem Tekin. Combinatorial multi-objective multi-armed bandit problem. arXiv preprint Xiv: 8833 04039, 2018.
A Appendix
Theorem 1. The coverage-regret of algorithm R O (Tá(mlog7)))
Proof. Let a be an arm in A* The goal is constructing sequence of arms S fa')T= where af is pulled by the algorithms in rounds 1, .... such that
T Σ
T Era(a') 1=1
raa)
s so (T(((nlog))t) va e [D].
To construct S, we simply choose arm a" in the first T" rounds, and for the next rounds (t (t= tot we choose a* if it is not removed from B. Otherwise, we choose an arm E such that b 2r > a*.
For such sequence of arms, a" B, the regret will be zero. Thus, let's analyze the case of a" B, that is, there exists arm b B such that b b+ 2r 2 a".
We define the clean event Slivkins 2019
C = (1aa(a) ma(a)) Sr, Va E A, Ad (D), V (7])
where the confidence radius T Define the unclean event C as the complement of the clean event C. By the law total expectation,
B[R(T)] P[C]+ C P.C.
Applying Hoeffding's inequality and union bounds, the deviation of the average reward from the true expected reward can be bound as:
2nDT 2 P[C < TM
< T
We used the fact that n < T and D T. So, the term E[R(T) P[C is negligible. Thus, by the fact that P[C] < 1, we can focus only on the clean events, particularly, E
Since arm + 2r dominates a", and both arms and b are clean, write
pa(a") S (aa(b) + 2r, Ad E (D),
14

---

Published in Transactions on Machine Learning Research (02/2026)
and
u(aa) S ip(a") - r, and μ(6) S j(b) +r.
Thus,
2 2
p(a") (()) - 4r = 4V
T
Considering all T T" rounds, results in
2 2
2 log T
(
4T
T
T
By choosing T" T 8 lo + we have
E[R(T) < 47 T)
Finally,
B[R(T)] =
P(C
I 42 T) +T 2
= =
Theorem 2. The oulcome of Algorithm 7 converges to the PO arms A as T xc.
Proof. The outcome of Algorithm is the set B which remains unchanged after round T'. To prove this convergence property, we need to show that as the time horizon T approaches infinity, the probability of = A" approaches When T approaches infinity, T' = (2) (2log T) approaches infinity and consequently the confidence radius dominated by some other arms b+ 2r Rs in the second phase algorithm [ So, all the PO arms will appear in B. On the other hand, by approaching the confidence radius r zero, any non-PO arm at least must be dominated by some PO arm. As result, set B will be exactly all PO arms.
22ogTT approaches zero. Therefore, none of the PO solutions is
Lemma 1. In case of the clean event C happens, the optimal solution for the minimmum set covering of arms, computed in Step of Algorithm 1 is bounded by \A*).
Proof. Note that no PO arms are removed up to Step 9 in the algorithm. On the other hand, the union of PO arms dominates all other arms. When all arms are clean with radius r, the union of improved (by 2r) PO arms, also dominates all other arms, i.e., UarE4- Dom(a*)= A.
Therefore, the minimum covering of arms has at least one solution of size |A*). Consequently, the optimal solution is bounded by [A"].
Now let's prove the cumulative adjustment-regret bound for algorithm I
Theorem 3. The cumulative adjjsttment-regrel holds for algoritlm with the regret R = O (T' (7
15

---

Published in Transactions on Machine Learning Research (02/2026)
Proof. To prove this theorem, need to show that
Σ t= E'EA!
Σ
min {e 2 3a E A : at +ez a²}
s 1A (T'S log
Similar to Theorem | the probability of the unclean event P(C] is bounded by Z. Therefore, assume only the case where all arms are clean. For this case, we decompose the above right-hand term into two components to analyze them separately and derive the desired bounds.
Term 1 =
Σ
Σ a'E
min 3a" A tc
and
T
Term 2 E
Σ
Σ
minfe 20 =aa e A : deb
Based on the behavior of Algorithm
Term 0 3a* e +c
aEA
That is pulling all arms in A. So,
T Term 15 1
1m PEA
We now proceed to bound
T
Term 2 = E
Σ
minfe 20 E A' A :bbbbba)]
+1
where is the minimum set of arms such that every arm E A, including PO arms, weakly dominated by 6 + 2r for some b E B. If b is PO arm, then 0. Otherwise, we show that under these conditions, there always exists PO arm a" such that a' ž b and pa(a") (b))) s 4r for all d e [D]. Specifically, this a can be expressed as:
a" = argmin aEA- and a
max Ha(a) - (a(b). kE[D]
Assume, for contradiction, that there exists some E [D] such that pa(aa) pa(b) > 4r. Since both and a² are clean (Vd E [D] paa(a*)-Aua (a()) < and [pa(b) #a(b) < r), this implies E Dom((a)) but a" & Dom However, as the weak domination relation (>=) transitive, it follows that Dom(b) C Dom((*).
Given that B is the minimum set covering all arms:
If aa B, then & B, as including both would violate B is the minimum set cover.
If a" & B, there must exist some clean arm &' such that a" E Dom(t'). By transitivity, this implies b E Dom(('), again contradicting B the minimum set cover.
16

---

Published in Transactions on Machine Learning Research (02/2026)
Thus, both cases lead to contradictions, proving that pa(a") pa(b) I 4r for all d [D].
So, we can bound Term 2 as:
1
2 2log T
Term 2 s E
Σ
47 = (T TB)
T
This simplifies further to:
2 2log? T
Term <4T/BlV
T
Based on lemma
|B] S [A4). So, by replacing T = (7) (2log T) we obtain:
Term 2 250 (n
Finally,
Term + Term 2 |A+10 (má
While the main proof concludes here, note that the polynomial-time approximation for the minimum covering set satisfies [B] < logn |4%). Consequently, the polynomial-time algorithm achieves the regret bound of O (logn. Té (og T) while maintaining correctness.
Theorem 4. In Algorithm 1 if after computing the minimuum arm covering set B, the non-efficient arms are removed, Theorem Theorem and Theorem remain valid for the efficient PO arms, EAA".
Proof. An arm B identified and removed as non-efficient arm if a linear combination of other arms in B weakly dominates Specifically, in this case, there exists a subset B' B with m I arms and coefficients (a1, (2,, ..,................ such that E a; 1, where the artificial arm b, Ei= a,a, dominates The term 'artificial" reflects that individual arm has rewards identical to ba, but since Theorem ! and Theorem 3 discuss the expected value for the defined regret, the rewards of ba can be approximated for sufficiently large by selecting arm E B' with probability dg, Replacing with such an artificial arm 6, in
2logT Theorems and confirms their validity for the efficient PO arms, EAr.. For Theorem since r r= / converges T - co, removing non-efficient arms from B ensures only efficient PO arms remain in EAA..
]
17


Reviews:
[{"review_id": "yRKN2kwVzB", "reviewer": "Reviewer_hg41", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies stochastic multi-objective multi-armed bandits (MO-MAB), where each arm yields a vector-valued reward across multiple conflicting objectives. The learner must balance exploration and exploitation while accounting for trade-offs among objectives.\nMost prior MO-MAB work evaluates algorithms using the Pareto regret metric introduced by Drugan \\& Nowé (2013). The authors argue that this metric is fundamentally flawed because it measures distance to the Pareto front only in a single direction, and it results in an algorithm that achieves low regret that optimizes only one objective and fails to ensure diversity across the Pareto front.\nTherefore, the authors propose two new regrets: (1) coverage-regret, ensuring all Pareto-optimal arms are well approximated, and (2) cumulative adjustment-regret, penalizing selecting unnecessarily large arm sets.\nThe authors give an arm elimination-based algorithm and measure the regret in using these two new metrics and prove that the algorithm achieves regret $O(T^{2/3} (n \\log(T))^{1/3})$ in both metrics, where $n$ is the number of arms and $T$ is the time horizon.\nThe authors also provide empirical validation of their algorithm on synthetic experiments with Bernoulli rewards, showing that the greedy approximation yields cover sizes close to optimal, runtime scales favorably compared to exact set cover, and the exploitation phase focuses on a small subset of arms while preserving Pareto coverage.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors give a clear statement of the problem setting. However, the motivation for the two proposed regret definitions could be further clarified. For example, why are the coverage-regret property and cumulative adjustment-regret property necessary for a regret definition to be meaningful in the multi-objective MAB setting? The authors could provide more intuition on why these two properties are important.\nAdditionally, the proof of Theorem 1 contains a minor error in bounding $P[\\bar{C}]$. The authors should clarify this in the revision.", "audience_yn": "Yes", "audience_explanation": "Yes, this paper proposes an interesting topic in multi-objective multi-armed bandits. The proposed regret definitions and algorithm could be of interest to researchers working on multi-objective optimization and bandit problems.", "requested_changes": "The authors claim that the existing works do not consider optimizing in the Pareto front but often focusing on optimizing along a single objective direction.\n\nThe authors give two main properties of their proposed regret definition: coverage-regret property and cumulative adjustment-regret property. Could the authors please clarify how these two properties are necessary for a regret definition to be meaningful in the multi-objective MAB setting? For example, what if a regret definition only satisfies one of these properties but not the other? Would it still be meaningful?\n\nIn the proof of Theorem 1, $P[\\bar{C}]$ should be bounded by $\\frac{2n D T}{T'^4}$ instead of $\\frac{2n D T}{T^4}$ based on the choice of $r$ is $\\sqrt{\\frac{2 \\log(T)}{T'}}$. Could the authors please elaborate on this?\n\nSome typos to fix throughout the paper:\n\n1. In key contributions, the third bullet point is repeated twice. Please fix this.\n\n2. In related work, many citations are not in the correct format. For example, Yahyaa et al. Yahyaa et al. (2014) -> Yahyaa et al., 2014. Yahyaa and Manderick Yahyaa & Manderick (2015) -> Yahyaa and Manderick, 2015.\nPlease fix this throughout the paper.\n\n3. The grammar in many sentences needs to be improved. For example, in the statement of Theorem 1, \"The cumulative adjustment-regret is hold\" could be \"The cumulative adjustment-regret holds\". At the beginning of section 5, \"The following introduces the first MO-MAB algorithm with a sublinear regret bound\" could be \"We introduce the first MO-MAB algorithm with a sublinear regret bound\".\nPlease fix this throughout the paper.", "broader_impact_concerns": "The submission is theoretical in nature, focusing on regret definitions, algorithmic design, and analysis for stochastic multi-objective multi-armed bandits. This paper does not introduce immediate societal, ethical, or safety risks.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yXrMwbaqbV", "reviewer": "Reviewer_fWd1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper makes several distinct contributions to the field of Multi-Objective MAB:\n1. The authors propose a new, comprehensive regret framework consisting of \"Coverage-Regret\" and \"Cumulative Adjustment-Regret\". This framework aims to address the limitations of the existing Pareto regret metric.\n2. The paper introduces the concept of EPO arms, which are Pareto-optimal arms lying on the convex hull of the Pareto front. This concept is tailored for online optimization, leveraging the iterative nature of bandit problems to argue that mixtures of arms can dominate non-convex Pareto solutions.\n3. Algorithm design and analysis. The authors develop a two-phase \"explore-then-exploit\" algorithm with a theoretical regret guarantee of $O(T^{2/3}(n\\log T)^{1/3})$. It also proves that the algorithm's outcome converges to the Pareto-optimal set as the time horizon approaches infinity.\n\nStengths:\n1. The MO-MAB problem is interesting and practically relevant.\n2. The proposed metrics and methods are useful to some extend and overcome some challenges of the previous literature.\n3. The paper is relatively easy to follow.\n\nWeaknesses:\n1. The theoretical results are somewhat weak. The $T^{2/3}$-regret should not be optimal. An educated guess of the tight regret should be $\\sqrt{T}$ as the  $T^{2/3}$ regret does not depend on $D$. If this intuition is wrong, the regret dependence on $D$ is very interesting to see and understand.\n2. The numerical results do not include some informative comparative baselines. We do not see any results from the state-of-art MO-MAB algorithms.\n3. The motivating example in the revised version is fine but not perfect. The scenario described sounds more like a best arm identification problem instead of regret minimization problem. In practice, people usually have multiple configurations to test with the purpose to choose the one that is the best, and thus the regret in the testing periods may not be very important.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I think the paper is well organized and the results are clearly presented and supported, although there is some space to improve.", "audience_yn": "Yes", "audience_explanation": "MAB is one of the core topics in ML, and this paper lies naturally in the scope of TMLR. Besides, the paper is relevant to the part of TMLR's audience working on the theoretical foundations of multi-objective learning.", "requested_changes": "Following my comments about weakness above, there are several changes from my perspective which can make the paper better.\n\n1. The dependence of the regret results on dimension $D$. Particularly, I am curious about the case $D=1$ and its connection to the conventional MAB problem.\n2. Some comparison with some baseline algorithms in the literature can be helpful since the authors point out some of the disadvantages of the formulation of the paper in the literature.\n3. Polish the motivating example slightly better. The current version should be fine as well, but can be better. This is a very minor point.", "broader_impact_concerns": "I think the paper is fine with this part.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NbleTf05ad", "reviewer": "Reviewer_7NwK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a new framework for the problem of multi-objective multi-armed bandits, in which the agent is allowed to pull multiple arms at each round. The regret formulation goes beyond the traditional Pareto-optimality criterion and is instead defined with respect to a newly proposed notion of Efficient Pareto Optimality. Building on this framework, the authors further develop an algorithm that achieves sublinear regret.\n\nKey Strength:\n\n1. The proposed framework is highly innovative.\n\nKey Weaknesses:\n\n1. The proposed framework lacks a (relatively) clear practical motivation.\n\n2. The core idea of the algorithm largely follows the standard confidence-bound approach used in methods such as L/UCB. Although the authors show that the proposed algorithm achieves sublinear regret, the paper does not provide a tightness analysis (e.g., a corresponding lower bound). That said, given that this is the first work to introduce this new framework, this limitation is understandable.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I did not examine the proofs in full detail, but the techniques appear to follow the standard L/UCB methodology, and the overall seems sound.", "audience_yn": "Yes", "audience_explanation": "The proposed new framework of MO-MAB is quite promising.", "requested_changes": "1. On page 5, the phrase “for a sufficiently large number of rounds” is overly vague. This needs to be clarified. Since the primary contribution of the paper lies in the formulation of the new problem, the problem statement itself must be precisely written so that future researchers can accurately follow and build upon it.\n\n2. It is unclear why both Cumulative Adjustment-Regret and Coverage-Regret are discussed together in Section 4. This presentation makes it somewhat difficult to identify the main focus. Note that different regret notions in bandit problems often reflect conflicting objectives. For example, in the classical bandit setting, an algorithm that is optimal in terms of simple regret may not be optimal with respect to cumulative regret, and vice versa.\n\nTherefore, I suggest the following:\n(a) If the authors can show that the two regret notions are fundamentally equivalent—for instance, by proving that an algorithm optimal for one type of regret (or an adaptation of it) is also optimal for the another type of regret —then keeping both regret formulations in the same section is justified.\n\n(b) Otherwise, the main text should focus on a single regret notion, while the discussion of the other should be moved to the appendix as \"more discussion.\"\n\n3. It would be better to provide a practical example for the proposed framework.", "broader_impact_concerns": "N/A", "additional_comments": "Indeed, restricting attention solely to Pareto optimality is highly limiting. The research direction introduced by the authors—namely efficient Pareto optimality—is inherently meaningful. In particular, the illustrative example with three arms (i.e., (1,0),(0,1), (\\epsilon,\\epsilon)) is quite insightful.\n\nHowever, given that the technical contribution of the proposed algorithm is rather limited (as discussed in the “Summary of Contributions”), the primary value of this work lies in the introduction of the new framework itself. For this reason, it is essential to provide a practical example (even a relatively simple or stylized one) to better motivate and demonstrate the utility of the proposed framework.\n\nThat said, I would recommend acceptance of this paper once the practical example is clear.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)