Lexicographic Multiarmed Bandit
Alihan Hüyük Cem Tekin
cs.LG stat.ML


Collapse of layer dimerization in the photo-induced hidden state of 1T-TaS_2
    Tobias Ritschel
    December 30, 2023
============================================================================




We consider a multiobjective multiarmed bandit problem with lexicographically ordered objectives. In this problem, the goal of the learner is to select arms that are lexicographic optimal as much as possible without knowing the arm reward distributions beforehand. We capture this goal by defining a multidimensional form of regret that measures the loss of the learner due to not selecting lexicographic optimal arms, and then, consider two settings where the learner has prior information on the expected arm rewards. 

In the first setting, the learner only knows for each objective the lexicographic optimal expected reward. In the second setting, it only knows for each objective near-lexicographic optimal expected rewards.

For both settings we prove that the learner achieves expected regret uniformly bounded in time. The algorithm we propose for the second setting also attains bounded regret for the multiarmed bandit with satisficing objectives. In addition, we also consider the harder prior-free case, and show that the learner can still achieve sublinear in time gap-free regret. Finally, we experimentally evaluate performance of the proposed algorithms in a variety of multiobjective learning problems.




§ INTRODUCTION
 

A vast number of decision making and learning tasks involve multidimensional performance metrics (objectives). Examples include recommending items in a recommender system to optimize accuracy, diversity and novelty <cit.>, learning lexicographic optimal routing flows in wireless networks <cit.>, and adjusting the dose of radiation therapy for cancer patients while prioritizing target coverage over proximity of the therapy to the organs at risk <cit.>. In the aforementioned problems, the learner aims to choose arms that yield high rewards in all of the objectives; however, it prefers arms that yield high rewards in the low priority objectives only if they do not compromise the rewards in the high priority objectives. 

