acceptodds
Under review as a conference paper at ICLR 2027

The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

Abstract

Adversarial multi-objective bandits help us optimize choices (arms) whose reward is a multidimensional vector chosen by an adversary and whose performance is measured by Pareto regret. We define loss as one minus reward and measure the easiness of a coordinate by the smallest cumulative loss of the arms on it, and call the coordinate easier when this quantity is smaller. Existing work suggests that in theory an easier coordinate may reduce Pareto regret. However, in practice, one may not know which coordinate is easier. On the negative side, we show that this lack of information eliminates the possibility: a smaller cumulative loss does not improve the worst-case order of Pareto regret. Precisely, let \(L_d\) be the smallest cumulative loss along coordinate over rounds. For \(K\ge4\) arms, \(T\ge6\) rounds, and at least 2 coordinates, we prove that the minimax expected Pareto regret is \(\Omega(\min{T-L_0,K(T-L_0)})\) where \(L_0=\min_d L_d\). It is monotonically decreasing in \(L_0\), even when is known. On the positive side, it motivates that other coordinates may suffice to attain the optimal rate. When is known, we apply Poly-INF to a fixed coordinate and obtain an upper bound on Pareto regret that exhibits the same order and thus matches the lower bound. Without such knowledge, we create reward-doubling Poly-INF that adapts to this unknown quantity while still attaining the matching minimax rate. Another implication is that it has no extra \(\log T\) factor and is independent of the number or choice of coordinates, but only with a deliberate policy along the chosen coordinate.

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

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_y3nSOpenReview ↗
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 Θ(min⁡{T−L0,K(T−L0)})\Theta(\min\{T-L_0,\sqrt{K(T-L_0)}\}), 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 L0L_0 is known and a reward-doubling variant when it is unknown. Numerical experiments on synthetic instances support the theoretical findings.

Critical strengths
  1. The paper provides a complete theoretical characterization of the studied problem. It establishes a matching lower bound and upper bound for the L0L_0-parameterized minimax Pareto regret, yielding a tight rate of Θ(min⁡{T−L0,K(T−L0)})\Theta(\min\{T-L_0,\sqrt{K(T-L_0)}\}). The paper also considers both the setting where L0L_0 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.
  2. . The paper provides some new insights. It shows that identifying the easiest coordinate is not necessary for achieving the minimax-optimal rate.
  3. 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.
  4. I did not find (significant) overclaiming.
Critical weaknesses

My concerns are relatively minor:

  1. 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.
  2. The known-L0L_0 result directly uses the existing Poly-INF algorithm. The main new algorithmic component is the reward-doubling variant for the unknown-L0L_0 setting.
  3. The paper introduces a large amount of notations, such as LdL_d, L⋆L^\star, L0L_0, UdU_d, and U0U_0, which makes parts of the presentation hard to follow.
  4. No formal related-work section in the main paper.
  5. The tight lower bound is established for K≥4K\ge 4, while the cases K=2,3K=2,3 remain open. (I view this as a minor technical limitation.)
  6. The characterization is tied to the specific L0L_0-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)
  7. 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
  1. At L0=0L_0=0, knowing only the value L0L_0 can still lead to large regret, whereas knowing d⋆d^\star, the coordinate attaining L0L_0, can substantially reduce it. Can the authors characterize, or discuss, the minimax rate when d⋆d^\star is known for general L0L_0?
  2. 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?
  3. 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.
  4. Given the relatively dense notation, it would be helpful to include a notation table in the appendix.
