Aadirupa Saha
email: aadirupasaha<aadirupa@iisc.ac.in>.

Pierre Gaillard

Michal Valko

Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards

In this paper, we consider the problem of sleeping bandits with stochastic action sets and adversarial rewards. In this setting, in contrast to most work in bandits, the actions may not be available at all times. For instance, some products might be out of stock in item recommendation. The best existing efficient (i.e., polynomial-time) algorithms for this problem only guarantee an O(T 2/3 ) upperbound on the regret. Yet, inefficient algorithms based on EXP4 can achieve O( √ T ). In this paper, we provide a new computationally efficient algorithm inspired by EXP3 satisfying a regret of order O( √ T ) when the availabilities of each action i ∈ A are independent. We then study the most general version of the problem where at each round available sets are generated from some unknown arbitrary distribution (i.e., without the independence assumption) and propose an efficient algorithm with O( √ 2 K T ) regret guarantee. Our theoretical results are corroborated with experimental evaluations.

Introduction

The problem of standard multiarmed bandit (MAB) is well studied in machine learning [START_REF] Auer | Using upper confidence bounds for online learning[END_REF][START_REF] Vermorel | Multi-armed bandit algorithms and empirical evaluation[END_REF] and used to model online decision-making problems under uncertainty. Due to their implicit exploration-vsexploitation tradeoff, bandits are able to model clinical trials, movie recommendations, retail management job scheduling etc., where the goal is to keep pulling the 'best-item' in hindsight through sequentially querying one item at a time and subsequently observing a noisy reward feedback of the queried arm [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF]Auer et al., 2002a;[START_REF] Auer | Using confidence bounds for exploitationexploration trade-offs[END_REF][START_REF] Agrawal | Analysis of thompson sampling for the multi-armed bandit problem[END_REF][START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF].

Proceedings of the 37 th International Conference on Machine Learning, Vienna, Austria, PMLR 119, 2020. Copyright 2020 by the author(s).

However, in various real world applications, the decision space (set of arms A) often changes over time due to unavailability of some items etc. For instance, in retail stores some items might go out of stock, on a certain day some websites could be down, some restaurants might be closed etc. This setting is known as sleeping bandits in online learning [START_REF] 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], where at any round the set of available actions could vary stochastically based on some unknown distributions over A [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] 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 known to be 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 rewards and adversarial availabilities the achievable regret lower bound is known to be Ω( √ KT ), K being the number of actions in the decision space A = [K]. The well studied EXP4 algorithm does achieve the above optimal regret bound, although it is computationally inefficient [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF][START_REF] Kale | Hardness of online sleeping combinatorial optimization problems[END_REF]. However, the best known efficient algorithm only guarantees an Õ((T K) 2/3 ) regret, 1 which is not matching the lower bound both in K and T [START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF].

In this paper we aim to give computationally efficient and optimal O( √ T ) algorithms for the problem of sleeping bandits with adversarial rewards and stochastic availabilities. Our specific contributions are as follows:

Contributions

• We identified a drawback in the (sleeping) loss estimates in the prior work for this setting and gave an insight and margin for improvement over the best know rate (Section 3).

• We first study the setting when the availabilities of each item i ∈ A are independent and propose an EXP3based algorithm (Alg. 1) with an O(K 2 √ T ) regret guarantee (Theorem 2, Sec. 3).

• We next study the problem when availabilities are not 1 Õ(•) notation hides the logarithmic dependencies.

independent and give an algorithm with an O( √ 2 K T ) regret guarantee (Sec. 4).

• We corroborated our theoretical results with empirical evidence (Sec. 5).

Problem Statement

Notation. We denote by [n] := {1, 2, . . . , n}. 1(•) denotes the indicator random variable which takes value 1 if the predicate is true and 0 otherwise. Õ(•) notation is used to hide logarithmic dependencies.

Setup

Suppose the decision space (or set of actions) is [K] := {1, 2, . . . , K} with K distinct actions, and we consider a T round sequential game. At each time step t ∈ [T ], the learner is presented a set of available actions at round t, say S t ⊆ [K], upon which the learner's task is to play an action i t ∈ S t and consequently suffer a loss t (i t ) ∈ [0, 1], where t := [ t (i)] i∈[K] ∈ [0, 1] K denotes the loss of the K actions chosen obliviously independent of the available actions S t at time t. We consider the following two types of availabilities:

Independent Availabilities. In this case we assume that the availability of each item

i ∈ [K] is independent of the rest [K] \ {i}, such that at each round item i ∈ [K] is drawn in set S t with probability a i ∈ [0, 1],
or in other words, for all item i ∈ [K], 1(i ∈ S t ) ∼ Ber(a i ), where availability probabilities {a i } i∈[K] are fixed over time intervals t, independent of each other, and unknown to the learner.

General Availabilities. In this case each S t s is drawn iid from some unknown distribution P over subsets {S ⊆ [K], |S| ≥ 1} with no further assumption made on the properties of P. We denote by P (S) the probability of occurrence of set S.

Analyses with independent and general availabilities are provided respectively in Sec. 3 and 4.

Objective

We define by a policy π : 2 [K] → [K] to be a mapping from a set of available actions/experts to an item.

Regret definition

The performance of the learner, measured with respect to the best policy in hindsight, is defined as:

R T = max π:2 [K] →[K] E T t=1 t (i t ) - T t=1 t (π(S t )) , (1)
where the expectation is taken w.r.t. the availabilities and the randomness of the player's strategy. Remark 1. One obvious regret lower bound of the above objective is Ω( √ KT ), which follows from the bound of stan-dard MAB with adversarial losses (Auer et al., 2002a) for the special case when all the items are available at all times (even for availability-independent case). Interestingly, for a harder Sleeping-Bandits setting with adversarial availabilities the lower bound is Ω(K √ T ) [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF], even for which no computationally efficient algorithm is known till date (EXP4 is the only algorithm which achieves the regret but it is computationally inefficient). Thus the interesting question to answer here is if for our setup-that lies in the middle-ground of (Auer et al., 2002a) and [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF]-is it possible to attend the O(K √ T ) learning rate? Here lies the primary objective of this work. To the best of our knowledge, there is no existing algorithm which are known to achieve this optimal rate and the best known efficient algorithm is only guaranteed to yield an Õ((T K) 2/3 ) regret [START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF].

Proposed algorithm: Independent Availabilities

In this section we propose our first algorithm for the problem (Sec. 2), which is based on a variant of thr EXP3 algorithm with a 'suitable' loss estimation technique. Thm. 2 proves the optimality of its regret performance.

Algorithm description. Similar to EXP3 algorithm, at every round t ∈ [T ] we maintain a probability distribution p t over the arm set [K] and also the empirical availability of each item a ti = 1 t t τ =1 1(i ∈ S τ ) . Upon receiving the available set S t , the algorithm redistributes p t only on the set of available items S t , say q t , and plays an item i t ∼ q t . Subsequently the environment reveals the loss t (i t ), and we update the distribution p t+1 using exponential weights on the loss estimates for all i ∈ [K]

t (i) = t (i)1(i = i t ) qt (i) + λ t , (2)
where λ t is a scale parameter and qt (i) (see definition (3)) is an estimation of P r St,it i t = i , the probability of playing arm i at time t under the joint uncertainty in availability of i (due to S t ∼ P) and the randomness of EXP3 algorithm (due to i t ∼ p t ).

New insight compared to existing algorithms. It is crucial to note that one of our main contributions lies in the loss estimation technique t in (2). The standard loss estimates used by EXP3 (see [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]) are of the form t (i) =

t (i)1(i = i t )/p t (i).
Yet, because of the unavailable actions, the latter is biased. The solution proposed by [START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF]) (see Sec. 4.3) consists of using unbiased loss estimates of the form t (i) = t (i)1(i = i t )/( p t (i) a ti ) where a ti and p t (i) are estimates for the availability probability a i and for the weight p t (i) respectively. The suboptimal O(T 2/3 ) of their regret bound resulted from this Confidence parameter: δ > 0 4: Initialize:

5: Initial probability distribution p 1 (i) = 1 K , ∀i ∈ [K] 6: while t = 1, 2, . . . do 7: Define q S t (i) := pt(i)1(i∈S) j∈S pt(j) , ∀i ∈ [K], S ⊆ [K] 8: Receive S t ⊆ [K] 9: Sample i t ∼ q St t 10:
Receive loss t (i t )

11:

Compute:

a ti = t τ =1 1(i∈Sτ ) t 12: P a (S) = Π K i=1 a 1(i∈S) ti (1 -a ti ) 1-1(i∈S)
13:

qt (i) = S∈2 [K] P a (S)q S t (i) 14:
Estimate loss: j) , ∀i ∈ [K] 16: end while separated estimation of p t (i) and a ti , which leads to a high variance in the analysis because p t (i) = 0 whenever i / ∈ S t .

