Safe Multi-Objective Linear Bandits with Hierarchical Preferences

1 Introduction

Multi-armed bandits (MAB) provide a foundational framework for modeling sequential decision-making under uncertainty [Lai and Robbins, 1985; Auer et al., 2002; Abbasiyadkori et al., 2011; Lattimore and Szepesv´ari, 2020]. In a standard MAB problem, a learner interacts with an environment over T rounds. At each round t ∈ [T], the learner selects an arm from a finite or structured decision set and receives a stochastic reward corresponding to the chosen arm. The goal of the learner is to maximize the cumulative expected reward. A key challenge in this problem is the exploration-exploitation trade-off: the learner must balance exploring less-known arms to gather information and exploiting currently known arms that believed to yield high rewards.

∗Qingfu Zhang is the corresponding author.

To address this, two widely used strategies have been developed: Upper Confidence Bound (UCB) and Thompson Sampling (TS). UCB algorithms construct confidence intervals for each arm's expected reward and select the arm with the highest upper bound [Auer, 2002; Dani et al., 2008; Magureanu et al., 2014; Xue et al., 2020; Xue et al., 2023]. This strategy favors arms with either high empirical rewards or high uncertainty, thereby balancing exploration and exploitation. TS adopts a Bayesian perspective by maintaining a posterior distribution over the arm parameters and selecting arms according to their probability of being optimal, thus encouraging exploration through randomization [Thompson, 1933; Chapelle and Li, 2011; Xu et al., 2023].

While the classical MAB focuses on a single objective [Bubeck and Cesa-Bianchi, 2012], many real-world problems involve multiple, often conflicting objectives. For example, recommender systems [Rodriguez et al., 2012] must balance user satisfaction, content diversity, and long-term engagement, while autonomous driving [Zhang et al., 2023] requires trade-offs among safety, passenger comfort, and energy efficiency. To capture such multi-criteria decision-making scenarios, the multi-objective multi-armed bandit (MOMAB) framework has been proposed [Drugan and Nowe, 2013], in which the learner receives a vector-valued reward at each round, with each component representing a distinct objective.

However, the MOMAB framework treats each arm independently and thus fails to exploit contextual or structural information often available in real-world applications, such as product categories, prices, or user profiles in recommender systems [Li et al., 2010]. To address this limitation, the multiobjective stochastic linear bandit (MOSLB) model was later introduced [Lu et al., 2019; Xue et al., 2025b], where each arm is associated with a feature vector, and the expected reward for each objective is assumed to be a linear function of this vector. This assumption enables the algorithm to generalize across arms: by leveraging the shared linear structure, the learner can use feedback from one arm to estimate the rewards of other arms with similar features.

Most existing methods in the multi-objective bandit literature rely on scalarization [Drugan and Nowe, 2013; Wanigasekara et al., 2019] or Pareto-based criteria [Auer et al.,

2016; Cheng et al., 2026], which either collapse the multiobjective problem into a single-objective one by imposing fixed preference weights, or seek to identify Pareto-optimal solutions without explicitly modeling priority among objectives. However, these approaches may fall short in applications where objectives are inherently prioritized. For example, in clinical treatment planning, ensuring safety or efficacy is often paramount, while secondary factors such as cost or comfort are considered only after primary goals are satisfied. To accommodate such structured preferences, lexicographic ordering has been proposed [Ehrgott, 2005; Skalse et al., 2022; Abernethy et al., 2024], wherein objectives are ranked by importance, and reward vectors are compared based on the first dimension where they differ. Incorporating lexicographic preferences into the bandit learning framework leads to the lexicographic multi-objective bandit problem [Tekin, 2019; H¨uy¨uk and Tekin, 2021], where the higher-priority objectives must be optimized before lower-priority ones. 1