5 comments
AuthorsOpenReview ↗

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 L0L_0, suppose the learner knows a coordinate d⋆d^\star with Ld⋆=L0L_{d^\star}=L_0. Our results provide two upper bounds for this setting. Reward-doubling Poly-INF run on d⋆d^\star achieves O(min⁡U0,KU0)O(\min\\{U_0,\sqrt{KU_0}\\}), whereas GREEN-IX run on d⋆d^\star achieves O(min⁡U0,KL0log⁡(KT)+Klog⁡(KT))O(\min\\{U_0,\sqrt{KL_0\log(KT)}+K\log(KT)\\}) (Corollary A.21). The former achieves the same order as the minimax rate in Theorem 4.6, whereas the latter depends on L0L_0 rather than U0U_0 in its learning term. Thus, knowing d⋆d^\star allows us to obtain a potentially tighter upper bound when L0L_0 is small. The lower bound in Theorem 3.2 relies on uncertainty about d⋆d^\star and thus represents a worst-case analysis. When d⋆d^\star 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⋆k^\star and the cutoff epoch e⋆e^\star 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(min⁡U0,KU0log⁡K)O(\min\\{U_0,\sqrt{KU_0\log K}\\}) when L0L_0 is known. For our reward-doubling version, however, both k⋆k^\star and e⋆e^\star may depend on the realized trajectory. If L⋆=L0L^\star=L_0 holds on every realized trajectory, we can replace e⋆e^\star with the deterministic cutoff ⌊log⁡2(1+U0/(81K))⌋\lfloor\log_2(1+U_0/(81K))\rfloor. The pathwise epoch inequality remains valid, and a union bound over the KK candidate comparators can control the estimation errors for the random best arm. This suggests that reward-doubling Poly-INF can achieve O(min⁡U0,(KU0+K)log⁡K)O(\min\\{U_0,(\sqrt{KU_0}+K)\log K\\}) 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).