t (i) = t(i)1(i=it) qt(i)+λt , ∀i ∈ [K] 15: Update p t+1 (i) = pt(i)e -η t (i) K j=1 pt(i)e -η t (
We circumvent this problem by estimating them jointly as

qt (i) := S∈2 [K] P a (S)q S t (i) , (3)
where P at (S) = Π K i=1 a 1(i∈S) ti

(1 -a ti ) 1-1(i∈S) is the empirical probability of the availability of set S, and for all i ∈ [K]

q S t (i) := p t (i)1(i ∈ S) j∈S p t (j) , (4)
is the redistributed mass of p t on support set S. As shown in Lem. 1, qt (i) is a good estimate for q * t (i) = E S∼a q S t (i) , which is the conditional probability of playing action i t = i at time t. It turns out that qt (i) is much more stable than p t (i) a ti and therefore implies better variance control in the regret analysis. This improvement finally leads to the optimal O( √ T ) regret guarantee (Thm. 2). The complete algorithm is given in Alg. 1.

The first crucial result we derive towards proving Thm. 2 is the following concentration guarantees on qt : Lemma 1 (Concentration of qt ). Let t ∈ [T ] and δ ∈ (0, 1). Let q * t (i) = E S∼a q S t (i) and qt as defined in Equation (3). Then, with probability at least 1 -δ,

|q * t (i) -qt (i)| ≤ 2K 2 log(K/δ) t + 8K log(K/δ) 3t , (5)
for all i ∈ [K].
Using the result of Lem. 1, the following theorem analyses the regret guarantee of Sleeping-EXP3 (Alg. 1).

Theorem 2 (Sleeping-EXP3: Regret Analysis). Let T ≥ 1.

The sleeping regret incurred by Sleeping-EXP3 (Alg. 1) can be bounded as:

R T = max π:2 [K] →[K] E T t=1 (i t ) - T t=1 (π(S t )) ≤ 16K 2 √ T ln T + 1 ,
for the parameter choices η = (log K)/(KT ), δ = K/T 2 , and

λ t = min 2K 2 log(K/δ) t + 8K log(K/δ) 3t , 1 .
Proof. (sketch) Our proof is developed based on the standard regret guarantee of the EXP3 algorithm for the classical problem of multiarmed bandits with adversarial losses [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Auer | Using confidence bounds for exploitationexploration trade-offs[END_REF]. Precisely, consider any fixed set S ⊆ [K], and suppose we run EXP3 algorithm on the set S, over any nonnegative sequence of losses 1 , 2 , . . . T over items of set S, and consequently with weight updates q S 1 , q S 2 , . . . q S T as per the EXP3 algorithm with learning rate η. Then from the standard regret analysis of the EXP3 algorithm [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF], we get that for any i ∈ S:

T t=1 q S t , t - T t=1 t (i) ≤ log K η + η T t=1 k∈S q S t (k) t (k) 2 .
Let π * : S → [K] be any strategy. Then, applying the above regret bound to the choice i = π * (S) and taking the expectation over S ∼ P a and over the possible randomness of the estimated losses, we get

T t=1 E q S t , t - T t=1 E t (π * (S)) ≤ log K η + η T t=1 E k∈S q S t (k) t (k) 2 . (6)
Now towards proving the actual regret bound of Sleeping-EXP3 (recall the definition from Eqn. ( 1)), we first need to establish the following three main sub-results that relate the different expectations of Inequality (6) with quantities related to the actual regret (in Eqn. (1)).

Lemma 3. Let δ ∈ (0, 1). Let t ∈ [T ]. Define q S t as in (4) and t as in (2). Assume that i t is drawn according to q St t as defined in Alg. 1. Then,

E t (i t ) ≤ E q S t , t + 2Kλ t + δ λ t , for λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t . Lemma 4. Let δ ∈ (0, 1). Let t ∈ [T ]. Define t as in (2)
and assume that i t is drawn according to q St t as defined in Alg. 1. Then for any i ∈

[K], E t (i) ≤ t (i) + δ λ t , for λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t . Lemma 5. Let δ ∈ (0, 1). Let t ∈ [T ]
. Define q S t as in (4) and t as in (2). Then,

E i∈S q S t (i) t (i) 2 ≤ K + δ λ 2 t . for λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t .
With the above claims in place, we are now proceed to prove the main theorem: Let us denote the best policy π * := arg min π:

2 [K] →[K] T t=1 E St∼Pa [ (π(S t ))]
. Now, recalling from Eqn. ( 1), the actual regret definition of our proposed algorithm, and combining the claims from Lem. 3, 4, we first get:

R T (Sleeping-EXP3) = T t=1 E t (i t ) -t (π * (S t )) ≤ 2K T t=1 λ t + 2 T t=1 δ λ t + T t=1 E q S t , t -t (π * (S)) .
Then, we can further upper-bound the last term on the righthand-side using Inequality (6) and Lem. 5, which yields

R T (Sleeping-EXP3) ≤ 2K T t=1 λ t + 2 T t=1 δ λ t + log K η + ηKT + η T t=1 δ λ 2 t ≤ log K η + ηKT + 2K T t=1 λ t + 3 T t=1 δ λ 2 t , (7)
where in the last inequality we used that η ≤ 1 and λ t ≤ 1.

Otherwise, we can always choose min{1, λ t } instead of λ t in the algorithm and Lem. 1 would still be satisfied.

The proof is concluded by replacing

λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t
and by bounding the two sums as follows:

T t=1 λ t ≤ 2K 2 log K δ T + 8K 3 log K δ (1 + log T )
and using λ t ≥ 2K 2 log(K/δ)/t, we have

T t=1 1 λ 2 t ≤ 1 8K 2 log(K/δ) T t=1 t ≤ T 2 8K 2 log(K/δ) ≤ T 2 8K 2 .
Then, using δ := K/T 2 , log(K/δ) = 2 log(T ), we can further upper-bound:

T t=1 λ t ≤ 4K √ T log T + 8K 3 (1 + log T )(log T ) ≤ 7K √ T log T , and 3 T t=1 δ λ 2 t ≤ 3 8K ≤ 1.
Thus, upper-bounding the two sums into (7), we get

R T (Sleeping-EXP3) ≤ log K η +ηKT +14K 2 T log T +1 .
Optimizing η = (log K)/KT and upper-bounding

√ KT log K ≤ K 2 √ T , finally concludes the proof.
The above regret bound is of order Õ(K 2 √ T ), which is optimal in T , unlike any previous work which could only achieve Õ((KT ) 2/3 ) regret guarantees [START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF] at best. Thus our regret guarantee is only suboptimal in terms of K, as the lower bound of this problem is known to be Ω( √ KT ) [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF][START_REF] Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF]. However, it should be noted that in our experiments (see Figure 4), the dependence of our regret on the number of arms behaves similarly to other algorithms although their theoretical guarantees expect better dependencies on K. The sub-optimality could thus be an artifact of our analysis, but despite our efforts, we have not been able to improve it. We think this may come from our proof of Lem. 1, in which we see two gross inequalities that may cost us this dependence on K. First, the proof upper-bounds |q (S) t (i)| ≤ 1, while in average over i and S the latter is around 1/K. Yet, dependence problems condemn us to use this worst-case upper-bound. Secondly, the proof uses uniform bounds of |a i -a ti | over i = 1, . . . , K when the estimation errors could offset each other.

Note also that the regret bound in the theorem is worst-case. An interested direction for future work would be to study whether it is possible to derive an instance-dependent bound, based on the a i instances. Typically, K could be replaced by the expected number of active experts. A first step in this direction would be to start from Inequality (15) in the proof of Lem. 1 and try to keep the dependence on the a i distribution along the proof.

Finally, note that the algorithm only requires the beforehand knowledge of the horizon T to tune its hyper-parameter. However, the latter assumption can be removed by using standard calibration techniques such as the doubling trick (see [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF]).

Efficient Sleeping-EXP3: Improving Computational Complexity

Thm. 2 shows the optimality of Sleeping-EXP3 (Alg. 1), but its one limitation lies in computing the probability estimates

qt (i) := S∈2 [K] P a (S)q S t (i), ∀i ∈ [K],
which requires O(2 K ) computational complexity per round.

In this section we show how to get around with this problem just by approximating qt (i) by an empirical estimate

qt (i) := 1 t t τ =1 q S (τ ) t t (i) , (8)
where S

(1)

t , S (2)
t , . . . S (t) t are t independent draws from the distribution P a , i.e. P at (S) := Π K i=1 a 1(i∈S) ti

(1a ti ) 1-1(i∈S) for any S ⊆ [K] (recall the notation from Sec. 3). The above trick proves useful with the crucial obser-

vation that q S (1) t t (i), q S (2) t t (i), . . . q S (T ) t t (i) are independent of
each other (given the past) and that each q

S (τ ) t t (i) are unbi- ased estimated of qt (i). That is, E at [q S (τ ) t t (i)] = qt (i), ∀i ∈ [K], τ ∈ [t]
. By classical concentration inequalities, this precisely leads to fast concentration of qt (i) to qt (i) which in turn concentrates to q * t (i) (by Lem. 1). Combining these results, thus one can obtain the concentration of qt (i) to q * t (i) as shown in Lem. 6. Lemma 6 (Concentration of qt (i)). Let t ∈ [T ] and δ ∈ (0, 1). Let q * t (i) = E S∼a q S t (i) and qt as defined in Equation (8). Then, with probability at least 1 -δ,

|q * t (i) -qt (i)| ≤ 4K log(2K/δ) t + 8K log(2K/δ) 3t , for all i ∈ [K].
Remark 2. Note that for estimating qt , we can not use the observed sets S 1 , S 2 . . . , S t , instead of resampling S

(1)

t , S (2)
t . . . , S

t again-this is because in that case the resulting numbers q S1 t (i), q S2 t (i), . . . q St t (i) would no longer be independent, and hence can not derive the concentration result of Lem. 6 (see proof in Appendix A.3 for details).

Using the result of Lem. 6, we now derive the following theorem towards analyzing the regret guarantee of the computationally efficient version of Sleeping-EXP3. Theorem 7 (Sleeping-EXP3 (Computationally efficient version): Regret Analysis). Let T ≥ 1. The sleeping regret incurred by the efficient approximation of Sleeping-EXP3 (Alg. 1) can be bounded as:

R T ≤ 20K 2 T log T + 1 ,
for the parameter choices η = log K KT , δ = 2K/T 2 and λ t := 4K log(2K/δ)/t + 8K log(2K/δ)/3t. Furthermore, the per-round time and space complexities of the algorithm are O(tK) and O(K) respectively.

Proof. (sketch) The regret bound can be proved using similar steps as described for Thm. 2, except now we replace the concentration result of Lem. 6 in place of Lem. 1.

Computational complexity: At any round t ≥ 1, the algorithm requires only an O(K) cost to update a ti , t (i) and

p t+1 (i), ∀i ∈ [K]. Resampling t subsets S (τ ) t and comput- ing {q S (τ ) t t (i)} i∈[K]
requires another O(tK) cost, resulting in the claimed computational complexity.

Spatial complexity:

We only need to keep track of a t ∈ [0, 1] K and p t ∈ [0, 1] K making the total storage complexity just O(K) (noting qt can be computed sequentially).

Proposed algorithm: General Availabilities

Setting. In this section we assume general subset availabilities (see Sec. 2).

Algorithm 2 Sleeping-EXP3G

1: Input:

2:
Learning rate η > 0, scale parameter λ t 3:

Confidence parameter: δ > 0 4: Initialize:

5: Initial probability distribution p 1 (i) = 1 K , ∀i ∈ [K] 6: while t = 1, 2, . . . do 7: Receive S t 8: Compute q t (i) = pt(i)1(i∈St) j∈S t pt(j) , ∀i ∈ [K] 9: Sample i t ∼ q t 10: Receive loss t (i t ) 11: Compute: qt (i) := 1 t t τ =1 q Sτ t (i) 12:
Estimate loss bound t (i) = t(i)1(i=it) qt(i)+λt 13:

Update p t+1 (i) = pt(i)e -η t (i) K j=1 pt(i)e -η t (j) , ∀i ∈ [K] 14: end while 4.1. Proposed Algorithm: Sleeping-EXP3G Main idea. By and large, we use the same EXP3 based algorithm as proposed for the case of independent availabilities, the only difference lies in using a different empirical estimate

qt (i) := 1 t t τ =1 q Sτ t (i) . (9)
In hindsight, the above estimate qt (i) is equal to the expectation

E S∼ Pt [q S t ], i.e., qt (i) = S∈2 [K] P (S)q S t (i), where P t (S) := 1 t t τ =1 1(S τ = S)
is the empirical probability of set S at time t. The rest of the algorithm proceeds the same as Alg. 1, the complete description is given in Alg. 2.

Regret Analysis

We first analyze the concentration of qt (i)-the empirical probability of playing item i at any round t, and the result goes as follows:

Lemma 8 (Concentration of qt (i)). Let t ∈ [T ]. Let q *
t (i) = E S∼a q S t (i) , and define qt (i) as in Equation (9).

Then, with probability at least (1 -δ),

|q * t (i) -qt (i)| ≤ 2 K+1 t ln 2 K δ + 2 K+1 3t ln 2 K δ , for all i ∈ [K].
Using Lem. 8 we now analyze the regret bound of Alg. 2. Theorem 9 (Sleeping-EXP3G: Regret Analysis). Let T ≥ 1. Suppose we set η = (log K)/(KT ), δ = 2 K /T 2 , and

λ t = (2 K+1 /t) ln(2 K /δ) + 2 K+1 ln(2 K /δ)/(3t).
Then, the regret incurred by Sleeping-EXP3G (Alg. 2) can be bounded as:

R T ≤ K 2 K+4 T log T + K2 K+3 (log T ) 2 .
Furthermore, the per-round space and time complexities of the algorithm are O(tK).

Proof. (sketch) The proof proceeds almost similar to the proof of Thm. 2 except now the corresponding version of the main lemmas, aka. Lem. 3,4, and 5 are satisfied but for

λ t = 2 K+1 t ln 2 K δ + 2 K+1 3t ln 2 K δ
, since here we need to use the concentration Lem. 8 instead of Lem. 1.

Similar to the proof of Thm. 2 and following the same notation, we first combine claims from Lem. 3, 4 to get:

R T (Sleeping-EXP3G) = T t=1 E t (i t ) -t (π * (S t )) ≤ T t=1 E q S t , t + 2Kλ t + 2δ λ t -E[ t (π * (S t ))] (a) ≤ log K η + η T t=1 E k∈S q S t (k) t (k) 2 + 2 T t=1 Kλ t + δ λ t (b) ≤ log K η + ηKT + T t=1 2Kλ t + 2δ λ t + ηδ λ 2 t ≤ log K η + ηKT + T t=1 2Kλ t + 3δ λ 2 t ,
where Inequality (a) and (b) respectively follow from (6) and Lem. 5. The last inequality holds because η ≤ 1 and λ t ≤ 1. To conclude the proof, it now only remains to compute the sums and to choose the parameters δ = 2 K /T 2 and η = (log K)/KT . Using λ t ≥ 2 K+1 /t, we have

T t=1 δ λ 2 t ≤ δT 2 2 K+1
≤ 1, and since log(2 K /δ) = 2 log T , we further have

λ t = 2 K+1 t ln T + 2 K+1 3t ln T which entails: T t=1 λ t ≤ 2 K+1 T log T + 2 K+1 3 (log T )(1 + log T ) ≤ 2 K+1 T log T + 2 K+2 (log T ) 2 .
Finally, substituting η and the above bounds in the regret upper-bound yields the desired result.

Complexity analysis. The only difference with Alg. 1 lies in computing qt (i). Following a similar argument given for proving the computational complexity of Thm. 7, this can also be performed with a computational cost of O(tK). Yet, now the algorithm specifically needs to keep in memory the empirical distribution of S 1 , . . . , S t and thus a space complexity of O(K + min{tK, 2 K }) is required.

Our regret bound in Thm. 9 has the optimal √ T dependency-to the best of our knowledge, Sleeping-EXP3G (Alg 2) is the first computationally efficient algorithm to achieve O( √ T ) guarantee for the problem of Sleeping-Bandits. Of course the EXP4 algorithm is known to attain the optimal O( √ KT ) regret bound, however it is computationally infeasible [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF] due to the overhead of maintaining a combinatorial policy class.

Yet, on the downside, it is worth pointing out that the regret bound of Thm. 9 only provides a sublinear regret in the regime 2 K ≤ O(T ), in which case algorithms such as EXP4 can be efficiently implemented. However, we still believe our algorithm to be an interesting contribution because it completes another side of the computational-performance trade-off. It is possible to move the exponential dependence on the number of experts from the computational complexity to the regret bound.

Another argument in favor of this algorithm is that it provides an efficient alternative algorithm to EXP4 with regret guarantees in the regime 2 K ≤ O(T ). In the other regime, though we could not prove any meaningful regret guarantee, Alg. 4.1 performs very well in practice as shown by our experiments. We believe the 2 K constant in the regret to be an artifact of our analysis. However, removing it seems to be highly challenging due to dependencies between q S t and S 1 , . . . , S t . An analysis of the concentration of qt (defined in (9)) to q * t without exponential dependence on K proved to be particularly complicated. We leave this question for future research.

Experiments

In this section we present the empirical evaluation of our proposed algorithms (Sec. 3 and 4) comparing their performances with the two existing sleeping bandit algorithms that apply to our problem setting, i.e. for adversarial losses Performance Measures. In all cases, we report the cumulative regret of the algorithms for T = 5000 time steps, each averaged over 50 runs. In the following subsections, we analyze our experimental evaluations for both independent and general (non-independent) availabilities.

Independent Availabilities

In this case the item availabilities are assumed to be independent at each round (description in Sec. 2).

Environments. We consider K = 20 and generate the probabilities of item availabilities {a i } i∈[K] independently and uniformly at random from the interval [0.3, 0.9]. We use the following loss generation techniques: (1) Switching loss or SL(τ ). We generate the loss sequence such that the best performing expert changes after every τ length epochs.

(2) Markov loss or ML(p). Similar to the setting used in [START_REF] Neu | Online combinatorial optimization with stochastic decision sets and adversarial losses[END_REF], losses for each arm are constructed as random walks with Gaussian increments of standard deviation p, initialized uniformly on [0, 1] such that losses outside [0, 1] are truncated. The explicit values used for τ and p are specified in the corresponding figures. The algorithm parameters η, λ t , δ are set as defined in Thm7.

Remarks. From Fig. 1 it clearly shows that regret bounds of our proposed algorithm Sleeping-EXP3 and Sleeping-EXP3G outperform the other two due to their orderwise optimal O( √ T ) regret performance (see Thm. 2 and 9). In particular, Bandit-SFPL performs the worst due to its initial O(T 4/5 ) exploration rounds and uniform exploration phases thereafter. Sleeping-Cat gives a much competitive regret bound compared to Bandit-SFPL however, still lags behind due to the O(T 2/3 ) regret guarantee (see Sec. 3.1 for a detailed explanation).

Regret vs Varying Availabilities.

We next conduct a set of experiments to compare the regret performances of the algorithms with varying availability probabilities: For this we assign same availability a i = a ∈ [0.1] to every item i ∈ [K] for a = 0.3, 0.5, 0.7, 0.9 and plot the final cumulative regret of each algorithm.

Remarks From Fig. 2, we again note our algorithms outperform the other two by a large margin for almost every p. The performance of BSFPL is worse, it steadily decreases with increasing availability probability due to the explicit O(T 4/5 ) exploration rounds in the initial phase of BSFPL, and even thereafter it keeps on suffering the loss of the uniform policy scaled by the exploration probability.

Correlated (General) Availabilities

We now assess the performances when the availabilities of items are dependent (description in Sec. 2).

Environments. To enforce dependencies of item availabilities we generate each set S t by drawing a random sample from a Gaussian(µ, Σ) such that µ i = 0, ∀i ∈ [K], and Σ is some random K×K positive definite matrix, e.g. block diagonal matrix with strong correlations among certain groups of items. More precisely, at each round t, we first sample a random K-vector, say v t , from Gaussian(µ, Σ) and we set S t = i ∈ [K]|v t (i) > 0, i.e. S t includes all those items whose corresponding coordinates are non-negative-this thus enforces item dependencies in the resulted S t if Σ is block diagonal (or any correlation matrix). To generate the loss sequences, we use similar techniques described in Sec. 5.1. The algorithm parameters are set as defined in Thm9.

Remarks. From Fig. 3 one can again verify the superior performance of our algorithms over Sleeping-Cat and Bandit-SFPL, however the effect is only visible for large T as for smaller time steps t, the O(2 K ) terms dominates the regret performance, but as t shoots higher our optimal O( √ T ) rate outperforms the suboptimal O(T 2/3 ) and O(T 4/5 ) rates of Sleeping-Cat and Bandit-SFPL respectively.

Regret vs Varying Item-size (K).

Finally we also conduct a set of experiments changing the item set size K over a wide range (K = 10 to 4000). We report the final cumulative regret of all algorithms vs. K for different switching loss sequence for both independent and general availabilities, as specified in Fig. 4.

Remark. Fig. 4 shows that the regret of each algorithm increases with K, as expected. As before the other two baselines perform suboptimally in comparison to our algorithms, however the interesting thing to note is the relative performance of Sleeping-EXP3 and Sleeping-EXP3G-as per Thm. 2 and 9, Sleeping-EXP3 must outperform Sleeping-EXP3G with increasing K, however the effect does not seem to be so drastic experimentally, possibly revealing the scope of improving Thm. 9 in terms of a better dependency in K.

Conclusion and Future Work

We have presented a new approach that brought an improved rate for the setting of sleeping bandits with adversarial losses and stochastic availabilities including both minimax and instance-dependence guarantees. While our bounds guarantee a regret of Õ( √ T ), there are several open questions before the studied setting can be considered as closed. Firstly, for the case of independent availabilities, we provide a regret guarantee of Õ(K 2 √ T ), leaving open whether Õ( √ KT ) is possible as in the standard non-sleeping setting. Secondly, while we provided computationally efficient (i.e., with per-round complexity of order O(tK)) Sleeping-EXP3, for the case of general availabilities and provided instance dependent regret guarantees for it, the worst case regret guarantee still amounts to Õ(

√ 2 K T ).
Therefore, it is still unknown if for the general availabilities we can get an algorithm that would be both computationally efficient and have Õ(poly(K)

√

T ) regret guarantee in the worst case. We would like to point out that the new techniques could be potentially used to provide new algorithms and guarantees in settings with similar challenges as in sleeping bandits, such as rotting or dying bandits. Finally, having algorithms for sleeping bandits with Õ( √ T ) regret guarantees, opens a way to deal with sleeping constraints in more challenging structured bandits with large or infinite number of arms and having the regret guarantee depend not on number of arms but rather some effective dimension of the arms' space.

Supplementary: Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards

A. Appendix for Sec. 3

A.1. Proof of Lem. 1

Lemma 1 (Concentration of qt ). Let t ∈ [T ] and δ ∈ (0, 1). Let q * t (i) = E S∼a q S t (i) and qt as defined in Equation (3). Then, with probability at least 1 -δ,

|q * t (i) -qt (i)| ≤ 2K 2 log(K/δ) t + 8K log(K/δ) 3t , (5)
for all i ∈ [K].
Proof. Let t ∈ [T ] and δ ∈ (0, 1). We start by noting the concentration of a ti = 1

t t τ =1 1(i ∈ S τ ) to a i for all i ∈ [K]
. By Bernstein's inequality together with a union bound over i = 1, . . . , K: with probability at least 1 -δ, for all i ∈ [K]

|a i -a ti | < 2a i (1 -a i ) ln K δ t + 2 ln K δ 3t . (10)
Then, β = 2 log(K/δ), using the definitions of

P at (S) = Π K i=1 a 1(i∈S) ti (1 -a ti ) 1-1(i∈S) and P a (S) = Π K i=1 a 1(i∈S) i (1 - a i ) 1-1(i∈S) , we get |P at (S) -P a (S)| = P a (S) P at (S) P a (S) -1 = P a (S) Π K i=1 a ti a i Si 1 -a ti 1 -a i 1-Si -1 = P a (S) Π K i=1 a ti -a i a i + 1 Si a i -a ti 1 -a i + 1 1-Si -1 ≤ P a (S) Π K i=1 | a ti -a i | a i + 1 Si |a i -a ti | 1 -a i + 1 1-Si -1 , (11)
where the last inequality is because for any 1 , . . .

, K ∈ [-1, 1] K K i=1 (1 + i ) -1 = max K i=1 (1 + i ) -1, 1 - K i=1 (1 + i ) ≤ max K i=1 1 + | i | -1, 1 - K i=1 1 -| i | ≤ K i=1 1 + | i | -1 .
Hence, denoting

Z i := 1 + β(1 -a i ) a i t + β 3a i t Si 1 + βa i (1 -a i )t + β 3(1 -a i )t 1-Si
, and using Bernstein's inequality (10), with probability 1 -δ, we have

|P at (S) -P a (S)| ≤ P a (S) K i=1 Z i -1 . (12)
Therefore,

|q * t (i) -qt (i)| = S∈2 [K]
q S t (i) P a (S) -P at (S) ← By definition (3)

≤ S∈2 [K]
q S t (i) P a (S) -P at (S)

≤ S∈2 [K] P a (S) K i=1 Z i -1 ← From (12) and |q S t (i)| ≤ 1 = E S∼Pa K i=1 Z i -1 . (13)
But by independence of the Z i , we know

E S∼Pa K i=1 Z i = K i=1 E S∼Pa Z i . (14)
Now, computing each expectation

E S∼Pa Z i = E Si∼ai   1 + β(1 -a i ) a i t + β 3a i t Si 1 + βa i (1 -a i )t + β 3(1 -a i )t 1-Si   = a i 1 + β(1 -a i ) a i t + β 3a i t + (1 -a i ) 1 + βa i (1 -a i )t + β 3(1 -a i )t ≤ 1 + 2 βa i (1 -a i ) t + 2β 3t (15)
≤ 1 + β t + 2β 3t .
Therefore, combining with Inequalities ( 13) and ( 14), it yields using 1 + x ≤ e x for x ≥ 0,

|q * t (i) -qt (i)| ≤ 1 + β t + 2β 3t K -1 ≤ e K √ β t + 2Kβ 3t -1 .
Then, assuming t ≥ 25βK 2 /9, we have

K β t + 2Kβ 3t ≤ 1
which implies since e x ≤ 1 + 2x for all 0 ≤ x ≤ 1 and replacing β = 2 log(K/δ)

|q * t (i) -qt (i)| ≤ 2K 2 log(K/δ) t + 8K log(K/δ) 3t . If t ≤ 15βK 2 /9, then, |q * t (i) -qt (i)| ≤ 1 ≤ 4K 3 log(1/δ) t .
Therefore, for all δ ∈ (0, 1), with probability at least 1 -δ, for all

1 ≤ i ≤ K |q * t (i) -qt (i)| ≤ 2K 2 log(K/δ) t + 8K log(K/δ) 3t . A.2. Proof of Thm. 2
Theorem 2 (Sleeping-EXP3: Regret Analysis). Let T ≥ 1. The sleeping regret incurred by Sleeping-EXP3 (Alg. 1) can be bounded as:

R T = max π:2 [K] →[K] E T t=1 (i t ) - T t=1 (π(S t )) ≤ 16K 2 √ T ln T + 1 ,
for the parameter choices η = (log K)/(KT ), δ = K/T 2 , and

λ t = min 2K 2 log(K/δ) t + 8K log(K/δ) 3t , 1 .
Proof. Consider any fixed set S ⊆ [K], and suppose we run EXP3 algorithm on the set S, over any nonnegative sequence of losses 1 , 2 , . . . T over items of set S, and consequently with weight updates q S 1 , q S 2 , . . . q S T where as per EXP3 algorithm

q S t (i) = e -η t-1 τ =1 τ (i) j∈S e -η t-1 τ =1 τ (j) , i ∈ S (16)
η > 0 being the learning rate of the EXP3 algorithm. Note here that for the analysis, we assume for this hypothetical EXP3 algorithm which plays on actions in S only, the available sets are fixed to S for all t ∈ [T ]. We also consider that q S t (i) = 0 for i / ∈ S.

Then from the standard regret analysis of the EXP3 algorithm it is known that [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF] for all i ∈ S T t=1 q S t , t -

T t=1 t (i) ≤ log K η + η T t=1 k∈S q S t (k) t (k) 2 .
Let π * : S → [K] be any strategy. Then, applying the above regret bound to the choice i = π * (S) and taking the expectation over S ∼ P a and over the possible randomness of the estimated losses, we get

T t=1 E q S t , t - T t=1 E t (π * (S)) ≤ log K η + η T t=1 E k∈S q S t (k) t (k) 2 . ( 17
)
Note that we did not make any assumptions on the estimated losses yet expect non-negativity.

For simplicity we abbreviate S ∼ P a as S ∼ a henceforth. We denote the sigma algebra generated by the history of outcomes till time t (i.e. {i τ , S τ } t τ =1 ) by H t . Then recall from Eqn.

(1) that we wish to analyse the regret R T , which is defined with respect to the loss sequence 1 , 2 , . . . T and with activation sets S 1 , . . . , S T . That is, we need to upper-bound

R T = max π:2 [K] →[K] T t=1 E t (i t ) - T t=1 E t (π(S t ))
.

Towards proving the above regret bound of Sleeping-EXP3 from Inequality (17), we now first establish the following lemmas that relates the different expectations of Inequality (17) with quantities related to the regret.

Lemma 3. Let δ ∈ (0, 1). Let t ∈ [T ]. Define q S t as in (4) and t as in (2). Assume that i t is drawn according to q St t as defined in Alg. 1. Then,

E t (i t ) ≤ E q S t , t + 2Kλ t + δ λ t , for λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t . Proof. Let t ∈ [T ].
We first consider the probabilistic event (denoted E t ) that ( 5) is true. That is, for all i ∈ [K]

|q * t (i) -qt (i)| ≤ λ t . (18)
Remark that E t is H t-1 measurable since qt and q * t are H t-1 measurable. We start from the right hand side noting that:

E q S t , t E t = E i∈S q S t (i) t (i) E t = E E i∈S q S t (i) t (i)1(i t = i) qt (i) + λ t S, S t , H t-1 E t ← by definition (2) of t = E E i∈St q S t (i) t (i)q St t (i) qt (i) + λ t S t , H t-1 E t ← taking the expectation over i t ∼ q St t = E E i∈St q * t (i) t (i)q St t (i) qt (i) + λ t H t-1 E t ← taking the expectation over S ∼ a ≥ E E i∈St q * t (i) t (i)q St t (i) q * t (i) + 2λ t H t-1 E t ← from Inequality (18) ≥ E E i∈St t (i)q St t (i) 1 - 2λ t q * t (i) H t-1 E t ← since (1 + x) -1 ≥ 1 -x for x ≥ 0 ≥ E E i∈St t (i)q St t (i) H t-1 E t -E 2λ t K i=1 E q St t (i) H t-1 q * t (i) E t ← since q * t is H t-1 measurable = E E i∈St t (i)q St t (i) H t-1 E t -2Kλ t ← by definition of q * t (i) = E q St t (i) H t-1 = E t (i t ) E t -2Kλ t .
It remains now to deal with the case when the event E t (i.e., (18)) is not satisfied. By Lem. 1, this happens with probability smaller than δ. Therefore because the estimated losses are smaller than 1/λ t , we have

E q S t , t = E q S t , t E t P r(E t ) + E q S t , t not E t P r not E t ≥ E t (i t ) E t ]P r(E t ) -2Kλ t - P r not E λ t ≥ E t (i t )] -2Kλ t - δ λ t .
Lemma 4. Let δ ∈ (0, 1). Let t ∈ [T ]. Define t as in (2) and assume that i t is drawn according to q St t as defined in Alg. 1. Then for any i ∈ [K],

