Mohammad Gheshlaghi Azar
email: mazar@cs.cmu.edu

Alessandro Lazaric
email: alessandro.lazaric@inria.fr

Emma Brunskill

Sequential Transfer in Multi-armed Bandit with Finite Set of Models

Learning from prior tasks and transferring that experience to improve future performance is critical for building lifelong learning agents. Although results in supervised and reinforcement learning show that transfer may significantly improve the learning performance, most of the literature on transfer is focused on batch learning tasks. In this paper we study the problem of sequential transfer in online learning, notably in the multi-armed bandit framework, where the objective is to minimize the total regret over a sequence of tasks by transferring knowledge from prior tasks. We introduce a novel bandit algorithm based on a method-of-moments approach for estimating the possible tasks and derive regret bounds for it.

Introduction

Learning from prior tasks and transferring that experience to improve future performance is a key aspect of intelligence, and is critical for building lifelong learning agents. Recently, multi-task and transfer learning received much attention in the supervised and reinforcement learning (RL) setting with both empirical and theoretical encouraging results (see recent surveys by [START_REF] Pan | A survey on transfer learning[END_REF][START_REF] Lazaric | Transfer in reinforcement learning: a framework and a survey[END_REF]. Most of these works focused on scenarios where the tasks are batch learning problems, in which a training set is directly provided to the learner. On the other hand, the online learning setting [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], where the learner is presented with samples in a sequential fashion, has been rarely considered (see [START_REF] Mann | Directed exploration in reinforcement learning with transferred knowledge[END_REF]; [START_REF] Taylor | Transfer in Reinforcement Learning Domains[END_REF] for examples in RL and Sec. E of ? for a discussion on related settings).

The multi-armed bandit (MAB) [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] is a simple yet powerful framework formalizing the online learning with partial feedback problem, which encompasses a large number of applications, such as clinical trials, web advertisements and adaptive routing. In this paper we take a step towards understanding and providing formal bounds on transfer in stochastic MABs. We focus on a sequential transfer scenario where an (online) learner is acting in a series of tasks drawn from a stationary distribution over a finite set of MABs. The learning problem, within each task, can be seen as a standard MAB problem with a fixed number of steps. Prior to learning, the model parameters of each bandit problem are not known to the learner, nor does it know the distribution probability over the bandit problems. Also, we assume that the learner is not provided with the identity of the tasks throughout the learning. To act efficiently in this setting, it is crucial to define a mechanism for transferring knowledge across tasks. In fact, the learner may encounter the same bandit problem over and over throughout the learning, and an efficient algorithm should be able to leverage the knowledge obtained in previous tasks, when it is presented with the same problem again. To address this problem one can transfer the estimates of all the possible models from prior tasks to the current one. Once these models are accurately estimated, we show that an extension of the UCB algorithm [START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF] is able to efficiently exploit this prior knowledge and reduce the regret through tasks (Sec. 3).

The main contributions of this paper are two-fold: (i) we introduce the tUCB algorithm which transfers the model estimates across the tasks and uses this knowledge to achieve a better performance than UCB. We also prove that the new algorithm is guaranteed to perform as well as UCB in early episodes, thus avoiding any negative transfer effect, and then to approach the performance of the ideal case when the models are all known in advance (Sec. 4.4). (ii) To estimate the models we rely on a new variant of method of moments, robust tensor power method (RTP) [START_REF] Anandkumar | A tensor spectral approach to learning mixed membership community models[END_REF][START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF] and extend it to the multi-task bandit setting1 :we prove that RTP provides a consistent estimate of the means of all arms (for all models) as long as they are pulled at least three times per task and prove sample complexity bounds for it (Sec. 4.2). Finally, we report some preliminary results on synthetic data confirming the theoretical findings (Sec. 5). An extended version of this paper containing proofs and additional comments is available in (?).

Preliminaries

We consider a stochastic MAB problem defined by a set of arms A = {1, . . . , K}, where each arm i ∈ A is characterized by a distribution ν i and the samples (rewards) observed from each arm are independent and identically distributed. We focus on the setting where there exists a set of models Θ = {θ = (ν 1 , . . . , ν K )}, |Θ| = m, which contains all the possible bandit problems. We denote the mean of an arm i, the best arm, and the best value of a model θ ∈ Θ respectively by µ i (θ), i * (θ), µ * (θ). We define the arm gap of an arm i for a model θ as ∆ i (θ) = µ * (θ)µ i (θ), while the model gap for an arm i between two models θ and θ ′ is defined as Γ i (θ, θ ′ ) = |µ i (θ)µ i (θ ′ )|. We also assume that arm rewards are bounded in [0, 1]. We consider the sequential transfer setting where at each episode j the learner interacts with a task θj , drawn from a distribution ρ over Θ, for n steps. The objective is to minimize the (pseudo-)regret R J over J episodes measured as the difference between the rewards obtained by pulling i * ( θj ) and those achieved by the learner:

R J = J j=1 R j n = J j=1 i =i * T j i,n ∆ i ( θj ), (1)
where T j i,n is the number of pulls to arm i after n steps of episode j. We also introduce some tensor notation. Let X ∈ R K be a random realization of the rewards of all arms from a random model. All the realizations are i.i.d. conditional on a model θ and E[X|θ = θ] = µ(θ), where the i-th component of µ(θ) ∈ R K is [µ(θ)] i = µ i (θ). Given realizations X 1 , X 2 and X 3 , we define the second moment matrix M

2 = E[X 1 ⊗ X 2 ] such that [M 2 ] i,j = E[X 1 i X 2 j ] and the third moment tensor M 3 = E[X 1 ⊗ X 2 ⊗ X 3 ] such that [M 2 ] i,j,l = E[X 1 i X 2 j X 3 l ].
Since the realizations are conditionally independent, we have that, for every θ

∈ Θ, E[X 1 ⊗ X 2 |θ] = E[X 1 |θ] ⊗ E[X 2 |θ] = µ(θ) ⊗ µ(θ)
and this allows us to rewrite the second and third moments as

M 2 = θ ρ(θ)µ(θ) ⊗2 , M 3 = θ ρ(θ)µ(θ) ⊗3 , where v ⊗p = v ⊗ v ⊗ • • • v is the p-th tensor power.
Let A be a 3 rd order member of the tensor product of the Euclidean space R K (as M 3 ), then we define the multilinear map as follows. For a set of three matrices Before considering the transfer problem, we show that a simple variation to UCB allows us to effectively exploit the knowledge of Θ and obtain a significant reduction in the regret. The mUCB (model-UCB) algorithm in Fig. 1 takes as input a set of models Θ including the current (unknown) model θ. At each step t, the algorithm computes a subset Θ t ⊆ Θ containing only the models whose means µ i (θ) are compatible with the current estimates μi,t of the means µ i ( θ) of the current model, obtained averaging T i,t pulls, and their uncertainty ε i,t (see Eq. 2 for an explicit definition of this term). Notice that it is enough that one arm does not satisfy the compatibility condition to discard a model θ. Among all the models in Θ t , mUCB first selects the model with the largest optimal value and then it pulls its corresponding optimal arm. This choice is coherent with the optimism in the face of uncertainty principle used in UCB-based algorithms, since mUCB always pulls the optimal arm corresponding to the optimistic model compatible with the current estimates μi,t . We show that mUCB incurs a regret which is never worse than UCB and it is often significantly smaller.

{V i ∈ R K×m } 1≤i≤3 , the (i 1 , i 2 , i 3 ) entry in the 3-way array representation of A(V 1 , V 2 , V 3 ) ∈ R m×m×m is [A(V 1 , V 2 , V 3 )] i1,i2,i3 := 1≤j1,j2,j3≤n A j1,j2,j3 [V 1 ] j1,i1 [V 2 ] j2,i2 [V 3 ] j3,i3 . We also use different norms: the Euclidean norm • ; the Frobenius norm • F ; the matrix max-norm A max = max ij |[A] ij |.
We denote the set of arms which are optimal for at least a model in a set Θ ′ as A * (Θ ′ ) = {i ∈ A : ∃θ ∈ Θ ′ : i * (θ) = i}. The set of models for which the arms in A ′ are optimal is Θ(A ′ ) = {θ ∈ Θ : ∃i ∈ A ′ : i * (θ) = i}. The set of optimistic models for a given model θ is Θ + = {θ ∈ Θ : µ * (θ) ≥ µ * ( θ)}, and their corresponding optimal arms A + = A * (Θ + ). The following theorem bounds the expected regret (similar bounds hold in high probability). The lemmas and proofs (using standard tools from the bandit literature) are available in Sec. B of ?. Theorem 1. If mUCB is run with δ = 1/n, a set of m models Θ such that the θ ∈ Θ and

ε i,t = log(mn 2 /δ)/(2T i,t-1 ), ( 2
)
where T i,t-1 is the number of pulls to arm i at the beginning of step t, then its expected regret is

E[R n ] ≤ K + i∈A+ 2∆ i ( θ) log mn 3 min θ∈Θ+,i Γ i (θ, θ) 2 ≤ K + i∈A+ 2 log mn 3 min θ∈Θ+,i Γ i (θ, θ) , ( 3
)
where A + = A * (Θ + ) is the set of arms which are optimal for at least one optimistic model Θ + and Θ +,i = {θ ∈ Θ + : i * (θ) = i} is the set of optimistic models for which i is the optimal arm.

Remark (comparison to UCB). The UCB algorithm incurs a regret

E[R n (UCB)] ≤ O i∈A log n ∆ i ( θ) ≤ O K log n min i ∆ i ( θ)
.

We see that mUCB displays two major improvements. The regret in Eq. 3 can be written as

E[R n (mUCB)] ≤ O i∈A+ log n min θ∈Θ+,i Γ i (θ, θ) ≤ O |A + | log n min i min θ∈Θ+,i Γ i (θ, θ)
.

This result suggests that mUCB tends to discard all the models in Θ + from the most optimistic down to the actual model θ which, with high-probability, is never discarded. As a result, even if other models are still in Θ t , the optimal arm of θ is pulled until the end. This significantly reduces the set of arms which are actually pulled by mUCB and the previous bound only depends on the number of arms in A + , which is

|A + | ≤ |A * (Θ)| ≤ K.
Furthermore, for all arms i, the minimum gap min θ∈Θ+,i Γ i (θ, θ) is guaranteed to be larger than the arm gap ∆ i ( θ) (see Lem. 4 in Sec. B of ?), thus further improving the performance of mUCB w.r.t. UCB.

Online Transfer with Unknown Models

We now consider the case when the set of models is unknown and the regret is cumulated over multiple tasks drawn from ρ (Eq. 1). We introduce tUCB (transfer-UCB) which transfers estimates of Θ, whose accuracy is improved through episodes using a method-of-moments approach.

The transfer-UCB Bandit Algorithm

Fig. 2 outlines the structure of our online transfer bandit algorithm tUCB (transfer-UCB). The algorithm uses two sub-algorithms, the bandit algorithm umUCB (uncertain model-UCB), whose objective is to minimize the regret at each episode, and RTP (robust tensor power method) which at each episode j computes an estimate {μ j i (θ)} of the arm means of all the models. The bandit algorithm umUCB in Fig. 3 is an extension of the mUCB algorithm. It first computes a set of models Θ j t whose means μi (θ) are compatible with the current estimates μi,t . However, unlike the case where the exact models are available, here the models themselves are estimated and the uncertainty ε j in their means (provided as input to umUCB) is taken into account in the definition of Θ j t . Once

Require: number of arms K, number of models m, constant C(θ).

Initialize estimated models

Θ 1 = {μ 1 i (θ)} i,θ , samples R ∈ R J×K×n for j = 1, 2, . . . , J do Run R j = umUCB(Θ j , n) Run Θ j+1 = RTP(R, m, K, j, δ) end for
v(θ)}, { λ(θ)} Compute µ j (θ) = λ(θ)( W T ) + v(θ) for all θ ∈ Θ return Θ j+1 = { µ j (θ) : θ ∈ Θ} Figure 4:
The robust tensor power (RTP) method [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF].

