Thompson Sampling for Multi-Objective Linear Contextual Bandit
Authors: Somangchan Park
Heesang Ann
Min-hwan Oh
Venue: NeurIPS 2025 poster ()
Keywords: Multi-Objective Multi-armed Bandit
Linear Contextual Bandit
Pareto Optimality
Thompson Sampling
Primary area: theory
TL;DR: We propose the first Thompson Sampling algorithm with Pareto regret guarantees in multi-objective linear contextual bandit.

Abstract: We study the multi-objective linear contextual bandit problem, where multiple possible conflicting objectives must be optimized simultaneously. We propose $\texttt{MOL-TS}$, the first Thompson Sampling algorithm with Pareto regret guarantees for this problem. Unlike standard approaches that compute an empirical Pareto front each round, $\texttt{MOL-TS}$ samples parameters across objectives and efficiently selects an arm from a novel effective Pareto front, which accounts for repeated selections over time. Our analysis shows that $\texttt{MOL-TS}$ achieves a worst-case Pareto regret bound of $\widetilde{O}(d^{3/2}\sqrt{T})$, where $d$ is the dimension of the feature vectors, $T$ is the total number of rounds, matching the best known order for randomized linear bandit algorithms for single objective. Empirical results confirm the benefits of our proposed approach, demonstrating improved regret minimization and strong multi-objective performance.