E t (i) ≤ t (i) + δ λ t , for λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t .
Proof. The proof follows a similar analysis to the one of Lem. 3. We start by assuming the probabilistic event E t of Inequality ( 18) and to ease the notation, we denote by E t = E • E t the conditional expectation given E t holds true. Then,

E t t (i) = E t E t (i)1(i t = i) qt (i) + λ t S t , H t-1 ← by definition of t = E t E t (i)q St t (i) qt (i) + λ t H t-1 ← taking the expectation over i t ∼ q St t = E t t (i)q * t (i) qt (i) + λ t ← taking the expectation over S t ∼ a ≤ E t t (i) ← by (18) = t (i) .
Similarly to the proof of Lem. 3, using that E holds with probability at least 1 -δ and using that the estimated losses are in [0, 1/λ t ], we get

E t (i) ≤ t (i) + δ λ t . Lemma 5. Let δ ∈ (0, 1). Let t ∈ [T ]
. Define q S t as in (4) and t as in (2). Then,

E i∈S q S t (i) t (i) 2 ≤ K + δ λ 2 t . for λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t . Proof. Let t ∈ [T ].
Then, denoting E t the event such that (18) holds, we can derive:

E t i∈S q S t (i) t (i) 2 = E t E i∈S q S t (i) 2 t (i)1(i t = i) (q t (i) + λ t ) 2 S, S t , H t-1 ← by definition of t = E t E i∈St q S t (i) 2 t (i)q St t (i) (q t (i) + λ t ) 2 S t , H t-1 ← taking the expectation over i t ∼ q St t ≤ E E i∈St q * t (i) q St t (q t (i) + λ t ) 2 H t-1 ,
where, in the last inequality, we took the expectation over S t ∼ a and used that t (i) 2 ≤ 1. Therefore, taking the expectation over S t ∼ a, we get

