Aadirupa Saha
email: aadirupa@iisc.ac.in.

Pierre Gaillard
email: pierre.gaillard@inria.fr

Dueling Bandits with Adversarial Sleeping

We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). In almost all dueling bandit applications, the decision space often changes over time; eg, retail store management, online shopping, restaurant recommendation, search engine optimization, etc. Surprisingly, this 'sleeping aspect' of dueling bandits has never been studied in the literature. Like dueling bandits, the goal is to compete with the best arm by sequentially querying the preference feedback of item pairs. The non-triviality however results due to the non-stationary item spaces that allow any arbitrary subsets items to go unavailable every round. The goal is to find an optimal 'no-regret' policy that can identify the best available item at each round, as opposed to the standard 'fixed best-arm regret objective' of dueling bandits. We first derive an instance-specific lower bound for DB-SPAA Ω( K-1 i=1 K j=i+1 log T ∆(i,j) ), where K is the number of items and ∆(i, j) is the gap between items i and j. This indicates that the sleeping problem with preference feedback is inherently more difficult than that for classical multi-armed bandits (MAB). We then propose two algorithms, with near optimal regret guarantees. Our results are corroborated empirically.

Introduction

The problem of Dueling-Bandits has gained much attention in the machine learning community [START_REF] Yue | The k-armed dueling bandits problem[END_REF][START_REF] Zoghi | Relative confidence sampling for efficient on-line ranker evaluation[END_REF][START_REF] Zoghi | Copeland dueling bandits[END_REF], which is an online learning framework that generalizes the standard multiarmed bandit (MAB) [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] setting for identifying a set of 'good' arms from a fixed decision-space (set of arms/items) by querying preference feedback of actively chosen item-pairs. More formally, in dueling bandits, the learning proceeds in rounds: At each round, the learner selects a pair of arms and observes stochastic preference feedback of the winner of the comparison (duel) between the selected arms; the objective of the learner is to minimize the regret with respect to a (or set of) 'best' arm(s) in hindsight. Towards this several algorithms have been proposed [START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF][START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF][START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF][START_REF] Gajane | A relative exponential weighing algorithm for adversarial utility-based dueling bandits[END_REF]. Due to the inherent exploration-vs-exploitation tradeoff of the learning framework and several advantages of preference feedback [START_REF] Busa-Fekete | A survey of preference-based online learning with bandit algorithms[END_REF][START_REF] Yue | Interactively optimizing information retrieval systems as a dueling bandits problem[END_REF], many real-world applications can be modeled as dueling bandits, including movie recommendations, retail management, search engine optimization, job scheduling, etc.

However, in reality, the decision spaces might often change over time due to the non-availability of some items, which are considered to be 'sleeping'. This 'sleeping-aspect' of online decision making problems has been widely studied in the standard multiarmed bandit (MAB) literature [START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF][START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF][START_REF] Kale | Hardness of online sleeping combinatorial optimization problems[END_REF][START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF][START_REF] Kanade | Learning hurdles for sleeping experts[END_REF][START_REF] Cortes | Online learning with sleeping experts and feedback graphs[END_REF]. There the goal is to learn a 'no-regret' policy that maps to the 'best awake item' of any available (non-sleeping) subset of items, and the learner's performance is measured with respect to the optimal policy in hindsight. This setting is famously known as Sleeping Bandits in MAB [START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF][START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF][START_REF] Kale | Hardness of online sleeping combinatorial optimization problems[END_REF][START_REF] Cortes | Online learning with sleeping experts and feedback graphs[END_REF]. More discussions are given in Related Works.

Surprisingly, however, the 'sleeping problem' is completely unaddressed in the preference bandits literature, even for the special case of pairwise preference feedback, which is famously studied as Dueling Bandits [START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF][START_REF] Yue | The k-armed dueling bandits problem[END_REF], even though the setup of changing decision spaces are quite relevant in almost every practical applications: Be that in retail stores where some items might go out of production over time, for search engine optimization Parameters. Item set: [K] (known), Preference: P (unknown), Available item sets: S T (observed sequentially) For t = 1, 2, . . . , T , the learner:

• Observes S t ⊆ [K] the set of available items • Chooses (x t , y t ) ∈ S 2 t

• Observes o t := 1(x t y t ) ∼ Ber(P(x t , y t ))

• Incurs r t := 1 /2 P(i * t , x t ) + P(i * t , y t ) -1 ; where i * t is such that min j∈St P(i * t , j) ≥ 1 /2

Figure 1: Setting of DB-SPAA(P, S T ) some websites could be down on certain days, in recommender systems some restaurants might be closed or movies could be outdated, in clinical trials certain drugs could be out of stock, and many more. This work is the first to consider the problem of Sleeping Dueling Bandits, where we formulated the stochastic K-armed dueling bandit problem with adversarial item availabilities. Here at each round t ∈ {1, 2, . . . , T } the item preferences are considered to be generated from a fixed underlying (and of course unknown) preference matrix P ∈ [0, 1] K×K , however, the set of available actions S t ⊆ {1, 2, . . . , K} is assumed to be adversarially chosen by the environment. We call the problem as Sleeping-Dueling Bandit with Stochastic Preferences and Adversarial Availabilities or in brief DB-SPAA(P, S T ), where S T = {S 1 , S 2 , . . . S T } denotes the sequence of available subsets over T rounds. We also assume the preference P follows a 'total-ordering assumption to ensure the existence of a best-item per available subset S t . We describe the setting in Fig. 1 with a formal description in Sec. 2.

Our specific contributions are as follows:

1. We first analyze the fundamental performance limit for the DB-SPAA(P, S T ) problem in Sec. 3: Thm. 1 gives an instance-specific regret lower bound of

Ω K-1 i=1 K j=i+1
log T ∆(i,j) , with ∆(i, j) being the 'preference gap' of item i-vs-j (see Eqn. [START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF]). Our lower bound, which can be of order Ω(K 2 log T /∆), ∆ := min i,j ∆(i, j) being the worst case gap, indicates that the problem of sleeping dueling bandits is inherently more difficult that standard sleeping bandits (MAB), unlike the 'non-sleeping' case where both dueling bandits (with 'total-ordering' assumption on P) and MAB are known to have the same fundamental performance limit of Ω(K log T /∆) (Rem. 1).

2.

We next design a 'fixed confidence regret' algorithm SlDB-UCB (Alg. 1), inspired from the pairwise upper confidence bound (UCB) based algorithm [START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF]. However due to the fixed confidence and 'adversarial-sleeping' nature of the problem, we need to differently maintain pairwise confidence bounds per item (based on the availability sequence {S t }), which makes the resulting algorithm and its subsequent analysis significantly different than standard UCB based dueling bandit algorithms: Precisely given any δ > 0, SlDB-UCB achieves a regret of

O K 3 log(1/δ) ∆ 2
with probability at least 1 -δ over any problem instance of DB-SPAA(P, S T ) (Sec. 4).

3. In Sec. 5, we design another computationally efficient algorithm, SlDB-ED (Alg. 2), for 'expected regret' guarantee. Unlike the previous algorithm (SlDB-UCB), SlDB-ED uses empirical divergence (ED) based measures to filter out the 'good' set of arms, inspired from the idea of RMED algorithm of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF] for standard dueling bandits; however, due to sleeping nature of the items, it requires a different maintenance of 'good' arms and the regret analysis of the algorithm requires derivation of new results (as described in Sec. 5). The algorithm is shown to perform near optimally with an expected non-asymptotic regret upper-bound of (Thm. 6). Note that for any problem instance with constant suboptimality gaps ∆(i, j) = ∆ for all i < j, regret bound of SlDB-ED is tight and matches the lower-bound ensuring the near optimality of SlDB-ED in the worst case. Furthermore, a novelty of our finite time regret analysis lies in showing a cleaner tradeoff between regret vs. availability sequence S T which automatically adapts to the inherent 'hardness' of the sequence of available subsets S T , compared to existing sleeping bandits work for adversarial availabilities in the MAB setting [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF] which only gives a worst-case regret bound over all possible availability sequences (Rem. 3).

4.

Finally we corroborate our theoretical results with extensive empirical evaluations. (Sec. 6).