Thompson Sampling for Multi-Objective Linear Contextual Bandit
Somangchan Park Seoul National University jrhopefulp@snu. ac.
Heesang Ann Scoul National University sang3798@snu.co ac
Min-hwan Oh Scoul National University minoh@snu, kr.
Abstract
We study the multi-objective linear contextual bandit problem, where multiple possible conflicting objectives must be optimized simultancously. We propose MOL-TS, the first Thompson Sampling algorithm with Pareto regret guarantees for this problem. Unlike standard approaches that compute empirical Pareto front each round, MOL-TS samples parameters across objectives and efficiently selects
from novel effective Pareto front, which accounts for repeated selections over time. Our analysis shows that MOL-TS achieves a worst-case Pareto regret bound of ((d/2V/T) where is the dimension of the feature vectors, T is the total number rounds, matching the best known order for randomized linear bandit a algorithms for single objective. Empirical results confirm the benefits of our proposed approach, demonstrating improved regret minimization and strong multi-objective performance.
Introduction
The multi-objectio the classical, single-objective multi aemti-armed bandit to settings with multiple, potentially conflicting objectives. Pulling arm yields vector of objective-specific rewards, single "best" arm is often ill-defined and optimality must account for trade-off' across objectives.
bandit (MOMAB) problem 8 55 18 10, 7 generalizes
One simple way to handle trade-off's is scalarization [14 20), which maps reward vectors to scalar via, e.g., weighted sums, minimax, or other nonlinear transforms, thereby reducing MOMAB to single-objective bandit. However, selecting suitable scalarization is itself nontrivial, and an arm optimal under one scalarization can be markedly suboptimal under another. An alternative is to directly in the vector space via Pareto optimality [8] 5 18 10 7 the Pareto front comprises arms whose mean reward vectors are not dominated component-wiss wise. Because it compares Pareto optimality is strictly more general than committing fixed
reward vectors objective-wisg scalarization, and we adopt it throughout.
All of the prior MOMAB work in Pareto regret propose and study UCB-based algorithms g 18 10). To the best of our knowledge, the Pareto regret of Thompson Sampling (TS) 2 has been studied for MOMAB. This gap is noteworthy: in many single-objective contextual and non-contextual bandits, TS and its variants are empirically competitive or superior to UCB methods [6 4 2 yet their worst-case analyses typically more delicate. Extending TS to MOMAB introduces additional challenges, including coordinating randomized samples across multiple objectives and handling the possibility of multiple Pareto Pareto-optimal arms.
In this work, we develop TS algorithm for the multi- multi-objective linear contextual bandit and analyze its worst-case Pareto regret. Our method samples separate parameters for each objective and evaluates arms via an optimistic sampling mechanism that ensures a nontrivial probability of being jointly optimistic across all objectives (Section 5.3). which underpins the regret analysis.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

We also revisit the notion of performance measurement. The standard Pareto regret compares per- round mean reward vectors; consequently, repeatedly playing a single Pareto-optimal arm can yield zero regret even when an alternative arm selection would strictly larger cumulative rewards (see Section 3.3). To address this, we introduce the notion of an effective Pareto-optimal arm (Definition an arm that is Pareto-optimal per round and remains undominated when evaluated through the lens of cumulative rewards under any number of repeated selections. Building on this, we define a corresponding regret notion that penalizes policies vulnerable to such cumulative inefficiencies; our algorithm targets the effective Pareto front to avoid these failures.
Our main contributions are summarized as follows:
We propose an algorithm for the multi-objective linear contextual bandit problem: Thompson sampling for Multi-objective Linear Bandit (MOL-TS), To the best of our knowledge, this is the first randomized algorithm for multi-objective contextual bandits with Pareto regret guarantees. Unlike the existing multi-objective algorithms. MOL-TS does not explicitly compute an empirical Pareto front each round, but rather randomly selects arm from that Pareto front, which is much more computationally efficiently.
We propose the concept of a effective Pareto optimal arm (Definition 5) which satisfies the condition of Pareto optimal arm, and also the total rewards for every objective with any number of its repeated selection satisfying Pareto optimality. Any arm that not effective Pareto optimal has an alternative selection of arms over the same total number of rounds, resulting higher total rewards in all objectives. Our proposed algorithm, MOL-TS, operates on this new notion of the effective Pareto front and samples an arm from the estimated effective Pareto front. As result, MOL-TS produces higher cumulative rewards compared to the methods that selected from the plain Pareto front.
We establish that MOL-TS is statistically efficient, achieving the Pareto regret bound of (dd5/2 where d is the dimension of the feature vectors, T is the total number of rounds. In order ensure the provable guarantees of the randomized exploration for multiple objectives, MOL-TS adopts the optimistic sampling strategy (Section 5.3
Numerical experiments demonstrate the effectiveness of our proposed approach, showing improved performance in regret minimization, and objective-wise total reward maximization.
2
Related works
Multi-objective multi armed bandit setting was first explored by Drugan and Nowe (8, who proposed UCB algorithms for MOMAB by applying two representative approaches: using Pareto order and scalarized order. Subsequently, Auer et al. [5] proposed algorithms that identify all Pareto optimal arms with high probability. More recently, the upper and lower bounds of Pareto regret in the MOMAB setting have been studied in both stochastic and adversarial settings by Xu and Klabjan [18. There are also several studies on multi-objective contextual bandits. For example, Tekin and contextual setting where dominant objective exists. but do not assume any dominance among objectives. Turgay et al. [17] developed the PCZ algorithm, which identifies the Pareto front using the idea of contextual zooming and proved its regret bound. However, the algorithm is complex, and the paper does not provide specific details on its implementation. Lu et al. studied the multi-objective generalized linear bandit (MOGLB) problem and analyzed the upper bound of Pareto regret using the ParetoUCB algorithm. Additionally, Kim et al. [I0] explored Pareto front identification in linear bandit settings. The studies mentioned thus far proposed complex algorithms that calculate the empirical Pareto front. In contrast, Zhang 220 introduced hypervolume scalarization method in stochastic linear bandit settings, which uses random scalarization to explore the entire Pareto front
Turgay [15] studied MOMAB
While these studies address significant challenges in multi-objective bandits, surprisingly, although the practical effectiveness of randomized methods is widely recognized, research on randomized algorithms in multi-objective bandits has been rare. To the best of our knowledge, only Yahyaa and Manderick [19] proposed Thompson Sampling (TS) algorithm for MOMAB, but no theoretical analysis of this approach has been conducted. Separately, there has been significant research on
randomized scalarization in the multi-objective Bayesian optimization problem [1] 21 including
theoretical analyses TS algorithms. However, Zhang and Golovin (2] and Paria et al. 14 analyzed the "Bayes regret" with known Gaussian prior setting, increasing with the number of objectives.
2

---

(2)
(2)
140
110
Puayi (.200.9
Muau (0.1.0.7)
Mhac [..1.
0.7
Phayi 0.440.4
8m13
Puasi [0.3.0.4]
6:75
Mhasi [0.8.033
Phayy (0.5002)
Phaui 0.7.0.2)
Muasi
0.00
Phaco [0.1,0.2]
(0.6,0.) 0.6]
6.00
Mrec 0.9]
0.2
033
633
4(10
040
0.00
6.00
25
180
823
000
0320
1.00
0.33
0:25
1.00
0075
1.30
0.00
0.5
0.08
0.72
1.00
8
Figure 1: Example two objectives and four arms, a(1)+ ((2), a(3), and ((4). Each subplot shows the mean reward vector round where the horizontal and vertical axes correspond to the first and second objective, respectively. Red circles represent Pareto optimal arms, blue triangles that are not. The mean reward vectors are listed the right, and the pink line represents the boundary of effective Pareto front (see Definition
In the single-objective case, the theoretical analysis of Thompson sampling was first introduced by Agrawal and Goyal [3, and then was extended the stochastic linear bandit setting in Agrawal and Goyal [4. where arms were categorized as either saturated or unsaturated to derive theoretical bounds. From different perspective, Abeille and Lazaric [2] analyzed Thompson Sampling under the assumption of fixed probabilities for sampling optimistic parameters. Additionally, Chapelle and Li [6] showed that, although the theoretical guarantees of Thompson Sampling are weaker than those of UCB, empirical results have consistently demonstrated that TS algorithms outperform UCB algorithms in practice. However, there has been clear gap in extending these theoretical guarantees from single objective settings to multi-objective bandits.
We provide the first theoretical analysis of randomized algorithm in the multi-ohjective bandit setting. To the best of our knowledge, this is the first work to propose TS algorithm for multi-objective linear contextual bandits and analyze it theoretically.
3 Preliminaries
3.1 Notations
Throughout this paper, we use notations that distinguish between different objectives. For any positive integer N E N, let [N] ;= (1,2,..., We denote L as the number of objectives, and for l E [Z]. any real number corresponding to the fo--objeciive is denoted (f)) The vector E RR comprises all ( values and is represented in bold notation, i.e., u = [x(1), (2))
(L)]T.
Otherwise, individual features of any vector x are typically denoted as ar().. For clarity, || denotes
the Euclidean norm, and for positive semi-definite matrix V, the norm || ||v is defined in the inner
product space with the matrix V as (2r, vevy vx Vy. Finally, define S R the unit (n -immlex.
3.2 Problem settings
We consider a standard stochastic linear contextual bandit problem, extended to the multi cojeti-obeective setting. Let A be finite set of arms. Each arm A corresponds to a d-dimensional context vector It,a E Rdd which is adversarially given at each round t. For each objective E [L], there exists a fixed parameter (²) Rd but unknown agent. In total, there are parameters 0! o!2)
(L At each round E [T], the agent selects an arm a, E A and receives a L-dimensional reward
vector Tt.a. [r,,, r2.,,...., (. R², where the reward for each objective é is given by (2)
(1) (2)
tta = ((1) ct and e is zero-mean random noise. The mean reward for objective é
is defined pL,,
(8) E[r (2)
1. And consequently, the mean reward vector of the chosen arm a, is
Ht,,. =[ut, p........ ................................ a
(1)
(L) T L.4.

---

3.3 Pareto optimality
Definition (Pareto order) Let u, v E Re be two distinct vectors. We say that the vector u is dominated by the vector v (i.e., v dominates u), denoted as u u, if if (0 S vl for all E [L] and (t < vl6) for some E [T.. Conversely, the vector u is not dominated by the vector denoted as R v, if there exists at least one 8 E [L] satisfying (0)) > v(0)
Definition 2 (Pareto optimal arm) An arm is Pareto optimal if its mean reward vector is not domi- nated by that of any other arm. The set of all Pareto optimal arms is called Pareto Front (P;),
P. = {a E EAI He,a A ot Va' E A}.
In linear setting, where the mean rewards of each arm remain fixed, the Pareto front is denoted as P
Definition 3 (Pareto sub-optimality gap) The Pareto sub-optimality gap of an arm a at round t is the minimum scalar value 2 0 for a to be Pareto optimal, i.e.,
A PR = fc 2 0 Pi,a + c1 Pt, Ya' E EA). t
The Pareto sub-optimal gap can be defined as A == maX minse (pre - -t.al. }. For every Pareto optimal arm a' E Pt, the arm that maximizes 1,a' is af itself, which implies A 0. Any other arm is dominated by at least one Pareto optimal arm, ensuring that A Pn
(8)
2 0.
Definition (Pareto regret) Let a1, 02. or be the sequence of arms chosen by agent. The Pareto regret up to round T is defined as PR(T) = E A.R.
In the contextual bandit setting, the Pareto front varies dynamically depending on the given context. Hence, we can not apply the algorithm of identifying Pareto front in Auer al. [5] and Kim et al. [10 as they remove arm from the arm set, which can be Pareto optimal in our setting.
By using the Pareto order relationship, the definition of Pareto regret provides a general measurement of an agent's performance in a multi-objective setting. Previous studies of Pareto optimality [ا
17 10] adopt this measurement and design algorithms that randomly select arms from the Pareto front, aiming to minimize the Pareto regret. However, this definition of Pareto regret does not fully account for cumulative rewards. For example, consider a case with two objectives and four arms, as illustrated in Figure [ Suppose two agents follow same policy that randomly selects arm from Pareto front. The first agent sequentially selects a(2); a(4) and d(3), while the second agent selects d(1), (4) and ((2)- Both agents selected Pareto optimal arms, resulting zero Pareto regret. But total rewards of the first agent is (1,0(2) + M220,4 + Ms = [1.3, 1.3) and the second agent is [1.6, 1.7]. This example highlights the limitation of Pareto regret, it does not distinguish between policies that yield different cumulative rewards despite selecting only Pareto optimal arms. Thereby, we propose the concept of effective Pareto optimal arm, whose mean reward vector is Pareto optimal and contributes to maximizing cumulative rewards across all objectives.
3.4 Effective Pareto optimality
Definition (Effective Pareto optimal arm) An arm is effective Pareto optimal (denoted a.) if its mean reward vector is either equal to or not dominated by any convex combination of the mean reward vectors of the other arms. Formally, for any AlAl-
H1.a.
Σ
Balta
M1,0. A
Baltra
aEA)(a.)
DEAA((a))
where 3 = (l The set all effective Pareto optimal arms at round t is called the effective Pareto front, denoted as CT In the linear bandit setting, where the mean reward vectors of all arms remain fixed, the effective Pareto front denoted C*
In this paper, we refer to an arm that not effective Pareto optimal as sub-optimal. If an arm a' E A is sub-optimal, then there exists convex combination B, such that pe, < EoEAyAa) Baltr

---

Every effective Pareto optimal arm is also Pareto optimal amm. This can be easily verified by restricting be a one-hot vector, which corresponds to comparing mean reward vectors between two individual arms. However, the converse does not hold. As can be seen from Figurel | at the first round, arm ((2) Pareto optimal, but not effective Pareto optimal, because mean reward vector dominated by a convex combination of two arms d(1) and a(3). Hence, for any E [T', we have C C P. This shows that our definition of effective Pareto optimal arm is strictly defined than the standard definition of Pareto optimal arm.
As shown in the example in the previous subsection, two agents following the same policy randomly selected arms from the Pareto front. The second agent consistently selected arms from the effective Pareto front, while the first agent selected arms from the Pareto front but not the effective Pareto front in the first and third rounds. This difference led the first agent achieving lower cumulative rewards than the second agent for all objectives. Importantly, this disparity becomes increasingly severe as the total number of rounds 7' grows, leading to significantly worse long-term performance for policies that fail to prioritize the effective Pareto front.
The intuition behind effective Pareto optimal is that repeatedly selecting such arms leads Pareto optimal cumulative rewards. In other words, rather than selecting a sub-optimal arm over multiple rounds, it is preferable to select effective Pareto optimal arms for the same total number of rounds, which is expected to yield strictly higher cumulative reward some objectives without worsening the others. In summary, for large enough total number of rounds T, selecting front C achieves higher total rewards than selecting arms from Pareto optimal front Pr. Based on this, we propose theorem that establishes relationship between the newly defined effective Pareto optimality and the linear scalarization method.
from effective Pareto
Theorem For any a, E C", there exist S satisfying a, arg max w Ma. Conversely, for any w E St, if a, = arg maxaeA w Na is unique arm, then a. E C
The theorem is proved in Appendix A where refer to the proof from Mangasarian 12 The theorem shows a one-to-one correspondence: every effective Pareto optimal arm is optimal for some non-negative weight vector, and every non-negative weight vector guarantees to have an effective Pareto optimal arm.
Definition 6 (Effective Pareto sub-optimality gap) Let 3 = (Ba)aEA be a vector in S/Al and define pt, EeEA Baltea The effective Pareto sub-optimality gap for selecting arm at at round is defined as
A
EPR F,
inf 2 Ht.a + el Mr,s, 43 S
The effective Pareto sub-optimal gap measures the minimum value for ae not to be dominated by any convex combination of the mean reward vectors of the other arms. In other words, the gap quantifies how close arm ag is to being effective Pareto optimal. For any effective Pareto optimal arm, this gap is zero. Also, it is easy verify that the effective Pareto sub-optimality gap is always greater than or equal to the standard Pareto sub-optimality gap, i.e., A < EPR since the Pareto sub-optimality gap corresponds to the special case where / is restricted to be one-hot vector. As discussed in Section 3.3 the effective Pareto sub-optimality gap can also be expressed as
t.o,
EPR L,
max min 0 RE(L.
Σ EC
Ba.
(E) 12,00
Definition (Efffettive Pareto regret) The effective Pareto regret up to round T is defined as EPR(T)= = Σr A EPR
L,as
4 Algorithm: MOL-TS
propose a multi-objective linear Thompson Sampling algorithm, MOL-TS, generic randomized algorithm designed with multiple regularized MLE, where need not sample from an actual
5

---

Algorithm 1 Multi-Objective Linear TS (MOL-TS)
Input: X, M, [ 0,
Initialize: 1/1 ATa, 1 2 =0 E [I])
for parl=11 1- do
for objective = 1,2,3, ..... L do 0:00 Sample 6,1 2,2 i. (N cvV, Evaluate every arm Pi,a using Equation 2 end for
Update the empirical effective Pareto front C2 using Equation
Sample arm a, from C2 uniformly at random, play az, observe reward vector Ti.ec Update V++1 4- 1 + Lt, Z2.00
for objective 1,..., do
Update 2 f- Z + Lt,a, Ti and (00 t V ((1)
end for end for
Bayesian posterior 2 Our algorithm adopts an optimistic sampling strategy to avoid the theoretical challenges in worst-case regret analysis [13 9
Each round t, the mean reward vector for each arm estimated based on the history of chosen arms a1, 01,02..... dr-1, and received reward vectors 11,0 22,021"...... 1,-1,0,-1 up round t. The true
parameter for each objective g is estimated by regularized least squares (RLS), denoted 0,00 Given regularizer À E 1 the matrix and the RLS estimator is defined as
V Σ Fsaa s,a + Mlxxd
0 = Vi-!
(2) 2. Fs,a, ",02"'
s=1
For each objective f, the parameters (0L.) (eEm) are sampled independently M times from Gaussian posterior distribution (0 (V, where the tunable parameters and M are given from the beginning. A total of M L samples are drawn. The reward for each arm and for each objective is then optimistically evaluated using the sample that yields the highest value,
Pe. max (x a(0 IT 22:-...... T7,00 (.M)
The reward vector for each arm then constructed as Pr.a = p Pea
Pi,
The number of samples M controls the probability that the estimated rewards are optimistically evaluated. Increasing M raises the likelihood that the reward estimates are optimistic, which is crucial for ensuring a high theoretical probability of optimism across multiple objectives (see Section 5.3).
We approximate the empirical effective Pareto front C, using the estimated reward vectors, by
E a=faeAt Vr.a
Σ Bo or Pi,a * EBer Vas S/A/ a'EAA
a'EAA
Note that this optimistic sampling strategy is different from that proposed in 13 The setting in 13 considers dynamic assortment selection problem, and [9] considers a combinatorial selection problem. Unlike multiple arms selection problem in single objective setting, our setting considers receiving multiple rewards from single arm selection problem.
Regret analysis
In this section, we analyze the expected effective Pareto regret of our algorithm MOL-TS in the worst-case, where the expectation is taken over all sources of randomness present the problem setup. We begin with the general assumptions widely used in the linear bandit literature. We then outline the challenges in bounding the effective Pareto regret and explain how the number of samples M affects the worst-case regret bound.

---

5.1 Assumptions
Let Fi (1I..))...... 2i,a, r',,, ,.t.................. T1-1, be the filtration up to round containing all historical information about the selected arms and the received rewards. The following assumptions are commonly used in the stochastic linear bandit literature.
Assumption (Boundedness) For each arm a E A. || S 1. Also, |10! S for all [4].
Assumption (Sub-Gaussian) Each noise &t is conditionally R-sub-Gaassiee given the filtration Fr and for some R. R
Under the first assumption, each vector is both fixed and bounded for all rounds. If || S C and || < C' are bounded for some constant C, then our regret bound would increase by factor of C. Note that we do not assume any linear independence of the true parameters or noise vectors between objectives. Our assumptions are essentially the same as those used in the single objective stochastic linear bandit setting.
5.2 Challenges in bounding the effective Pareto regret
Previously, there are many papers of multi-objective UCB-ttyp algorithm with Pareto regret analysis 17 II TO 18. The analysis of UCB algorithm almost similar that of single objective setting, attaining Pareto regret bound where the number of objectives depend up to logarithmic factor. By contrast, deriving comparable guarantees for TS in the multi-objective linear contextual setting remains an open problem, and our work is the first to tackle these technical obstacles directly.
Recall the effective Pareto regret Equation
I.
For any weight vector E S" since ||/|| 1,
Ba, Ba.Hr.a. (
min (E(L.]
Σ a. EC;
Ba.llaa
(E) M2,00
un
Σ EC2
The algorithm MOL-TS optimistically evaluates reward vector Ut,a for each arm, and selects arm ag randomly from the set C. Hence, by Theorem | there exist weight vector, denoted wt, satisfying a₂ arg maXae_ w. f4,a- But for true mean reward vector, let a = arg maxae w. Nt.0 be the effective Pareto optimal arm for given weight vector wi. Then have
EPR A
<
max BESICT
W.TT
wi
(
Σ ECEC*
Ba, M1,0, Me.a1 } w. (Her, Me,ae) s,0
EC
The key insight is that the effective Pareto regret is bounded by the weighted sum of rewards under an arbitrary weight vector, and the same holds for Pareto regret. This analysis generalizes the single objective case, which is recovered by restricting w, to one-hot vector.
However, since the arm a is randomly selected from the set č. both the weight vector w., and the corresponding effective Pareto optimal arm a, are random. Due to the randomness of the vector w, and the optimal arm a., analyzing the worst-case regret bound of TS algorithm becomes significantly more difficult. Also, unlike the single objective setting, the multi-objective setting involves multiple true parameters and corresponding RLS estimates. This complicates the problem of ensuring optimism, as there are multiple sampled parameters in TS algorithm (see example in We resolve these theoretical challenges by adopting optimistic sampling strategy.
Section 5.3
5.3
Why do we need optimistic sampling?
In this section, we explain the necessity of the number of samples M. As we discuss in Section 5.2 the challenges in the worst-case regret analysis for TS algorithms lie in the difficulty of ensuring optimism in randomly selected arm a,. When w, is one-hot vector, the analysis aligns with the single objective setting 4 2 However, since w, is random, the analysis requires that the randomly chosen arm optimistically evaluated under a weighted sum of rewards. This probability can become exponentially small as the number of objectives increases.
7

---

Before providing a detailed explanation, we first define the event & that the true parameters 0. are close enough to the RLS estimate parameters 8 and define (1.(()) which the high probability bound on the distance between the true parameter and the RLS estimate,
& = [ve L 11000 -6 S c1,(()), c1,(0) = R dlog 1+ (t 1)/(Ad) + X2/2.
8/L
we have IP(E:) 1 6. The OVVlo L) dependence in c1,r(6) ) is inevitable as the confidence bound must hold uniformly over all objectives. We define the event ((f) for specific arm a and objective f, where the event has at least one parameter following anti-concentration property of being optimistic, i.e.,
By Lemma 8
t,a {3m E [M] 2T,a (0 0!00) 2 c1,r(8)]
As the algorithm MOL-TS optimistically evaluate each a with Equation (2). the probability ((E(f) increases as M increases. Suppose, for example, one follows standard TS algorithm by setting M 1, that only one parameter is sampled for each objective. Previous studies 4 2 have shown that the probability of an arm a being optimistically evaluated is at least p, i.e.,
Pf
0(()) 2
}} 2 p.
where ÿ is constant probability, that depends on the choice of sampling distribution. However, since w, is random, the probability of ensuring this optimism for every objective is at least p'. Since this probability decreases exponentially with the number of objectives, the regret grows exponentially in L, yielding 0(1/p" - /T)2
Optimistic sampling strategy resolves this problem MOL-TS optimistically evaluate the rewards using M independent parameter samples for each objective. Specifically, the algorithm evaluates the arm according to the sampled parameter that maximizes the evaluation, i.c.,
(x.Ta 000 1,10 TT TT ((0) 2.2 Lt 0.0)
argmax
(8 E[M]
Then, the probability bound for the optimism event is
P( (0 a.t 0 2 c1.(())lrr.ll)))))))) (1- -1-
To prevent the exponential growth the probability of ensuring optimism, the number of samples must depend on the number of objectives L. The next lemma shows the minimum number of samples M for ensuring the event of optimism with constant probability.
Lemma (Optimistic Sampling) For any arm a A, define the event of anti-concentraatio prop- (66 erty of being optimism É.,. = NeElL Lta Then on event &g with = 0.15 and M 2 log(1-p) we have P(E,,) 2
log
The event & is that the arm is optimistically evaluated for every objective. Lemmal shows that the lower bound on the probability that arm a being optimistically evaluated remains constant by taking optimistic sampling strategy. The proof of this lemma is provided in Appendix B.
5.4 Worst-case regret bound
We now present the worst-case (frequentist) regret upper bound of MOL-TS, where the expectation is taken over all sources of randomness present in the problem setup.
Theorem (Effective Pareto regret MOL-TS) With Assumptions and 2 with c = (,)) and M
log
). the effective Pureto regret of the algorithm MOL-TS is upper-bounded by
og
T + 25 A
E|PR() = 14 p-
(r)))
2T
1 A
8

---

objective
objective
100
20
Reword
5000
Cumulatte Rboord
5000
Poreto Begret
Parato Begret
20
2000
2000
23
1000
1000
01
2500
5000
7500
10000
0
2600
5000
7900
10000
2500
5000
7500
10000
0
20000
5000
7000
10000
Round
Round (1)
Round
Round
objective
objective
1000
20
Effective Poreto ftegrt
5000
Cumulatre Roward
50000
Effective Partto Rogre
4000
4000
30
Cumulativ
5000
10
2000
2000
20
1000
1000
2000 5000 7500
10000
2500
5000
7000
10000
2500
2000
7500 10000
2000
5000 Round (f)
7000
10000
Round (f)
Round (1)
Round (f)
Figure 2: Experimental results with objectives (I. = 4). Plots in the left three columns measure the performances of MOL-TS and the others. Two plots in the first column measure the Pareto regret and the effective Pareto regret. Four plots the second and third columns measure the cumulative reward for each objective. Plots in the right most column measure the performances of MOL-TS with M 1 and (log L). The error bars represent the I-sigma standard deviation over instances.
where
(1+
1 (T
(T-11/(2d)) + 11/2)
1)/(
2LM
cr(0) R dlog
2d log
5/L
5
Corollary (Pareto regret of MOL-TS) With same assumptions and initialization, the Pareto regret of the algorithum MOL-TS is upper-hounded by
2 p
1) + 282
E[PR(T)]
1
cr())
2T
1 x1+,)
Discussions of Theorem 2 and Corollary 1 Theorem establishes that the expected effective Pareto regret of MOL-TS is bounded above by (d /T), where the regret has an additional O(log L) and O(ylog M7) dependence the number of objectives and the number samples, respectively, both of which are minimal. Additionally, Corollary holds since A PR < A EPR The details of the proof Lee are provided Appendix B To the best our knowledge, MOL-TS is the first TS algorithm with the worst-case regret guarantees in both Pareto regret and effective Pareto regret.
6 Experiments
In this section, we empirically evaluate the performance of our algorithm. We measure the Pareto regret and effective Pareto regret over T 10000 rounds. Each experimental setup contains 10 different instances with fixed number of arms K, objectives L, and feature dimension
We demonstrate the case where K 50, d 5, L 4. The parameter vector for each objective o! has a norm 1. Each round, d-dimensional context vectors are revealed for every arm, bounded by in Euclidean norm. Upon playing term, where the noise values are sampled from a zero mean Gaussian distribution with o 1.
the agent receives a reward vector with additional noise
We compare the performance of MOL-TS with those basic novel algorithms the Upper Confidence Bound algorithm,
e-Greedy algorithm. The Upper Confidence Bound algorithm is MOGLM- UCB (represented as MOL-UCB in our experiments), from Lu et al. [1]] in linear bandit setting and Greedy algorithm MOL-c-Gren voL-e-Greedy is basic MOMAB algorithm with e = 0.05. Other algorithms cannot be applied in contextual setting, they remove sub-optimal arm from the arm set. We also

---

compare the performance of MOL-TS with and without the optimistic sampling. As shown in Figure 2 our proposed algorithm MOL-TS shows greater performance compared other algorithms, with minimizing the Pareto regret and effective Pareto regret, and maximizing cumulative rewards in all objectives. Additionally, MOL-TS with optimistic sampling performs better in minimizing regret. Additional experiments with different settings of K, d and I, are left in Appendix F with additional algorithm PFIwR from Kim et al. [10 in linear bandit setting.
We observe that MOL-e-Greedy yields higher Pareto regret and effective Pareto regret, but also total rewards compared to MOL-UCB. This counterintuitive behavior arises from the averaging of cumulative rewards: although the algorithm selects arms that are Pareto optimal, averaging their outcomes can reduce the overall performance because the algorithm randomly samples from the Pareto front. In other words, by exploring multiple Pareto optimal arms without a consistent preference direction, averaging total rewards may appear smaller despite balanced trade-offs. This issue could be mitigated by guiding the arm selection toward a specific scalarization or optimization direction, allowing the algorithm to maintain both Pareto efficiency and higher total reward.
Discussions
In this paper, study the multi-objective linear contextual bandit problem, where multiple con- flicting objectives must be optimized simultancously. We define the effective Pareto regret, whose definition considers the Pareto optimality of cumulative reward vectors. We propose a Thompson Sampling algorithm with optimistic sampling strategy, MOL-TS, that achieves the Pareto regret and effective Pareto regret of ((d//2T)) matching the best known order for randomized linear ban- dit algorithms for single objective setting. Empirical results confirm the benefits of our proposed approach, demonstrating improved regret minimization and strong multi-objective performance.
Acknowledgements
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2--2022-NR071 1853 and (8S-2023-00222663) by Institute of Information & communications Technology Planning Evaluation (IIPP) grant funded by the Korea government (MSIT) (No. RS-2005--02663554 and RS-2025-25463302,, by the Global-LAMP Program of the NRF grant funded by the Ministry of Education (No. ASS-2033-00301977 and by
Al-Bio Research Grant through Seoul National University.
References
[1] Yasin Ybbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
[2] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017.
[3] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armes bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[4] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
[5] Peter Auer, Chao-Kai Kai Chiang, Ronald Ortner, and Madalina Drugan. Pareto front identification from stochastic bandit feedback. In Artificial intelligence and statistics, pages 939-947. PMLR, 2016.
[6] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
[7] Ji Cheng, Bo Xue, Jiaxiang Yi, and Qingfu Zhang. Hierarchize pareto dominance in multi- objective stochastic linear handits. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 38, pages 1 11489-11497, 2024.
10

---

[8] Madalina M Drugan and Ann Nowe. Designing multi-objective multi- armed bandits algorithms: study. In The 2013 international joint conference on neural networks (IJCNN), pages 1-8. IEFF, 2013.
[9] Taehyun Hwang, Kyuwook Chai, and Min-hwan Oh. Combinatorial neural bandits. In Interna- tional Conference on Machine Learning pages 14203-14223 PMLR, 2023.
[10] Wonyoung Kim, Garud Iyengar, and Assaf Zeevi. Learning the pareto front using bootstrapped observation samples. arXiv preprint arXiv:2306. 2.0.::220000000996, 2023.
[11] Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Multi-objective generalized linear bandits, arXiv preprint arXiv:1905. 128,:,99 2019.
[12] Olvi L Mangasarian. Nonlinear programming. Society for Industrial and Applied Mathematics, 1994.
[13] Min-hwan Oh and Garud lyengar. Thompson sampling for multinomial logit contextual bandits. In Advances in Neural Information Processing Systems, volume 32, 2019.
[14] Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póezos. A flexible framework for multi-objective bayesian optimization using random scalarizations. Uncertainty in Artificial Intelligence, pages 766-776. PMLR, 2020.
[15] Cem Tekin and Eralp Turgay. Multiobjecttive contextual multi-armed bandit with dominant objective. IEEE Transactions on Signal Processing, 66(14):379933133 2018.
[16] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
[17] Eralp Turgay, Doruk Oner, and Cem Tekin. Multi-objective contextual bandit problem with similarity information. In International Conference Artificial Intelligence and Statistics, pages 1673-1681. PMLR, 2018.
[18] Mengfan Xu and Diego Klabjan. Pareto regret analyses in multi-objective multi-armed bandit. In International Conference on Machine Learning, pages 38499-38517. PMLR, 2023.
[19] Saba Q Yahyaa and Bernard Manderick. Thompson sampling for multi-objective multi-armed bandits problem. In ESANN, 2015.
[20] Qiuyi Richard Zhang. Optimal scalarizations for sublinear hypervolume regret. Advances in Neural Information Processing Systems, 17:39963-39999, 2024.
[21] Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multi- objective black box optimization. In International conference on machine learning, pages 11096-11 1105. PMLR, 2020.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We propose the first Thompson Sampling algorithm with Pareto regret guaran- tees in multi-objective linear contextual bandit. Our contributions are clearly summarized in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Appendix D
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
12

---

Answer: [Yes]
Justification: Theorems are presented with assumptions in detail (see Section 5). Details
and explanations of the proofs given in Appendix A and Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All codes of algorithms and experiments are provided in ZIP file. Experi- mental results provided in Section 6 and Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
13

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All codes of algorithms and experiments are provided ZIP file. Experi- mental results are provided in Section 6 and Appendix F
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
jublic/guiiee/CooeSuumii wtt.Suuwiiiiioooooiiiiiooooooooo for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https htcc/public/guuiees/Ccddee
ssi sissonnnicc for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details of experimental settings are provided in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: both Section and and Appendix all the bars in regret plots and reward plots represent the 1-sigma standard deviation of experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
14

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We include information about the computing environment used to run experi- ments in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The research in paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper has no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
15

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We clearly mention the sources of the comparator algorithms in Section 0
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
16

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper clearly describes our proposed algorithm in Section The codes of our proposed algorithm are provided in a ZIP file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
17

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Our core method development in this research does not involve any usage of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non- standaadd components.
non Please refer to LLM policy thttps://neurip: www.urrppsscccooeeeeeeeeeeeeeeee /cc//ooneeeeencs//222/////// for what should or should not be described.
18

---

A Proof of Theorem 1
In this section we present the proof for the necessary properties of effective Pareto optimal arms. Before proving this theorem, we use the following definition that denotes the convex hull of arbitrary set.
Definition 8 Let M C Be' be set of mean reward vector Mo. For all E A. Define the convex hull a set M Conv(M).
By definition, for any 3 = (Ba)aEA SIA, we have
Σ Bataa E Conv(M)
This convex hull covers all the convex combination of mean reward vectors of every arms. We note that, in the convex set Conv(M the mean reward vector of the effective Pareto optimal arm satisfies the Pareto optimality in Conv(M). In other words, for all a. E C*, we have
Na. * p4,
Vp E Conv(M) \ {Ha.)
However, for the arm EA\C C*, there exists μ Conv(M) satisfying
Na
The arm that is effective Pareto optimal, satisfies the Pareto optimality in Conv(MM (see Definition 5
Other than the Pareto optimality, the next definition describes the optimality of one specific objective, with constraint on the other objectives.
Definition (e-constraint optimal) Let El be dimensional arbitrary constraint vector
(E(1) ... elt-1)
(l+1)
_e4i] E R-
Given the constraint vector Eg, the e--constraint optimal vector among the set Conv(M), denoted He,, is defined by
argmax (1(0) (k()) (8) for all k: = 4
(M))
The vector is e-constraint optimal (denoted μ..) if. for all l E [L], there exists constraint vector Ei such that the vector μ. is e--constraint optimal vector.
The constraint vector e2 the lower bound values, such that the vector μ dominates the constraint vector, except objective Among those vector 41 satisfying constraint, the e--constraint optimal vector the one that has maximum value in objective é. The e-constraint optimal vector is such constraint vector e, exists, as to be é, constraint optimal, for all & E [L].
The next lemma shows the equivalence between e-constraint optimality and Pareto optimality.
Lemma The vector μ. E (Cov(MM) is Pareto optimal if and only if is e-constraint optimal.
Proof. (=) Let μ. be Pareto optimal. Assume it is not ee-constraint optimal for some &. Let the constraint vector be (k) = fam
(k) for = 1,..., L, + f. Since is not eg-constraint optimal, then (k) < (x(*) for h: = 1, ...., I. and μaa ( < ji(t), Since ja exists and dominates μ., this contradicts the definition Pareto optimality.
there exists vector je such that μ
(=)) Let sa, be e-constraint optimal. Suppose the constraint vector is defined as ( = = E [L]. Since μ. is ez-constraint optimal for every & 1, ..., L. there is no other μ E Conv(M) satisfying μ!! < i and p.. < (k) when + f, for every = 1,... L. This holds the definition of Pareto optimality.
(6) for all
Above lemma demonstrates that every Pareto optimal arm is also e-constraint optimal. This equiv- alence also holds for non-convex set. But in the convex set Conv(M), the mean reward vector
19

---

effective Pareto optimal arm satisfies the Pareto optimality in Conv(M), hence, it also satisfies e-constraint optimal. It is enough show that, for any e-constraint optimal vector μ. Conv(M). there exists weight vector E 8 satisfying
argmaax w pe
ConN (M)
To prove above equation, we prove some of the lemmas that are useful for our proof.
Lemma let Q be non-empty convex set R not containing origin. Then there exists vector E 8h such that w 2 0 holds for all μ E Q.
Proof. for p1 M2g .. pm E Q2 define matrix and arbitrary vector as
M = [M
M2 ... uml RR=xL SES.
by convexity of set 12 have M B Ω but 0 of Q. So, there is solution B, satisfying
3 0, E
The solution still do not exist even we remove the constraint || By Proposition | the second condition of Gordan's 's theorem does not hold. Hence, there exist L-dimensional vector w that w μ4 0 holds for all ..., m. Since w is non-zero vector, we can take as EeE (w( 1. Define the
VN (w E R
Σ [E[T]
| = 1, 2 0}.
Then we can write
14 0.
Each set Vi,, is closed and bounded, hence, it is compact set. Since μ4 was arbitrary chosen, the collection (Vi)aa satisfies finite intersection property. So, we have
VU + 0.
EEΩ
Lemma 4 Let QI be non non-empty corvex set in R.,, such that the vector μ E Ω with all negative entries do not exist. Then, there exist vector w S³. such that T p 2 holds for all μ Qt
Proof. For vector μ Ωt define the set
B₁ by E R2 12 > 100 ve [4]}
B = U By
REn
origin is in B, then there exists μ that 0 (t) holds for all & e [4], which contradicts the assumption. If y Bp V/2 B Bug we have
791 + (1 7)92 E BBp,- C B
for 7 E [0. 1]. Hence, is convex set. By Lemma 3 there exist vector w, satisfying w y 2 0 for with large ( so that w y < 0. Hence, we must have ((()) > for all E [L]. Also, since w non-zero vector, we can restrict the vector in unit L-dimensional simplex. We now prove f1 = for all μ E Q. For any positive real e > 0, we have μ + cl E B. If there exist 5 > 0, f with w f -5, we can choose
all y E B. the vector has negative entry w(() < 0, we can choose
é < d, so that
w (1 c1) - 5 0.
Hence, we must have vector w that satisfies w" 2 0 for all Ω, and w E S..
The next lemma is the revision of Generalized Gordan's Theorem.
20

---

Lemma (Generalized Gordan's Theorem) Let Q be non-emprr convex set. Either one of the following statements holds, but not both.
1. There exists μ E Q whose entries are all negative.
2. There exists L-dimensional vector w E S satisfying wi 2 Ofor all Ω.
Proof. (1 + 2) proof follows by Lemma
(2 1) y negative vector, we must have w μ < 0 for all w e s
Lemma 6 For any E Sh, let Ar, be set of optimal arm, that has optimal weight reward given weight vector u, ie.,
A' = arg max w Ma aEA
Then there exists effective Pareto optimal arm a,, such that A
Proof. Suppose there exist w that & A for any E C.. Let â E A'//C* that maximizes w Ma. Since à & C", for every effective Pareto optimal arm a₂ E C", there exist Sa. 2 satisfying
Pa Σ
Ma.
Σ a.
Ba.
R.EC
Since w is vector with non-negative entries, we have
Pa Σ
Ba. w Na S
Σ
Ba, w Pa.
EC
a. EC
We have, at least, one Pareto optimal arm with
w Ma S TT No.
Such existence of a, is guaranteed with existence Bo. 0.
Now, we begin the proof of Theorem
Proof. Suppose a, is effective Pareto optimal. By Equation 44, for any E Conv(M) \ {&aa h
we have Ma, A μu, hence, the vector μa, satisfies the Pareto optimality in Conv(M). By Lemma 2
Ha. is also e-constraint optimal, with ( pa_. such that vector μ Cony(M) {Ma.)
(2)
(k) (k) satisfies pa. 1h < 0 for k = 1,.... I. and Ma. 1h < O for some f. By Lemma since the set Conv(M) is convex, the first statement does not hold. There exists L-dimensional vector w E St.
(E) (9)
satisfying w (Ma. p)) 2 0 for all μ E Cony(M). Hence, we have
a. argmax w pa aEA
Conversly, Suppose a = arg maX w Ha is unique arm. By Lemma 6 the existence of effective Pareto optimal arm implies a E C².
B Analysis of MOLB-TS
In this section, we provide the analysis of the worst-case regret of algorithm MOLB-TS.
We begin with the proof of Lemma]
B.1 Proof of Lemma I
Proof. The parameters ) are sampled from Gaussian distribution ((((()) ... V. Then for any given d-dimensional vector L1,a, we can rewrite this probability distribution as
((0) T fm ~ No 0 (.
21

---

Also, we can see the probability of the event e(e)
et,
P((L, [3m [M] x (0 0,5) c1al|sr,ally-1
= Pm [M] 1m 2 1}
where (1m m sampled from standard normal distribution (V(O, 1). For M 1, the probability of optimism ((E( is bounded below by p. The probability of optimism, satisfying least one sampled parameter, is bounded by
2 (1 p) p)
These optimism events between different objectives are independent. Let the event Ér,a be defined as
E
n
a(E)
Lta
EE[L]
The event Éi, is the optimism satisfying for all objectives E [L]. Hence, we have
P((E,a) (1 (1 p) M
To have ((É,,)) 2 p, we need to choose large enough M so that
(1 (1- (1-(1- )² 2
Rearrange the equation, we get
M log(1 - p1/b)
log(1 p)
log(1 p) -log(1 /1/// p2/b... ... p(b-12/L)
log(1 p)
+ log(1 + p//1 2/11 + +ppl p(1--11/14
log 1-p
With sampling by Gaussian distribution, we have p = 0.15. However, the probability p can be different by choosing different sampling distribution. But, as long p E 1), we have
log L
2 log(1 + p2/L 2244 + p (11-11/L)
log T-p
log T-p
Hence, by choosing M
log L
log 1-P
1
we get P(Er,a) 2
Lemma 1 shows the minimum number of M for the inequality P(εY,a) 2 p to hold.
B.2 Proof of Theorem
Dependence on log L. Before proving Theorem 2 define the events &,, E, such that the true
parameters g. and all sampled parameters (fLm))E are close enough to the RLS estimate
parameters 0.00 for all objectives, respectively.
&, (Ve E [ : 110!
0000 llv ci,(
& (vm [M] AE E [7-] _
0.71 S (,))
where (0) and (0) defined
c,,( = RV doog 1+ (+ 1)d(Ad)
+ 1/22
8/L
2LMdT
(2)(0) co)
2d 2dg
8
22

---

Let ε = N220 &.. By Lemma 8 we have P(E) 2 111& 8, and by Lemma 9 on event E, we have P.(E.) = P(E. 2 1 8/T. The high probability bounds cτ, and c increased by factor of log L due the union bound over the number of objectives. Consequently, the regret inevitably depends on log as this factor arises from the concentration bounds required to hold uniformly over
all objectives.
Bounding the sub-optimality gap. We now prove the following lemma, which bounds the conditional expectation of the regret of MOLB- at round & given the historical information up to that point.
Lemma For any filtration Ft-1, on event E, we have
E
EPR
1+
0.15 (c1,((0) + c2,) Er Bell llv. 1] + T
A mor
Proof. Let BB.a.e..cc be one that maximizes A APPR
A ErRR_ = max min BES BE(L]
Σ EC;
Ba 2 tto. 0!!0)
Fi (())
Σ R.ECT
Bra oi, 0/0)
Itaar o5
min EE
Let we be the weight vector unit L-simplex sampled, described in Section 5.2 Then,
min EPR
Σ
Be,a "ia 0500)
060)
Liaa o
EE(T]
Σ C.ECi
Br,a F 2 8!0))
x g
EE[L]
Σ Br oia
Σ RE(L]
Wi (0)0
(2)
Σ wi (
1t
E.EC;
(E(L)
By Theorem there exists a. E C satisfying
Σ SE(L]
(()
0. = arrgaaaxxx
2i,0 aEA
Wi
Hence, we have
EPR
Dt
<
Σ
Br Lia
Σ wi EEIL
tta0
Σ
wi 10) 050)
(5)
ECi
(E(2)
S Ttaa-
Σ
we
(0
g(e)
I Dttas
Σ (8)
g(
(6)
BEIL
NELL]
From M multiple sampled parameters, we define g(e) a. as optimal sampled parameter with arm a, i.e.
g(
argmax(# g(t) x g(0) (...... T (..)
p..m
At round f, the arm is evaluated with the sampled parameters g for all & E [4]. As described
Section 5.2 we can write a., ag as
Σ w
a argmax BEA
tta
[E|L]
T 44 argmax Ft a
(1)
g(0)
[E[L]
23

---

Let cτ() (6) + C2,( We separated arms into two sets with given weight vector, saturated and unsaturated 4
B, set of saturated arms, that is, for all a E Br, we have
r,a.
Σ FE[T
Σ [E(M
wx
g(
ce(5)]lzaally
B, set of unsaturated arms, that is, for all a E Br, we have
Σ PE(T.]
wi (2) 100!!
Σ [E(T)
(8) wi
Iza
Note that w; is random variable, since the arm dj is uniform randomly selected from C. Hence, those of saturated and unsaturated arms (B,, B,) are not fixed. Let ag argmin || lly, be arm in B, with smallest matrix norm. From Equation (6). bounding the sub-optimality gap AEPR on event & and &,, we have
A EPR < 2t,a.
Σ
w
100
ol!)
Ft
T
Σ
Wy
(1) (())
[E(T)
PEiT
Σ FE(T.
w/ o
T + Ft
Σ
(2)
Ft.a.
[E(T]
T Ft,0t
(E) we
(
(
(())
Fta
Wi
[E[L]
PE|L
For any arm a, by the Sauchy-Schward inequality of matrix norm, we have
Σ
79))))
Σ w/
S I
Σ
w/ 10 - 08211v,
tta
wi
a.t
(E|L]
(E(L)
REIL)
And by triangle inequality of norm, we have
Σ
w (6)
6!" llv. S Σ w( (1019) σ lv. + -1000- -
(E[L]
8E|L]
And lastly, on event & and E,, we get
11057 Ilv: + 110/0 0!0 I (c1,((0) + (2)())))=))))==)) (
In total, we get
T
Σ
(1)
-IT Σ
Σ un
c.(6)llz.olll
Itaa
wi
<
FE(L]
(E(L]
(E
24

---

Hence, on event & and Es,
T A EPRR I 1,a
Σ tE|L]
w
(9)
Σ Wi
g(t)
+
Σ we
cx( (.
FE|L]
tEla)
1t++
wi
(2)
g(
2 2i
Wi
(E)
g(e)
Σ (() KELL)
a(6)]l=2,a1lly
tE(2)
(EIL)
Fi,00
Σ rE(T.
W
(0)
g
Σ (E(T)
Wi
(0)
(1)
+c((8)|22,,al11
Ft,ās
We
(8) g(())
Li,a
T
(8) 0(0) wi
+c((0)l2x.aelly
LE(L]
FE(L)
Since
Σ NE[L]
(1) g(t) W/ a.t
4+ argmax aEA
we have
A EPR < Ft,.
T
Σ FE(T)
Li,
Σ [E(T.]
wi 10!!
at
s (2)(0))l + (=(0)]l=r.ailll
where the last inequality holds since ā, is unsaturated arm. This inequality holds on event & and &. Define the conditional probability F. P(- Fe). Then, on event E, we have
E2 CPR < E, (6) llv. + et ( llv, +I+ (I-Pr1E:)) mar
< E,12c, (0) b (6)) Ilv. + 5
T Amax
We bound the term E. a, [ with [ We have
E. 11 [ly. 2 Bell ll. a E B.J.Prfa, E B,) 2 Il E B.}
The probability Pr(aa E B.} has randomness over algorithm selecting arm from empirical effective Pareto front C. where the set B, varies on this random selection. More precisely, the set B, and B change as we changes. But, for any given w;, the probability Pr (a= E B.} bounds below by the probability that at least unsaturated arm is evaluated higher compared all saturated arms, i.e.,
Pila, B.) > P. Da B. LT
Σ W
(0 (
Σ
(E)
(L0)
max Li a'EB,
wi
KETT
FE
where the unsaturated arm exists by a, E Br, Hence this probability bounds below by the probability that the arm a evaluated higher compared all saturated arms, i.e..
}
Po(ar Bd) P
L...
Σ
( W
g()
max ah.a' e'eBs
Σ EELL]
W (C) 10) (d/1
EEIL]
On event é,, those saturated arms a' E B, satisfy
Σ
(0)
T
Σ
(0) 10!0
c1(6)l=2e.0111 Ilv."
KE[L]
[E[L]
25

---

and
Σ
w
((1))
(2)
(())
Σ LE|L]
w/
(8)
KE[L]
Subtracting Equation
from Equation
we get
T tta
Σ
Wi
(0)
F 2,0'
Σ
(4)
g(t)
att
2 0.
RE[L]
REIL)
for all d' E Bt. Using this inequality, the Probability bounds as
Prfa E Bit 2 Pe
Lta..
Σ EEIL
wi
(1)
g( Bunt
> T
Lta
Σ
w g!0
REIL)
}
T 2 Pr
Σ
(E)
0(0) Bo.l
Σ
(E)
(1 - Pr(E))
Lt..
wi
> Lzz..
we
EE
FE(T.
Since (!1)) a.,
objective wise independent, the probability bounds by objective wise probability,
} n
Pr
T Tt..
wi
g(e)
a.dt
>
T Lta.
Σ
Prizia. 0.. > xT,aa 0.413
EEIL
RETL]
RE|L]
Removing the random vector wy, this incquality holds for any wt. In other words, this inequality holds for any random selection arms from the set C. Hence, we get
Pr(ar [.)
N rE(r]
0.0 (1 (-P(((E)))
2
n EE[L]
Pr Pitzia, 009 > 21,a, 2T,a,00 060)
T
Pafaa d!! > a, 0
0
8 T
As we remove w., the probability Pr(ar B.} gets exponentially small as the number of objective increases. We remove this by adopting optimistic sampling strategy. With the number multiple samples M, following Lemma
we have
P. T00 > Fta. 000) 2 11-1-pppp
Hence, we get
Pe(a, BB) 2 (1 M3
5
T
This inequality holds for any w. With M =
log & log pp
we have (1 - (1-p) 2 Finally,
have
8 Ey Fe | 2 Ara.lly. (p- (P-n) T
Replacing the term
| | to ||<
11, we get.
2 # p
(6) llv, + 8
E, A EPR
1
T Amax
T
26

---

given filtration Fe for any Now we begin the proof of Theorem
2
Proof.
We have
T
[|EPR(T)) = Σ
E
EPR
t=1
P(())
EPR 11 (E} + (1 - P(E))
PA BI d2
11 [8]] + 8.max
1(88) + 6m
ae
By Lemma bounding the term E, A
EP have
2
[[EPR(T)
(. 21 11y-))1(EE) -20
0.15
T CT (
E|
E, Ft 11 [1{E]] +225m
0.15
T
+
cr (
|| 1l4-11 + 252
0.15
2
2T 1+ (+7))==
T)
+
cr(
+ 28A max
0.15
where the last inequality follows by Proposition
C Additional Technical Tools
Proposition 1 (Gordan's Theorem, page 31, Mangasarian 12) For given matrix M RR ei- ther one of the following statements holds, but not both.
There exists T--dimensional vector w, that Mu has all positive entries.
2. M B 0, 3 0 has solution R
Proposition 2 (Lemma 11, Abbasi-Yadkon et al. a Let A 2 1.
For arbitrary sequence
)EETT we have
T
T 1
I 1R, < 2d 1
Lemma (Theorem 2, Abbasi- Yadkori et [I Let (Fi)20 be a filtration. Let (g. be a real- valued stochastic process such that e! is conditionally é E [L]. Then with probability at least 1 1 ô, the event
VL E [L] 11000 - 10 s R dlog dlog ē=
1+ (t (1-1/(A) + 41122
5/1.
holds for all 1.
Proof. By Theorem 2 in Abbasi- Yadkori et al. (1. and union bound with L.
27

---

Lemma (Definition 1, Abeille and Lazaric 2) On event & with probability at least 5, all sampled parameters (0 (411)11)))) follow concentration property, i.e.,
1+ (t (1-(1)/(Ad)) ) A2/2 }
== 110 1lv. for all E [M]e E [T].
2LMd 8
2d
RV dog
6/L
Proof. By Definition in Abeille and Lazaric
2 and union bound with M and L.
D Discussions
Our proposed algorithm demonstrates strong empirical performance with various settings. But its theoretical worst-case regret bound is not tighter than that of UCB-based algorithms. This gap between UCB-type algorithms and TS algorithms is well-known in the regret analysis of previous algorithms 4 [2] bounding the worst-case frequentist regret.
Our work studied under the standard linear contextual bandit setting. Our framework can readily extended to generalized linear contextual bandits. Extension more complex function class such as neural networks requires analysis that is beyond the scope of this work, but is certainly the promising avenue for future work.
Yet, our work introduces the first randomized algorithm with Pareto regret guarantees in the multi- objective bandit framework. We hope that our work lays foundation basis for extending such techniques follow-up works.
E
Computing resources for experiments
All experiments are conducted with INTEL(R) XEON(R) GOLD 6526Y CPU and 4 TB memory. The software environment includes Python 3.17.7, Scipy 1. 1.14.1, and Numpy 1.26.4. The experiments took approximately 4 hours day, it takes longer with increasing numbers of arms, dimensions, and objectives.
28

---

Additional experimental results
objective I
objective 3
Lattete Rower
0000
8000
Parto Maget
Paroo Riper
9000
2000
60
Cimulabe
3000
2000
20
1000
1000
2500
5000
7900
10033
2000
2000
7000
10000
2003
1000 7500 10000
2500 5000 7900 1000 Bound (9)
Round
Road
Roand (4)
objective
2
objective =
0000
5000
Ettooive Partoo Regeet
ETfutive Parto Rearee
Cum Letie Rowad
0000
4000
9000
5000
Lake
3000
2000
55
1000
1000
2500
1000
7000
1003
2900
5000
7000
10000
2003
1000
7500
10000
25000 5000
1990 1000
Round
Round
Round (4)
Round (1)
Figure Experimental results with K = 50, d= 10, L = 4
HOL-LCE
Vol-is
MCDFFS
objective
objective
110)
Cumuar ke llwood
Parto Regett
1500
1500
2000
2000
Farsto
15
2500
5000
7300
10000
2000
5000 7300 10000
2000 5000 7500 10000 Round (4)
2000 500D 7300 10000 Round (6)
Round (4)
Round (6)
objectivn
objective
118)
Effectee Parcio Regis.
Combkntu llwood
8500
2500
Elfectie Purts
Comuenttrr
2000
2000
10
1500
2500
5000
7300
10000
2000
1000
7300
10000
2500
5000
7500 10000
2000 500D 7300 10000 Round (6)
Round (4)
Round (6)
Round (4)
Figure Experimental results with K 100, d 5, L 4
VOL-R5
objertive
objective e 3
3000)
Partoo Regett
26
Cumbatue Rowced
4000
4200
2000
2000
Pando
Hound
(4)
objective
objective i
3000
Eltecte Parcto Rogget
70
Cimiattar Boweed
1000
60
2000
2000
Effectiv
(4)
Figure 5: Experimental results with K = 100, d = 10, L =
29

---

objective
objective d' =
Cumdattn Bronm
Parto Roges
1100
2000)
2000)
Facto Roant
100
2000
2000
1000
2001
7500
2000 7500
10200
0000 10000
objective
objective
Effectee Parto Raget
Parto Rupot
Comitette Brond
1100
3000
2000
2000
2000
Round
Figure 6: Experimental results with K = 100, d = 15, L = 4
VOL-75
objective
objective
6000)
6000
100
Downrd
Parso Reget
100
2000)
2000
1000
1500
27401
5000
7500
10300
2001
5000
7500 10000
2000 DAED 7300 1930
2003 5000 7300 10000
Hound
Hound (4)
Hound (4)
Hound (4)
objective
objective
6000
100
Eltccles Rartto Rightt
Eumaativ Dbweed
Ragest
100
3000
2000
2000
2000
7500
10300
2003
5000 7500 10000
2000 5000 7500 10300
2000 500D 7300 10000 Hound (4)
Hound
Hound (4)
Hound (4)
Figure Experimental results with 200, d 10, L=
LEA
MOLTS
objective
objective
200)
6200
100
Comubrtte Resent
Paddo Raget
150
4200
4500
50
1500
1500
Round
Round (4)
(4)
(4)
objective
objective
(00)
6000)
6000
Eftaciee Parto Reges
Grrubortee Roaar
Rouns
150
4500
1500
50
1200
1500
5000
7500
10000
2000
5009 7000 Round (6)
10000
2500
5000
7500 10000
2500 5000 10000 Round (4)
Round
Round (4)
Figure 8: Experimental results with K = 200, d = 15, L 4
30

---

MOT
175
175
Ragnet
Panto Reget
75
720
30
500
25
10.0
6500
10000
2000
3000
(0000
10000
objectiive
Comubriee Reward
Canusbbie Roward
Round objectivv
objective
Cumubrie Reward
Camulibiee Roward
Cam ton Rescrr
Figure 9: Experimental results with K 500 d = 5, L 8
31

---

Ragst
Parto Reges
126
225
000
200
2000
6000
80000
10000
3000
4000
(000)
1000)
Round (1)
Rounel (4)
objectivn
objective
objective
abjechioe
Combatio Breard
Cumuuativ Roward
2.0
3,00
Combbttin
0:00
3:40
8000
1000
D00
1008
020
800
1000
1000
1700
Round (3)
Round (5)
Round (3)
Round (5)
abjjctivon 5
objechive /
objective
abjjcciio 8=88
Combatii Broard
Camuaatio Roward
Combittin Braxnd
2.0
3:40
30.0
C203
1000
4:30
D000
1000
0300 (3)
000
.000
4:10
1000
1900
Round (3)
Round (5)
Round
Round (5)
Figure 10: Experimental results with K 100, d 10,
HOL-igeedy
VOL-UCE
MOLLTS janr
Dagest
Parto Reget
2000
1000
6000
8000
10000
2000
4000
0000
8000
10000
Round
Round
Comubative Rerword
Canulaivee Rovord
4mm
bxx
box
kmo
2000
1201
1900
18:00
2010
1300
5000
2.00
2.00
2000
0.00
10.00
10.00
130.0
Rzund (+)
Round (1)
Round
(1)
Round (1)
Figure 11: Experimental results with = 100, d = 10, L = 4, linear (non-contextual) setting.
32

---

Rayes
Pareo Reges
126
-25
000
200
6003
8000
10000
3000
4000
(000)
1000)
Round (1)
Rounel (4)
objjctivw
objjchive
objective
objjechion
Combatio Breard
Cumuaativ Roward
240
3,00
Combittii
0:00
3:40
100
80.00
1000
380
D00
1008
300
1803
0200
600
1000
6000
1000
1700
Round (3)
Round (3)
Round (3)
Round (5)
abjjctivnn 5
objechive d
objective
abjechioo 8=88
Combatii Broard
Camuaatie Roward
2.0
1000
3.00
Combitiin
3:40
2000
0203
.000
2300
4:30
D000
1000
0200
000
.000
4:10
1000
1900
Rourd (1)
Round (3)
Round
(3)
Round (5)
Figure 12: Experimental results with K 200, d 15,
HOL-igeedy
VOL-UCE
MOLLTS
Dagest
Parto Reget
2000
1000
6000
8000
10000
2000
4000
0000
8000
10000
Round
Round
Comuintive Rewurd
Canulaive Rovord
box
aum
100
X000
2000
1203
1000
18:00
2000
1000
5000
2.00
2.0
2003
0400
80.0
10.0
150.
Round (+)
Round (1)
Round
(1)
Round (1)
Figure 13: Experimental results with = 200, d = 15, L = 4, linear (non-contextual) setting.
33


Reviews:
[{"review_id": "5FxNjzrWtR", "reviewer": "Reviewer_bJq2", "summary": "The paper studies the multi-objective linear contextual bandit problem. The paper introduces a new concept effective Pareto regret and proposes a Thompson sampling based algorithm relying on the principle of optimism, The paper proves the effective Pareto regret (hence the Pareto regret) of the algorithm. The paper concludes with experiments.", "questions": "1. This is still on the problem of $L$. I am curious why in the appendix if we keep $L$ the same, the difference between $M=1$ and $M=\\log L$ is larger when $d$ is larger? \n2. I am also a bit confused about why $M=1$ does not seem to be that bad given the algorithm relies on optimistic sampling.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n1. Significance: The paper establishes the first TS based algorithm with worst case Pareto regret guarantee, and the regret bound matches the best known order that in the single objective setting. The multi-objective is very common in real word scenarios but less studied.\n2. Clarity: The presentation leading up to the introduction of the algorithm is very clear for someone like me who do not have the extensive background in multi-objective settings. \n3. Originality: I really like the optimistic sampling intuition\n\nWeakness: \n1. I think this is minor but I think it would be interesting to see some stretch analysis on the number $L$ in the appendix (or in the main text). Is there any reason that you omitted the comparison between $M=1$ and $M = \\log L$when $L=8$ in the appendix? What if $L$ keeps getting larger.", "was_revised": true, "final_justification": "All my concerns are resolved and I vote for acceptance.", "rebuttal": "We thank the reviewer for taking the time to review our paper. We sincerely appreciate the insightful comments, particularly the recognition of the optimistic sampling. We view this as an excellent opportunity to further clarify and strengthen our contributions, ensuring a more thorough understanding of our approach and its implications.\n\n**Streching Analysis on the number $L$** : We thank the reviewer for highlighting this issue. We will gladly revise the technical lemmas in Appendix C to provide a more detailed explanation of how the number of objectives $L$ affects the regret analysis of our algorithm.\n\n**The Comparison between $M=1$ and $M=\\log L$, for $L=8$** : We are also grateful for this feedback and happy to show our results. Due to the limited space (by large number of objectives), we omitted the comparison between $M=1$ and $M=\\log L$. We will add the results of additional experiments comparing these two settings. However, when $L\\ge8$, the results demonstrate that Thompson Sampling with optimistic sampling clearly exhibits lower effective Pareto regret. The following table is the experimental results of total regret when $L=8, 12$ and $T=10000$.\n\n| Pareto Regret $(L=8)$ | $M=1$ |$M=O(\\log L)$ |\n|----------|----------|----------|\n| $d = 5$ | 3.72 | 3.29 |\n| $d = 10$  | 10.53 | 8.81 |\n| $d = 15$  | 24.39 | 17.84 |\n\n| Effective Pareto Regret $(L=8)$| $M=1$ |$M=O(\\log L)$ |\n|----------|----------|----------|\n| $d = 5$ | 4.53 | 3.89 |\n| $d = 10$  | 13.81 | 11.39 |\n| $d = 15$  | 32.16 | 23.96 |\n\n| Pareto Regret $(L=12)$| $M=1$ |$M=O(\\log L)$ |\n|----------|----------|----------|\n| $d = 5$ | 2.42 | 1.57 |\n| $d = 10$  | 6.59 | 4.15 |\n| $d = 15$  | 11.87 | 8.73 |\n\n| Effective Pareto Regret $(L=12)$| $M=1$ |$M=O(\\log L)$ |\n|----------|----------|----------|\n| $d = 5$ | 2.96 | 1.91 |\n| $d = 10$  | 8.86 | 5.43 |\n| $d = 15$  | 16.45 | 11.97 |\n\n**The difference with respect to $d$** : As the dimension $d$ increases, the theoretical worst-case regret increases as well, due to the higher uncertainty in the parameter estimation. Empirically, this behavior is consistent with our experiments, as the regret gap between $M=1$ and $M=\\log L$ grows more significant.\n\n**Why $M=1$ does not seem to be bad?** : The worst-case theoretical regret bound does not imply that the algorithm must fail to the worst-case empirical results. It is essential to note that without optimistic sampling, the theoretical worst-case regret could grow exponentially. We resolve this issue by adopting optimistic sampling in $\\texttt{MOL-TS}$, which mitigate the potential for exponential growth in regret. However, the empirical results do not necessarily be the worst-case scenario. While optimistic sampling still achieving better outcomes empirically, optimistic sampling is employed in $\\texttt{MOL-TS}$ to resolve the theoretical issue and ensure better performance in the worst-case scenario."}, {"review_id": "H2DPgFlIUk", "reviewer": "Reviewer_fjDD", "summary": "The paper studies the multi-objective linear contextual bandit problem, where a decision-maker (or learner) must simultaneously optimize several potentially conflicting objectives. The goal is to learn a policy for selecting an effective Pareto optimal arm (Definition 5) for each given context, whose mean reward vector is Pareto optimal and maximizes the cumulative rewards across all objectives. The performance of the learned policy is measured in terms of minimizing effective Pareto regret (Definition 7), which is the sum of effective Pareto sub-optimality gap (defined in Eq. (1)).\n\n\nThe authors propose a Thompson sampling-based algorithm,  MOL-TS (Thompson Sampling for Multi-Objective Linear Bandits), for this setting with sub-linear effective Pareto regret guarantees. This paper introduces the notion of effective Pareto front, which consists of arms whose selection maximizes the total reward. The authors have also validated the performance of MOL-TS using synthetic problem instances and show that MOL-TS outperforms baseline algorithms in both regret minimization and cumulative objective-wise rewards.", "questions": "Please address the weaknesses raised in **Strengths And Weaknesses***.", "limitations": "I have raised a few limitations of the paper in my response to the **Strengths And Weaknesses***. Since the paper is a theoretical contribution to bandit literature, I do not find any potential negative societal impact of this work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "#### **The following are the strengths of the paper:**\n1. This paper studies the multi-objective multi-armed bandit problem, which has applications in many areas, especially having several potentially conflicting objectives. \n\n2. This paper proposes a Thompson sampling-based algorithm, MOL-TS, to learn a policy to select the best effective Parato optimal arms for each context. They have theoretically shown that MOL-TS enjoys a sub-linear regret guarantee while choosing a better arm that maximizes the total reward.\n \n3. The authors have also empirically validated the performance (lower regret and higher cumulative rewards) of MOL-TS using synthetic problem instances.\n\n\n#### **The following are the weaknesses of the paper:**\n1. **Assumption:** Assuming a linear reward function may not be practical in real-life applications. Since there has been a lot of work considering the non-linear bandit setting, it would be much better to have a more practical algorithm by considering a general reward function.\n\n2. **Selecting the best arm:** Selecting an effective Pareto optimal arm can lead to a better performance than simply selecting a Pareto optimal arm. Since there can be multiple effective Pareto-optimal arms, it is unclear how to choose a single best arm among them. Doing this may need additional constraints, but it may make it more practical, as one can explain why a specific effective Pareto-optimal arm is selected. Otherwise, different effective Pareto-optimal arms may lead to different values of the objectives.\n\n3. **Analysis novelty:** The multi-objective linear contextual bandits and Thompson sampling-based bandit variants are now separately well-studied problems. From the paper, it is unclear what the key challenges are faced in the regret analysis, especially after getting an upper bound on the effective Pareto sub-optimality gap in Section 5.2.", "was_revised": true, "final_justification": "The authors’ rebuttal has addressed my concerns. Overall, this paper proposes, for the first time, a Thompson sampling–based algorithm for the multi-objective contextual bandits setting. This work can serve as a fundamental building block for designing bandit algorithms in more complex real-world applications, including modeling nonlinear objectives or incorporating refined criteria for the optimal arm from Pareto optimal arms.", "rebuttal": "We would like to sincerely thank the reviewer for taking the time to review our paper. We address the feedback you provided point by point below.\n\n**Why linear assumption?** : We appreciate the reviewer’s feedback regarding the assumption of a linear reward function, but we believe this is not a fundamental weakness of the paper. Analyzing Thompson Sampling in multi-objective bandits (particularly in contextual bandits including linear and generalized linear settings) has remained as an open problem, and to the best of our knowledge, for the first time, our work presents a fundamental milestone in the development of randomized algorithms with the (worst-case) Pareto regret guarantees in multi-objective linear contextual bandits. \n\nThe focus of our paper is providing the first randomized algorithm, with Pareto regret analysis and empirical validation in linear reward function. Extending our approach to the (non-linear) GLM is straightforward. Hence, our results aren't limited to linear settings. Further extension to handle more general function class is certainly an interesting direction. However, it is important to note that the optimistic sampling that we propose for Pareto regret analysis can be naturally generalized to other non-linear reward functions. Our work is a noteworthy contribution that sets the foundation for future work with more complex settings.\nOverall, the fact that we have solved this long-standing open problem in the multi-objective linear contextual bandit should be considered a notable contribution, rather than considered as a weakness.\n\n**What is a best single arm?** : In multi-objective bandits—and, more broadly, in multi-objective optimization—a single best optimal solution is generally **not** guaranteed to exist. As noted in our Introduction, multiple objectives often conflict, so improvement in one objective can degrade another. The appropriate notion of optimality is therefore Pareto optimality: the set of solutions that cannot be improved in any objective without worsening at least one other.\n\nIf a unique “best” arm did exist under some scalarized criterion, the problem would degenerate to a single-objective bandit setting—contradicting the essence of multi-objective learning. Prior work thus focuses on identifying the Pareto-optimal set (the Pareto front), where each arm is non-dominated by the rest.\nHowever, simply enumerating Pareto arms does not address how to maximize cumulative reward across all objectives. Our contribution is to introduce effective Pareto-optimal arms, together with an algorithm that attains sub-linear regret for this richer goal. This adds a fresh perspective to the multi-objective bandit literature.\n\nShould one wish to impose problem(or user)-specified weights and reduce the problem to a single scalar objective, our algorithm naturally specializes to that case and still guarantees sub-linear regret. Nevertheless, that scenario is not the focus of this paper, and therefore it should not be viewed as a weakness of our work.\n\n**Technical challenges in analysis** : \nWe are happy to elaborate on this. First of all, a simple, straightforward combination of Thompson Sampling (TS) techniques with existing analyses for multi-objective linear contextual bandits is not sufficient for multi-objective linear contextual bandits\nThis gap explains why no worst-case regret analysis of TS currently exists for this setting.\n\nAs explained in Section 5.3, one of the key technical challenges in deriving the regret bound of Thompson Sampling algorithm for multi-objective linear contextual bandits lies in ensuring the probability of optimism. Previously, there are many papers of multi-objective UCB-type algorithm with Pareto regret analysis (Drugan & Nowe (2013), Tekin & Turgay (2018), Turgay et al. (2018), Lu et al. (2019), Xu & Klabjan (2023)). The analysis of UCB algorithm is almost similar to that of single objective setting, attaining Pareto regret bound $\\widetilde O(d\\sqrt{T})$ where the number of objectives depend up to logarithmic factor. \nBy contrast, deriving comparable guarantees for TS in the multi-objective linear contextual setting remains an open problem, and our work is the first to tackle these technical obstacles directly.\n\nSuppose we follow standard Thompson Sampling algorithm, by setting $M=1$. Widely known in single objective setting $(L=1)$, the probability that $\\tilde\\theta_t^{(1)}$ is sufficiently optimistic is $\\mathbb{P}\\bigl( x_{t,a_t}^\\top(\\tilde\\theta_t^{(1)}-\\hat\\theta_t^{(1)})\\ge c_{1,t}(\\delta)\\lVert x_{t,a_t}\\rVert_{V_t^{-1}} \\bigr) \\ge \\tilde p$, where $\\tilde p$ is a constant probability. In multi-objective setting $(L>1)$, as the arm is randomly selected, this optimism must hold for all objectives. For any randomly selected arm, we need to ensure this optimism for all parameters $(\\tilde{\\theta}\\_t^{(\\ell)})\\_{\\ell\\in[L]}$, i.e., $\\bigcap_{\\ell\\in[L]}\\mathbb{P}(x_{t,a_t}^\\top(\\tilde\\theta_t^{(\\ell)}-\\hat\\theta_t^{(\\ell)})\\ge c_{1,t}(\\delta)\\lVert x_{t,a_t}\\rVert_{V_t^{-1}})\\ge \\tilde p^{L}$. In the worst-case, this results in the regret bound $\\displaystyle\\widetilde O(\\frac{1}{\\tilde p^L}d^{3/2}\\sqrt{T})$, which become exponentially large as the number of objectives $L$ increases. \n\nThe optimistic sampling resolves this problem with multiple sampled parameters. Suppose $M>1$. For each objective $\\ell\\in[L]$, there are $M$ sampled parameters $(\\tilde\\theta\\_{t,m}^{(\\ell)})\\_{m\\in[M]}$. The arm is evaluated with the sampled parameter that maximizes the evaluation, i.e., $\\tilde\\theta\\_{t,a}^{(\\ell)}=\\arg\\max\\_{\\theta}\\{(x_{t,a}^\\top\\tilde\\theta\\_{t,m}^{(\\ell)})\\_{m\\in[M]}\\}$. Then, the probability bounds for optimism become $\\mathbb{P}(x_{t,a_t}^\\top(\\tilde\\theta_{t,a}^{(\\ell)}-\\hat\\theta_t^{(\\ell)})\\ge c_{1,t}(\\delta)\\lVert x_{t,a_t}\\rVert\\_{V_t^{-1}}) \\ge 1-(1-\\tilde p)^M$. Following above steps, we have the probability of optimism at least $(1-(1-\\tilde p)^M)^L$. We choose large enough $M$ so that this probability is bounded below by $\\tilde p$. \n\nWe modify Thompson sampling algorithm with optimistic sampling to ensure the optimism and attaining the regret bound $\\widetilde O(d^{3/2}\\sqrt{T})$. Addressing this challenging problem requires the development of a novel approach and perpectives.\nWe would be more than happy to include more explanations in Section 5.3 in the final version to further strengthen our contributions.\n\n**Overall remarks** : We appreciate the reviewer’s feedback, but we do not believe the points raised constitute fundamental weaknesses of our paper. We are confident that our work makes substantial contributions to the multi-objective contextual bandit literature and respectfully ask the reviewer to re-evaluate our work in light of our clarifications.\n\nIf any questions remain, please let us know, and we would be more than happy to provide further explanations."}, {"review_id": "6vipX3VUEt", "reviewer": "Reviewer_dCvZ", "summary": "This paper studies the multi-objective linear bandit problem, which extends traditional linear contextual bandit problems by requiring optimization across multiple, often conflicting objectives simultaneously. In this paper, the authors proposes MOL-TS as the first randomized algorithm for multi-objective contextual bandits with Pareto regret guarantees, achieving $O(d^{3/2}\\sqrt{T})$ regret. Also, this paper firstly introduces \"effective Pareto optimal arm\" that not only satisfies standard Pareto optimality but also ensures total rewards across all objectives remain Pareto optimal with repeated selections. Numerical experiments demonstrate improved performance in both regret minimization and objective-wise total reward maximization", "questions": "In feel-good TS[1], it is shown that for standard linear bandits, the regret upper bound is $O(d\\sqrt{T})$, which matches with the UCB-based approaches. Can similar techniques be applied in multi-objective linear bandit settings to achieve a tighter bound?\n\n[1] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n - This research addresses multi-objective bandit literature by introducing the first Thompson Sampling approach with theoretical guarantees. \n\n- The algorithm sample multiple models from the posterior distribution and compute an optimistic reward estimation to adapt to the multi-objective setting, which is novel.\n\n - The effective Pareto optimality concept provides a more robust framework for multi-objective optimization, ensuring better long-term performance across all objectives rather than just instantaneous optimality.\n\nWeaknesses\n- The regret bound achieved by this paper is $O(d^{3/2}\\sqrt{T})$, which is worse than UCB-based approaches for multi-objective linear bandits.\n\n- It would be better if the authors also discuss how to modify the previous approaches so that they could work for the new definition of Pareto optimality.", "was_revised": true, "final_justification": "The authors' rebuttal helps me assess this work better. I will keep my original score.", "rebuttal": "We sincerely thank the reviewer for taking the time to carefully review our paper. We especially appreciate the positive comments on the strength of our work, especially acknowledging optimistic sampling.\n\n**Regret bound of $\\widetilde{O}\\bigl(d^{3/2}\\sqrt{T}\\bigr)$ and possible adaptation of Feel-Good TS**\n\nWe are happy to answer this. First, the regret bound of  $\\widetilde{O}\\bigl(d^{3/2}\\sqrt{T}\\bigr)$  for our algorithm—viewed as a member of the LinTS family—is *not improvable* in terms of the $d$ dependence. Hamidi & Bayati (2023) [1] show that Linear Thompson Sampling incurs an inherent posterior-variance inflation by a factor of $\\sqrt{d}$, leading to a frequentist regret lower bound of $\\widetilde{O}(d^{3/2}\\sqrt{T})$ is the best possible for LinTS-type algorithms. If not for such an inflation, LinTS-type algorithms would incur a linear regret in $T$ [1]\n\nOur work extends this single-objective result to the multi-objective setting, and the bound we obtain remains consistent with these fundamental limitations of LinTS.\n\n[1] Hamidi & Bayati. “On Frequentist Regret of Linear Thompson Sampling” (2023).\n\n\nAdapting *Feel-Good TS* is indeed intriguing. However, even in the single-objective case, adding the *Feel-Good* exploration term typically requires **approximate MCMC** to sample from a non-conjugate posterior—unless strong distributional assumptions are imposed. Because we assume only classical sub-Gaussian noise, such sampling would introduce significant computational overhead.\n\nFor these reasons we base our algorithm on LinTS techniques. Extending *Feel-Good TS* to the multi-objective setting is an interesting avenue for future research, but lies beyond the scope of the present work.\n\n\n**Previous methods and our new notion of Pareto optimality**:\nWe are happy to revise the discussion to clarify how our newly defined concept—*effective Pareto optimality*—can benefit existing algorithms as well. Existing multi-objective bandit methods typically sample directly from the standard Pareto front, which can lead to inferior cumulative rewards across objectives. Replacing that step with our notion of effective Pareto optimality could improve the performance of those algorithms as well as our own, further underscoring the contribution of this work."}, {"review_id": "YltAZerpws", "reviewer": "Reviewer_EmBN", "summary": "The paper proposes a Thompson sampling (TS) based approach for multi-objective linear bandits, with the goal of optimizing the effective Pareto regret. The authors define this new notion to overcome the issues associated with measuring cumulative regret using the Pareto regret idea. The algorithm (MOL-TS) essentially takes multiple samples from the posteriors to construct a randomized optimistic confidence bound for each arm, based on which the effective Pareto front is determined at that round, and action is taken randomly from this front. The paper establishes a $\\tilde{O}(d^{3/2}\\sqrt{T})$ worst-case regret bound, which matches the lower bound for single-objective linear bandit TS.", "questions": "1. The optimistic TS using $M$ samples basically behaves like a UCB-type algorithm, by taking large number of samples and taking the maximum, this maximum (for large $M$) behaves like the mean added with an upper confidence term, depending on the Gaussian tail and $M$, however unlike UCB it is slightly randomized (amount of randomization controlled by $M$) - can the authors provide any comment on this connection?\n2. Can you explain why for each individual objective, greedy outperforms UCB, but somehow the Pareto regret is way better for UCB (in Figure 2)? This figure is misleading and leads to question the effectiveness of the Pareto regret (and effective PR) notion.\nAppendix is missing - proofs and other experimental details.\n3. Can you be more explicit in the regret bounds in the orders of dependence on $K$ and $L$? Is the bound tight in these? Also, it might be good to show the dependence on $M$ (or $p$) in theorem 2 and corollary 1.\n4. [Contextual Bandits with Linear Payoﬀ Functions by Chu et al. 2011] shows lower bound for linear contextual bandits (single-objective) of the order $\\Omega(\\sqrt{Td})$ and a matching upper bound (up to log terms). For TS, the recent [Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits by Luo et al] used a slight modification of TS to achieve this regret bound for randomized algorithms. Even in the high-dimensional case, the dependence on dimension and sparsity for TS is $O(s\\log d)$ (e.g. [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits by Chakraborty et al.]), demonstrating better dependence on dimension (stochastic setting). - in the current paper, the dependence on $d$ seems to be slightly higher at $d^{3/2}$ - can the authors comment on this? At least the authors should include a brief discussion on single-objective regret bounds in the literature to claim “best known order for randomized linear bandit algorithms for single objective”.\n5. What is the parameter $\\delta$ in the algorithm 1?\n6. From a practician’s perspective, how do you tune all the hyper parameters in algorithm 1. Theoretical results give some indication on $M$, but what about the others, in particular $\\lambda, c$ and $\\delta$? Did you tune these parameters for the numerical experiments? If so, did you tune the associated parameters for greedy and UCB based methods for a fair comparison?", "limitations": "See the questions.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is well-written and the results are promising. However, due to the missing appendix, the proofs cannot be verified and experimental details are missing at present.", "was_revised": true, "final_justification": "I increased my score based on the authors responses.", "rebuttal": "We thank the reviewer for your time reviewing our paper. We sincerely hope that our answers can help clarify your questions.\n\n**The appendix has been uploaded.** We would like to respectfully clarify that **the full appendix, containing all proofs, experimental details, and additional experimental results, has been submitted as part of the supplementary material**. Every theoretical claim made in the main paper is rigorously proved in the appendix, and our empirical evaluations are documented in detail. \n\nWe sincerely hope that, in light of this information, the reviewer might reconsider any concerns based on the (unintended) mistaken assumption that proofs or technical details are missing. We are concerned that an evaluation influenced by this misunderstanding could inadvertently affect the overall assessment of the well-prepared paper. We greatly appreciate the reviewer’s time and thoughtful engagement, and we are happy to point to any specific section of the appendix upon request.\n\nWe provide answers to your questions below:\n\n**Does the optimistic TS using $M$ samples behaves like UCB-type algorithm?** : No, they are fundamentally different. UCB algorithm is deterministic, as they use upper confidence bound to evaluate arms, and the optimism comes from deterministically evaluating arms within the estimated confidence bounds. This algorithm is a fixed strategy for exploration.\n\nThompson Sampling is a randomized algorithm. The optimism in TS is handled through multiple sampling from the posterior distribution where the number $M$ controls the randomness of optimism and controls the boundary that the sampled parameters following concentration property [1] (more specifically, for every $m\\in [M]$,  $\\lVert\\tilde\\theta_{t,m}^{(\\ell)}-\\hat\\theta_t^{(\\ell)}\\rVert_{V_t} \\le O(d\\log LM)$ holds with probability at least $1-\\delta$) . Even with large $M$, the maximum of the sampled parameters does not guarantee an optimistic value in the same way as UCB does.\n\n[1] Abeille and Lazaric. \"Linear thompson sampling revisited\" (2017).\n\n**Comparison between greedy and UCB algorithm** : We are more than happy to clarify this question. The single-metric regret measure may not fully explain the observed behavior in Figure 2 (also Figure 3~13 in Appendix F) because it is difficult to calculate a single value of regret that captures the full complexity of the reward vector across multiple objectives. It becomes more difficult as the number of objectives grows, which may lead to misleading interpretations in certain cases. To the best of our knowledge, for the first time, our paper demonstrates the experiments of objective-wise total rewards. \n\nPareto regret focuses on the trade-offs between objectives, but it does not account for the total rewards across all objectives. Our newly defined effective Pareto regret covers this problem, which offers a more comprehensive measure of performance. This new definition represents an important step forward in overcoming the difficulties associated with measuring the regret in multi-objective settings.\n\n**Explicit regret equation** : In the Appendix B.2, Theorem 2 shows that algorithm $\\texttt{MOL-TS}$ has the worst-case regret upper bound by $\\left(1+\\frac{2}{p-\\frac{\\delta}{T}}\\right)c_T(\\delta)\\sqrt{2Td\\log\\left(1+\\frac{T}{\\lambda}\\right)} + 2\\delta \\Delta_{\\text{max}}$, where $c_T(\\delta) = \\left(R\\sqrt{d\\log\\left(\\frac{1+(T-1)/(\\lambda d)}{\\delta/L}\\right)}+\\lambda^{1/2}\\right)\\left(1+\\sqrt{2d\\log\\frac{2LMdT}{\\delta}}\\right).$ The regret depends on the number $L$ and $M$ up to logarithmic factor, and it does not depend on the number of arms $K$.\n\n\n**Comparisons with LinTS-type algorithms for single objective** : \nWe are happy to elaborate on this. First of all, the well-known minimax lower bound for the linear contextual bandit is $\\Omega(d\\sqrt{T})$ [2], so there is a $\\sqrt d$ gap between ours and the lower bound. (Please note that $O(\\sqrt{dT})$ bounds such as Chu et al. 2011 possess $log K$ factors for finite arms and $O(d^{3/2}\\sqrt T)$ regret algorithms including ours do not depend on the number of arms. We hope that we are discussing the results based on the relevant context.)\nThe regret bound in our paper is $\\widetilde O(d^{3/2}\\sqrt T)$, which matches the best-known regret bound of the  linear Thompson Sampling (LinTS) type algorithms (e.g., [1]) in single objective setting. It is known that this bound cannot be improved for LinTS and its variants due to the inevitable requirement of posterior variance inflation by a factor of $\\sqrt d$, a limitation that arises in the analysis of worst-case regret for Thompson Sampling compared to fixed optimism-based algorithms [3]. Our work extends this well-known result to the multi-objective setting, and the core regret bound still aligns with the fundamental limitations of LinTS in single objective setting.\n\nOur work extends this well-known result from single objective to multi-objective setting, where we also face the same fundamental limitations in terms of the scaling with $\\sqrt d$. Therefore, while the regret bound in the multi-objective setting grows more complex due to the additional factor of $L$ (the number of objectives), the worst-case regret bound is $\\widetilde O(d^{3/2}\\sqrt T)$.\n\n[2] Dani, Hayes, and Kakade. \"Stochastic Linear Optimization under Bandit Feedback\" COLT (2008).\\\n[3] Hamidi and Bayati. \"On Frequentist Regret of Linear Thompson Sampling\" (2020).\n\n\n**What is $\\delta$?** : In Algorithm 1, the input $\\delta$ represents a confidence bound input that plays two key roles, RLS estimations and concentration property. As described in Appendix C, $\\delta$ measures the probability bound on the distance between the true parameter and the RLS estimates [4]. This ensures that the estimated parameters are close enough to true values with probability at least $1-\\delta$. Also, it controls the probability that the sampled parameters follow the concentration property [1]. This property ensures that sampled parameters are close enough to RLS estimate with high probability. It is crucial property for random exploration in the Thompson Sampling algorithm, as it helps balance the trade-off between exploration and exploitation, while maintaining reliable confidence bounds.\n\n[4] Abbasi-Yadkori et al. \"Improved algorithms for linear stochastic bandits\" (2011).\n\n**Extra experiments of $\\lambda$, $c$, $\\delta$** : The main focus of our experiments is to compare the performance of the algorithms with different values of $M$ and $L$. The other hyperparameters, including $\\lambda, c$, and $\\delta$ were kept fixed in our experiments, with the value set to $\\lambda=1, c=1$, and $\\delta=0.01$. We did explore additional results for different initial values of these hyperparameters. But these values were not central to the core ideas of our paper, and varying these parameters does not change the results. Regarding the comparison with greedy and UCB algorithm, we used the same fixed hyperparameters for fairness, ensuring that the comparison is made under consistent restriction. The following table measures the average of total regret over 10 different instances in $T = 10000$ with different $\\lambda, c$, and $\\delta$.\n\n| $\\lambda = 2, c = 1, \\delta=0.01$ | $\\epsilon$-Greedy | $\\texttt{MOL-UCB}$|$\\texttt{MOL-TS}$(ours) |\n|----------|----------|----------|----------|\n| Pareto Regret | 240.71 | 178.29|73.93|\n| Effective Pareto Regret  | 285.38|268.92|95.50|\n\n| $\\lambda = 1,  c=2, \\delta=0.01$ | $\\epsilon$-Greedy | $\\texttt{MOL-UCB}$|$\\texttt{MOL-TS}$(ours) |\n|----------|----------|----------|----------|\n| Pareto Regret | 235.12 | 196.08|105.86|\n| Effective Pareto Regret  | 279.80|289.89|133.27|\n\n| $\\lambda = 1,  c=1, \\delta=0.1$ | $\\epsilon$-Greedy | $\\texttt{MOL-UCB}$|$\\texttt{MOL-TS}$(ours) |\n|----------|----------|----------|----------|\n| Pareto Regret | 239.18 | 211.66 | 77.42 |\n| Effective Pareto Regret  |285.00 | 310.29 |99.16|\n\n**Adversarial setting** : We are happy to modify Section 3 of the paper, that the contexts are adversarially given."}, {"review_id": "8H5F7r9Yn8", "reviewer": "Reviewer_1D53", "summary": "In this paper, the authors study stochastic linear contextual bandits under the multi-objective setting, in which each arm corresponds to a vector of $L$ objective rewards, whose expected reward is the inner product between the hidden objective value and the arm’s context. As the Pareto front is non-convex, they define the effective Pareto optimality, which is essentially the convex hull of all arms. They measure performance using the cumulative minimal effective Pareto sub-optimality, defined as the $\\ell_\\infty$ distance between the performance and the convex hull.\n\nThey present a Thompson Sampling-based algorithm to solve this problem efficiently. Specifically, for each objective, they sample a logarithmic number of hidden objective parameters and estimate the empirical objective reward of each arm using the maximum inner product between the sampled parameters and the context. The algorithm then randomly plays an action sampled uniformly from the empirical Pareto front. They establish a regret bound of order $\\sqrt{T}$ for their algorithm. Experiments are provided to demonstrate the benefits of the algorithm.", "questions": "- How does $M$ affect the constant in the regret bound of Theorem 2? For example, what happens if $M$ doubles?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n- The multi-objective linear contextual bandit setting is definitely significant and interesting. Applying Thompson Sampling to this setting is a natural idea. The authors propose a clean algorithm for this setting, with a regret upper bound that matches the performance of Thompson Sampling in the linear contextual bandit setting.\n\n- I think optimistic sampling is a novel idea, as it allows one to perform optimistic estimation in a computationally efficient way compared to the UCB bounds ($\\mathcal{O}(d^2 M)$ for optimistic sampling per action vs. $\\mathcal{O}(d^3)$ in UCB). The corresponding intuition and proof sketch look correct to me. This analysis may shed light on future work in the bandit literature.\n\nWeakness:\n\n- I feel that the main reason one would prefer a TS-based approach over a UCB-based approach is its computational efficiency, as suggested by Agrawal et al. (2012), especially when there are many arms. Unfortunately, I don't see the authors highlighting this point. I would suggest that the authors add a section discussing the computational complexity of the proposed approach.\n\n\nAgrawal, Shipra and Navin Goyal. “Thompson Sampling for Contextual Bandits with Linear Payoffs.” International Conference on Machine Learning (2012).", "was_revised": true, "final_justification": "I would maintain my positive evaluation of this work and recommend it for acceptance.", "rebuttal": "We thank the reviewer for your time and thoughtful review of our paper. We greatly appreciate the insightful feedback, especially the positive recognition of our use of optimistic sampling.\n\n**Computational Cost** : We will gladly discuss the computational complexity of our proposed approach. Unlike previous works that require computing the entire Pareto front, which involves comparing all pairs of arms and has a computational complexity of $O(K^2)$ (where $K$ is the number of arms), our method significantly reduces the computational cost. Instead of explicitly identifying all effective Pareto optimal arms, we play an arm based on a random weight vector, thus selecting an arm that is optimal with respect to the random weight, which is effective Pareto optimal arm. This approach takes the computational complexity to $O(KL)$. Our method saves computational time since $K>>L$.\n\nDiscussing the computational complexity involves several factors, including both the selection of arms and the method for computing the Pareto front. Beside comparing computational complexity between UCB and TS which involves considering multiple factors of each algorithm, our experiments show that the proposed Thompson Sampling algorithm is computationally faster. We believe that the computational efficiency of TS, as demonstrated empirically, arises from the way it avoids the explicit computation of the entire Pareto front and instead samples arms based on a random weight vector, leading to lower computational overhead. The following table shows the average time complexity with $T = 10000$, and $L = 4$.\n\n| Time Complexity (s) | $\\texttt{MOL-UCB}$ | $\\texttt{MOL-TS}$ (ours) |\n|----------|----------|----------|\n| $d = 5,\\ \\ K = 50$ | 16.73 | 5.09 |\n| $d = 10, K = 50$  | 17.39 |6.92|\n| $d = 5,\\ \\ K = 100$  | 34.64 |5.97|\n| $d = 10, K = 100$  | 37.25 | 7.29 |\n| $d = 15, K = 100$  | 40.87 | 11.43 |\n| $d = 10, K = 200$  | 79.95 | 7.81 |\n| $d = 15, K = 200$  | 88.08 | 11.69 |\n\nIt is also important to mention that anthor main reason of using TS over UCB is the superior empirical regret performances which are presented in the experiments in the paper (Figure 2~13).\n\n\n**The constant dependency with respect to $M$** : The regret bound in Theorem 2 depends on $M$ through the term $\\sqrt{2d\\log\\frac{2LMdT}{\\delta}}$, which arises from the fact that multiple sampled parameters need to satisfy the concentration property [1]. Doubling $M$ results in a logarithmic increase only in the regret bound. \n\n[1]Abeille and Lazaric. \"Linear thompson sampling revisited\" (2017)."}]

Author rebuttal:

Meta-review: This paper studies the problem of cumulative reward maximization in multi-objective stochastic linear contextual bandits. The paper observes that the conventional definition of Pareto regret does not take into account the optimality of cumulative rewards. To address this issue, the authors introduce the notion of Effective Pareto optimality of cumulative reward vectors. Building on this, they propose an algorithm called MOL-TS, based on Linear Thompson Sampling, which aims to minimize the Effective Pareto regret. 
In MOL-TS, regularized least squares are performed for each objective, and for each objective $M$ samples are drawn from the posterior distribution. 
By taking the maximum, each parameter is evaluated optimistically. The authors also prove a worst-case regret bound. The key algorithmic and analytical novelty lies in incorporating this form of optimism, which prevents the regret coefficient from growing exponentially with respect to $L$. However, this appears to be essentially the only substantial contribution of the paper.


After the review and discussion phases, all reviewers expressed a positive evaluation of this paper. While there were questions about the technical novelty, comparisons with UCB-type algorithms, and whether the dependency on $d$ is optimal, the authors’ responses were found satisfactory, and several reviewers raised their scores accordingly.

As also pointed out by Reviewer EmBN, the current theorem statement (Theorem 2) in the main part of the paper does not make the explicit dependence on important parameters such as $L$ entirely clear. If possible, presenting such dependencies directly in the main part would help make the paper’s main contributions more transparent.
Decision: Accept (poster)