Despite recent progress in lexicographic bandits [H¨uy¨uk and Tekin, 2021; Xue et al., 2024; Xue et al., 2025a; Xue et al., 2026], existing methods often neglect safety constraints, which are essential in many real-world applications. For example, in high-stakes environments such as healthcare systems, deploying exploratory policies without performance guarantees may lead to unacceptable outcomes. This motivates the study of conservative (or safe) bandits [Wu et al., 2016; Katariya et al., 2019; Kazerouni et al., 2017; Moradipari et al., 2020; Lin et al., 2022], where the learner must ensure that its performance does not fall significantly below that of a known baseline. While conservative constraints have been well-studied in single-objective settings, whether comparable guarantees can be attained under multi-objective formulations remains an open problem.

In this paper, we introduce the framework of safe MOSLB with hierarchical preferences, which combines lexicographic preferences with two types of safety constraints: cumulative constraints and stage-wise constraints. This is the first work to address multi-objective bandits under safety constraints, and our main contributions are summarized as follows:

• Under cumulative constraints, we present LexUCB-C, a UCB-based algorithm that achieves a regret bound of ˜O(W i (w) · d√T + d2 · α-2 ) for each objective i ∈ [m] where W i (w) = 1+w+· · ·+wi-1 , w is a weight parameter reflecting the trade-off among conflicting objectives (introduced in Assumption 4), d is the dimension, T is the time horizon, and α is the safety threshold.
• Under stage-wise constraints, we develop LexTS-S, a Thompson Sampling-based method that enforces perround safety. LexTS-S achieves a regret bound of ˜O(W i (w)·d3/2√T+d·α-3 ) for each objective i ∈ [m].
• Both algorithms achieve regret bounds comparable to those of single-objective safe bandit methods [Kazerouni et al., 2017; Moradipari et al., 2020], in terms of their dependence on d, T and α. Moreover, since W 1 (w) = 1 for any trade-off value w, the performance

1 Due to space limitations, a more comprehensive discussion of related work can be found in the Appendix A.

• of the highest-priority objective (i = 1) remains nearly unaffected when optimizing additional objectives.
• We conduct experiments on both synthetic and realworld datasets using carefully designed settings that reflect hierarchical preferences and safety requirements. The results validate our theoretical findings.

2 Problem Setting

This section formalizes the problem setting. First, we introduce the notation and the standard MOSLB model. Second, we define the lexicographic ordering and extend the conservative bandit framework to the multi-objective setting. Finally, we state the key assumptions used in our analysis.

Notation. We denote by x ∈ Rd a feature (context) vector in a d-dimensional real space. The standard Euclidean norm of x is written as ∥x∥, while the Mahalanobis norm with respect to a positive definite matrix V ∈ Rd×d is defined as ∥x∥V = (x⊤Vx)1/2 . For a positive integer m, we use [m] to represent the index set {1, 2, . . . , m}. The superscript i ∈ [m] indicates quantities associated with the i-th objective.

Model. MOSLB is a T-round sequential decision-making problem. At each round t ∈ [T], the learner observes a set of feasible arms Xt ⊆ Rd , and selects an arm xt ∈ Xt. Upon selection, the learner receives a stochastic reward vector yt = [y1 t , y2 t , . . . , ym t ] ∈ Rm, wherem is the number of objectives. The expected reward for each objective i ∈ [m] satisfies

where θi∗ ∈ Rd is an unknown vector for the i-th objective. Next, we adopt the lexicographic order [H¨uy¨uk and Tekin, 2021] to compare reward vectors across multiple objectives.

Definition 1 (Lexicographic Order). Suppose u, v ∈ Rm. u lexicographically dominates v, if there exists an index i∗ ∈ [m] such that uj = vj for all j < i∗ , and ui∗ > vi∗ .

For example, [1, 3, 2] dominates [1, 0, 8] with i∗ = 2. Based on this, the optimal arm is defined as follows.

Definition 2 (Lexicographic Optimal Arm). An armx∗t ∈ Xt is lexicographic optimal if its expected reward vector is not lexicographically dominated by that of any arm in Xt.

