- 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
- the paper is very well written and structured, it is overall pleasant to read in llm era now. reference is well listed.
- 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.
- 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.
- experiment is comprehensive, with solid baselines included.
Critical weaknesses
- 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.
- 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
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.
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.
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≥2 and d≥2. 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 is the Pareto gap of arm a and A⋆ is the Pareto set. Suppose every dominated arm has positive Pareto gap, and let LT=log(T(d∣A⋆∣)1/4). The leading upper bounds in Remark 6 satisfy
our leading boundPareto-UCB1 leading bound=8Kg†(∑a:ΔaP>0ΔaP1)logTLT.
Since LT≥logT, our leading bound is smaller whenever g†∑a:ΔaP>01/ΔaP>8K, and the advantage grows without limit as the Pareto gaps shrink with g† fixed. For example, if m dominated arms have Pareto gaps at most δ, this condition holds whenever δ<mg†/(8K). Importantly, g† can remain large while δ becomes arbitrarily small and m 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] and the number of near-front dominated arms m∈1,4,8,12, while keeping g†=0.55 fixed. At δ=0.02, increasing m from 1 to 12 increases the normalized Pareto-UCB1 coefficient from 30.45 to 142.08, exceeding the theoretical threshold of 64 when m=8 and m=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=6) and KuaiRec (d=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(KlogT/g†) for bounded i.i.d. instances with full-vector feedback whenever g†>0, with no multiplicative dependence on d in the leading term, and a matching asymptotic Ω(KlogT/g†) 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 KlogT/g† 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.