acceptodds
Under review as a conference paper at ICLR 2027

Taming Pareto Regret with Marginal Regret in Stochastic Multi-objective Bandits

Abstract

Stochastic multi-objective bandits generalize bandits to -dimensional reward vectors. Performance is commonly measured by Pareto regret, which sums the Pareto gaps of the selected arms, where each gap is the smallest uniform lift that makes the arm nondominated. As this measure is defined through the Pareto front, existing methods typically minimize it by estimating the front and thus inherit the difficulties of doing so. However, we find a direct link between Pareto regret and marginal regret in bandits that bypasses Pareto-front estimation. Beyond this, under regularity conditions, it even reaches the smaller scale of marginal regret. We formalize this idea through a width-guided method that maintains upper and lower confidence bounds for each arm and objective, races the top two arms within each objective, and commits once an objective has a strictly separated unique winner. For bounded i.i.d. instances with largest objective-wise suboptimality gap , the method achieves Pareto regret over horizon with arms, with no explicit multiplicative dependence on in the leading gap-dependent term. We further construct an explicit subclass on which every uniformly good policy incurs regret asymptotically, establishing optimality. Experiments on synthetic and real-world datasets support the theory. Across the data families, our method reduces Pareto regret by orders of magnitude relative to the baselines. Moreover, these results empirically expose what Pareto regret omits: Pareto front recovery and fairness remain distinct goals and call for further study.

Primary area:
learning theory
Keywords:
multi-objective bandits, Pareto regret, bandits

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TWnLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

this paper studies the problem on multi-objective bandits, under the popular pareto regret framework. specifically they study if pareto front estimation is necessary for pareto regret minimization, thereby to further understand what the right quantity is that the finite time regret scales with. the authors proposed a new algorithm called width guided and show an upper bound for pareto regret that scales with the largest objective wise suboptimality gap, as well as an asymptotic lower bound on Bernoulli cases. the authors further demonstrate the results via experiments on both of real world dataset and synthetic dataset.

Critical strengths
  1. the paper is very well written and structured, it is overall pleasant to read in llm era now. reference is well listed.
  2. the problem of the paper is surely a value problem in multi-objective bandits, what is the right quantity that the pareto regret scales with. the authors show that at least for a limited range of problem instances, the largest objective wise suboptimality gap can be a right one / better one compared to prior art. the authors further provide a matching lower bound, tho asymptotic.
  3. perhaps one of the most valuable parts is right after the main theorem, thm5, a clear discussion on the comparison with prior work and the range of instances where the result holds are presented well.
  4. experiment is comprehensive, with solid baselines included.
Critical weaknesses
  1. a minor presenting issue, there is no conclusion section in the main paper. tho I know that it is not mandatory, but it often helps reader have a takeaway and know the limitation. later on, I found the A.1 section in appendix, tho it is not called as conclusion, but it essentially plays the same role. perhaps the authors can consider having a small section of conclusion in the main paper so it wont be ignored easily compared with one in appendix and move part of the experiment content to the appendix.
  2. the lower bound is a bit weak, only holds for very limited class range, however it is not that rare in bandit area.
Questions for authors

while following theorem 5, the authors discussed the comparison with pareto ucb1 on when one is tighter than other. on the cases where the result of the paper is tighter than ucb1, it is not very immediate for me to tell if a meaningfully large range of instances can be covered. can the authors help here by making comments further?

3 comments
AuthorsOpenReview ↗

Response to Reviewer TWnL

Response to the question on the range of instances

We sincerely thank the reviewer for the positive assessment and for appreciating the value of our work. It is truly rewarding when our work is appreciated in its entirety. We also appreciate the insightful question. Our leading bound is smaller on a broad family of instances where one objective is well separated while dominated arms have small Pareto gaps, for any K≥2K\ge2 and d≥2d\ge2. We elaborate on the range of these instances through both the theoretical condition and experiments.

(a) The condition in theory. As in the paper, ΔaP\Delta_a^{\mathrm P} is the Pareto gap of arm aa and A⋆A^\star is the Pareto set. Suppose every dominated arm has positive Pareto gap, and let LT=log⁡(T(d∣A⋆∣)1/4)L_T=\log(T(d|A^\star|)^{1/4}). The leading upper bounds in Remark 6 satisfy

