Aditya Gopalan
email: aditya@ece.iisc.ernet.

Odalric-Ambrym Maillard
email: odalricambrym.maillard@

Mohammadi Zaki
email: zaki@ece.iisc.ernet.

Low-rank Bandits with Latent Mixtures

Keywords: Multi-armed bandits, online learning, low-rank matrices, recommender systems, reinforcement learning

. We provide the first rigorous regret analysis of this combination, showing that its regret after T user interactions is Õ(C √ BT ), with B the number of users. An ingredient towards this result is a novel robustness property of OFUL, of independent interest.

Introduction

Recommender systems aim to provide targeted, personalized content recommendations to users by learning their responses over time. The underlying goal is to be able to predict which items a user might prefer based on preferences expressed by other related users and items, also known as the principle of collaborative filtering.

A popular approach to model preferences expressed by users in recommender systems is via probabilistic mixture models or latent class models [START_REF] Hofmann | Latent class models for collaborative filtering[END_REF][START_REF] Kleinberg | Using mixture models for collaborative filtering[END_REF]. In such a mixture model, we have a set of A items (content) that can be recommended to B users (consumers). Whenever item a is recommended to user b, the system gains an expected reward of r a,b . The key structural assumption that captures the relationship between users' preferences is that there exists a set of latent set of C representative user types or typical taste profiles. 1 Formally, each taste profile c is a unique vector u c ≡ (u a,c ) a of the expected rewards that every item a elicits under the taste profile. Each user b is assumed to sample one of the typical profiles randomly using an individual probability distribution v b ≡ (v b,c ) c ; its reward distribution across the items subsequently becomes that induced by the assumed profile.

Our focus is to address the sequential optimization of net reward gained by the recommender, without any prior knowledge of either the latent user classes or users' mixture distributions. Assuming that users arrive to the system repeatedly following an unknown stochastic process and re-sample their profiles over time, according to their respective unknown mixtures across latent classes, we seek online learning strategies that can achieve low regret relative to the best single item that can be recommended to each user. Note that this is qualitatively different than the task of estimating latent classes or user mixtures in a batch fashion, well-studied by now (Sutskever et al., 2009;Anandkumar et al., 2014a,b); the task of simultaneously optimizing net utility in a bandit fashion in complex expression models like these has received little or no analytical treatment. Our work takes a step towards filling this void.

An especially challenging aspect of online learning in recommender systems is the relatively meager number of available interactions with a same user, which is offset to an extent by the assumption that users can only have a limited number of taste profiles (classes). Indeed, if one can identify the class to which a certain user belongs and aggregate information from all other users in that class, then one can recommend to the user the best item for the class. In practice, classes are latent and not necessarily known in advance, and several works [START_REF] Gentile | Online clustering of bandits[END_REF][START_REF] Lazaric | Sequential transfer in multi-armed bandit with finite set of models[END_REF][START_REF] Maillard | Latent bandits[END_REF] study the restricted situation when each user always belongs to one specific class (i.e., when all mixture distributions have support size 1). We go two steps further, since in many situations (a) users cannot be assumed to belong to one class only, such as when a user account is shared by several individuals (e.g. a smart-TV), and (b) the duration of a user-session, that is the number of consecutive recommendations to the same individual connected to a user-account, cannot assumed to be long 1 .

The key challenges that this work addresses are (1) the lack of knowledge of "features" on both the user-side and item-side in a linear bandit problem (in this case, both the user mixture weights and the item class reward profiles) and (2) provable regret minimization with very few i.e. O(1) interactions with every user b having a specific taste profile, as opposed to a large number of interactions such as in transfer learning [START_REF] Lazaric | Sequential transfer in multi-armed bandit with finite set of models[END_REF].

Contributions and overview of results. We consider a setting when users are assumed to come from arbitrary mixtures across classes (they are not assumed to fall perfectly in one class as was the assumption in works by [START_REF] Gentile | Online clustering of bandits[END_REF]; [START_REF] Maillard | Latent bandits[END_REF]). We develop a novel bandit algorithm (Algorithm 3) that combines (a) the Optimization in the Face of Uncertainty Linear bandit OFUL algorithm [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF] for bandits with known action features, and (b) a variant of the Robust Tensor Power (RTP) algorithm [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF] that uses only bandit (partial) estimates of latent user classes with observations coming from a mixture model. More specifically, we introduce a subroutine (Algorithm 1) that makes use of the RTP method to extract item-side attributes (U ) and, contributing to its theoretical analysis, show a recovery property (Theorem 1). Note that the RTP method ideally requires (unbiased) estimates of the 2nd and 3rd order moments of actions' rewards, but with bandit information the learner can access only partial reward information, i.e., a single reward sample from an action. To overcome this, we devise an importance sampling scheme across 3 successive time instants to build the 2nd and 3rd order moment tensor estimates that RTP uses. For the task of issuing recommendations, we develop an algorithm (section 4), essentially based on OFUL, instantiated per user, using for each a the estimated latent class vectors {u a,c } c (obtained via the RTP subroutine) as arm features, and uncertain parameter vector to be learned v b .

We carry out a rigorous analysis of the algorithm and show that it achieves regret Õ(ℓC √ BT ) in T rounds of interaction (Theorem 4), provided each arriving user interacts with the system for ℓ 3 rounds with the same profile. In comparison, the regret of the strategy that completely disregards the latent mixture structure of rewards and employs a standard bandit strategy (e.g. UCB [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]) per user, scales as O(B T A/B) = O( √ ABT ) after T rounds2 , which is considerably suboptimal in the practical case with a very large number of items but very few representative user classes (C ≪ A). It is also worth noting that the regret bound we achieve, order-wise, is what would result from applying the OFUL or any optimal linear bandit algorithm assuming a priori knowledge of all latent user classes {u a,c } a,c , that is Õ(ℓC √ BT ). In this sense, our result shows that one can simultaneously estimate features on both sides of a bilinear reward model and achieve regret performance equivalent to that of a one-sided linear model, which is the first result of its kind to the best of our knowledge3 . Our results are presented for finite time horizons with explicit details of the constants arising from the error analysis of RTP, which at this point are large but possibly improvable.

En route to deriving the regret for our algorithm, we also make a novel contribution that advances the theoretical understanding of OFUL, and which is of independent interest. We show that in the standard linear bandit setting, where the expected reward of an arm linearly depends on d features, OFUL yields (sub-linear) Õ ρd √ T regret even when it makes decisions based on perturbed or inexact feature vectors (Theorem 3), where ρ quantifies the distortion. This property holds whenever the perturbation error is small enough, and we explicitly give both (a) a sufficient condition on the size of the perturbation in terms of the set of actual features, and (b) a bound on the (multiplicative) distortion ρ in the regret due to the perturbation (note that ρ = 1 in the ideal linear case).

Setup and notation

For any positive integer n, [n] denotes the set {1, 2, . . . , n}.

At each n ∈ N, nature selects a user b n ∈ [B] according to the probability distribution β over [B], independent of the past, and b n is revealed to the learner. A user class c n is subsequently sampled from the probability distribution v bn over [C], and c n (the assumed class of user b n ) interacts with the learner for the next ℓ 3 consecutive steps. Such an interaction will often be termed a mini-session.

In each step l ∈ [ℓ] of a mini-session, the learner plays an action (issues a recommendation) a n,l ∈ [A] and subsequently receives reward Y n,l = u a n,l ,cn + η n,l , where η n,l is a (centered) R-sub-Gaussian i.i.d. random variable independent from a n,l , c n , representing the noise in the reward. We let u a ∈ R C represent the vector (u a,c ) c∈[C] of the mean rewards from action a in each class. Note that

E[u a n,l ,cn |a n,l ] = E[u ⊤ a n,l v bn |a n,l ].
For convenience, we use the index notation t ≡ (n, l) and introduce T = N ℓ, where N is the total number of mini-sessions, and T the total number of interactions of the learner with the system. We denote likewise Y t , a t , c t , η t for Y n,l , a n,l , c n , η n,l , and let

u max def = max a∈[A],c∈[C] |u a,c |.
We are interested in designing an online recommendation strategy, i.e., one that plays actions depending on past observations, achieving low (cumulative) regret after T ≡ (N, ℓ) mini-sessions,

defined as R T def = n∈[N ],l∈[ℓ] r n,l , where r n,l def = max a∈[A] u ⊤ a v bn -u ⊤ a n,l v bn .
In other words, we wish to compete against a strategy that plays for every user an action yielding the highest reward in expectation under its mixture distribution over user classes.

Recovering latent user classes: The EstimateFeatures subroutine

In this section, we provide an estimation algorithm for the matrix U , using the RTP method. 4

Estimation of tensors. We assume that in mini-session n, when interacting with user b n , the triplet {a n,l } l ℓ is chosen from a distribution p n (a, a ′ , a ′′ |b n ). Letting X a n,l ,bn,n,l def = Y n,l = u a n,l ,cn + η n,l to explicitly indicate the active user and action chosen at (n, l), we form the importance-weighted estimates

ra,a ′ ,n def = 1 n n i=1 X ai,1,bi,i,1 X ai,2,bi,i,2 p i (a, a ′ |b i ) I{a i,1 = a, a i,2 = a ′ }, ra,a ′ ,a ′′ ,n def = 1 n n i=1 X ai,1,bi,i,1 X ai,2,bi,i,2 X ai,3,bi,i,3 p i (a, a ′ , a ′′ |b i ) I{a i,1 = a, a i,2 = a ′ , a i,3 = a ′′ } .
for the second and third-order tensors 5 . We introduce the matrices

M n,2 ≡ (r a,a ′ ,n ) a,a ′ ∈[A] and M 2 ≡ (m a,a ′ ) a,a ′ ∈[A] with m a,a ′ def = E[r a,a ′ ,n ],
and the tensors

M n,3 ≡ (r a,a ′ ,a ′′ ,n ) a,a ′ ,a ′′ ∈[A] and M 3 ≡ (m a,a ′ ,a ′′ ) a,a ′ ,a ′′ ∈[A] with m a,a ′ ,a ′′ def = E[r a,a ′ ,a ′′ ,n ].
The following result decomposes the matrix M 2 and tensor M 3 as weighted sums of outer products.

Lemma 1 When the user arrivals are i.i.d. according to the law

β, i.e., b i i.i.d ∼ β ∀i ∈ [n], it holds that m a,a ′ ,n = c∈[C] v β,c u a,c u a ′ ,c , and m a,a ′ ,a ′′ ,n = c∈[C] v β,c u a,c u a ′ ,c u a ′′ ,c .
Having shown the unbiasedness of the empirical 2nd and 3rd moment tensors M n,2 and M n,3 , we next turn to showing concentration to their respective means. Lemma 2 Assuming that p i (a, a ′ |b i ) q 2,i and p i (a, a ′ , a ′′ |b i ) q 3,i for deterministic q 2,i , q 3,i , for all i ∈ N, a, a ′ , a ′′ ∈ [A], then for all n N , with probability higher than 1 -δ, it holds simultaneously for all a, a ′ , a ′′ that

|r a,a ′ ,n -m a,a ′ ,n | n i=1 q -2 2,i log(4A 2 /δ) 2n 2 , |r a,a ′ ,n -m a,a ′ ,a ′′ ,n | n i=1 q -2 3,i log(4A 3 /δ) 2n 2 .
An immediate corollary is the following one:

Corollary 1 Provided that q 2,i = γ i /A 2 and q 3,i = γ i /A 3 for some γ i > 0, then on an event of probability higher than 1 -δ, the following hold simultaneously:

