acceptodds
Under review as a conference paper at ICLR 2027

Information-Theoretic Analysis of Multi-Objective Bandits: Pareto Violations and Gap-Based Regret

61 views

Abstract

We study Bayesian multi-objective bandits and ask a basic information-theoretic question: what aspects of an unknown environment must be resolved to achieve low regret? We show that the answer depends on the regret criterion and on the resolution of information needed to represent the corresponding loss. We first consider Pareto-violation regret, which incurs unit loss whenever the selected action is dominated. Because this loss depends only on Pareto membership, the Pareto-optimal set provides a natural information target. We introduce a separation-based measure of the difficulty of distinguishing among competing candidate Pareto sets, relate it to information gain about the unknown Pareto-optimal set, and use this connection to analyze Thompson Sampling and develop an Information-Directed Sampling strategy. We establish sublinear Bayesian regret under uniform and polynomially decaying separation and prove a lower bound showing that weak separability can impose an unavoidable statistical cost. We then consider gap-based Pareto regret, which measures the magnitude of Pareto suboptimality. Here, Pareto-set information is generally too coarse for a direct magnitude-sensitive analysis: distinct environments can share the same Pareto set while inducing different reward geometries and hence different Pareto gaps, and averaging over environments consistent with the same Pareto set need not preserve the Pareto dominance relations. This motivates retaining finer information about the environment that preserves the relevant reward geometry. We develop parameter-level information-theoretic analyses of Thompson Sampling and Information-Directed Sampling to derive gap-based Pareto regret guarantees. Together, our results reveal a hierarchy in the information needed for multi-objective learning: binary Pareto membership can be controlled through information about the Pareto set, whereas quantitative Pareto-gap suboptimality can require a finer representation of reward geometry.

Primary area:
reinforcement learning
Keywords:
Multi-Objective Bandits, Pareto Regret, Information-Directed Sampling, Thompson Sampling, Bayesian Regret, Information Theory

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yVCFOpenReview ↗
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
  1. The main Pareto-violation regret guarantees require κt\kappa_t, 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. κt\kappa_t 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.

  2. The lower bound does not match the upper bound for long horizons. Proposition 3.2 gives a lower bound of order min⁡T,1/κ\min{T,1/\kappa}, while Theorem 3.3 gives an upper bound of order T/κ\sqrt{T/\kappa}. They match around T≈1/κT\approx 1/\kappa, but when TT is much larger, the lower bound stays at order 1/κ1/\kappa while the upper bound continues to grow. Proposition 3.2 shows that separation matters, but does not establish that Theorem 3.3 is tight.

  3. The near-T\sqrt{T} 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 IBT=O(dK∣A∣log⁡T)IB_T=O(dK|\mathcal A|\log T), In summary, the regret bound gives O(∣A∣MdKTlog⁡T)O(|\mathcal A|\sqrt{M dK T\log T}). The dependence on TT is near-T\sqrt{T} 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 d\sqrt{d}, so it remains unclear whether this dependence is necessary.

Questions for authors

I would like the authors discuss the weaknesses parts.