Given the optimal arm x∗t , we can naturally define the regret in multi-objective setting, which is the cumulative gap between the optimal armx∗t and the chosen armxt, i.e.,

In conservative bandits, the learner is required to maintain performance that does not fall significantly below that of a given baseline policy [Kazerouni et al., 2017; Moradipari et al., 2020]. We extend this principle to the multi-objective setting. Specifically, at each round t, a baseline arm xbt is provided. We consider two types of safety constraints:

Definition 3 (Cumulative Constraint). For each objective i ∈ [m], the learner's cumulative expected reward must exceed a fraction (1 - α) of the baseline's cumulative reward:

Definition 4 (Stage-Wise Constraint). For each objective i ∈ [m], the learner's expected reward at each round must exceed a fraction (1 - α) of the baseline reward:

Finally, we introduce some common assumptions on linear bandits [Abbasi-yadkori et al., 2011; Jun and Kim, 2024], conservative bandits [Kazerouni et al., 2017; Moradipari et al., 2020] and multi-objective bandits [Xue et al., 2024].

Assumption 1. The reward noise is σ-sub-Gaussian, i.e., for all t ∈ [T] and i ∈ [m],

Assumption 2. The inherent parameter vectors and contextual vectors are bounded, such that there exists some B > 0,

The sub-Gaussian assumption allows us to derive highprobability confidence bounds via standard concentration inequalities, while the boundedness of both model parameters and context vectors ensures that the expected rewards remain within a well-defined range.

Assumption 3. Let ∆i (xbt ) = µi (x∗t )-µi (xbt ). There exist constants 0 ≤ ∆ℓ ≤ ∆u and 0 ≤ µℓ ≤ µu such that for all i ∈ [m] and t ∈ [T ],

This assumption ensures that the conservative baseline arm maintains a bounded gap from the optimal arm, which is critical for establishing safe exploration guarantees.

Assumption 4. There exists a constant w > 0 such that for any i ≥ 2 and x ∈ Xt, the trade-off between the i-th objective and higher-priority objectives is bounded as

This structural condition captures the lexicographic preference among objectives, ensuring that, relative to the optimal arm x∗t , any improvement in a lower-priority objective cannot compensate for excessive degradation in higher-priority ones.

3 Algorithms

We develop two algorithms for lexicographic linear bandits with safety constraints. LexUCB-C addresses the cumulative constraint using the UCB principle, while LexTS-S handles the stage-wise constraint via Thompson Sampling. Together, they provide complementary approaches for safe lexicographic bandit optimization.

3.1 Lexicographic UCB for Cumulative Safety

LexUCB-C is a UCB-based algorithm for setting with cumulative safety constraints. At each round, it either selects a high-performing arm under lexicographic preferences or defaults to a conservative baseline to ensure safety. The full procedure is in Algorithm 1.

Algorithm 1 LexUCB-C

Input: T,m,B, α, δ, λ,w

1: Set V1 = λI, c1 = √λB, ˆ θi1 = 0, z1 = 0, T1 = ∅ 2: for t = 1 to T do 3: x′t ← SELECTARM({ˆ θi t }mi=1 , ct, Vt, Xt) (Alg. 2) 4: Compute the lower bounds Lit for i ∈ [m] by Eq. (1) 5: if Safety condition (2) holds for all objectives then 6: Play xt = x′t and observe [y1 t , y2 t , . . . , ym t ] 7: Update zt+1 = zt +xt, Tt+1 = Tt ∪ {t} 8: Update Vt+1 = Vt +xtx⊤t 9: Compute the estimators {ˆ θi t+1 }mi=1 by Eq. (3) 10: Compute the confidence radius ct+1 by Eq. (4) 11: else 12: Play baseline xt = xbt (Conservative play) 13: Maintain zt+1 = zt, update T c t+1 = T c t ∪ {t} 14: Keep Vt+1 = Vt, ct+1 = ct, ˆ θi t+1 = ˆ θi t , ∀i ∈ [m] 15: end if 16: end for