E t i∈S q S t (i) t (i) 2 ≤ E t i∈[K] q * t (i) 2 (q t (i) + λ t ) 2 ≤ K ,
where the last inequality is because under E t , |q t (i) -q * t (i)| ≤ λ t . Now, using that t (i) 2 ≤ 1/λ 2 t , and using that E t is satisfied with probability at least 1 -δ, we conclude the proof of the lemma:

E i∈S q S t (i) t (i) 2 ≤ K + δ λ 2 t .
Given the above claims in place, we are now in a position to prove the main theorem as shown below. Recall from Eqn. (1), the actual regret definition of our proposed algorithm:

R T (Sleeping-EXP3) = max π:2 [K] →[K] T t=1 E t (i t ) -t (π(S t ))
Denoting the best policy π * := arg min π:2

[K] →[K] T t=1 E St∼Pa [ (π(S t ))],
and combining the claims from Lem. 3, 4, we get:

R T (Sleeping-EXP3) = T t=1 E t (i t ) -t (π * (S t )) ≤ T t=1 E q S t , t + 2Kλ t + δ λ t -t (π * (S t )) + δ λ t ← from Lemmas 3 and 4 ≤ 2K T t=1 λ t + 2 T t=1 δ λ t + T t=1 E q S t , t -t (π * (S)) .
Then, we can further upper-bound the last term in the right-hand-side using Inequality (17) and Lem. 5, which yields

R T (Sleeping-EXP3) ≤ 2K T t=1 λ t + 2 T t=1 δ λ t + log K η + η T t=1 E k∈S q S t (k) t (k) 2 ≤ 2K T t=1 λ t + 2 T t=1 δ λ t + log K η + ηKT + η T t=1 δ λ 2 t ≤ log K η + ηKT + 2K T t=1 λ t + 3 T t=1 δ λ 2 t , (19)
where in the last-inequality we used that η ≤ 1 and λ t ≤ 1. Otherwise, we can always choose min{1, λ t } instead of λ t in the algorithm and Lem. 1 would still be satisfied.

The proof is concluded by replacing

λ t = 2K 2 log(K/δ) t + 8K log(K/δ) 3t
and by upper-bounding the two sums

T t=1 λ t = 2K 2 log K δ T t=1 1 √ t + 8K 3 log K δ T t=1 1 t ≤ 2K 2 log K δ T + 8K 3 log K δ (1 + log T )
and using λ t ≥ 2K 2 log(K/δ)/t, we have

T t=1 1 λ 2 t ≤ 1 8K 2 log(K/δ) T t=1 t ≤ T 2 8K 2 log(K/δ) ≤ T 2 8K 2 .
Then, using δ := K/T 2 , log(K/δ) = 2 log(T ), we can further upper-bound:

T t=1 λ t ≤ 4K T log T + 8K 3 (1 + log T )(log T ) ≤ 7K T log T and 3 T t=1 δ λ 2 t ≤ 3 8K ≤ 1 .
Thus, upper-bounding the two sums into (19), we get

R T (Sleeping-EXP3) ≤ log K η + ηKT + 14K 2 T log T + 1 .
Optimizing η = (log K)/KT and upper-bounding

√ KT log K ≤ K 2 √ T ,
Taking a union bound over all 2 K subsets S ⊆ [K], we get that: P r(E t ) ≥ 1 -δ. Now recall in this case that by definition q * t (i) := E S∼P [q S t (i)] =

S∈2 [K] P (S)q S t (i),

and similarly,

qt (i) := 1 t t τ =1
q Sτ t (i) = E S∼ Pt(S) [q S t (i)] = S∈2 [K] P t (S)q S t (i),