Related Works. The problem of regret minimization for stochastic multiarmed bandits (MAB) is extremely well studied in the online learning literature [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Agrawal | Analysis of Thompson sampling for the multi-armed bandit problem[END_REF][START_REF] Lattimore | Bandit algorithms[END_REF][START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF][START_REF] Shivaram Kalyanakrishnan | PAC subset selection in stochastic multi-armed bandits[END_REF], where the learner gets to see a noisy draw of absolute reward feedback of an arm upon playing a single arm per round.

A well motivated generalization of MAB framework is Sleeping Bandits [START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF][START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF][START_REF] Kanade | Learning hurdles for sleeping experts[END_REF][START_REF] Kale | Hardness of online sleeping combinatorial optimization problems[END_REF], much studied in the online learning community, where at any round the set of available actions could vary stochastically based on some unknown distributions over the decision space of K items [START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF][START_REF] Cortes | Online learning with sleeping experts and feedback graphs[END_REF] or adversarially [START_REF] Kale | Hardness of online sleeping combinatorial optimization problems[END_REF][START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF][START_REF] Kanade | Learning hurdles for sleeping experts[END_REF]. Besides the reward model, the set of available actions could also vary stochastically or adversarially [START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF][START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF]. The problem is NP-hard when both rewards and availabilities are adversarial [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF][START_REF] Kanade | Learning hurdles for sleeping experts[END_REF][START_REF] Kale | Hardness of online sleeping combinatorial optimization problems[END_REF]. In case of stochastic reward and adversarial availabilities [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF] proposed an UCB based no-regret algorithm, which was also shown to be provably optimal. The case of adversarial reward and stochastic availabilities has also been studied where the achievable regret lower bound is known be Ω( √ KT ) by the inefficient EXP4 algorithm [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF][START_REF] Kale | Hardness of online sleeping combinatorial optimization problems[END_REF].

On the other hand over the last decade, the relative feedback variants of stochastic MAB problem has seen a widespread resurgence in the form of the Dueling Bandit problem, where, instead of getting noisy feedback of the reward of the chosen arm, the learner only gets to see a noisy feedback on the pairwise preference of two arms selected by the learner. The objective of the learner is to minimize the regret with respect to 'best arm in the stochastic model. Several algorithms have been proposed to address this dueling bandits problem, for different notions of 'best arms' or preference models [START_REF] Busa-Fekete | Preference-based rank elicitation using statistical models: The case of mallows[END_REF][START_REF] Szörényi | Online rank elicitation for plackett-luce: A dueling bandits approach[END_REF][START_REF] Zoghi | Relative confidence sampling for efficient on-line ranker evaluation[END_REF][START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF][START_REF] Zoghi | Copeland dueling bandits[END_REF][START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF][START_REF] Wu | Double Thompson sampling for dueling bandits[END_REF][START_REF] Dudík | Contextual dueling bandits[END_REF], or even extending the pairwise preference to subsetwise preferences [START_REF] Sui | Multi-dueling bandits with dependent arms[END_REF][START_REF] Brost | Multi-dueling bandits and their application to online ranker evaluation[END_REF][START_REF] Saha | Battle of bandits[END_REF][START_REF] Saha | PAC Battling Bandits in the Plackett-Luce Model[END_REF][START_REF] Wenbo Ren | PAC ranking from pairwise and listwise queries: Lower bounds and upper bounds[END_REF]. However, surprisingly, unlike the 'sleeping bandits generalization' of MAB, no parallel has been drawn for dueling bandits, which remains our main focus.

Problem Formulation

Notations. Decision space (or item/arm set) [K] := {1, 2, . . . , K}. The available set of items at round t is denoted by S t ⊆ [K]. For any matrix M ∈ R K×K , we define m ij := M (i, j), ∀i, j ∈ [K]. We write S \i = S \ {i}, for any S ⊆ [K] and i ∈ S. 1(•) denotes the indicator random variable which takes value 1 if the predicate is true and 0 otherwise and a rough inequality which holds up to universal constants. For any two items x, y ∈ [K], we use the symbol x y to denote x is preferred over y. Σ K denotes the set of all permutations of the items in set [K]. The KL-divergence of two Bernoullis with biases p and q respectively is written kl(p, q) := p log( p /q) + (1 -p) log( (1-p) /(1-q)). We assume 0 0 := 0.5 (in Alg. 1 and 2). Setup. We consider the problem of stochastic K-armed dueling bandits with adversarial availabilities: At every iteration t = 1, . . . , T , a set of available items (actions) S t ⊆ [K] is revealed, and the learner is asked to choose two items x t , y t ∈ S t . Then, the learner receives a preference feedback o t = 1(x t y t ) ∼ Ber(P(x t , y t )), where P ∈ [0, 1] K×K is an underlying pairwise preference matrix, unknown to the learner. The setting is described in Figure 1. We assume that P respects a 'total ordering', say σ * ∈ Σ K . Without loss of generality, we set σ * = (1, 2, . . . , K) thoughout the paper. This implies P(i, j) ≥ 0.5 for i ≤ j. One possible pairwise probability model which respects 'total ordering' is Plackett-Luce [START_REF] Azari | Random utility theory for social choice[END_REF], where it is assumed that the K items are associated to positive score parameters θ 1 , . . . , θ K , and P(i, j) = θ i /(θ i + θ j ) for all i, j ∈ [K]. In fact any well random utility (RUM) based preference model would have the above property, like [START_REF] Azari | Random utility theory for social choice[END_REF][START_REF] Azari Soufiani | Preference elicitation for general random utility models[END_REF]. Note also that our assumption corresponds to assuming the existence of a Condorcet winner for every subset S t ⊆ [K].

Objective. The objective of the learner is to minimize his regret over T rounds with respect to the best policy in the policy class Π = {π : 2 K → [K] | ∀t ∈ [T ], π(S t ) ∈ S t }, i.e. any π ∈ Π is such that for any t ∈ [T ], π(S t ) ∈ S t . More formally we define the regret as follows:

R T = max π∈Π T t=1 P(π(S t ), x t ) + P(π(S t ), y t ) -1 2 . (1)
We analyze both fixed-confidence and expected regret guarantees in this paper respectively in Sec. 4 (see Thm. 3) and Sec. 5 (see Thm. 6). It is easy to note that under our preference modelling assumptions, the best policy, say π * , turns out to be π * (S) = min{S} for any S ⊆ [K]. We henceforth denote by i * t = π * (S t ). We define the above problem to be Sleeping-Dueling Bandit with Stochastic Preferences and Adversarial Availabilities over the stochastic preference matrix P ∈ [0, 1] K×K and the sequence of available subsets S T = {S 1 , . . . , S T }, or in short DB-SPAA(P, S T ). For ease of notation we respectively define the gaps and the non-zeros gaps as ∆(i, j) := P(i, j) -1/2, and

∆(i, j) + := ∆(i, j) if ∆(i, j) = 0 +∞ if ∆(i, j) = 0 (2)
The regret thus can be rewritten as R T := T t=1 r t , where r t := (∆(i * t , x t ) + ∆(i * t , y t ))/2 denotes the instantaneous regret. We also denote by n ij (t) := t τ =1 1 {x t , y t } = {i, j} the number of times the pair (i, j) is played until time t and by w ij (t) the number of times i beats j in t rounds.

Lower Bound

We first derive a worst case regret lower bound over all possible sequences of S T . The proof idea essentially lies in constructing hard enough availability sequences S T , where no learner can escape learning the preferences of every distinct pair of items (i, j). This leads to a potential lower bound of Ω K 2 log(T )/∆ . For this section we denote P by P K to make the dependency on K more precise.

Theorem 1 (Lower Bound for DB-SPAA(P K , S T )). For any No-regret learning algorithm A, there exists a problem instance DB-SPAA(P K , S T ) with T ≥ K 4 , such that its expected regret is lower-bounded as:

E[R T (A)] ≥ Ω K-1 i=1 K j=i+1 log T ∆(i, j) + .
The No-regret learning algorithm refers to the class of 'consistent algorithms' which do not pull any suboptimal pair more than O(T α ), α ∈ [0, 1] (see Def. 7, Appendix 8)). Proof (sketch) The main argument lies behind the fact that in the worst case the adversary can force the algorithm to learn the preference of every distinct pair (i, j) as for the 'worst-case' sequences S T , a knowledge of the already 'learnt' pairwise preferences would not disclose any information on the remaining pairs; e.g. assuming σ * = (1, 2, . . . , K), revealing the available subsets in the following sequence (1, 2), (1, 3), . . . (1, K), (2, 3), (2, 4), . . . (K -1, K) would force the learner to explore (learn the preferences) all K 2 distinct pairs. The remaining proof establishes this formally, towards which we first show a Ω(ln(T )/∆(1, 2)) regret lower bound for a DB-SPAA instance with just two items (i.e. K = 2) as shown in Lem. 2. The lower bound for any general K can now be derived applying the above bound on independent K 2 subintervals, with the availability sequence (1, 2), [START_REF] Agrawal | Analysis of Thompson sampling for the multi-armed bandit problem[END_REF][START_REF] Noga Alon | Online learning with feedback graphs: Beyond bandits[END_REF]

, . . . (1, K), (2, 3), (2, 4), . . . (K -1, K). The full proof is given in Appendix 8.
Lemma 2 (Lower Bound of DB-SPAA(P K , S T ) for 2 items). For any No-regret learning algorithm A, there exists a problem instance DB-SPAA(P 2 , S T ) such that the expected regret incurred by A on that can be lower bounded as: E[R T (A)] ≥ ∆ -1 log(T ), ∆ being the 'preference-gap' between the two items (i.e. ∆ = P 12 -1 /2, assuming P 12 > 1 /2 or equivalently ∆ > 0).

Remark 1 (Implication of the lower bound). The above result indicates that in the preference based learning setup, the fundamental problem complexity lies in distinguishing every pair of items

1 ≤ i < j ≤ K. If the Algorithm 1 SlDB-UCB 1: input: Arm set: [K], parameters α > 0.5, Confidence parameter δ ∈ [0, 1) 2: init: w ij (1) ← 0, ∀i, j ∈ [K]. 3: define: n ij (t) := w ij (t) + w ji (t), ∀t ∈ [T ] 4: for t = 1, 2, . . . , T do 5: Receive S t ⊆ [K] 6: p ij (t) = w ij (t) n ij (t) , c ij (t) ← α log a ij (t) n ij (t)
, ∀i, j ∈ S t , (assume x 0 := 0.5, ∀x ∈ R)

7: u ij (t) ← p ij (t) + c ij (t), u ii (t) ← 1 /2, ∀i, j ∈ S t UCB of empirical preferences 8:
for k ∈ S t do 9:

C k (t) := {j ∈ S t | u kj (t) > 1 /2} Potential losers to k 10:
end for 11:

C t = {i ∈ S t | |C i (t)| = max j∈St |C j (t)|} Potential best items 12:
Select a random x t from C t . Choose y t ← arg max i∈Ct u ixt (t)

13:

Play (x t , y t ). Receive preference o t 14:

Update: ∀i, j ∈ [K], w xtyt (t + 1) ← w xtyt (t) + o t , w ytxt (t + 1) ← w ytxt (t) + (1 -o t ), a ij (t + 1) ← max{n ij (t + 1), C(K, δ)}, ∀i, j ∈ [K] 15:
end for learner fails to learn the preference of any pair (i, j), the adversary can make the learner suffer O(T ) regret by setting S t = {i, j} henceforth at all round. It is worth noting that in the 'no sleeping' case both dueling bandits and MAB are known to have the same fundamental performance limit of Ω(K log(T )/∆) (assuming P respects a condorcet winner [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]). Thus Thm. 1 shows that the 'sleeping-aspect' of dueling bandits makes the problem K-times harder than 'sleeping-MAB' for which the regret lower bound is known to be only

Ω K i=1 log(T )/∆(i, i + 1) [19].

SlDB-UCB: A Fixed-Confidence Algorithm

In this section, we design an efficient algorithm for the DB-SPAA(K, T ) problem with instance-dependent regret guarantee. Main ideas. Our algorithm, described in Alg. 1, depends on an hyper-parameter α > 0.5 and a confidence parameter δ > 0. It maintains, for each item k ∈ [K], its own record of empirical pairwise estimates of the duels, (i, j) ∈ [K] × [K] and their respective upper confidence bounds defined as:

p ij (t) := wij (t) nij (t) and u ij (t) := p ij (t) + c ij (t), with c ij (t) := α log aij (t) nij (t)
, where w ij (t) denotes the total number of times item i beats j up to round t, n ij (t) := w ij (t) + w ji (t), and for all i, j ∈ [K] and t ∈ [T ]

a ij (t) := max{C(K, δ), n ij (t)} and C(K, δ) := (4α-1)K 2 (2α-1)δ 1 2α-1 .
A key observation is that our careful choice of the confidence bounds c ij (t) ensures that with high probability

p ij (t) ∈ [ p ij (t) -c ij (t), p ij + c ij (t)]
for any duel i, j ∈ [K] and any t ∈ [T ] (Lem. 4). Now at any round t ≥ 1, the algorithm first computes a set of potential winners of S t as

C t = {k ∈ S t | |C k (t)| = max j∈St |C j (t)|}, where C k (t) := {j ∈ S t | u kj (t) > 1 2
} denotes the set of items that item k dominates (optimistically). At each round, we play a random item from the set potential winners C t as the left arm x t . Finally the right-arm y t is chosen to be the most competitive opponent of x t as y t ← arg max i∈Ct u ji (t) from the potential winners. Our arm selection strategy ensures that eventually for all t, algorithm plays the optimal pair (i * t , i * t ) frequently enough as desired.

Theorem 3 (Fixed-confidence regret analysis: SlDB-UCB). Given any δ > 0 and α > 1/2, with probability at least 1 -δ, the regret incurred by SlDB-UCB (Alg. 1) is upper-bounded as:

R T ≤ 2 K-1 i=1 K j=i+1 M ij log 2C(K, δ)M ij where C(K, δ) := (4α -1)K 2 (2α -1)δ 1 2α-1 and M ij = i k=1 4α min ∆(k, i) + , ∆(k, j) + 2 .
The complete proof with a precise dependencies on the model parameters is deferred to Appendix 9.

Remark 2. The dependency on ∆ = min i,j ∆ + (i, j) does not match the lower-bound of Thm. 1, which is of order O(log(T )/∆). Instead, Thm. 3 proves O(log(1/δ)/∆ 2 ). Yet, the bounds are not directly comparable because the lower-bound is on the expected regret while the upper-bound considers fixed-confidence δ and is hence independent of T . All existing dueling bandit algorithms, that minimize the expected regret, suffer an additional constant term of order O(1/∆ 2 ) -see for instance [START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF][START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]. Achieving an order O(1/∆) dependendence is an interesting question for future work.

Proof sketch of Thm. 3. The key steps lie in proving the following four lemmas. The first lemma follows along the line of Lem. 1 of RUCB algorithm [START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF]and shows that all the pairwise estimates are contained within their respective confidence intervals with high probability.

Lemma 4. Let α > 0.5 and δ > 0. Then, for any i, j

∈ [K], with probability at least 1 -δ/K 2 , p ij (t) -c ij (t) ≤ p ij ≤ u ij (t) := p ij (t) + c ij (t), ∀t ∈ [T ] .
The lemma below shows that once the algorithm can not play any suboptimal pair 'too many times'.