e (2) n def = M n,2 -M 2 A 3 n i=1 γ -2 i log(4A 2 /δ) 2n 2 , e (3)
n def = M n,3 -M 3 A 9/2 n i=1 γ -2 i log(4A 3 /δ) 2n 2 .
4. We consider ℓ = 3 to describe the algorithm; ℓ > 3 is easily handled by repeating the 3-wise sampling p(a, a ′ , a ′′ ) for ⌊ℓ/3⌋ times and discarding the remaining (< 3) steps in the mini-session during exploration (leading to a negligible regret overhead). 5. An alternative is the implicit exploration method due to [START_REF] Kocák | Efficient learning by implicit exploration in bandit problems with side observations[END_REF].

Algorithm 1 EstimateFeatures

1: Input: #sessions n; #mini-sessions ℓ;

(user, action, reward) tuples

(b i , a i,l , X a i,l ,b i ,i,l ) 1 i n,1 l ℓ . 2: Compute the A × A matrix M n,2 = (r a,a ′ ,n ) a,a ′ ∈[A] and the A × A × A tensor M n,3 = ( r a,a ′ ,a ′′ , ) a,a ′ ,a ′′ ∈[A] . 3: Compute a A × C whitening matrix W n of M n,2 {Take W n = U n D -1/2 n
where D n is the C × C diagonal matrix with the top C eigenvalues of M n,2 , and U n the A × C matrix of corresponding eigenvectors.}

4: Form the C × C × C tensor T n = M n,3 ( W n , W n , W n ).
5: Apply the RTP algorithm [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF] to T n , and compute its robust eigenvalues

( λ n,c ) c∈[C] with eigenvectors ( ϕ n,c ) c∈[C] .
{The paper of Anandkumar et al. (2014b, Sec. 4) defines eigenvalues/eigenvectors of tensors.}

6: Compute for each c ∈ [C], u n,c = λ n,c ( W ⊤ n ) † ϕ n,c and v n,c = λ -2 n,c
. 7: Output: Estimate of latent classes U : The A × C matrix U n obtained by stacking the vectors u n,c ∈ R A side by side.

Reconstruction algorithm. The EstimateFeatures algorithm (Algorithm 1) employs a whitening matrix W n , of the empirical estimate of the matrix M 2 , to build the empirical tensor T n . This tensor is then used to recover the columns of the matrix U = (u a,c ) a∈[A],c∈[C] via the RTP algorithm. For the sake of completeness, we also introduce W , a whitening matrix of M 2 (i.e., W T M 2 W = I), the corresponding tensor T = M 3 (W, W, W ), and finally the estimation error Lemma 1 gives a decomposition of the (symmetric) tensor M 3 , but it may be not orthogonal; standard transformation (Anandkumar et al., 2014b, Sec. 4.3) gives an orthogonal decomposition for the tensor 6 M 3 (W, W, W ), with W a matrix that whitens M 2 . We can thus use Proposition 1 6. For a 3rd order tensor A ∈ R a×a×a and 2nd order tensor or matrix B ∈ R a×b , A(B, B, B) ∈ R b×b×b is the 3rd order tensor defined by [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF] for more details on notation and results.

[A(B, B, B)]i 1 ,i 2 ,i 3 def = j 1 ,j 2 ,j 3 ∈[n] Aj 1 ,j 2 ,j 3 Bj 1 ,i 1 Bj 2 ,i 2 Bj 3 ,i 3 . See
with T = M 3 (W, W, W ), T = T n , ε = e n and η = δ in order to prove the following guarantee (Theorem 1) on the recovery error between columns of U and their estimate.

We now introduce mild separability conditions on the mixture weights v b and the spectrum of the 2nd moment matrix M 2 needed for the reconstruction guarantee to hold, similar to those assumed for Lazaric et al. (2013, Theorem 2).

Assumption 1 There exist positive constants v min , σ min , σ max and Γ such that

min b∈[B],c∈[C] v b,c v min , ∀c ∈ [C], σ c = λ c (M 2 ) ∈ [σ min , σ max ] and min c =c ′ ∈[C]×[C] |σ c -σ c ′ | Γ ,
where λ c (A) denotes the c th top eigenvalue of A.

Theorem 1 (Recovery guarantee for online estimation of user classes U ) Let Assumption 1 hold, and let δ ∈ (0, 1). If the number of mini-session satisfies

n 2 n i=1 γ -2 i max 2A 6 log(4A 2 /δ) min{Γ, σ min } 2 , A 9 (1 + 10( 1 Γ + 1 σmin )(1 + u 3 max )) 2 C 5 log(4A 3 /δ) 2C 2 1 σ 3 min ,
then with probability at least 1 -2δ, there exists some permutation π ∈ S C such that for all c ∈ [C], the output Ūn of the EstimateFeatures algorithm satisfies

||u c -u n,π(c) || A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2 . ( 1
)
where u c = (u a,c ) a∈ [A] . Here, the constant (we use the "diamond" symbol to denote it) is

= CA σ min 3/2 13 √ σ max + 4 2 min{Γ, σ min } + 5 σ max Γ + 1 2σ max min{Γ, σ min } ℵ + 2σ max Γ + 1 σ max 1 v 2 min + 5 3/8 √ σ max + min{Γ, σ min }/2 2CA σ min 3 ℵ 2 min{Γ, σ min } , with the notation ℵ = 1 + 10( 1 Γ + 1 σmin )(1 + u 3 max ).
The proof strategy follows that of Lazaric et al. (2013, Theorem 2) and is detailed in the appendix for clarity. It consists in relating, on the one hand, the estimation errors e , and, on the other hand, relating the reconstruction error on the columns of U to the control on the terms |λ c -λ π(c) | and ||ϕ c -ϕ π(c) || coming from Proposition 1. We note that the bound appearing in the condition on the number of mini-sessions is potentially large (due to the terms A 6 , C 5 , etc.). This is due to the combination of the RTP method with the importance sampling scheme, and it remains unclear if the bound can be significantly improved within this framework.

Recovering latent mixture distributions (v b ): robustness of the OFUL algorithm

In order to recover the weights vectors v b ∈ R C and thus the matrix V , it would be tempting to use again an instance of the RTP method but this time to aggregate across actions, i.e., by forming a B × B and B × B × B tensor. Unfortunately, aggregation of elements of U fails for two reasons: First, we do not have different views across users b, contrary to what we have for actions a. It is thus hopeless to be able to form an estimate of the 2nd and 3rd moment tensors as before. Second, and rather technically, convex combinations of the {u a,c } a∈ [A] need not be positive. This prevents the application of the RTP method which requires positive weights to work.

We thus consider a different strategy that uses an algorithm designed for linear bandits. However since the feature matrix U is unknown a priori and can only be estimated, we need to work with perturbed features. A first solution is to propagate the additional error resulting from the error on the features in the standard proof of OFUL. However, this leads to a sub-optimal regret that is no longer scaling as Õ( √ T ) with the time horizon. We overcome this hurdle by showing in Theorem 3 a robustness property of OFUL of independent interest, which aids us in controlling the regret of the overall latent class algorithm (Algorithm 3).

Consider OFUL run with perturbed (not necessarily linearly realizable) rewards. Formally, consider a finite action set A = {1, 2, . . . , A} and distinct feature vectors {ū a ∈ R C×1 } a∈A . Let Ū ⊤ := [ū 1 ū2 . . . ūA ] ∈ R C×A . The expected reward when playing action A t = a at time t is denoted by m a := E Y t A t = a , with m := (m a ) a∈A . Let us assume that there exists a unique optimal action for the expected rewards m, i.e., arg max a∈A m a = {a ⋆ }, with the regret at time

n being R n := n t=1 (m a ⋆ -m At ).
The key point here is that m need not be linearly realizable w.r.t. the actions' features -we will not require that min v∈R C m -Ū v be 0.

Algorithm 2 OFUL (Optimism in Face of Uncertainty for Linear bandits) [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF] Require: Arms' features Ū , regularization parameter λ, norm parameter R Θ for all times t 1 do 1. Form the C × (t -1) matrix Ū1:t-1 := [ū A 1 ūA 2 . . . ūA t-1 ] consisting of all arm features played up to time t -1, and Y 1:t-1 := (Y 1 , . . . , Y t-1 ) ⊤ . Set V t-1 := λI + t-1 s=1 ūAs ū⊤ As .

Choose the action

A t ∈ arg max a∈A max v∈C t-1 ū⊤ a v, where C t-1 := {v ∈ R C : v -v t-1 V t-1 D t-1 }, D t-1 := R 2 log det(V t-1 ) 1/2 λ -C/2 δ +λ 1/2 R Θ v t-1 := V -1 t-1 Ū1:t-1 Y 1:t-1.
. end for OFUL Regret with linearly realizable rewards. The OFUL algorithm is stated for the sake of clarity as Algorithm 2. Before studying the linearly non-realizable case, we record the wellknown regret bound for it in the unperturbed case, that is when ∀a ∈

[A], m a = ū⊤ a v ⋆ for some unknown v ⋆ . Theorem 2 (OFUL regret (Abbasi-Yadkori et al., 2011)) Assume that ||v ⋆ || 2 R Θ , and that for all a ∈ A, ||ū a || 2 R X , | ūa , v ⋆ | 1.
Then with probability at least 1 -δ, the regret of OFUL satisfies: ∀n 0,