with P t (S) := 1 t t τ =1 1(S τ = S). To ease the notation, let us denote S i = 1(i ∈ S). We now proceed to bound |q * t (i) -qt (i)| for any item i ∈ [K], t ∈ [T ]. Let us denote Q t (i) = S∈2 [K] q S t (i). Note that Q t (i) ≤ 2 K . Let us also define for simplicity α(S) = 2P (S)(1 -P (S)) ln(2 K /δ) and β = 2 3 ln(2 K /δ) the terms in the right-hand-side of (23). Then, following the above claims we note that from (23) with probability at least (1 -δ),

|q * t (i) -qt (i)| ≤ S∈2 [K]
q S t (i) P (S) -P t (S) ← from ( 24) and ( 25)

≤ S∈2 [K]
q S t (i)

α(S) t + β t ← from (23) ≤ β2 K t + Q t (i) S∈2 [K] q S t (i) Q t (i) α(S) t ← because Q t (i) ≤ 2 K ≤ β2 K t + Q t (i) S∈2 [K]
q S t (i)α(S) Q t (i)t ← from Jensen's inequality

≤ 2 K+1 t ln 2 K δ + 2 K+1 3t ln 2 K δ ,
where the last inequality is because Q t (i) ≤ 2 K and S∈2 [K] q S t (i)α(S) ≤ S∈2 [K] α(S) ≤ 2 log(2 K /δ) S∈2 [K] P (S) ≤ 2 log(2 K /δ) .

This concludes the proof of the Lemma.

B.1. Proof of Thm. 9

Theorem 9 (Sleeping-EXP3G: Regret Analysis). Let T ≥ 1. Suppose we set η = (log K)/(KT ), δ = 2 K /T 2 , and λ t = (2 K+1 /t) ln(2 K /δ) + 2 K+1 ln(2 K /δ)/(3t). Then, the regret incurred by Sleeping-EXP3G (Alg. 2) can be bounded as: R T ≤ K 2 K+4 T log T + K2 K+3 (log T ) 2 .

Furthermore, the per-round space and time complexities of the algorithm are O(tK).

Proof. The proof is almost similar to the proof of Thm. 2. We use the same notation introduced in that proof for ease of understanding. Same as before the proof relies on the Lemmas 3, 4, and 5 that are satisfied but for

λ t =

Figure 1 .

 1 Figure 1. Regret vs Time: Independent availabilities

Figure 2 .

 2 Figure 2. Final regret (at round T ) vs availability probabilities((a))

Figure 3 .

 3 Figure 3. Regret vs time: General availabilities

Figure 4 .

 4 Figure 4. Final regret (at round T ) vs item size (K)

  Lemma 8 (Concentration of qt (i)). Let t ∈ [T ]. Let q * t (i) = E S∼a q S t (i) , and define qt (i) as in Equation (9). Then, with probability at least (1 -δ), Proof. Let t ∈ [T ]. We start by first noting the concentration of P (S) for any S ⊆ [K], which using Bernstein's inequality we know that given any fixed δ ∈ [0, 1]:

		|q * t (i) -qt (i)| ≤	2 K+1 t	ln	2 K δ	+	2 K+1 3t	ln	2 K δ	,
	for all i ∈ [K].
		P r |P (S) -P t (S)| >	2P (S)(1 -P (S)) ln 1 δ t	+	2 ln 1 δ 3t	≤ δ .
	Then consider the event
	E t :=	   ∀S ⊆ [K] : |P (S) -P t (S)| >	2P (S)(1 -P (S)) ln 2 K δ t	+	2 ln 2 K δ 3t	  	.

we finally conclude the proof R T (Sleeping-EXP3) ≤ 16K 2 T log T + 1 . B. Appendix for Sec. 4

  since we need to use the concentration Lem. 8 instead of Lem. 1. Now, recall from Eqn. (1), the actual regret definition of our proposed algorithm: St∼Pa [ (π(S t ))], and combining the claims from Lem. 3, 4 and 5, we get following the same arguments as the ones of Thm. 2:R T (Sleeping-EXP3G) = (i t )t (π * (S t ))To conclude the proof, it only remains to compute the sums and to choose the parameters δ = 2 K /T 2 and η = (log K)/KT . Using λ t ≥ 2 K+1 /t, we have

								2 K+1 t	ln	2 K δ	+	2 K+1 3t	ln	2 K δ	,
				R T (Sleeping-EXP3G) = max
						T
	t=1 E t ≤ T t=1 E q S t , t + 2Kλ t + 2δ λ t -E[ = T t=1 E q S t , T t=1		Kλ t +	δ λ t
	≤	log K η	+ η	T t=1	E	k∈S	q S t (k) t (k) 2 + 2	T t=1	Kλ t +	δ λ t	← from Inequality (17)
	≤	log K η	+ ηKT +	T t=1	2Kλ t +	2δ λ t	+	ηδ t λ 2	← from Lem. 5
	≤	log K η	+ ηKT +	T t=1	2Kλ t +	3δ λ 2
								T t=1	δ λ 2 t	≤	δT 2 2 K+1 ≤ 1
	and since log(2 K /δ) = 2 log T ,
							λ t =	2 K+1 t	ln T +	2 K+1 3t	ln T
	which entails

π:2 [K] →[K] T t=1 E t (i t )t (π(S t ))

Denoting the best policy π * := arg min π:2

[K] →[K] T t=1 E t (π * (S t ))] ← from Lem. 3 and Lem. 4 tt (π * (S)) + 2 t ← because η ≤ 1 and λ t ≤ 1 T t=1 λ t ≤ 2 K+1 T log T + 2 K+1 3 (log T )(1 + log T ) ≤ 2 K+1 T log T + 2 K+2 (log T ) 2 .

Acknowledgements

We thank the anonymous reviewers for their valuable suggestions. The research presented was supported French National Research Agency project BOLD (ANR-19-CE23-0026-04) and by European CHIST-ERA project DELTA. We also wish to thank Antoine Chambaz and Marie-Hélène Gbaguidi for supporting Aadirupa's internship at Inria, and Rianne de Heide for the thorough proofreading.

A.3. Proof of Lem. 6 Lemma 6 (Concentration of qt (i)). Let t ∈ [T ] and δ ∈ (0, 1). Let q * t (i) = E S∼a q S t (i) and qt as defined in Equation (8). Then, with probability at least 1 -δ,

We start by remarking that for any i ∈ [K]:

Note that q

(i) are independent of each other given the past H t-1 . Furthermore, they are in [0, 1] and are unbiased estimates of qt (i) = E S∼ at [q S t (i)], i.e., for all i

Thus, using Hoeffding's inequality and a union bound over all i ∈ [K], we get that with probability at least (1 -δ/2):

Furthermore, from Lem. 1 we have, for all i ∈ [K], with probability at least (1 -δ/2):

The proof follows combining Eqn. ( 20), ( 21) and ( 22) and using K ≥ 1.

A.4. Proof of Thm. 7

Theorem 7 (Sleeping-EXP3 (Computationally efficient version): Regret Analysis). Let T ≥ 1. The sleeping regret incurred by the efficient approximation of Sleeping-EXP3 (Alg. 1) can be bounded as:

for the parameter choices η = log K KT , δ = 2K/T 2 and λ t := 4K log(2K/δ)/t + 8K log(2K/δ)/3t. Furthermore, the per-round time and space complexities of the algorithm are O(tK) and O(K) respectively.

Proof. The regret bound can be proved using the same proof technique used for Thm. 2, except replacing the concentration result of Lem. 6 in place of Lem. 1.

Concerning the computational time. At each round t ≥ 1, the Alg. 1 performs the following operations:

The time complexity to perform iteration t is therefore O(tK).

As for spatial complexity, the algorithm only needs to keep track of a t ∈ [0, 1] K and p t ∈ [0, 1] K . Since the step b) above can also be performed sequentially, the total storage complexity is O(K).

Substituting η and these upper-bounds in the regret upper-bound concludes the proof:

As for the complexity, the only difference with Alg. 1 comes from the computation of qt (i). The latter can also be performed with a computational cost of O(tK). Yet, the algorithm needs to keep in memory the empirical distribution of S 1 , . . . , S t . Thus, a space complexity of O(K + min{tK, 2 K }).


Andrianasolo Fety

f.andrianasolo@arvalis.fr Deswarte Jean-Charles

Jorant Amaury

Developing a mechanistic foliar stage model adapted to wheat diseases decision tools

published or not. The documents may come

Developing a mechanistic foliar stage model adapted to wheat diseases decision tools

Fety Andrianasolo, Jean-Charles Deswarte, Amaury Jorant

Introduction

Phenological stages are widely used in crop models as starting points for most processes based on leaf, biomass and yield growth. In soft wheat in particular, the appearance of the last leaf on the main shoot is a mandatory stage for crop protection strategy, since this stage alone, contributes to up to half of the carbon allocated to the grain. We propose to build a mechanistic model for simulating flag leaf appearance stage (FLAS) in soft wheat, consisting in three main steps ; (1) estimation of floral transition stage, that we assumed to be the stage corresponding to the moment when primordia are determined as future spikelets or leaves ; (2) computation of a dynamic phylochron along crop cycle, based on photoperiod and thermal time scales ; and (3) calculation of all leaf stages from pre-formed primordia to the last leaf to appear (FLAS).

Materials and Methods

This model was constructed using agronomic trials data, located in 53 sites in France and more than 20 years of experiments (+ 200 varieties), for floral transition stage, final leaf number and FLAS calibration and evaluation ; another database composed of regular leaf counts (Villiers-le-Bâcle, 2005 to 2016, France) was used for phylochron optimization. Cross-validation per year was carried out on both datasets, and indicators of error of prediction (RMSEP) and model efficiency (EF) were computed.

Results and Discussion

Results showed that the global error of the model was 5.9 days (EF = 0.6) (Figure 1). Adjusted mean value of phylochron was lower than those found in literature (90 versus 100 to 130 degrees-days per leaf respectively). There was likely a compensation phenomenon between overestimated floral transition date and underestimated final leaf number (compared to literature) ; nonetheless, these could neither be measured nor evaluated in the data we used. We discuss the potential of our approach compared to other existing leaf stage models in the context of crop protection and system decision tool usage.

Conclusions

Our newly phylochron-based soft wheat model provided similar predictive performance as compared to existing models, and could be further enriched with nitrogen and water stress effects for optimizing crop protection decisions.

Figure 1 .

 1 Figure 1. Comparison of observed and simulated dates of flag leaf appearance stage (FLAS) in soft wheat Keywords: floral transition, phylochron, photoperiod, final leaf number, soft wheat.


Andrianasolo Fety

f.andrianasolo@arvalis.fr Deswarte Jean-Charles

Garcia Cécile

Predicting wheat yield and protein content at the plot scale with machine-learning and mechanistic models

published or not. The documents may come

Predicting wheat yield and protein content at the plot scale with machine-learning and mechanistic models

Fety Andrianasolo, Jean-Charles Deswarte, Cécile

Introduction

Providing the earliest reliable model predictions of crop production is of a major interest since it allows to optimize crop management and strategic positioning in the market. For wheat in particular, the recurrence of drought episodes due to climate change and variability challenges crop models on their ability to take into account genotype x environment effects at the plot scale.

Materials and Methods

Three yield component-based models were proposed to predict the grain number, grain weight and protein content respectively, for soft and durum wheat. These models were calibrated on historical database of field experiments conducted at plot scale (from 1996 to 2016), on more than 50 varieties and 40 sites in France. Models simulating grain number and protein content took into account varietal effects, agro-climatic indicators (e.g water stress and photothermal quotient around heading) and variables describing canopy state (nitrogen nutrition index, aboveground biomass) by the use of random forest methods. Grain weight model corresponded to a logistic curve describing the needs in temperatures (degree-days) of each variety, modulated by daily temperature, radiation and water stress effects during grain filling. Models were calibrated using indicators such as model efficiency, bias, and relative root mean squared error (RRMSE).