Lemma 5. Let α > 0.5. Under the notations and the high-probability event of Lem. 4, for all i, j, k ∈ [K] such that {i, j} = {k, k}, and for any τ ≥ 1

τ t=1 1(i * t = k)1 {x t , y t } = {i, j} ≤ 4α log a i,j (τ ) min ∆(k, i) + , ∆(k, j) + 2 ,
where recall

a ij (τ ) = max C(K, δ), n ij (τ ) .
With probability of at least 1 -δ, the event of Lem. 4 holds and thus so do the ones of Lem. 5. The regret of Alg. 1 then follows from applying the above lemmas with the following careful decomposition of the regret:

R T ≤ K-1 i=1 K j=i+1 T t=1 i k=1 1(i * t = k)1 {x t , y t } = {i, j} = K-1 i=1 K j=i+1 n ij (T )
and the proof is concluded by using Lemma 5 to upper-bound n ij (T ). The complete proof given in Appendix 9.

5 SlDB-ED: An Expected Regret Algorithm

In this section, we propose another computationally efficient algorithm, SlDB-ED (Alg. 2), which achieves nearoptimal expected-regret for DB-SPAA problem, and also performs competitively against SlDB-UCB empirically (see Sec. 6). Furthermore, a novelty of our finite time regret analysis of SlDB-ED lies in showing a cleaner trade-off between regret vs availability sequence S T which automatically adapts to the inherent 'hardness' of the sequence of available subsets S T , unlike the previous attempts made in standard sleeping bandits for adversarial availabilities [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF] (Rem. 3).

Algorithm 2 SlDB-ED

p ij (t) := wij (t) nij (t) , p(i, i) ← 1 /2, ∀i, j ∈ [K] (assume x 0 := 0.5, ∀x ∈ R) 4:
Receive S t ⊆ [K]

B i (t) := {j ∈ [K] \ {i} | p ij (t) ≤ 1 /2} ∩ S t , ∀i ∈ [K]
Empirical winners over i 9:

I i (t) := j∈ Bi(t) n ij (t) kl( p ij (t), 1 /2), ∀i ∈ [K] and i * t ← arg min i∈St I i (t)
10: We again use the notations w ij (t), n ij (t) as used for SlDB-UCB (Alg. 1), with the same initializations. Same as SlDB-UCB, this algorithm also maintains the empirical pairwise preferences p ij (t) for each item pair i, j ∈ [K]. However, unlike the earlier case here we need to ensure an initial t 0 rounds of exploration (t 0 = 1 in the theorem) for every distinct pairs (i, j), and instead of maintaining pairwise UCBs, in this case the set of 'good-items' is defined in terms of empirical divergences for all i ∈ S t

C t := {i ∈ S t | I i (t) -I i * t (t) ≤ α
I i (t) := j∈ Bi(t) n ij (t) kl p ij (t), 1 /2 , B i (t) := j ∈ [K] \ {i} | p ij (t) ≤ 1 /2 ∩ S t
denotes the empirical winners of item i in set S t . Now intuitively since exp(-I i (t)) can be interpreted as the likelihood of i being the best-item of S t , we denote by i * t ← arg min i∈St I i (t) the empirical-best item of round t and define the set of 'near-best' items C t := i ∈ S t | I i (t) -I i * t (t) ≤ α log t , whose likelihood is close enough to that of i * t . Finally the algorithm selects an arm pair (x t , y t ) such that x t is a potential candidate of good arm (which ensures the required exploration) and y t being the strongest challenger of x t w.r.t the empirical preferences. The algorithm is given in Alg. 2.

Theorem 6 (Expected regret analysis SlDB-ED). Let t 0 = 1 and α = 4K. Then as T → ∞, the expected regret incurred by SlDB-ED (Alg. 2) can be upper bounded as: For all ε 2 , . . . , ε K ≥ 0

E R T K 2 + 1≤i<j≤K K1 {∆(i,j)>εj } ∆(i, j) 2 + n ij (T ) min{ε j , ∆(i, j)} + K j=2 K log T max ε j , ∆(j -1, j) + ≤ O min K j=2 K log T ∆(j -1, j) + , KT 2/3 .
The proof is deferred to Appendix 10. Although it borrows some high-level ideas from [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF] for sleeping bandits and from [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF] for RMED in standard dueling bandits, our analysis needed new ingredients in order to obtain O(K 2 (log T )/∆). This is especially the case for the proofs of the technical Lemmas 8 and 9 which significantly differ from "corresponding" technical lemmas of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]. Specifically, both regret bounds of RMED and ours need to control the length of an initial exploration t 0 after which pairwise preferences are well estimated by p ij (t). This is done respectively by our Lemma 8 and Lemma 5 of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]. Yet, RMED's original analysis is based on a union bound over all possible subsets S ⊂ {1, . . . , K} of items (see Equation [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF] in [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]), whose number is exponential in K. Despite our efforts, we could not follow the proof of Lemma 5 of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF], which to the best of our understanding, should yield to an exploration t 0 exponentially large in K contrary to O(1) claimed in [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]. Instead, in our proof of Lem. 8, we carefully apply concentration inequalities to run union bounds over the items directly instead of sets of items.

The upper-bound of Thm. 6 is close to optimal. It suffers at most a suboptimal factor K and exactly matches the lower-bound for some problems. The distribution-free upper-bound of order O(T 2/3 ) matches obtainable standard dueling bandit problems [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF][START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF], since the latter algorithms also suffer constant terms of order ∆ -2 . Yet, it is unclear whether it is optimal or if O( √ T ) can be obtained.

Remark 3 (Sequence S T adaptivity of Alg. 2). It is worth pointing out that the regret bound of Thm. 6 is finite time and automatically adapts to the sequence of available sets S T . In the worst-case, the complexity lies in identifying for all items j the gap with the earlier item j -1. Yet, our regret-bound, which holds for any ε j ≥ 0, will automatically perform a trade-off for each j between the gap ∆(j -1, j) -1 + and ε j j-1

i=1 n ij (T ) the number of times j is played together with a better item i < j. In particular, j-1 i=1 n ij (T ) can be small if j is rarely available in S t while not optimal. Notably, this adaptivity to S T item per item improves the regret guarantee of Thm. (10), [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF], which also addresses the problem of sleeping bandits with 'adversarial availabilities' but for the stochastic multi-armed bandit setup and only provides worst-case guarantees over all S T and a trade-off ε independent of j.

Remark 4 (SlDB-ED in standard dueling bandits). Even in the dueling bandit setting (without the sleeping component), SlDB-ED and Thm. 6 have advantages compared to the RMED algorithm and analysis of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]. Our regret bound is valid for all number of items K, while the one of Thm. 3 of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF] is only asymptotic when K → ∞. This is due to the fact that the algorithm of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF] depends on a hyper-parameter f (K) which needs to larger than AK, where A is a constant in K and T but which depends on the unknown sub-optimality gaps ∆(i, j). Thus, [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF] chooses f (K) ≈ K 1+ε so that eventually the bound is satisfied when K → ∞. Instead, our algorithm only depends on easily tunable hyper-parameters t 0 and α, whose optimal values are independent of unknown parameters.

Experiments

In this section, we compare the empirical performances of our two proposed algorithms (Alg. 1 and 2). Note that there are no other existing algorithms for our problem (see Sec. 1).

Constructing Preference Matrices (P). We use the following three different utility based Plackett-Luce(θ) preference models (see Sec. 2) that ensures a total-ordering. We now construct three types of problem instances 1. Easy 2. Medium 3. Hard, for any given K, such that items with their respective θ parameters are assigned as follows: 1. Easy: θ(1 :

K/2 ) = 1, θ( K/2 + 1 : K) = 0.5. 2. Medium: θ(1 : K/3 ) = 1, θ( K/3 + 1 : 2K/3 ) = 0.7, θ( 2K/3 + 1 : K) = 0.4. 3. Hard: θ(i) = 1 -(i -1)/K, ∀i ∈ [K]. Note for each σ * = (1 > 2 > . . . K).
In every experiment, we set the learning parameters α = 0.51, δ = 1/T for SlDB-UCB (Alg. 1) and as per Thm. 6 for SlDB-ED (Alg. 2). All results are averaged over 50 runs.

Regret over Varying Preference Matrices. We first plot the cumulative regret of our two algorithms (Alg. 1 and 2) over time on the above three Plackett-Luce datasets for K = 10. We generate availability sequence S T randomly by sampling every item i ∈ [K] independently with probability 0.5. Fig 2 shows that, as their names suggest too, instance-Easy is easiest to learn as the best-vs-worst item preferences are well separated and the diversity of the item preferences across different groups are least. Consequently the algorithms yield slightly more regret on instance-Medium due to higher preference diversity, and the hardest instance being Hard where the learner really needs to differentiate the ranking of every item for any arbitrary set sequences S T . Empirically SlDB-UCB is seen to slightly outperform SlDB-ED, though orderwise they perform competitively.

Regret over Varying Set Availabilities. In these set of experiments, the idea is to understand how the regret improves over completely random subset availabilities as now the learner may not have to distinguish all item preferences as some of the item combinations occurs rarely. We choose K = 10 and to enforce item dependencies we generate each set S t by drawing a random sample from Gaussian(µ, Σ) such that µ i = 0, ∀i ∈ [START_REF] Busa-Fekete | Preference-based rank elicitation using statistical models: The case of mallows[END_REF], and Σ is a fixed 10 × 10 positive definite matrix which controls the set dependencies: Precisely we use two different block diagonal matrices for Low-Correlation and High-Correlation with the following correlations: 1. Low-Correlation: Σ is a separated block diagonal matrix on item partitions {1, 2, 3}, {4, 5, 6}, {7, 8, 9, 10}. 2. High-Correlation: Σ is constructed by merging three all-1 matrices on partitions {1 . . . 5}, {2, . . . 8}, and {6, . . . 10}, however as the resulting matrix is positive semi-definite, so we further take its SVD and reconstruct the matrix back eliminating the negative eigenvalues. At every round we sample a random vector from Gaussian(µ, Σ), and S t is considered to be the set of items whose value exceeds 0.5. Both experiments are run on instance-Hard. Fig. 3 shows, as expected, on Low-Correlation both algorithms converge to σ * relatively faster and at lower regret compared to High-Correlation (as the latter induces higher variability of the available subsets). Final Regret vs Setsize(K). We also compared the (averaged) final regret of the two algorithms over varying item sizes K. We additionally constructed two larger Plackett-Luce (θ) Easy and Hard instances for K = 20 and 40, using similar θ assignments explained before. We set T = 10 000 and use itemwise independent set generation idea, as described for Fig. 2. As expected, Fig. 4 shows the regret of both algorithms scales up with increasing K with effect on SlDB-ED being slightly worse than SlDB-UCB, though the latter generally exhibits a higher variance.

Worst Case Regret vs Time. We run an experiment to analyse the regret of our two algorithms on the worst case problem instances. Towards this we use preference matrices P ∆ of the form: P ∆ (i, j) = 0.5 + ∆, ∀1 ≤ i < j ≤ K, i.e. all items are spaced with equidistant gap ∆ ∈ (0, 0.5]. As before, we choose T = 20, 000 and K = 10, and run the algorithms on above problem instances varying ∆ in the range [10/T, . . . , 0.5] with uniform grid-size of 0.005 (i.e. total 100 values of ∆, each corresponds to a separate problem instance P ∆ with different 'gap-complexity'). At the end we plot the worst case regret of both the algorithms over time, by plotting max ∆ R t (P ∆ ) vs t. We run the experiments over three availability sequences: 1. Independent (as used in Fig. 2), 2. Low-Correlation, and 3. High-Correlation (as used in Fig. 3). As a consequence the resulting plots reflect the worst case (w.r.t. ∆) performances of the algorithms, which seem to be scaling as O(T 2/3 ) for SlDB-ED, as conjectured to be its distribution free upper bound (see discussion after Thm. 6), and with a slightly lower rate for SlDB-UCB. Fig. 5 shows the comparative performances.