R n 4 nC log(1 + nR 2 X /(λC) × λ 1/2 R Θ + R 2 log(1/δ) + C log(1 + nR 2 X /(λC)) ,
provided that the regularization parameter λ is chosen such that λ max 1, R 2 X , 1/R 2 Θ . Regret of OFUL with Perturbed Features. We make a structural definition to present the

result. Let α( Ū ) := max J A -1 J 2 , where A = Ū I C ∈ R (A+C)×C , A J is the C × C
submatrix of A formed by picking rows J, and J ranges over all size-C subsets of full-rank rows of A. We will require for our purposes that α( Ū T ) is not too large. For intuition regarding α, we refer to [START_REF] Forsgren | On linear least-squares problems with diagonally dominant weight matrices[END_REF] (the final 3 paragraphs of p. 770, Corollary 5.4 and section 7). We remark that the condition that α( Ū T ) be small is analogous to a γ-incoherence type property commonly used in prior work (Bresler et al., 2014, Assumption A2), stating that two distinct feature vectors

u c and u c ′ , c = c ′ , must have a minimum angle separation. Let v • ∈ R C be arbitrary with ℓ 2 norm at most R Θ (it helps to think of Ū v • as an approxima- tion of m), ε a := m a -ū⊤ a v • , ε := (ε a ) a∈A ∈ R A .
We now state a robustness result for OFUL potentially of independent interest.

Theorem 3 (OFUL robustness property)

Suppose ||v • || 2 R Θ , λ max 1, R 2 X , 1/4R 2 Θ , ∀a ∈ A, ||ū a || 2 R X and |m a | 1. If the deviation from linearity satisfies ε 2 ≡ m -Ū v • 2 < min a =a ⋆ ū⊤ a ⋆ v • -ū⊤ a v • 2α( Ū ⊤ ) ūa ⋆ -ūa 2 , (2)
then, with probability at least 1 -δ for all T 0,

R T 8ρ ′ T C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC ,
where

ρ ′ := max 1, max a =a ⋆ m a ⋆ -ma ū⊤ a ⋆ v • -ū ⊤ a v • .
Theorem 3 essentially states that when the deviation of the actual mean reward vector from the subspace spanned by the feature vectors is small, the OFUL algorithm continues to enjoy a favorable O( √ T ) regret up to a factor ρ ′ 1. The quantity ρ ′ in the result is a geometric measure of the distortion in the arms' actual rewards m with respect to the (linear) approximation Ū v • . We control this quantity in the next paragraph. (Note that ρ ′ = 1 in the perfectly linearly realizable case ε = 0, and this gives back the standard OFUL regret up to a universal multiplicative constant.)

Applying the Robust analysis of OFUL to the Low-rank Bandit setup. In this paragraph, we translate Theorem 3 to our Low Rank Bandit (LRB) setting in which OFUL uses feature vectors with noisy perturbations (estimated by, say, a Robust Tensor Power (RTP) algorithm). Throughout this section, we fix a user b.

We can now translate Theorem 3 thanks to the correspondence with the perturbed OFUL setting: In our low-rank bandit setting, the matrix Ū = Ūn depends on the reconstruction algorithm at mini-session n. Moreover, the optimal action a ⋆ ≡ a ⋆ b now depends on the user b. We denote for a user b ∈ [B] the minimum gap across suboptimal actions to be g

b def = min a =a ⋆ b (u a ⋆ b -u a ) ⊤ v b .
Likewise, the error vector ε depends on b, n. Its norm ||ε|| 2 appears in the condition (2) and the definition of ρ, and is controlled by the reconstruction error of Theorem 1. It decays with the number of mini-sessions n.

We define

α n def = α( Ūn ), α ⋆ def = α(U ) and use max b ||v b || for R Θ ,
Using these notations, and adapting the proof of Theorem 3 to handle a variable U n , we can now translate the result of the perturbed OFUL to our LRB setting:

OFUL LRB v • v b ≡ (v b,c ) c∈[C] ∈ R C Ū Ūn ∈ R A×C m m b ≡ U v b ∈ R A a ⋆ a ⋆ b := arg max a∈[A] u T a v b ε a (u a -ūn,a ) ⊤ v b ε ≡ (ε a ) a∈A (U -Ūn )v b
Table 1: Correspondences between OFUL and Low Rank Bandit (LRB) quantities at time n and for user b

Lemma 3 Let 0 < δ 1 and b ∈ [B].
Provided that the number of mini-sessions n 0 satisfies

n 2 0 n 0 i=1 γ -2 i b,δ , where we introduced the notation b,δ = max 2A 6 log(4A 2 /δ) min{Γ, σ min } 2 , A 9 (1 + 10( 1 Γ + 1 σmin )(1 + u 3 max )) 2 C 5 log(4A 3 /δ) 2C 2 1 σ 3 min × 2 A 6 C 2 log(4A 3 /δ) × max 2α 2 ⋆ , 8A||v b || 2 2 g 2 b , 2 7 α 2 ⋆ Cu 2 max ||v b || 2 2 g 2 b + 1 2 ,
then with probability at least 1 -2δ, ||ε|| 2 = ||(U -Ūn )v b || 2 is small enough that for any n n 0 , condition (2) is satisfied. Consequently, Theorem 3 applies with

R Θ = max b ||v b || 2 , R X = max a∈A ||u a || 2 + √ A 2α ⋆
, and

ρ ′ ≡ ρ ′ n,b 2.
Thus, provided that the total number of mini-sessions of interaction (not necessarily corresponding to interactions with user b) is large enough, then the OFUL algorithm run during interactions with user b will achieve a controlled regret. However, we want to warn that the b,δ resulting from the RTP method, especially the second term of the max, may be potentially large, although being a constant.

Putting it together: Online Recommendation algorithm

This section details our main contributions for recommendations in the context of mini-sessions of interactions with unknown mixtures of latent profiles: first Algorithm 3 that combines RTP with OFUL, and then a regret analysis in Theorem 4.

The recommendation algorithm we propose (Algorithm 3) uses the RTP method to estimate the matrix U and then applies OFUL to determine an optimistic action. Importantly, it finally outputs a distribution that mixes the optimistic action with a uniform exploration. The mixture coefficient goes to 0 with the number of rounds, thus converging to playing OFUL only. It ensures that the importance sampling weights are bounded away from 0 in the beginning.

Main analytical result: Regret bound

Theorem 4 (Regret of Algorithm 3) With Assumption 1 holding, let δ ∈ (0, 1), δ = max b∈[B] b,δ (from Lemma 3), and let n 0 be the first mini-session at which

n 2 0 n 0 i=1 γ -2 i δ .
The regret of Algorithm 3 at time T = N ℓ (acting for N mini-sessions of length ℓ) using internal instances of OFUL parameterized by δ > 0 satisfies

E[R T ] 16 BT C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC + ℓ(n 0 -1 + N n=n0 γ n ) + 3δT , provided that λ min{1, R 2 X , 1/R 2 Θ }, with R Θ max b ||v b || 2 , R X max a∈A ||u a || 2 + √ A 2α⋆ . Conse- quently, choosing δ = 1/T and γ n = log(n + 1)/n, n ∈ N, say, yields the order E[R T ] = O C √ BT log T .
Discussion.

(1) The regret of Algorithm 3 scales with T similar to that of an OFUL algorithm run with perfect knowledge of the feature matrix U : Õ(C √ BT ). This is a non-trivial result as U is not assumed to be known a priori and is estimated by Algorithm 3 using tensor methods.

Algorithm 3 Per-user OFUL with exploration Require: Parameters λ, R Θ for OFUL, exploration rate parameters γ n , n 1.

1: for mini-session n = 1, . . . , N do 2:

Get user b n .

3:

Let p n ∼ Bernoulli(γ n ) 4: if p n = 0 then 5:
{Carry out an ESTIMATE mini-session} 6:

for step k = 1, 2, . . . , ℓ do 7:

Output a n,k ∼ Uniform([A]).

8:

end for 9:

Let U n = EstimateFeatures (Algorithm 1) with input (b i , a i,l , X a i,l ,b i ,i,l ) 1 i n,1 l ℓ,pn=0 {Update feature estimates using samples from previous ESTIMATE mini-sessions} 10: else 11:

{Carry out an OFUL mini-session} 12:

for step k = 1, 2, . . . , ℓ do 13:

Run one iteration of OFUL (Algorithm 2) with features U n , parameters λ and R Θ , and past actions and rewards (a i,l , X a i,l ,b i ,i,l ), 1 i < n, 1 l ℓ, for which p i = 1 and b i = b n {An instance of OFUL for each user using current feature estimates, and observed actions and rewards from previous OFUL mini-sessions} 14:

Output action a n,k returned by OFUL 15:

end for 16:

end if 17: end for

(2) One can also compare the result with the regret of ignoring the mixture (low-rank) structure and simply running an instance of UCB per user, which would scale as O( √ ABT ). This becomes highly suboptimal when the number of actions/items A is much larger than the number of user types C, demonstrating the gain from leveraging the mixed linear structure of the problem. Note also that we do not need a specific user to interact for a long time but for as few as ℓ 3 consecutive steps, contrary for instance to the transfer method [START_REF] Lazaric | Sequential transfer in multi-armed bandit with finite set of models[END_REF], where a large number of consecutive interaction steps with the same user is required.

(3) It is worthwhile to contrast the result and approach with that in Djolonga et al. ( 2013)the authors there incur an additional regret term due to the error in approximately estimating the low-rank matrix, which requires additional tuning ending up with a regret of O(T 4/5 ). On the other hand, we avoid this approximation error by showing and exploiting the robustness property of OFUL, which guarantees √ T regret as soon as the estimated features Ũ are within a small radius of the actual ones.

The result (and analysis) does come with a caveat that the model-dependent term δ , although being independent on the time horizon T , is potentially large. With γ n set as in Theorem 4, it appears as an additive exponential constant term in the regret7 . This arises from the RTP method, and it is currently unclear if this term can be significantly reduced with the current line of analysis. Numerical evidence, however, indicates that no such large additive constant enters into the regret (Section 5). Also, on the bright side, note that δ does not need to be known by the algorithm.

Numerical Results. The performance of the low-rank bandit strategy (Algorithm 3) is shown in Figure 1, simulated for 20 users arriving uniformly at random, 3 user classes and 200 actions. Both the latent class matrix U 200×3 the mixture matrix V 20×3 are random one-shot instantiations. The proposed algorithm (Algorithm 3), with two different exploration rate schedules Õ(n -1/2 ) and Õ(n -1/3 ) ('RTP+OFUL(sqrt)' and 'RTP+OFUL(cuberoot)' in the figure), is compared with (a) basic UCB ('UCB' in the figure) ignoring the linear structure of the problem (i.e., UCB per-user with 200 actions), (b) OFUL per-user with complete knowledge of the user classes and p n = 1 always, i.e., no exploration mini-sessions, and (c) An implementation of the Alternating Least Squares estimator [START_REF] Takács | Alternating least squares for personalized ranking[END_REF][START_REF] Mary | Bandits warm-up cold recommender systems[END_REF] for the matrix U along with OFUL per-user. The proposed algorithm, with the theoretically suggested exploration Õ(n -1/2 ), is observed to exploit the latent structure considerably better than simple UCB, and is not too far from the unrealistic OFUL strategy which enjoys the luxury of latent class information. It is also competitive with performing Alternating Least Squares, which does not come with analytically sound performance guarantees in the bandit learning setting. Also, the large additive constants in the theoretical bounds for Algorithm 3 do not manifest here.

Related work. The popular low-rank matrix completion problem studies the recovery U and V given a small number of entries sampled at random from U V T with both U and V being tall matrices, see for instance [START_REF] Jain | Low-rank matrix completion using alternating minimization[END_REF] and citations therein. However, its setting is different than ours for several reasons. It typically deals with batch data arising from a sampling process that is not active but uniform across entries of U V T . Further, it requires sensing operators having strong properties (such as the RIP property), and most importantly, the performance metric is not regret but reconstruction error (Frobenius or 2-norm).

In the linear bandit literature [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF][START_REF] Rusmevichientong | Linearly parameterized bandits[END_REF][START_REF] Dani | Stochastic Linear Optimization under Bandit Feedback[END_REF], the key constraining assumption is that either user side (V ) or item side (U ) features are precisely and completely known a priori. In contrast, the problem of low regret recommendation across users with latent mixtures does not afford us the luxury of knowing either U or V , and so they must be learnt "on the fly". Another related work in the context of bandit type schemes for latent mixture model recommender systems is that of Bresler et al. (2014), in which, under the very specific uniform mixture model for all users, they exhibit strategies with good regret.

Nguyen et al. ( 2014) consider an alternating minimization type scheme in linear bandit models with two-sided uncertainty (an alternative model involving latent "factors"). However no rigorous guarantees are given for the bandit schemes they present; moreover, it is not known if alternating minimization finds global minima in general. Another related work is in the transfer learning setting from [START_REF] Lazaric | Sequential transfer in multi-armed bandit with finite set of models[END_REF]: The method combines the RTP method [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF][START_REF] Anandkumar | A method of moments for mixture models and hidden markov models[END_REF] essentially with a standard UCB [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], but however works in the setting of a large number interactions with a same user, without assuming access to "user ids". As a result, the regret bound in this setting scales linearly with the number of rounds. Our result in this paper shows that with additional access to just user identifiers, we can reduce the regret rate to be sublinear in time.

The RTP method has been used as a processing step to the EM algorithm in crowdsourcing [START_REF] Zhang | Spectral methods meet EM: A provably optimal algorithm for crowdsourcing[END_REF], but only convergence properties are considered, which is not enough to provide regret guarantees.

On the theoretical side, our contribution generalizes the setting of clustered bandits [START_REF] Maillard | Latent bandits[END_REF][START_REF] Gentile | Online clustering of bandits[END_REF] in which a hard clustering model is assumed (one user is assigned to one class, or equivalently mixture distributions can only have support size 1). In particular, [START_REF] Maillard | Latent bandits[END_REF] specifically highlight the benefit of a collaborative gain across users against using a vanilla UCB for each user. However their setting is less general than assuming a soft clustering of users (one user corresponds to a mixture of classes) across various "representative" taste profiles as we study here.

The Alternating Least-Squares (ALS) method [START_REF] Takács | Alternating least squares for personalized ranking[END_REF][START_REF] Mary | Bandits warm-up cold recommender systems[END_REF] has been shown to yield promising experimental results in similar settings where both U and V are unknown. However, no theoretical guarantees are known for this algorithm that may converge to a local optimum in general.

The work of [START_REF] Valko | Spectral Bandits for Smooth Graph Functions[END_REF] studies stochastic bandits with a linear model over a low-rank (graph Laplacian) structure. However, they assume complete knowledge of the graph and hence knowledge of the eigenvectors of the Laplacian, converting it into a bilinear problem with only one-sided uncertainty. This is in contrast to our setup where both U , V are completely uncertain.

Perhaps the closest work to ours is that of [START_REF] Djolonga | High-dimensional Gaussian process bandits[END_REF] where the authors develop a flexible approach for bandit problems in high dimension but with low-dimensional reward dependence. They use a two-phase algorithm: First a low-rank matrix completion technique (the Dantzig selector) estimates the feature-reward map, then a Gaussian Process-UCB (GP-UCB) bandit algorithm controls the regret, and show that if after n iterations the approximation error between the feature matrix and its estimate is less then η, the final regret is given by the sum of the regret of GP-UCB when given perfect knowledge of the features and of n + η(T -n) (due to the learning phase and approximation error). This results in an overall regret scaling with O(T 4/5 ). We depart from their results in two fundamental ways: Firstly, they have the possibility of uniformly sampling the entries (a common assumption in low-rank matrix completion techniques). We do not have this luxury in our setting as we do not control the process of user arrivals, that is not constrained to be uniform. Secondly, we prove and exploit a novel robustness property (see Theorem 8) of the bandit subroutine we use (OFUL in our case instead of GP-UCB), which allows us to effectively eliminate the approximation error in their work and obtain a O( √ T ) regret bound (see Theorem 4).

Conclusion & Directions

We consider a full-blown latent class mixture model in which users are described by unknown mixtures across unknown user classes, more general and challenging than when users are assumed to fall perfectly in one class [START_REF] Gentile | Online clustering of bandits[END_REF][START_REF] Maillard | Latent bandits[END_REF].

We provide the first provable sublinear regret guarantees in this setting, when both the canonical classes and user mixture weights are completely unknown, which we believe is striking when compared to existing work in the setting, e.g., alternate minimization typically gets stuck in local minima. We currently use a combination of noisy tensor factorization and linear bandit techniques, and control the uncertainty in the estimates resulting from each one of these techniques. This enables us to effectively recover the latent class structure.

Future directions include reducing the numerical constant (e.g. using an alternative to RTP), and studying how to combine our work with the aggregation of user parameters suggested in [START_REF] Maillard | Latent bandits[END_REF].

Appendix A. Proofs of Lemmas 1 and 2

Proof of Lemma 1 This result holds by construction of the estimates ra,a ′ ,n and ra,a ′ ,a ′′ ,n . Note that

E ra,a ′ ,n = 1 n n i=1 b∈[B] E X ai,1,bi,i,1 X ai,2,bi,i,2 p i (a, a ′ |b i ) I{a i,1 = a, a i,2 = a ′ } b i = b β(b) = 1 n n i=1 b∈[B] c∈[C] E X ai,1,b,i,1 X ai,2,b,i,2 p i (a, a ′ |b) I{a i,1 = a, a i,2 = a ′ } b i = b, c i = c v b,c β(b) = 1 n n i=1 b∈[B] c∈[C] E X a,b,i,1 X a ′ ,b,i,2 b i = b, c i = c v b,c β(b) (a) = 1 n n i=1 b∈[B] c∈[C] E X a,b,i,1 b i = b, c i = c E X a ′ ,b,i,2 b i = b, c i = c v b,c β(b) = 1 n n i=1 b∈[B] c∈[C] u a,c u a ′ ,c v b,c β(b) = c∈[C] ( b∈[B] v b,c β(b))u a,c u a ′ ,c = c∈[C] v β,c u a,c u a ′ ,c ,
where (a) holds by independence of the sample generated by user b when in the same class c. Note that c i is the same for all ℓ = 1, 2, 3 interaction steps, that is c i = c i,1 = c i,2 = c i,3 , where c i,ℓ is the class corresponding to sample X a,b,i,ℓ . This is the reason why we get u a,c u a ′ ,c v b,c and not a product u a,c u a ′ ,c v 2 b,c for instance.

Proof of Lemma 2

Since the rewards generated by each source a, b are i.i.d., the estimate ra,a ′ ,n is a sum of i.i.d. random variables bounded in [0, 1], re-weighted by the probability weights p i (a, a ′ |b i ), which are measurable functions of the past. Assuming that there exists some deterministic q 2,i > 0 such that ∀i ∈ N, p i (a, a ′ |b i ) q 2,i , we can thus apply a version of Azuma-Hoeffding inequality for bounded martingale difference sequence. Let us recall that by this inequality, for a deterministic time s, and (Y m ) m s ∈ [0, 1] being a bounded martingale difference sequence, then for all δ ∈ (0, 1) it holds

P(| 1 s s i=1 Y i | log(2/δ) 2s ) δ . In our case, Y i = X a i,1 ,b i ,i,1 X a i,2 ,b i ,i,2 pi(a,a ′ |bi)
I{a i,1 = a, a i,2 = a ′ } -m a,a ′ , and we deduce that

P(|r a,a ′ ,n -m a,a ′ | n i=1 q -2 2,i log(2/δ) 2n 2 ) δ .
Likewise, we get that

P(|r a,a ′ ,a ′′ ,n -m a,a ′ ,a ′′ | n i=1 q -2 3,i log(2/δ) 2n 2 ) δ .
Taking a union bound over the actions in each case, and then over the two events concludes the proof.

Proof of Corollary 1

From Lemma 2, we deduce that on an event of probability higher than 1 -δ, it holds simultaneously that e (2)

n def = M n,2 -M 2 A n m=1 q -2 2,m log(4A 2 /δ) 2n 2
) and

