- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies adversarial multi-objective bandits under Pareto regret. The authors establish a tight minimax regret rate of , showing that an easier coordinate does not necessarily reduce the worst-case regret when its identity is unknown. They further show that optimizing over any fixed coordinate is sufficient to achieve the optimal rate, using Poly-INF when is known and a reward-doubling variant when it is unknown. Numerical experiments on synthetic instances support the theoretical findings.
Critical strengths
- The paper provides a complete theoretical characterization of the studied problem. It establishes a matching lower bound and upper bound for the -parameterized minimax Pareto regret, yielding a tight rate of . The paper also considers both the setting where is known and where it is unknown, with the reward-doubling variant achieving the same minimax order. In this sense, the paper essentially (almost) closes a small and well-defined theoretical question.
- . The paper provides some new insights. It shows that identifying the easiest coordinate is not necessary for achieving the minimax-optimal rate.
- The paper contains good discussion and interpretation beyond the complex results. The authors frequently explain the intuition and limitations of the results rather than simply presenting theorem statements and proofs.
- I did not find (significant) overclaiming.
Critical weaknesses
My concerns are relatively minor:
- The paper builds on an existing adversarial multi-objective bandit setting and Pareto-regret formulation. The framework itself is not that new, and the specific problem considered is relatively narrow. This may limit the broader impact of the work, which is the main reason I lean toward weak accept rather than clear accept.
- The known- result directly uses the existing Poly-INF algorithm. The main new algorithmic component is the reward-doubling variant for the unknown- setting.
- The paper introduces a large amount of notations, such as , , , , and , which makes parts of the presentation hard to follow.
- No formal related-work section in the main paper.
- The tight lower bound is established for , while the cases remain open. (I view this as a minor technical limitation.)
- The characterization is tied to the specific -parameterized minimax formulation. It does not rule out other coordinate-dependent complexity measures that may give finer instance-dependent guarantees. (the authors also acknowledge this as a limitation)
- The main results assume an oblivious adversary. The paper suggests that an extension to adaptive adversaries may be possible, but this is not established in the current work.
Overall, the paper is quite complete, and I do not see any major weakness that would strongly support rejection.
Questions for authors
- At , knowing only the value can still lead to large regret, whereas knowing , the coordinate attaining , can substantially reduce it. Can the authors characterize, or discuss, the minimax rate when is known for general ?
- The paper suggests that an extension to adaptive adversaries may be possible. Which parts of the analysis fundamentally rely on obliviousness, and do the authors expect the reward-doubling argument to retain the same rate against an adaptive adversary?
- I suggest adding a formal related work section in the main text to make the positioning with respect to prior adversarial multi-objective bandit work clearer.
- Given the relatively dense notation, it would be helpful to include a notation table in the appendix.
5 comments
Response to Reviewer y3nS (2/3)
Novelty and broader impact (response to the comments on the framework)
We thank the reviewer for the constructive comments. This response corresponds to the first comment in the weakness section. We agree that our setting and Pareto-regret formulation build on Xu and Klabjan (2023), and would like to highlight the following novelty which we believe critical. In terms of the results, [1] establishes the horizon dependence of Pareto regret bounds without distinguishing among coordinates; yet it is known that horizon dependence can be overly pessimistic in adversarial bandits. While [1] identifies coordinate selection in algorithm design and coordinate dependence in regret analysis as open problems, our work addresses both. More deeply, [1] remarks that coordinates affect only the constant, while the regret order stays the same. In contrast, we show that a coordinate-level quantity enters the regret order itself. We also address some issues with the definition in [1] and remove the logarithmic factor in its upper bound. We have added Remark 4.8 at the end of Section 4.2 of the revised paper to highlight this comparison.
Our framework sits in an active literature on MO-MAB, with Pareto regret under stochastic rewards from Drugan and Nowé (2013), Turgay et al. (2018), Lu et al. (2019), and Guan and Xu (2026), other criteria from Busa-Fekete et al. (2017) and Hüyük and Tekin (2021), and a sequence-wise analogue in online convex optimization from Jiang et al. (2023). To the best of our knowledge, the minimax rate or the coordinate-dependent quantities of adversarial Pareto regret has remained open thus far, motivating this paper.
More broadly, we also see the broader impact in two directions, for practitioners and for related fields.
For practitioners, the result brings some insights. First, the difficulty of an adversarial multi-objective problem is set by the reward scale , the largest cumulative reward any arm attains on any objective, not by the horizon . When rewards are sparse, as with clicks or conversions, regret of order is attainable and the horizon-based is pessimistic. Second, no algorithm can improve the worst-case regret order over sequences with the same , even when its value is known (Theorem 3.2). In particular, knowing that some objective has a near-perfect arm does not improve the worst-case rate without knowing which objective it is. If nothing is known, reward-doubling Poly-INF on any fixed objective is worst-case optimal without knowing (Theorem 4.5), while knowing improves the upper-bound constant from 100 to 10 (Theorem 4.3).
We believe it also has several implications for related fields in the community. (a) The lower bound separates two kinds of side information, the value of a favorable parameter and the identity of the component that attains it, and shows that under adversarial rewards only the identity has worst-case value. Theorem A.5 together with Lemma A.4 gives the same separation under full information at , so it is a property of the vector criterion rather than of bandit feedback, and we expect it to appear in multi-objective online learning and in multi-task settings with a hidden easy component. (b) The additive-shift criterion of Eq. (3), which asks by how much one fixed comparator beats the learner on every coordinate, is bounded by the positive part of scalar regret, which signed expected-regret bounds do not control (Proposition A.10). The route we use, a tail bound integrated over the confidence level, works for any algorithm whose parameters do not depend on that level and whose deviation term is linear in (Lemma A.13). Hence, it is a general recipe for turning scalar high-probability guarantees into guarantees for such criteria. (c) The reward-doubling analysis shows that adapting to an unknown reward scale by restarting at data-dependent times need not cost a logarithmic factor (Appendix A.7.1). The argument does not use the multiple objectives, and we expect it to transfer to scalar first-order bounds with unknown scale, although we have not formally pursued this. (d) The -parameterized minimax value provides us a template for asking which other coordinate quantities govern multi-objective problems; Appendix A.9 takes a first step.
Response to Reviewer y3nS (3/3)
The use of Poly-INF (response to the comment on Poly-INF)
The known- policy uses the Poly-INF policy of Audibert and Bubeck (2010), while the reward-doubling variant is the main new algorithmic component. We believe this doubling technique may be useful in bandit problems with unknown parameters. Establishing the desired Pareto-regret rate also requires controlling the positive part of coordinate regret. Pareto regret is bounded by the positive part, (Lemma 4.1), and can be negative, because a switching learner can beat every fixed arm on one coordinate (Remark 4.2). The identity shows what a signed bound misses. The negative part is bounded by the switching term , which can exceed the minimax order (Lemma A.12, Proposition A.10). Lemma A.13 supplies the required bound by converting a high-probability guarantee into a bound on the positive part. The conversion is possible because of two properties of Poly-INF with known scale . Its parameters do not depend on the confidence level , so the same policy satisfies the bound of Audibert and Bubeck (2010, Theorem 18) for every , and its deviation term is linear in , so integrating over costs a constant rather than a logarithm. Combining this positive-part bound with Lemma 4.1 yields the Pareto-regret guarantee (Theorem 4.3). We have added Remark 4.7 at the end of Section 4.2 of the revised paper to highlight this point.
The cases and finer coordinate-dependent guarantees (response to the comments on and on other complexity measures)
We thank the reviewer for these two thoughtful remarks and agree with both.
On Weakness 5, we share the reviewer's view that this is a minor technical limitation. The upper bounds hold for every , and the lower bound requires (discussion after Theorem 4.6). Our construction for the lower bound analysis needs two arms per group (Lemma A.2) and two groups, and thus . These two cases would require a different construction. For , the rate itself can be smaller. For example, when , a simple elimination rule already attains constant Pareto regret. We leave their characterization to future work.
On Weakness 6, as the reviewer notes, we acknowledge this in the conclusion (Section 5). We hope this reflects our commitment to the genuine pursuit of science and to the research community. Through this communication, we also hope to inspire future work, as we believe the new perspective developed herein may contribute to meaningful follow-ups. For example, the minimax value in Eq. (6) considers the worst case over the class , so it opens up finer instance-dependent guarantees. Appendix A.9 provides initial thoughts in this direction through and (Corollary A.21).
Response to Reviewer y3nS (1/3)
Minimax rate when the minimizing coordinate is known (response to Question 1)
We thank the reviewer for the insightful question. For general L0, suppose the learner knows a coordinate d⋆ with Ld⋆=L0. Our results provide two upper bounds for this setting. Reward-doubling Poly-INF run on d⋆ achieves O(minU0,KU0), whereas GREEN-IX run on d⋆ achieves O(minU0,KL0log(KT)+Klog(KT)) (Corollary A.21). The former achieves the same order as the minimax rate in Theorem 4.6, whereas the latter depends on L0 rather than U0 in its learning term. Thus, knowing d⋆ allows us to obtain a potentially tighter upper bound when L0 is small. The lower bound in Theorem 3.2 relies on uncertainty about d⋆ and thus represents a worst-case analysis. When d⋆ is known, we cautiously conjecture that the minimax rate should resemble existing bounds for adversarial bandits, although a rigorous statement remains open.
Adaptive adversaries (response to Question 2 and the comment on oblivious adversaries)
We thank the reviewer for the insights. For the upper bounds, obliviousness enters in two places.
First, Theorem 4.3 relies on the high-probability bound for Poly-INF in Audibert and Bubeck (2010, Theorem 18), which assumes that rewards are fixed before play. We integrate this bound over confidence levels to control the expected positive part of coordinate regret in Lemma A.13 and derive the Pareto regret bound through Lemma 4.1. Second, in the proof for our reward-doubling version (Appendix A.7.1), obliviousness ensures that the comparator arm k⋆ and the cutoff epoch e⋆ are deterministic. This enables us to construct one stopped supermartingale to control the estimation errors across all epochs.
When the adversary is adaptive, we have a feeling that the two analyses can be extended as follows. For Theorem 4.3, Audibert and Bubeck (2010, Theorem 20) provide a Poly-INF guarantee against adaptive adversaries, yielding a regret bound of O(minU0,KU0logK) when L0 is known. For our reward-doubling version, however, both k⋆ and e⋆ may depend on the realized trajectory. If L⋆=L0 holds on every realized trajectory, we can replace e⋆ with the deterministic cutoff ⌊log2(1+U0/(81K))⌋. The pathwise epoch inequality remains valid, and a union bound over the K candidate comparators can control the estimation errors for the random best arm. This suggests that reward-doubling Poly-INF can achieve O(minU0,(KU0+K)logK) against adaptive adversaries. It seems open to us whether the logarithmic factor can be removed.
Lastly, we believe that the lower bound carries over, as oblivious adversaries might generally be easier to work with than adaptive ones.
Related-work section in the main text (response to Question 3 and the comment on related work)
We thank the reviewer for the suggestion. The related work is in Appendix A.1 and we should have pointed to it; we apologize for it. In the revision, we add a Related Work subsection to the Introduction (Section 1.1), condensed from Appendix A.1, which remains as the extended discussion.
Notation table (response to Question 4 and the comment on notation)
We thank the reviewer for the suggestion. We have added a notation table at the start of the appendix in the revised paper (both in the uploaded paper and in the global comment).