Pareto-UCB1 leading boundour leading bound=g†8K(∑a:ΔaP>01ΔaP)LTlog⁡T.\frac{\text{Pareto-UCB1 leading bound}} {\text{our leading bound}} = \frac{{g^\dagger}}{8K}\left(\sum_{a:\Delta_a^{\mathrm P} > 0} \frac1{\Delta_a^{\mathrm P}}\right)\frac{L_T}{\log T}.

Since LT≥log⁡TL_T\ge\log T, our leading bound is smaller whenever g†∑a:ΔaP>01/ΔaP>8K{g^\dagger}\sum_{a:\Delta_a^{\mathrm P} > 0} 1/\Delta_a^{\mathrm P} > 8K, and the advantage grows without limit as the Pareto gaps shrink with g†{g^\dagger} fixed. For example, if mm dominated arms have Pareto gaps at most δ\delta, this condition holds whenever δ<mg†/(8K)\delta < m{g^\dagger}/(8K). Importantly, g†{g^\dagger} can remain large while δ\delta becomes arbitrarily small and mm increases (and thus this condition becomes easier to meet). Thus, the favorable regime includes instances with one well-separated objective and even multiple dominated arms close to the Pareto front. The latter can be quite common and generally hard to distinguish, as doing so requires higher statistical complexity.

(b) Instances in the experiments. Beyond the theoretical bound, our algorithm shows a practical advantage over Pareto UCB1 across all experimental instances. The controlled study in Table 2 illustrates the range of favorable instances by varying both the Pareto gaps δ∈[0.01,0.12]\delta\in[0.01,0.12] and the number of near-front dominated arms m∈1,4,8,12m\in\\{1,4,8,12\\}, while keeping g†=0.55{g^\dagger}=0.55 fixed. At δ=0.02\delta=0.02, increasing mm from 1 to 12 increases the normalized Pareto-UCB1 coefficient from 30.45 to 142.08, exceeding the theoretical threshold of 64 when m=8m=8 and m=12m=12. Our algorithm achieves lower empirical Pareto regret in all eight settings, by factors of 5 to 40. The experiments in Table 1 further examine three different Pareto geometries in real-world data from Spotify (d=6d=6) and KuaiRec (d=26d=26), ranging from misleading near-front to friendly near-front and easy separated. Across all six groups, Pareto UCB1's measured Pareto regret is at least 379 times ours.

Response to the comments on a conclusion section

We thank the reviewer for the careful reading and kind words on the writing. Following the reviewer's suggestion, we have added a conclusion to the main text, drawn from Appendix A.1 and shown in blue in the revised paper. We also moved part of the experimental discussion on front coverage to Appendix A.4. The conclusion reads as follows.

“Conclusion. We studied stochastic multi-objective bandits under cumulative Pareto regret and showed that a strictly separated unique winner on any one objective certifies a Pareto-optimal arm and ends Pareto regret. Width-guided certification attains Pareto regret O(Klog⁡T/g†)O(K\log T/{g^\dagger}) for bounded i.i.d. instances with full-vector feedback whenever g†>0{g^\dagger} > 0, with no multiplicative dependence on dd in the leading term, and a matching asymptotic Ω(Klog⁡T/g†)\Omega(K\log T/{g^\dagger}) lower bound for uniformly good policies on an explicit subclass shows that this order cannot be improved. Appendix A.1 further discusses limitations and directions for future work.”

Response to the comment on the lower bound

We thank the reviewer for this observation. Proposition 4 establishes that the order Klog⁡T/g†K\log T/{g^\dagger} cannot be improved uniformly over the model class by uniformly good policies. This is a class-level lower bound, and it does not characterize instance-dependent optimality for general Pareto geometries. We acknowledge this limitation in Appendix A.1 and suggest developing instance-dependent lower bounds as a direction for future work.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal and Paper Revision

Dear reviewer TWnL,

Thank you very much for your feedback. We would be grateful to know whether our rebuttal has adequately addressed your concerns. We would be more than happy to answer any further questions if any.

AuthorsOpenReview ↗

Kind reminder: the discussion period closes soon

Dear Reviewer TWnL,

As the rebuttal period draws to a close, we sincerely thank you again for your feedback, which has helped us improve our work. We would be grateful for any final thoughts on whether our responses have addressed your concerns.