e (3) n def = M n,3 -M 3 A 3/2 n m=1 q -2 3,m log(4A 3 /δ) 2n 2 ) .
This indeed holds by relating the norm of the matrix (tensor) with each of the elements. We conclude by replacing the values of q 2,i and q 3,i .

Appendix B. Proof of Theorem 1

We prove in this section a slightly more detailed result, namely, the following:

Theorem 1. Assume that {γ i } i 1 are chosen such that n -2 n i=1 γ -2 i n → 0. Let λ min be the minimum robust eigenvalue of the tensor

T = M 3 (W, W, W ). Let δ ∈ (0, 1). Provided that n 2 n i=1 γ -2 i max 2A 6 log(4A 2 /δ) min{Γ, σ min } 2 , A 9 (1 + 10( 1 Γ + 1 σmin )(1 + u 3 max )) 2 C 5 log(4A 3 /δ) 2C 2 1 λ 2 min σ 3 min ,
with probability higher than 1 -2δ, there exists some permutation π ∈ S C such that for all c ∈ [C],

||u c -u n,π(c) || ∆A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2 + o(n -2 n i=1 γ -2 i ),
where we introduced the problem-dependent constant

∆ = 13 √ σ max CA σ min 3/2 1 + 10( 1 Γ + 1 σ min )(1 + u 3 max ) + 2σ max Γ + 1 σ max 1 v 2 min . For general {γ i } i 1 (not necessarily such that n -2 n i=1 γ -2 i n → 0), it holds with same probability that ||u c -u n,π(c) || A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2 ,
where, using the notation ℵ = 1 + 10( 1 Γ + 1 σmin )(1 + u 3 max ), we have introduced the constant We first decompose the following term to make appear the terms from Proposition 1:

= CA σ min 3/2 13 √ σ max + 4 2 min{Γ, σ min } + 5 σ max Γ + 1 2σ max min{Γ, σ min } ℵ + 2σ max Γ + 1 σ max 1 v 2 min + 5 3/8 √ σ max + min{Γ, σ min }/2 2CA σ min 3 ℵ 2 min{Γ, σ min } .

Proof

||u c -u n,π(c) || (3) |λ c -λ n,π(c) | RT P.1 W ⊤ † b ||ϕ c || a + | λ π(c) | RT P.3 W ⊤ † -W ⊤ † d ||ϕ c || 1 + | λ π(c) | RT P.3 W ⊤ † c ||ϕ c -ϕ n,π(c) || RT P.2
.

Note that ϕ c , and ϕ n,π(c) are both normalized vectors. Thus, (a) is bounded as ||ϕ c || 1. It holds for (b) that W ⊤ † √ Cσ max , and for (c), on the 1 -δ event Ω from Corollary 1, that

W ⊤ † C σ max √ C( √ σ max + e (2) n ) . (4)
The term (d) requires a little more work. It holds that

W ⊤ † -W ⊤ † = U D 1/2 -U D 1/2 ( U -U )D 1/2 + U ( D 1/2 -D 1/2 ) U -U e σ max + D 1/2 -D 1/2 f √ C .
We use the result of Lemma 5 from Gheshlaghi Azar et al. ( 2013) to control (e) and (f ). If e

(2) n 1 2 Γ, then it holds

D 1/2 -D 1/2 e (2) n σ max U -U 2 √ Ce (2) n Γ ,
from which we deduce that (where C 1 is a universal constant). In this case, with probability 1 -δ, the RTP algorithm with well-chosen parameters achieves