Conclusion and Perspective

We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities, which, despite of great practical relevance, was left unaddressed till date. Towards this we adapt two dueling bandit algorithms for the problem and give regret analysis for both. We also derive an instance dependent regret lower bound for our problem setup which shows that our second algorithm is asymptotically near-optimal (up to the problem dependent constants). Finally, we compare both our algorithms empirically where usually the first algorithm is shown to outperform the second, although having a relatively weaker regret.

Future Works. Moving forward, one can address many open questions along this direction, including relaxing the total-ordering assumption on the stochastic preferences assuming more general ranking objective based on borda [START_REF] Urvoy | Generic exploration and k-armed voting bandits[END_REF] or copeland scores [START_REF] Zoghi | Copeland dueling bandits[END_REF], or extending the framework to a general contextual scenario with subsetwise feedback. Another direction worth understanding is to analyze the connection of this problem with other bandit setups, e.g., learning with feedback graphs [START_REF] Noga Alon | Online learning with feedback graphs: Beyond bandits[END_REF][START_REF] Noga Alon | Nonstochastic multi-armed bandits with graph-structured feedback[END_REF] or other side information [START_REF] Mannor | From bandits to experts: On the value of side-observations[END_REF][START_REF] Kocak | Efficient learning by implicit exploration in bandit problems with side observations[END_REF]. It would also be interesting to consider the dueling bandit problem for adversarial preference and stochastic availabilities [START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF][START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF], and also analyzing these class of problems for general subsetwise preferences [START_REF] Wenbo Ren | PAC ranking from pairwise and listwise queries: Lower bounds and upper bounds[END_REF][START_REF] Sui | Advancements in dueling bandits[END_REF][START_REF] Brost | Multi-dueling bandits and their application to online ranker evaluation[END_REF].

Supplementary: Dueling Bandits with Adversarial Sleeping

8 Appendix for Sec. 3

Definition 7 (No-regret algorithm). An algorithm A for Sleeping-Dueling Bandit with Stochastic Preferences and Adversarial Availabilities problem is defined to be a No-regret algorithm, if for each problem instance DB-SPAA(P, S T ) model, the expected number of times A plays any suboptimal duel (i, j)

∈ [K]×[K] is sublinear in T , or more precisely, ∀(i, j) = (i * t , i * t ), E[n ij (T )] = o(T α
), for some α ∈ (0, 1), where recall that we define n ij (t) := Proof. The main argument lies behind the fact that in the worst case the adversary can force the algorithm to learn the preference of every distinct pair (i, j) as the in the 'worst-case' sequence S T knowledge of the already 'learnt' pairwise preferences would not disclose any information on the remaining pairs; e.g. assuming σ * = (1, 2, . . . , K), revealing the available subsets in the following sequence (1, 2), (1, 3), . . . (1, K), (2, 3), (2, 4), . . . (K-1, K) would force the learner to explore (learn the preferences) all K 2 distinct pairs. The remaining proof establishes this formally, towards which we first show a Ω( ln T ∆(1,2) ) regret lower bound for a DB-SPAA instance with just two items (i.e. K = 2) as shown in Lem. 2. The lower bound for any general K can now be derived applying the above bound on independent K 2 subintervals, with the availability sequence (1, 2), (1, 3), . . . (1, K), (2, 3), [START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF][START_REF] Noga Alon | Nonstochastic multi-armed bandits with graph-structured feedback[END_REF]

, . . . (K -1, K).
For the interest of the problem instance construction to prove the lower bound, we would assume ∆(i, i + 1) > 0, ∀i ∈ [K -1] and thus we use ∆(i, i + 1) + = ∆(i, i + 1) for the rest of this proof (as also assumed for Lem. 2). Note that this is without loss of generality since otherwise the regret lower bound in Lem. 2 is trivially 0.

We add the details below for completeness. Let K = K 2 and suppose we divide the time horizon into sub-intervals 1, 2, . . . K each of length T := T /K , where the available subsets are fixed inside every subinterval, and follows the sequence (1, 2), (1, 3), . . . (1, K), (2, 3), [START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF][START_REF] Noga Alon | Nonstochastic multi-armed bandits with graph-structured feedback[END_REF], . . . (K -1, K) across subintervals. Note that with above construction, the regret minimization problem within each sub-interval boils down to the standard stochastic dueling bandit problem over 2 arms.

Further since the preferences of available set S t s are independent across different sub-intervals, applying the lower bound of Lem. 2 individually to every K subintervals the total cumulative regret of A in T rounds can be lower bounded as:

E[R T (A)] = K-1 i=1 K j=i+1 E[R T (A)] ≥ Ω K-1 i=1 K j=i+1 log T ∆(i, j) = Ω K-1 i=1 K j=i+1 log T ∆(i, j)
where the last inequality holds since T ≥ (K ) 2 , which implies log T K ≥ log T -log √ T = 1 /2 log T , and this concludes the proof.

Lemma 2 (Lower Bound of DB-SPAA(P K , S T ) for 2 items). For any No-regret learning algorithm A, there exists a problem instance DB-SPAA(P 2 , S T ) such that the expected regret incurred by A on that can be lower bounded as: E[R T (A)] ≥ ∆ -1 log(T ), ∆ being the 'preference-gap' between the two items (i.e. ∆ = P 12 -1 /2, assuming P 12 > 1 /2 or equivalently ∆ > 0).

Proof. Note that for K = 2, the only non-trivial available set is {1, 2}, therefore we assume S t = {1, 2}, ∀t ∈ [T ]. The proof now simply follows by applying the existing lower bound (Thm. 2) of [START_REF] Yue | The k-armed dueling bandits problem[END_REF] for standard stochastic dueling bandit problem for only 2 arms. 9 Appendix for Sec. 4

Notations. Let us start with defining useful notation for the analysis. We write for any pair

1 ≤ i < j ≤ K M ij = i k=1 4α min ∆(k, i) + , ∆(k, j) + 2 .
We also denote S \i = S \ {i}, i ∈ S, for any S ⊆ [K].

9.1 Complete proof of Thm. 3

Theorem 3. Given any δ > 0 and α ≥ 1, with probability at least 1-δ, the regret incurred by SlDB-UCB (Alg. 1) is upper-bounded as:

R T ≤ 2 K-1 i=1 K j=i+1 M ij log 2C(K, δ)M ij where C(K, δ) := (4α -1)K 2 /((2α -1)δ) 1 2α-1 .
Proof of Thm. 3. The key steps lie in proving the following four lemmas. The first lemma follows along the line of Lem. 1 of RUCB algorithm [START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF]. It shows after C(K, δ) rounds all the pairwise estimates are contained within their respective confidence intervals: Lemma 4. Let α > 0.5 and δ > 0. Then, with probability at least 1 -δ, for any i, j ∈ [K]

p ij (t) -c ij (t) ≤ p ij ≤ u ij (t) := p ij (t) + c ij (t), ∀t ∈ [T ] .
The lemma below is adapted from Proposition 2, [START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF]. It basically states that once the algorithm has explored enough (i.e., more than C(K, δ)) the algorithm will not play a suboptimal pair too many times. Lemma 5. Let α > 0.5. Under the notations and the high-probability event of Lem. 4, for all i, j, k ∈ [K] such that {i, j} = {k, k}, and for any τ ≥ 1

τ t=1 1(i * t = k)1 {x t , y t } = {i, j} ≤ 4α log a i,j (τ ) min ∆(k, i) + , ∆(k, j) + 2 ,
where recall

a ij (τ ) = max C(K, δ), n ij (τ ) .
Given the above results, we are ready to analyze the regret guarantee of SlDB-UCB. For ease on notation we denote X t = {x t , y t }. Let us assume the 'good event' of Lem. 4 holds good for all t ∈ [T ], which is true with probability of at least 1 -δ. Conditioned on that, note that Lem. 5 is satisfied. Based on this we now analyze the regret of Alg. 1:

R T = T t=1 K-1 k=1 1(i * t = k)r t = T t=1 K k=1 K i=k K j=i 1(i * t = k)1 {x t , y t } = {i, j} r t ← because x t ≥ k and y t ≥ k Let τ ij (n) the time step t ∈ [T ]
when the pair (i, j) was updated (i.e. i and j was compared) for the n th time. We now bound the probability of the confidence bound (G ij (t)) getting violated at any round t ∈ [T ] for some duel (i, j) as follows:

P ∃t ∈ [T ], i < j, such that G c ij (t) ≤ i<j P ∃n ≥ 0, |p ij -p ij (τ ij (n))| > αa ij (τ ij (n)) n ij (τ ij (n)) = i<j P ∃n ≤ C(K, δ), |p ij -p ij (n)| > α ln(C(K, δ)) n + P ∃n > C(K, δ), |p ij -p ij (τ ij (n))| > α ln n ij τ ij (n) n ,
where

p ij (t) = wij (t) wij (t)+wij (t)
is the frequentist estimate of p ij at round t (after n = n ij (t) comparisons between arm i and j). To ease the notation, denote F = C(K, δ). Noting n ij (τ ij (n)) = n, and using Hoeffding's inequality, we further get

P ∃t ∈ [T ],i < j, such that G c ij (t) ≤ i<j F n=1 2e -2n α ln F n + ∞ n=F +1 2e -2n α ln n n = n(n -1) 2 2 F n=1 1 F 2α + ∞ n=F +1 2 n 2α ≤ n 2 F 2α-1 + n 2 ∞ F dx x 2α ≤ n 2 F 2α-1 - n 2 (1 -2α)F 2α-1 = (2α)n 2 (2α -1)F 2α-1 = δ.
where the last inequality is because

F = C(K, δ) = 2αn 2 (2α-1)δ 1 2α-1
. This concludes the claim. Lemma 5. Let α > 0.5. Under the notations and the high-probability event of Lem. 4, for all i, j, k ∈ [K] such that {i, j} = {k, k}, and for any τ ≥ 1

τ t=1 1(i * t = k)1 {x t , y t } = {i, j} ≤ 4α log a i,j (τ ) min ∆(k, i) + , ∆(k, j) + 2 ,
where a ij (τ ) = max C(K, δ), n ij (τ ) .

Proof. We assume the confidence bound of Lem. 4 is holds good for all pair (i, j) ∈ [K] 2 , at all round t ∈ [T ], which we know happens with probability at least (1 -δ). Let us define l ij (t) := 1 -u ji (t). Let t ≥ 1. Let i, j, k ∈ [K] such that i * t = k, x t = i, and y t = j and {i, j} = {k, k}. Since i * t = k, this implies both i ≥ k and j ≥ k. Furthermore, we recall that i * t = k is unique by definition, i * t = min{S t }. We consider the following cases.

• Case 1 (i = j > k). Then, x t = y t = i = j. By the arm selection strategy (Step 14. of Algorithm 1)

y t ← arg max m∈Ct u mxt (t)
which implies 1/2 = u jj (t) > u kj (t). But, on the other hand, since k < j, by Lemma 4, u kj (t) ≥ p kj > 1 2 . This causes a contraction and this case is not possible.

• Case 2 (j > i = k). Then, y t = j and x t = i * t = k. We again proceed by contradiction. Assume that n kj (t) > . Then, by definition of c kj (t), it implies

2c kj (t) = 2 α log a kj (t) n ij (t) < ∆(k, j) + ,
10 Appendix for Sec. 5

Technical lemmas