Reviewer_KD2tOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The authors study stochastic multi-objective bandits with KK arms and dd-dimensional bounded rewards. When at least one objective has a unique maximizer, they obtain an expected Pareto regret bound of O(Klog⁡T/g)O(K\log T/g), where gg is the largest gap between the best and second-best arms across objectives, with no explicit multiplicative dependence on dd in the leading term. They also establish a matching asymptotic lower bound of Ω(Klog⁡T/g)\Omega(K\log T/g). Finally, they provide experiments on synthetic and real-world datasets.

Critical strengths

As a main strength, I find the setting studied in the paper interesting and well motivated. In particular, many decision problems involve several objectives that may conflict, and the best choice for one objective may not be the best for another.

Furthermore, the authors establish both upper bound on Pareto regret for their method and a matching lower bound. These results return quite a complete characterisation of the problem.

Critical weaknesses

The main weakness is that the extent of the technical novelty is not entirely clear to me. The upper-bound analysis mainly uses standard confidence-bound arguments, and a similar reasoning can be applied to the lower bound, too. I think the authors should explain more clearly which parts of the algorithm and analysis introduce new ideas beyond these standard ingredients.

I also believe that the presentation could be a lot improved. For instance, the authors could better highlight contributions and explain better the techniques in the introduction while reducing the experimental part, which, in a theory paper, is completely minor.

Questions for authors

See Weaknesses.

5 comments
AuthorsOpenReview ↗

Response to Reviewer KD2t (1/2)

Response to the comment on technical novelty

We thank the reviewer for the comment.

We agree that our policy follows the UCB decision principle. In fact, motivated both by UCB's seminal success and by its elegant, explicit formula that offers a clear interpretation of the exploration–exploitation trade-off, the bandit community has developed many algorithms that adapt UCB, which is quite common. The key idea is to construct a decision criterion for each arm and then select arms based on that criterion. The main differences among these methods lie in how the decision criteria are constructed, and a wide variety of adaptations have been explored. Examples include LinUCB [2], Neural-UCB [3], and CUCB [4] in single-agent bandits, as well as UCB-ODC [1], Gossip-UCB [5], and DDUCB [6] in multi-agent bandits. Unique to this setting, we also invent new methodologies, as stated below, to make the legacy of UCB work herein.

The main technical novelty lies in the algorithmic design and the upper-bound analysis, complemented by a class-level lower bound.

First, a new layer of exploration and exploitation across objectives. The algorithm maintains a top-two race for each objective, with width Wj(t)W_j(t) given by the sum of the two confidence radii. Before certification, we can show that gj≤2Wj(t)g_j\le 2W_j(t) on the confidence event. Selecting the objective with the largest width explores the objective with the greatest uncertainty in its top-two comparison, while optimistically favoring objectives that could have larger suboptimality gaps. Once the empirical difference between the top two candidates exceeds their width, the corresponding objective certifies a unique winner and the algorithm commits. Within the selected objective, the algorithm samples the more uncertain arm. This creates a two-level exploration–exploitation mechanism across objectives and arms, without knowing the best-separated objective in advance.

Second, a certificate that ends Pareto regret. On the simultaneous-confidence event, Lemma 10 shows that certifying a unique winner on any one objective identifies a Pareto-optimal arm, making all subsequent Pareto regret zero. Thus, unlike existing methods that estimate the Pareto front which can be computationally expensive, our algorithm only needs to find the first objective-wise certificate.

Third, a new regret accounting for this allocation rule. We believe these regret analyses behind this new algorithm idea are novel and nontrivial. On the confidence event and after the warm start, each non-certifying pull incurs at most 4βAt(t)4\beta_{A_t}(t) Pareto regret (Lemma 11). Moreover, when g†>0{g^\dagger} > 0, the largest-gap objective maintains a width of at least g†/2{g^\dagger}/2 before certification. Our width-guided allocation therefore ensures that the sampled-arm radius is at least g†/4{g^\dagger}/4 (Lemma 12). Consequently, each arm has at most 32log⁡T/(g†)232\log T/({g^\dagger})^2 non-certifying pulls after the warm start. Charging each pull to its shrinking confidence radius, rather than a constant regret cost, gives