W ⊤ † -W ⊤ † ( 2σ max Γ + 1 σ max ) √ Ce (2) n . (5
|λ c -λ n,π(c) | 5 T -T n ϕ c -ϕ n,π(c) 8 T -T n λ c .
In order to make the condition explicit in our setting, we use the fact that by Lemma 6 from Gheshlaghi Azar et al. ( 2013

), if e (2) n 1 2 min{Γ, σ min } then e n C σ min 3/2 e (3) n + 2(1 + √ 2 + 2)e (2) n ( 1 Γ σ + 1 σ min )(e (3) n + max c ||u c || 3 ) . (6)
The condition e

(2) n 1 2 min{Γ, σ min } holds if the number of sessions n is sufficiently large: Indeed on an event of probability higher than 1 -δ, then it is enough that

A 3 n i=1 γ -2 i log(4A 2 /δ) 2n 2 1 2 min{Γ, σ min } ,
that is, reordering the terms, that

n 2 n i=1 γ -2 i 2A 6 log(4A 2 /δ) min{Γ, σ min } 2 . (7)
Now, in order to satisfy the condition

e n = T -T n C 1 λmin C , it is enough that C σ min 3/2 e (3) n + 2(1 + √ 2 + 2)e (2) n ( 1 Γ + 1 σ min )(e (3) n + max c ||u c || 3 ) C 1 λ min C .
Let us decompose the left-hand-side term: After some simplifications using max c ||u c || 3 A 3/2 u 3 max and e

(3) n

A 3/2 , the previous inequality happens when

e (3) n + A 3/2 e (2) n C 1 λ min σ 3/2 min C 5/2 . where = 2(1 + √ 2 + 2)( 1 Γ + 1 σmin )(1 + u 3 max ).
Using the definition of e

(3)

n and e

(2)

n then we deduce that it is enough that

(1 + )A 9/2 n i=1 γ -2 i log(4A 3 /δ) 2n 2 C 1 λ min σ 3/2 min C 5/2 ,
that is, reordering the terms that

n 2 n i=1 γ -2 i A 9 (1 + ) 2 C 5 log(4A 3 /δ) 2C 2 1 λ 2 min σ 3 min . ( 8
)
Combining the decomposition ( 3) with ( 4),( 5), and using the fact that v -2 min λ c 1, we obtain

||u c -ūn,π(c) || 5e n √ C √ σ max + (λ c + 5e n ) √ C 2σ max Γ + 1 σ max e (2) n +8 √ C(λ c + 5e n )( √ σ max + e (2) n ) e n λ c . √ C 13 √ σ max e n + 2σ max Γ + 1 σ max e (2) n v 2 min + 8 e (2) n e n +5 2σ max Γ + 1 σ max e (2) n e n + 40( √ σ max + e (2)
n )e 2 n .

Now, using (6) and unfolding the last inequality, it holds with probability higher than 1 -2δ that

||u c -ūn,π(c) || √ C 13 √ σ max C σ min 3/2 (e (3) n + e (2) n A 3/2 ) + 2σ max Γ σ + 1 σ max e (2) n v 2 min +8 C σ min 3/2 e (2)
n (e (3) n + e (2)

n A 3/2 ) +5 C σ min 3/2 2σ max Γ σ + 1 σ max e (2) n (e (3) n + e (2) n A 3/2 ) + 40( √ σ max + e (2) n )e 2 n 13 √ σ max CA σ min 3/2 (1 + ) + 2σ max Γ σ + 1 σ max 1 v 2 min ×A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2 + o(n -2 n i=1 γ -2 i ) ,
which, after some cosmetic simplifications, concludes the first part of the proof of Theorem 1. Alternatively, when n -2 n i=1 γ -2 i → ∞, we can always resort to the condition that e

(2) n 1/2 min{Γ, σ min } in order to simplify the previous derivation. We deduce, similarly, that

||u c -ūn,π(c) || √ C 13 √ σ max C σ min 3/2 (e (3) n + e (2) n A 3/2 ) + 2σ max Γ σ + 1 σ max e (2) n v 2 min +8 C σ min 3/2 e (2)
n (e (3) n + e (2)

n A 3/2 ) +5 C σ min 3/2 2σ max Γ σ + 1 σ max e (2) n (e (3) n + e (2) n A 3/2 ) + 40( √ σ max + e (2) n )e 2 n 13 √ σ max CA σ min 3/2 + 8 CA σ min 3/2 min{Γ, σ min }/2 +5 CA σ min 3/2 σ max Γ σ + 1 2σ max min{Γ, σ min } (1 + ) + 2σ max Γ σ + 1 σ max 1 v 2 min +40 √ σ max + min{Γ, σ min }/2 CA σ min 3 (1 + ) 2 min{Γ, σ min } 3/8 ×A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2 ,
where, in order to control the last term e 2 n , we used the property that

e n CA σ min 3/2 1 + min{e (2) n log(4A 3 /δ) log(4A 2 /δ) , A -3/2 e (3) n } CA σ min 3/2 1 + min{ 3/2e (2) n , A -3/2 e (3) n } .
with probability at least 1 -δ. Now, let a + t-1 ∈ arg max a∈A ū⊤ a v + t-1 be an optimal action corresponding to the approximate parameter v + t-1 , and define the instantaneous regret at time t with respect to the approximate parameter as r + t := ū⊤

a + t-1 v + t-1 -ū⊤ At v + t-1 0.
We now bound this approximate regret using arguments along the lines of Yadkori et al, 2011. Consider

r + t = ū⊤ a + t-1 v + t-1 -ū⊤ At v + t-1 ū⊤ At ṽt -ū⊤ At v + t-1 (since (A t , ṽt ) is optimistic) = ū⊤ At ṽt -v + t-1 = ū⊤ At (ṽ t -v t-1 ) + ū⊤ At v t-1 -v + t-1 ūAt V -1 t-1 ṽt -v t-1 Vt-1 + ūAt V -1 t-1 v t-1 -v + t-1 Vt-1 (Cauchy-Schwarz's inequality) 2D t-1 ūAt V -1 t-1 . ( 9
)
Noting that m a ∈ [-1, 1] ∀a, the regret can be written as

R T = T t=1 (m a ⋆ -m At ) = T t=1 min{m a ⋆ -m At , 2} = ρ ′ a =a ⋆ T t=1 min m a ⋆ -m a ρ ′ , 2 ρ ′ I{A t = a} ρ ′ a =a ⋆ T t=1 min ū⊤ a ⋆ v • -ū⊤ a v • , 2 ρ ′ I{A t = a} (using the definition of ρ ′ ) (a) ρ ′ T t=1 min 2 ū⊤ a ⋆ v + t-1 -ū⊤ At v + t-1 , 2 ρ ′ (b) = 2ρ ′ T t=1 min ū⊤ a + t-1 v + t-1 -ū⊤ At v + t-1 , 1 ρ ′ = 2ρ ′ T t=1 min r + t , 1 ρ ′ = ρ ′ T t=1 2 ρ ′ min ρ ′ r + t , 1 (c) ρ ′ T t=1 2 ρ ′ min 2ρ ′ D t-1 ūAt V -1 t-1 , 1 (d) ρ ′ T t=1 4D t-1 min ūAt V -1 t-1 , 1 ρ ′ T T t=1 16D T 2 min ūAt 2 V -1 t-1
, 1 (by using Cauchy-Schwarz's inequality).

In the derivation above,

• Steps (a) and (b) hold because of the following. By Lemma 4 (to follow below),

v + t-1 -v • 2 = V -1 t-1 Ū1:t-1 E 1:t-1 2 α( Ū ) ε 2 . Since arg max a∈A ū⊤ a v
• is uniquely a ⋆ by hypothesis, we have, thanks to Lemma 5 (to follow below), that ū⊤ establishing (a). This in turn shows that the optimal action for v + t-1 is uniquely a ⋆ at all times t, i.e., a + t-1 = arg max a∈A ū⊤ a v + t-1 = a ⋆ , which is equality (b). • Inequality (c) holds by ( 9) and (d) holds because ρ ′ 1 by definition, and D t-1 λ 1/2 R Θ 1/2 by hypothesis, implying that 2ρ ′ D t-1 1.

a ⋆ v + t-1 -ū⊤ a v + t-1 > ū⊤ a ⋆ v • -ū ⊤ a v • 2 > 0 ∀a = a ⋆ ,
The argument from here can be continued in the same way as in [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF] to yield

R T 8ρ ′ T C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC .
This proves the theorem.

Lemma 4 (Analysis of the time-varying parameter error

V -1 t-1 Ū1:t-1 E 1:t-1 ) Let ε a = m a -ū⊤ a v
• be the bias in arm a's reward due to model error, and let ε ≡ (ε a ) a∈A be the |A| dimensional vector of arm reward biases. Then,

V -1 t-1 Ū1:t-1 E 1:t-1 2 max J A -1 J 2 ε 2 ,
where

A (A+C)×C = Ū I d , A J is the C × C submatrix of A
formed by picking rows J, and J ranges over all subsets of full-rank rows of A.

Proof [Proof of Lemma 4] Let z t-1 := V -1 t-1 Ū1:t-1 E 1:t-1 = v t-1 -v • ∈ R C , with E 1:t-1 ∞ ε ∞ = m -Ū v • ∞ . We have z t-1 = t-1 s=1 ūAs ū⊤ As + λI -1 t-1 s=1 ε As ūAs = 1 t -1 t-1 s=1 ūAs ū⊤ As + λ t -1 I -1 1 t -1 t-1 s=1 ε As ūAs = a∈A ūa ū⊤ a t-1 s=1 I{A s = a} t -1 + λ t -1 I -1 a∈A ε a ūa t-1 s=1 I{A s = a} t -1 = a∈A ūa ū⊤ a f a (t -1) + λ t -1 I -1 a∈A ε a ūa f a (t -1),
where f a (t -1) ≡ f a represents the empirical frequency with which action a ∈ A has been played up to and including time t -1. This allows us to equivalently interpret z t-1 as the solution of a weighted ℓ 2 -regularized least squares regression problem with K = |A| observations (instead of the original interpretation with t -1 observations) as follows.

Let F 1/2 be the A × A diagonal matrix with the values √ f 1 , . . . , √ f A on the diagonal (note:

A a=1 f a = 1)
. With this, we can express z t-1 as

z t-1 = arg min z∈R C F 1/2 Ū z -F 1/2 ε 2 2 + λ t -1 z 2 2 = arg min z∈R C F 1/2 Ū z -ε 2 2 + λ t -1 z 2 2 = arg min z∈R C F 1/2 0 0 λ t-1 I C Ū I C z - ε 0 2 2 ≡ arg min z∈R C D 1/2 (Az -b) 2 2 = (A ⊤ DA) -1 A ⊤ Db, with D 1/2 being a (A + C) × (A + C) diagonal & positive semidefinite matrix, A ⊤ DA =
a∈A ūa ū⊤ a f a (t -1) + λ t-1 I positive definite, and A having full column rank C. A result of Forsgren (1996, Corollary 2.3) can now be applied to yield

(A ⊤ DA) -1 A ⊤ D 2 max J A -1 J 2
where J ranges over all subsets of full-rank rows of A, and A J is the C ×C submatrix of A formed by picking rows J. Thus, z t-1 2 max J A -1 J 2 ε 2 . This proves the lemma.

Lemma 5 (Critical radius) Let ū⊤ a ⋆ v • > ū⊤ a v • ∀a = a ⋆ .
Then, the following are equivalent:

v -v • 2 α( Ū ) ε 2 ⇒ ū⊤ a ⋆ v -ū⊤ a v > ū⊤ a ⋆ v • -ū⊤ a v • 2 ∀a = a ⋆ , (10)
and

ε 2 < min a =a ⋆ ū⊤ a ⋆ v • -ū⊤ a v • 2α( Ū ) ūa ⋆ -ūa 2 . ( 11
)
Proof [Proof of Lemma 5] Assuming (11), observe that when v lies in the interior of an α( Ū ) ε 2ball around v • , we have, for any a = a ⋆ ,

(ū a ⋆ -ūa ) ⊤ v = (ū a ⋆ -ūa ) ⊤ v • + (ū a ⋆ -ūa ) ⊤ (v -v • ) (ū a ⋆ -ūa ) ⊤ v • + min ψ 2 α( Ū ) ε 2 (ū a ⋆ -ūa ) ⊤ ψ = (ū a ⋆ -ūa ) ⊤ v • -α( Ū ) ε 2 ūa ⋆ -ūa 2 > (ū a ⋆ -ūa ) ⊤ v • -α( Ū ) ūa ⋆ -ūa 2 ū⊤ a ⋆ v • -ū⊤ a v • 2α( Ū ) ūa ⋆ -ūa 2 = ū⊤ a ⋆ v • -ū⊤ a v • 2 ,
which proves one direction of the lemma. For the other direction, note that if

ε 2 ū⊤ a ⋆ v • -ū ⊤ a v • 2α( Ū ) ūa ⋆ -ūa 2 for some a = a ⋆ , then by setting v = v • - (ū ⊤ a ⋆ v • -ū ⊤ a v • )(ūa⋆ -ūa) 2 ūa ⋆ -ūa 2 2 , we have both v -v • 2 = ū⊤ a ⋆ v • -ū⊤ a v • (ū a ⋆ -ūa ) 2 ūa ⋆ -ūa 2 2 2 = ū⊤ a ⋆ v • -ū⊤ a v • 2 ūa ⋆ -ūa 2 α( Ū ) ε 2 and (ū a ⋆ -ūa ) ⊤ v = (ū a ⋆ -ūa ) ⊤ v • -(ū a ⋆ -ūa ) ⊤ ū⊤ a ⋆ v • -ū⊤ a v • (ū a ⋆ -ūa ) 2 ūa ⋆ -ūa 2 2 = (ū a ⋆ -ūa ) ⊤ v • 2
which contradicts (10), and we are done.

C.1 Proof of Lemma 3

We begin by establishing some auxiliary technical results, which together imply Lemma 3.

Lemma 6 (Controlling α n ) If n is large enough so that (1) and

A 3 C n i=1 γ -2 i log(4A 3 /δ) 2n 2 1 2α ⋆ , (12)
hold, then with probability at least 1 -δ, α n 2α ⋆ .

Proof [Proof of Lemma 6] The first step is to estimate the factor α in the analysis of Perturbed OFUL. Towards this, note that the quantity α ≡ α( Ū ) in our setting becomes

α n ≡ α n ( Ūn ) = max J (u ⋄ n ) -1 J 2 ,
where u ⋄ n := Ūn I C has rank C, and J ranges over all combinations of its C full-rank rows. For any such subset of C linearly independent rows J, we have, after denoting

u ⋄ := U I C , that (u ⋄ n ) -1 J 2 (u ⋄ ) -1 J 2 + (u ⋄ n ) -1 J -(u ⋄ ) -1 J 2 .
The final term above can be bounded using Anandkumar et al. (2012, Lemma E.4) -a version of Theorem 2.5 in [START_REF] Stewart | Matrix perturbation theory[END_REF]. Assuming (u ⋄ ) J is invertible, and

(u ⋄ ) -1 J ((u ⋄ n ) J -(u ⋄ ) J ) 2 < 1, then (u ⋄ n ) J is invertible
, and a resulting bound on the norm of its inverse lets us write

(u ⋄ ) -1 J 2 + (u ⋄ n ) -1 J -(u ⋄ ) -1 J 2 (u ⋄ ) -1 J 2 + (u ⋄ n ) J -(u ⋄ ) J 2 (u ⋄ ) -1 J 2 2 1 -(u ⋄ ) -1 J ((u ⋄ n ) J -(u ⋄ ) J ) 2
.

Writing J = J u ∪ J l (u and l stand for "upper" and "lower") with J l representing the subset of rows taken from the bottom C rows of u ⋄ n (i.e., I C ), we have

(u ⋄ n ) J -(u ⋄ ) J = ( Ūn -U ) Ju 0 .
Thus, with • F denoting the Frobenius norm, and using the dominance of the Frobenius norm over the matrix 2-norm, with probability at least 1 -δ,

(u ⋄ n ) J -(u ⋄ ) J 2 (u ⋄ n ) J -(u ⋄ ) J F = ( Ūn -U ) Ju F Ūn -U F = c∈[C] Ūn,c -U c 2 2 A 3 C n i=1 γ -2 i log(4A 3 /δ) 2n 2 , ( 14
)
from the RTP error estimate (1). Now, letting α ≡ α(U ) = max J (u ⋄ J )

-1 2 , the result above implies that for any suitable J,

(u ⋄ ) -1 J ((u ⋄ n ) J -(u ⋄ ) J ) 2 (u ⋄ ) -1 J 2 (u ⋄ n ) J -(u ⋄ ) J 2 α (u ⋄ n ) J -(u ⋄ ) J 2 α A 3 C n i=1 γ -2 i log(4A 3 /δ) 2n 2 < 1/2
whenever n is large enough to satisfy (12). When the condition (12) above holds, we get, for any J at time n,

(u ⋄ n ) -1 J 2 (u ⋄ ) -1 J 2 + (u ⋄ n ) J -(u ⋄ ) J 2 (u ⋄ ) -1 J 2 2 1 -(u ⋄ ) -1 J ((u ⋄ n ) J -(u ⋄ ) J ) 2 α + 2α 2 (u ⋄ n ) J -(u ⋄ ) J 2 α + 2α 2 A 3 C n i=1 γ -2 i log(4A 3 /δ) 2n 2 [by (14)] α + 2α 2 1 2α = 2α .
This shows that

α n = max J (u ⋄ n ) -1 J 2 2α.
Lemma 7 (Sufficient condition for (2)) If n is large enough so that ( 1), ( 12) and

A 3 C n i=1 γ -2 i log(4A 3 /δ) 2n 2 min g b 4 √ A v b 2 , g b 16α ⋆ √ Cu max v b 2 + g b (15)
hold, then ( 2) is satisfied with probability at least 1 -δ.

Proof [Proof of Lemma 7] The term ε 2 = U -Ūn v b 2 is bounded from above by U -Ūn 2 v b 2 U -Ūn F v b 2 √ C v b 2 A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2
(by ( 14))

≡ √ C v b 2 ℵ n , say. (16)
For any a = a ⋆ ,

(ū n,a ⋆ -ūn,a ) ⊤ v b = (u a ⋆ -u a ) ⊤ v b + ∂ a v b ζ a , (17)
with

∂ ⊤ a := (ū n,a ⋆ -u a ⋆ ) -(ū n,a -u a ), and
ζ a := inf ξ 2 ∂a 2 (u a ⋆ -u a ) ⊤ v b + ξ ⊤ v b .
Also, by ( 14), we have

max a∈[A] ūn,a -u a 2 √ AC max c∈[C] ūn,c -u c 2 √ AC A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2 =: ℵ n √ AC.
Thus,

ζ a inf ξ 2 2ℵn √ AC (u a ⋆ -u a ) ⊤ v b + ξ ⊤ v b = (u a ⋆ -u a ) ⊤ v b -2ℵ n √ AC v b 2 . (18)
By ( 17) and ( 18), for any a = a ⋆ ,

(ū n,a ⋆ -ūn,a ) ⊤ v b (u a ⋆ -u a ) ⊤ v b -2ℵ n √ AC v b 2 . (19)
We also have

ūn,a ⋆ -ūn,a 2 u a ⋆ -u a 2 + ūn,a ⋆ -u a ⋆ 2 + ūn,a -u a 2 u a ⋆ -u a 2 + 2ℵ n √ AC (20)
whenever ( 12) holds. Putting ( 16), ( 19), ( 20) and the conclusion of Lemma 6 together, we have that condition (2) in our case, i.e,

ε 2 ≡ U -Ūn v b 2 min a =a ⋆ (ū n,a ⋆ -ūn,a ) ⊤ v b 2α n ūn,a ⋆ -ūn,a 2 is satisfied when √ C v b 2 ℵ n min a =a ⋆ (u a ⋆ -u a ) ⊤ v b -2ℵ n √ AC v b 2 4α ⋆ u a ⋆ -u a 2 + 2ℵ n √ AC .
This, in turn, is satisfied if

2ℵ n √ AC v b 2 1 2 min a =a ⋆ (u a ⋆ -u a ) ⊤ v b = g b 2 , and
√ C v b 2 ℵ n g b /2 8α ⋆ √ Cu max + g b /(2 v b 2 ) ⇔ ℵ n g b 16α ⋆ Cu max v b 2 + g b √ C .
Lemma 8 (Control of the distortion ρ due to noisy feature estimates) If n is large enough so that (1), ( 12) and ( 15) hold, then ρ ′ 2 with probability at least 1 -δ.

Proof [Proof of Lemma 8] We begin by considering

max a =a ⋆ (u a ⋆ -u a ) ⊤ v b (ū n,a ⋆ -ūn,a ) ⊤ v b max a =a ⋆ (u a ⋆ -u a ) ⊤ v b (u a ⋆ -u a ) ⊤ v b + ∂ a v b max a =a ⋆ (u a ⋆ -u a ) ⊤ v b ζ a , with ∂ ⊤ a := (ū n,a ⋆ -u a ⋆ ) -(ū n,a -u a ), and
ζ a := inf ξ 2 ∂a 2 (u a ⋆ -u a ) ⊤ v b + ξ ⊤ v b
as in the proof of Lemma 7. Also, by ( 14), we have that with probability at least 1 -δ,

max a∈[A] ūn,a -u a 2 √ AC max c∈[C] ūn,c -u c 2 √ AC A 3 n i=1 γ -2 i C log(4A 3 /δ) 2n 2 =: ℵ n √ AC, say.
Thus,

ζ a inf ξ 2 2ℵn √ AC (u a ⋆ -u a ) ⊤ v b + ξ ⊤ v b = (u a ⋆ -u a ) ⊤ v b -2ℵ n √ AC v b 2 ⇒ ζ a (u a ⋆ -u a ) ⊤ v b 1 - 2ℵ n √ AC v b 2 (u a ⋆ -u a ) ⊤ v b 1 - 2ℵ n √ AC v b 2 g b ,
where g b := min a =a ⋆ (u a ⋆u a ) ⊤ v b > 0 is the minimum gap for user b across suboptimal actions.

Provided that (1), ( 12) and ( 15) hold, we get that with probability at least 1 -δ, ζa (u a ⋆ -ua) ⊤ v b 1 2 for each a = a ⋆ . Also, by the definition of a ⋆ , the denominator is positive, i.e., (u a ⋆u a )

⊤ v b > 0. Hence,

max a =a ⋆ (u a ⋆ -u a ) ⊤ v b (ū n,a ⋆ -ūn,a ) ⊤ v b 2,
completing the proof of the result.

Lemma 9 (Bounding R X ) If n is large enough so that ( 1) and ( 12) hold, then

R X √ A 2α ⋆ + max a∈A u a 2 ,
with probability at least 1 -δ.

Proof [Proof of Lemma 9] Conditions (1) and ( 12), together with the estimate (20), imply that for any action a,

ūn,a 2 u a 2 + ūn,a -u a 2 u a 2 + ℵ n √ AC u a 2 + √ A/(2α ⋆ ).
with probability at least 1 -δ.

In order to conclude the proof of Lemma 3, we gather the conditions from Lemma 6 and Lemma 7. After some simplifications, both conditions are satisfied as soon as

n 2 n i=1 γ -2 i 2 A 6 C 2 log(4A 3 /δ) max 2α 2 ⋆ , 8A||v b || 2 2 g 2 b , 2 7 α 2 ⋆ Cu 2 max ||v b || 2 2 g 2 b + 1/2 .

Appendix D. Proof of Theorem 4

Proof Let n 0 be the first mini-session such that both conditions in Lemma 3 are satisfied, that is such that

n 0 n0 i=1 γ -2 i δ .
The cumulative regret R T = T t=1 r t of Algorithm 3 satisfies

E[r t |b n = b] = E[r t I{p n = 1}|b n = b] + E[r t I{p n = 0}|b n = b] E[u ⊤ a ⋆ b v b -u ⊤ ãn,k v b ](1 -γ n ) + γ n . E[u ⊤ a ⋆ b v b -u ⊤ ãn,k u b ] + γ n ,
where ãn,k is an action output by an instance of OFUL for user b n = b. Thus, we have We can now use the OFUL robustness guarantee -a natural technical extension 8 of Theorem 3 along with Lemma 3 -to obtain that, for a given user sequence b 1 , . . . , b N , with probability at least

E[R T |b 1 , . . . , b N ] (n 0 -1)ℓ + E b∈[B] N n=n0 ℓ l=1 u ⊤ a ⋆ b v b -u ⊤ ãn,l v b I{b n = b} b 1 , . . . , b N + ℓ N n=n0 γ n . = (n 0 -1)ℓ + b∈[B] E n0 n N, bn=b ℓ l=1 u ⊤ a ⋆ b v b -u ⊤ ãn,l v b (⋆) b 1 , . . . , b N + ℓ N n=n0 γ n . (21
9 1 -2δ -δ = 1 -3δ, R b,N b,n 0 ({U n } n∈[n0,N ],bn=b ) 16 ℓN b,n0 C log 1 + ℓN b,n0 R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + ℓN b,n0 R 2 X λC .
8. Although Theorem 3 holds only for a fixed perturbation ε and feature set ū, it is not hard to see that a modification of it, with time-varying εt, ūt and ρ ′ being the largest ρ ′ t over all times t, yields the same conclusion (regret bound). We provide this extension in Theorem 5 in Appendix E below. 9. Although the time horizons played by each OFUL instance per user, N b,n 0 , are technically random and unknown to the instance at the start, conditioning on the sequence of users arriving at each time instant lets us use the conclusion of Lemma 3.

This in turn implies that

b∈B E R b,N b,n 0 ({U n } n∈[n0,N ],bn=b ) b 1 , . . . , b N (a) 16 b∈B ℓN b,n0 C log 1 + ℓN b,n0 R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + ℓN b,n0 R 2 X λC + b∈B 3δℓN b,n0 (b) 16 b∈B ℓN b,n0 C log 1 + ℓN b,n0 R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + ℓN b,n0 R 2 X λC + 3δT.
The last term on the right-hand side in (a) is due to the fact that with probability at most 3δ, the per-user regret R b,N b,n 0 ({U n } n∈[n0,N ],bn=b ) can be as large as ℓN b,n0 (the total number of time slots for which user b interacts with the system). The corresponding term in (b) is by using b∈[B] ℓN b,1 = T . Further bounding using the Cauchy-Schwarz inequality b∈B ℓN b,n0

√ BT gives b∈B E R b,N b,n 0 ({U n } n∈[n0,N ],bn=b ) b 1 , . . . , b N 16 b∈B ℓN b,n0 C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC + 3δT 16 BT C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC + 3δT.
Plugging this estimate into (21), we obtain that

E[R T |b 1 , . . . b N ] ℓ n 0 -1 + N n=n0 γ n + 16 BT C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC + 3δT.
Expliciting n 0 and tuning γ n The next step is to control the term n 0 -1 + N n=n0 γ n . To this end, we explicit n 0 and optimize γ n . We write ≡ δ in the sequel for convenience.

If

γ n = min{1, 1/2 n -1/2 }, then n 2 n m=1 γ -2 m = n 2 ⌈ ⌉ + 1 n m>⌈ ⌉ m = 2 n 2 ⌈ ⌉2 + n(n + 1) -⌈ ⌉(⌈ ⌉ -1) 2 1 + 1/n + (⌈ ⌉ )/n 2 . Thus, this is higher than if n 2 -n -⌈ ⌉ 0, that is if n n 0 def = ⌈1/2 + ⌈ ⌉ + 1/4⌉. Since n 0 ⌈ ⌉, we immediately get N n=n0 γ n 1/2 n -1 2 0 + 2 1/2 N 1 2 -n 1 2 0 1 + 2 1/2 N 1 2 -n 1 2 0 .
Thus, we obtain

n 0 -1 + N n=n0 γ n 2 1/2 N 1 2 + n 0 -2 1/2 n 1/2 0 2 1/2 N 1 2 + n 0 -2 ⌈ ⌉
Using the fact that > 1, the bound simplifies to

n 0 -1 + N n=n0 γ n 2 √ N + 1 .
If, on the other hand, a bound on is not readily available beforehand, then choosing

γ n = log(1 + n)/n, n 1, gives, via a crude bound, n m=1 γ -2 m = n m=1 m/ log(1 + m) √ n m=1 m/ log 2 + n m= √ n m/ log(1 + √ n) n/ log 2 + n 2 / log √ n 2n 2 / log √ n ⇒ n 2 0 n0 m=1 γ -2 m n 2 0 2n 2 0 / log √ n 0 = log n 0 4 .
The bound above is at least provided n 0 exp(4 ). Thus, we finally get that, upon setting δ = 1/ √ T , the total expected regret satisfies (as an order-wise function of T )

E[R T ] ℓ exp(4 ) + N n=1 log(n + 1)/n + 16 BT C log 1 + T R 2 X λC λ 1/2 R Θ + R log T + C log 1 + T R 2 X λC + 3 √ T = O C √ BT log T .

Theorem 5 (OFUL robustness result, extension of Theorem 3 for time-varying features) Assume ||v

• || 2 R Θ , λ max 1, R 2 X , 1/4R 2 Θ , ∀a ∈ A, t T , ||ū (t)
a || 2 R X and |m a | 1, and that for all t T , arg max a∈A ū(t)⊤ a v • = {a ⋆ } (i.e., the linearly realizable approximation with respect to the current features has a ⋆ as its unique optimal action). If

ε (t) 2 ≡ m -Ū (t) v • 2 < min a =a ⋆ ū(t)⊤ a ⋆ v • - ū(t)⊤ a v • 2α( Ū (t)⊤ ) ū(t) a ⋆ - ū(t) a 2 , ( 22
)
then with probability at least 1 -δ, for all T 0,

R T 8ρ ′ T C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC , where ρ ′ := max t max 1, max a =a ⋆ m a ⋆ -ma ū(t)⊤ a ⋆ v • -ū (t)⊤ a v • . Proof Let M 1:t = (m A1 , . . . , m At ) ⊤ . The argument used to prove Theorem 2 in Yadkori et al, 2011, shows that v t-1 = V -1 t-1 Ū(t) 1:t-1 η 1:t-1 + V -1 t-1 Ū(t) 1:t-1 M 1:t-1
where η 1:t-1 := (η 1 , . . . , η t-1 ) is the observed noise sequence, and where Ū(t) 1:t-1 is the matrix built from the time varying features at time t and the action sequence thus far. Let E (t)

1:t-1 := (ε (t) A1 , . . . , ε (t) At ) ⊤ = M 1:t-1 - Ū(t) 1:t-1 v • . We then have v t-1 = V -1 t-1 Ū(t) 1:t-1 η 1:t-1 + V -1 t-1 Ū(t) 1:t-1 M 1:t-1 = V -1 t-1 Ū(t) 1:t-1 η 1:t-1 + V -1 t-1 Ū(t) 1:t-1 Ū(t)⊤ 1:t-1 v • + E (t) 1:t-1 = V -1 t-1 Ū(t) 1:t-1 η 1:t-1 + v • -λV -1 t-1 v • + V -1 t-1 Ū(t) 1:t-1 E (t) 1:t-1 . Thus, letting v + t-1 := v • + V -1 t-1 Ū (t) 1:t-1 E (t)
1:t-1 , and using the above with techniques from Yadkori et al together with v • 2 R Θ , we have that

v + t-1 ∈ C t-1
with probability at least 1 -δ.

Now, let a + t-1 ∈ arg max a∈A ū(t)⊤ a v + t-1 be an optimal action corresponding to the approximate parameter v + t-1 and approximate feature ū(t)⊤ a , and define the instantaneous regret at time t with respect to the approximate parameter as

r + t := ū(t)⊤ a + t-1 v + t-1 - ū(t)⊤ At v + t-1 0.
We now bound this approximate regret using arguments along the lines of Yadkori et al, 2011 as follows. Write

r + t = ū(t)⊤ a + t-1 v + t-1 - ū(t)⊤ At v + t-1 ū(t)⊤ At ṽt - ū(t)⊤ At v + t-1 (since (A t , ṽt ) is optimistic) = ū(t)⊤ At ṽt -v + t-1 = ū(t)⊤ At (ṽ t -v t-1 ) + ū(t)⊤ At v t-1 -v + t-1 ū(t) At V -1 t-1 ṽt -v t-1 Vt-1 + ū(t) At V -1 t-1 v t-1 -v + t-1 Vt-1 (Cauchy-Schwarz's inequality) 2D t-1 ū(t) At V -1 t-1 . ( 23
)
Noting that m a ∈ [-1, 1] ∀a, the regret can be written as

R T = T t=1 (m a ⋆ -m At ) = T t=1 min{m a ⋆ -m At , 2} = ρ ′ a =a ⋆ T t=1 min m a ⋆ -m a ρ ′ , 2 ρ ′ I{A t = a} ρ ′ a =a ⋆ T t=1 min ū(t)⊤ a ⋆ v • -ū(t)⊤ a v • , 2 ρ ′ I{A t = a} (using the definition of ρ ′ ) (a) ρ ′ T t=1 min 2 ū(t)⊤ a ⋆ v + t-1 - ū(t)⊤ At v + t-1 , 2 ρ ′ (b) = 2ρ ′ T t=1 min ū(t)⊤ a + t-1 v + t-1 - ū(t)⊤ At v + t-1 , 1 ρ ′ = 2ρ ′ T t=1 min r + t , 1 ρ ′ = ρ ′ T t=1 2 ρ ′ min ρ ′ r + t , 1 (c) ρ ′ T t=1 2 ρ ′ min 2ρ ′ D t-1 ū(t) At V -1 t-1 , 1 (d) ρ ′ T t=1 4D t-1 min ū(t) At V -1 t-1 , 1 ρ ′ T T t=1 16D T 2 min ū(t) At 2 V -1 t-1
, 1 (by using Cauchy-Schwarz's inequality).

In the derivation above,

• Steps (a) and (b) hold because of the following. By Lemma 10 (to follow below), a). This in turn shows that the optimal action for v + t-1 is uniquely a ⋆ at all times t, i.e., a + t-1 = arg max a∈A ū(t)⊤ a v + t-1 = a ⋆ , which is precisely equality (b). • Remark. In the above, Lemma 5 is written for generic ūa , ε, so in particular applies to each time varying ū(t) a , ε (t) . We also used an extended version of Lemma 4 to the case of varying ū(t) a , ε (t) , which we state and prove below as Lemma 10.

v + t-1 -v • 2 = V -1 t-1 Ū(t) 1:t-1 E (t) 1:t-1 2 α( Ūt ) ε (t) 2 . Since arg max a∈A ū(t)⊤ a v • is uniquely a ⋆ by hypothesis, we have, thanks to Lemma 5, that ū(t)⊤ a ⋆ v + t-1 - ū(t)⊤ a v + t-1 > ū(t)⊤ a ⋆ v • -ū (t)⊤ a v • 2 > 0 ∀a = a ⋆ , es- tablishing (
• Inequality (c) holds by ( 23) and (d) holds because ρ ′ 1 by definition, and D t-1 λ 1/2 R Θ 1/2 by hypothesis, implying that 2ρ ′ D t-1 1.

The argument from here can be continued in the same way as in Abbasi-Yadkori et al. (2011, proof of Theorem 3) to yield

R T 8ρ ′ T C log 1 + T R 2 X λC λ 1/2 R Θ + R 2 log 1 δ + C log 1 + T R 2 X λC .
This proves the theorem.

Lemma 10 (Extension of Lemma 4 to time-varying feature sets) Let ε

(t) a = m a - ū(t)⊤ a v
• be the bias in arm a's reward due to model error, with respect to the features Ūt , and let ε

(t) ≡ ε (t) a a∈A
. Then, we have

V -1 t-1 Ū(t) 1:t-1 E (t) 1:t-1 2 max J A (t)-1 J 2 ε (t) 2 ,
where

A (t) (A+C)×C = Ū (t) I d , A (t)
J is the C × C submatrix of A (t) consisting of rows in J, and J ranges over all subsets of full-rank rows of A (t) .

Proof [Proof of Lemma 10] Let z (t) t-1 := V -1 t-1 Ū(t) 1:t-1 E (t) 1:t-1 = v + t-1 -v • ∈ R C , thus E (t) 1:t-1 ∞ ε (t) ∞ = m -Ū (t) v • ∞ . We now write z (t) t-1 = t-1 s=1 ū(t) As ū(t)⊤ As + λI -1 t-1 s=1 ε (t) As ū(t) As = 1 t -1 t-1 s=1 ū(t) As ū(t)⊤ As + λ t -1 I -1 1 t -1 t-1 s=1 ε (t) As ū(t) As = a∈A ū(t) a ū(t)⊤ a t-1 s=1 I{A s = a} t -1 + λ t -1 I -1 a∈A ε (t) a ū(t) a t-1 s=1 I{A s = a} t -1 = a∈A ū(t) a ū(t)⊤ a f a (t -1) + λ t -1 I -1 a∈A ε (t) a ū(t) a f a (t -1),
where f a (t -1) is the empirical frequency with which action a ∈ A has been played up to and including time t -1. This allows us to equivalently interpret z t-1 as the solution of a weighted ℓ 2 -regularized least squares regression problem with K = |A| observations (instead of the original interpretation with t -1 observations) as follows (we suppress the dependence of f a on t as per the context for clarity of notation). Let F 1/2 be the A × A diagonal matrix with the values √ f 1 , . . . , √ f A on the diagonal (note:

A a=1 f a = 1). With this, we can express z t-1 as z (t)

t-1 = arg min where J ranges over all subsets of full-rank rows of A, and A J is the C ×C submatrix of A formed by picking rows J. Thus, z t) 2 . This proves the lemma.

z∈R C F 1/2 Ū (t) z -F 1/2 ε (t) 2 2 + λ t -1 z 2 2 = arg min z∈R C F 1/2 Ū (t) z -ε (t) 2 2 + λ t -1 z 2 2 = arg min z∈R C F 1/2 0 0 λ t-1 I C Ū (t) I C z - ε (
(t) t-1 2 max J A -1 J 2 ε (

Appendix F. Unregularized Least squares

In our setting where we consider finitely many arms, one way wonder whether it is possible to remove the regularization parameter λ. Following [START_REF] Rusmevichientong | Linearly parameterized bandits[END_REF], this is indeed possible under the assumption that the minimum eigenvalue of a∈A u a u ⊤ a is away 0. Then, we first play each arm once (once for all users B, not for each of them) before running Algorithm 3, where OFUL is used with λ = 0 and with D t-1 redefined to be 4R 2 A log(t) + log(A/δ) . This leads essentially to similar bounds, with α ⋆ replaced by max J ||U -1 J || 2 , as we show below.

Let U ⊂ R C . We receive at time s, observation y s = u ⊤ s v ⋆ + η s ∈ R where v ⋆ ∈ R C and u s ∈ U.

We make the following Assumption 2 There exists R X , R, λ 0 ∈ R + ⋆ such that 1. ∀s, ||u s || R X 2. ∀λ ∈ R, log E exp(λη s ) λ 2 R 2 /2. Then, under Assumption 2, it holds

P v t -v ⋆ ∈ C t 1 -δ .

F.2 Application to Low-Rank bandits

In order to apply this result to the low-rank bandit problem, we need to show that G t is invertible.

In our case, this matrix is at mini-session n Mt = t s=1 ũn,as ũ⊤ n,as . Let us assume that all actions are sample at least once in the beginning. Thus, in this case λ min ( Mt ) λ min ( Ã), where à = a∈[A] ũn,a ũ⊤ n,a . For convenience, let us also introduce the C × C matrix A = a∈[A] u a u ⊤ a = U ⊤ U . In order to show that Mt is invertible, it us enough to show that λ min ( Ã) > 0. Now, by the result of reconstruction of the feature matrix M , we know that there exists with high probability a permutation π such that the columns are well estimated: A straightforward adaptation of the proof of Theorem 3 then gives

R n ρ ′ n(A + 16D 2 n,δ n t=A+1 min{||ū At || 2 M-1 t-1 , 1}) 16ρ ′ R 2 A log(n) + log(A/δ) n 2 + 4R 2 X λ 0 C log 1+ 2R 2 X λ 0 + (C+1) log(n+1) +ρ ′ √ An .
Following the same steps as for Lemma 3, we finally obtain the result:

Theorem 8 (Unregularized OFUL robustness result) Assume ||v • || 2 R Θ , for all a ∈ A, ||ū a || 2 R X and |m a | 1, and that arg max a∈A ū⊤ a v • = {a ⋆ } (i.e., the linearly realizable approximation has a ⋆ as its unique optimal action). Assume that each action has been played once. Let 0 < δ 1. Provided that the number of mini-sessions n 0 is large enough to satisfy This result enables to get the corresponding variant of Theorem 4 using an unregularized OFUL.

=

  T n -T . Reconstruction guarantee. Our next result makes use of the following proposition from Anandkumar et al. (2014b, Theorem 5.1), restated here for completeness. Proposition 1 (Theorem 5.1 of Anandkumar et al. (2014b)) Let T = T + E ∈ R C×C×C , where T is a symmetric tensor with orthogonal decomposition T = C c=1 λ c ϕ ⊗3 c , where each λ c > 0, {ϕ c } c∈[C] is an orthonormal basis, and E is a symmetric tensor with operator norm ||E|| ε. Let λ min = min{λ c : c ∈ [C]}, λ max = max{λ c : c ∈ [C]}. Run the RTP algorithm with input T for C iterations. Let {( λ c , ϕ c )} c∈[C] be the corresponding sequence of estimated eigenvalue/eigenvector pairs returned. Then, there exist universal constants C 1 , C 2 > 0 for which the following is true. Fix η ∈ (0, 1) and run RTP with parameters (i.e., number of iterations) L, N with L = poly(C) log(1/η), and N C 2 log(C) + log log λmax ε with probability at least 1 -η, there exists a permutation π ∈ S C such that ∀c ∈ [C] : |λ c -λ π(c) | 5ε, ||ϕ c -ϕ π(c) || 8ε/λ c ,

Figure 1 :

 1 Figure 1: Regret of the proposed algorithm ('RTP+OFUL' or Algorithm 3) for two different exploration rate schedules, compared with (a) independent UCB per-user, (b) OFUL per-user with perfect knowledge of latent classes U , and (c) Alternating Least Squares estimation for the matrix U , along with OFUL per-user. Here, B = 20 users, C = 3 classes, and A = 200, with randomly generated U and V . Plots show the sample mean of cumulative regret with time, with 1 standard deviation-error bars over 10 sample experiments.

  The proof closely follows that of GheshlaghiAzar et al. (2013). First, note that by property of the rank 1 decomposition ((Anandkumar et al., 2014b, Theorem 4.3)), it holds that λ c = ( b∈[B] v b,c β(b)) -2 and thus v -2 min λ max λ min 1.

)

  At this point, (RT P.1), (RT P.2) and (RT P.3) are controlled by the perturbation method from[START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF], under the condition that e n = T -T C 1 λmin C

  I{b n = b} where r t ≡ r n,l def = u ⊤ a ⋆ bn v bn -u ⊤a n,l v bn is the instantaneous regret of Algorithm 3 at time t = ℓn+k when the current user is b n = b. Using the notations of Algorithm 3, it holds that

)

  For each user b ∈ [B], the expectation in the right-hand side above corresponds to the cumulative regret of the OFUL strategy when interacting with user b in mini-sessions n 0 through N , and when given at each mini-session n the set of perturbed feature vectors U n . Let N b,n0 = N n=n0 I{b n = b} count the total number of mini-sessions from n 0 in which user b is present (note that b∈[B] N b,1 = N and b∈[B] ℓN b,1 = T ). Let us denote the term (⋆) in the above explicitly using R b,N b,n 0 ({U n } n∈[n0,N ],bn=b ).

  ⊤ DA) -1 A ⊤ Db, with D 1/2 being a (A + C) × (A + C) diagonal & positive semidefinite matrix, A ⊤ DA = t -1) + λt-1 I being positive definite, and A having full column rank C. A result ofForsgren (1996, Corollary 2.3) now gives(A ⊤ DA) -1 A ⊤ D 2 max J

  3. λ min ( t s=1 u s u ⊤ s ) λ 0 . Assumption 2.3 is satisfied for instance when there are C points (u 0,i) i∈[C] in R d such that λ min ( C i=1 u 0,i u ⊤ 0,i ) = λ 0 > 0, and u s = u 0,s for s ∈ [C].We consider the least-squares estimate In case U is finite, one can get the following result Theorem 6 Let us introduce the confidence setC t = w ∈ R C : w ⊤ G t w D t,δ , where G t = t s=1 u s u ⊤s and D t,δ = 4R 2 |U| log(t) + log(|U|/δ) .

a∈

  study E = Ã -A. Let λ be any eigenvalue of E, then it holdsλ trace(E) = a∈[A] trace ũn,a ũ⊤ n,au a u ⊤ a a∈[A] ||ũ n,a || 2 -||u a || 2 ,a,c -u a,c ) 2 + 2u a,c (ũ n,a,c -u a,c ) c∈[C] ||ũ n,c -u c || 2 ,a,c -u a,c ) 2 c∈[C] ||ũ n,cu c || 2 + 2||u c ||||ũ n,cu c || (2u max + 1) c∈[C] ||ũ n,cu c || .Thus, provided that n is large enough thatλ min (A) > 2(2u max + 1) c∈[C] ||ũ n,cu c || ,we deduce that Mt is invertible. Using the fact that A = U ⊤ U , This translates to the conditionλ min (U ⊤ U ) > 2 (2u max + 1)CA 3 2u max + 1) 2 C 3 A 6 log(4A 3 /δ) λ 2 min (U ⊤ U ).Thus, assuming that all actions are chosen at least once in the beginning, and thatn 2 n m=1 γ -2 m > 4 2 (2u max + 1) 2 C 3 A 6 log(4A 3 /δ) λ 2 min (U ⊤ U ), then λ min ( Mt ) λ min (U ⊤ U )/2 = λ 0 /2 > 0 and Theorem 6 and Theorem 7 both apply.In order to control the regret of the unregularized version of OFUL, we now use the proof ofRusmevichientong and Tsitsiklis (2010, Theorem 4.1) combined with the fact that λ min ( Mt ) λ 0 /2 to get

  2u max + 1) 2 C 3 A 6 log(4A 3 /δ) λ 2 min (U ⊤ U ) , 2 A 6 C 2 log(4A 3 /δ) max 2α 2 ⋆ , at least 1 -δ for all T 0, the regret R A+1:n of the OFUL algorithm from decision A + 1 to n satisfies R A+1:n 32R 2 A log(n) + log(A/δ)