Initialization. At the beginning of the algorithm, several quantities are initialized. The regularized covariance matrix is set to V1 = λI, where λ > 0 ensures numerical stability in the estimation process. The confidence radius is initialized as c1 = √λB, where B is the bounded prior in Assumption 2. The initial estimators for each objective i ∈ [m] are set to zero vectors, i.e., ˆ θi1 = 0. The cumulative decision vector z1 is initialized to zero and will be used to accumulate the sum of selected arms that are not conservative. The set T1, which tracks rounds in which optimistic (i.e., nonconservative) arms are played, is initialized to be empty.

MainLoop. At each round t, LexUCB-Cfirst calls the subroutine SELECTARM (Algorithm 2), which returns a candidate arm x′t that respects the lexicographic preference structure. The details of this subroutine will be discussed shortly.

Given a selected candidate arm x′t , LexUCB-C evaluates its safety by computing the worst-case lower bound on the cumulative reward, including x′t for each objective i ∈ [m],

zt denotes the cumulative action vector up to round t-1, and ˆ θi t is the empirical estimate of the reward vector for objective i. The term Lit captures the most pessimistic cumulative reward that could be incurred under current confidence region, assuming x′t is selected.

To ensure safety, LexUCB-C verifies whether the total worst-case reward exceeds a certain fraction of the reward obtained by always playing a fixed conservative baseline. Specifically, the arm x′t is considered safe if the following condition holds:

where T c t is the set of rounds up to t-1 in which the conservative baseline action xbτ was played. This constraint guarantees that, in each objective, the cumulative reward does not fall below the benchmark established by the baseline policy.

Algorithm 2 SELECTARM

Input: {ˆ θi t }mi=1 , ct, Vt, Xt 1: Initialize s = 1, Xt,s = Xt 2: repeat 3: if ∃ x ∈ Xt,s with ∥x∥V-1 t ≤ 1/√T then 4: Xt,T ←LEXFILTER({ˆ θi t }mi=1 , ct,Xt,s, 1 √T ) 5: Return any x ∈ Xt,T 6: else if ∃ x ∈ Xt,s with ∥x∥V-1 t > 2-s then 7: Return such x 8: else 9: Xt,s+1 ←LEXFILTER({ˆ θi t }mi=1 , ct, Xt,s, 2-s ) 10: s ← s + 1 11: end if 12: until an arm is selected

Algorithm 3 LEXFILTER

Input: {ˆ

• 1: Initialize X 0 t,s = Xt,s

θi t }mi=1 , ct, Xt,s, C

• 2: for i = 1 to mdo
• 3: ˆxit = argmaxx∈X i-1 t,s ⟨ˆ θi t , x⟩

• 5: end for
• 6: return X m t,s

If the safety condition is satisfied for all objectives, the candidate arm x′t is considered safe. LexUCB-C plays x′t and observes the reward vector [y1 t , . . . , ym t ]. It then updates the cumulative arm vector, zt+1 = zt + xt, adds the current round to the non-conservative set, Tt+1 = Tt ∪ t, updates the covariance matrix, Vt+1 = Vt +xtx⊤t , and recomputes the estimators { ˆ θi t+1 }mi=1 via regularized least squares:

The confidence radius ct+1 is then updated accordingly, i.e.,

If the safety test fails for some objective, LexUCB-C plays a predefined conservative arm xt = xbt . In this case, the cumulative vector zt, estimators, confidence radius and covariance matrix remain unchanged. The round index is added to the set of conservative rounds: T c t+1 = T c t ∪ {t}.

Arm Selection. To identify a candidate arm x′t for the safety test, LexUCB-C relies on a dedicated subroutine, SELECTARM, which aims to find a lexicographically optimal arm under current uncertainty. We now describe this arm selection procedure and its internal mechanism.