4∑a=1K∑s=1ma2log⁡Ts≤64Klog⁡Tg†,4\sum_{a=1}^K\sum_{s=1}^{m_a}\sqrt{\frac{2\log T}{s}} \le \frac{64K\log T}{{g^\dagger}},

where mam_a denotes the number of non-certifying pulls of arm aa after the warm start. This establishes the inverse-gap dependence without knowing the best-separated objective and without a multiplicative dd-factor (Theorem 5).

For the lower bound, we construct a duplicated-coordinate Bernoulli subclass where cumulative Pareto regret equals scalar regret and each pull reveals only one Bernoulli sample. Applying the classical bandit lower bound establishes that the order Klog⁡T/g†K\log T/{g^\dagger} cannot be improved uniformly over the full class by uniformly good policies (Proposition 4).

Thus, the novelty lies in using the pair width as a proxy for objective-wise separation, designing the corresponding certification and two-level allocation rules, and analyzing their interaction to attain the easiest-objective regret scale. We believe that this approach may also have implications for sequential decision problems with multiple layers of uncertainty. We have added a remark summarizing this technical novelty after the proof intuition in Section 4.2 of the revised paper.

[1] Chen, Yu-Zhen Janice, et al. "On-demand communication for asynchronous multi-agent bandits." AISTATS, 2023.

[2] Chu, Wei, et al. Contextual bandits with linear payoff functions. AISTATS, 2011.

[3] Zhou, Dongruo, et al. Neural contextual bandits with ucb-based exploration. ICML, 2020.

[4] Chen, Wei, et al. Combinatorial multi-armed bandit: General framework and applications. ICML, 2013.

[5] Zhu, Zhaowei, et al. Federated bandit: A gossiping approach. ACM SIGMETRICS, 2021.

[6] Martínez-Rubio, David, et al. Decentralized cooperative stochastic bandits. NeurIPS, 2019.

AuthorsOpenReview ↗

Response to Reviewer KD2t (2/2)

Response to the comment on presentation and experiments

We thank the reviewer for the suggestions. We have addressed them in the revised paper, with changes shown in blue.

(a) Contributions and techniques in the introduction. We added two sentences to the contribution paragraph on page 2. “This scale comes from the two-level mechanism together with a new regret accounting. On the confidence event, each pull made after the warm start and before the commitment is charged to the confidence radius of the sampled arm, and the objective that attains g†{g^\dagger} limits how many such pulls can occur.”

(b) Experiments. Following the reviewer's suggestion, we shortened the front-coverage discussion at lines 442–450, with the details retained in Appendix A.4. We retain Table 1 as an empirical complement to the theory, demonstrating the algorithm's practical performance across different Pareto geometries and objective dimensions. On the held-out Spotify and KuaiRec subsets, our algorithm achieves the lowest Pareto regret in all six reported groups, with improvements of approximately 111 to 591 times over the best competing method on Spotify and at least an order of magnitude in four of the six groups.

(c) Conclusion. We also added a short conclusion to the main text, summarizing the contributions and pointing to the limitations in Appendix A.1.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal and Paper Revision

Dear reviewer KD2t,

Thank you very much for your feedback. We would be grateful to know whether our rebuttal has adequately addressed your concerns. We would be more than happy to answer any further questions if any.

Reviewer_kn3oOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies cumulative Pareto regret in stochastic multi-objective bandits with full reward-vector feedback. It proposes an algorithm that compares the leading arms within each objective, samples according to confidence widths, and commits once it certifies a unique maximizer of any objective. The authors provide an upper bound for expected regret and a Bernoulli construction provides a matching asymptotic lower bound on a subclass.

Critical strengths
  • The paper answers an interesting, specific question: can an algorithm attain the best-separated coordinate’s gap scale without knowing that coordinate, under cumulative per-round Pareto regret? That is a meaningful result.
  • The paper shows that one objective’s unique winner suffices to stop accumulating Pareto regret. This provides a useful alternative to maintaining an optimistic Pareto front.
  • The “Proof Intuition” passage in Section 4.2 identifies the right mechanism. A reader can understand why uncertainty controls instantaneous regret and why the best-separated objective limits exploration.