7 comments

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 TT, so κT>0\kappa_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\delta_t, then κt≥δt2/∣A∣\kappa_t\ge\delta_t^2/|\mathcal A|. Our two-objective, two-hypothesis Bernoulli construction has κt=2δ2\kappa_t=2\delta^2 at every finite realizable history with Gt>0G_t>0; it verifies Assumption 3.1 with κ=2δ2\kappa=2\delta^2 and Assumption 3.2 with β=0\beta=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\kappa>0, every adaptive policy incurs RTviol≥132min⁡(T,1/κ)R_T^{\mathrm{viol}}\ge\frac1{32}\min(T,1/\kappa) 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))O(\sqrt{T\log(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 TT. The precise comparison is at T≍1/κT\asymp1/\kappa.

(a) An unavoidable identification cost. Proposition~3.2 constructs, for each κ∈(0,1/8]\kappa\in(0,1/8], an instance with κt=κ\kappa_t=\kappa at every finite realizable history with Gt>0G_t>0. Every adaptive algorithm then suffers RTviol≥132min⁡(T,1/κ)R_T^{\mathrm{viol}}\ge\frac1{32}\min(T,1/\kappa). For T≤1/κT\le1/\kappa, linear violation regret is unavoidable on this hard family.

(b) Matching at the critical horizon. At T≍1/κT\asymp1/\kappa, the lower bound is Ω(1/κ)\Omega(1/\kappa). Theorem 3.3 and the tuned-TS bound of Proposition A.2 give O(H(S∗)T/κ)=O(1/κ)O(\sqrt{H(S^\ast)T/\kappa})=O(1/\kappa) for this two-hypothesis family, since H(S∗)=log⁡2H(S^\ast)=\log2. Thus the bounds match in their 1/κ1/\kappa dependence precisely at this scale.

(c) What remains open. For fixed κ\kappa and T≫1/κT\gg1/\kappa, 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.

AuthorsOpenReview ↗

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 RTgap=O(∣A∣MTI(θ;HT+1))R_T^{\mathrm{gap}}=O(\sqrt{|\mathcal A|MT I(\theta;H_{T+1})}), 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, I(θ;HT+1)=O(dK∣A∣log⁡T)I(\theta;H_{T+1})=O(dK|\mathcal A|\log T), giving O(∣A∣MdKTlog⁡T)O(|\mathcal A|\sqrt{MdKT\log T}) regret. The horizon dependence is near-T\sqrt T at fixed model size, with explicit dependence on ∣A∣|\mathcal A|, dd, KK, and MM. The concentration restriction applies to the categorical information-budget proof.

(2) Comparison with Xu and Klabjan (2023). Whether the d\sqrt d 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-T\sqrt T gap regret and complete Pareto-set recovery on the same run, under the stated model conditions. The d\sqrt d 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 (1,0)(1,0), (0,1)(0,1), and (0.4,0.4)(0.4,0.4). All three arms are Pareto optimal with zero Pareto gap. First-coordinate UCB favors (1,0)(1,0) and second-coordinate UCB favors (0,1)(0,1), since the balanced arm is suboptimal on both coordinates. For every normalized nonnegative ww, the balanced arm has weighted value 0.40.4, while an extreme arm obtains max⁡(w1,w2)≥0.5\max(w_1,w_2)\ge0.5. Even the union of all linearly scalarized optima omits this Pareto-optimal option. If deployment later requires a mean of at least 0.30.3 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 StS_t and plays uniformly from it, so πt(a)≥qt(a)/M\pi_t(a)\ge q_t(a)/M, where qt(a)=Pr⁡(a∈St∣Ht)q_t(a)=\Pr(a\in S_t\mid H_t) and MM 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 et=Pr⁡(St≠S∗)e_t=\Pr(S_t\ne S^\ast) as the probability that the sampled set at round tt differs from the true Pareto set, and eˉT=T−1∑t=1Tet\bar e_T=T^{-1}\sum_{t=1}^T e_t as the average mismatch probability over the first TT rounds. With finite conditional absolute first moments and I(θ;HT+1)=o(T)I(\theta;H_{T+1})=o(T), the proposition gives eT≤eˉT→0e_T\le\bar e_T\to0, 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 eT≤eˉT=O((log⁡(1+T)/T)1/4)e_T\le\bar e_T=O((\log(1+T)/T)^{1/4}) and O(Tlog⁡(1+T))O(\sqrt{T\log(1+T)}) Bayesian gap regret.

(5) Empirical full Pareto-set recovery in Figure 3. Across 200200 independent trials per instance, we record a mismatch whenever StS_t omits a Pareto-optimal arm or includes a dominated arm i.e. reporting avg ∑t=1T1(St≠S∗)\sum_{t=1}^T\mathbf{1}(S_t\ne\mathcal S^\ast) over 200200 independent trials. Figure 3(a) adds two dominated arms to the example above (i.e. true arm means are (1,0)(1,0), (0,1)(0,1), (0.4,0.4)(0.4,0.4), (0.1,0.3)(0.1,0.3), and (0.3,0.1)(0.3,0.1)) . Pareto TS matches the full true set, including the balanced arm, on about 9898 percent of the first 5,0005{,}000 rounds on average. In Figures 3(b) and 3(c), mismatches account for about 99 and 1010 percent of the first 20,00020{,}000 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.

AuthorsOpenReview ↗

Rebuttal Continued

Near-T\sqrt T 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-T\sqrt T 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 RTgap=O(∣A∣MTI(θ;HT+1))R_T^{\mathrm{gap}}=O(\sqrt{|\mathcal A|MT I(\theta;H_{T+1})}). 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 I(θ;HT+1)≤H(θ)≤log⁡∣Θ∣I(\theta;H_{T+1})\le H(\theta)\le\log|\Theta|. 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 α≥1\alpha\ge1. This includes the uniform Dir(1,…,1)\mathrm{Dir}(1,\ldots,1) 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 Beta(5,1)\mathrm{Beta}(5,1) to Arm 1 and Beta(1,1)\mathrm{Beta}(1,1) 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-T\sqrt T 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 Yj∈[0,Rmax⁡]Y_j\in[0,R_{\max}], generate Zj∣Yj∼Bernoulli(Yj/Rmax⁡)Z_j\mid Y_j\sim\mathrm{Bernoulli}(Y_j/R_{\max}) independently. By construction, Eθ[Zj(a)]=Eθ[Yj(a)]/Rmax⁡\mathbb E_\theta[Z_j(a)]=\mathbb E_\theta[Y_j(a)]/R_{\max}, so the transformation preserves all coordinatewise mean comparisons and hence the complete Pareto set, while scaling every Pareto gap as ΔY(a)=Rmax⁡ΔZ(a)\Delta_Y(a)=R_{\max}\Delta_Z(a). Running the algorithms on the induced Bernoulli model therefore gives original-model regret exactly Rmax⁡R_{\max} times the transformed regret. Moreover, the induced model admits a logarithmic information budget, O(d∣A∣log⁡(T+1))O(d|\mathcal A|\log(T+1)), through its Bernoulli success/failure counts. Thus, near-T\sqrt T regret extends to the original bounded-reward problem while retaining the d\sqrt d 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.

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

This paper studies Bayesian multi-objective multi-armed bandits from an information-theoretic perspective, focusing on two notions of regret: Pareto-violation regret and gap-based Pareto regret. For Pareto-violation regret, the authors use the unknown Pareto-optimal set as the information target and introduce a separation measure based on the total variation distance between posterior-predictive distributions associated with competing Pareto sets. For gap-based Pareto regret, the authors argue that Pareto-set identity alone does not preserve the reward geometry required to quantify Pareto gaps. They therefore analyze Thompson Sampling and IDS using information about the underlying environment parameter, deriving regret bounds in terms of parameter-level mutual information.

Critical strengths
  1. The paper investigates an important conceptual question: what information must be learned to achieve low regret under different multi-objective performance criteria? The distinction between Pareto-violation regret and gap-based Pareto regret is meaningful.
  2. The paper develops information-theoretic regret guarantees for both regret criteria, including separation-dependent bounds, a weak-separation lower bound, and parameter-information-budget analyses for several Bayesian models.
Critical weaknesses
  1. The paper mainly extends existing information-theoretic analyses of Thompson Sampling and IDS to multi-objective bandits. The technical novelty beyond these established frameworks is not sufficiently clear. Moreover, the regret guarantees rely on strong separation assumptions, and it remains unclear whether these assumptions hold in common multi-objective bandit settings.
  2. The experiments mainly focus on synthetic environments and do not directly examine how the proposed separation measure affects regret. Additional experiments on more challenging instances and comparisons of computational costs would strengthen the paper.
  3. The Gaussian extension requires uniformly bounded means and sub-Gaussian rewards, which are not automatically satisfied by the Gaussian/inverse-Wishart prior considered in the paper. The authors should clarify the conditions under which these results hold.
Questions for authors
  1. Could the authors clarify which technical results are genuinely new relative to the classical Thompson Sampling and IDS information-ratio framework of Russo and Van Roy? In particular, which steps in the Pareto-violation and gap-based analyses require fundamentally new techniques beyond replacing the optimal-action information target with Pareto-set or parameter-level information?
  2. Theorem 3.1 establishes generic pointwise positivity of the separation measure, whereas Theorems 3.2 and 3.3 require explicit uniform or polynomial lower bounds on this quantity over all realizable histories. Can the authors establish such quantitative separation rates for standard models, such as independent Beta–Bernoulli multi-objective bandits? Without these results, how broadly applicable are the stated regret guarantees?
8 comments

1. Technical novelty beyond classical TS and IDS (i.e. russo and Van roy Papers).

Our technical contribution is not a routine replacement of the best arm by a Pareto set in existing TS/IDS proofs. Such a replacement leave many essential questions unresolved: Are competing Pareto sets statistically distinguishable? Does sampling from a random set acquire enough information? How can a nonlinear Pareto gap be bounded by observable discrepancies? Can low regret be achieved while identifying the entire set? We establish new theorems and proof tools answering all four questions.

(1) Lemma 3.1 and Theorem 3.1: Pareto-set identifiability. We define posterior Pareto-set disagreement GtG_t and predictive separation κt\kappa_t, proving Ea∼Unif(A)[It(a)]≥Gtκt/2\mathbb E_{a\sim\mathrm{Unif}(\mathcal A)}[I_t(a)]\ge G_t\kappa_t/2. Theorem 3.1 establishes generic pointwise separation for finite discrete Dirichlet models under explicit nondegeneracy conditions. Its proof combines analytic posterior-predictive probabilities, measure-zero exceptional sets, and all finite posterior count-update histories. This identifiability result is not supplied by classical TS/IDS theory.

(2) Theorem 3.2 and Propositions 3.1 and Proposition A.2: Pareto TS. A sampled Pareto set may contain arms that reveal little about competing hypotheses. Our proof shows precisely how explicit exploration supplies information and controls both binary violation regret and cumulative full-set mismatch. A separation-tuned schedule gives sublinear violation regret for every β<1\beta<1 under polynomially decaying separation, rather than the default schedule's β<1/2\beta<1/2 range. The improvement comes from the exploration--information analysis, not simply from sampling a set

(3) Theorem 3.3: A new Pareto-IDS comparator. We construct a two-arm comparison distribution: one action has posterior violation probability at most GtG_t, and another gains at least κtGt/2\kappa_tG_t/2 information about competing sets. Mixing with probabilities 1−Gt1-G_t and GtG_t yields expected loss at most 2Gt2G_t and information at least κtGt2/2\kappa_tG_t^2/2, hence ψt(πtIDS)≤8/κt\psi_t(\pi_t^{\mathrm{IDS}})\le8/\kappa_t. This Pareto-specific loss--information inequality is the essential new step.

(4) Proposition 3.2: Algorithm-independent hardness. For every κ∈(0,1/8]\kappa\in(0,1/8], we construct a two-objective family with κt=κ\kappa_t=\kappa at every finite realizable history with Gt>0G_t>0, proving RTviol≥132min⁡(T,1/κ)R_T^{\mathrm{viol}}\ge\frac1{32}\min(T,1/\kappa) for every adaptive algorithm. At T≍1/κT\asymp1/\kappa, the IDS and tuned-TS upper bounds match its 1/κ1/\kappa dependence. This proves that weak separation creates an intrinsic statistical cost.

(5) Section 4 and Lemma A.1: Why scalar-bandit proofs fail.

In scalar TS analysis, averaging models that share an optimal arm preserves the optimality of that arm. This fails for Pareto sets: Section 4 shows that averaging models with the same Pareto set can change which arms are Pareto optimal. Thus, the scalar conditional-comparator proof does not transfer. Lemma A.1 develops a new geometric witness argument. For an arm in a sampled Pareto set, we construct an arm on the true Pareto frontier that improves it by its true gap in every coordinate. Because the sampled arm is Pareto optimal under the sampled parameter, the same strict improvement cannot hold there. At least one coordinate therefore differs sufficiently between the two models. Total variation controls that discrepancy, and posterior exchangeability then yields an expected Pareto-gap bound. This is the new structural step needed before information-theoretic TS/IDS analysis can begin.

(6) Lemma A.2, Theorems 4.1 4.2, and Corollary 4.1:. Pareto TS samples an action from a random set , so the membership probability qt(a)q_t(a) is not the play probability πt(a)\pi_t(a). We prove πt(a)≥qt(a)/M\pi_t(a)\ge q_t(a)/M, with MM the maximum sampled-set size. The witness lemma (Lemma A.1) then gives (E[Δθ(At)∣Ht])2≤32Rmax⁡2∣A∣MJt(\mathbb E[\Delta_\theta(A_t)\mid H_t])^2\le32R_{\max}^2|\mathcal A|M J_t, where Jt=∑aπt(a)It(a)J_t=\sum_a\pi_t(a)I_t(a) is the information gained by the actual policy. This new inequality yields the TS bound, its IDS comparison, and Corollary 4.1 on aggregate sampled-set gaps.

(7) Propositions 4.1 4.2 (now added to revision) and Appendix A.19: Model rates, full-set recovery. We derive finite, categorical--Dirichlet, and Gaussian information budgets; Gaussian regret additionally uses the conditioning/clipping proof in Appendix A.17. Crucially, small Pareto-gap regret does not imply exact-set recovery: even a dominated arm can have zero uniform gap. Proposition 4.2 proves a distinct union-of-Pareto-sets witness argument and quantitative full pareto-set recovery.

Together, these results go beyond changing the information target of a classical proof. They establish new Pareto-set identifiability, separation hardness, geometric regret--information inequalities, and joint regret/recovery guarantees.

AuthorsOpenReview ↗

Rebuttal Continued

Additional experiments on more challenging instances and comparisons of computational costs would strengthen the paper

We added targeted experiments that make Pareto comparisons progressively harder. Appendix A.22 (Figures 6, 7) studies 1010-arm, 44-objective Beta--Bernoulli instances, narrowing the mean ranges from [0.05,0.95][0.05,0.95] to [0.25,0.75][0.25,0.75] and [0.40,0.60][0.40,0.60]. This brings arm means closer and concentrates Bernoulli probabilities near 1/21/2, where observation variance is largest, making dominance harder to infer.

Figure 6 (added to revised version) shows increased violation regret as the means become closer; Pareto-IDS has the lowest regret, followed by Pareto TS. In the hardest setting, Figure 7 reports approximately 2525 gap regret for IDS, 8080 for TS, 190190 for two-phase MO-MAB, and 275275 for Pareto-UCB1 at T=20,000T=20{,}000. These are controlled difficulty stress tests, not direct measurements of the history-dependent κt\kappa_t.

Appendix~A.21 (Figures 4,5) further evaluates continuous Gaussian rewards with unknown action-dependent means and variances, beyond the Bernoulli setting. For computation, Appendix~A.20 details Monte Carlo information estimates, closed-form alternatives, and optimization over at most two IDS actions; Appendix~A.23 reports the computing resources. These experiments and implementation analyses directly strengthen the empirical discussion.

Gaussian extension requires uniformly bounded means and sub-Gaussian rewards, which are not automatically satisfied by the Gaussian/inverse-Wishart prior considered in the paper:

An unrestricted Gaussian/inverse-Wishart prior indeed has unbounded support for means and variances. Appendix A.17 (after some changes in revised version) (Equations~98--106) directly addresses this point by constructing and analyzing a restricted model. The Gaussian regret theorem does not silently assume boundedness under the unrestricted prior.

(a) The assumptions hold under a specified prior, with controlled conditioning. Let p0p_0 be the proper normal–inverse-Wishart prior for unknown arm means μa\mu_a and shared covariance Σ\Sigma. Define the event E=(max⁡a,j∣μa,j∣≤μmax⁡, max⁡jΣjj≤σ2)E=(\max_{a,j}|\mu_{a,j}|\le\mu_{\max},\ \max_j\Sigma_{jj}\le\sigma^2) and p1=p0(⋅∣E)p_1=p_0(\cdot\mid E). For any fixed δ∈(0,1)\delta\in(0,1), finite thresholds μmax⁡,σ>0\mu_{\max},\sigma>0 can be selected from the known prior, independently of TT, so that p0(E)≥δp_0(E)\ge\delta. Indeed, both maxima are finite p0p_0-almost surely. Choosing each bounding event to have probability at least (1+δ)/2(1+\delta)/2 and applying the union bound gives the claim; e.g., δ=1/2\delta=1/2 ensures 1/p0(E)≤21/p_0(E)\le2. Thus the conditioning factor is controllable, not merely finite. Under p1p_1, both the learner and environment are supported on EE, and Equation (98) holds since ∣μa,j∣≤μmax⁡|\mu_{a,j}|\le\mu_{\max} and Eθeλ(Ya,j−μa,j)=eλ2Σjj/2≤eσ2λ2/2\mathbb E_\theta e^{\lambda(Y_{a,j}-\mu_{a,j})}=e^{\lambda^2\Sigma_{jj}/2}\le e^{\sigma^2\lambda^2/2}.

(b) Clipping preserves the learning target. The algorithms use the exact likelihood and posterior for coordinatewise clipped rewards, with BT=μmax⁡+2σlog⁡(2T)B_T=\mu_{\max}+2\sigma\sqrt{\log(2T)}. Equation (99) controls the original-versus-clipped Pareto-gap discrepancy, whose cumulative contribution satisfies 2TεBT=o(1)2T\varepsilon_{B_T}=o(1). Equation (105) shows that clipping preserves the entire Pareto set, including ties, since the same covariance across arms makes each clipped coordinate mean a strictly increasing function of its original mean.

(c) Information and regret remain controlled. Lemma A.5 establishes a logarithmic information budget IT0=O((d∣A∣+d2)log⁡(1+T))I_T^0=O((d|\mathcal A|+d^2)\log(1+T)) under p0p_0. Applying the same action-selection rule under both priors, conditioning and data processing (Equations 102–103) yield IB~T≤IT0/p0(E)≤IT0/δ=O(log⁡(1+T))\widetilde{\mathrm{IB}}_T\le I_T^0/p_0(E)\le I_T^0/\delta=O(\log(1+T)) for fixed model size. Although larger thresholds may increase the clipping level and regret constants, the thresholds and conditioning factor 1/p0(E)1/p_0(E) are independent of TT. Consequently, Equation (104) establishes O(Tlog⁡(1+T))O(\sqrt T\log(1+T)) Bayesian gap regret for clipped TS and IDS under p1p_1, evaluated using the original Gaussian means. Appendix A.18 additionally establishes full Pareto-set recovery on the same clipped TS run.

The scope is explicit: Lemma A.5 supplies the unrestricted-prior information budget; conditioned shared-covariance model with clipping supplies the Gaussian regret guarantee. We do not assert boundedness or the same regret theorem for the unrestricted prior.

AuthorsOpenReview ↗

Rebuttal Continued

Theorem 3.1 establishes generic pointwise positivity of the separation measure, whereas Theorems 3.2 and 3.3 require explicit uniform or polynomial lower bounds on this quantity over all realizable histories. Can the authors establish such quantitative separation rates for standard models, such as independent Beta–Bernoulli multi-objective bandits? Without these results, how broadly applicable are the stated regret guarantees

Pointwise identifiability and quantitative all-history separation are distinct guarantees. Theorem 3.1 establishes generic κt>0\kappa_t>0 at every finite realizable history under its conditions. Since only finitely many count states occur up to any fixed horizon TT, this implies κT>0\kappa_T>0, but does not establish a uniform-in-time or polynomial lower bound. We therefore do not claim that Assumptions 3.1–3.2 automatically hold for arbitrary independent Beta–Bernoulli models.

We provide verifiable sufficient conditions and an explicit quantitative example. Proposition A.1 shows that if every competing posterior-supported Pareto-set pair admits an action and reward coordinate whose posterior-predictive means differ by at least δt\delta_t, then, for rewards in [0,1]d[0,1]^d, κt≥δt2/∣A∣\kappa_t\ge\delta_t^2/|\mathcal A|. Thus, δt≥δ>0\delta_t\ge\delta>0 implies uniform separation, while δt≥δt−γ\delta_t\ge\delta t^{-\gamma} implies polynomial separation with β=2γ\beta=2\gamma. Our two-objective Bernoulli construction with a two-point prior (Section 3, lines 188–194) satisfies κt=2δ2\kappa_t=2\delta^2 at every finite realizable history with Gt>0G_t>0, explicitly verifying Assumption 3.1. Appendix A.4 separately verifies Theorem 3.1's nondegeneracy conditions for an independent Beta–Bernoulli model. We acknowledge that these results do not establish polynomial all-history rates for arbitrary Beta–Bernoulli priors.

The scope of the guarantees is therefore important. The Section 3 violation-regret bounds apply when the stated quantitative separation conditions can be verified. Proposition 3.2 further establishes an algorithm-independent Ω(min⁡{T,1/κ})\Omega(\min\{T,1/\kappa\}) violation-regret lower bound, demonstrating the intrinsic cost of weak separation. However, the Section 4 results do not require Assumptions 3.1–3.2. For the covered independent Beta–Bernoulli models, Theorems 4.1–4.2 and Proposition 4.1 yield O(Tlog⁡(1+T))O(\sqrt{T\log(1+T)}) Bayesian gap regret at fixed model sizes, while Proposition 4.2 establishes full Pareto-set recovery for Pareto TS. Thus, the quantitative separation assumptions restrict the stated violation-regret guarantees, not the applicability of our gap-regret and full-set recovery results.

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.

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

This paper studies Bayesian multi-objective bandits with two different regret objectives: pareto-violation regret (incurs unit loss whenever the selected action is dominated) and the gap-based regret (measures the largest amount by which another action improves on the selected action in every objective). For the first objective, the authors introduce a separation-based measure and develop an Information-Directed Sampling. The authors establish separation-dependent upper bounds and a weak-separation lower bound. For the second objective, the authors analyze Thompson Sampling and Information-Directed Sampling using information about the model parameter. Experiments are conducted to test the performances of these algorithms.

Critical strengths

This paper considers an interesting problem of Bayesian multi-objective bandits. For both the pareto-violation regret and the gap-based regret, the authors establish algorithms and theoretical guarantees. In particular, they consider the regret from an information-theoretic perspective. With the assumption of uniform separation or decaying separation, sublinear regret bounds are established for the pareto-violation metric. They also show that weak separability can result in linear regret (when T is small). Their analysis further establishes bounds for the gap-based metric. Numerical experiments indicate that the proposed algorithms can achieve better performances against benchmarks under Bernoulli and Gaussian rewards.

Critical weaknesses

The main limitation concerns the assumptions. Assumptions 3.1 and 3.2 require candidate Pareto sets to be distinguishable at every history point. This seems to fail in the Beta–Bernoulli model used in the experiments: when two arms have nearly equal empirical means, the separation is of order 1/t (i.e., \beta = 1), so Theorems 3.2 and 3.3 no longer give sublinear regret. The gap-based results can also be strengthened. With a collection of positive weights summing to one, the weighted regret gives an upper bound of the Pareto-gap regret. Therefore, we are able to apply the standard Thompson Sampling results, which can achieve better regret rate than Theorem 4.1. A clarification with this baseline would help.

Questions for authors
  1. Can the Assumptions 3.1 and 3.2 be relaxed?
  2. Can the authors compare with Thompson Sampling on a fixed weighted sum of the objectives and explain the benefit of the proposed algorithm with the gap-based metric?
3 comments

Assumptions 3.1 and 3.2 require candidate Pareto sets to be distinguishable at every history point. This seems to fail in the Beta--Bernoulli model used in the experiments: when two arms have nearly equal empirical means, the separation is of order 1/t1/t

Separation assumptions and the two regret criteria: The key distinction is between two different losses: Pareto-violation regret assigns unit loss to every dominated pull, whereas gap-based Pareto regret measures the magnitude of suboptimality. Assumptions 3.1 and 3.2 provide sufficient conditions for the separation-dependent guarantees for the former, while Section 4 establishes guarantees for the latter without these assumptions.

We agree that a separation rate of order t−1t^{-1} falls outside the sublinear regimes established by Theorems 3.2 and 3.3. Theorem 3.1 establishes pointwise positivity of the separation measure, not the stronger rates required by these theorems. However, nearly equal empirical means do not by themselves establish κt≍t−1\kappa_t\asymp t^{-1} : κt\kappa_t measures the separation between posterior-predictive distributions for the same action, conditional on competing Pareto-set hypotheses. Thus, the proposed t−1t^{-1} behavior does not follow directly from the proximity of empirical means. We do not claim that Assumptions~3.1 and 3.2 automatically hold for every Beta--Bernoulli model.

The importance of quantitative separation arises from the binary nature of Pareto-violation regret: a dominated pull incurs unit regret even when its mean is arbitrarily close to the Pareto frontier. Such alternatives can be statistically difficult to distinguish, yet each mistaken pull incurs the same loss. Proposition 3.2 formalizes this difficulty: for every κ∈(0,1/8]\kappa\in(0,1/8], it constructs a two-objective instance with κt=κ\kappa_t=\kappa at every finite realizable history with Gt>0G_t>0, on which every adaptive policy satisfies RTviol≥132min⁡(T,1/κ)R_T^{\mathrm{viol}}\ge \frac{1}{32}\min(T,1/\kappa). Consequently, the lower bound grows linearly with TT for horizons T≤1/κT\le1/\kappa. At T≍1/κT\asymp1/\kappa, the IDS and separation-tuned TS upper bounds O(H(S∗)T/κ)O(\sqrt{H(\mathcal S^\ast)T/\kappa}) match the lower bound's 1/κ1/\kappa dependence, since H(S∗)=log⁡2H(\mathcal S^\ast)=\log 2 for this construction. This establishes an intrinsic statistical cost of weak separation and matching separation dependence at the crossover horizon. It does not imply that Assumptions 3.1--3.2 are necessary for every instance or that the bounds are tight at every horizon.

Importantly, this limitation is specific to the stated Pareto-violation regret guarantees. For gap-based Pareto regret, nearly optimal actions incur correspondingly small losses. Theorems 4.1--4.2 exploit this distinction by controlling regret through parameter-level information, without requiring Assumptions 3.1--3.2. For the covered independent Beta--Bernoulli models, Proposition 4.1 establishes a logarithmic information budget, yielding O(Tlog⁡(1+T))O(\sqrt{T\log(1+T)}) Bayesian gap regret at fixed model sizes. Moreover, Proposition 4.2 establishes recovery of the entire Pareto-optimal set for Pareto TS without these separation assumptions. Thus, even when the Section 3 separation conditions cannot be verified, the Section~4 guarantees provide sublinear gap-based regret and full Pareto-set recovery without assumptions 3.1 and 3.2.

Can Assumptions 3.1 and 3.2 be relaxed?

Assumptions 3.1 and 3.2 suffice for Section 3s separation-dependent rates. Theorem 3.3 gives RTviol≤ΨH(S∗)TR_T^{\mathrm{viol}}\le\sqrt{\Psi H(\mathcal S^\ast)T} if ψt(πtIDS)≤Ψ\psi_t(\pi_t^{\mathrm{IDS}})\le\Psi at every realizable history. The assumptions bound the ratio by linking expected violations to predictive separation. Model-specific bounds can replace them with separate proofs. Binary loss charges one unit even for a nearly undetectable difference in mean reward.

For each κ∈(0,1/8]\kappa\in(0,1/8], Proposition~3.2 gives a model with κt=κ\kappa_t=\kappa at every finite realizable history with Gt>0G_t>0 and RTviol≥min⁡(T,1/κ)/32R_T^{\mathrm{viol}}\ge\min(T,1/\kappa)/32 for every adaptive algorithm. Taking κ=1/T\kappa=1/T for T≥8T\ge8 gives RTviol≥T/32R_T^{\mathrm{viol}}\ge T/32, ruling out uniform sublinear violation regret on this family with arbitrarily weak separation. At the crossover T≍1/κT\asymp1/\kappa, IDS and separation-tuned TS match the intrinsic 1/κ1/\kappa cost, with H(S∗)=log⁡2H(\mathcal S^\ast)=\log 2.

Section 4 proves exact Pareto-set recovery and bounds gap regret without Assumptions 3.1 and 3.2. For Pareto TS (Algorithm~3) in fixed-size independent Beta--Bernoulli models with admissible priors, Proposition 4.2 gives eˉT=T−1∑t=1TPr⁡(St≠S∗)=O((log⁡(1+T)/T)1/4)\bar e_T=T^{-1}\sum_{t=1}^T\Pr(S_t\ne\mathcal S^\ast)=O((\log(1+T)/T)^{1/4}) and a.s. posterior concentration on S∗\mathcal S^\ast. Small Pareto gaps incur small losses. Theorems 4.1--4.2 use parameter-level information. Proposition 4.1 gives logarithmic budgets for standard bounded-reward models, including Beta--Bernoulli, yielding O(Tlog⁡(1+T))O(\sqrt{T\log(1+T)}) Bayesian gap regret.

AuthorsOpenReview ↗

Rebuttal Continued

Can the authors compare with Thompson Sampling on a fixed weighted sum of the objectives and explain the benefit of the proposed algorithm with the gap-based metric?

Fixed-weight TS is a valid and useful comparison. For normalized nonnegative weights ww, Δθ(a)≤max⁡bw⊤μθ(b)−w⊤μθ(a)\Delta_\theta(a)\le\max_b w^\top\mu_\theta(b)-w^\top\mu_\theta(a); consequently, scalar-regret guarantees also control Pareto-gap regret and may have better model-size dependence. Similarly, (Xu and Klabjan (2023)) upper-bound their Pareto regret by regret on an arbitrarily chosen fixed objective coordinate; their stochastic MO-KS algorithm runs ordinary UCB on that coordinate. These reductions can achieve low Pareto regret. What they do not guarantee is identification of the entire Pareto set. Our analysis establishes both gap-regret control and full-set recovery for Pareto TS on the same run.

This distinction matters when preferences are unknown at learning time. Consider arms (1,0)(1,0), (0,1)(0,1), and (0.4,0.4)(0.4,0.4). All are Pareto optimal with zero Pareto gap. Yet, for every normalized nonnegative ww, the balanced arm has scalar value 0.40.4, while some extreme arm has value max⁡(w1,w2)≥0.5\max(w_1,w_2)\ge0.5. Even the union of all linearly scalarized optima therefore misses a genuine Pareto-optimal trade-off. A fixed-coordinate policy also treats the balanced arm as suboptimal: pulling it incurs at least 0.10.1 scalar regret but zero Pareto-gap regret. If deployment later requires a mean of at least 0.30.3 in both objectives, this balanced arm is the only feasible option. Scalar algorithms may incidentally observe it, but their scalar-regret bounds do not guarantee its identification as Pareto optimal.

Pareto TS instead draws a parameter from the posterior, forms its entire Pareto set StS_t, and plays uniformly from StS_t. Thus, every sampled Pareto-optimal trade-off remains eligible, even if no linear weighting selects it. If qt(a)=Pr⁡(a∈St∣Ht)=Pr⁡(a∈S∗∣Ht)q_t(a)=\Pr(a\in S_t\mid\mathcal H_t)=\Pr(a\in\mathcal S^\ast\mid\mathcal H_t) and MM bounds the set size, the play probability satisfies πt(a)≥qt(a)/M\pi_t(a)\ge q_t(a)/M. Posterior support for Pareto membership therefore translates into an opportunity to learn about that arm. Once the posterior concentrates on the three-arm Pareto set above, each of its arms, including the balanced one, is played with probability approaching 1/31/3.

Proposition 4.2 (which now added to revised manuscript) turns this advantage into a formal guarantee on the same TS run that controls regret. For the stated models we have eT=Pr⁡(ST≠S∗)→0e_T=\Pr(S_T\ne\mathcal S^\ast)\to0: the sampled set includes every Pareto-optimal arm and excludes every dominated arm with probability tending to one. Furthermore, posterior mass on the entire true set converges to one almost surely. Low regret for selected actions alone does not imply this: the learner may still fail to identify other Pareto-optimal choices.

The proof uses a information theoretic argument. If two candidate models have different Pareto sets, some arm in their union has different observation laws. Posterior exchangeability and the sampling inequality connect this witness to information gained from arms actually played. With Proposition 4.1s information budget bounds, the covered bounded categorical models, including Beta--Bernoulli bandits, achieve O(Tlog⁡(1+T))O(\sqrt{T\log(1+T)}) Bayesian gap regret and eT≤eˉT=O((log⁡(1+T)/T)1/4)e_T\le\bar e_T=O((\log(1+T)/T)^{1/4}), at fixed model sizes and prior. Hence the same run has vanishing average gap regret and vanishing full-set error, without committing to preferences in advance.

Figure 3 (newly added in the revision) measures this stronger objective directly, reporting average ∑t=1T1(St≠S∗)\sum_{t=1}^T\mathbf{1}(S_t\ne\mathcal S^\ast) over 200200 independent trials. Figure 3(a) adds two dominated arms to the example above (i.e. true arm means are (1,0)(1,0), (0,1)(0,1), (0.4,0.4)(0.4,0.4), (0.1,0.3)(0.1,0.3), and (0.3,0.1)(0.3,0.1)): Pareto TS identifies the complete true set, including the balanced arm, on approximately 9898 percent of the first 5,0005{,}000 rounds on average. In Figures 3(b)--(c), full-set mismatches account for approximately 99 and 1010 percent of the first 20,00020{,}000 rounds. Our benefit is therefore not merely a small gap for the chosen arm, but preserving every Pareto-optimal option for decisions made after learning.

Fixed-weight TS can control Pareto-gap regret. In the stated models, Pareto TS pairs sublinear gap regret with full-set recovery on the same run, keeping even trade-offs missed by every linear weighting available when preferences are specified after learning.

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.

AuthorsOpenReview ↗

Follow-Up on Rebuttal and Revised Manuscript.

Dear Reviewer LGML,

As we are approaching the end of the discussion period, we would like to kindly follow up on our responses to your review.

We have addressed both of your main concerns regarding the separation assumptions and the comparison with fixed-weight Thompson Sampling. We have also substantially revised the manuscript, including adding Proposition 4.2 and Figure 3 to establish and empirically demonstrate full Pareto-set recovery alongside sublinear gap regret.

We would greatly appreciate it if you could take a look at our responses and revised manuscript. If you have any remaining concerns or follow-up questions, please let us know so that we have sufficient time to address them before the discussion period ends.

If our responses and revisions have satisfactorily addressed your concerns, we would also be grateful if you would consider reconsidering your rating of 2: Weak rejection.

Thank you again for your time and thoughtful feedback.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Key Theoretical Contributions and Guarantees Addressing Reviewers’ Concerns on Novelty, Applicability, and Pareto-Set Recovery

Dear Area Chair and Reviewers,

We summarize our responses and key contributions.

Different regrets require different information. Violation regret depends on Pareto-set membership; gap regret on suboptimality magnitude. Averaging models sharing S∗S^{\ast} can change dominance, so scalar TS/IDS proofs do not transfer directly.

Section 3: separation, algorithms, and hardness. Lemma 3.1 links information about S∗S^{\ast} to κt\kappa_t: predictive separation for the same arm under competing Pareto-set hypotheses. Theorem 3.1 proves pointwise positivity under its conditions, not uniform or polynomial rates. Proposition A.1 gives sufficient conditions; a Bernoulli example verifies uniform separation. Theorem 3.2 and Proposition A.2 analyze exploratory TS; Theorem 3.3 constructs a Pareto-IDS comparator. For κt≥ct−β\kappa_t\ge ct^{-\beta}, tuned TS and IDS give sublinear violation regret for β<1\beta<1. These bounds need all-history separation rates, unproved for arbitrary Beta–Bernoulli priors. Proposition 3.2 proves algorithm-independent hardness: constructed instances force RTviol≥min⁡(T,1/κ)/32R_T^{\mathrm{viol}}\ge\min(T,1/\kappa)/32 for every adaptive policy. Bounds match in κ\kappa at T≍1/κT\asymp1/\kappa, not all horizons.

Section 4: new Pareto-specific proof tools. Algorithm 3 samples a Pareto set StS_t and plays uniformly from it without forced exploration or scalarization. Lemma A.1 links nonlinear gaps to reward laws via a Pareto-optimal witness. Lemma A.2 handles random-set sampling: πt(a)≥qt(a)/M\pi_t(a)\ge q_t(a)/M links membership to actual play, yielding a policy regret–information inequality. These go beyond scalar reductions.

General theory and model coverage. Theorems 4.1–4.2 give RTgap=O(∣A∣MTI(θ;HT+1))R_T^{\mathrm{gap}}=O(\sqrt{|\mathcal A|MTI(\theta;H_{T+1})}) for bounded-reward finite-action models with arbitrary priors and dependent objectives; MM bounds set size. Proposition 4.1 gives finite-parameter, categorical–Dirichlet, and Gaussian information budgets. The categorical case includes independent Beta–Bernoulli rewards with both Beta shapes at least one, allowing asymmetric priors. Bernoullization preserves the Pareto set for bounded continuous rewards. Near-T\sqrt T rates use model-specific budgets.

Proposition 4.2: three guarantees on one Pareto TS run. Appendix A.18 proves a union-of-Pareto-sets witness: different sets imply distinct reward laws for an arm in their union, including ties. Posterior exchangeability and the sampling inequality link witnesses to information from actions actually played, without all-history separation. For a high-prior-mass parameter set GG with distinguishability ρ>0\rho>0, Eq. (115) bounds set error by 2p1(Gc)+(2/ρ)2∣A∣MI(θ;HT+1)/T2p_1(G^c)+(2/\rho)\sqrt{2|\mathcal A|MI(\theta;H_{T+1})/T}. Here GG concerns parameters, not histories; ρ\rho need not be global. Under exact posterior sampling, finite conditional absolute first moments, and I(θ;HT+1)=o(T)I(\theta;H_{T+1})=o(T), it proves eˉT=T−1∑t=1TPr⁡(St≠S∗)→0\bar e_T=T^{-1}\sum_{t=1}^T\Pr(S_t\ne S^{\ast})\to0, eT≤eˉTe_T\le\bar e_T, and almost-sure posterior concentration on the entire true set. Since At∈StA_t\in S_t, a dominated pull implies mismatch, so RTviol≤TeˉT=o(T)R_T^{\mathrm{viol}}\le T\bar e_T=o(T) without Assumptions 3.1–3.2. Theorem 4.1 simultaneously gives sublinear gap regret for bounded rewards. For fixed-size independent Beta–Bernoulli models with stated priors, the same run achieves RTgap=O(Tlog⁡(1+T))R_T^{\mathrm{gap}}=O(\sqrt{T\log(1+T)}), eˉT=O((log⁡(1+T)/T)1/4)\bar e_T=O((\log(1+T)/T)^{1/4}), and RTviol=O(T3/4log⁡1/4(1+T))R_T^{\mathrm{viol}}=O(T^{3/4}\log^{1/4}(1+T)). Appendix A.19 covers a TS/IDS mixture. Thus missing all-history rates limit Section 3 bounds, not Algorithm 3's separate violation-regret guarantee.

Scalar baselines and dd-dependence. Fixed-weight/coordinate methods bound gap regret, sometimes with better dd-dependence, but do not establish complete Pareto-set recovery. Among (1,0)(1,0), (0,1)(0,1), and (0.4,0.4)(0.4,0.4), the balanced arm is Pareto-optimal yet optimal for no nonnegative linear weighting. Xu–Klabjan, Lu et al., and Park et al. do not prove exact recovery of the entire ordinary Pareto set on the same regret-controlled run. We do not claim the categorical d\sqrt d factor is necessary; it comes from the information budget, not the general theory. Sharper dimensional and long-horizon bounds remain open.

Gaussian case and experiments. Appendix A.17 uses prior conditioning and clipping; its Gaussian regret bound excludes the unrestricted prior. We added harder 10-arm/4-objective Bernoulli tests, Gaussian experiments, Figure 3 on recovery, and computational details.

To the Area Chair and reviewers: We respectfully ask you to weigh: Pareto-specific information-theoretic proofs, algorithm-independent hardness, general Bayesian regret guarantees, and joint sublinear gap and violation regret with complete Pareto-set recovery on one TS run. Proposition 4.2 addresses the applicability concern through an independent on-policy guarantee. Thank you for your consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.