Results and Discussion

The models calibration results are illustrated in Figure 1. They were further evaluated on an independant dataset with very promising performances (relative error of 15% and 8%) for yield and proteins, respectively. Models highlighted differential varietal response to water stress between soft and durum wheat. These models will be soon deployed as part of a decision support tool, which combines the use of a dynamic crop model (CHN model) and LAI sensor data used to readjust model predictions during the campaign.

Conclusions

Based on this study, the combination of machine learning and mechanistic models appears to be a promising way for simulating wheat yield and protein at plot scale. Keywords: wheat yield, random forest, logistic, water deficit, CHN crop model.

Figure 1 .

 1 Figure 1. Results of wheat yield components model calibration (Grain number, grain weight, yield and protein content at harvest).


Crystèle Léauthaud

Laurent Kergoat

Pierre Hiernaux

Manuela Grippa

Winfred Musila

Stéphanie Duvail

Jean Albergel

Modelling floodplain grasslands to explore the impact of changing hydrological conditions on vegetation productivity

come   L'archive ouverte pluridisciplinaire

Modelling floodplain grasslands to explore the impact of changing hydrological conditions on vegetation productivity

Leauthaud Crystele 1 (crystele.leauthaud@cirad.fr), Kergoat Laurent 2 , Hiernaux Pierre 3 , Grippa Manuela 4 , Musila Winfred 5 , Duvail Stéphanie 6 , Albergel Jean 7 1 G-eau, Cirad, Montpellier, France; 2 Géosciences Environnement Toulouse, CNRS, Toulouse, France; 3 Pastoralisme Conseil, Caylus, France; 4 CNRS, Toulouse, France; 5 Kenya Water Towers Agency, Nairobi, Kenya; 6 IRD, Paris, France; 7 IRD, Montpellier, France This study (i) presents a coupled vegetation-soil model adapted to perennial C4 seasonally flooded semi-arid grasslands; and (ii) applies the model to evaluate changes in the annual productivity of the grasslands of the Tana River Delta, Kenya, under changing flooding conditions. Main plant growth processes are modelled within coupled plant carbon balance and soil water budget modules: photosynthesis, allocation of photosynthates, respiration, translocation of root phytomass to aerial phytomass, senescence and litter production. Aerial phytomass can also be subtracted from the system, to simulate grazing or cutting. New features concern the inclusion of effects of floods on energy conversion efficiency, photosynthate allocation, senescence and litter production. The vegetation model, composed of four phytomass compartments (leaves, stems, roots, aerial dead matter), simulates three main growth phases related to flooding: floods, a post-flood phase and a non-flooded phase. It was designed to be used with limited climatic data. Data collected during a 14-month experiment (2010)(2011)(2012) in the Tana River Delta, Kenya, in which different irrigation and cutting treatments and flood events were recorded, were used for calibration and validation purposes. Fourteen parameters, selected through a sensitivity analysis, were calibrated on half of these treatments. Uncertainty in parameter estimation was expressed through a stochastic ensemble of simulations. The remaining independent data were used for model validation. Overall, the model predictions are in good agreement with the experimental data. This model can be used to assess the impact of rain variability, grazing or flooding patterns on the annual primary productivity of Sub-Saharan floodplain grasslands composed mainly of Echinochloa stagnina (Retz) P. Beauv. In particular, simulations for the Tana River Delta suggest that past changes in the hydrological regime of the river, as well as future changes due to the construction of hydroelectric infrastructure, have led and will certainly lead to an important decrease of the floodplain grassland productivity. As local and regional livestock keeping activities rely heavily on the dry seasons' grazing resources available within the wetland, future development plans should seriously consider the negative effects of these changes on local activities and livelihoods. This presentation results from a publication in Ecological Modelling: https://doi.org/10.1016/j. ecolmodel.2018.09.015 Keywords: Echinochloa stagnina (Retz) P. Beauv., plant growth model, floodplains, Tana River Delta, Kenya.

References:

1. Leauthaud, C., Kergoat, L., Hiernaux, P., Grippa, M., Musila, W., Duvail, S., & Albergel, J. (2018). Modelling the growth of floodplain grasslands to explore the impact of changing hydrological conditions on vegetation productivity. Ecological modelling, 387, 220-237. 2. Leauthaud, C., Hiernaux, P., Musila, W., Kergoat, L., Grippa, M., Duvail, S., .

Modelling of drought stress in field crops by crop growth model DAISY

  .. & Rode, N. O. (2019). Influence of floods and growth duration on the productivity of wet grasslands of Echinochloa stagnina (Retz) P. Beauv. in an East African Floodplain. Wetlands, 1-10. https://doi.org/10.1007/s13157-019-01148-9. 3. Leauthaud, C., Belaud, G., Duvail, S., Moussa, R., Grunberger, O., & Albergel, J. (2013). Characterizing floods in the poorly gauged wetlands of the Tana River Delta, Kenya, using a water balance model and satellite data. Hydrology and Earth System Sciences, 17(8), p-3059. 4. Leauthaud, C., Duvail, S., Hamerlynck, O., Paul, J. L., Cochet, H., Nyunja, J., ... & Grünberger, O. (2013). Floods and livelihoods: The impact of changing water resources on wetland agro-ecological production systems in the Tana River Delta, Kenya. Global environmental change, 23(1), 252-263.

  Pohanková Eva 1 (Eva.Pohankova@seznam.cz), Hlavinka Petr 2 , Takáč Jozef 3 , Bednařík Martin 2 , Trnka Miroslav 4 1 Department of Climate Change Impacts, Global Change Research Institute CAS, Brno, Česká republika, Czech Republic; 2 Department of Climate Change Impacts, Global Change Research Institute CAS, Brno, Czech Republic; 3 Soil Science and Conservation Research I, Bratislava, Slovakia; 4 Department of Climate Change Impacts on, Global Change Research Institute CAS, Brno, Czech RepublicThe field experiment with rain-out shelters for precipitation reduction was established in Bohemian-Moravian highlands (Domanínek experimental station, 49°31'42»N, 16°14'13»E, altitude 560 m) in 2014. The purpose of this field experiment is to gather sufficient data for modelling the crop's response to the climatic conditions expected in the future, in this case drought stress. Winter wheat and spring barley are the most widely grown cereals in the Czech Republic. The main aim of this study was evaluate a drought stress effect on winter wheat (cultivar Bohemia) and spring barley (cultivar Bojos). At the same time the ability of crop model DAISY to simulate drought stress response was tested. The monitored parameters were development, grain yield and soil moisture on two growth seasons (2017/2018 and 2018/2019) for two experimental variants with three repetitions in each crops (the first variant = natural climatic conditions; the second variant = drought stress is induced using the mobile rain-out shelters made of corrugated clear polycarbonate material and installed in the crop canopy). In each variant were sensors TDR (time domain reflectometry, CS 616, Campbell Scientifi c Inc., Shepshed, UK) to measure the soil water content placed vertically to monitor the soil water content from the surface to a depth of 30 cm. Observed and measured parameters such as terms of phenological phases, soil moisture and grain yields were compared with modelled data. The simulation results with respect to the phenological phase of flowering/maturity showed a slight deviation from the observations, from +3/-1 to -3/+1 days for winter wheat and -6/-2 to +5/+1 days for spring barley. The precipitation was reduced during the growth season. A reduction of precipitation by 138,2 mm and 203,8 mm for winter wheat 2018 and 2019 and a reduction of precipitation by 87,6 mm and 102,2 mm for spring barley 2018 and 2019, led to decrease in grain yields. Grain yield for winter wheat/spring barley decreased from 7.43 /4.97 t/ha (natural climatic conditions) to 4.19/3.70 t/ha (drought stress was induced using the rain-out shelters) in 2018 and from 6.72/6.12 t/ha to 4.99/4.44 t/ha in 2019. The results of this study showed that the crop model DAISY relatively satisfactorily simulates the main feature soil water content dynamics as measured by TRD sensors in 2018 and 2019 and reproduce the drought stress for crop yields of winter wheat and spring barley to a certain extent. The crop model DAISY simulated the movement of soil water based on the numerical solution of Richards' equation. The decrease in the simulated grain yield after precipitation reduction is obvious. The simulation results for winter wheat/spring barley grain yield in natural climatic conditions were 8.04/3.98 t / ha in 2018 and 8.01/6.12 t/ha in 2019. The simulation results for winter wheat/spring barley grain yield in drought stress were 4.42/2.54 t/ha in 2018 and 4.40/4.20 t/ha in 2019. When rain-out shelters were used, real winter wheat/spring barley grain yields were reduced by 3.24/1.27 t/ha in 2018 and by 1.73/1.68 t/ha in 2019. The model underestimated the yields of winter wheat/spring barley for the sheltered variant by 3.62/1.44 t/ha in 2018 and by 3.61/1.92 t/ha in 2019. The study and contribution was funded through SustES -Adaptation strategies for sustainable ecosystem services and food security under adverse environmental conditions" project no. CZ.02.1.01/0.0/0.0/16_019/0000797.

…/…


Ruelle Elodie

( Elodie Ruelle

Delaby Luc

Hennessy Deirdre

Predicting grass growth: The MoSt GG model

Introduction

PastureBase Ireland (PBI - [START_REF] Hanrahan | PastureBase Ireland: A grassland decision support system and national database[END_REF]) is a grassland management tool for farmers. PBI helps farmers to manage the grass on their farm, identify grass supply surpluses or deficits and to take appropriate action. However, currently within PBI farmer can only make decisions based on historical information. The incorporation of a predictive model within PBI such as the MoSt GG [START_REF] Ruelle | Development of the Moorepark St Gilles grass growth model (MoSt GG model): a predictive model for grass growth for pasture based systems[END_REF] would allow farmer to get information on the future growth of their farm. And help to facilitate anticipation and improve decision making.

Materials and Methods

The MoSt GG model [START_REF] Ruelle | Development of the Moorepark St Gilles grass growth model (MoSt GG model): a predictive model for grass growth for pasture based systems[END_REF]) is a dynamic model developed in C++ describing the grass growth and the nitrogen (N) and water fluxes of a paddock. The model is run with a daily time step simulating soil N mineralisation, immobilisation and water balance, grass growth, N uptake and grass N content. The model is driven by a daily potential growth depending on the radiation and the total green biomass. To calculate the actual daily growth, this potential growth is then multiplied by parameters depending on environmental conditions (temperature, water in the soil and radiation) and a parameter depending on the availability of the mineral N in the soil compared to the N demand associated with the potential grass growth. Animal depositions of N from dung and urine are also separately represented by the model. The main inputs of the model are the soil type (% sand and clay, organic matter and soil mineral N content), the weather (temperature, rainfall and solar radiation) and paddock management (fertilisation, grazing and cutting). The MoSt GG model was evaluated using experimental data for 2013-2018 from three Teagasc experimental farms -Ballyhaise, Clonakilty and Curtins in Ireland.

Results and Discussion

Overall the model showed a similar accuracy across the three farms. The accuracy at the paddock level with RMSE of between 27 (Curtins 2018) to 31.7 kg DM/ha day (Ballyhaise 2014) is quite poor, however the accuracy at the farm level of between 11.5 (Ballyhaise 2015) to 17.9 kg DM/ha/day (Clonakilty 2016) is quite promising. The Figure 1 presents the simulated and recorded growth during two contrasting years. Since February 2019 the model is being used to predict grass growth on 40 farms across Ireland. The farms are representative of the soil type and geographic variability of Ireland. Historical and forecast weather data is provided for each individual farm by Met Éireann, the Irish Meteorological Service. Information about N fertiliser and grazing and cutting events are entered weekly by the farmer in to PBI. The weekly grass growth is communicated to farmers involved in the pilot study in the form of a map sent to the farmers on a Tuesdays. The feedback from the farm managers is very positive, and the farmers consider the predictions are very useful aids to decision making and help to be more confident.