SELECTARM begins with the full feasible arm set Xt,1 = Xt and iteratively refines it. At each iteration s, SELECTARM

considers the current set Xt,s, and evaluates the uncertainty term ∥x∥V-1 t for each arm x ∈ Xt,s. Precisely, if there exists an arm with sufficiently small uncertainty (Step 3), SELECTARM invokes the LEXFILTER procedure with a highconfidence threshold C = 1/√T, and randomly returns any arm from the resulting filtered set. This ensures the selection of a confident and lexicographically optimal arm. Otherwise, if there exists an arm with norm exceeding a coarser threshold 2-s (Step 6), such an arm is directly selected. This branch encourages timely exploration when high-confidence arms are not yet available. If neither condition is met (Step 8), the arm set is refined by applying LEXFILTER with the threshold C = 2-s . Note that this lexicographic criterion becomes stricter as the iteration progresses, i.e., from stage s to s + 1. The updated set Xt,s+1 is then used in the next iteration, and such process repeats until an arm is selected.

Lexicographic Elimination. LEXFILTER performs sequential elimination across objectives following their priorities. Given the current arm set Xt,s, it maintains a sequence of filtered subsets X i t,s for i ∈ [m]. At each level i, LEXFILTER identifies the empirically optimal arm,

It then eliminates any arm x from X i-1 t,s if its estimated reward falls behind that of ˆxit by more than a threshold proportional to ct · C,

The threshold is scaled by a factor capturing the cumulative uncertainty propagated from higher-priority objectives. After m rounds, the final surviving set X m t,s is returned which consists of arms that remain competitive under all objectives.

In summary, LexUCB-C combines lexicographic optimization with cumulative safety monitoring. It ensures that the chosen arms respect safety constraints over time while optimizing higher-priority objectives first. We provide the following theoretical guarantee for LexUCB-C.

Theorem 1. Suppose Assumptions 1 - 4 hold. Then, with probability at least 1-δ, for any objective i ∈ [m], the regret of LexUCB-C is bounded as

where

Remark 1. Theorem 1 shows that LexUCB-C achieves a regret bound of ˜O(W i (w) · d√T +d2 · α-2 ) for any objective i ∈ [m]. The first term matches the standard regret rate of single-objective linear bandits [Kazerouni et al., 2017] up to a multiplicative factor W i (w). This factor reflects the cost of optimizing multiple objectives in a lexicographic manner. Notably, W 1 (w) = 1 implies that the regret bound on the highest-priority objective remains unaffected even optimizing other objectives simultaneously. Lower-priority objectives incur larger regret so as to maintain prioritization structure.

3.2 Lexicographic TS for Stage-Wise Safety

Under the stage-wise safety setting, we propose LexTS-S, a Thompson Sampling-based algorithm that incorporates lexicographic preferences and enforces safety at every round. The full procedure is summarized in Algorithm 4.

Initialization. At the beginning, LexTS-S set the regularized covariance matrix as V1 = λI, where the parameter λ > 0 ensures numerical stability. The initial confidence parameter is defined as c1 = β1 = √λB, and the reward estimator for each objective i ∈ [m] is initialized to zero, i.e., ˆ θi1 = 0. Meanwhile, a mixing parameter ρ1 ∈ (0, µℓα B+µu ) is also specified for constructing safe exploration.

MainLoop. At each round t, LexTS-S first generates a randomized parameter vector to estimate reward for each objective. Specifically, for each i ∈ [m], a sample is drawn from a Gaussian posterior,

where the posterior mean ˆ θi t and covariance c2t ·V-1 t are constructed using the same regularized least-squares estimator and covariance matrix as in LexUCB-C. This TS-based sampling introduces randomized exploration, in contrast to the optimistic UCB strategy used in LexUCB-C.