AuthorsOpenReview ↗

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 U0=T−L0U_0=T-L_0, the largest cumulative reward any arm attains on any objective, not by the horizon TT. When rewards are sparse, as with clicks or conversions, regret of order KU0\sqrt{KU_0} is attainable and the horizon-based KT\sqrt{KT} is pessimistic. Second, no algorithm can improve the worst-case regret order over sequences with the same L0L_0, 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 L0L_0 (Theorem 4.5), while knowing L0L_0 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 L0=0L_0=0, 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 log⁡(1/δ)\log(1/\delta) (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 L0L_0-parameterized minimax value provides us a template for asking which other coordinate quantities govern multi-objective problems; Appendix A.9 takes a first step.

AuthorsOpenReview ↗

Response to Reviewer y3nS (3/3)

The use of Poly-INF (response to the comment on Poly-INF)

The known-L0L_0 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, RTfs≤[RTd′]+R_T^{\mathrm{fs}}\le[R_T^{d'}]_+ (Lemma 4.1), and RTd′R_T^{d'} can be negative, because a switching learner can beat every fixed arm on one coordinate (Remark 4.2). The identity [R]+=R+[−R]+[R]_+=R+[-R]_+ shows what a signed bound misses. The negative part is bounded by the switching term Sd′=∑tmax⁡ird′i,t−Ud′S_{d'}=\sum_t\max_i r_{d'}^{i,t}-U_{d'}, which can exceed the minimax order min⁡U0,KU0\min\\{U_0,\sqrt{KU_0}\\} (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 B=U0B=U_0. Its parameters do not depend on the confidence level δ\delta, so the same policy satisfies the bound P(Rn>4.5,Gn⋆K/B+4KB+2KBlog⁡(1/δ))≤δ\mathbb P\big(R_n > 4.5\\,G_n^\star\sqrt{K/B}+4\sqrt{KB}+\sqrt{2KB}\log(1/\delta)\big)\le\delta of Audibert and Bubeck (2010, Theorem 18) for every δ\delta, and its deviation term 2KBlog⁡(1/δ)\sqrt{2KB}\log(1/\delta) is linear in log⁡(1/δ)\log(1/\delta), so integrating over δ\delta costs a constant rather than a logarithm. Combining this positive-part bound with Lemma 4.1 yields the Pareto-regret guarantee E[RTfs]≤10min⁡U0,KU0\mathbb E[R_T^{\mathrm{fs}}]\le10\min\\{U_0,\sqrt{KU_0}\\} (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 K∈2,3K\in\\{2,3\\} and finer coordinate-dependent guarantees (response to the comments on K∈2,3K\in\\{2,3\\} 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 K≥2K\ge2, and the lower bound requires K≥4K\ge4 (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 K≥4K \geq 4. These two cases would require a different construction. For K=2K=2, the rate itself can be smaller. For example, when L0=0L_0=0, 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 L⋆=L0L^\star=L_0, so it opens up finer instance-dependent guarantees. Appendix A.9 provides initial thoughts in this direction through UdU_d and LdL_d (Corollary A.21).

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

This paper considers multi-objective bandits problems and in particular, the authors focus on providing impacts of coordinates in adversarial multi-objective bandits.

The authors showed several aspects of coordinates in the context of Pareto regret optimization. The most important role is the coordinate-level quantity is reflected in the minimum coordinate loss L0L_0. It has an important role in coordinate regret and governs the best admissible coordinate regret.

The authors showed a lower bound on Pareto regret , and it is is monotonically decreasing in L0L_0, resulting in an instance-dependency through L0L_0.

The authors proposed an algorithm to achieve the above rate uniformly, proving both tightness and optimality for every L0L_0 and over instances in the minimax sense. Authors also showed that the limited impact of the coordinate dimension (D) and coordinate choice (d).

Note that the claimed results may be limited to specific intrinsic quantities and do not exclude the possibility that there may be other quantities that are also related to coordinates and affect Pareto regret.

Critical strengths

The critical strength is in exposing the role of L0L_0 and its impact , and in proposing an algorithm to achieve the rate uniformly, as well as in proving both tightness and optimality for every L0L_0.

Overall, the paper is quite technical.

Critical weaknesses

The claimed results may be limited to specific intrinsic quantities and do not exclude the possibility that there may be other quantities that are also related to coordinates and affect Pareto regret.

So I am not sure how "general" is the claimed result.

Questions for authors

The results seem quite limited. Can the authors provide guidelines or alternate algorithms to overcome this restrictions?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 4cdA

Generality of the results and guidance for practice (response to the comment on generality and the question on guidelines)

We thank the reviewer for raising this question. We would like to first highlight the generality of the results and then discuss the scope/restrictions of these results. Our results establish that L0L_0 determines the minimax rate over the class of reward sequences satisfying L⋆=L0L^\star=L_0. Specifically, Theorem 4.6 shows that VK,D,T(L0)=Θ(min⁡U0,KU0),\mathcal V_{K,D,T}(L_0) =\Theta(\min\\{U_0,\sqrt{KU_0}\\}), where U0=T−L0U_0=T-L_0. To our knowledge, this is the first result that characterizes the dependence of minimax Pareto regret on an intrinsic coordinate-level quantity, instead of only the number of arms KK and the horizon TT. It is general in the sense that it applies to all oblivious adversarial MO-MABs, which is a broad class of problems where reward vectors can take arbitrary bounded values. The matching lower bounds further proves the tight rate. It also offers a new perspective on tackling Pareto regret in adversarial MO-MAB. In general, this problem can be challenging to analyze and optimize because, unlike in stochastic settings, rewards need not be stationary, and Pareto regret depends on the relationships among multiple reward coordinates through Pareto dominance. Our results provide a new route and thus a new algorithmic perspective: we can focus on a single coordinate and use an appropriately designed adversarial bandit algorithm to attain the minimax rate. This avoids directly optimizing multiple objectives or identifying the Pareto front, which is almost hopeless in the adversarial setting. Surprisingly, the learner does not even need to identify the coordinate attaining L0L_0, as any fixed coordinate suffices (Theorem 4.5). More broadly, this new route makes the problem more tractable by allowing us to connect to seminal adversarial bandits.

Beyond these technical strengths, which the reviewer kindly notes, the result brings some insights to a practitioner. In applications with sparse rewards, such as clicks or conversions, the U0U_0-dependent regret guarantee can be substantially tighter than horizon-dependent bounds. Moreover, the choice of coordinate and algorithm can be made jointly to exploit more specific information. Reward-doubling Poly-INF run on coordinate dd achieves O(min⁡Ud,KUd)O(\min\\{U_d,\sqrt{KU_d}\\}), whereas GREEN-IX achieves O(min⁡Ud,KLdlog⁡(KT)+Klog⁡(KT))O(\min\\{U_d,\sqrt{KL_d\log(KT)}+K\log(KT)\\}) (Corollary A.21). Thus, when a coordinate is expected to have rare successes, reward-doubling Poly-INF can exploit its small UdU_d. When a coordinate is expected to have a consistently good arm, GREEN-IX can exploit its small LdL_d. For policies such as Tsallis-INF, EXP3++, and MO-US, our analysis identifies another coordinate-dependent quantity, SdS_d, that affects the resulting bounds (Proposition A.10).

Regarding the reviewer's reference to “restrictions,” our understanding is that it concerns the focus of our characterization on the coordinate-level quantity L0L_0. We would appreciate the reviewer's clarification if a different restriction was intended. We agree that other coordinate-dependent quantities may also affect Pareto regret. Based on our new perspective, one could ask different questions about the roles of coordinates. For example, our results already suggest LdL_d and SdS_d as additional coordinate-dependent quantities (Corollary A.21 and Proposition A.10). One could further investigate whether these or newly defined quantities yield sharper minimax rates. Our reduction in Lemma 4.1 also provides a possible approach to studying these quantities by relating Pareto regret to regret on individual coordinates. If preference weights over objectives are known, Lemma 4.1 also allows us to operate on a weighted average of coordinates. We intentionally add this statement of scope, in the hope of being faithful to scientific rigor and to inspire future efforts. We believe these directions are nontrivial and could themselves deserve multiple works.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal and Paper Revision

Dear Reviewer 4cdA,

Thank you very much for your feedback. We truly appreciate your time and would be grateful to hear whether our rebuttal and revision of the paper have 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 4cdA,

With the rebuttal period nearing its end, we would like to thank you once more for your feedback and engagement, which have helped us strengthen our work. We would greatly appreciate any final thoughts on whether our responses have addressed your concerns.

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

This paper studies adversarial multi-objective bandits under Pareto regret. Its main contribution is to show that an easy coordinate, one on which some arm incurs small cumulative loss, does not reduce worst-case Pareto regret when the learner does not know which coordinate it is. Furthermore, the paper shows that running Poly-INF on any fixed coordinate attains the matching optimal rate, and it gives a reward-doubling variant that achieves the same rate when the minimum coordinate loss L0L_0 is unknown. Together these yield a tight minimax rate that removes a log factor from previous works.

Critical strengths
  1. The paper gives a tight minimax regret in terms of the minimum coordinate loss, with matching upper and lower bounds that remove a logarithmic factor from prior work.
  2. To my knowledge, the lower-bound construction is new: an initial phase with complementary rewards makes the two cases indistinguishable, and a single hidden arm is then made to lead on both coordinates. This cleanly separates knowing the value of the easiest coordinate’s loss from knowing which coordinate it is.
Critical weaknesses
  1. The main weakness is limited contribution: the only substantively new result is the lower bound. The matching upper bounds follow directly from combining the single-coordinate reduction of [1] with the known gain-based guarantee of Poly-INF [2].

  2. Corollary 3.3 is false as stated. If the reward sequence is fixed and only coordinates are permuted, always playing the arm with the largest coordinate-sum of cumulative rewards yields zero Pareto regret on every permutation. The proof actually uses the larger class of sequences whose multiset of coordinate losses equals λ(L0)\lambda(L_0), so the definition, the statement, and the accompanying discussion in the main paper should be aligned with the one in the appendix.

  3. The paper is hard to follow. There are so many symbols that are used only briefly. Some symbols are reused with different meanings across sections (e.g., B, V, h), others are used without definition.. Streamlining the notation would considerably improve readability.

[1] Pareto regret analyses in multi-objective multi-armed bandit.

[2] Regret Bounds and Minimax Policies under Partial Monitoring

Questions for authors

See weakness

4 comments
AuthorsOpenReview ↗

Response to Reviewer PJq7 (1/2)

Technical novelty (response to the comment on contribution)

We thank the reviewer for the comment. 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 selecting coordinates in the algorithmic sense or establishing dependence on coordinates in the analysis as an open problem, our work settles this debate. 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 actually enters the order itself. Together with the lower bound, we establish the minimax rate Θ(min⁡U0,KU0)\Theta(\min\\{U_0,\sqrt{KU_0}\\}) for every L0L_0, where U0=T−L0U_0=T-L_0, and this dependence on U0U_0 can yield a bound much smaller than the horizon-dependent T\sqrt{T} rate of [1]. This rate is independent of the number of coordinates and can be attained by optimizing along any coordinate, without identifying the coordinate attaining L0L_0. We also address some issues with the definition in [1] and remove the logarithmic factor in its upper bound.

Analytically, when L0L_0 is known, we use Poly-INF from [2] to establish the matching Pareto regret bound in Theorem 4.3. Compared with [1], which derives its expected Pareto regret upper bounds through a reduction to expected regret on a single coordinate, our nonnegative Pareto regret satisfies RTfs≤[RTd′]+R_T^{\mathrm{fs}}\le[R_T^{d'}]_+ (Lemma 4.1). Since RTd′R_T^{d'} can be negative when a switching learner outperforms every fixed arm (Remark 4.2), an expected signed-regret bound alone is insufficient. Indeed, converting such a bound introduces a switching term Sd′=∑tmax⁡ird′i,t−Ud′S_{d'}=\sum_t\max_i r_{d'}^{i,t}-U_{d'}, which can exceed the minimax order (Lemma A.12, Proposition A.10). We instead use the high-probability guarantee of [2, Theorem 18]. Its parameters do not depend on the confidence level δ\delta, and its deviation term is linear in log⁡(1/δ)\log(1/\delta), allowing us to integrate the tail bound and control the expected positive part without an additional logarithmic factor (Lemma A.13). Together with the deterministic bound for small U0U_0, this gives E[RTfs]≤10min⁡U0,KU0\mathbb E[R_T^{\mathrm{fs}}] \le 10\min\\{U_0,\sqrt{KU_0}\\} (Theorem 4.3). Together with our lower bound, this establishes the tight dependence on L0L_0 and removes the logarithmic factor in [1].

Second, when L0L_0 is unknown, directly applying [2, Theorem 18] with the available scale B=TB=T gives KT\sqrt{KT} instead of KU0\sqrt{KU_0} (Table 1). We develop Algorithm 5, reward-doubling Poly-INF, which runs Poly-INF with scale Be=81K⋅2eB_e=81K\cdot2^e and restarts with the doubled scale whenever the collected reward in the current epoch reaches BeB_e. Meanwhile, [2] provides a regret guarantee over a fixed number of rounds. In Algorithm 5, however, each epoch ends when the learner's collected reward reaches a threshold. In other words, its length is itself random, as it depends on the learner's random actions and observations. Consequently, [2] cannot be applied directly to each randomly terminated epoch, and a union bound over all possible ending times would introduce an additional logarithmic factor.

Appendix A.7.1 develops a novel analysis to overcome this difficulty. We measure every epoch against the same comparator arm k⋆k^\star, so that the epoch regrets add up exactly to RTd′R_T^{d'} (Eq. (28)). We then show that whenever RTd′>0R_T^{d'} > 0, the last epoch index is bounded by the deterministic index e⋆=⌊log⁡2(1+Ud′/(81K))⌋e^\star=\lfloor\log_2(1+U_{d'}/(81K))\rfloor, with Be⋆≤Ud′+81KB_{e^\star}\le U_{d'}+81K (Eq. (31)). Building on a pathwise inequality from [2], we establish an epoch regret bound (Lemma A.16) and control the estimation errors across all epochs up to e⋆e^\star through one stopped supermartingale (Lemmas A.17--A.18), avoiding a union bound over restart times. This yields the high-probability positive-regret bound in Lemma A.15, which, after integration and combination with the deterministic bound, establishes E[RTfs]≤100min⁡U0,KU0\mathbb E[R_T^{\mathrm{fs}}] \le 100\min\\{U_0,\sqrt{KU_0}\\} (Theorem 4.5).

We have added Remarks 4.7 and 4.8 at the end of Section 4.2 of the revised paper to highlight these points. We hope the above could effectively communicate the contributions of this paper.

AuthorsOpenReview ↗

Response to Reviewer PJq7 (2/2)

Corollary 3.3 and the permutation class (response to the comment on Corollary 3.3)

We thank the reviewer for pointing this out. We apologize for the confusion and clarify that it arises from an ambiguity in the wording. The permutation in Corollary 3.3 is meant to act on the coordinate losses of rr, not on the reward sequence itself, as the paper indicates in several places. The class is introduced in Section 2.2 as the case where “all coordinate losses are fixed, but the learner does not know which value corresponds to which coordinate.” The discussion after Corollary 3.3 further concludes that “uncertainty about which coordinate attains L0L_0 is sufficient for the rate.” Appendix A.1.3 presents the corollary as preserving the rate “for an explicit family of prescribed unordered coordinate-loss profiles.” Appendix A.3.5 proves the result for the unordered loss profile λ(L0)=(L0,(T+L0)/2,…,(T+L0)/2)\lambda(L_0)=(L_0,(T+L_0)/2,\dots,(T+L_0)/2), with the matching upper bound from Theorem 4.3.

For the intended interpretation of C(r)\mathcal C(r), the result proved in Appendix A.3.5, its proof, and its constant remain valid. Therefore, to the best of our knowledge, we believe that there is no technical issue.

To avoid the ambiguity, we make the following minimal changes. These involve changing only a few words in three sentences, while the technical content, including the proof, the constant, and the derivation of Theorem 4.6 in Appendix A.8, stays the same. Specifically, (i) In the definition of C(r)\mathcal C(r) in Section 2.2, “all reward sequences obtained by permuting the coordinates of the same reward sequence rr” becomes “all reward sequences whose coordinate losses are a permutation of those of rr.” (ii) In Corollary 3.3, “we have” becomes “for rr with coordinate losses (L0,(T+L0)/2,…,(T+L0)/2)(L_0,(T+L_0)/2,\dots,(T+L_0)/2) we have.” (iii) In the discussion after Corollary 3.3, “the reward sequence is fixed and only the coordinates are permuted” becomes “the coordinate losses are fixed and only their assignment to coordinates is permuted.”

Notation and readability (response to the comment on notation)

We thank the reviewer for the suggestion to improve readability. We have added a notation table at the beginning of the appendix (both in the uploaded paper and in the global comment). It summarizes the main symbols used in the theorems, as well as symbols such as BB, VV, and hh that have different meanings in different contexts.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal and Paper Revision

Dear Reviewer PJq7,

Thank you very much for your feedback. We truly appreciate your time and would be grateful to hear whether our rebuttal and revision of the paper have 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 PJq7,

With the rebuttal period nearing its end, we would like to thank you once more for your feedback and engagement, which have helped us strengthen our work. We would greatly appreciate any final thoughts on whether our responses have addressed your concerns.

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 tight minimax characterization, the new construction of lower bounds, and the role of L0L_0 together with the matching algorithm. In response to the weaknesses and questions raised, we have posted our responses under each review block and uploaded the revised paper with changes marked in blue. Below, we summarize our responses and the revisions. We are more than happy to answer any further questions.

Summary of responses.

(1) Technical novelty of the upper bounds. Pareto regret is controlled by the positive part of coordinate regret (Lemma 4.1), which a signed expected-regret bound does not provide. When L0L_0 is known, we integrate the high-probability bound of Poly-INF to control the positive part without a logarithmic factor (Lemma A.13, Theorem 4.3). When L0L_0 is unknown, we develop reward-doubling Poly-INF and a new analysis built on one comparator arm and one stopped supermartingale (Appendix A.7.1, Theorem 4.5).

(2) Novelty compared to Xu and Klabjan 2023. Our main contributions are twofold. (1) Minimax rate. [1] establishes horizon-dependent Pareto regret bounds and remarks that coordinates affect only the constants. In contrast, we show that coordinate dependence enters the regret order itself, establishing matching lower and upper bounds of Θ(min⁡U0,KU0)\Theta(\min\\{U_0,\sqrt{KU_0}\\}) for every L0L_0, where U0=T−L0U_0=T-L_0. This can be substantially sharper than horizon-dependent bounds. (2) Coordinate choice and algorithm design. While [1] suggests selecting favorable coordinates, we show that any fixed coordinate suffices to attain the minimax rate, but the algorithm used along that coordinate matters, resolving the open problem raised in [1]. We also refine the Pareto regret definition in [1] and remove the logarithmic factor in its upper bound.

(3) Corollary 3.3. The permutation acts on the coordinate losses of rr, as specified in Sections 2.2 and 3 and Appendices A.1.3 and A.3.5. We believe the concern arises from an ambiguity in our wording. We have modified this in three sentences in the revised paper, while the result, proof, and constant in Appendix A.3.5 remain the same.

(4) Generality of the results and guidance for practice. Theorem 4.6 characterizes the minimax Pareto regret rate through L0L_0 for every L0L_0, allowing arbitrary bounded adversarial reward sequences fixed before play. This generalizes the pessimistic horizon dependency in Xu and Klabjan (2023). Moreover, our new routes show that any coordinate suffices to attain the minimax rate, but the algorithm used on that coordinate matters substantially, thereby resolving the open problem in Xu and Klabjan (2023). This also makes adversarial MO-MAB more tractable, as directly estimating the Pareto front seems almost hopeless in the adversarial setting, whereas we can build on the numerous success of adversarial bandits.

We add the scope statement in the conclusion, in the hope of being fully faithful. 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 herein may yield meaningful follow-ups. We also discuss how we may exploit other coordinate-dependent quantities, such as UdU_d and LdL_d (Corollary A.21), and potentially extend this perspective beyond.

(5) Known minimizing coordinate and adaptive adversaries. We discuss the upper bounds available when d⋆d^\star is known, where obliviousness enters our analysis, and how the two upper bounds may extend to adaptive adversaries.

(6) Presentation. We add a notation table in the appendix and a Related Work section in the main text of the revised paper.

AuthorsOpenReview ↗

Summary of responses and revisions (2/2)

Summary of revisions. The revision is confined to the four items below. We keep all technical content unchanged, and the only statement reworded is Corollary 3.3, as in (R1).

(R1) Wording of the permutation class (Sections 2.2 and 3). The definition of C(r)\mathcal C(r), the statement of Corollary 3.3, and one sentence of the discussion after it now state that the coordinate losses are permuted, in line with the proof in Appendix A.3.5.

(R2) Notation table (start of Appendix A; also presented below). The table lists the main symbols used in the theorems and clarifies the context-dependent meanings of BB, VV, and hh, including where each is used.

(R3) Related Work section (new Section 1.1 in the main text). It is condensed from Appendix A.1, which remains as the extended discussion.

(R4) Two remarks on novelty (end of Section 4.2). Remark 4.7 summarizes the technical novelty of the upper bounds, and Remark 4.8 summarizes the novelty compared to Xu and Klabjan (2023).

SymbolMeaningWhere
KK, DD, TTarms, coordinates, roundsSec. 2
rdi,tr_d^{i,t}reward of arm ii in round tt on coordinate ddSec. 2
ata_tarm played in round ttSec. 2
Gi,dG_{i,d}, AT,dA_{T,d}cumulative reward of arm ii, and of the learner, on coordinate ddSec. 2.1
RTdR_T^dcoordinate regret max⁡iGi,d−AT,d\max_i G_{i,d}-A_{T,d}Eq. (2)
RTfsR_T^{\mathrm{fs}}Pareto regret [max⁡imin⁡d(Gi,d−AT,d)]+[\max_i\min_d (G_{i,d}-A_{T,d})]_+Eq. (3)
UdU_d, LdL_dbest-arm reward on coordinate dd, and its loss T−UdT-U_dSec. 2.2
L⋆L^\star, U⋆U^\star, d⋆d^\starmin⁡dLd\min_d L_d, T−L⋆T-L^\star, and a coordinate attaining L⋆L^\starEq. (5)
L0L_0, U0U_0prescribed value of L⋆L^\star, and T−L0T-L_0Eq. (6), Sec. 3
VK,D,T(L0)\mathcal V_{K,D,T}(L_0)minimax Pareto regret over the sequences with L⋆=L0L^\star=L_0Eq. (6)
VK,D,Tperm(r)V^{\mathrm{perm}}_{K,D,T}(r), C(r)\mathcal C(r)the same over C(r)\mathcal C(r), the sequences whose coordinate losses are a permutation of those of rr (as clarified in change (i) of the Corollary 3.3 response)Sec. 2.2, Cor. 3.3
d′d'coordinate fixed before play (written dd in App. A.9)Lemma 4.1
gi,tg_{i,t}, RTwR_T^wreward and regret of a fixed weighted scalarization, with one coordinate as a special caseLemma 4.1
Sd′S_{d'}switching term ∑tmax⁡ird′i,t−Ud′\sum_t\max_i r_{d'}^{i,t}-U_{d'}Prop. A.10
ee, e⋆e^\star, k⋆k^\starepoch index, cutoff epoch, and comparator arm of reward doublingAlg. 5, App. A.7.1
qq, WqW_q, nn, α\alpha, mmgroup size ⌊K/2⌋\lfloor K/2\rfloor, scale min⁡T,qT\min\\{T,\sqrt{qT}\\}, suffix length, advantage, and embedded rounds ⌊U0⌋\lfloor U_0\rfloor of the lower boundSec. 3, App. A.3
BB, BeB_escale input of Poly-INF, U0U_0 if L0L_0 is known and TT otherwise, and 81K⋅2e81K\cdot2^e in epoch eeSec. 4.1, Alg. 1 to 5
VVmin⁡n,qn\min\\{n,\sqrt{qn}\\} in Eq. (8); scale of gain-based EXP3 in Table 1; estimates Vi,sV_{i,s} in Alg. 1Sec. 3; Table 1; Alg. 1
hhprefix length ⌊Wq/256⌋\lfloor W_q/256\rfloor of the lower bound; block length in Alg. 6; lead V−Ud′V-U_{d'} in App. A.3.6Sec. 3; Alg. 6; App. A.3.6
AuthorsOpenReview ↗

Gentle reminder before the discussion period ends

Dear Reviewers,

Thank you very much again for your time and comments. As the discussion period is closing soon, we would like to kindly remind you that our responses and the revised paper (changes marked in blue) were posted on November 11.

We would be grateful if you could check whether our responses address your concerns, and we are happy to clarify any remaining points. If our responses have resolved your concerns, we would sincerely appreciate it if you could consider updating your assessment accordingly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.