Conclusion

The MoSt GG model is a mechanistic model developed for both research and farmer use. The initial evaluation indicates that the model is capable of adapting to differences in farm and in weather conditions. The pilot study currently on-going will provide a true indication of the MoSt GG model's ability to provide useful grass growth prediction across soil types, regions and management conditions. If the pilot study is successful, and the accuracy of the model is sufficient across the different farms, the model will be integrated into PBI.

  2015, RMSE 13.8 kg DM/ha, CCC 0.89 Right Ballyhaise 2013, RMSE 12.0 kg DM/ha, CCC 0.90 Figure 1: Comparison between the growths recorded in PBI (grey) and predicted by the MoSt model (black) for two contracting years in two contrasting farms.


Juan Zamora
email: juan.zamora@pucv.cl

Jérémie Sublime
email: jeremie.sublime@isep.fr

A new Information theory based clustering fusion method for multi-view representations of text documents

Keywords: Multi-view Clustering, Information theory, Corpus Analysis

Multi-view clustering is a complex problem that consists in extracting partitions from multiple representations of the same objects. In text mining and natural language processing, such views may come in the form of word frequencies, topic based representations and many other possible encoding forms coming from various vector space model algorithms. From there, in this paper we propose a clustering fusion algorithm that takes clustering results acquired from multiple vector space models of given documents, and merges them into a single partition. Our fusion method relies on an information theory model based on Kolmogorov complexity that was previously used for collaborative clustering applications. We apply our algorithm to different text corpuses frequently used in the literature with results that we find to be very satisfying.

Introduction

The goal of text corpus clustering is to partition a collection of text documents into several groups, such that texts inside the same groups (or clusters) are similar and share common themes or have a common style, while documents in different clusters are very distinct in nature. To achieve this goal, text documents must first be transformed using models such as the Vector Space Model (VSM) [START_REF] Salton | A vector space model for automatic indexing[END_REF] in order to transform the original documents into numerical vectors that can be used by clustering algorithms such as K-Means or hierarchical clustering. One difficulty with the VSM model is the large number of existing methods to transform text documents into vector representations. Many representation models exist, some are topic oriented, others focus on word embedding, while some methods are purely statistical representations. This abundance of methods in the literature allows for multiple vector representations of the same texts, all with different strengths and weaknesses. Applying clustering algorithms to these multiple representations can be seen as a multi-view clustering problem where the goal could be to find a consensus between the clustering partitions proposed under the various Vector Space Models [START_REF] Fraj | Ensemble method for multi-view text clustering[END_REF]. Within this context, in this paper we propose a new method inspired from collaborative clustering, and which relies on the notion of Kolmogorov complexity to merge clustering partitions acquired from the clustering algorithms applied to different vector representations of text documents. Our proposed method is compared with state of the art methods applied to common text corpuses that can be found in the literature.

The remainder of this paper is organized as follows: Section 2 focuses on various related works about both text mining and the information theory model used in this paper. Section 3 presents our algorithm. Section 4 features our experimental results and some comparisons with other methods. Finally, in section 5 we draw some conclusion and give some ideas on possible extensions of this work.

State of the art

Cluster ensembles is an overall framework in which multiple partitions are combined in order to obtain a consensus clustering. Multi-view clustering is one of the specific problems covered in this area [START_REF] Ghosh | Cluster ensembles[END_REF].

The problem of combining multiple data partitions into a single one has been tackled at least by two approaches, namely Clustering Ensembles [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF][START_REF] Li | On combining multiple clusterings[END_REF]4,[START_REF] Topchy | Clustering ensembles: Models of consensus and weak partitions[END_REF][START_REF] Yi | Robust ensemble clustering by matrix completion[END_REF][START_REF] Wu | K-means-based consensus clustering: A unified view[END_REF][START_REF] Liu | Entropy-based consensus clustering for patient stratification[END_REF][START_REF] Rashidi | Diversity based cluster weighting in cluster ensemble: an information theory approach[END_REF] and Multi-View Clustering [START_REF] Janssens | Dynamic hybrid clustering of bioinformatics by incorporating text mining and citation analysis[END_REF][START_REF] Liu | Hybrid clustering of text mining and bibliometrics applied to journal sets[END_REF][START_REF] Greene | A matrix factorization approach for integrating multiple data views[END_REF][START_REF] Yu | Clustering by heterogeneous data fusion: framework and applications[END_REF][START_REF] Liu | Hybrid clustering of multi-view data via tucker-2 model and its application[END_REF][START_REF] Liu | Multiview partitioning via tensor methods[END_REF][START_REF] Xie | Multi-view clustering ensembles[END_REF][START_REF] Romeo | Semantic-based multilingual document clustering via tensor modeling[END_REF][START_REF] Hussain | Multi-view document clustering via ensemble method[END_REF][START_REF] Fraj | Ensemble method for multi-view text clustering[END_REF], also known as data fusion.

In ensemble learning and ensemble clustering, several algorithms will work on the same data set with the goal of achieving a single result that should be better that the partitions learned from the different algorithms. As one can see, in ensemble clustering, several algorithms work on the same data and therefore the same view. However, in the case of multi-view clustering like in the present work, we have several algorithms and each of them works in a different view of the same data. And since we are dealing with several views, the goal with multi-view clustering is to merge them while taking into considerations that there might be multiple truths [START_REF] Zimek | The blind men and the elephant: on meeting the problem of multiple truths in data from clustering and pattern mining perspectives[END_REF].

It is worth mentioning, that the distinction between ensemble clustering and multi-view clustering is not always obvious in the literature and some confusion may exist with different naming conventions depending on the field of application. In the following subsection, we make a quick review of the literature for both multi-view and ensemble clustering with a particular focus on text mining applications and methods that are close to the one presented in this work.

State of the art on combining multiple clustering partitions

There are many different applications that require to combine multiple clustering partitions: In [START_REF] Li | On combining multiple clusterings[END_REF], the authors make a proposal for music clustering using partitions obtained from different music feature sets. Among these sets, they employ several word-level features. They pose the ensemble clustering problem as a binary clustering in a space induced by the multiple partitions. Additionally, they explore various optimization criteria for finding consensus partitions and propose a strategy for determining the final number of clusters. It is interesting to note that they apply this proposal for In [START_REF] Hussain | Multi-view document clustering via ensemble method[END_REF], the authors work specifically on text clustering. They propose to generate several partitions from each view by using different feature representations and then applying a clustering algorithm over each one. Then, similarity matrices are computed in three different ways, namely two based on partition memberships and another one based on feature similarity. Finally, a combined similarity matrix is obtained from those three previous ones and a standard clustering technique is applied to produce the consensus partition. In the same direction, [START_REF] Fraj | Ensemble method for multi-view text clustering[END_REF] use more diverse text representations as views, more specifically LDA [START_REF] Blei | Latent dirichlet allocation[END_REF], Word2Vec [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF] and TF-IDF [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF] and then apply the same idea as the former work.

It is woth noting that multi-view text clustering shouldn't be confused with distributed clustering of texts [START_REF] Zamora | Distributed clustering of text collections[END_REF], which mainly consists in distributing the clustering task without consideration for whether or not this is a multi-view task.

Another common application of multi-view clustering is multilingual clustering. In [START_REF] Romeo | Semantic-based multilingual document clustering via tensor modeling[END_REF], for this specific application, the authors pose the multi-view clustering problem as a tensor decomposition as this approach was proven earlier to be theoretically efficient [START_REF] Liu | Hybrid clustering of multi-view data via tucker-2 model and its application[END_REF][START_REF] Liu | Multiview partitioning via tensor methods[END_REF].

Methods to combine multiple partitions

In [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF], the authors pose that an application of Cluster Ensembles is to combine partitions obtained from partial sets of features. As we have seen earlier, this is a case of multi-view clustering. Additionally, they pose that a motivation for using a cluster ensemble is to build a more robust solution that performs well over a wide range of data sets. Since the diversity of base partitions has a positive impact on the final consensus solution, it can be introduced mainly by using different sets of features in each partition, different parameter configurations of the same algorithm (values of k for k-means) and also using different and complementary base techniques. The authors also formulate consensus clustering as a hyper-graph cutting problem and solve in three different ways.

Co-association matrices are based on relative co-occurrence of two data points in the same cluster. They are another very common tool to tackle multi-view clustering. Several works exploit them in order to produce final partitions from several combinations of different data representations. [4] explore two strategies for producing cluster ensembles: Using different views and using different clustering algorithms or parameter configurations. [START_REF] Yi | Robust ensemble clustering by matrix completion[END_REF] address the problem from a similarity matrix completion problem in which missing values are associated to uncertain data pairs, this is pair of data points whose common membership in every partition is not consistent. In the same path, [START_REF] Rashidi | Diversity based cluster weighting in cluster ensemble: an information theory approach[END_REF] propose to weight the contribution of each co-association matrix based on a novel reliability measure of each partition within the ensemble. Some other contributions employ an utility function to measure similarity between partitions and then directly maximize an objective function to obtain the consensus [START_REF] Topchy | Clustering ensembles: Models of consensus and weak partitions[END_REF][START_REF] Wu | K-means-based consensus clustering: A unified view[END_REF][START_REF] Liu | Entropy-based consensus clustering for patient stratification[END_REF].

In [START_REF] Janssens | Dynamic hybrid clustering of bioinformatics by incorporating text mining and citation analysis[END_REF], a hybrid clustering method based on weighted linear combination of distance matrices for textual and bibliometric information is proposed.

Multi-view clustering applications and Kolmogorov complexity

In the work of [START_REF] Rissanen | Modeling by shortest data description[END_REF] [START_REF] Wallace | An information measure for classification[END_REF], the notion of minimum description length (MDL) is introduced, with the description length being the minimal number of bits needed by a Turing Machine to describe an object. This measure of the minimal number of bits is also known under the name Kolmogorov complexity.

If M is a fixed Turing machine, the complexity of an object x given another object y using the machine M is defined as K M (x|y) = min p∈P M {l(p) : p(y) = x} where P M is the set of programs on M, p(y) designates the output of program p with argument y and l measures the length (in bits) of a program. When the argument y is empty, we use the notation K M (x) and call this quantity the complexity of x. The main problem with this definition is that the complexity depends on a fixed Turing machine M. Furthermore, the universal complexity is not computable, since it is defined as a minimum over all programs of all machines.

In relation with this work, in [START_REF] Murena | An information theory based approach to multisource clustering[END_REF], the authors solved the aforementioned problem by using a fixed Turing Machine before applying this notion of Kolmogorov complexity to collaborative clustering, which is a specific case of multiview clustering where several clustering algorithms work together in a multi-view context but aim at improving each other partitions rather than merging them [START_REF] Cornuéjols | Collaborative clustering: Why, when, what and how[END_REF]. While collaborative clustering does not aim at a consensus, this application is still very close to what we try to achieve in this paper where we try to merge partitions of the same objects under multiple representations. For these reasons, we decided to use the same tool.

In the rest of this paper, just as the authors did in [START_REF] Murena | An information theory based approach to multisource clustering[END_REF], we will consider that the Turing Machine M is fixed, and to make the equations easier we will denote by K(x) the complexity of x on the chosen machine. Then, we adapt the equations used in their original paper to our multi-view context for text mining and we use Kolmogorov complexity as a tool to compute the complexity of one partition given another partition. The algorithm to do so and how we use it is described in the next section.