Before proving the regret guarantee of SlDB-ED (Alg. 2) in Thm. 6, we would like to introduce three lemmas which are crucially used towards bounding Alg. 2's regret. Lemma 8 below states that after some exploration, the algorithm estimates well all p ij with p ij (t).

Lemma 8. Let t 0 ≥ 1 and α ≥ 4K. Let ε i > 0 for all i ∈ [K]. For any t ∈ [T ], let us define E t := {n ij (t) > t 0 , ∀i, j ∈ S t , i = j} to be the event when all distinct pairs i, j ∈ [K] is played for at least for t 0 times. Let us also denote the event G(t) := {∀j > i * t , ∆(i * t , j) > ε i , p i * t j (t) > 1 /2}. G c (t) denotes the complement event of G(t). Then SlDB-ED satisfies:

E T t=1 1(E t )1 G c (t) = 2K + K K-1 i=1 K j=i+1|∆(i,j)>εi e -(t0-1)∆(i,j) 2 ∆(i, j) 2 .
Proof. First, we show that with high probability for all t = 1, . . . , T , i where pij (n) denotes the frequentist empirical estimate of P (i, j) after n pairwise comparisons between i and j (i.e., pij (n) = p ij (t) with n ij (t) = n). From Lemma II.1 of [START_REF] Csiszár | The method of types[END_REF], this yields

P(i * t / ∈ C t ) ≤ K j=i * t +1 t n=1 n exp - α log t K ≤ Kt 2 exp - α log t K ≤ K t 2 ,
since α ≥ 4K. Therefore,

T t=1 P(i * t / ∈ C t ) ≤ K T t=1 1 t 2 ≤ 2K . (7)
Then,

E T t=1 1(E t )1 G c (t) ≤ E T t=1 1(E t )1 G c (t) 1(i * t ∈ C t ) + E T t=1 1(i * t / ∈ C t ) (7)
≤ E T t=1 1(E t )1 G c (t) 1(i * t ∈ C t ) + 2K = E T t=1 K i=1 1(E t )1 G c (t) 1(i * t = i)1(i ∈ C t ) + 2K .
Now, since x t is uniformly sampled from C t from Line 11 of Algorithm 2, given that i ∈ C t , the probability that x t = i is at least 1/|C t | ≥ 1/K. Thus,

E 1(E t )1 G c (t) 1(i * t = i)1(i ∈ C t ) ≤ KE 1(E t )1 G c (t) 1(i ∈ C t )1(i * t = x t = i) ,
which yields

E T t=1 1(E t )1 G c (t) ≤ K K i=1 E T t=1 1(E t )1 G c (t) 1(i ∈ C t )1(i * t = x t = i) + 2K ( * ) = K K i=1 j:∆(i,j)>εi E T t=1 1(E t )1(i ∈ C t )1(i * t = i)1 (x t , y t ) = (i, j) 1( p ij (t) < 1/2) + 2K ≤ K K i=1 j:∆(i,j)>εi E T t=1 1(E t )1 (x t , y t ) = (i, j) 1( p ij (t) < 1/2) + 2K (8)
where

( * ) is because G c (t) := ∃j > i, ∆(i, j) > ε i * t , p ij (t) < 1/2 when i = i * t ,
and since y t is chosen such that p iyt (t) < 1/2 (see Line 12. of Alg. 2). Recall that E t ensures that (i, j) was pulled at least t 0 times during the exploration phase. Recalling that pij (n) equals p ij (t) where t is such that n = n ij (t), we have

T t=1 1(E t )1 (x t , y t ) = (i, j) 1( p ij (t) < 1/2) ≤ ∞ n=t0 1(p ij (n) < 1/2) .
Therefore, plugging the latter inequality into the previous upper-bound [START_REF] Brost | Multi-dueling bandits and their application to online ranker evaluation[END_REF], it yields

E T t=1 1(E t )1 G c (t) ≤ K K i=1 j:∆(i,j)>εi ∞ n=t0 P pij (n) < 1/2 + 2K (a) = K K i=1 j:∆(i,j)>εi ∞ n=t0 P pij (n) < P (i, j) -∆(i, j) + 2K (b) ≤ K K i=1 j:∆(i,j)>εi ∞ n=t0 exp -n∆(i, j) 2 + 2K ≤ K K i=1 j:∆(i,j)>εi e -(t0-1)∆(i,j) 2 e ∆(i,j) 2 -1 + 2K ≤ K K i=1 j:∆(i,j)>εi e -(t0-1)∆(i,j) 2 ∆(i, j) 2 + 2K
where (a) follows by definition ∆(i, j) := P(i, j) -1/2 and (b) is by Hoeffding's inequality.

The high-level idea of Lemma 9 below is that for any pair 1 ≤ i < j ≤ K, j will not be played too much more than M ij (δ) times together with items k ≤ i. In other words, after sufficiently enough rounds j is detected as worse than all items k < i.

Lemma 9. Let 1 ≤ i < j ≤ K. Then, SlDB-ED (Alg. 2) satisfies: E T t=1 1(G(t)) i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ) ≤ 32 δ 2 ∆(i, j) 2 ,
where G(t) is as defined in Lem. 8 and N ij (t) := i k=1 n kj (t) is the number of times j was compared with some arm in 1, . . . , i and M ij (δ) := (α + δ)(log T )/kl(p ji , 0.5).

Proof. Let 1 ≤ i ≤ K -1. We start by recalling some useful notations:

B i (t) := j | j ∈ [K], p i,j (t) ≤ 1 /2 , I i (t) := j∈ Bi(t) n ij (t) kl( p ij (t), 0.5) ,
where i * (t) := arg min i∈[K] I i (t), and for simplicity we here denote I i * t (t) = I * (t) := min i∈[K] I i (t). We also denote that event J i (t) := {I i (t) -I * (t) ≤ α log t}. Then for any fixed j > i, we have

S T (i, j) := E T t=1 1(G(t)) i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ) = E T t=1 1(G(t)) i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ) 1(J j (t) ← as x t = j implies 1(J j (t)) = 1 = E T t=1 1(G(t)) i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ), J j (t)
Substituting J i (t) := {I i (t) -I * (t) ≤ α log t}, and using that G(t) implies I * (t) = 0, we get

S T (i, j) ≤ E T t=1 i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ), I j (t) ≤ α log t ≤ E T t=1 i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ), k∈ Bj (t) n jk (t) kl( p jk (t), 0.5) ≤ α log T ≤ E T t=1 i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ), i k=1 n kj (t) kl + ( p jk (t), 0.5) ≤ α log T
where kl + (p, q) := kl(p, q)1(p < q). But, from convexity of kl + (•, 0.5) together with Jensen's inequality

i k=1 n kj (t) kl + ( p jk (t), 0.5) ≥ N ij (t) kl + 1 N ij (t) i k=1 n kj (t) p jk (t), 0.5 . Therefore, denoting p1:ij (N ij (t)) := 1 N ij (t) i k=1 n kj (t) p jk (t) = 1 N ij (t) i k=1 w ki (t)
the frequentist empirical estimate obtained after N ij (t) comparisons of j with any item better than i, we have

S T (i, j) ≤ E T t=1 i k=1 1(x t = j, y t = k)1 N ij (t) > M ij (δ), N ij (t) kl + p1:ij (N ij (t)), 0.5 ≤ α log T But, for each n > M ij (δ), N ij (t) = n is only possible for one of the above rounds since (x t , y t ) = (i, k) with k ≤ i, which increases N ij (t) by one. Thus, S T (i, j) ≤ E T n=Mij (δ) 1 n kl + p1:ij (n), 0.5 ≤ α log T ≤ E T n= Mij (δ) 1 M ij (δ) kl + (p 1:ij (n), 0.5) ≤ α log T ≤ E T n= Mij (δ) 1 kl + (p 1:ij (n), 0.5) ≤ kl(p ji , 0.5) 1 + δ
Now, let µ i ∈ (p ji , 0.5) such that kl(µ i , 0.5) = kl(p ji , 0.5)/(1 + δ). By monotonicity of kl + (•, 0.5),

S T (i, j) = T n= Mij (δ) P kl + (p 1:ij (n), 0.5) ≤ kl + (µ i , 0.5) ≤ T n= Mij (δ) P p1:ij (n) ≤ µ i ≤ T n= Mij (δ) P pij (n) ≤ µ i ≤ T n= Mij (δ) e -kl(µi,pij )n ,
where the last inequality is by Chernoff's inequality (e.g. see Fact 8 of [START_REF] Komiyama | Regret lower bound and optimal algorithm in dueling bandit problem[END_REF]). Then,

S T (i, j) ≤ ∞ n=1 e -kl(µi,pij )n ≤ 1 kl(µ i , p ij ) .
The proof is concluded using Pinksker's inequality followed by 4∆(i, j)-Lipschitzness of kl(•, 0.5) over (0.5 -∆(i, j), 0.5):

kl(µ i , p ij ) ≥ 2(µ i -p ij ) 2 ← Pinsker's inequality ≥ 2 16∆(i, j) 2 kl(µ i , 0.5) -kl(p ij , 0.5) 2 ← Lipschitzness = 2 kl(p ij , 0.5) 2 δ 2 16∆(i, j) 2 (1 + δ) 2 ← def of µ i ≥ kl(p ij , 0.5) 2 δ 2 32∆(i, j) 2 ← δ ∈ (0, 1) ≥ ∆(i, j) 2 δ 2 32 . ← Pinsker's inequality Therefore, S T (i, j) ≤ 32 ∆(i, j) 2 δ 2 . Lemma 10. For any ε 2 , . . . , ε K ≥ 0, 1≤i<j≤K|∆(i,j)>εj ∆(i, j) -∆(i + 1, j) ∆(i, j) 2 ≤ n j=2 2 max ε j , ∆(j -1, j) .
Proof. The proof is adapted from similar techniques used for proving Lem. 5 of [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF]. First note that 1≤i<j≤n|∆(i,j)>εj ∆(i, j) -∆(i + 1, j) ∆(i, j Proof. We analyse the expected regret SlDB-ED (Alg 2) for some fixed sequence S T . Recall that t 0 is the budget spent on exploration of each pair (i, j) and the notation E(t) := n ij (t) > t 0 , ∀i, j ∈ S t , i = j , to be the event when all distinct pairs in S t have been explored t 0 times and G(t) := ∀j > i * t , ∆(i * t , j) > ε i , p i * t j (t) > 1 /2 the event when the probabilities p ij have been well estimated by the algorithm. Then, from Lemma 8, we have

E R T = E T t=1 r t = E T t=1 1(E c (t))r t + T t=1 1(E(t))1(G c (t))r t + T t=T0+1 1(E(t))1(G(t))r t ≤ K 2 t 0 + 2K + K K-1 i=1 K j=i+1|∆(i,j)>εj e -(t0-1)∆(i,j) 2 ∆(i, j) 2 + E T t=T0+1 1(E(t))1(G(t))r t E T . (9)
We now upper-bound the third term of [START_REF] Busa-Fekete | A survey of preference-based online learning with bandit algorithms[END_REF]. Remark that under G(t) the algorithm chooses y t = i * t . Therefore,

1 x t = j, y t = k 1 N ij (t) ≤ M ij (δ) + 1 N ij (t) > M ij (δ) ≤ M ij (δ) + T t=1 1(G(t)) i k=1 1 x t = j, y t = k 1 N ij (t) > M ij (δ)
≤ M ij (δ) + 32 δ 2 ∆(i, j) 2 ← Lemma 9 = (α + δ) log T kl(p ji , 0.5) + 32 δ 2 ∆(i, j) 2 ≤ 2(α + δ) log T + 32 δ 2 1 ∆(i, j) 2 , where the last inequality comes from Pinksker's inequality. This entails 1≤i<j≤K:∆(i,j)>εj Ñij (T ) ∆(i, j) -∆(i + 1, j) 2

≤ (α + δ) log T + 16 δ 2
1≤i<j≤K:∆(i,j)>εj ∆(i, j) -∆(i + 1, j)

∆(i, j) 2 ≤ 2 K j=2
(α + δ) log T + 16δ -2 max ε j , ∆(j -1, j) .

Combining this inequality with (9), [START_REF] Busa-Fekete | Preference-based rank elicitation using statistical models: The case of mallows[END_REF], and (11) and choosing t 0 = 1 and α = 4K concludes

E R T ] ≤ K 2 t 0 + 2K + K K-1 i=1 K j=i+1|∆(i,j)>εj
e -(t0-1)∆(i,j) 2 ∆(i, j) (4K + δ) log T + 16δ -2 max ε j , ∆(j -1, j) .