Critical weaknesses
  • Novelty: Xu and Klabjan already relate their Pareto criterion to marginal regret and use a single-coordinate bandit algorithm in both stochastic and adversarial settings. Their Section 4.1 even suggests using an initial exploration period to choose a favorable coordinate. The regret definitions differ, so this does not establish the submitted result, but it makes the conceptual starting point less novel than the introduction suggests.
  • I would not describe the result as resolving a recognized open problem. Xu and Klabjan explicitly raise understanding dimension and Pareto-front-size dependence as future work, but for their different criterion.
  • Presentation: I suggest improving presentation by making more explicit the following: 1. Choosing a fixed coordinate already avoids front estimation. 2. The best coordinate is unknown. 3. Naive exploration can incur excessive regret. 4. The width rule controls that adaptation cost. That sequence would communicate the contribution more convincingly than repeated claims about bypassing Pareto geometry. A simple example demonstrating why a natural competing scheduling rule fails would also strengthen the explanation.
Questions for authors
  • How does the method compare with single-coordinate UCB and simple coordinate-selection baselines under matched tuning? What precisely is new beyond the coordinate-selection idea discussed by Xu and Klabjan?
5 comments
AuthorsOpenReview ↗

Response to Reviewer kn3o (1/3)

Response to the comments on novelty beyond Xu and Klabjan

We thank the reviewer for the comments. Both works rest on the link between Pareto regret and the regret of a single objective. However, there are three differences. The first is the regret definitions (Appendix A.2), as already acknowledged. The second is that their policy predetermines and fixes an arbitrary coordinate, while ours fixes no coordinate and commits to an arm once any objective certifies a unique winner. The third is the accompanying algorithms and analyses based on top-two sampling. As a result, we believe that these differences are exciting enough to constitute meaningful contributions, conveying our commitment to the genuine pursuit of science.

In Xu and Klabjan (2023), the coordinate is an input. Their Algorithm 1 takes a “Fixed dimension d′d',” which they remark could be specified “by running a burning period,” and then runs UCB along it. However, how to select a favorable coordinate and control the associated exploration cost is left unresolved in their work. This is important because the gap scales of two coordinates can differ by a factor of 1000 (lines 161–162). Choosing an unfavorable coordinate can lead to Pareto regret at the scale of the smallest positive objective-wise gap, rather than the largest gap g†{g^\dagger}. Following their suggestion directly leads to an explore-then-select baseline, whose exploration cost we discuss in our response to the question on comparison under matched tuning.

Our algorithm instead races the top-two arms of every objective and commits to an arm once any objective certifies a unique winner (line 90), at a data-dependent time. With high probability, the objective that certifies has a gap within a constant factor of g†{g^\dagger} (Lemma 13 in the revised paper), so the method does not have to identify the best coordinate. Moreover, its exploration is guided by the width of the objective-wise comparisons rather than by a predetermined exploration period.

This distinction also speaks to the technical contribution. Fixing one objective in advance also avoids estimating the Pareto front, but its regret bound follows the gap of the fixed objective, and finding the objective with the largest gap by an initial exploration can add regret of its own. On the simultaneous-confidence event and after the warm start, our width-guided allocation controls this cost through two properties: each non-certifying pull incurs at most 4βAt(t)4\beta_{A_t}(t) Pareto regret (Lemma 11), while the sampled-arm radius remains at least g†/4{g^\dagger}/4 before certification (Lemma 12). Together, they yield the O(Klog⁡T/g†)O(K\log T/{g^\dagger}) upper bound without knowing the best-separated coordinate.

Response to the comments on presentation

Thank you for the suggestion on presentation. We have clarified this in the introduction, which now states the following after line 90. “The commitment is to an arm, not to an objective. Fixing one objective in advance (Xu & Klabjan, 2023) also avoids estimating the Pareto front, but its regret bound follows the gap of the fixed objective, and finding the objective with the largest gap by an initial exploration can add regret of its own. Our algorithm fixes no objective. With high probability, the objective that separates first has a gap within a constant factor of g†{g^\dagger}.” We also reworded line 77, which now ends “by achieving the regret of the easiest one without knowing which it is.”

AuthorsOpenReview ↗

Response to Reviewer kn3o (2/3)

Response to the comment on a recognized open problem