Next, LexTS-S constructs a stage-wise safety region St by intersecting the per-objective safe sets:

whereS i

Here, C i t = {θ | ∥θ - ˆ θi t ∥Vt ≤ ct} is the confidence region for objective i. Intuitively, S i t includes arms whose worstcase reward is guaranteed to exceed a fraction (1 - α) of the baseline's reward for objective i. By intersecting these sets, St contains only arms that are simultaneously safe across all objectives at round t. This differs from LexUCB-C, where safety is verified cumulatively using a global reward budget, and thus the candidate arm could be risky in the short term as long as cumulative safety is maintained.

LexTS-S then checks whether the safety region St is nonempty and whether the design matrix is sufficiently wellconditioned, i.e.,

Algorithm 4 LexTS-S

Input: T,m,B, α, δ, λ,w,∆ℓ, µℓ

• 2: Choose a value ρ1 ∈ (0, µℓα B+µu )
• 1: Set V1 = λI, c1 = β1 = √λB, ˆ θi1 = 0
• 3: for t = 1 to T do
• 4: Sample ˜ θi t ∼N(ˆ θi t , c2t · V-1 t )
• 5: Compute the safety region: St = ∩mi=1S i t , where

• 6: if St ̸= ∅ and λmin(Vt) ≥ ( 2ct ∆ℓ+αµℓ )2 then
• 7: xt ← SELECTARM(˜ θi t , ct + βt, Vt, St) (Alg. 2)
• 8: else
• 9: Sample ζt uniformly from the unit sphere in Rd
• 10: xt ← (1-ρ1)xbt +ρ1ζt (Conservative play)
• 11: end if
• 12: Play xt and observe reward vector [y1 t , y2 t , . . . , ym t ]
• 13: Update Vt+1 = Vt +xtx⊤t
• 14: Compute the estimators {ˆ θi t+1 }mi=1 by Eq. (3)
• 15: Compute ct+1 and βt+1 by Eq. (5)
• 16: end for

where ∆ℓ and µℓ are problem-dependent constants defined in Assumption 3. If these conditions are satisfied, LexTS-S calls the SELECTARM subroutine (Algorithm 2) to select an arm xt, which passes the sampled parameters {˜ θi t }mi=1 , the confidence parameter ct + βt, and the feasible set St. This subroutine follows the same iterative filtering mechanism as in LexUCB-C, using LEXFILTER to preserve lexicographic optimality among the arms in St.

If either condition fails, either because the safety region is empty or because the confidence in parameter estimates is too low, LexTS-S takes a conservative action. Instead of playing a fixed baseline arm, it mixes the conservative baseline xbt with a randomly sampled unit vector ζt,

where ρ1 balances between baseline performance and exploratory progress. This conservative play guarantees the stage-wise safety constraint even in highly uncertain situations, similar to the conservative mechanism in LexUCB-C but with a stage-wise guarantee.

After the arm xt is played, LexTS-S observes the reward vector [y1 t , y2 t , . . . , ym t ] and updates the covariancematrix and estimators in the same manner as LexUCB-C. Finally, the confidence radius is computed as follows,

In summary, LexTS-S differs from LexUCB-C in two key aspects: (i) it enforces stage-wise safety, requiring that each selected arm be immediately safe, rather than maintaining safety cumulatively; and (ii) it adopts a Thompson Sampling strategy based on posterior sampling of reward parameters, in contrast to the optimistic upper confidence bound approach used in LexUCB-C. These distinctions make LexTS-S more conservative in the short term, and better suited for environments where immediate safety is essential.

The regret bound of LexTS-S is provided as follows.

Theorem 2. Suppose Assumptions 1 - 4 hold, and that the arm set Xt is convex and compact for all t ∈ [T]. Then, with probability at least 1-δ, for any objective i ∈ [m], the regret of LexTS-S is bounded as