the active set is computed, the algorithm computes an upper-confidence bound on the value of each arm i for each model θ and returns the best arm for the most optimistic model. Unlike in mUCB, due to the uncertainty over the model estimates, a model θ might have more than one optimal arm, and an upper-confidence bound on the mean of the arms μi (θ) + ε j is used together with the upperconfidence bound μi,t + ε i,t , which is directly derived from the samples observed so far from arm i. This guarantees that the B-values are always consistent with the samples generated from the actual model θj . Once umUCB terminates, RTP (Fig. 4) updates the estimates of the model means µ j (θ) = {μ j i (θ)} i ∈ R K using the samples obtained from each arm i. At the beginning of each task umUCB pulls all the arms 3 times, since RTP needs at least 3 samples from each arm to accurately estimate the 2 nd and 3 rd moments [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF]. More precisely, RTP uses all the reward samples generated up to episode j to estimate the 2 nd and 3 rd moments (see Sec. 2) as

M 2 = j -1 j l=1 µ 1l ⊗ µ 2l ,
and

M 3 = j -1 j l=1 µ 1l ⊗ µ 2l ⊗ µ 3l , (4)
where the vectors µ 1l , µ 2l , µ 3l ∈ R K are obtained by dividing the T l i,n samples observed from arm i in episode l in three batches and taking their average (e.g., [µ 1l ] i is the average of the first T l i,n /3 samples).2 Since µ 1l , µ 2l , µ 3l are independent estimates of µ( θl ), M 2 and M 3 are consistent estimates of the second and third moments M 2 and M 3 . RTP relies on the fact that the model means µ(θ) can be recovered from the spectral decomposition of the symmetric tensor T = M 3 (W, W, W ), where W is a whitening matrix for M 2 , i.e., M 2 (W, W ) = I m×m (see Sec. 2 for the definition of the mapping A(V 1 , V 2 , V 3 )). Anandkumar et al. (2012b) (Thm. 4.3) have shown that under some mild assumption (see later Assumption 1) the model means {µ(θ)}, can be obtained as µ(θ) = λ(θ)Bv(θ), where (λ(θ), v(θ)) is a pair of eigenvector/eigenvalue for the tensor T and B := (W T ) + .Thus the RTP algorithm estimates the eigenvectors v(θ) and the eigenvalues λ(θ), of the m × m × m tensor T := M 3 ( W , W , W ).3 Once v(θ) and λ(θ) are computed, the estimated mean vector µ j (θ) is obtained by the inverse transformation µ j (θ) = λ(θ) B v(θ), where B is the pseudo inverse of W T (for a detailed description of RTP algorithm see [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF].

Sample Complexity of the Robust Tensor Power Method

umUCB requires as input ε j , i.e., the uncertainty of the model estimates. Therefore we need sample complexity bounds on the accuracy of {μ i (θ)} computed by RTP. The performance of RTP is directly affected by the error of the estimates M 2 and M 3 w.r.t. the true moments. In Thm. 2 we prove that, as the number of tasks j grows, this error rapidly decreases with the rate of 1/j. This result provides us with an upper-bound on the error ε j needed for building the confidence intervals in umUCB. The following definition and assumption are required for our result. Definition 1. Let Σ M2 = {σ 1 , σ 2 , . . . , σ m } be the set of m largest eigenvalues of the matrix M 2 . Define σ min := min σ∈Σ M 2 σ, σ max := max σ∈Σ M 2 σ and λ max := max θ λ(θ). Define the minimum gap between the distinct eigenvalues of M 2 as Γ σ := min σi =σ l (|σ iσ l |). Assumption 1. The mean vectors {µ(θ)} θ are linear independent and ρ(θ) > 0 for all θ ∈ Θ.

We now state our main result which is in the form of a high probability bound on the estimation error of mean reward vector of every model θ ∈ Θ.

Theorem 2. Pick δ ∈ (0, 1). Let C(Θ) := C 3 λ max σ max /σ 3 min (σ max /Γ σ + 1/σ min + 1/σ max )
, where C 3 > 0 is a universal constant. Then under Assumption 1 there exist constants C 4 > 0 and a permutation π on Θ, such that for all θ ∈ Θ, we have w.p.

1 -δ µ(θ) -µ j (π(θ)) ≤ ε j C(Θ)K 2.5 m 2 log(K/δ) j after j ≥ C4m 5 K 6 log(K/δ) min(σmin,Γσ) 2 σ 3 min λ 2 min . (5)
Remark (computation of C(Θ)). As illustrated in Fig. 3, umUCB relies on the estimates µ j (θ) and on their accuracy ε j . Although the bound reported in Thm. 2 provides an upper confidence bound on the error of the estimates, it contains terms which are not computable in general (e.g., σ min ). In practice, C(Θ) should be considered as a parameter of the algorithm.This is not dissimilar from the parameter usually introduced in the definition of ε i,t in front of the square-root term in UCB.

Regret Analysis of umUCB

We now analyze the regret of umUCB when an estimated set of models Θ j is provided as input. At episode j, for each model θ we define the set of non-dominated arms (i.e., potentially optimal arms) as

A j * (θ) = {i ∈ A : ∄i ′ , μj i (θ) + ε j < μj i ′ (θ) -ε j }.
Among the non-dominated arms, when the actual model is θj , the set of optimistic arms is

A j + (θ; θj ) = {i ∈ A j * (θ) : μj i (θ) + ε j ≥ µ * ( θj )}. As a result, the set of optimistic models is Θ j + ( θj ) = {θ ∈ Θ : A j + (θ; θj ) = ∅}.
In some cases, because of the uncertainty in the model estimates, unlike in mUCB, not all the models θ = θj can be discarded, not even at the end of a very long episode. Among the optimistic models, the set of models that cannot be discarded is defined as

Θ j + ( θj ) = {θ ∈ Θ j + ( θj ) : ∀i ∈ A j + (θ; θj ), |μ j i (θ)-µ i ( θj )| ≤ ε j }.
Finally, when we want to apply the previous definitions to a set of models Θ ′ instead of single model we have, e.g., A j * (Θ ′ ; θj ) = θ∈Θ ′ A j * (θ; θj ). The proof of the following results are available in Sec. D of ?, here we only report the number of pulls, and the corresponding regret bound.

Corollary 1. If at episode j umUCB is run with ε i,t as in Eq. 2 and ε j as in Eq. 5 with a parameter δ ′ = δ/2K, then for any arm

i ∈ A, i = i * ( θj ) is pulled T i,n times such that            Ti,n ≤ min 2 log 2mKn 2 /δ ∆i( θj ) 2 , log 2mKn 2 /δ 2 min θ∈Θ j i,+ ( θj ) Γi(θ; θj ) 2 + 1 if i ∈ A j 1 Ti,n ≤ 2 log 2mKn 2 /δ /(∆i( θj ) 2 ) + 1 if i ∈ A j 2 Ti,n = 0 otherwise w.p. 1 -δ, where Θ j i,+ ( θj ) = {θ ∈ Θ j + ( θj ) : i ∈ A + (θ; θj )} is the set of models for which i is among their optimistic non-dominated arms, Γ i (θ; θj ) = Γ i (θ, θj )/2-ε j , A j 1 = A j + (Θ j + ( θj ); θj )- A j + ( Θ j + ( θj ); θj ) (i.

e., set of arms only proposed by models that can be discarded), and

A j 2 = A j + ( Θ j + ( θj ); θj ) (i.

e., set of arms only proposed by models that cannot be discarded).

The previous corollary states that arms which cannot be optimal for any optimistic model (i.e., the optimistic non-dominated arms) are never pulled by umUCB, which focuses only on arms in i ∈ A j + (Θ j + ( θj ); θj ). Among these arms, those that may help to remove a model from the active set (i.e., i ∈ A j 1 ) are potentially pulled less than UCB, while the remaining arms, which are optimal for the models that cannot be discarded (i.e., i ∈ A j 2 ), are simply pulled according to a UCB strategy. Similar to mUCB, umUCB first pulls the arms that are more optimistic until either the active set Θ j t changes or they are no longer optimistic (because of the evidence from the actual samples). We are now ready to derive the per-episode regret of umUCB. Theorem 3. If umUCB is run for n steps on the set of models Θ j estimated by RTP after j episodes with δ = 1/n, and the actual model is θj , then its expected regret (w.r.t. the random realization in episode j and conditional on θj ) is

E[R j n ] ≤ K + i∈A j 1 log 2mKn 3 min 2/∆i( θj ) 2 , 1/ 2 min θ∈Θ j i,+ ( θj ) Γi(θ; θj ) 2 ∆i( θj ) + i∈A j 2 2 log 2mKn 3 /∆i( θj ).
Remark (negative transfer). The transfer of knowledge introduces a bias in the learning process which is often beneficial. Nonetheless, in many cases transfer may result in a bias towards wrong solutions and a worse learning performance, a phenomenon often referred to as negative transfer. The first interesting aspect of the previous theorem is that umUCB is guaranteed to never perform worse than UCB itself. This implies that tUCB never suffers from negative transfer, even when the set Θ j contains highly uncertain models and might bias umUCB to pull suboptimal arms.

Remark (improvement over UCB). In Sec. 3 we showed that mUCB exploits the knowledge of Θ to focus on a restricted set of arms which are pulled less than UCB. In umUCB this improvement is not as clear, since the models in Θ are not known but are estimated online through episodes. Yet, similar to mUCB, umUCB has the two main sources of potential improvement w.r.t. to UCB. As illustrated by the regret bound in Thm. 3, umUCB focuses on arms in A j 1 ∪ A j 2 which is potentially a smaller set than A. Furthermore, the number of pulls to arms in A j 1 is smaller than for UCB whenever the estimated model gap Γ i (θ; θj ) is bigger than ∆ i ( θj ). Eventually, umUCB reaches the same performance (and improvement over UCB) as mUCB when j is big enough. In fact, the set of optimistic models reduces to the one used in mUCB (i.e., Θ j + ( θj ) ≡ Θ + ( θj )) and all the optimistic models have only optimal arms (i.e., for any θ ∈ Θ + the set of non-dominated optimistic arms is A + (θ; θj ) = {i * (θ)}), which corresponds to A j 1 ≡ A * (Θ + ( θj )) and A j 2 ≡ {i * ( θj )}, which matches the condition of mUCB. For instance, for any model θ, in order to have A * (θ) = {i * (θ)}, for any arm i = i * (θ) we need that μj

i (θ) + ε j ≤ μj i * (θ) (θ) -ε j . Thus after j ≥ 2C(Θ) min θ∈Θ min θ∈Θ+( θ) min i ∆ i (θ) 2 + 1.
episodes, all the optimistic models have only one optimal arm independently from the actual identity of the model θj . Although this condition may seem restrictive, in practice umUCB starts improving over UCB much earlier, as illustrated in the numerical simulation in Sec. 5.

Regret Analysis of tUCB

Given the previous results, we derive the bound on the cumulative regret over J episodes (Eq. 1).

Theorem 4. If tUCB is run over J episodes of n steps in which the tasks θj are drawn from a fixed distribution ρ over a set of models Θ, then its cumulative regret is

RJ ≤ JK + J j=1 i∈A j 1 min 2 log 2mKn 2 /δ ∆i( θj ) 2 , log 2mKn 2 /δ 2 min θ∈Θ j i,+ ( θj ) Γ j i (θ; θj ) 2 ∆i( θj ) + J j=1 i∈A j 2
2 log 2mKn 2 /δ ∆i( θj ) , w.p. 1δ w.r.t. the randomization over tasks and the realizations of the arms in each episode. This result immediately follows from Thm. 3 and it shows a linear dependency on the number of episodes J. This dependency is the price to pay for not knowing the identity of the current task θj . If the task was revealed at the beginning of the task, a bandit algorithm could simply cluster all the samples coming from the same task and incur a much smaller cumulative regret with a logarithmic dependency on episodes and steps, i.e., log(nJ). Nonetheless, as discussed in the previous section, the cumulative regret of tUCB is never worse than for UCB and as the number of tasks increases it approaches the performance of mUCB, which fully exploits the prior knowledge of Θ.

Numerical Simulations

In this section we report preliminary results of tUCB on synthetic data. The objective is to illustrate and support the previous theoretical findings. We define a set Θ of m = 5 MAB problems with K = 7 arms each, whose means {µ i (θ)} i,θ are reported in Fig. 5 (see Sect. F in ? for the actual values), where each model has a different color and squares correspond to optimal arms (e.g., arm 2 is optimal for model θ 2 ). This set of models is chosen to be challenging and illustrate some interesting cases useful to understand the functioning of the algorithm. 4 Models θ 1 and θ 2 only differ in their optimal arms and this makes it difficult to distinguish them. For arm 3 (which is optimal for model θ 3 and thus potentially selected by mUCB), all the models share exactly the same mean value. This implies that no model can be discarded by pulling it. Although this might suggest that mUCB gets stuck in pulling arm 3, we showed in Thm. 1 that this is not the case. Models θ 1 and θ 5 are challenging for UCB since they have small minimum gap. Only 5 out of the 7 arms are actually optimal for a model in Θ. Thus, we also report the performance of UCB+ which, under the assumption that Θ is known, immediately discards all the arms which are not optimal (i / ∈ A * ) and performs UCB on the remaining arms. The model distribution is uniform, i.e., ρ(θ) = 1/m. Before discussing the transfer results, we compare UCB, UCB+, and mUCB, to illustrate the advantage of the prior knowledge of Θ w.r.t. UCB. Fig. 7 reports the per-episode regret of the three algorithms for episodes of different length n (the performance of tUCB is discussed later). The results are averaged over all the models in Θ and over 200 runs each. All the algorithms use the same confidence bound ε i,t . The performance of mUCB is significantly better than both UCB, and UCB+, thus showing that mUCB makes an efficient use of the prior of knowledge of Θ. Furthermore, in Fig. 6 the horizontal lines correspond to the value of the regret bounds up to the n dependent terms and constants5 for the different models in Θ averaged w.r.t. ρ for the three algorithms (the actual values for the different models are in the supplementary material). These values show that the improvement observed in practice is accurately predicated by the upper-bounds derived in Thm. 1.

We now move to analyze the performance of tUCB. In Fig. 8 we show how the per-episode regret changes through episodes for a transfer problem with J = 5000 tasks of length n = 5000. In tUCB we used ε j as in Eq. 5 with C(Θ) = 2. As discussed in Thm. 3, UCB and mUCB define the boundaries of the performance of tUCB. In fact, at the beginning tUCB selects arms according to a UCB strategy, since no prior information about the models Θ is available. On the other hand, as more tasks are observed, tUCB is able to transfer the knowledge acquired through episodes and build an increasingly accurate estimate of the models, thus approaching the behavior of mUCB. This is also confirmed by Fig. 6 where we show how the complexity of tUCB changes through episodes. In both cases (regret and complexity) we see that tUCB does not reach the same performance of mUCB. This is due to the fact that some models have relatively small gaps and thus the number of episodes to have an accurate enough estimate of the models to reach the performance of mUCB is much larger than 5000 (see also the Remarks of Thm. 3). Since the final objective is to achieve a small global regret (Eq. 1), in Fig. 7 we report the cumulative regret averaged over the total number of tasks (J) for different values of J and n. Again, this graph shows that tUCB outperforms UCB and that it tends to approach the performance of mUCB as J increases, for any value of n.

Conclusions and Open Questions

In this paper we introduce the transfer problem in the multi-armed bandit framework when a tasks are drawn from a finite set of bandit problems. We first introduced the bandit algorithm mUCB and we showed that it is able to leverage the prior knowledge on the set of bandit problems Θ and reduce the regret w.r.t. UCB. When the set of models is unknown we define a method-of-moments variant (RTP) which consistently estimates the means of the models in Θ from the samples collected through episodes. This knowledge is then transferred to umUCB which performs no worse than UCB and tends to approach the performance of mUCB. For these algorithms we derive regret bounds, and we show preliminary numerical simulations. To the best of our knowledge, this is the first work studying the problem of transfer in multi-armed bandit. It opens a series of interesting directions, including whether explicit model identification can improve our transfer regret.

Optimality of tUCB. At each episode, tUCB transfers the knowledge about Θ acquired from previous tasks to achieve a small per-episode regret using umUCB. Although this strategy guarantees that the per-episode regret of tUCB is never worse than UCB, it may not be the optimal strategy in terms of the cumulative regret through episodes. In fact, if J is large, it could be preferable to run a model identification algorithm instead of umUCB in earlier episodes so as to improve the quality of the estimates μi (θ). Although such an algorithm would incur a much larger regret in earlier tasks (up to linear), it could approach the performance of mUCB in later episodes much faster than done by tUCB. This trade-off between identification of the models and transfer of knowledge may suggest that different algorithms than tUCB are possible.

Unknown model-set size. In some problems the size of model set m is not known to the learner and needs to be estimated. This problem can be addressed by estimating the rank of matrix M 2 which equals to m [START_REF] Kleibergen | Generalized reduced rank tests using the singular value decomposition[END_REF]. We also note that one can relax the assumption that ρ(θ) needs to be positive (see Assumption 1) by using the estimated model size as opposed to m, since M 2 depends not on the means of models with ρ(θ) = 0.

Appendices A Table of Notation

σmax Γσ + 1 σ min + 1 σmax π(θ) Permutation on θ A j * (θ)
Set of non-dominated arms for model θ at episode j Θ j + Set of models that cannot be discarded at episode j Θ j i,+ Set of models for which i is among the optimistic non-dominated arms at episode j 1 B Proofs of Section 3 Lemma 1. mUCB never pulls arms which are not optimal for at least one model, that is ∀i / ∈ A * (Θ), T i,n = 0 with probability 1. Notice also that |A * (Θ)| ≤ |Θ|.

Lemma 2. The actual model θ is never discarded with high-probability. Formally, the event E = {∀t = 1, . . . , n, θ ∈ Θ t } holds with probability P

[E] ≥ 1 -δ if ε i,t = 1 2T i,t-1 log mn 2 δ ,
where T i,t-1 is the number of pulls to arm i at the beginning of step t and m = |Θ|.

In the previous lemma we implicitly assumed that |Θ| = m ≤ K. In general, the best choice in the definition of ε i,t has a logarithmic factor with min{|Θ|, K}.

Lemma 3. On event E, all the arms i / ∈ A * (Θ + ), i.e., arms which are not optimal for any of the optimistic models, are never pulled, i.e., T i,n = 0 with probability 1δ.

The previous lemma suggests that mUCB tends to discard all the models in Θ + from the most optimistic down to the actual model θ which, on event E, is never discarded. As a result, even if other models are still in Θ t , the optimal arm of θ is pulled until the end. Finally, we show that the model gaps of interest (see Thm. 1) are always bigger than the arm gaps.

Lemma 4. For any model

θ ∈ Θ + , Γ i * (θ) (θ, θ) ≥ ∆ i * (θ) ( θ).
Proof of Lem. 1. From the definition of the algorithm we notice that I t can only correspond to the optimal arm i * of one model in the set Θ t . Since Θ t can at most contain all the models in Θ, all the arms which are not optimal are never pulled.

Proof of Lem. 2. We compute the probability of the complementary event E C , that is that event on which there exist at least one step t = 1, . . . , n where the true model θ is not in Θ t . By definition of Θ t , we have that

E = {∀t, θ ∈ Θ t } = {∀t, ∀i ∈ A, |µ i -μi,t | ≤ ε i,t }, then P[E C ] = P[∃t, i, |µ i -μi,t | ≥ ε i,t ] ≤ n t=1 i∈A P[|µ i -μi,t | ≥ ε i,t ] = n t=1 i∈A * (Θ) P[|µ i -μi,t | ≥ ε i,t ]
where the upper-bounding is a simple union bound and the last passage comes from the fact that the probability for the arms which are never pulled is always 0 according to Lem. 1. At time t, μi,t is the empirical average of the T i,t-1 samples observed from arm i up to the beginning of round t. We define the confidence ε i,t as

ε i,t = 1 2T i,t-1 log |Θ|n α δ ,
where δ ∈ (0, 1) and α is a constant chosen later. Since T i,t-1 is a random variable, we need to take an additional union bound over T i,t-1 = 1, . . . , t -1 thus obtaining

P[E C ] ≤ n t=1 i∈A * (Θ) t-1 Ti,t-1=1 P[|µ i -μi,t | ≥ ε i,t ] ≤ n t=1 i∈A * (Θ) t-1 Ti,t-1=1 2 exp -2T i,t-1 ε 2 i,t ≤ n(n -1) |A * (Θ)|δ |Θ|n α .
Since |A * (Θ)| < |Θ| (see Lem. 1) and by taking α = 2 we finally have

P[E C ] ≤ δ.
Proof of Lem. 3. On event E, Θ t always contains the true model θ, thus only models with larger optimal value could be selected as the optimistic model θ t = arg max θ∈Θt µ * (θ), thus restricting the focus of the algorithm only to the models in Θ + and their respective optimal arms.

Proof of Lem. 4. By definition of Θ + we have µ i * (θ) (θ) = µ * (θ) > µ * ( θ) and by definition of optimal arm we have µ * ( θ) > µ i * (θ) ( θ), hence µ * (θ) > µ i * (θ) ( θ). Recalling the definition of model gap, we have

Γ i * (θ) (θ) = |µ i * (θ) (θ) -µ i * (θ) ( θ)| = µ * (θ) -µ i * (θ) ( θ)
, where we used the definition of µ * (θ) and the previous inequality. Using the definition of arm gap ∆ i , we obtain

Γ i * (θ) (θ, θ) = µ * (θ) -µ i * (θ) ( θ) ≥ µ * ( θ) -µ i * (θ) ( θ) = ∆ i * (θ) ( θ),
which proves the statement.

Proof of Thm. 1. We decompose the expected regret as

E[R n ] = i∈A ∆ i E[T i,n ] = i∈A * (Θ) ∆ i E[T i,n ] ≤ nP{E C } + i∈A+ ∆ i E[T i,n |E],
where the refinement on the sum over arms follows from Lem. 1 and 3 and the high probability event E. In the following we drop the dependency on θ and we write µ i ( θ) = µ i .

We now bound the regret when the correct model is always included in Θ t . On event E, only the restricted set of optimistic models Θ + = {θ ∈ Θ : µ * (θ) ≥ µ * } is actually used by the algorithm. Thus we need to compute the number of pulls to the suboptimal arms before all the models in Θ + are discarded from Θ t . We first compute the number of pulls to an arm i needed to discard a model θ on event E. We notice that

θ ∈ Θ t ⇔ {∀i ∈ A, |µ i (θ) -μi,t | ≤ ε i,t },
which means that a model θ is included only when all its means are compatible with the current estimates. Since we consider event

E, |µ i -μi,t | ≤ ε i,t , thus θ ∈ Θ t only if for all i ∈ A 2ε i,t ≥ Γ i (θ, θ),
which corresponds to

T i,t-1 ≤ 2 Γ i (θ, θ) 2 log |Θ|n 2 δ , (6)
which implies that if there exists at least one arm i for which at time t the number of pulls T i,t exceeds the previous quantity, then ∀s > t we have θ / ∈ Θ t (with probability P(E)). To obtain the final bound on the regret, we recall that the algorithm first selects an optimistic model θ t and then it pulls the corresponding optimal arm until the optimistic model is not discarded. Thus we need to compute the number of times the optimal arm of the optimistic model is pulled before the model is discarded. More formally, since we know that on event E we have that T i,n = 0 for all i / ∈ A + , the constraints of type (6) could only be applied to the arms i ∈ A + . Let t be the last time arm i is pulled, which coincides, by definition of the algorithm, with the last time any of the models in Θ +,i = {θ ∈ Θ + : i * (θ) = i} (i.e., the optimistic models recommending i as the optimal arm) is included in Θ t . Then we have that T i,t-1 = T i,n -1 and the fact that i is pulled corresponds to the fact the a model

θ i ∈ Θ +,i is such that θ i ∈ Θ t ∧ ∀θ ′ ∈ Θ t , µ * (θ i ) > µ * (θ ′ ),
which implies that (see Eq. 6)

T i,n ≤ 2 min θ∈Θ+,i Γ i (θ, θ) 2 log |Θ|n 2 δ + 1. ( 7
)
where the minimum over Θ +,i guarantees that all the optimistic models with optimal arm i are actually discarded. Grouping all the conditions, we obtain the expected regret

E[R n ] ≤ K + i∈A+ 2∆ i ( θ) min θ∈Θ+,i Γ i (θ, θ) 2 log |Θ|n 3
with δ = 1/n. Finally we can apply Lem. 4 which guarantees that for any θ ∈ Θ +,i the gaps Γ i (θ, θ) ≥ ∆ i ( θ) and obtain the final statement.

Remark (proof). The proof of the theorem considers a worst case. In fact, while pulling the optimal arm of the optimistic model i * (θ t ) we do not consider that the algorithm might actually discard other models, thus reducing Θ t before the optimistic model is actually discarded. More formally, we assume that for any θ ∈ Θ t not in Θ +,i the number of steps needed to be discarded by pulling i * (θ t ) is larger than the number of pulls needed to discard θ t itself, which corresponds to min θ∈Θ+,i

Γ 2 i (θ, θ) ≥ max θ∈Θ + θ / ∈Θ+,i Γ 2 i (θ, θ).
Whenever this condition is not satisfied, the analysis is suboptimal since it does not fully exploit the structure of the problem and mUCB is expected to perform better than predicted by the bound.

Remark (comparison to UCB with hypothesis testing). An alternative strategy is to pair UCB with hypothesis testing of fixed confidence δ. Let Γ min ( θ) = min i min θ Γ i (θ, θ), if at time t there exists an arm i such that T i,t > 2 log(2/δ)Γ 2 min , then all the models θ = θ can be discarded with probability 1δ. Since from the point of view of the hypothesis testing the exploration strategy is unknown, we can only assume that after τ steps we have T i,τ ≥ τ /K for at least one arm i. Thus after τ > 2K log(2/δ)/Γ 2 min steps, the hypothesis testing returns a model θ which coincides with θ with probability 1δ. If τ ≤ n, from time τ on, the algorithm always pulls I t = i * ( θ) and incurs a zero regret with high probability. If we assume τ ≤ n, the expected regret is

E[R n (UCB+Hyp)] ≤ O i∈A log nτ ∆ i ≤ O K log nτ ∆ .
We notice that this algorithm only has a mild improvement w.r.t. standard UCB. In fact, in UCB the big-O notation hides the constants corresponding to the exponent of n in the logarithmic term. This suggests that whenever τ is much smaller than n, then there might be a significant improvement. On the other hand, since τ has an inverse dependency w.r.t. Γ min , it is very easy to build model sets Θ where Γ min = 0 and obtain an algorithm with exactly the same performance as UCB.

C Sample Complexity Analysis of RTP

In this section we provide the full sample complexity analysis of the RTP algorithm. In our analysis we rely on some results of [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF]. [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF] have provided perturbation bounds on the error of the orthonormal eigenvectors v(θ) and the corresponding eigenvalues λ(θ) in terms of the perturbation error of the transformed tensor ǫ = T -T (see Anandkumar et al., 2012b, Thm 5.1). However, this result does not provide us with the sample complexity bound on the estimation error of model means. Here we complete their analysis by proving a sample complexity bound on the ℓ 2 -norm of the estimation error of the means µ(θ)µ(θ) .

We follow the following steps in our proof: (i) we bound the error ǫ in terms of the estimation errors ǫ 2 := M 2 -M 2 and ǫ 3 := M 3 -M 3 (Lem. 6). (ii) we prove high probability bounds on the error ǫ 2 and ǫ 3 using some standard concentration inequality results (Lem. 7). The bounds on the errors of the estimates v(θ) and λ(θ) immediately follow from combining the results of Lem. 6, Lem. 7 and Thm. 5. (iii) Based on these bounds we then prove our main result by bounding the estimation error associated with the inverse transformation µ(θ) = λ(θ) B v(θ) in high probability.

We begin by recalling the perturbation bound of [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF]:

Theorem 5 [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF]. Pick η ∈ (0, 1). Define W := U D -1/2 , where D ∈ R m×m is the diagonal matrix of the m largest eigenvalues of M 2 and U ∈ R K×m is the matrix with the eigenvectors associated with the m largest eigenvalues of M 2 as its columns. Then W is a linear mapping which satisfies W T M 2 W = I. Let T = T + E ∈ R m×m×m , where the 3 rd order moment tensor T = M 3 (W, W, W ) is symmetric and orthogonally decomposable in the form of θ∈Θ λ(θ)v(θ) ⊗3 , where each λ(θ) > 0 and {v(θ)} θ is an orthonormal basis. Define ǫ := E and λ max = max θ λ(θ). Then there exist some constants C 1 , C 2 > 0, some polynomial function f (•), and a permutation π on Θ such that the following holds w.p.

1 -η v(θ) -v(π(θ)) ≤ 8ǫ/λ(θ), |λ(θ) -λ(π(θ))| ≤ 5ǫ, for ǫ ≤ C 1 λmin m , L > log(1/η)f (k) and N ≥ C 2 (log(k) + log log(λ max /ǫ))
, where N and L are the internal parameters of RTP algorithm.

For ease of exposition we consider the RTP algorithm in asymptotic case, i.e., N, L → ∞ and η ≈ 1. We now prove bounds on the perturbation error ǫ in terms of the estimation error ǫ 2 and ǫ 3 . This requires bounding the error between W = U D -1/2 and W = U D -1/2 using the following perturbation bounds on U -U , D -1/2 -D -1/2 and D 1/2 -D 1/2 . Lemma 5. Assume that ǫ 2 ≤ 1/2 min(Γ σ , σ min ), then we have

D -1/2 -D -1/2 ≤ 2ǫ 2 (σ min ) 3/2 , and D 1/2 -D 1/2 ≤ ǫ 2 σ max , and
U -U ≤ 2 √ mǫ 2 Γ σ .
Proof. Here we just prove bounds on D -1/2 -D -1/2 and U -U . The bound on D -1/2 -D -1/2 can be proven using a similar argument to that used for bounding

D 1/2 -D 1/2 . Let Σ m = { σ 1 , σ 2 , .
. . , σ m } be the set of m largest eigenvalues of the matrix M 2 . We have

D -1/2 -D -1/2 (1) = max 1≤i≤m 1 σ i - 1 σ i = max 1≤i≤m   1 σi -1 σi 1 σi + 1 σi   ≤ max 1≤i≤m √ σ i 1 σ i - 1 σ i ≤ max 1≤i≤m σ i -σ i √ σ i σ i (2) ≤ ǫ 2 √ σ min (σ min -ǫ 2 ) (3) ≤ 2ǫ 2 (σ min ) 3/2 ,
where in (1) we use the fact that the spectral norm of matrix is its largest singular value, which in case of a diagonal matrix coincides with its biggest element, in (2) we rely on the result of Weyl (see Stewart and Sun, 1990, Thm. 4.11, p. 204) for bounding the difference between σ i and σ i , and in (3) we make use of the assumption that ǫ 2 ≤ 1/2σ min .

In the case of U -U we rely on the perturbation bound of [START_REF] Wedin | Perturbation bounds in connection with singular value decomposition[END_REF]. This result guarantees that for any positive definite matrix A the difference between the eigenvectors of A and the perturbed A (also positive definite) is small whenever there is a minimum gap between the eigenvalues of A and A. More precisely, for any positive definite matrix A and A such that ||A -A|| ≤ ǫ A , let the minimum eigengap be Γ A↔ A := min j =i |σ iσ j |, then we have

u i -u i ≤ ǫ A Γ A↔ A , (8)
where (u i , σ i ) is an eigenvalue/vector pair for the matrix A. Based on this result we now bound the error

U -U U -U ≤ U -U F ≤ i u i -u i 2 (1) ≤ √ mǫ 2 Γ M2↔ M2 (2) ≤ √ mǫ 2 Γ σ -ǫ 2 (3) ≤ 2 √ mǫ 2 Γ σ ,
where in (1) we rely on Eq. 8 and in (2) we rely on the definition of the gap as well as Weyl's inequality. Finally, in (3) We rely on the fact that ǫ 2 ≤ 1/2Γ σ for bounding denominator from below.

Our result also holds for those cases where the multiplicity of some of the eigenvalues are greater than 1. Note that for any eigenvalue λ with multiplicity l the linear combination of the corresponding eigenvectors {v 1 , v 2 , . . . , v l } is also an eigenvector of the matrix. Therefore, in this case it suffices to bound the difference between the eigenspaces of two matrix. The result of [START_REF] Wedin | Perturbation bounds in connection with singular value decomposition[END_REF] again applies to this case and bounds the difference between the eigenspaces in terms of the perturbation ǫ 2 and Γ σ .

We now bound ǫ in terms of ǫ 2 and ǫ 3 . Lemma 6. Let µ max := max θ µ(θ) , if ǫ 2 ≤ 1/2 min(Γ σ , σ min ), then the estimation error ǫ is bounded as

ǫ ≤ m σ min 3/2 10ǫ 2 1 Γ σ + 1 σ min ǫ 3 + µ 3 max + ǫ 3 .
Proof. Based on the definitions of T and T we have

ǫ = T -T = M 3 (W, W, W ) -M 3 ( W , W , W ) ≤ M 3 (W, W, W ) -M 3 (W, W, W ) + M 3 (W, W, W ) -M 3 (W, W, W ) + M 3 (W, W, W ) -M 3 (W, W , W ) + M 3 (W, W , W ) -M 3 ( W , W , W ) = E M3 (W, W, W ) + M 3 (W, W, W -W ) + M 3 (W, W -W , W ) + M 3 (W -W , W , W ) , (9)
where E M3 = M 3 -M 3 . We now bound the terms in the r.h.s. of Eq. 9 in terms of ǫ 3 and ǫ 2 . We begin by bounding E M3 (W, W, W ) :

E M3 (W, W, W ) ≤ E M3 W 3 ≤ E M3 U 3 D -1 3/2 ≤ E M3 U 3 F D -1 3/2 (1) = m σ min 3/2 E M3 ≤ m σ min 3/2 ǫ 3 , (10)
where in (1) we use the fact that U is an orthonormal matrix and D is diagonal. In the case of M 3 (W, W, W -W ) we have

M 3 (W, W, W -W ) ≤ W 2 W -W M 3 ≤ W 2 W -W ( M 3 -M 3 + M 3 ) (1) ≤ W 2 W -W (ǫ 3 + µ 3 max ) ≤ W 2 U D -1/2 -U D -1/2 (ǫ 3 + µ 3 max ) ≤ W 2 ( (U -U )D -1/2 + U ( D -1/2 -D -1/2 ) ) ǫ 3 + µ 3 max ≤ W 2 U -U √ σ min + √ m D -1/2 -D -1/2 ǫ 3 + µ 3 max .
where in (1) we use the definition of M 3 as a linear combination of the tensor product of the means µ(θ). This result combined with the result of Lem. 5 and the fact that W ≤ m/σ min (see Eq. 10) implies that

M 3 (W, W, W -W ) ≤ m σ min 2 √ mǫ 2 Γ σ √ σ min + 2 √ mǫ 2 (σ min ) 3/2 ǫ 3 + µ 3 max ≤ 2ǫ 2 m σ min 3/2 1 Γ σ + 1 σ min ǫ 3 + µ 3 max .
(11)

Likewise one can prove the following perturbation bounds for M 3 (W, W -W , W ) and M 3 (W, W -W , W ):

M 3 (W, W -W , W ) ≤ 2 √ 2ǫ 2 m σ min 3/2 1 Γ σ + 1 σ min ǫ 3 + µ 3 max M 3 (W -W , W , W ) ≤ 4ǫ 2 m σ min 3/2 1 Γ σ + 1 σ min ǫ 3 + µ 3 max . (12)
The result then follows by plugging the bounds of Eq. 10, Eq. 11 and Eq. 12 into Eq. 9.

We now prove high-probability bounds on ǫ 3 and ǫ 2 when M 2 and M 3 are estimated by sampling.

Lemma 7. For any δ ∈ (0, 1), if M 2 and M 3 are computed with samples from j episodes, then we that with probability 1δ:

ǫ 3 ≤ K 1.5 6 log(2K/δ) j and ǫ 2 ≤ 2K log(2K/δ) j .
Proof. Using some norm inequalities for the tensors we obtain

ǫ 3 = M 3 -M 3 ≤ K 1.5 M 3 -M 3 max = K 1.5 max i,j,x |[M 3 ] i,j,x -[ M 3 ] i,j,x |.
A similar argument leads to the bound of

K max i,j |[M 2 ] i,j -[ M 2 ] i,j | on ǫ 2 .
One can easily show that, for every 1 ≤ i, j, x ≤ K, the term [M 3 ] i,j,x -[ M 3 ] i,j,x and [M 3 ] i,j,x -[ M 3 ] i,j,x can be expressed as a sum of martingale differences with the maximum value 1/j. The result then follows by applying the Azuma's inequality (e.g., see Cesa-Bianchi and Lugosi, 2006, appendix, pg. 361) and taking the union bound.

We now draw our attention to the proof of our main result.

Proof of Thm. 2. We begin by deriving the condition of Eq. 5. The assumption on ǫ 2 in Lem. 6 and the result of Lem. 7 hold at the same time, w.p. 1δ, if the following inequality holds

2K log(2K/δ) j ≤ 1/2 min(Γ σ , σ min ).
By solving the bound w.r.t. j we obtain

j ≥ 16K 2 log(2K/δ) min(Γ σ , σ min ) 2 . ( 13
)
A similar argument applies in the case of the assumption on ǫ in Thm. 5. The results of Thm. 5 and Lem. 6 hold at the same time if we have

ε ≤ mK σ min 3/2 20ǫ 2 1 Γ σ + 1 σ min + ǫ 3 ≤ C 1 λ min m ,
where in the first inequality we used that ε 3 ≤ K 3/2 and µ 3 max ≤ K 3/2 by their respective definitions. This combined with high probability bounds of Lem. 7 on ǫ 1 and ǫ 2 implies m σ min 1.5 20K 2.5 log(4K/δ) j

1 Γ σ + 1 σ min + K 1.5 6 log(4K/δ) j ≤ C 1 λ min m .
By solving this bound w.r.t. j (and some simplifications) we obtain w.p. 1δ j ≥ 43 2 m 5 K 6 log(4K/δ)

C 1 σ 3 min λ 2 min 1 Γ σ + 1 σ min 2 .
Combining this result with that of Eq.13 and taking the union bound leads to the bound of Eq. 5 on the minimum number of samples.

We now draw our attention to the main result of the theorem. We begin by bounding µ(θ)µ(π(θ)) in terms of estimation error term ǫ 3 and ǫ 2 :

µ(θ) -µ(π(θ)) = λ(θ)Bv(θ) -λ(π(θ)) B v(π(θ)) ≤ (λ(π(θ)) -λ(θ))Bv(π(θ)) + λ(θ)(B -B)v(π(θ)) + λ(θ) B(v(π(θ)) -v(θ)) ≤|λ(θ) -λ(π(θ))| B + λ(π(θ)) B -B + λ(π(θ)) B v(θ) -v(π(θ)) , (14)
where in the last line we rely on the fact that both v(θ) and v(π(θ)) are normalized vectors. We first bound the term B -B :

B -B = U D 1/2 -U D 1/2 ≤ (U -U )D 1/2 + U (D 1/2 -D 1/2 ) (1) ≤ 2 √ mǫ 2 σ max Γ σ + √ mǫ 2 σ max ≤ √ mǫ 2 2σ max Γ σ + 1 σ max ,
where in (1) we make use of the result of Lem. 5. Furthermore, we have

B = U D 1/2 ≤ m σ max ≤ √ m(σ 1/2 max + ǫ 1/2 2 ) ≤ √ m(σ 1/2 max + σ 1/2 min ) ≤ √ 2mσ max ,
where we used the condition on ǫ 2 . This combined with Eq.14 and the result of Thm 5 and Lem. 6 implies µ(π(θ))µ(θ)

(1)

≤ 5 √ mσ max ǫ + √ mǫ 2 (λ(θ) + ǫ) 2σ max Γ σ + 1 σ max + 8ǫ λ(θ) √ 2mσ max (λ(θ) + ǫ) (2) ≤ 5 √ mσ max ǫ + √ mǫ 2 λ(θ) + 5C 1 σ min m 2σ max Γ σ + 1 σ max + 8 √ 2mσ max 1 + 5C 1 σ min m ǫ ≤ 5 √ mσ max m σ min 3/2 10ǫ 2 1 Γ σ + 1 σ min ǫ 3 + µ 3 max + ǫ 3 + √ mǫ 2 λ(θ) + 5C 1 σ min m 2σ max Γ σ + 1 σ max + 8 √ 2mσ max 1 + 5C 1 m m σ min 3/2 10ǫ 2 1 Γ σ + 1 σ min ǫ 3 + µ 3 max + ǫ 3 .
where in (1) we used ||B|| ≤ √ mσ max , the bound on λ(π(θ)) ≤ λ(θ) + 5ǫ, v(θ)v(π(θ)) ≤ 8ǫ/λ(θ), in (2) we used λ(θ) = 1/ ρ(θ) ≥ 1 and the condition that ε ≤ 5C 1 σ min /m. The result then follows by combining this bound with the high probability bound of Lem. 7 and taking union bound as well as collecting the terms.

D Proofs of Section 4.3

Lemma 8. At episode j, the arms i / ∈ A j * (Θ; θj ) are never pulled, i.e., T i,n = 0. Lemma 9. If umUCB is run with

ε i,t = 1 2T i,t-1 log 2mKn 2 δ , ε j = C(Θ) 1 j log 2mKJ δ , (15)
where C(Θ) is defined in Thm. 2, then the event

E = E 1 ∩ E 2 is such that P[E] ≥ 1 -δ where E 1 = {∀θ, t, i, |μ i,t -µ i (θ)| ≤ ε i,t } and E 2 = {∀j, θ, i, |μ j i (θ) -µ i (θ)| ≤ ε j }.
Notice that the event E implies that for any episode j and step t, the actual model is always in the active set, i.e., θj ∈ Θ j t . Lemma 10. At episode j, all the arms i / ∈ A j + (Θ j + ( θj ); θj ) are never pulled on event E, i.e., T i,n = 0 with probability 1δ.

Lemma 11. At episode j, the arms i ∈ A j + (Θ j + ( θj ); θj ) are never pulled more than with a UCB strategy, i.e.,

T j i,n ≤ 2 ∆ i ( θj ) 2 log 2mKn 2 δ + 1, (16)
with probability 1δ.

Notice that for UCB the logarithmic term in the previous statement would be log(Kn 2 /δ) which would represent a negligible constant fraction improvement w.r.t. umUCB whenever the number of models is of the same order of the number of arms.

Lemma 12. At episode j, for any model θ ∈ (Θ j + ( θj ) -Θ j ( θj )) (i.e., an optimistic model that can be discarded), the number of pulls to any arm i ∈ A j + (θ; θj ) needed before discarding θ is

T j i,n ≤ 1 2 Γ i (θ, θj )/2 -ε j 2 log 2mKn 2 δ + 1, (17)
with probability 1δ.

Proof of Lem. 8. We first notice that the algorithm only pulls arms recommended by a model θ ∈ Θ j t . Let î * (θ) = arg max i B j t (i; θ) with θ ∈ Θ j t , and i ∈ A j * (θ; θj ). According to the selection process, we have B j t (i; θ) < B j t ( î * ; θ). Since θ ∈ Θ j t we have that for any i, |μ i,tμj i (θ)| ≤ ε i,t +ε j which leads to μj i (θ)-ε j ≤ μi,t +ε i,t . Since μj i (θ)ε j ≤ μj i (θ) + ε j , then we have that μj i (θ)ε j ≤ min{μ i,t + ε i,t , μj i (θ) + ε j } = B j t (i; θ). Furthermore from the definition of the B-values we deduce that

B j t ( î * ; θ) ≤ μj î * (θ) + ε j .
Bringing together the previous inequalities, we obtain

μj i (θ) -ε j ≤ μj î * (θ) + ε j .
which is a contradiction with the definition of non-dominated arms A j * (Θ; θj ).

Proof of Lem. 9. The probability of E 1 is computed in Lem. 2 with the difference that now we need an extra union bound over all the models and that the union bound over the arms cannot be restricted to the number of models. The probability of E 2 follows from Thm. 2.

Proof of Lem. 10. We first recall that on event E, at any episode j, the actual model θj is always in the active set Θ j t . If an arm i is pulled, then according to the selection strategy, there exists a model θ ∈ Θ t such that B j t (i; θ) ≥ B j t ( î * ( θj ); θj ). Since î * ( θj ) = arg max i B j t (i; θj ), then B j t ( î * ( θj ); θj ) ≥ B j t (i * ( θj ); θj ) where i * ( θj ) is the true optimal arm of θj . By definition of B(i; θ), on event E we have that B j t (i * ( θj ); θj ) ≥ µ * ( θj ) and that B j t (i; θ) ≤ μj i (θ) + ε j . Grouping these inequalities we obtain μj i (θ) + ε j ≥ µ * ( θj ), which, together with Lem. 8, implies that i ∈ A j + (θ; θj ) and that this set is not empty, which corresponds to θ ∈ Θ j + ( θj ).

Proof of Lem. 11. Let t be the last time arm i is pulled (T i,t-1 = T i,n + 1), then according to the selection strategy we have B j t (i; θ j t ) ≥ B j t ( î * ( θj ); θj ) ≥ B j t (i * ; θj ), where i * = i * ( θj ). Using the definition of B, we have that on event E B j t (i * ( θj ); θj ) = min (μ j i * ( θj ) + ε j ); (μ i * ,t + ε i * ,t ) ≥ µ * ( θj ) and B j t (i; θ j t ) ≤ μi,t + ε i,t ≤ µ i ( θj ) + 2ε i,t . Bringing the two conditions together we have µ i ( θj ) + 2ε i,t ≥ µ * ( θj ) ⇒ 2ε i,t ≥ ∆ i ( θj ), which coincides with the (high-probability) bound on the number of pulls for i using a UCB algorithm and leads to the statement by definition of ε i,t .

Proof of Lem. 12. According to Lem. 10, a model θ can only propose arms in A j + (θ; θj ). Similar to the analysis of mUCB, θ is discarded from Θ j t with high probability after t steps and j episodes if 2(ε i,t + ε j ) ≤ Γ i (θ, θj ).

At round j, if ε j ≥ Γ i (θ, θj )/2 then the algorithm will never be able to pull i enough to discard θ (i.e., the uncertainty on θ is too large), but since i ∈ A j * (θ; θj ), this corresponds to the case when θ ∈ Θ j ( θj ). Thus, the condition on the number of pulls to i is derived from the inequality ε i,t ≤ Γ i (θ, θj )/2ε j .

E Related Work

As discussed in the introduction, transfer in online learning has been rarely studied. In this section we review possible alternatives and a series of settings which are related to the problem we consider in this paper.

Models estimation.

Although in tUCB we use RTP for the estimation of the model means, a wide number of other algorithms could be used, in particular those based on the method of moments (MoM). Recently a great deal of progress has been made regarding the problem of parameter estimation in LVM based on the method of moments approach (MoM) (Anandkumar et al., 2012c,a,b).

The main idea of MoM is to match the empirical moments of the data with the model parameters that give rise to nearly the same corresponding population quantities. In general, matching the model parameters to the observed moments may require solving systems of high-order polynomial equations which is often computationally prohibitive. However, for a rich class of LVMs, it is possible to efficiently estimate the parameters only based on the low-order moments (up to the third order) (Anandkumar et al., 2012c). Prior to RTP various scenarios for MoM are considered in the literature for different classes of LVMs using different linear algebra techniques to deal with the empirical moments Anandkumar et al. (2012c,a). The variant introduced in (Anandkumar et al., 2012c, Algorithm B) recovers the matrix of the means {µ(θ)} up to a permutation in columns without any knowledge of ρ. Also, theoretical guarantees in the form of sample complexity bounds with polynomial dependency on the parameters of interest have been provided for this algorithm. The excess correlation analysis (ECA) (Alg. 5 in Anandkumar et al. (2012a)) generalizes the idea of the MoM to the case that ρ is not fixed anymore but sampled from some Dirichlet distribution. The parameters of this Dirichlet distribution is not to be known by the learner. 6 In this case again we can apply a variant of MoM to recover the models.

Online Multi-task. In the online multi-task learning the task change at each step (n = 1) but at the end of each step both the true label (in the case of online binary classification) and the identity of the task are revealed. A number of works [START_REF] Dekel | Online multitask learning[END_REF][START_REF] Saha | Online learning of multiple tasks and their relationships[END_REF][START_REF] Cavallanti | Linear algorithms for online multitask classification[END_REF][START_REF] Lugosi | Online multi-task learning with hard constraints[END_REF] focused on this setting and showed how the samples coming from different tasks can be used to perform multi-task learning and improve the worst-case performance of an online learning algorithm compared to using all the samples separately.

Contextual Bandit. In contextual bandit (e.g., see [START_REF] Agarwal | Contextual bandit learning with predictable rewards[END_REF][START_REF] Langford | The epoch-greedy algorithm for multi-armed bandits with side information[END_REF], at each step the learner observes a context x t and has to choose the arm which is best for the context. The contexts belong to an arbitrary (finite or continuous) space and are drawn from a stationary distribution. This scenario resembles our setting where tasks arrive in a sequence and are drawn from a ρ. The main difference is that in our setting the learner does not observe explicitly the context and it repeatedly interact with that context for n steps. Furthermore, in general in contextual bandits some similarity between contexts is used, while here the models are completely independent.

Non-stationary Bandit. When the learning algorithm does not know when the actual change in the task happens, then the problem reduces to learning in a piece-wise stationary environment. [START_REF] Garivier | On upper-confidence bound policies for switching bandit problems[END_REF] introduces a modified version of UCB using either a sliding window or discounting to track the changing distributions and they show, when optimally tuned w.r.t. the number of switches R, it achieves a (worst-case) expected regret of order O( √ T R) over a total number of steps T and R switches. Notice that this could be also considered as a partial transfer algorithm. Even in the case when the switch is directly observed, if T is too short to learn from scratch and to identify similarity with other previous tasks, one option is just to transfer the averages computed before the switch. This clearly introduces a transfer bias that could be smaller than the regret cumulated in the attempt of learning from scratch. This is not surprising since transfer is usually employed whenever the number of samples that can be collected from the task at hand is relatively small. If we applied this algorithm to our setting T = nJ and R = J, the corresponding performance would be O(J √ n), which matches the worst-case performance of UCB (and tUCB as well) on J tasks. This result is not surprising since the advantage of knowing the switching points (every n steps) could always be removed by carefully choosing the worst possible tasks. Nonetheless, whenever we are not facing a worst case, the non-stationary UCB would have a much worse performance than tUCB. In Table 1 we report the actual values of the means of the arms of the models in Θ, while in Table 2 we compare the complexity of UCB, UCB+, and mUCB, for all the different models and on average. Finally, the graphs in Fig. 9 are an extension up to J = 10000 of the performance of tUCB for n = 5000 reported in the main text.

F Numerical Simulations

Figure 1 :

 1 Figure 1: The mUCB algorithm.

Figure 2 :

 2 Figure 2: The tUCB algorithm.

Figure 3 :

 3 Figure 3: The umUCB algorithm. Require: samples R ∈ R j×n , number of models m and arms K, episode j Estimate the second and third moment M2 and M3 using the reward samples from R (Eq. 4) Compute D ∈ R m×m and U ∈ R K×m (m largest eigenvalues and eigenvectors of M2 resp.) Compute the whitening mapping W = U D -1/2 and the tensor T = M3( W , W , W ) Plug T in Alg. 1 of Anandkumar et al. (2012b) and compute eigen-vectors/values {v(θ)}, { λ(θ)} Compute µ j (θ) = λ(θ)( W T ) + v(θ) for all θ ∈ Θ return Θ j+1 = { µ j (θ) : θ ∈ Θ}

Figure 7 :

 7 Figure 5: Set of models Θ.

Figure 8 :

 8 Figure 8: Per-episode regret of tUCB.

Figure 9 :

 9 Figure 9: Complexity and per-episode regret of tUCB over tasks.

  Arm gap of an arm i for a model θ Γi(θ, θ ′ ) Model gap for an arm i between two models θ and θ ′

	Symbol	Explanation
	A	Set of arms
	Θ	Set of models
	K	Number of arms
	m	Number of models
	J	Number of episodes
	n	Number of steps per episode
	t θ	Time step Current model
	Θt	Active set of models at time t
	νi	Distribution of arm i
	µi(θ)	Mean of arm i for model θ
	µ(θ) μi,t	Vector of means of model θ Estimate of µi( θ) at time t
	μj
	Θ j	Estimated model of RTP after j episode
	ε j	Uncertainty of the estimated model by RTP at episode j
	εi,t	Model uncertainty at time t
	δ	Probability of failure
	i * (θ)	Best arm of model θ
	µ * (θ)	Optimal value of model θ
	∆i(θ)
	M2	2 nd -order moment
	M3	3 rd -order moment
	M2	Empirical 2 nd -order moment
	M3	Empirical 3 rd -order moment
	•	Euclidean norm
	• F	Frobenius norm
	• max	Matrix max-norm
	RJ	Pseudo-regret
	T j i,n A * (Θ ′ ) Θ(A ′ ) Θ+	The number of pulls to arm i after n steps of episode j Set of arms which are optimal for at least a model in a set Θ ′ Set of models for which the arms in A ′ are optimal Set of optimistic models for a given model θ
	A+	Set of optimal arms corresponds to Θ+
	W	Whitening matrix of M2
	W	Empirical whitening matrix
	T	M2 under the linear transformation W
	T	M2 under the linear transformation W
	D	Diagonal matrix consisting of the m largest eigenvalues of M2
	D	Diagonal matrix consisting of the m largest eigenvalues of M2
	U	K × m matrix with the corresponding eigenvectors of D as its columns
	U	K × m matrix with the corresponding eigenvectors of D as its columns
	λ(θ)	Eigenvalue of T associated with θ
	v(θ)	Eigenvector of T associated with θ
	λ(θ)	Eigenvalue of T associated with θ
	v(θ)	Eigenvector of T associated with θ
	ΣM 2	Set of m largest eigenvalues of the matrix M2
	σmin	Minimum eigenvalue of M2 among the m-largest
	σmax	Maximum eigenvalue of M2
	λmax	Maximum eigenvalue of T
	Γσ	Minimum gap between the eigenvalues of M2
	C(Θ)	O λmax σmax σ 3 min

i (θ) Estimate of µi(θ) by RTP for model θ and arm i at episode j µ j (θ)

Estimate of µ(θ) by RTP for model θ at episode j

Table 1 :

 1 Models.

		Arm1 Arm2 Arm3 Arm4 Arm5 Arm6 Arm7
	θ1	0.9	0.75	0.45	0.55	0.58	0.61	0.65
	θ2	0.75	0.89	0.45	0.55	0.58	0.61	0.65
	θ3	0.2	0.23	0.45	0.35	0.3	0.18	0.25
	θ4	0.34	0.31	0.45	0.725	0.33	0.37	0.47
	θ5	0.6	0.5	0.45	0.35	0.95	0.9	0.8
				UCB UCB+ mUCB
			θ1 22.31	14.87	2.33
			θ2 23.32	15.58	8.48
			θ3 33.91	25.21	2.08
			θ4 17.91	11.17	3.48
			θ5 35.41	8.76	0
			avg 26.57	15.11	3.27

Table 2 :

 2 Complexity of UCB, UCB+, and mUCB.

Notice that estimating the models involves solving a latent variable model estimation problem, for which RTP is the state-of-the-art.

Notice that 1/3([µ 1l ]i + [µ 2l ]i + [µ 1l ]i) = μl i,n, the empirical mean of arm i at the end of episode l.

The matrix W ∈ R K×m is such that M2( W , W ) = I m×m , i.e., W is the whitening matrix of M2. In general W is not unique. Here, we choose W = U D -1/2 , where D ∈ R m×m is a diagonal matrix consisting of the m largest eigenvalues of M2 and U ∈ R K×m has the corresponding eigenvectors as its columns.

Notice that although Θ satisfies Assumption 1, the smallest singular value σmin = 0.0039 and Γσ = 0.0038, thus making the estimation of the models difficult.

For instance, for UCB we compute i 1/∆i.

We only need to know sum of the parameters of the Dirichlet distribution α0.

Acknowledgments. This research was supported by the National Science Foundation (NSF award #SBE-0836012). We would like to thank Sham Kakade and Animashree Anandkumar for valuable discussions. A. Lazaric would like to acknowledge the support of the Ministry of Higher Education and Research, Nord-Pasde-Calais Regional Council and FEDER through the' Contrat de Projets Etat Region (CPER) 2007-2013', and the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement 231495 (project CompLACS).