We thank the reviewer for raising this point. The open question is how Pareto regret depends on the structure of the multi-objective problem and not only on the horizon TT. Xu and Klabjan (2023) raise it in their discussion of future work, where they write that “it is worth investigating the explicit relationship between the regret upper bound and both the dimension DD and the size of the Pareto optimal set ∣O∣|O|.” For cumulative Pareto regret in the stochastic setting, our result explicitly resolves both dependences. The leading term 64Klog⁡T/g†64K\log T/{g^\dagger} contains neither the dimension nor the size of the Pareto set, and it is logarithmic in the horizon TT (Theorem 5). No uniformly good policy improves this order over the class (Proposition 4). What governs the regret is g†{g^\dagger}, which characterizes the intrinsic structure of the multi-objective instance. In particular, our method achieves the regret scale of the easiest coordinate without knowing that coordinate in advance, which can substantially improve Pareto regret compared with choosing an arbitrary coordinate. We hope to convey this excitement. Their question is posed for a different regret criterion, as the reviewer notes. This is why our paper poses this specific research question at lines 60–67, while the abstract and Appendix A.1 present the contributions as a connection between cumulative Pareto regret and marginal regret, together with the corresponding upper and lower bounds (lines 16–25 and 662–667). Hence, in a rigorous sense, we hope to be faithful to the specific scope of the problem.

To make this clearer and avoid any ambiguity, we have reworded line 77 and added a remark clarifying the novelty of our paper and its distinctions from Xu and Klabjan (2023), as mentioned above.

AuthorsOpenReview ↗

Response to Reviewer kn3o (3/3)

Response to the question on comparison under matched tuning

We thank the reviewer for the question. In what follows, we compare the theoretical guarantees and numerical results under the same confidence radius βa(t)=2log⁡T/Na(t−1)\beta_a(t)=\sqrt{2\log T/N_a(t-1)} as in Algorithm 1. We have also added new experiments considering these baselines to the revised paper (Appendix A.3).

The key distinction is that single-coordinate UCB depends on the gap of the chosen coordinate, while our guarantee depends on the largest objective-wise gap without knowing that coordinate. An explore-then-select baseline can also incur an additional exploration cost.

(a) Single-coordinate UCB. Its Pareto regret is bounded by its marginal regret on the chosen coordinate jj (line 153), of order Klog⁡T/gjK\log T/g_j when gj>0g_j > 0. Our bound is of order Klog⁡T/g†K\log T/{g^\dagger} on every instance with g†>0{g^\dagger} > 0 (Theorem 5). These orders agree when gjg_j is comparable to g†{g^\dagger}, but can differ substantially when gjg_j is small.

For example, take two arms with deterministic rewards (1/2,1)(1/2,1) and (1/2−δ,0)(1/2-\delta,0). The objective-wise gaps are δ\delta and 11, respectively, and the second arm has Pareto gap δ\delta. For fixed 0<δ≤1/20 < \delta\le1/2 and sufficiently large TT, UCB on coordinate 1 incurs Pareto regret of order log⁡T/δ\log T/\delta, while our leading upper bound is 128log⁡T128\log T. At δ=10−3\delta=10^{-3}, the ratio of the standard leading UCB upper bound to ours is approximately 62.5. Thus, the choice of coordinate can substantially affect the regret guarantee, and blindly applying single-coordinate algorithms can still yield large regret, e.g., on the scale of the inverse of the smallest positive objective-wise suboptimality gap.

(b) Coordinate selection. Following the suggestion in Xu and Klabjan (2023), a natural baseline first explores the arms, selects a coordinate, and then runs UCB on it. To select a coordinate whose gap is at least a constant fraction of g†{g^\dagger} with probability at least 1−ε1-\varepsilon, an initial exploration with O(log⁡(Kd/ε)/(g†)2)O(\log(Kd/\varepsilon)/({g^\dagger})^2) pulls per arm suffices. However, this exploration length depends on the unknown g†{g^\dagger}, and the initial pulls themselves incur Pareto regret.

For example, consider three arms with means

μ1=(1/2+g,1/2+g2),μ2=(1/2,1/2),μ3=(0,0),\mu_1=(1/2+g,1/2+g^2),\qquad \mu_2=(1/2,1/2),\qquad \mu_3=(0,0),