Remark 2. Theorem 2 provides a high-probability regret bound for LexTS-S under stage-wise safety constraints. The leading term ˜O(W i (w) · d3/2√T) matches the typical regret rate of Thompson Sampling-based linear bandits [Abeille and Lazaric, 2017] up to a multiplicative factor W i (w), which arises from sequentially optimizing multiple objectives with lexicographic priorities. Similar to LexUCB-C, the bound ensures that the most important objective (i = 1) achieves nearly optimal regret scaling, i.e., W 1 (w) = 1, while lowerpriority objectives may incur increased regret due to the hierarchical optimization. The additional d3 · α-1 term reflects the cost of maintaining strict stage-wise safety throughout the learning process. In particular, a smaller α leads to more cautious behavior, ensuring that safety constraints are less likely to be violated, but at the expense of a larger regret penalty.

4 Experiments

In this section, we evaluate our algorithms under safety constraints on both synthetic and real-world datasets.We summarize the baselines and briefly describe the datasets here. Full experimental details are provided in Appendix B.

We compare our methods with two representative singleobjective conservative linear bandit methods: (i) CLUCB [Kazerouni et al., 2017], which optimizes only the first objective while ensuring the cumulative reward stays above (1-α) times that of the baseline, and (ii) SCLTS [Moradipari et al., 2020], which optimizes only the first objective and maintains the stage-wise reward above (1 - α) times the baseline.

Synthetic Dataset. The decision set (arm space) is the convex hull of four vertices: {(0, 0), (1, 0), (0, 1), (0.5, 1)}, as illustrated in Figure 1(a). The inherent vectors for the two objectives are θ1 ∗ = [0, 1] and θ2 ∗ = [1, 0], respectively. Under this setting, the expected reward for any arm x is given by [⟨θ1 , x⟩, ⟨θ2 , x⟩] = [x2, x1]. Thus, the first objective is maximized when x2 = 1, achieving the optimal value of 1. All arms lying on the top edge of the convex hull satisfy this condition. Among these arms, the second objective is maximized when x1 = 0.5, which yields the highest possible secondobjective reward of 0.5 under the constraint that the first objective remains optimal. Therefore, the lexicographic optimal arm is x∗t = [0.5, 1], corresponding to the expected reward vector [1, 0.5]. The baseline (safe) arm is set to the centroid of the convex hull, ¯x = [0.375, 0.5].

Under the cumulative safety constraint, Figure 1(b) shows that our proposed algorithm LexUCB-C achieves performance comparable to the baseline CLUCB on the first objective. This empirically supports our theoretical guarantee that LexUCB-C preserves the performance of the most important objective. Moreover, LexUCB-C-2nd consistently yields lower cumulative regret than CLUCB-2nd across the entire time horizon, demonstrating its effectiveness in optimizing the secondary objective without compromising safety. These results highlight the strength of LexUCB-C in balancing lexicographic reward maximization with long-term cumulative safety guarantees in multi-objective decision-making.

Under the stage-wise constraint, Figure 1(c) shows that LexTS-S incurs slightly higher regret on the primary objec-

• (a) Objective 1: User Satisfaction
• (b) Objective 2: Diversity Promotion
• (c) Objective 3: Genre Alignment

Figure 2: Cumulative regret comparison between LexUCB-C and CLUCB (cumulative safety constraint) and LexTS-S and SCLTS (stagewise safety constraint) on MovieLens 100K dataset.

tive compared to the baseline SCLTS. This is expected, as SCLTS is designed to solely optimize the primary objective. Nonetheless, the flattened regret curves of LexTS-S on both objectives suggest that it successfully identifies the lexicographic optimal arm. In contrast, SCLTS exhibits nearly linear regret on the second objective, highlighting LexTS-S's ability to handle multiple objectives simultaneously. These results demonstrate that LexTS-S effectively leverages the multi-objective structure to maintain strong performance even under stringent per-round safety constraints.