Proof. Recall that the proof was done for any ε 2 , . . . , ε K ≥ 0 that are independent of the algorithm. In particular, choosing ε 2 , . . . , ε K = ε entails that for any ε > 0

E R T K 2 + εT + 1≤i<j≤K|∆(i,j)>ε K ∆(i, j) 2 + K j=2 K log T max ε, ∆(j -1, j)
which yields making ε → 0 the distribution-dependent asymptotic upper-bound

E R T ] ≤ O K log(T ) K j=2 1 ∆(j -1, j) > 0 ∆(j -1, j)
as T → ∞ and for any fix ε ≥ 0 and choosing δ = 1. Furthermore, optimizing

ε 1 = ε 2 = • • • = ε K = ε = 2 1/3 KT -1/3 yields the distribution-free upper-bound E R T ≤ K(K + 2) + K 3 ε 2 + T ε 2 + (8K + 1)K log T + 16K ε ≤ 2KT 2/3 + O(K 2 + KT 1/3 log T ) .

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Regret (R t ) vs time (t) over three preference instances (P)

Figure 5 :

 5 Figure 5: "Worst Case Regret" (max ∆ R t (P ∆ )) vs time (t) over three availability sequences S T

t τ =1 1

 1 {x t , y t } = {i, j} denotes the number of times the pair (i, j) is played by A in T rounds. (E[•] denotes expectation under the randomization of A and the DB-SPAA(P, S T ) model.) 8.1 Proof of Thm. 1

  4α ln a kj (t) ∆(k,j) 2 +

6 Theorem 6 (

 66 K]\[i]|∆(i,j)>εj ∆(i, j) -∆(i + 1, j) ∆(i, j) 2Let us fix any arm i ∈ [K -1], and denote by ∇ i,j := ∆(i, j) -∆(i + 1, j). Then we notej∈[K]\[i]|∆(i,j)>εj ∆(i, j) -∆(i + 1, j) ∆(i, j) 2 = j∈[K]\[i]|∆(i,j)>εj ∇ i,j ∞ 0 1(∆(i, j) -2 ≥ x)dx10.2 Proof of Theorem Expected regret analysis SlDB-ED). Let t 0 = 1 and α = 4K. Then as T → ∞, the expected regret incurred by SlDB-ED (Alg. 2) can be upper bounded as: For all ε 2 , . . . , ε K ≥ 0E R T K 2 + 1≤i<j≤K K1 {∆(i,j)>εj } ∆(i, j) 2 + n ij (T ) min{ε j , ∆(i, j)} + K j=2 K log T max ε j , ∆(j -1, j) + ≤ O min K j=2 K log T ∆(j -1, j) +, KT 2/3 .

2 =

 2 t = j, y t = i)r t t = j, y t = i) ∆(i, j) 2 ← because G(t) implies y t = i * t = j, y t = i) ∆(i, j) the notations n ij (T ) := T t=1 1 {x t , y t } = {i, j} and defining Ñij (T ) := i k=1 t s=1 1(G(s))1(x t = k, y t = j) ≤ N ij (T ) := i k=1n kj (T ) , t))1(x t = j, y t = i) need to upper-bound Ñij (T ). We have, Ñi,j (T ) :=

  Select any x t from C t uniformly at random xt (t) or B xt (t) = ∅ : set y t ← i * t , else: y t ← arg max i∈St\{xt} p ixt (t)

		log t}	Potential good arms
	11:
	12: t ∈ B 13: if i * end if
	14:	Play (x t , y t ) Receive preference feedback o t
	15: end for
	Main ideas.

  * t ∈ C t , i * t belongs to the set of potential winners. Let t ≥ 1. By definition of C t , we have

	P(i * t / ∈ C t ) ≤ P			n i * t j (t) kl( p i * t j (t), 0.5) ≥ α log t
		j∈ B i * t	(t)
	≤ P ∃j > i * t	s.t. n i * t j (t) kl( p i * t j (t), 0.5) ≥	α log t K
	≤	K j=i * t +1	t n=1	P kl(p i * t j (n), 0.5) ≥	α log t nK	,

Now, fix 1 ≤ i < j ≤ K and let us upper-bound n ij (T ) the number of times such a pair is played. Summing the upper-bound of Lemma 5 over k ≤ i, we get

Therefore, since C(K, δ) ≥ 1,

which implies

Substituting into Inequality (3) entails

which concludes the proof.

Technical lemmas for Thm. 3

Lemma 4. Let α > 0.5 and δ > 0. Then, with probability at least 1 -δ, for any i, j ∈ [K]

Proof. The proof of this lemma is adapted from a similar result (Lemma 1) of [START_REF] Zoghi | Relative upper confidence bound for the k-armed dueling bandit problem[END_REF]. Suppose G ij (t) denotes the event that at time t ∈ [T ] and item-pair i, j

Note that for any such that pair (i, i), G ii (t) always holds true for any t ∈ [T ] and i ∈

We can thus assume i = j. Moreover, for any t and i, j,

Thus we will restrict our focus only to pairs i < j for the rest of the proof. Hence, to prove the lemma it suffices to show

which we do now. Recall from the definition of c ij (t) that G ij (t) can be rewritten as:

which by Lem. 4 entails

Again since our arm selection strategy enforces y t ← arg max i∈Ct u ixt (t), clearly 1 2 = u kk (t) > u jk (t), so that j can not be selected as y t . Therefore, recalling that k = i,

• Case 3 (i > j = k). Then, x t = i and y t = i * t = k. This can be proved similarly as the previous case. Assuming

But by Lemma 4, for all m > k, u km (t)

By

Step 12 of Algorithm 1, this implies that i / ∈ C t and thus x t = i as x t is selected from C t , which causes a contradiction. Therefore, recalling j = k,

But, on the other hand, x t = i implies u ij (t) > 1 /2, and y t = j implies u ji (t) > u jk (t) > p jk , and then l ij (t) = 1 -u ji (t) < 1 -p jk . So we have u ij (t) -l ij (t) > 1 /2 -p ik = ∆(k, i) + which gives a contradiction. Thus,

Note that the case x t = j, y t = i, and i * t = k is symmetric with the above cases and can be considered similarly. Denote by τ the last time before τ ≥ 1 such that a pair {i, j} = {k, k} is pulled when k

Then,

But, at time τ , the suboptimal pair {i, j} got pulled, thus one of the above four cases is true, which implies from Inequalities (4), [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF], and (6) that

Substituting into the previous inequality concludes the proof.

Further summing over all i ∈ [K -1], we get

where i ε (j) := arg min{i|i ≤ j, ∆(i, j) ≤ ε} (with the convention that the sum is empty if the arg min is empty) and because ε j < ∆(i, j) ≤ y is equivalent to i y (ε) ≤ i ≤ i εj -1. Using telescoping summation over i, we further get:

∞ εj y -3 ∆(i y (j), j) -∆(i εj (j), j) dy

∞ εj y -3 ∆(i y (j), j)dy ← since ∆(i εj (j), j) > 0 Then, since ∆(i y (j), j) = 0 if y < ∆(j -1, j), we have


Nicolas Agier

Aubin Fleiss

Stéphane Delmas

Gilles Fischer
email: gilles.fischer@sorbonne-universite.fr

A Versatile Protocol to Generate Translocations in Yeast Genomes using CRISPR/Cas9

Keywords: CRISPR, Cas9, Yeast, Reciprocal Translocation, Segmental duplication, Chromosome Rearrangement, Structural Variation, Balanced Rearrangement, Genome Shuffling

Genomic engineering methods represent powerful tools to examine chromosomal modifications and to subsequently study their impacts on cellular phenotypes. However, quantifying the fitness impact of translocations, independently from base substitutions or the insertion of genetic markers remains a challenge. Here we report a rapid and straightforward protocol for engineering either targeted reciprocal translocations at the base pair level of resolution between 2 chromosomes or multiple simultaneous rearrangements in the yeast genome, without inserting any marker sequence in the chromosomes. Our CRISPR/Cas9based method consists of inducing either (i) 2 double-strand breaks (DSBs) in 2 different chromosomes with 2 distinct guide RNAs (gRNAs) while providing specifically-designed homologous donor DNA forcing the trans-repair of chromosomal extremities to generate a targeted reciprocal translocation or (ii) multiple DSBs with a single gRNA targeting dispersed repeated sequences and leaving endogenous uncut copies of the repeat to be used as donor DNA, thereby generating multiple translocations, often associated with large segmental duplications (1).

Introduction

The ability to engineer targeted chromosomal rearrangements is instrumental for quantifying the fitness contribution of balanced chromosomal rearrangements independently from other polymorphisms such as base substitutions or the insertion of selection markers. The classical approach used to engineer targeted rearrangements in yeast is to induce targeted DSBs in chromosomes that promote either the trans-repair of the DNA ends via homology directed repair or by non-homologous end joining (2-4). The induction of targeted DSBs has been achieved to date by a variety of technologies utilizing the HO and I-SceI endonucleases (5-10), which first requires cloning the enzyme recognition sites at the loci of interest, the Cre/Lox recombination method (11-14), which, combined with synthetic designer chromosomes can generate extensive genomic rearrangements (15-18), the use of a temperature dependent endonuclease that allows large-scale genomics rearrangements by inducing multiple DSBs (19), as well as designer proteins such as zinc finger nucleases and transcription activator-like effector nucleases (20-23).

These methods, that often rely on the use of genetic markers, are either difficult to implement or work with varying levels of efficiency. The development of the CRISPR/Cas9 technology (24), consisting of a short RNA that guides the Cas9 endonuclease to generate a DSB at the targeted genomic site, revolutionized the field of genome engineering in a wide variety of species (25). In yeast, a CRISPR/Cas9-induced DSB is efficiently repaired by homologous recombination by co-transforming the cells with a linear donor DNA that is homologous to both sides of the DSB extremities (26). A CRISPR-based approach has been used to engineer translocations in mammalian cells by introducing two DSBs in two different chromosomes and repairing them in trans using chimerical donor DNA templates carrying a selectable marker. This marker is subsequently lost by Cre/Lox recombination, leaving a single loxP scar in the chromosomes [START_REF] Vanoli | CRISPR-Cas9-guided oncogenic chromosomal translocations with conditional fusion protein expression in human mesenchymal cells[END_REF].

Here, we describe a CRISPR/Cas9-based protocol relying on the generation of two or more DSBs in the yeast genome and the trans-repair of DNA ends by homologous recombination using either designed or endogenous donor DNAs (1). This protocol is easy to implement and allows engineering of targeted or random translocations with high efficiency. This method does not rely on the use of genomic markers and induces rearrangements with base pair precision leaving no scar at the breakpoints. The entire workflow (Fig. 1) can be completed in approximately two weeks. The protocol presented within will guide the reader through the selection of suitable CRISPR target sites, the cloning of a single or a pair of gRNA sequences into a plasmid containing the Cas9 gene (Fig. 2), the design of linear donor DNA, the transformation of yeast cells and finally the validation of the transformants containing the engineered rearrangements by colony PCR and Pulse Field Gel Electrophoresis (PFGE). Our method is based on the pAEF5 shuttle vector that replicates in Escherichia coli and yeast (Fig. 3) and encodes the dominant drug marker HygR, as well as the Cas9 endonuclease and cloning sites for gRNAs, and therefore is applicable to any Saccharomyces strain, including wild-type isolates for which no auxotrophic mutant is available.