It is also unlikely to be very short, say, less than 3.

Roughly, each UCB per-user plays from a pool of A actions for about T /B rounds, thus suffering regret O( A(T /B)).

An earlier result of[START_REF] Djolonga | High-dimensional Gaussian process bandits[END_REF] gets O(T 4/5 ) regret while moreover assuming a perfect control of the sampling process (we can't assume this due to the user arrivals).

With additional prior knowledge of γn, the dependence of the additive term can be made polynomial in δ : choosing γn = min{1, δ /n}, it holds that ℓ(n0 -1 + N n=n 0 γn) 2 √ δ ℓT + ℓ .

Appendix C. Proof of Theorem 3

Proof Let M 1:t = (m A1 , . . . , m At ) ⊤ . The argument used to prove Theorem 2 in Yadkori et al, 2011, can be used to show that

where

Thus, letting v + t-1 := v • + V -1 t-1 Ū1:t-1 E 1:t-1 and using the above with techniques from Yadkori et al together with v • 2 R Θ , we have that

Appendix E. Extension of Theorem 3: Robustness of OFUL's regret with time-varying features

We now control the robust regret for user

We reindex the n ∈ [n 0 , N ], b n = b as t = 1, . . . , .. and prove the following result.

In the general case, it holds

Theorem 7 Let us introduce the confidence set

Then, under Assumption 2, and if

and thus

In the case when U is finite, using the Proof of Theorem B.1 in Rusmevichientong and Tsitsiklis (2010) then we further get for all ε > 0,

Thus, choosing ε = 2 log(|U|t |U | /δ), we obtain that

which concludes the proof of Theorem 6.

From the Proof of Theorem B.2 in [START_REF] Rusmevichientong | Linearly parameterized bandits[END_REF], it holds that for all ε > 2,

where k 0 = 2 1 + log(1 + 36R 2 X /λ 0 ), which leads to