Real-world Dataset. We evaluate our proposed algorithms on the MovieLens 100K dataset 2 [Harper and Konstan, 2015], a widely used benchmark in recommender systems and bandit research [Li et al., 2025]. The dataset consists of 100,000 ratings provided by 943 users on 1,682 movies, where each rating is given on a 5-star scale. Each movie is accompanied by metadata such as title, release date, and genre information covering 19 categories (Action, Adventure, Animation, Children's, Comedy, Crime, Documentary, Drama, Fantasy, Film-Noir, Horror, Musical, Mystery, Romance, Sci-Fi, Thriller, War, and Western). We represent each movie as a 21dimensional feature vector, consisting of a 19 one-hot encoding of its genre affiliations, a 1 normalized popularity score (ranging from 0 to 1), and a 1 bias term (set to a constant value of 1). To construct a multi-objective recommendation environment, we define three distinct objectives: User Satisfaction, Diversity Promotion, Genre Alignment.

Figures 2(a)-(c) present the cumulative regrets of all algorithms on the real-world dataset. For the first objective (Figure 2(a)), our proposed algorithms, LexUCB-C and LexTS-S, exhibit regret curves that are almost indistinguishable from those of the baselines CLUCB and SCLTS throughout the learning horizon. This observation indicates that incorporating lexicographic preferences does not compromise the optimization of the most critical objective. In the early stage, the regret of LexUCB-C slightly fluctuates due to its confidencebased exploration, while LexTS-S demonstrates smoother convergence, benefiting from the posterior sampling mechanism. As the number of rounds increases, both algorithms rapidly stabilize, achieving a comparable cumulative regret level to that of the baselines, thereby validating their ability to preserve first-priority optimality.

2 https://movielens.org/

In contrast, for the second and third objectives (Figures 2(b)-(c)), the advantage of our lexicographic design becomes evident. Both LexUCB-C and LexTS-S achieve smaller cumulative regrets compared to CLUCB and SCLTS, with the performance gap widening over time. This demonstrates that, after optimizing the dominant objective, our algorithms effectively exploit the remaining exploration capacity to improve outcomes for subsequent objectives. The hierarchical update rules in LexUCB-C and LexTS-S enable the agent to adaptively focus on secondary and tertiary objectives without violating the lexicographic priority constraints. Overall, these results confirm that the proposed algorithms not only maintain competitiveness on the leading objective but also substantially enhance performance on subordinate ones, thereby realizing true lexicographic optimization in practice.

5 Conclusion and FutureWork

In this paper, we formalize and investigate the problem of safe lexicographic MOSLB, which integrates lexicographic preferences with two widely adopted safety constraints: cumulative and stage-wise constraints. We design two algorithms tailored to these settings. For the cumulative-safe setting, we develop LexUCB-C, a UCB-based algorithm that respects lexicographic order while ensuring cumulative safety. For the stage-wise-safe setting, we offer LexTS-S, a Thompson Sampling-based method that guarantees per-round safety. We provide rigorous regret analysis for both algorithms, showing that their performance matches that of existing singleobjective safe bandit algorithms [Kazerouni et al., 2017; Moradipari et al., 2020] in terms of dependence on the dimension d, time horizon T, and safety threshold α. Notably, we demonstrate that optimizing lower-priority objectives incurs minimal additional regret to the highest-priority objective.

This work opens several promising directions for future research. First, extending our framework to nonlinear reward models or more general action spaces would broaden its applicability. Second, while our analysis provides worstcase guarantees, exploring problem-dependent algorithms that leverage structural properties to improve empirical performance is an important direction. Finally, eliminating the reliance on prior knowledge assumed in Assumptions 1-4 would enhance the practical utility of our algorithms.

Acknowledgments

The work described in this paper was supported by the Research Grants Council of the Hong Kong Special Administrative Region [GRF Project No. CityU 9043546] and the National Natural Science Foundation of China (NSFC) under Grant No. 62276223.