where 0<g≤1/40 < g\le1/4. Here, g1=gg_1=g, g2=g2g_2=g^2, and g†=g{g^\dagger}=g, while arm 3 has Pareto gap 1/2+g21/2+g^2. Such an exploration period of order log⁡(Kd/ε)/g2\log(Kd/\varepsilon)/g^2 pulls per arm therefore incurs Pareto regret of the same inverse-square order from arm 3 alone.

In contrast, our algorithm does not require a predetermined exploration period. Its width-guided allocation simultaneously explores uncertain objective-wise comparisons and adapts toward a certificate, while Lemmas 11–12 establish the inverse-gap leading term 64Klog⁡T/g†64K\log T/{g^\dagger}. This is the additional guarantee provided by our method beyond the initial coordinate-selection suggestion.

(c) Numerical comparison. Single-coordinate UCB runs UCB on one fixed coordinate, and in this family coordinate 2 is the poorly separated one, with gap δ\delta. We ran it and an explore-then-select baseline on the synthetic family of Table 2, with the same confidence radius, horizon T=106T=10^6, and 20 runs. For single-coordinate UCB on coordinate 2 at δ=0.02\delta=0.02, the Pareto regret is 1030, 3392, 6516, and 9115 for m=1,4,8,12m=1,4,8,12, against 427, 377, 304, and 222 for our algorithm, which is 2.4 to 41 times larger. The explore-then-select baseline pulls every arm nn times, selects the coordinate with the largest empirical top-two gap, and then runs UCB on it. It has to fix nn before it knows the gaps. A conservative choice makes the confidence radius 2log⁡T/n\sqrt{2\log T/n} small compared with g†{g^\dagger}. A radius of g†/4{g^\dagger}/4 gives n=⌈32log⁡T/(g†)2⌉=1462n=\lceil 32\log T/({g^\dagger})^2\rceil=1462 pulls per arm here, which can be computed only if g†{g^\dagger} is known. With this length its Pareto regret is between 2105 and 5146 across the eight settings, which is 9.5 to 11.7 times ours, because every arm is explored nn times, including arms with large Pareto gaps. We also ran a version that needs no knowledge of g†{g^\dagger}. It explores all arms until the same confidence radius separates a unique winner on some coordinate, which takes about 360 pulls per arm, and then runs UCB on that coordinate. Its Pareto regret is between 524 and 1299, which is 2.4 to 3.0 times ours.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Summary of responses and revisions (1/2)

We sincerely appreciate all the reviewers for their valuable time and constructive comments. We are also grateful for the reviewers' acknowledgment of the interesting question the paper answers and its meaningful result, the well-motivated setting with matching upper and lower bounds that give quite a complete characterisation of the problem, and the clear writing with comprehensive experiments. In response to the comments and questions raised, we have posted our responses under each review block and uploaded the revised paper with changes marked in blue. Line numbers in all responses refer to the original submission. Below, we summarize our responses and the revisions. We are more than happy to answer any further questions.

Summary of responses.

(1) Novelty beyond Xu and Klabjan (2023). Both works build on the link between Pareto regret and single-objective regret, but differ in their regret definitions, algorithms, and analyses. Xu and Klabjan (2023) fix a coordinate and hypothetically suggest initial exploration to select a favorable one, without analyzing the associated exploration cost. This matters because an unfavorable coordinate can lead to substantially larger regret. Our algorithm instead adaptively races the top-two arms across objectives and commits once any objective certifies a unique winner. The key novelty lies in using the pair width as a proxy for the unknown objective-wise gap and developing a new regret analysis (Lemmas 11–12) that controls the adaptation cost, achieving O(Klog⁡T/g†)O(K\log T/{g^\dagger}) without knowing or explicitly identifying the best-separated coordinate.

(2) Recognized open problem. The open question is how Pareto regret depends on the structure of the multi-objective problem and not only on the horizon TT. Xu and Klabjan (2023) raise it in their discussion of future work, where they write that “it is worth investigating the explicit relationship between the regret upper bound and both the dimension DD and the size of the Pareto optimal set ∣O∣|O|.” For cumulative Pareto regret in the stochastic setting, our result explicitly resolves both dependences. The leading term 64Klog⁡T/g†64K\log T/{g^\dagger} contains neither the dimension nor the size of the Pareto set. It is logarithmic in the horizon TT and governed by g†{g^\dagger}, with a matching class-level lower bound. Their question is posed for a different regret criterion, which is why the paper states its own research question at lines 60–67. We also reworded line 77 and added a remark clarifying the novelty compared with Xu and Klabjan (2023).