Motivated by the above applications, in this paper we propose a new multiarmed bandit (MAB) problem called the lexicographic multiarmed bandit (Lex-MAB). In this problem, the learner's priority over the objectives is formally captured by lexicographic ordering. Essentially, given D objectives indexed by the set D := [D], objective i has a higher priority than objective j if i<j.[For a positive integer D, [D] := {1,…,D}] This priority induces a preference over the finite set of arms denoted by A. Namely, given two arms a and a' with the corresponding real-valued expected reward vectors μ_a:=(μ^1_a,…,μ^D_a) and μ_a':=(μ^1_a',…,μ^D_a'), we say that arm a lexicographically dominates arm a' in the first i ≤ D objectives (written as a ≻_,i a') if μ^j_a>μ^j_a', where j:=min{k≤ i: μ^k_a≠μ^k_a'}.[If there is no such j, then μ^k_a=μ^k_a' for all k∈ [i], which implies that μ_a does not lexicographically dominate μ_a' in the first i objectives.] Here, the latter expression is succinctly expressed as μ_a ≻_,iμ_a'. Based on this preference, the set of lexicographic optimal arms are defined as the ones that are not lexicographically dominated by any other arm in all of the D objectives, which is given as 

A_* :=  {a∈𝒜: μ_a'⊁_,Dμ_a, ∀ a'∈𝒜}.


In the Lex-MAB, in each round t the learner selects an arm a(t)=a from A, and then, receives a D-dimensional random reward vector r(t) = (r^1(t),…,r^D(t)) that is drawn from a fixed distribution with expectation vector μ_a. The goal of the learner is to perform as well as an oracle which perfectly knows the set of lexicographic optimal arms and selects a lexicographic optimal arm in every round. We capture the ordering of the objectives by introducing a multidimensional regret measure called the lexicographic regret. As this regret notion is fundamentally different from the scalar regret notion used in the classical stochastic MAB <cit.>, minimizing it requires exploiting the multidimensional nature of the rewards and ordering of the objectives both in algorithm design and technical analysis. 

This is a challenging task because simple techniques such as turning the problem into an MAB with scalar rewards by using scalarizing methods from multiobjective optimization <cit.> will not work since the solution of the scalarized problem may not produce lexicographic optimal arms. The problem is further complicated due to the fact that without any prior knowledge on the expected arm rewards, it is impossible to identify lexicographic optimal arms with high probability. This can be observed by considering a problem instance with arms a and b, and D=2, such that a and b have the same expected reward in objective 1 and a is the only lexicographic optimal arm. Although in this problem the learner can identify with high probability which arm is better in the second objective, it can never be sure about the lexicographic optimality of this arm. We call this problem the identifiability problem.[It also exists in the best arm identification problem with a fixed confidence (see Chapter 33 in <cit.>).]


The challenges described above motivates us to focus on the cases when the learner has prior knowledge on expected rewards. Specifically, we consider two types of prior knowledge, which generalize the prior knowledge introduced in <cit.> and <cit.> to multidimensional rewards. In the first case, we assume that the expected rewards of a lexicographic optimal arm are known. In the second case, we assume that near-lexicographic optimal expected rewards are known. Then, we build learning algorithms that utilize the prior information to achieve uniformly bounded in time lexicographic regret for both cases. 

Importantly, for the first case, we show that the regret in each objective due to selecting a suboptimal arm a is inversely proportional to the maximum of the gaps of arm a over all objectives. This shows that having prior information over multiple objectives speeds up elimination of suboptimal arms. This is analogous to the combinatorial MAB <cit.> in the sense that observations from one objective can help ruling out suboptimal arms in other objectives. We also prove that a similar gain appears in the second case, albeit we cannot rule out an arm performing much better than a lexicographic optimal arm in some objective as suboptimal. 

In addition to the cases with prior information, as the third case, we consider learning without any prior information. In this setting, despite the identifiability problem, we show that it is possible to achieve Õ(T^2/3) gap-free regret by learning to select near-lexicographic optimal arms. Finally, we numerically evaluate the performance of the learner with and without prior information on several multiobjective learning problems with lexicographically ordered objectives. 







Rest of the paper is organized as follows. Related work is given in Section <ref>. The Lex-MAB, the lexicographic regret and two types of prior information are defined in Section <ref>. Algorithms and regret bounds for the Lex-MAB under prior information and for the prior-free case are considered in Section <ref>.
Experimental results are given in Section <ref> followed by the concluding remarks in Section <ref>. Proofs, additional simulations, tables of notation and the code for experimental results are given in the appendix.




§ RELATED WORK
 


<cit.> shows that in the classical stochastic MAB problem, for any uniformly good policy the regret grows at least logarithmically over time. As opposed to this, <cit.> proves for the two-armed stochastic bandit that when the learner has prior information on the maximum expected reward μ^* and the minimum nonzero suboptimality gap Δ, there exists policies that can achieve uniformly bounded regret. This idea is further investigated in <cit.>, which shows that bounded regret of order 1/Δ is achieved for the case with finitely many arms when the learner knows μ^* and a positive lower bound on Δ. 

<cit.> studies the case where only μ^* is known and proposes an algorithm with bounded regret of order log(1/Δ) (1/Δ), and also proves a lower bound of order 1/Δ. This paper also provides a generic tool to prove gap-dependent lower bounds on the regret. Similarly, <cit.> considers Thompson sampling and shows that its regret is uniformly bounded when μ^* and a positive lower bound on Δ are known. On the other hand, <cit.> considers a weaker prior information model where the learner knows a near-optimal expected reward η, which can be computed using μ^* and a positive lower bound on Δ. The proposed algorithm obtains ∑_a Δ_a/δ^3 regret, where δ=μ^*-η<Δ and Δ_a is the suboptimality gap of arm a.

<cit.> and <cit.> consider as prior information the knowledge of parametrized expected reward functions for each arm. In these works, the only unknown is the true parameter, which can be estimated by using reward observations from all of the arms. 

Different from the works mentioned above, in this paper we consider a multiobjective MAB problem with lexicographically ordered objectives. We design algorithms that exploit the prior information in all objectives simultaneously to rule out arms that are not lexicographic optimal. Our regret bounds match the one in <cit.> and improve the one in <cit.> for the case with a single objective.









Numerous works have investigated regret minimization in multiobjective variants of the MAB problem. For instance, <cit.> defines for each suboptimal arm its distance to the Pareto front as the Pareto suboptimality gap and the regret as the sum of the Pareto suboptimality gaps of the arms chosen by the learner. It proposes a learning algorithm that achieves O(log T) gap dependent Pareto regret. <cit.> considers the multiobjective contextual MAB problem with similarity information, and extends the contextual zooming algorithm in <cit.> to minimize the Pareto regret while making fair selections among the estimated Pareto optimal arms. The proposed algorithm is shown to achieve Õ(T^(1+d_p)/(2+d_p)) Pareto regret where d_p is the Pareto zooming dimension. In addition, <cit.> considers a biobjective contextual MAB problem with lexicographically ordered objectives. Unlike this work, we study the general case with D lexicographically ordered objectives and focus on the importance of prior information in learning. 




Our problem is also related to the tresholding MAB studied in <cit.> and satisficing MAB studied in <cit.>. Specifically, if the prior information is given with respect to a target arm which is not necessarily a lexicographic optimal arm, and the regret in each objective is defined with respect to the expected reward of the target arm in that objective, then our algorithms for the cases with prior information can easily be adapted to minimize the regret with respect to the target arm. Specifically, we adapt our second case to the satisfaction-in-mean-reward problem introduced in <cit.> and prove that our algorithm achieves bounded regret for this problem as well.[See Section <ref> for our results on the multiarmed bandit with satisficing objectives.]
 






§ PROBLEM FORMULATION
 



System Model:
We consider rounds indexed by t∈{1,2,…}. In each round t, the learner first selects an arm a(t) from the finite arm set 𝒜 := [A], and then, observes a random reward for each objective i ∈𝒟:= [D], denoted by r^i(t), which is equal to μ_a(t)^i+κ^i(t), where μ_a^i denotes the expected reward of arm a in objective i and κ^i(t) denotes the zero mean noise. The learner does not know the expected reward vector μ_a:=(μ_a^1,…,μ_a^D), a∈𝒜 beforehand, and given a(t)=a, the noise vector {κ^1(t),…,κ^D(t)} is sampled from a fixed (unknown) multivariate distribution ν_a, independent of the other rounds. Moreover, its marginal distribution is 1-sub-Gaussian, i.e., ∀ a ∈ A and ∀λ∈ℝ, [e^λκ^i(t)|a(t)=a] ≤exp(λ^2/2).[Noise can be dependent over the objectives.] The assumption on the noise distribution is very general as it covers the Gaussian distribution with zero mean and unit variance, and any bounded zero mean distribution defined over an interval of length 2. 


Lexicographic Optimality:
For two D-dimensional real-valued vectors μ:=(μ^1,…,μ^D) and μ':=(μ'^1,…,μ'^D), and i ∈ [D], we say that μ lexicographically dominates μ' in the first i objectives, denoted by μ≻_,iμ', if μ^j>μ'^j, where j:=min{k≤ i: μ^k≠μ'^k}. Based on this, we say that arm a lexicographically dominates arm a' in the first i objectives if μ_a≻_,iμ_a'. The complement of this is denoted by μ_a⊁_,iμ_a'.


Let 𝒜_*^i := {a∈𝒜: μ_a'⊁_,iμ_a, ∀ a'∈𝒜} denote the set of lexicographic optimal arms in the first i objectives and define A_* := 𝒜_*^D. Clearly, we have 𝒜_*^i+1⊆𝒜_*^i for i∈ [D-1]. We use * to denote an arm that is lexicographic optimal in all objectives, and μ_*^i to denote the expected reward of this arm in objective i. Moreover, we define the gap of arm a in objective i as Δ_a^i:=μ_*^i-μ_a^i and the absolute gap of arm a in objective i as ∇_a^i := |μ_*^i-μ_a^i|.

For i∈{2,…,D}, we let 𝒮_*^i := 𝒜_*^i-1-𝒜_*^i denote the set of arms that are lexicographic optimal in the first i-1 objectives but not lexicographic optimal in the first i objectives and define 𝒮_*^1:=𝒜-𝒜_*^1. Note that a∈𝒮_*^i implies that Δ_a^i>0. The set of suboptimal arms in objective i is given as 𝒮^i:={a:Δ_a^i>0}.
We also define the maximum suboptimality gap in objective i as Δ_max^i := max_a ∈𝒜Δ_a^i and the maximum absolute gap as ∇_a^max:=max_j∈𝒟∇_a^j. 
Finally, let Δ_min^i := min_a ∈𝒮_*^iΔ_a^i denote the minimum suboptimality gap among arms in 𝒮_*^i.[If S_*^i=∅, then Δ_min^i=∞.]  





Types of Prior Knowledge:

(Case 1) Lexicographic optimal expected rewards are known: The learner knows μ_*^i for all i∈𝒟. For this case, we assume μ_*^i =0, ∀ i∈𝒟 without any loss of generality.

(Case 2) Near-lexicographic optimal expected rewards are known: The learner knows η_i such that μ_*^i - Δ_min^i < η_i < μ_*^i for all i∈𝒟. For this case, we define δ_i:=μ_*^i-η_i, ∀ i∈𝒟 and assume η_i=0, ∀ i∈𝒟 without any loss of generality.

(Case 3) No prior knowledge on the expected rewards. 









In Case 1, if μ_*^is are not equal to 0, we can subtract them from the rewards to obtain r̃^i(t) := r^i(t)-μ_*^i. Under these transformed rewards, we will have μ̃_*^i=0, ∀ i∈𝒟 and the gaps that we have defined will not be affected. Similarly, in Case 2, we can subtract η_is from the rewards to obtain r̃^i(t):=r^i(t)-η_i. 



Regret Definitions:
The (pseudo) regret of the learner is measured with respect to an oracle, which knows the expected rewards of the arms, and chooses a lexicographic optimal arm in each round. We define two notions of regret: Priority-based and priority-free regrets in objective i are given as ^i_pb(T) := ∑_t=1^T Δ_a(t)^i{a(t)∈𝒮_*^i} and ^i_pf(T) := ∑_t=1^T Δ_a(t)^i respectively. 




The lexicographic priority-based and priority-free regrets are defined as the tuples _pb(T):=(^1_pb(T),…,^D_pb(T)) and _pf(T):=(^1_pf(T),…,^D_pf(T)) respectively. Subscripts will be removed from the notation when the considered regret notion is clear from the context. 

For _pb(T), when a(t)∈𝒮_*^i, regret is incurred only in objective i. No regret is incurred for j<i since Δ_a(t)^j=0. In addition, no regret is incurred for j>i when a(t) ∈𝒮_*^i. This definition of regret is consistent with the priority that the learner assigns to each objective. Since lexicographic ordering implies that even a small improvement in the expected reward in objective i is more important than any improvement in the expected rewards of objectives j>i, the learner does not care about the loss it incurs in higher indexed objectives when a(t)∈𝒮_*^i. 
For _pf(T), an arm a for which μ^i_a > μ^i_* will incur negative regret in objective i, but positive regret in some other objective. 

We say that the regret is O(max{f_1(T),…,f_D(T)}) when ^i(T)∈ O(f_i(T)) for i∈𝒟. Under both notions of regret, the (cumulative) regret of any arm selection strategy cannot lexicographically dominate the cumulative regret of always selecting a lexicographic optimal arm, which is essentially the zero vector. Therefore, the time-averaged expected rewards of any algorithm that achieves sublinear _pb(T) or _pf(T) will converge (as T →∞) to the lexicographic optimal expected rewards. In addition, under _pf(T) the lexicographic ordering between the cumulative expected rewards and the regrets of any pair of sequences of arms (a(1),…,a(T)) and (a'(1),…,a'(T)) will be the same.


	For Case 1, the bound for _pb(T) given in Theorem <ref> also holds for _pf(T) if we replace 𝒮_*^i with 𝒮^i. For Case 2, if we redefine the minimum suboptimality gap as 
	Δ_min^i := min_a ∈𝒮^iΔ_a^i (which implies a stronger prior knowledge on the near-lexicographic optimal expected rewards), and replace 𝒮_*^i with 𝒮^i, then the bound for _pb(T) in Theorem <ref> also holds for _pf(T). Theorems <ref> and <ref> in the appendix bound _pf(T) for Cases 1 and 2 respectively. On the other hand, for Case 3, the regret analysis only holds for _pf(T) (see Section <ref> for the details).






§ LEARNING ALGORITHMS AND REGRET BOUNDS


A Learning Algorithm for Case 1: 
We propose Optimal Mean based Lexicographic Exploration and eXploitation (OM-LEX) given in Algorithm <ref> for the prior information described in Case 1. In essence, OM-LEX generalizes the arm selection rule proposed in Algorithm 1 in <cit.> to multiple objectives. It keeps for each arm a a counter N_a that counts how many times arm a was selected prior to the current round and the sample mean estimate μ̂_a^i of the rewards from objective i of arm a observed prior to the current round for all i ∈ D. The values of these variables at the beginning of round t are denoted by N_a(t) and μ̂_a^i(t) respectively. 



OM-LEX starts by selecting each arm exactly once. In the remaining rounds, it checks whether there exists an arm whose sample mean reward in objective i is within a shrinking neighborhood of the lexicographic optimal arm's expected reward for all objectives i∈𝒟. For this, it computes the set of estimated lexicographic optimal arms in round t as

    Â_*(t) := { a ∈𝒜: ∀ i∈𝒟, |μ̂_a^i(t)| < √(4log N_a(t)/N_a(t))} .

If Â_*(t) ≠∅, then OM-LEX exploits by selecting one of the arms in Â_*(t) uniformly at random as it expects only the lexicographic optimal arms to satisfy this condition in the long run. If no such arm exists, then OM-LEX explores by playing all arms in a round-robin fashion.

The following theorem shows that the expected priority-based regret of OM-LEX is uniformly bounded in time. 

 
	When OM-LEX is run,  ∀ i∈𝒟 and ∀ T≥ 1, we have
    
    [^i_pb(T)] ≤∑_a∈𝒮_*^i( (π^2/3D + 1 )Δ_a^i+ 36/∇_a^maxlog17/∇_a^max) .



When D=1, this result is identical to the regret bound in Theorem 9 in <cit.> except for some constants. In the multiobjective case, we see that the regret induced by an arm in one objective depends on the maximum of the absolute gaps of the same arm over all objectives. As long as the arm has a large absolute gap in at least one objective, it is easy to identify it as a suboptimal arm.




A Learning Algorithm for Case 2: 
We propose Near Optimal Mean based Lexicographic Exploration and eXploitation (NOM-LEX). NOM-LEX has almost the same structure with OM-LEX. Its pseudocode is exactly the same as Algorithm <ref> except two differences: Firstly, its input prior knowledge (given in line 1 of Algorithm <ref>) is η_i=0, ∀ i ∈ D. Secondly, NOM-LEX computes the set of estimated lexicographic optimal arms in round t (given in line 6 of Algorithm <ref>) as 

    Â_*(t) := { a ∈𝒜: ∀ i∈𝒟, μ̂_a^i(t) > -√(4log N_a(t)/N_a(t))} .


The next theorem bounds the expected priority-based regret of NOM-LEX.

 
	When NOM-LEX is run, ∀ i∈𝒟 and ∀ T≥ 1, we have
    
    [^i_pb(T)] ≤∑_a∈𝒮_*^i( (π^2/6D + 1 )Δ_a^i+ 36Δ_a^i/(max_j∈𝒟(Δ_a^j-δ_j))^2log17/max_j∈𝒟(Δ_a^j-δ_j))  .



From Theorem <ref>, we see that the regret due to a suboptimal arm a in objective i depends on the maximum squared difference between the suboptimality gaps of that arm and near-lexicographic optimal expected rewards over all objectives. This also shows that the prior knowledge in other objectives may help the learner attain smaller regret in objective i. However, since the lexicographic optimal expected rewards are not known, unlike Case 1, we cannot rule out a suboptimal arm in objective i by observing that it is much better than a lexicographic optimal arm in another objective.


A Learning Algorithm for Case 3: 
We propose Prior Free Lexicographic Exploration and eXploitation (PF-LEX) given in Algorithm <ref>, which learns to select near-lexicographic optimal arms without any prior information on the mean arm rewards. 

PF-LEX takes as input ϵ>0, which is proportional to the suboptimality that the learner aims to tolerate in the objectives (this will be adjusted based on the time horizon T). Similar to OMG-LEX, it keeps for each arm a the counter N_a(t) and the sample mean reward μ̂^i_a(t), ∀ i ∈𝒟.

Arm selection of PF-LEX in round t depends on the confidence intervals in the first D-1 objectives. The upper confidence bound (UCB) and the lower confidence bound (LCB) of arm a in objective i are given as u_a^i(t) := μ̂_a^i(t) + c_a(t) and l_a^i(t) := μ̂_a^i(t) - c_a(t) respectively. Here


    c_a(t) := √(1+N_a(t)/N^2_a(t)( 1+ 2 log( AD √(1 + N_a(t) )/δ) )  )

represents the uncertainty in arm a's reward, and δ is called the confidence term, which is also given as input to PF-LEX. As expected, the uncertainty decreases as arm a gets selected. It is easy to see that μ^i_a ∈ [l_a^i(t), u_a^i(t)] with high probability for all objectives and all rounds.

In each round, PF-LEX estimates the set of near-lexicographic optimal arms. For this, similar to <cit.>, we say that arms a and b are linked in objective i if [l_a^i(t),u_a^i(t)]∩[l_b^i(t),u_b^i(t)]≠∅. When a and b are in the same component of the transitive closure of the linked relation in objective i, we say they are chained in objective i and write a C_i,t b. Starting from 𝒜̂_*^0(t) = 𝒜, PF-LEX recursively computes the estimate Â^i_*(t) of A^i_* for i ∈ [D-1]. After it computes Â_*^i-1(t), it identifies the optimistic near-lexicographic optimal arm in objective i as â^i_*(t) = _a ∈Â_*^i-1(t) u_a^i(t). Then, it sets Â^i_*(t) = { a ∈Â_*^i-1(t): a C_i,t â_*^i(t) }.

Suppose we always select â_*^D(t), which happens to be in S^i_* for some round t. For this case, we show in Lemma <ref> in the appendix that the regret incurred in this round is bounded by the length of the chain formed by 𝒜̂_*^i(t). In order to guarantee regret that is proportional to ϵ, we want the length of the chains not be more than a constant factor of ϵ. As it is not always possible to shrink the chains by always selecting â_*^D(t), to achieve our goal, we require all arms in 𝒜̂_*^1(t) to have narrow confidence intervals. Thus, PF-LEX selects a(t)=a∈𝒜̂_*^1(t) if there is an arm a with high uncertainty, i.e., c_a(t)>ϵ/2. On the other hand, if c_a(t)≤ϵ/2 for all a∈𝒜̂_*^1(t), then PF-LEX simply selects a(t)=â^D_*(t). Algorithm <ref> shows a more efficient implementation of PF-LEX that does not compute Â_*^j(t) for j>1 when a(t) is selected from Â_*^1(t). Finally, After PF-LEX selects arm a(t), it observes the random reward vector r(t) = (r^1(t), … , r^D(t)) of arm a(t), and then, updates the sample mean estimates of the rewards in objectives i∈𝒟 and the counter of a(t). 



The following theorem shows that PF-LEX achieves Õ(T^2/3) regret. 

 
	When PF-LEX is run with δ∈ (0,1) and ϵ > 0, with probability at least 1-δ, for all i∈𝒟 and for all T≥ 1, we have
	
    _pb^i(T) ≤ 4√(2)B_T,δ√(| S^i_*|T) + ( 3+16/ϵ^2log2√(e)AD/ϵδ)| S^i_*|Δ^i_max + ϵ(A-1)T

	where B_T,δ := √(1+2log(AD√(T)/δ)).
	
	Given a particular time horizon T, by setting ϵ = T^-1/3, with probability at least 1-δ, we have
	
    _pb^i(T) ≤ 4√(2)B_T,δ√(| S^i_*|T) + ( 3+16T^2/3log2√(e)ADT^1/3/δ)| S^i_*|Δ^i_max + (A-1)T^2/3 .

	
	Moreover, taking δ=1/T, [_pb^i(T)] = Õ(T^2/3).



	Unlike the cases with prior information, an analogue of the regret bound in Theorem <ref> will not hold for the priority-free regret when 𝒮^i_* is replaced by S^i. Any two arms that are both lexicographic optimal in the first i-1 objectives are linked in these objectives with high probability. If one happens to be the selected arm, we are confident that they are both in 𝒜̂_*^i-1. When the selected arm is in 𝒮_*^i, we use this fact and compare it to a lexicographic optimal arm to conclude that the gap of the selected arm in objective i is smaller than the regret that we aim to tolerate. However, we fail to make any deductions about the higher indexed objectives.





§ EXPERIMENTS
 
We demonstrate our results in three different settings with A=3 and D=2. All rewards are assumed to come from independent Bernoulli distributions in both objectives with expected reward vectors given in Table <ref>. In all settings, the only lexicographic optimal arm is the first arm and Δ_min^1=Δ_min^2=0.10. We focus on the priority-based regret in this section. Additional experiments that also consider the priority-free regret are given in the appendix.

In Setting 1, apart from the lexicographic optimal arm, there is another arm that is also optimal in objective 1, which requires the learner to consider rewards in objective 2. However, the third arm makes this tricky. It is not only suboptimal in objective 1 but also has very high reward in objective 2.

Setting 2 is specifically designed to be challenging for Cases 1 and 2. Since arms that are not lexicographic optimal are suboptimal in exactly one objective, eliminating arms based on information from the other objective is not possible.

Setting 3 contrasts with Setting 1. Unlike Setting 1 in which the expected reward of arm 3 in objective 2 is much higher than the lexicographic optimal expected reward, in Setting 3, it is much lower. However, the gap of arm 3 in objective 2 in Setting 3 is same as the absolute gap of arm 3 in Setting 1.

For all cases, we set T=10^5 and average the regret of the learners over 100 individual runs. We consider OM-LEX, NOM-LEX, and PF-LEX with prior knowledge and parameters that are summarized in Table <ref>. For PF-LEX, we do not consider the choices for ϵ and δ given in Theorem <ref> because they require a large number of rounds for the initial exploration stage of the algorithm. Instead, we consider different exponents of T as both ϵ and δ (see the appendix for additional discussion and a result which shows the regret of PF-LEX for ϵ = δ = T^-1/3 for T=5×10^8).



Table <ref> shows the regrets of OM-LEX 1, NOM-LEX 1, 2, 3, and PF-LEX 1, 2 in Settings 1, 2 and 3 at T=10^5. There, we also report the performance of the variants of OM-LEX and NOM-LEX which only learn from the first objective and ignore the second objective, i.e., they act as if D=1. Note that all settings are equivalent for objective 1.


p denotes × 10^-12 and f denotes × 10^-15. Average regrets are rounded to three most significant digits and standard deviations are rounded to two most significant digits.

By looking at the regrets in objective 1 of OM-LEX 1, NOM-LEX 1, and their single objective variants, we observe how information from objective 2 helps learning in objective 1. OM-LEX takes advantage of large absolute gaps independent from whether the actual mean reward is higher or lower than the mean reward of arm 1. As a result, in Settings 1 and 3, it achieves lower regret in objective 1 than its single objective variant does. NOM-LEX is capable of doing this only when the gap is positive, a large absolute gap is not sufficient. As a result, only in Setting 3, it outperforms its single objective variant. In Setting 2, where information from objective 2 is not as useful as it is in Settings 1 and 3 to rule out the suboptimal arm in objective 1, OM-LEX 1 and NOM-LEX 1 perform worse than the other settings in objective 1.

By looking at the regrets of NOM-LEX 1, 2, and 3, we observe how different prior information affects the performance of NOM-LEX. Consistent with the proven regret bounds, knowing near optimal expected rewards that are closer to the lexicographic optimal ones decreases the regret in all objectives. When the near optimal expected rewards are extremely close to the lexicographic optimal ones, the performance of NOM-LEX is very similar to that of OM-LEX.




§ CONCLUSION AND FUTURE WORK
 
We proposed a new multiobjective MAB problem, called the Lex-MAB, where the learner aims to minimize its regret with respect to lexicographic optimal arms. We studied the Lex-MAB with and without prior information on the expected rewards. We proved that the regret is uniformly bounded when the learner knows either the lexicographic optimal expected rewards or near-lexicographic optimal expected rewards. We also made a connection between knowing near-lexicographic optimal expected rewards and satisficing, and proved that uniformly bounded regret can be achieved for the MAB with satisficing objectives. Interestingly, we showed that the regret incurred in an objective also depends on the prior information and observations from the other objectives. We also showed that the learner can still achieve Õ(T^2/3) gap-free regret without prior information. An important open question is whether O(√(T)) gap-free regret can be achieved in the Lex-MAB. This will answer the question of whether learning in the Lex-MAB without prior information is fundamentally more difficult than learning in the classical stochastic MAB without prior information. The case where there is prior information only for a subset of objectives is also worth investigating in the future. Another important future research direction is to extend the current work in the multiobjective MAB to minimize the regret with respect to a target arm other than a lexicogrpahic optimal arm by exploiting the prior information about the expected rewards of the target arm. 



IEEEtran




§ APPENDIX




 §.§ Additional Theorems

 
	When OM-LEX is run for Case 1, ∀ i∈𝒟 and ∀ T≥ 1, we have
	
    [^i_pf(T)] ≤∑_a∈𝒮^i( (π^2/3D + 1 )Δ_a^i+ 36/∇_a^maxlog17/∇_a^max)  .




	Note that 
	
    [^i_pf(T)]     = [ ∑_t=1^T Δ_a(t)^i ] 
       ≤[ ∑_t=1^T Δ_a(t)^i{a(t)∈𝒮^i}] 
       ≤∑_a∈𝒮^i( (π^2/3D + 1 )Δ_a^i+ 36/∇_a^maxlog17/∇_a^max)

	where we prove (<ref>) by replacing 𝒮_*^i with 𝒮^i in the proof of Theorem <ref>.


 
	Redefine Δ_min^i:=min_a∈𝒮^iΔ_a^i, ∀ i∈𝒟. When NOM-LEX is run for Case 2, ∀ i∈𝒟 and ∀ T≥ 1, we have
	
    [^i_pf(T)] ≤∑_a∈𝒮^i( (π^2/6D + 1 )Δ_a^i+ 36Δ_a^i/(max_j∈𝒟(Δ_a^j-δ_j))^2log17/max_j∈𝒟(Δ_a^j-δ_j))  .




	We redefine Δ_min^i as stated in the theorem. Then, 
	
    [ ^i_pf(T) ]    = [ ∑_t=1^T Δ_a(t)^i ] 
       ≤[ ∑_t=1^T Δ_a(t)^i{a(t)∈𝒮^i}] 
       ≤∑_a∈𝒮^i( (π^2/6D + 1 )Δ_a^i+ 36Δ_a^i/(max_j∈𝒟(Δ_a^j-δ_j))^2log17/max_j∈𝒟(Δ_a^j-δ_j))

	where we prove (<ref>) by replacing 𝒮_*^i with 𝒮^i in the proof of Theorem <ref>.


Note that redefining Δ_min^i as min_a∈𝒮^iΔ_a^i in Case 2 implies that the learner has stronger prior knowledge on the near-lexicographic optimal expected rewards, since min_a∈𝒮^iΔ_a^i ≤min_a∈𝒮^i_*Δ_a^i.




 §.§ Multiobjective MAB with Satisficing Objectives
 

In this section, we extend the satisfaction-in-mean-reward problem introduced in <cit.> to the multiobjective setting. We keep the same system model but introduce the concept of satisficing optimality and a new notion of regret that captures this concept.

Satisficing Optimality: In the satisficing setting, the learner is given a target threshold η_i for each objective i∈𝒟. We say that an arm a is satisficing “optimal” or simply satisficing in objective i if and only if its mean reward in objective i is equal to or larger than the corresponding target threshold. Let 𝒜_s^i:={a∈𝒜:μ_a^i≥η_i} be the set of satisficing arms in objective i and 𝒮_s^i:=𝒜-𝒜_s^i be the set of non-satisficing arms in objective i. The satisficing goal is to play arms that are satisficing in all objectives. We assume such arms exist and call them satisficing “optimal” arms. Then, we use * to denote an arbitrary satisficing “optimal” arm and call it the “optimal” satisficing arm. Note that η_i≤μ_*^i for all i∈𝒟 and define δ_i:=μ_*^i-η_i for all i∈𝒟.

Regret Definition: The satisficing regret in objective i is given as _s^i(T):=∑_t=1^T (Δ_a(t)^i-δ_i) 𝕀{ a(t)∈𝒮_s^i } and the satisficing regret is defined as the tuple _s(T):=(_s^1(T),…,_s^D(T)). Note that an arm a incurs regret in objective i only when it is not satisficing in that objective and the amount of regret incurred is equal to the gap between its mean reward in objective i and the corresponding target threshold, i.e., Δ_a^i-δ_i = η_i - μ_a^i.


    When D=1, the multiobjective formulation reduces to the exact same problem introduced in <cit.> as Problems 1 and 2 (satisfaction-in-mean-reward problem).


Assuming η_i=0 for all i∈𝒟 without any loss of generality,[See Remark <ref> for a detailed discussion of why the generality is not lost.] the algorithm proposed for Case 2, which is NOM-LEX, can also be used to solve the satisficing goal in the multiobjective MAB. Since the goal now is to minimize the satisficing regret rather than the lexicographic regret, we no longer need η_i to lie between the lexicographic optimal and the second highest lexicographic optimal expected rewards in objective i. The following theorem bounds the expected satisficing regret for NOM-LEX.

 
    When NOM-LEX is run for the satisficing goal, ∀ i∈𝒟 and ∀ T≥ 1, we have
    
    [_s^i(T)] ≤∑_a∈𝒮_s^i( (π^2/6D+1)(Δ_a^i-δ_i) + 36/max_j∈𝒟(Δ_a^j-δ_j)log17/max_j∈𝒟(Δ_a^j-δ_j))  .




    Replacing lexicographic optimality with satisficing optimality, 𝒮_*^i with 𝒮_s^i, and every instance of the exact phrase Δ_a^i (and Δ_a(t)^i) with Δ_a^i-δ_i (and Δ_a(t)^i-δ_i), the proof of Theorem <ref> holds for Theorem <ref>
     as well. Note that
    
    Δ_a^i-δ_i/(max_j∈𝒟(Δ_a^j-δ_j))^2≤1/max_j∈𝒟(Δ_a^j-δ_j)

    for all i∈𝒟.


 
    When NOM-LEX is run for the single objective satisfaction-in-mean-reward problem (D=1), ∀ T≥ 1, we have
    
    [_s(T)] ≤∑_a∈𝒮_s( (π^2/6D+1)(Δ_a-δ) + 36/Δ_a-δlog17/Δ_a-δ)  .

    For simplicity, the objective index 1 is omitted.



    Theorem <ref> and Corollary <ref> show that bounded regret is possible for satisfaction-in-mean-reward problem whether it is single objective or multiobjective, when the learner is given the target thresholds. This result is directly in conflict with Corollary 2 of <cit.>, which claims a logarithmic lower bound on the single objective case, and suggests that satisfaction-in-mean-reward UCL algorithm given in Section VI-A of <cit.> is not optimal since it fails to achieve bounded regret.




 §.§ Additional Experiments

Figure <ref> shows the regrets of OM-LEX 1, NOM-LEX 1, PF-LEX 1 in Setting 1. We observe that the regret of OM-LEX in objective 1 is significantly smaller than the regret of NOM-LEX. We believe this is the case because OM-LEX is able to take advantage of the large absolute gap of arm 3 to eliminate it early on, whereas NOM-LEX cannot. The behavior of PF-LEX is explained as follows. Until around round 30000, it explores all three arms uniformly since their estimated rewards in objective 1 are still chained to each other. At round 30000, the gap between the arms is deemed small enough with respect to the time horizon of the problem.

In the remaining rounds, it plays only the optimistic near-lexicographic optimal arm in objective 2 (â^2_*(t)). 



For this case, ϵ matches with the minimum suboptimality gap. Thus, although PF-LEX always chooses â^2_*(t), because Â^1_*(t) =  A^1_*, it learns to play optimally. 
As a remark, we note that PF-LEX could incur high regret in objective 1 (see PF-LEX 2 in Table <ref>) if the minimum suboptimality gap were smaller than ϵ. 



Next, for Setting 1, we consider PF-LEX 3 that has parameters ϵ=δ=T^-1/3 as given in Table <ref> (that match with the optimal choice for ϵ given in Theorem <ref>), run simulations for T=5×10^8, and report the average regret of the learner over 5 runs (Figure <ref>). This result illustrates the identifiability problem introduced earlier that makes learning lexicographic optimal arms particularly challenging. We see that PF-LEX rules out arm 3 as a potential lexicographic optimal arm and stops incuring regret in objective 1 very early on. However, since it is not possible to be confident in that both arm 1 and arm 2 have equal expected rewards in objective 1, the algorithm still keeps exploring them uniformly until around round 2× 10^8. During this exploration stage, it incurs linear regret in objective 2. Once both arms are deemed to be optimal in objective 1, PF-LEX starts exploiting the optimistic near-lexicographic optimal arm in objective 2, after which the increase of the regret in objective 2 drops drastically.



We also present experiments in two additional settings with D=3. In Setting 4, there are 43 arms with expected reward vectors in {0.90,0.50,0.40,0.10}^3 such that each arm has a unique expected reward vector, where we eliminated arms that lexicographically dominate (0.50,0.50,0.50) so that it is the only lexicographic optimal arm and Δ_min^1=Δ_min^2=Δ_min^3=0.10. Setting 4 features a large variety of arms with combinations of expected rewards that are much higher than, equal to, slightly lower than, and much lower than the lexicographic optimal expected rewards in all objectives. 

In Setting 5, there are 19 arms, where we eliminated arms in 𝒮_*^2 from Setting 4 so that 𝒮_*^2=∅ and Δ_min^2=∞ while Δ_min^1=Δ_min^3=0.10.

Table <ref> shows OMG-LEX and NOM-LEX with different prior knowledge and parameters than the ones considered in Section <ref>.



We run simulations with T=10^5 and average the regret of the learners over 100 individual runs. Different from simulations in Section <ref>, we give results for priority-free regrets as well.

Table <ref> shows the priority-based and priority-free regrets of OM-LEX 2, NOM-LEX 4 and 5 in Settings 4 and 5 at T=10^5. Since NOM-LEX considers arms with very high expected rewards compared to the near optimal expected reward as potential optimal arms, it tends to incur a lot more negative regret in priority-free settings as opposed to OM-LEX, which only looks for arms with expected rewards that are very close to the lexicographic optimal expected rewards.

In Setting 5,[Note that the prior information of NOM-LEX 5 is not valid for Setting 4.] note that any δ_2>0 would guarantee a bounded regret for NOM-LEX (since Δ_min^2=∞). Moreover, δ_2 appears in none of our regret bounds in Theorems <ref> and <ref> for Setting 5. However, our numerical experiments show that it still affects the regret. This is because, knowing a larger δ_2 better captures the information Δ_min^2=∞ and results in having smaller regret in objective 1. 







 §.§ Proof of Theorem <ref>


We use the following fact to prove both Theorem <ref> and <ref>.
[Results from the proof of Theorem 9 in <cit.>] 
    Given Δ>0, for all arms a∈𝒜, for all objectives i∈𝒟 and for all rounds t∈{1,2,…,T}, we have
    
    ∑_w=1^∞( μ̂_a^i(t)-μ_a^i>Δ-√(4log N_a(t)/N_a(t)) |  N_a(t)=w  )  
          = ∑_w=1^∞( μ̂_a^i(t)-μ_a^i<√(4log N_a(t)/N_a(t))-Δ |  N_a(t)=w ) 
         ≤36/Δ^2log17/Δ .




For an arm a that is not lexicographic optimal, let †(a):=_j∈𝒟∇_a^j so that ∇_a^†(a)=∇_a^max. When a can be inferred from the context, †(a) is denoted by † only. For all objectives i∈𝒟, we decompose [^i(T)] as

    [^i(T)]    = [ ∑_t=1^T {a(t)∈𝒮_*^i}Δ_a(t)^i ] 
       = [ ∑_a∈𝒮_*^i∑_t=1^T {a(t)=a}Δ_a^i ] 
       = [ ∑_a∈𝒮_*^i∑_t=1^T {t≤ A, a(t)=a}Δ_a^i ] 
          + [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, |μ̂_a^†(t)|<√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ] 
          + [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, |μ̂_a^†(t)|≥√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ]  .


Bounding (<ref>) is trivial, since each arm is played exactly once for rounds t≤ A. We have

    [ ∑_a∈𝒮_*^i∑_t=1^T {t≤ A, a(t)=a}Δ_a^i ]    = [ ∑_a∈𝒮_*^i∑_t=1^T {t=a}Δ_a^i ] 
       = ∑_a∈𝒮_*^i[ ∑_t=1^T {t=a}] Δ_a^i 
       = ∑_a∈𝒮_*^iΔ_a^i  .


In order to bound (<ref>), we define τ_a(w) as the wth round for which a(t)=a, and w_a(T) as the number of rounds for which a(t)=a by round T. By definition, N_a(τ_a(w+1))=w, τ_a(1)≤ A and w_a(T)≤ T hold for all arms a. Thus, we have

    [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, |μ̂_a^†(t)|<√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ] 
         =∑_a∈𝒮_*^i[ ∑_w=1^w_a(T)-1∑_t=τ_a(w)+1^τ_a(w+1){ |μ̂_a^†(t)|<√(4log N_a(t)/N_a(t)), a(t)=a}] Δ_a^i 
          = ∑_a∈𝒮_*^i[ ∑_w=1^w_a(T)-1{ |μ̂_a^†(τ_a(w+1))|<√(4log w/w)}] Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_w=1^∞( |μ̂_a^†(τ_a(w+1))|<√(4log w/w)) Δ_a^i  .


When μ_a^†=∇_a^†, we have

    ∑_w=1^∞( |μ̂_a^†(τ_a(w+1))|<√(4log w/w))    ≤∑_w=1^∞( μ̂_a^†(τ_a(w+1))<√(4log w/w)) 
       ≤∑_w=1^∞( μ̂_a^†(τ_a(w+1))-μ_a^†<√(4log w/w)-∇_a^†) 
       ≤36/(∇_a^†)^2log17/∇_a^† ,

where (<ref>) is due to Fact <ref>.

Similarly, when μ_a^†=-∇_a^†, we have

    ∑_w=1^∞( |μ̂_a^†(τ_a(w+1))|<√(4log w/w))    ≤∑_w=1^∞( μ̂_a^†(τ_a(w+1))>-√(4log w/w)) 
       ≤∑_w=1^∞( μ̂_a^†(τ_a(w+1))-μ_a^†>∇_a^†-√(4log w/w)) 
       ≤36/(∇_a^†)^2log17/∇_a^† ,

where (<ref>) is again due to Fact <ref>.

Combining (<ref>) and (<ref>), we obtain

    (<ref>)   ≤∑_a∈𝒮_*^i(36/(∇_a^†)^2log17/∇_a^†) Δ_a^i 
       ≤∑_a∈𝒮_*^i36/∇_a^†log17/∇_a^† .


In order to bound (<ref>), we observe that t>A ∧ |μ̂_a^†(t)|≥√(4log N_a(t)/N_a(t))∧ a(t)=a can only occur during an exploration stage, where each arm is played successively. Hence, we can infer that

    
  * a(t-a+*)=*,
    
  * t-a+1>A,
    
  * 𝒜̂_*(t-a+1)=∅, which implies that there exists an objective j such that
    
    |μ̂_*^j(t-a+*)| = |μ̂_*^j(t-a+1)| ≥√(4log N_*(t-a+1)/N_*(t-a+1)) = √(4log N_*(t-a+*)/N_*(t-a+*)) ,

    since arm * is not played after round t-a+1 until round t-a+*.


Using these observations and defining t_a:=t-a+*, we obtain

    [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, |μ̂_a^†(t)|≥√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ] 
          = [ ∑_a∈𝒮_*^i∑_t=1^T {∃ j: t_a>A, |μ̂_*^j(t_a)|≥√(4log N_*(t_a)/N_*(t_a)), a(t_a)=*}Δ_a^i ] 
         ≤∑_a∈𝒮_*^i∑_j=1^D [ ∑_t=1^T {t_a>A, |μ̂_*^j(t_a)|≥√(4log N_*(t_a)/N_*(t_a)), a(t_a)=*}Δ_a^i ] 
         ≤∑_a∈𝒮_*^i∑_j=1^D [ ∑_t=1^T {t>A, |μ̂_*^j(t)|≥√(4log N_*(t)/N_*(t)), a(t)=*}Δ_a^i ] 
         =∑_a∈𝒮_*^i∑_j=1^D [ ∑_w=1^w_*(T)-1∑_t=τ_*(w)+1^τ_*(w+1){ |μ̂_*^j(t)|≥√(4log N_*(t)/N_*(t)), a(t)=*}] Δ_a^i 
          = ∑_a∈𝒮_*^i∑_j=1^D [ ∑_w=1^w_*(T)-1{ |μ̂_*^j(τ_*(w+1))|≥√(4log w/w)}] Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_j=1^D ∑_w=1^∞( |μ̂_*^j(τ_*(w+1))|≥√(4log w/w)) Δ_a^i 
         =∑_a∈𝒮_*^i∑_j=1^D ∑_w=1^∞[ ( μ̂_*^j(τ_*(w+1))≤-√(4log w/w)) + ( μ̂_*^j(τ_*(w+1))≥√(4log w/w)) ] Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_j=1^D ∑_w=1^∞2/w^2Δ_a^i 
         ≤∑_a∈𝒮_*^i( π^2/3) DΔ_a^i  ,

where (<ref>) is due to Hoeffding's inequality for sub-Gaussian random variables <cit.>.




 §.§ Proof of Theorem <ref>

For an arm a that is not lexicographic optimal, let †(a):=_j∈𝒟Δ_a^j-δ_j. When a can be inferred from the context, †(a) is denoted by † only. For all objectives i∈𝒟, we decompose [^i(T)] as

    [^i(T)]    = [ ∑_t=1^T {a(t)∈𝒮_*^i}Δ_a(t)^i ] 
       = [ ∑_a∈𝒮_*^i∑_t=1^T {a(t)=a}Δ_a^i ] 
       = [ ∑_a∈𝒮_*^i∑_t=1^T {t≤ A, a(t)=a}Δ_a^i ] 
          + [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, μ̂_a^†(t)>-√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ] 
          + [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, μ̂_a^†(t)≤-√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ]  .


Bounding (<ref>) is trivial, since each arm is played exactly once for rounds t≤ A. We have

    [ ∑_a∈𝒮_*^i∑_t=1^T {t≤ A, a(t)=a}Δ_a^i ]    = [ ∑_a∈𝒮_*^i∑_t=1^T {t=a}Δ_a^i ] 
       = ∑_a∈𝒮_*^i[ ∑_t=1^T {t=a}] Δ_a^i 
       = ∑_a∈𝒮_*^iΔ_a^i  .


In order to bound (<ref>), we use τ_a(w) and w_a(T) defined in the proof of Theorem <ref>. We have

    [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, μ̂_a^†(t)>-√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ] 
         =∑_a∈𝒮_*^i[ ∑_w=1^w_a(T)-1∑_t=τ_a(w)+1^τ_a(w+1){μ̂_a^†(t)>-√(4log N_a(t)/N_a(t)), a(t)=a}] Δ_a^i 
          = ∑_a∈𝒮_*^i[ ∑_w=1^w_a(T)-1{μ̂_a^†(τ_a(w+1))>-√(4log w/w)}] Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_w=1^∞( μ̂_a^†(τ_a(w+1))>-√(4log w/w)) Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_w=1^∞( μ̂_a^†(τ_a(w+1))-μ_a^†>Δ_a^†-δ_†(a)-√(4log w/w)) Δ_a^i 
         ≤∑_a∈𝒮_*^i36Δ_a^i/(Δ_a^†-δ_†(a))^2log17/Δ_a^†-δ_†(a) ,

where (<ref>) is due to Fact <ref>.

In order to bound (<ref>), we observe that t>A ∧μ̂_a^†(t) ≤ -√(4log N_a(t)/N_a(t))∧ a(t)=a can only occur during an exploration stage, where each arm is played successively. Hence we can infer that

    
  * a(t-a+*)=*,
    
  * t-a+1>A,
    
  * 𝒜̂_*(t-a+1)=∅, which implies that there exists an objective j such that
    
    μ̂_*^j(t-a+*) = μ̂_*^j(t-a+1) ≤ -√(4log N_*(t-a+1)/N_*(t-a+1)) = -√(4log N_*(t-a+*)/N_*(t-a+*)) ,

    since arm * is not played after round t-a+1 until round t-a+*.


Using these observations and defining t_a:=t-a+*, we obtain

    [ ∑_a∈𝒮_*^i∑_t=1^T {t>A, μ̂_a^†(t)≤-√(4log N_a(t)/N_a(t)), a(t)=a}Δ_a^i ] 
          = [ ∑_a∈𝒮_*^i∑_t=1^T {∃ j: t_a>A, μ̂_*^j(t_a)≤-√(4log N_*(t_a)/N_*(t_a)), a(t_a)=*}Δ_a^i ] 
         ≤∑_a∈𝒮_*^i∑_j=1^D [ ∑_t=1^T {t_a>A, μ̂_*^j(t_a)≤-√(4log N_*(t_a)/N_*(t_a)), a(t_a)=*}Δ_a^i ] 
         ≤∑_a∈𝒮_*^i∑_j=1^D [ ∑_t=1^T {t>A, μ̂_*^j(t)≤-√(4log N_*(t)/N_*(t)), a(t)=*}Δ_a^i ] 
         =∑_a∈𝒮_*^i∑_j=1^D [ ∑_w=1^w_*(T)-1∑_t=τ_*(w)+1^τ_*(w+1){μ̂_*^j(t)≤-√(4log N_*(t)/N_*(t)), a(t)=*}] Δ_a^i 
          = ∑_a∈𝒮_*^i∑_j=1^D [ ∑_w=1^w_*(T)-1{μ̂_*^j(τ_*(w+1))≤-√(4log w/w)}] Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_j=1^D ∑_w=1^∞( μ̂_*^j(τ_*(w+1))≤-√(4log w/w)) Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_j=1^D ∑_w=1^∞( μ̂_*^j(τ_*(w+1))-μ_*^j≤-√(4log w/w)) Δ_a^i 
         ≤∑_a∈𝒮_*^i∑_j=1^D ∑_w=1^∞1/w^2Δ_a^i 
         ≤∑_a∈𝒮_*^i( π^2/6) DΔ_a^i  ,

where (<ref>) holds since μ_*^j=δ_j ≥ 0 and (<ref>) is due to Hoeffding's inequality for sub-Gaussian random variables <cit.>.




 §.§ Proof of Theorem <ref>

First, we state a concentration inequality that will be used in the proof. 

   (Lemma 6 in <cit.>) 
	Consider an arm a for which the rewards of objective i are generated by a process { R^i_a(t) }_t=1^T with μ^i_a= E [R^i_a(t)], where the noise R^i_a(t) - μ^i_a is conditionally 1-sub-Gaussian. Let N_a(T) denote the number of times a is selected by the beginning of round T. 
	Let μ̂_a(T) = ∑_t=1^T-1I (a(t) =a ) R^i_a(t) / N_a(T) for N_a(T) >0 and μ̂_a(T) = 0 for N_a(T) = 0.
	Then, for any 0 < δ < AD with probability at least 1-δ/ (AD) we have
	
	
    | μ̂_a(T)  - μ_a |     ≤√(1+N_a(T)/N^2_a(T)( 1 + 2 log(   AD √(1 + N_a(T) )/δ)  
    		)  )  ∀ T ∈ℕ.




Let 
UC^i_a := ∪_t=1^T{μ^i_a ∉[ l^i_a(t)  , u^i_a(t) ] }, 
UC^i := ∪_a ∈ AUC^i_a 
and UC := ∪_i ∈ DUC^i.
The following lemma bounds the probability of UC. 

 
	( UC ) ≤δ.


	This follows from Lemma <ref>. We observe that {μ^i_a ∈[ l^i_a(t)  , u^i_a(t) ] } =  { | μ^i_a - μ̂^i_a(t) | ≤ c_a(t)  }. Thus, Lemma <ref> shows that UC^i_a holds with probability at least 1 - δ/(AD), and hence, UC^i_a holds with probability at most δ/(AD). Applying the union bound, we get ( UC ) ≤δ.
	


Let T := { 1 ≤ t ≤ T : ∀ a∈𝒜̂_*^1(t): c_a(t)≤ϵ/2 } denote the set of rounds in which PF-LEX selects the arm â_*^D(t) and T := {1,…,T} -  T. In the following lemma, the gap of the arm selected in round t ∈ T in objective i is bounded as a function of ϵ and the length of the confidence interval of the selected arm on event UC if the selected arm is in 𝒮_*^i. 

 
	When PF-LEX is run, the following holds on event UC if a(t)∈𝒮_*^i: μ_*^i-μ_a(t)^i ≤ u_a(t)^i(t)-l_a(t)^i(t) + ϵ(A-1) for t ∈ T.


	Consider any lexicographic optimal arm *. We have 
	
    μ_*^i-μ_a(t)^i    ≤ u_*^i(t)-l_a(t)^i(t) 
       ≤ u_â_*^i(t)^i(t)-l_a(t)^i(t) 
       ≤ u_a(t)^i(t)-l_a(t)^i(t) + ϵ(A-1)  .

   Here (<ref>) holds since μ_*^i≤ u_*^i(t) and μ_a(t)^i≥ l_a(t)^i(t) on event UC. (<ref>) holds by the definition of â_*^i(t) and the fact that *∈𝒜̂_*^i-1(t), which is proven by induction. For this, consider any objective j∈{1,…,i-1}. We first observe that *∈𝒜̂_*^0(t) and a(t)=â_*^D(t)∈𝒜̂_*^D-1(t)⊆𝒜̂_*^j(t). Next, we show that *∈𝒜̂_*^j-1(t)  *∈𝒜̂_*^j(t) to conclude that *∈𝒜̂_*^i-1(t). Since a(t)∈𝒮_*^i, μ_a(t)^j=μ_*^j, which implies that a(t) and * are linked in objective j. Since a(t)∈𝒜̂_*^j(t), a(t) is chained to â_*^j(t) in objective j, which implies that * is chained to â_*^j(t) in objective j as well.
    
	Finally, if i=D, (<ref>) holds trivially as a(t)=â_*^i(t)=â_*^D(t). Otherwise, since a(t)=â_*^D(t)∈𝒜̂_*^D-1(t)⊆𝒜̂_*^i(t), a(t) is chained to â_*^i(t), which implies that |u_â_*^i(t)^i(t)-u_a(t)^i(t)| ≤ 2(|𝒜̂_*^i(t)|-1)max_a∈𝒜̂_*^i(t)c_a(t) ≤ϵ(A-1).


We also need to bound the regret in objective i for rounds up to round T for which t ∉ T. Let T_a := {t ∈𝒯 : a(t)=a }. Obviously, PF-LEX does not incur any regret in objective i in rounds t ∈ T_a for a ∈ A -  S^i_*, and incurs regret Δ^i_a in objective i in rounds t ∈ T_a for a ∈ S^i_*.

 
	When PF-LEX is run, we have 
	
    ∑_t ∈ T{a(t)∈𝒮_*^i}Δ^i_a(t)   ≤∑_ a ∈ S^*_i (3 + 16/ϵ^2log2√(e) AD/ϵδ)  Δ^i_a

	for all objectives i∈𝒟.
 

	The proof follows from bounding the cardinality of T_a for a ∈ S^i_*. Note that t ∈ T_a happens only when c_a(t) > ϵ/2. Similar to the proof of Theorem 7 in <cit.>, this implies that 
	
    N^2_a(t)-1/N_a(t)+1≤N^2_a(t)/N_a(t)+1≤4/ϵ^2(1+ 2 logAD√(1+N_a(t))/δ)  .

	Then, from Lemma 8 in <cit.>, we obtain N_a(t) ≤ 3 + 16/ϵ^2log2√(e) AD/ϵδ.


In the remaining part, we bound _pb^i(T) under the event UC and [_pb^i(T) ] by using the results of the lemmas above. For the latter, we observe that:

    [ _pb^i(T) ]    =  [_pb^i(T) | UC ]  ( UC ) +  [ _pb^i(T) | UC ]  ( UC ) 
       ≤ T Δ^i_max ( UC  ) +  [ _pb^i(T) | UC ]  .


For each i∈𝒟, the bound for _pb^i(T) is obtained by using the result in Lemmas <ref> and <ref>. By Lemma <ref>, we know that 

    ∑_t ∈ T{a(t)∈𝒮_i^*}Δ^i_a(t)   ≤ 3 | S^i_*|  Δ^i_max  + 16 | S^i_*|  Δ^i_max/ϵ^2log2√(e) AD/ϵδ .

Let N_a := { t∈𝒯 : a(t) = a }. By Lemma <ref>, on event UC (which happens with probability at least 1-δ), we have 

    ∑_t ∈ T{a(t)∈𝒮_i^*}Δ^i_a(t)   ≤∑_a ∈ S^i_*∑_t ∈ N_a ( u^i_a(t) - l^i_a(t) ) + ϵ(A-1)T 
       ≤ 2 √(2)∑_a ∈ S^i_*( B_T,δ∑_ t ∈ N_a√(1/N_a(t) )) + ϵ(A-1)T 
       ≤ 2 √(2) B_T,δ∑_a ∈ S^i_*√(N_a(T)) + ϵ(A-1)T 
       ≤ 4 √(2) B_T,δ√(  | S^i_*|  T ) +  ϵ(A-1)T .






The bound for _pb^i(T) is obtained by summing the results of (<ref>) and (<ref>). Finally, the bounds on the expected regret simply follows from using (<ref>) and setting δ = 1/T.




 §.§ Tables of Notation

General notation is listed in Table <ref>. Notations specific to each case covered in Section <ref> are listed in Tables <ref>, <ref> and <ref> respectively.