3 Proposed merging method

Problem definition

Let us consider a data set X of n data points and a measure of similarity S that allows to quantify the strength of the connection or closeness between any pair of data points in X . The problem of data clustering can be stated as inducing an equivalence relation4 on X such that points a, b in the same equivalence class (that is a cluster) have a larger similarity value S(a, b) in comparison with S(a, c) or S(b, c) for any other point c in a different equivalence class.

The Multi-view clustering task considers that the information regarding to each data point in X comes from multiple sources called views. After performing a clustering algorithm over each view several partitions are generated. Let us define this set of partitions as P, and denote each of them with a capital letter (e.g.: A).

A partition A is a set of |A| disjoint sets c ∈ ℘ (X ) (the Power set of X )
called clusters of X . Let us define an agreement function Ω between two clusters as a mapping Ω : ℘ (X ) × ℘ (X ) → [0, 1] which attains lower values for clusters having a smaller overlap and higher values for clusters sharing more elements of X . In this work we employ the Jaccard similarity function to measure agreement between two clusters.

For a point p ∈ X , its cluster in any partition A ∈ P is denoted by N A p and it is defined as:

N A p = {x ∈ X |∃c ∈ A ∧ p ∈ c ∧ x ∈ c}
Given a cluster c and a partition B the function that maps c to the cluster in B with the largest overlap is called maximum agreement function and it is defined as follows:

Φ B (c) = argmax e∈B Ω(c, e) (1)

The Algorithm

Our goal in this paper is to combine several partitions in order to build a final consensus. To this end, in our method we perform successive pairwise fusion procedures between partitions following a bottom-up strategy until we reach a single partition. This procedure is depicted in Algorithm 1. Without loss of generality, when a fusion step is performed between two partitions A and B , a new partition C is created. Since the successive partition fusions are performed by following the maximum agreement criteria between clusters as stated in Eq. ( 1), it is possible that some data points do not fit to this rule and hence be marked as exceptions during the execution of the merge operation. The set of data points marked as exceptions before the creation of partition C is denoted by ξ C , formally,

ξ C = {p ∈ X |N A p ∩ Φ B (N A p ) = ∅ ∪ N B p ∩ Φ A (N B p ) = ∅} (2)
Thus, when partition C is created, each point p ∈ ξ C receives a weight W C (p, c) for every cluster c ∈ C . This weight is made up by the relative weights that both source partitions A and B contribute, namely ω A (p, c) and ω B (p, c). Without loss of generality, the contribution of each source partition is given by:

ω A (p, c) = Ω(c, N A p ) if p / ∈ ξ A Ω(c, Φ A (c)) • W A (p, Φ A (c)) if p ∈ ξ A (3)
Thus, the final weight W C (p, c) for each point p ∈ ξ C in each cluster c ∈ C is given by:

W C (p, c) = ω A (p, c) 2 + ω B (p, c) 2
A more detailed description of this merging process is depicted in Algorithm 2. It is important to indicate that once a point is marked as an exception, it remains so through all the subsequent fusions. After the last fusion, each of these exception data points are assigned to one of the final clusters by picking the one whose membership weight is the highest. This exception resolution is described between lines 7 -9 in Algorithm 1 where K(A|B) is the kolmogorov complexity of partition A knowing partition B [START_REF] Murena | An information theory based approach to multisource clustering[END_REF]:

K(A|B) = K B × (log K A + log K B ) + |ξ C | × (log n + log K A ) (4)
with n the total number of points, K A the number of clusters in partition A, K B the number of clusters in partition B and ξ C the set of exceptions between partitions A and B as defined in Equation (2).

Algorithm 1: Main procedure for building the consensus partition.

Input: A set P of m partitions over the data X . Output: A consensus partition.

1 Q ← [] /* exceptions after each merge operation */ 2 while |P| > 1 do 3 A, B ← argmin A * ,B * ∈P K(A * |B * ) + K(B * |A * ) 4 C ← merge(A, B , Q, W )

Experimental settings

Since external class labels are available for each data set, let us consider the true clustering T and the final partition obtained by the clustering algorithm as C . Then, two measures are employed to assess the quality of a clustering solution, namely Entropy and Purity. Entropy is defined in two parts: the former allows to measure the Entropy for a single partition and it is characterized for any partition c ∈ C in equation ( 5). The latter is just a weighted average of the entropy computed for all the partitions in the final solution and it is defined in equation [START_REF] Greene | A matrix factorization approach for integrating multiple data views[END_REF]. Purity is defined in a similar way, that is first the Purity of a single partition is defined in equation ( 7) and then, the overall Purity of the partition is denoted as equation [START_REF] Janssens | Dynamic hybrid clustering of bioinformatics by incorporating text mining and citation analysis[END_REF].

E(c) = - 1 log |T | t∈T |c ∩ t| |c| log |c ∩ t| |c| (5)
Entropy(C ) = c∈C |c| n E(c) (6)
P(c) = 1 |c| max t∈T |c ∩ t| (7)
Purity(C ) = c∈C |c| n P(c) (8)
Entropy measures the degree in which the true classes are dispersed within each cluster. A good solution is the one that does not break the true clusters into too many parts. Purity is targeted to measure the extent to which each cluster contains documents from mostly a single true class. Thus, a good solution should present homogeneous clusters in terms of the true classes of the contained documents.

Since the quality of the overall solution depends on the initial source k-Means clusterings, which in turn have a random nature, we follow the scheme presented in [START_REF] Zhao | Criterion functions for document clustering: Experiments and analysis[END_REF] to eliminate some of this sensitivity in the performance assessment. This is, we use several values for k and for each specific value, the overall clustering procedure is repeated 10 times and the best performance solution is kept. Additionally, since partition quality improves as the number of clusters increases, relative performances are reported for each clustering solution. To compute the relative entropy, we divide the entropy attained by a particular solution by the smallest entropy for that particular data set and value of k. In case of relative purity and in order to allow the same interpretation of the relative entropy, we divide the best Purity attained for that particular data set and value of k by the entropy value obtained by the clustering solution under evaluation. Since these two ratios represent the extent to which a specific algorithm performed worse than the best algorithm, for each dataset better solutions are closer to 1.0 and they are worse as the become greater then 1.0. Finally, as a performance summary for each solution the average relative performance across all data sets are reported for each clustering solution.

Results and interpretations

The result tables 2,1, 4 and 3 show the relative performances attained by the proposal, each source clustering and another ensemble method recently proposed in [START_REF] Fraj | Ensemble method for multi-view text clustering[END_REF]. As we can see from Table 1 and Table 2, the results on the relative entropy show that our proposed method achieves significantly better results than the method of Fraj et al. [START_REF] Fraj | Ensemble method for multi-view text clustering[END_REF] on the same data sets.

Going more into details, from Table 2 we can see that overall the TFIDF first and the LDA view second have the best results in term en entropy and are used as baseline for the relative entropy. We can see that for many data set our proposed method not only is close from the best entropy result, but that it achieves better results on average than the 3 original lda, skipgram and tfidf views, and always better results than the method from Fraj et al.

Since each view may hold its own truth, it is only logical that we rarely achieve fusion results that are better than all original view. This is a common problem in multi-view clustering [START_REF] Zimek | The blind men and the elephant: on meeting the problem of multiple truths in data from clustering and pattern mining perspectives[END_REF] and should be considered as normal. Regardless, it is worth mentioning that our proposed method still achieves the best results in the case of the BBCSport data set with 15 clusters in terms of relative entropy. From Table 3 and 4, we can see that the results in term of purity are the same than the one we had with entropy, thus enabling us to affirm that our proposed method proved superior than the one of Fraj et al. on all data sets regardless of the number of clusters.

Like for entropy, we can see that we rarely achieve the best results among views, but that we still do better than the average of the 3 original views, and from Table 3 we can see that our algorithm remains very competitive even when compare to the best view.

The best performances of our proposed algorithm for relative purity are for the BBCSport data set with 15 clusters, Reuters-R8 with 15 clusters and Web-bKB with 10 clusters. For all 3 cases, we not only get better results than other methods in the literature, but we also do better than the best views in term of relative purity.

Conclusion and future works

We have presented a new clustering fusion method applied to the case of multiview text corpus clustering. Our method was applied to 4 data sets that are very common in the literature (20Newsgroup, Reutors-R8, WebKB and BBCSport) and has proved to be competitive with state of the art methods. Unlike previously proposed methods, our algorithm relies on the notion of Kolmogorov complexity and information compression thus giving it a solid theoretical background on how to best fusion the clustering partitions.

In our future works, we plan on coupling our proposed method with existing collaborative method so that we could have a collaborative step first, and a merging step then. We hope that doing so may help to detect incompatible or noisy views, but could also ease the merging process by creating closer partition with collaborative clustering before hand. Other possible extensions of this work include applications on merging multi-view clustering partitions in fields other than text mining and natural language processing.

5 add C into P 6 removeAlgorithm 2 : 12 a ← a 13 a 14 b

 562121314 A, B from P /* Solving points marked in last item from Q */ 7 ξD ←last partition's exceptions added to Q 8 foreach p ∈ ξD do 9 Merge procedure that fuses two partitions into a new one identifying also troublesome points as exceptions. Input: Partitions A, B ∈ P s.t. |A| > |B | 1 , list with previous merge exceptions Q and weight function for previously created partitions W Output: New partition C and a set of marked points along with their scores ∀c ∈ C . 2 M ← [] 3 foreach a ∈ A do 4 add ΦB (a) into M[a] 5 foreach b ∈ B do /* b can be associated to more than one cluster in A */ 6 add b into M[ΦA(b)] 7 C ← ∅ /* The new partition to be returned */ 8 foreach a ∈ A do 9 c ← ∅ 10 foreach b ∈ M[a] do 11 c ← c ∪ (a ∩ b) ← ab /* updates cluster a */ ← ba /* updates cluster b */ 15 add c into C /* generating the list of marked points by the current fusion */ 16 ξC ← ∅ foreach a ∈ A do 17 if |a| > 0 then 18 add each p ∈ a into ξC 19 foreach b ∈ M[a] s.t. |b| > 0 do 20 add each p ∈ b into ξC 21 add ξC into Q 22 foreach p ∈ ξC and c ∈ C do 23 WC (p, c) = ωA(p, c)

Table 2 .

 2 Relative entropy

	k lda skipgram tfidf	fraj proposal
	5 1.737 1.509	1.031 2.271 1.075
	10 1.565 1.447 1.019 2.045 1.074
	15 1.727 1.453 1.021 2.239 1.057
	Table 1. Average relative entropy
	k dataset	lda skipgram tfidf fraj proposal
	5 WebKB	1.000 1.111 1.008 1.289 1.012
	5 20Newsgroup 1.306 1.256 1.000 1.813 1.116
	5 BBCSport	3.641 1.948 1.000 4.397 1.144
	5 Reuters-R8 1.000 1.722 1.116 1.586 1.028
	10 WebKB	1.000 1.216 1.074 1.256 1.021
	10 20Newsgroup 1.147 1.310 1.000 1.653 1.023
	10 BBCSport	3.105 1.628 1.000 3.541 1.191
	10 Reuters-R8 1.010 1.632 1.000 1.727 1.059
	15 WebKB	1.000 1.246 1.082 1.282 1.012
	15 20Newsgroup 1.210 1.375 1.000 1.784 1.205
	15 BBCSport	3.689 1.642 1.000 4.185 1.000
	15 Reuters-R8 1.009 1.548 1.000 1.707 1.010

For the clustering task, the relation could be stated as "has the same label as".