Materials

All solutions and media are prepared with double-distilled water. For PCR and cloning, use molecular biology grade water.

Bacterial Media

1. Lysogeny Broth (LB) growth medium: 10 % tryptone (w/v), 5 % yeast extract (w/v), 10% NaCl (w/v). For LB agar growth medium add 2 % bacto-agar (w/v). Resuspend the powders in 1 litre of double-distilled water, bring to a boil for 1 minute with frequent agitation then autoclave for 15 minutes at 121°C. For solid media, cool down to 55°C and pour 20 mL in Petri dishes.

2. LB ampicillin selective medium: Prepare LB growth medium or LB agar growth medium depending on the requirement for the experiment. After autoclaving, cool down the medium to 55°C and add ampicillin to a final concentration of 100 µg/mL. For solid media, pour 20 mL in Petri dishes.

Yeast Media

1. Yeast Peptone Dextrose (YPD) growth medium: 1 % yeast extract (w/v), 2 % peptone (w/v), 2 % dextrose (w/v). For YPD agar growth medium add 2 % bacto-agar (w/v).

Resuspend the powders in 1L of double-distilled water, bring to a boil for 1 minute with frequent agitation then autoclave for 15 minutes at 121°C. For solid medium cool down to 55°C and pour 20 mL in Petri dishes.

2. YPD agar hygromycin B selective media: Prepare YPD agar growth medium. After autoclaving, cool down the media to 55°C, add hygromycin B to a final concentration of 200 µg/mL and pour 20 mL in Petri dishes.

Bacterial and Yeast Growth Culture

1. Grow bacteria in a microbiological incubator at 37°C with shaking at 220 rpm for liquid cultures and without agitation for cells grown on solid medium.

2. Grow yeast in a microbiological incubator at 30°C with shaking at 150 rpm for liquid cultures and without agitation for cells grown on solid medium.

Microbiological Manipulation

1. Sterile 50 mL plastic tube.

Sterile plastic loops (1 µL).

Sterile glass beads (3 mm).

4. Sterile toothpicks. 5. Electric Bunzen burner.

6. 90 mm Petri dishes.

Agarose Gel Electrophoresis

1. Agarose gel electrophoresis equipment.

2. Electrophoresis buffer: tris borate EDTA (TBE) 0.5x. For 1 litre 5.4 g of tris base, 2.75 g of boric acid and 2 mL of 0.5 M EDTA pH 8.0.

3. Agarose gel: 1% agarose and TBE 0.5x buffer. Ethidium bromide is used at the concentration recommended by the provider.

PCR Amplification and Purification

1. Thermo-cycler. 5. PCR and gel purification kit.

For colony PCR:

-Heat block.

-1.5 mL tubes filled with 50 µL of water.

-Sterile toothpicks.

-Ice.

Cloning the gRNA Sequences in pAEF5

1. SapI enzyme and associated buffer.

Bacterial Transformation

1. DH5α competent cells.

Ice.

3. Heat block.

4. Incubator at 37°C with agitation at 220 rpm.

5. Incubator at 37°C. [START_REF] Fasullo | Direction of chromosome rearrangements in Saccharomyces cerevisiae by use of his3 recombinational substrates[END_REF]. LB growth media.

7. LB ampicillin selective media. 6. Solution II: 450 mM EDTA pH9, 10 mM tris-HCl pH8, 7.5 % ß-mercaptoethanol.

Yeast Transformations

7. Solution III: 450 mM EDTA pH9, 10 mM tris-HCl pH8, 1 % N-lauryl sarcosyl 10, 1 mg/mL proteinase K. 8. 1.5 mL tubes.

Strain Storage

1. Cryotubes.

2. Yeast storage media: 1% yeast extract (w/v), 2% peptone (w/v), 2% dextrose (w/v), 20% glycerol (v/v). Prepare 1 litre of YPD broth and a sterile solution of 80 % glycerol. Mix 3:1 v/v the YPD broth and the glycerol solution.

3. 10 µL sterile loops.

Methods

In the following method the DNA sequence coding for the gRNA will be referred to as the gRNA sequence.

Design of the gRNAs Sequence

Targeted Translocations

The two gRNA target sequences have to be chosen as close as possible to the desired breakpoints. The website CRISPOR (http://crispor.tefor.net/) can be used for this purpose (28).

1. For each target, provide 2000 bp of the sequence of the chromosomal region centered around the desired cut site.

Choose the provided version of the genome of Saccharomyces cerevisiae.

3. Choose the NGG protospacer adjacent motif (PAM) associated with the Streptococcus pyogenes Cas9 protein used here (option Sp Cas9, SpCas9-HF1, eSpCas9 1.1).

4. Click submit.

5.

Choose the closest and most specific guide sequence possible next to the desired breakpoint.

Multiple Translocations

The single gRNA must be chosen considering the desired number and location of target sequences (and potential donor DNAs, see step 3.5, Note 1) in the genome.

1. Identify on both strands in the genome all target sequences of 20 bp followed by the NGG PAM.

2. Select among these sequences the gRNA sequence with the desired number of targets in the genome.

Construction of the gRNA Sequences

Targeted Translocations

Two different gRNA sequences targeting two distinct chromosomes must be cloned in pAEF5 (Addgene ID 136305). There are two options available to achieve this task. The 5' extremity of the two oligonucleotides is composed of a SapI restriction site (underlined in the sequence above), followed by the gRNA sequence of interest (designed as 20 Ns above). The 20 bp at the 3' extremity of the forward primer is complementary to the structural part of the first gRNA. The 20 bp at the 3' extremity of the reverse primer is complementary to the end of the second TEF promoter (Fig. 2). f. The amplification is verified by electrophoresis on a 1% agarose gel using a standard protocol.

e. The PCR product is purified by gel extraction using a standard protocol.

Multiple Translocations

A single gRNA sequence targeting multiple loci in the genome must be cloned in pAEF5.

Two 23 bp oligonucleotides that are complementary within the 20 bp corresponding to the target sequence identified by CRISPOR need to be ordered and annealed. One oligonucleotide starts with ATC at its 5' extremity, followed by the 20 bp of the target sequence (symbolised as 20Ns in the sequence below). The other oligonucleotide starts with AAC at its 5' extremity, followed by the reverse complement of the target sequence (20Ns in the sequence k. The remaining volume of the culture will be used for plasmid extraction using a standard alkaline lysis protocol in order to validate the plasmid (see 3.4).

Validation of the Clones

Correct cloning is verified by double enzymatic restriction of the plasmid DNA: a. Mix 1 µg of plasmid with SapI (5U) and SpeI (10U) with the appropriate buffer. b. Incubate 1 hour at 37°C. c. Analyse the size of the restriction fragments using electrophoresis in a 1% agarose gel (Note 4).

Design of the Donor DNA Fragments

Targeted Translocations

The two donor DNAs required for homologous repair upon Cas9 cutting are 90 bp long, comprising 45 bp identical to the centromere-proximal region flanking the cut site in one chromosome and 45bp identical to the telomere-proximal region flanking the cut site on the other chromosome (Fig. 4). e. The DNA fragment is ready for yeast transformation, go to step 3.6

Multiple Translocations:

The identification of the number and location of donor DNAs is achieved by an in-house script that performs the following steps: a. For each occurrence of a repeated gRNA target sequence in the genome, select an 80 bp segment centered on the cut site. b. Use as query all possible sequences of 50 bp comprised within this 80 bp segment to search the genome for homologous regions with at least 90% identity and a mutated PAM and/or at least one mutation in the 20 bp gRNA sequence. c. Assemble a non-redundant set of donor DNAs gathering all homologous regions detected for all occurrences of the repeated gRNA target sequence.

Yeast Transformation

Targeted Translocation

3 transformations are performed: i) pAEF5 (500 ng per transformation) to control for transformation efficiency.

ii) pAEF5 with the cloned gRNAs (500 ng per transformation) to control for cutting efficiency.

iii) pAEF5 with the cloned gRNAs (500 ng per transformation) and 10 µL of a 90 µM donor DNA solution to obtain the desired rearrangements.

Multiple Translocations

Only 2 transformations are performed: i) pAEF5 (500 ng per transformation) to control for transformation efficiency.

ii) pAEF5 with the cloned gRNA (500 ng per transformation) to obtain the desired rearrangements.

Lithium Acetate Yeast Transformation

All yeast transformations are performed following the standard protocol described in Gietz and Woods 2002 (29) with the following adaptations:

1. Prior to transformation, 10 8 cells are washed twice in 1 mL of water and twice in LiAC/TE solution.

2. The heat-shock is performed at 42°C for 25 minutes.

3. Centrifugations are performed at 8000 g for 2 minutes, at 4°C. e. Store at -80°C.

Validation of the Transformants

Karyotyping of the strains can be realized by PFGE for both targeted and multiple translocations.

Saccharomyces cerevisiae karyotyping is done according to the standard method (30) with the following adaptation:

1. Cells are thawed on YPD agar.

2. 10 mL of YPD in a 50 mL plastic tube are inoculated with a 1µL loop of cells. This culture will be used the next day to prepare the plugs.

3. Agarose plugs are prepared using SeaPlaque GTG low melting temperature agarose.

4. PFGE is performed using a CHEF DRIII Biorad system.

5. An agarose gel is prepared using 1% Seakem GTC agarose dissolved in 0.5 x TBE buffer.

6. The running program is the following: a. 6 V/cm for 10 hours with a switching time of 60 seconds b. 6 V/cm for 17 hr with switching time of 90 seconds.

c. The included angle was 120° for the whole duration of the run.

7. After the migration the agarose gel is stained for 30 minutes in ethidium bromide.

8. The gel is washed twice in double-distilled water.

9. A picture is taken with an imager.

For targeted translocations, an additional validation can be obtained by amplifying the junction of the rearranged chromosomes by colony PCR.

1. Design oligonucleotides to amplify 300 bp surrounding the junctions of the expected chromosomal rearrangements.

2. Thaw candidate strains on YPD agar.

3. Incubate at 30°C overnight.

4. Pick cells with a toothpick.

5. Cells are resuspended in a 1.5 mL tube containing 50 µL of sterile distilled water.

6. The tube is then incubated at 95°C for 5 minutes.

7. The tube is transferred directly onto ice for 5 minutes.

8. Realize a standard PCR using 5 µL of the boiled cells as template (note 6).

Loss of the Plasmid

1. Thaw the strain from -80°C on a YPD agar plate and incubate overnight at 30°C.

2. Inoculate with a 1 µL loop full of cells, 20 mL of YPD broth in a 50 mL plastic tube.

3. Incubate the cells for 24 hours at 30°C with shaking at 150 rpm.

4.a Micro-manipulate 10 cells on a YPD agar plate using a standard yeast cells micromanipulation protocol.

4.b If there is no micromanipulator available, plate 100 cells from a dilution of the overnight culture on YPD agar plate.

5. Incubate the plate for 3 days at 30°C.

6. Test the clone for the loss of the plasmid by patching them on a YPD agar plate and on a YPD agar hygromycin B selective plate (Note 7).

7. For the clones that have lost the plasmid, proceed to step 3.9.

Storage of the Clones

1. From a patch of cells grown on YPD agar, pick cells with a 10 µL loop and resuspend them in the yeast storage medium in a cryotube.

2. Vortex for 20 seconds.

3. Store at -80°C.

NOTES