(3) Comparison with coordinate baselines. Under the same confidence radius, the guarantee of single-coordinate UCB depends on the gap of the chosen coordinate, while ours depends on the largest objective-wise gap without knowing that coordinate. An explore-then-select baseline with a fixed exploration length needs a length that depends on the unknown g†{g^\dagger} and can pay an exploration cost that is inverse-square in g†{g^\dagger}, where our leading term is inverse. On the synthetic family of Table 2, the poorly separated coordinate costs up to 41 times our regret, and the two explore-then-select versions reported here cost 2.4 to 11.7 times.

(4) Technical novelty. The novelty lies in the algorithmic design and the upper-bound analysis, complemented by a class-level lower bound. The three ingredients are a new layer of exploration and exploitation across objectives, a certificate that ends Pareto regret (Lemma 10), and a new regret accounting for this allocation rule (Lemmas 11 and 12).

(5) Instances tighter than Pareto UCB1. Our leading bound is smaller whenever g†∑a:ΔaP>01/ΔaP>8K{g^\dagger}\sum_{a:\Delta_a^{\mathrm P} > 0}1/\Delta_a^{\mathrm P} > 8K, for any K≥2K\ge2 and d≥2d\ge2, which covers instances with one well-separated objective and dominated arms close to the Pareto front. Our algorithm also has lower measured Pareto regret than Pareto UCB1 in all eight settings of Table 2 and in all six real-data groups of Table 1.

(6) Lower bound. Proposition 4 shows that the order Klog⁡T/g†K\log T/{g^\dagger} cannot be improved uniformly over the model class by uniformly good policies. It is a class-level lower bound, as Appendix A.1 states.

(7) Presentation, experiments, and conclusion. In the introduction we state that the commitment is to an arm, not to an objective, and that the scale comes from the two-level mechanism together with a new regret accounting. We shortened the front-coverage discussion while keeping Table 1 as an empirical complement to the theory, and we added a conclusion to the main text.

AuthorsOpenReview ↗

Summary of responses and revisions (2/2)

Summary of revisions. The revision is confined to the six items below. Existing section, theorem, and appendix numbers stay the same, and the main text is ten pages, within the limit for the discussion phase.

(R1) Introduction (pp. 2–3). Line 77 now ends “by achieving the regret of the easiest one without knowing which it is.” Four sentences after line 90 begin “The commitment is to an arm, not to an objective.” Two sentences in the contribution paragraph (lines 92–98) begin “This scale comes from the two-level mechanism together with a new regret accounting.” The rounded factor at line 103 is written as at least 110.

(R2) Two remarks on novelty (Section 3, p. 5, and Section 4.2, p. 7). The remark after Remark 3 summarizes the novelty compared to Xu and Klabjan (2023), and the remark after the proof intuition summarizes the technical novelty. Both are unnumbered, so the existing numbers are unchanged.

(R3) Front-coverage discussion (lines 442–450, and Appendix A.4 on p. 18). The paragraph is shortened, with its details kept in Appendix A.4.

(R4) Conclusion (new Section 6 on p. 10). It is drawn from Appendix A.1, which remains as the extended discussion.

(R5) Coordinate baselines (Appendix A.3, p. 15). One paragraph reports single-coordinate UCB and explore-then-select on the synthetic family of Table 2.

(R6) New lemma (Appendix A.5, p. 20). Lemma 13 shows that, with high probability, the objective that certifies has a gap within a constant factor of g†{g^\dagger}. It is placed after Lemma 12, so the existing numbers are unchanged.

AuthorsOpenReview ↗

Gentle reminder before the discussion period ends

Dear Reviewers,

We greatly appreciate the time and care you have put into reviewing our submission. With the discussion period ending shortly, we would like to let you know that our responses and the revised paper (with changes highlighted in blue) were posted on November 13.

Please let us know whether our responses address your concerns. We would be glad to clarify anything that remains unclear. If your concerns have been resolved, we would be thankful if you could consider reflecting this in your assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.