- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies Bayesian multi-objective bandits under Pareto-violation and gap-based regret. For violation regret, it relates information about the unknown Pareto set to predictive separation, analyzes Thompson Sampling, and proposes Pareto-IDS. For gap-based regret, it uses information about the underlying model parameter and establishes regret guarantees; experiments compare the proposed methods with existing baselines.
Critical strengths
The paper’s main strength is its explanation of why the information needed for learning depends on the regret criterion. For Pareto-violation regret, it connects the separation between competing Pareto-set hypotheses to information gain and provides both upper and lower bounds. For gap-based regret, it explains why identifying the Pareto set alone is insufficient and instead analyzes information about the underlying model parameter. The paper also evaluates both criteria against existing baselines and includes additional Gaussian experiments in the appendix.
Critical weaknesses
-
The main Pareto-violation regret guarantees require , where the assumption 3.1 and 3.2 must hold for every realizable history where multiple Pareto sets remain possible. I think different reward distributions across actions do not guarantee this. compares predictions for the same action under different Pareto-set hypotheses. The general identifiability result shows that this separation is positive, but does not give a quantitative lower bound for a broad range of models. Appendix A.4 checks it only in a specific Beta–Bernoulli example. It is unclear how widely the regret guarantees apply.
-
The lower bound does not match the upper bound for long horizons. Proposition 3.2 gives a lower bound of order , while Theorem 3.3 gives an upper bound of order . They match around , but when is much larger, the lower bound stays at order while the upper bound continues to grow. Proposition 3.2 shows that separation matters, but does not establish that Theorem 3.3 is tight.
-
The near- gap-regret result applies to specific models. The logarithmic information bound used for this result is proved for particular models and prior assumptions, rather than general finite-action Bayesian models. For the categorical Dirichlet model, the result assumes that every prior concentration parameter is at least one and gives , In summary, the regret bound gives . The dependence on is near- when these model sizes are fixed, but the bound can grow substantially with the number of actions, objectives, and categories. Compared with Xu and Klabjan (2023), this paper’s gap-regret bound explicitly scales as , so it remains unclear whether this dependence is necessary.
Questions for authors
I would like the authors discuss the weaknesses parts.
7 comments
Rebuttal Continued
Model dependence, dimensional scaling, and comparison with Xu and Klabjan (2023):
(1) General theory versus explicit model rates. Theorems 4.1 and 4.2 apply to general finite-action Bayesian multi-objective bandits with bounded rewards. They give , with arbitrary priors and potentially dependent objectives. Proposition 4.1 derives explicit information budgets for specific models. For categorical rewards with conditionally independent objectives and independent Dirichlet priors with all concentration parameters at least one, , giving regret. The horizon dependence is near- at fixed model size, with explicit dependence on , , , and . The concentration restriction applies to the categorical information-budget proof.
(2) Comparison with Xu and Klabjan (2023). Whether the dependence in our bound is necessary remains open. Their (Xu and Klabjan (2023)) Theorem 4.1 bounds Pareto regret by scalar regret on any chosen objective coordinate. Accordingly, MO-KS (their Algorithm 1) applies UCB to a fixed coordinate in stochastic settings and EXP3.P in adversarial settings, while MO-US (their Algorithm 2) uses a fixed-coordinate EXP3++-type strategy when the setting is unknown. These approaches can achieve favorable dimension dependence, but their regret guarantees do not establish recovery of the complete Pareto set. In contrast, our Pareto TS learns the full set of Pareto-optimal trade-offs, and Proposition 4.2 (added in the revision) establishes both near- gap regret and complete Pareto-set recovery on the same run, under the stated model conditions. The factor in our bound therefore accompanies a stronger learning guarantee that retains all Pareto-optimal options for decisions made after preferences are specified. While we do not claim this factor is unavoidable, comparing dimension dependence alone overlooks this important distinction.
(3) A concrete limitation of fixed-coordinate learning. Consider means , , and . All three arms are Pareto optimal with zero Pareto gap. First-coordinate UCB favors and second-coordinate UCB favors , since the balanced arm is suboptimal on both coordinates. For every normalized nonnegative , the balanced arm has weighted value , while an extreme arm obtains . Even the union of all linearly scalarized optima omits this Pareto-optimal option. If deployment later requires a mean of at least on each objective, the balanced arm is the only feasible choice.
(4) Joint gap regret and full-set recovery. Pareto TS draws a posterior Pareto set and plays uniformly from it, so , where and bounds the set size. Whenever two models have different Pareto sets, an arm in their union has different reward laws under the two models. The sampling bound and posterior exchangeability connect this difference to information gained from the arms actually played. Proposition 4.2, added in the revision, defines as the probability that the sampled set at round differs from the true Pareto set, and as the average mismatch probability over the first rounds. With finite conditional absolute first moments and , the proposition gives , and the posterior mass on the entire true set converges to one almost surely. For the covered Beta--Bernoulli models with fixed size and prior, the same run achieves and Bayesian gap regret.
(5) Empirical full Pareto-set recovery in Figure 3. Across independent trials per instance, we record a mismatch whenever omits a Pareto-optimal arm or includes a dominated arm i.e. reporting avg over independent trials. Figure 3(a) adds two dominated arms to the example above (i.e. true arm means are , , , , and ) . Pareto TS matches the full true set, including the balanced arm, on about percent of the first rounds on average. In Figures 3(b) and 3(c), mismatches account for about and percent of the first rounds, respectively. The cumulative mismatch curves rise more slowly after the initial rounds, indicating fewer exact-set errors per round as learning progresses.
Our additional contribution is a simultaneous guarantee of low Pareto-gap regret and recovery of every Pareto-optimal option on the same run. This lets the learner keep all Pareto-optimal options available for decisions made after preferences or feasibility constraints are specified.
Rebuttal Continued
Near- gap-regret result applies to specific models. The logarithmic information bound used for this result is proved for particular models and prior assumptions, rather than general finite-action Bayesian models.
Breadth of the near- guarantees. Theorems 4.1–4.2 apply to general finite-action Bayesian multi-objective bandits with bounded rewards, arbitrary priors, and potentially dependent objectives, giving . Proposition 4.1 provides explicit logarithmic information budgets for three broad model families, rather than restricting the general theory:
(1) Finite parameter spaces: Arbitrary finite parameter spaces with any prior, where . This guarantee does not require discrete reward observations and also covers continuous reward distributions with bounded support.
(2) Categorical rewards: Arbitrary numbers of actions, objectives, and categories, with independent Dirichlet priors satisfying . This includes the uniform prior and a wide range of informative asymmetric priors. For binary rewards, the two-category Dirichlet distribution reduces to a Beta distribution. For example, if prior knowledge suggests that Arm 1 performs better than Arm 2, we may assign to Arm 1 and to Arm 2. Both satisfy the assumption while encoding different prior beliefs: the former favors higher success probabilities, while the latter is uniform. More generally, concentration parameters can vary across arms, objectives, and categories, allowing substantial flexibility in representing prior information. Thus, the condition accommodates both uniform and informative priors rather than restricting the analysis to a narrow prior specification.
(3) Gaussian rewards: Unknown arm-specific mean vectors and an unknown shared covariance matrix, allowing correlations between objectives, under conjugate normal–inverse-Wishart priors. Appendix A.17 extends the regret analysis through controlled prior conditioning and clipping, yielding near- regret for the conditioned Gaussian model.
(4) General bounded rewards through Bernoullization: Our framework extends beyond categorical distributions to general bounded reward models, including continuous rewards. For conditionally independent reward coordinates , generate independently. By construction, , so the transformation preserves all coordinatewise mean comparisons and hence the complete Pareto set, while scaling every Pareto gap as . Running the algorithms on the induced Bernoulli model therefore gives original-model regret exactly times the transformed regret. Moreover, the induced model admits a logarithmic information budget, , through its Bernoulli success/failure counts. Thus, near- regret extends to the original bounded-reward problem while retaining the dependence.
Importantly, Proposition 4.2 strengthens these results beyond regret. Whenever the parameter-information budget is sublinear and its finite-moment condition holds, Pareto TS also recovers the complete true Pareto set. This applies broadly to finite-parameter models, including those with continuous reward observations; categorical models with discrete rewards; and induced Bernoulli models obtained from bounded continuous rewards. In particular, Bernoullization preserves the entire Pareto set, so the recovery guarantee transfers directly to the original bounded-reward model. For Gaussian rewards, Appendix A.17 establishes the corresponding regret guarantees through prior conditioning and clipping, while the clipped-model recovery analysis yields convergence in probability for horizon-dependent runs.
Thus, our framework provides both sublinear gap regret and complete Pareto-set recovery across broad classes of discrete, bounded continuous, and Gaussian reward models, rather than only a few specialized Bayesian instances.
Thank you for your thoughtful feedback. As ICLR allows revisions during rebuttal, we hope you’ll take a look at our revised manuscript. We’ve marked the changes in blue, including Proposition 4.2 and Figure 3 on full Pareto-set recovery. If the revisions address your concerns, we’d be grateful if you’d consider raising your score. We welcome any further questions.
Rebuttal
Scope and applicability of separation assumptions.:
The important question is whether competing Pareto-set hypotheses predict distinguishable rewards for the some action. This is the information a learner can obtain by choosing that action; the distinction is built into our definition of predictive separation.
(1) Identifiability versus rates. Theorem 3.1 establishes generic pointwise positivity for finite discrete Dirichlet models under its stated conditions. Finitely many count states are realizable up to any fixed horizon T, so κT>0 at that horizon. This does not prove a time-uniform or polynomial lower bound; Assumptions 3.1, 3.2 are separate, quantitative hypotheses.
Verifiable conditions and examples. Section~3 shows that if every competing Pareto-set pair has a common action with posterior-predictive mean-coordinate difference at least δt, then κt≥δt2/∣A∣. Our two-objective, two-hypothesis Bernoulli construction has κt=2δ2 at every finite realizable history with Gt>0; it verifies Assumption 3.1 with κ=2δ2 and Assumption 3.2 with β=0. Appendix A.4 independently checks Theorem 3.1's nondegeneracy conditions for a Beta--Bernoulli example. Neither is presented as a polynomial all-history rate for arbitrary independent Beta--Bernoulli priors.
(2) Why separation matters. Proposition 3.2 proves that for arbitrarily small κ>0, every adaptive policy incurs RTviol≥321min(T,1/κ) on a constructed instance. Thus, weak separation imposes a genuine cost on binary Pareto-violation learning, independent of the algorithm.
(3) Broader applicability: Section 4 does not require Assumptions 3.1 and 3.2. Theorems 4.1 and 4.2 and Propositions 4.1 and 4.2 (now added to revised version) give O(Tlog(1+T)) Bayesian gap regret and vanishing complete-set recovery error for covered independent Beta--Bernoulli models at fixed model size and prior. The assumptions restrict the stated Section 3 violation-regret rates, not the scope of these additional guarantees.
Interpretation and tightness of the separation lower bound.:
Proposition 3.2 establishes sharp dependence on separation at the identification scale, not a globally tight long-horizon regret rate. We agree that its lower bound does not match Theorem 3.3 for all T. The precise comparison is at T≍1/κ.
(a) An unavoidable identification cost. Proposition~3.2 constructs, for each κ∈(0,1/8], an instance with κt=κ at every finite realizable history with Gt>0. Every adaptive algorithm then suffers RTviol≥321min(T,1/κ). For T≤1/κ, linear violation regret is unavoidable on this hard family.
(b) Matching at the critical horizon. At T≍1/κ, the lower bound is Ω(1/κ). Theorem 3.3 and the tuned-TS bound of Proposition A.2 give O(H(S∗)T/κ)=O(1/κ) for this two-hypothesis family, since H(S∗)=log2. Thus the bounds match in their 1/κ dependence precisely at this scale.
(c) What remains open. For fixed κ and T≫1/κ, the lower bound saturates, while the general upper bound grows. We therefore do not claim matching long-horizon rates or global minimax optimality. Sharper instance-dependent bounds are a separate question. Proposition 3.2 establishes why separation matters and identifies the horizon regime where our dependence on it is sharp.