1. We have generated the full catalogue of the repeated gRNA sequences and their corresponding donor DNAs. This catalogue was generated using the R64.2.1 version of the S288c Saccharomyces cerevisiae genome (https://www.yeastgenome.org/) and is available on request.

2. 0

 0 .2 mL PCR tubes.

3. 10 mM dNTP mix. 4 .

 4 High fidelity polymerase and associated buffer.

2 .

 2 SpeI enzyme and associated buffer.

3 .

 3 T4 DNA ligase and associated buffer.

4 .

 4 1X annealing buffer: 50 mM potassium acetate, 20 mM tris-acetate, 10 mM magnesium acetate, 1 mM DTT, pH 7.9 at 25°C. 5. 0.2 mL tubes. 6. 1.5 mL tubes.

7 .

 7 Heat block.

1 . 1 .

 11 TE solution (10X): 0.1 M tris-HCl pH 7.5, 0.01 M EDTA, autoclave. 2. LiAc solution (10X) : 1 M LiAc pH 7.5, autoclave. 3. PEG solution: PEG 4000 48% w/v (e.g. 4.8 g in 10 mL of water), filtered (0.22 µm filter). 4. LiAC/TE solution: TE solution 10% v/v, LiAc solution 10% v/v. 5. LiAc/TE/PEG solution: PEG solution 80% v/v, TE solution 10% v/v, LiAc solution 10% vCHEF-DRIII (BioRad) system. 2. SeaPlaque GTG low melting temperature agarose. 3. SeaKem GTG agarose. 4. Tris borate EDTA 0.5x. For 1 liter 5.4 g of tris base, 2.75 g of boric acid and 2 mL of 0.5 M EDTA pH 8.0. 5. Solution I: SCE 1M [sorbitol 1M, 10 mM EDTA pH9, 100 mM sodium citrateadjust to pH 8.5 with citric acid 40 %], 5 % ß-mercaptoethanol, 200 U zymolyase 100T.

1 .

 1 The first option consists of ordering a 464 bp synthetic double stranded DNA fragment containing both gRNA sequences (Note 2): a. Quantity: 300 ng. b. Delivery format: lyophilized. Resuspend the synthetic DNA fragment: a. spin down the lyophilised fragments for 10 seconds with a centrifuge. b. Add water to reach a final concentration of 30 ng/µL. c. Incubate 1 hour at room temperature. d. Vortex 5 seconds and spin down 10 seconds. e. The DNA fragment is ready for cloning, go to step 3.3.2. 2. The second option is to amplify a 430 bp DNA sequence by PCR using as template the pAEF5 plasmid into which two gRNA sequences were already cloned, called pAEF6 (available on Addgene repository under the ID 136303) and as primers two oligonucleotides designed as follows (Fig. 2): Forward oligonucleotide sequence: 5' atgcgctcttccatcNNNNNNNNNNNNNNNNNNNNgttttagagctagaaatagc 3' Reverse oligonucleotide sequence: 5' atgcgctcttcaaacNNNNNNNNNNNNNNNNNNNNgatcatttatctttcactgc 3'

  PCR recommendations: a. Use a high-fidelity DNA polymerase following the provider guidelines. b. Use as template 20 ng of the pAEF6 plasmid. c. Annealing temperature for the PCR is 54°C. d. The elongation time should be set to amplify 500 bp according to manufacturer instructions. e. Perform 30 cycles of amplification.

3 . 3

 33 below). The two triplets of bases ATC and AAC are complementary to the single-strand overhangs generated by the SapI digestion of the pAEF5 plasmid, allowing to clone the double-stranded DNA target sequence in the correct orientation: Forward oligonucleotide sequence: 5' atcNNNNNNNNNNNNNNNNNNNN 3' Reverse oligonucleotide sequence: 5' aacNNNNNNNNNNNNNNNNNNNN 3' Order the two oligonucleotides with the following characteristics: a. Purification: salt free. b. Synthesis scale: 0.01 µmol. c. Delivery format: lyophilized. d. Quality control: MALDI. Anneal the oligonucleotides: a. Resuspend oligonucleotides to a final concentration of 100 µM in water. b. Prepare an equimolar mix of both oligonucleotides in the annealing buffer. c. Vortex the mix. d. Incubate at 95°C for 5 minutes and let cool down slowly to room temperature. e. The DNA fragment is ready for cloning, go to step 3.3. Cloning gRNA Sequences 1. Prepare the pAEF5 plasmid for cloning (Note 3): a. mix 1 µg of the plasmid with 5 U of SapI in the appropriate buffer. b. Incubate for 1 hour at 37°C. c. Purify the digested plasmid by running on a standard agarose gel, cutting the high molecular band, and purifying the gel slice, using standard gel purification protocols. 2. Ligation of plasmid and gRNA sequences: 2.1. Targeted translocations: a. Mix 300 ng of the DNA fragment containing a pair of gRNA sequences (synthetic or PCR amplified) with 5U of SapI in the appropriate buffer. b. Incubate for 1 hour at 37°C. c. Purify the preparation using a standard column DNA purification protocol. d. Mix in a 0.2 mL tube 100 ng of the digested and purified plasmid backbone with 18 ng of the purified synthetic or PCR amplified DNA fragment and 5 U of T4 DNA ligase in the appropriate buffer. Adjust the final volume to 20 µL with water. e. Incubate at room temperature for at least 60 minutes before bacterial transformation. 2.2 Multiple translocations: a. Mix in a 0.2 mL tube 100 ng of the digested and purified plasmid backbone with 2 µL of the annealed oligonucleotides prepared in paragraph 3.2.2 and 5 U of T4 DNA ligase in the appropriate buffer. Adjust the final volume to 20 µL with water. b. Incubate at room temperature for at least 60 minutes before bacterial transformation. 3. Bacterial transformation: a. Use 10 µL of the ligation mix in a standard transformation protocol of Escherichia coli DH5α competent cells. b. Plate a 10 -2 dilution of the cells on LB agar supplemented with ampicillin at 100 µg/mL. c. Incubate the plates overnight at 37°C. d. Streak 12 clones on LB agar supplemented with ampicillin at 100 µg/mL using sterile toothpicks e. Incubate the plates overnight at 37°C. f. Inoculate 3 mL liquid cultures of LB supplemented with ampicillin (100 µg/mL) with single colonies in 15 mL tubes. g. Incubate under constant shaking (220 rpm) overnight at 37°C. h. In a cryotube, store 900 µL of the overnight culture with 300 µL of sterile glycerol 80 %. i. Vortex for 30 seconds. j. Store at -80°C.

1 .

 1 The donor DNAs of 90 bp have the following characteristics: a. Purification: salt free b. Synthesis scale: 0.05 µmol c. Delivery format: Lyophilized d. Quality control: MALDI 2. For each donor DNA, anneal the two complementary 90 bp oligonucleotides: a. Resuspend the oligonucleotides at the final concentration of 100 µM in water. b. Prepare an equimolar mix of both oligonucleotides in the annealing buffer c. Vortex the mix d. Incubate at 95°C for 5 minutes and let cool down slowly to room temperature.

4 . 6 .

 46 A recovery step is necessary for the pAEF5 plasmid: a. Pellet the cells by centrifugation. b. Resuspend gently in 1 mL of YPD broth. c. Incubate for 90 minutes at 30°C without agitation. 5. Cells are plated on YPD agar and selective media as described below: a. 100 µL of a 10 -5 dilution is plated on YPD to assess cell viability. b. 100 µL of a 10 -1 dilution is plated on selective medium. c. The rest of the cells are plated on selective medium. d. Incubate the plates for 3 days at 30°C. The number of colonies are counted after 3 days of incubation. (indicative results for the strains BY4741 and BY4742 are given in note 5). 7. Streak, on selective agar medium, with sterile toothpicks, 12 colonies from transformations with pAEF5 with the cloned gRNA and with or without the donor DNA for the targeted and multiple translocation transformations, respectively. 8. Incubate the plates for three days at 30°C. 9. Store 12 colonies at -80°C: a. Fill a cryotube with 500 µL of yeast storage media. b. Pick a colony with a 10 µL loop. c. Resuspend the colony by flicking the loop 10 times in the storage media. d. Vortex for 30 seconds.

2 . 3 .

 23 Sequence of the 464 bp synthetic DNA fragment. The two gRNA sequences are designated by 20 N in bolds. the two SapI restriction site are indicated in bold and underlined. The pAEF5 contains the hph gene which provides resistance to hygromycin B (Figure 3) and was deposited in the Addgene repository under the ID 136305.

Fig. 1

 1 Fig. 1 Flowchart representing the different steps to generate both targeted and multiple translocations. The numbers on the left refer to the paragraphs in the Methods section.

Fig. 2

 2 Fig. 2 PCR construction of 2 gRNA sequences and cloning in pAEF5. a) The plasmid pAEF5is digested with the SapI enzyme which cuts twice. As SapI cuts outside of its recognition site these sites are removed, leaving two extremities with 3 base overhangs (5'-gat-3') and (5'-gtt-3'). b) A plasmid pAEF5 already containing two cloned gRNAs (open green boxes) is used as a template for PCR with the 2 oligonucleotides (forward and reverse oligonucleotides). This PCR will give an amplicon with SapI restriction sites (purples arrows) at its extremities. After digestion of the PCR product with SapI, two complementary overhangs for cloning in the digested plasmid are generated (5'-atc-3') and (5'-aac-3').

Fig. 3

 3 Fig. 3 The plasmid pAEF5 was obtained by Gibson assembly of three fragments. The first two DNA fragments (blue and red sectors) are PCR amplified from pGZ110 (Note 8). They encode the replication origins for bacteria and yeast, the bacterial ampicillin resistance cassette, the Cas9 and the gRNA expression cassette. This cassette contains two SapI restriction sites in opposite orientation, allowing the cloning of DNA fragments containing single or double gRNA sequences (see lower part of the figure). The third DNA fragment (green sector) is amplified from pAG32 (https://www.addgene.org/35122/) and encodes the yeast hygromycin B resistance cassette.

Fig. 4

 4 Fig. 4 Targeted translocations. pAEF5 cloned with 2 gRNA sequences is used to transform Saccharomyces cerevisiae and generate DBSs at two loci situated on two different chromosomes. To guide the homologous repair, two chimerical donor DNAs are used.

  However, the number of colonies obtained may change due to variability in the transformation efficiency of strains. After 3 days of incubation, the expected number of colonies in each plate is: The pGZ110 plasmid kindly provided by Gang Zhao and Bruce Futcher (Stony Brook University) is described in (1) and does not correspond to the plasmid deposited on the addgene website (https://www.addgene.org/browse/sequence/129168/).

	Condition			Targeted	Multiple
	Viability (YPD agar)		10 1 -10 2	10 1 -10 2
	pAEF5 empty			10 3 -10 4	10 3 -10 4
	pAEF5 with gRNA(s)		10 0 -10 1	10 2 -10 3
	pAEF5 with 2 gRNAs and with donor	10 2 -10 3
	DNAs
	6. For rearrangements in repeated regions of the genome, the validation by PCR is not
	recommended.
	7. Expected results for the loss of the plasmid:
	Plasmid	YPD agar YPD+Hygro B
			agar
	Cells with pAEF5	growth	growth
	Cells without pAEF5 growth	no growth
	8.
	4. The expected SapI/SpeI digestion profiles for pAEF5, with one or two gRNA are presented
	in the table below:
		pAEF5 (fragment size in bp)
	empty	4713 -4215 -1925 -11
	1 gRNA	6649 -4215
	2 gRNAs	7059 -4215

5. These results are given for the strains BY4741 and BY4742. This protocol can also be applied to natural isolates of Saccharomyces cerevisiae.

Acknowledgement

We thank Allyson Holmes and Samuel O'Donnell for reading the manuscript.

CRISPR/Cas9. 415349