Michal Valko

Rémi Munos
email: remi.munos@

Branislav Kveton
email: branislav.kveton@technicolor.

Tomáš Kocák
email: tomas.kocak@

Spectral Bandits for Smooth Graph Functions

Smooth functions on graphs have wide applications in manifold and semi-supervised learning.

In this paper, we study a bandit problem where the payoffs of arms are smooth on a graph. This framework is suitable for solving online learning problems that involve graphs, such as contentbased recommendation. In this problem, each item we can recommend is a node and its expected rating is similar to its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret with respect to the optimal policy would not scale poorly with the number of nodes. In particular, we introduce the notion of an effective dimension, which is small in real-world graphs, and propose two algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on real-world content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of nodes evaluations.

Introduction

A smooth graph function is a function on a graph that returns similar values on neighboring nodes. This concept arises frequently in manifold and semi-supervised learning [START_REF] Zhu | Semi-Supervised Learning Literature Survey[END_REF], and reflects the fact that the outcomes on the neighboring nodes tend to be similar. It is well-known [START_REF] Belkin | Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples[END_REF][START_REF] Belkin | Regularization and Semi-Supervised Learning on Large Graphs[END_REF]) that a smooth graph function can be expressed as a linear combination of the eigenvectors of the graph Laplacian with smallest eigenvalues. Therefore, the problem of learning such function can be cast as a regression problem on these eigenvectors. This is the first work that brings this concept to bandits. In particular, we study a bandit problem where the arms are the nodes of a graph and the expected payoff of pulling an arm is a smooth function on this graph.

We are motivated by a range of practical problems that involve graphs. One application is targeted advertisement in social networks. Here, the graph is a social network and our goal is to discover a part of the network that is interested in a given product. Interests of people in a social network tend to change smoothly [START_REF] Mcpherson | Birds of a Feather: Homophily in Social Networks[END_REF], because friends tend to have similar preferences. Therefore, we take advantage of this structure and formulate this problem as learning a smooth preference function on a graph.

Another application of our work are recommender systems [START_REF] Jannach | Recommender Systems: An Introduction[END_REF]. In content-based recommendation [START_REF] Chau | Apolo: making sense of large network data by combining rich user interaction and machine learning[END_REF], the user is recommended items that are similar to the items that the user rated highly in the past.

The assumption is that users prefer similar items similarly.

The similarity of the items can be measured for instance by a nearest neighbor graph [START_REF] Billsus | A learning agent for wireless news access[END_REF], where each item is a node and its neighbors are the most similar items.

In this paper, we consider the following learning setting.

The graph is known in advance and its edges represent the similarity of the nodes. At time t, we choose a node and then observe its payoff. In targeted advertisement, this may correspond to showing an ad and then observing whether the person clicked on the ad. In content-based recommendation, this may correspond to recommending an item and then observing the assigned rating. Based on the payoff, we update our model of the world and then the game proceeds into time t + 1. Since the number of nodes N can be huge, we are interested in the regime when t < N .

If the smooth graph function can be expressed as a linear combination of k eigenvectors of the graph Laplacian, and k is small and known, our learning problem can be solved using ordinary linear bandits [START_REF] Auer | Using confidence bounds for exploitationexploration trade-offs[END_REF][START_REF] Li | A Contextual-Bandit Approach to Personalized News Article Recommendation[END_REF].

In practice, k is problem specific and unknown. Moreover, the number of features k may approach the number of nodes N . Therefore, proper regularization is necessary, so that the regret of the learning algorithm does not scale with N . We are interested in the setting where the regret is independent of N and therefore this problem is non-trivial.

Setting

Let G be the given graph with the set of nodes V and denote |V| = N the number of nodes. Let W be the N × N matrix of similarities w ij (edge weights) and D is the N × N diagonal matrix with the entries

d ii = j w ij . The graph Laplacian of G is defined as L = D -W. Let {λ L k , q k } N k=1
be the eigenvalues and eigenvectors of L ordered such that

0 = λ L 1 ≤ λ L 2 ≤ • • • ≤ λ L N .
Equivalently, let L = QΛ L Q T be the eigendecomposition of L, where Q is an N × N orthogonal matrix with eigenvectors in columns.

In our setting we assume that the reward function is a linear combination of the eigenvectors. For any set of weights α let f α : V → R be the function defined on nodes, linear in the basis of the eigenvectors of L:

f α (v) = N k=1 α k (q k ) v = x v , α , where x v is the v-th row of Q, i.e., (x v ) i = (q i ) v .
If the weight coefficients of the true α * are such that the large coefficients correspond to the eigenvectors with the small eigenvalues and vice versa, then f α * would be a smooth function on G [START_REF] Belkin | Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples[END_REF]. Figure 1 displays first few eigenvectors of the Laplacian constructed from data we use in our experiments. In the extreme case, the true α * may be of the form [α * 1 , α * 2 , . . . , α * k , 0, 0, 0] T N for some k ≪ N . Had we known k in such case, the known linear bandits algorithm would work with the performance scaling with k instead of D = N . Unfortunately, first, we do not know k and second, we do not want to assume such an extreme case (i.e., α * i = 0 for i > k). Therefore, we opt for the more plausible assumption that the coefficients with the high indexes are small. Consequently, we deliver algorithms with the performance that scale with the smoothness with respect to the graph.

The learning setting is the following. In each time step t ≤ T , the recommender π chooses a node π(t) and obtains a noisy reward such that:

r t = x π(t) , α * + ε t ,
where the noise ε t is assumed to be R-sub-Gaussian for any t. In our setting, we have x v ∈ R D and x v 2 ≤ 1 for all x v . The goal of the recommender is to minimize the cumulative regret with respect to the strategy that always picks the best node w.r.t. α * . Let π(t) be the node picked (referred to as pulling an arm) by an algorithm π at time t.

The cumulative (pseudo) regret of π is defined as:

R T = T max v f α * (v) - T t=1 f α * (π(t))
We call this bandit setting spectral since it is built on the spectral properties of a graph. Compared to the linear and multi-arm bandits, the number of arms K is equal to the number of nodes N and to the dimension of the basis D (eigenvectors are of dimension N ). However, a regret that scales with N or D that can be obtained using those settings is not acceptable because the number of nodes can be large. While we are mostly interested in the setting with K = N , our algorithms and analyses can be applied for any finite K.

Related Work

Most related setting to our work is that of the linear and contextual linear bandits. [START_REF] Auer | Using confidence bounds for exploitationexploration trade-offs[END_REF] proposed a SupLin-Rel algorithm and showed that it obtains √ DT regret that matches the lower bound by [START_REF] Dani | Stochastic Lin-ear Optimization under Bandit Feedback[END_REF]. First practical and empirically successful algorithm was LinUCB [START_REF] Li | A Contextual-Bandit Approach to Personalized News Article Recommendation[END_REF]. Later, [START_REF] Chu | Contextual Bandits with Linear Payoff Functions[END_REF] [START_REF] Kleinberg | Multi-armed bandit problems in metric spaces[END_REF]; [START_REF] Slivkins | Contextual Bandits with Similarity Information[END_REF][START_REF] Bubeck | Xarmed bandits[END_REF] use similarity information between the context of arms, assuming a Lipschitz or more general properties.

While such settings are indeed more general, the regret bounds scale worse with the relevant dimensions. [START_REF] Srinivas | Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design[END_REF] and [START_REF] Valko | Finite-Time Analysis of Kernelised Contextual Bandits[END_REF] also perform maximization over the smooth functions that are either sampled from a Gaussian process prior or have a small RKHS norm. Their setting is also more general than ours since it already generalizes linear bandits. However their regret bound in the linear case also scales with D. Moreover, the regret of these algorithms also depends on a quantity for which dataindependent bounds exists only for some kernels, while our effective dimension is always computable given the graph.

Another bandit graph setting called the gang of bandits was studied by [START_REF] Cesa-Bianchi | A Gang of Bandits[END_REF] where each node is a linear bandit with its own weight vector which are assumed to be smooth on the graph. Next, [START_REF] Caron | Leveraging Side Observations in Stochastic Bandits[END_REF] assume that they obtain the reward not only from the selected node but also from all its neighbors. Yet another kind of the partial observability model for bandits on graphs in the adversarial setting is considered by [START_REF] Alon | From Bandits to Experts: A Tale of Domination and Independence[END_REF].

Spectral Bandits

In our setting, the arms are orthogonal to each other. Thinking that the reward observed for an arm does not provide any information for other arms would not be correct because of the assumption that under another basis, the unknown parameter has a low norm. This provides additional information across the arms through the estimation of the parameter. We could think of our setting as an N -armed bandit problem where N is larger than the time horizon T and the mean reward µ k for each arm k satisfies the property that under a change of coordinates, the vector has small weights, i.e., there exists a known orthogonal matrix U such that α = Uµ has a low norm. As a consequence, we can estimate α using penalization and then recover µ.

Given a vector of weights α, we define its Λ norm as:

α Λ = N k=1 λ k α 2 k = √ α T Λα (1)
We make use of this norm later in our algorithms. Intuitively, we would like to penalize the coefficients α that correspond to the eigenvectors with the large eigenvalues, in other words, to the less smooth basis functions on G.

Effective dimension

In order to present our algorithms and analyses, we introduce a notion of effective dimension d. We keep using capital D to denote the ambient dimension, which is equal to N in the spectral setting. Intuitively, the effective dimension is a proxy for the number of relevant dimensions. We first provide a formal definition and then discuss its properties.

In general, we assume there exists a diagonal matrix Λ with the entries 0

< λ = λ 1 ≤ λ 2 ≤ • • • ≤ λ N and a set of K vectors x 1 , . . . , x K ∈ R N such that x i 2 ≤ 1 for all i.
For the spectral bandits, we have K = N . Moreover, since Q is an orthonormal matrix, x i 2 = 1. Finally, since the first eigenvalue of a graph Laplacian is always zero, λ L 1 = 0, we use Λ = Λ L + λI, in order to have λ 1 = λ. Definition 1. Let the effective dimension d be the largest d such that:

(d -1)λ d ≤ T log(1 + T /λ)
The effective dimension d is small when the coefficients λ i grow rapidly above T . This is the case when the dimension of the space D (and K) is much larger than T , such as in graphs from social networks with very large number of nodes N . In contrast, when the coefficients are all small then d may be of the order of T , which would make the regret bounds useless. Figure 2 shows how d behaves compared to D on the generated and the real Flixster network graphs1 that we use for the experiments in Section 6. The actual form of Definition 1 comes from Lemma 6 and will become apparent in Section 5. The dependence of the effective dimension on T comes from the fact, that d is related to the number of "non-negligible" dimensions characterizing the space where the solution to the penalized least-squares may lie, since this solution is basically constrained to an ellipsoid defined by the inverse of the eigenvalues multiplied by T . Consequently, d is related to the metric dimension of this ellipsoid. Therefore, when T goes to infinity, the constraint is relaxed and all directions matter, thus the solution can be anywhere in a (bounded) space of dimension N . On the contrary, for a smaller T , the ellipsoid possesses a smaller number of "non-negligible" dimensions. Notice that it is natural that this effective dimension depends on T as we consider the setting T < N . If we wanted to avoid T in the definition of d, we could define it as well in terms of N by replacing T by N in Definition 1, but this would only loosen its value.

Algorithm 1 SPECTRALUCB

Input: N : the number of nodes, T : the number of pulls {Λ L , Q} spectral basis of L λ, δ : regularization and confidence parameters R, C : upper bounds on the noise and α * Λ Run:

Λ ← Λ L + λI d ← max{d : (d -1)λ d ≤ T / log(1 + T /λ)} for t = 1 to T do Update the basis coefficients α: X t ← [x 1 , . . . , x t-1 ] T r ← [r 1 , . . . , r t-1 ] T V t ← X t X T t + Λ αt ← V -1 t X T t r c t ← 2R d log(1 + t/λ) + 2 log(1/δ) + C Choose the node v t (x vt -th row of Q): v t ← arg max v f α(v) + c t x v V -1 t
Observe the reward r t end for

SPECTRALUCB

The first algorithm we present is SPECTRALUCB (Algorithm 1) which is based on LinUCB and uses the spectral penalty (1). For clarity, we set x t = x vt = x π(t) . Here we consider regularized least-squares estimate αt of the form:

αt = arg min α t v=1 [ x v , α -r v ] 2 + α Λ
A key part of the algorithm is to define the c t x V -1 t confidence widths for the prediction of the rewards. We take advantage of our analysis (Section 5.2) to define c t based on the effective dimension d which is specifically tailored to our setting. By doing this we also avoid the computation of the determinant (see Section 5). The following theorem characterizes the performance of SPECTRALUCB and bounds the regret as a function of effective dimension d. Theorem 1. Let d be the effective dimension and λ be the minimum eigenvalue of Λ.

If α * Λ ≤ C and for all x v , x v , α * ∈ [-1, 1],
then the cumulative regret of SPEC-TRALUCB is with probability at least 1 -δ bounded as:

R T ≤ 8R d log(1 + T /λ) + 2 log(1/δ) + 4C + 4 × dT log(1 + T /λ) Remark 1. The constant C needs to be such that α * Λ ≤ C.
If we set C too small, the true α * will lie outside of the region and far from αt , causing the algorithm to underperform. Alternatively, C can be time dependent, e.g., C t = log T . In such case, we do not need to know an upper bound on α * Λ in advance, but our regret bound would only hold after some t, when C t ≥ α * Λ .

Algorithm 2 SPECTRALELIMINATOR Input: N : the number of nodes, T : the number of pulls {Λ L , Q} spectral basis of L λ : regularization parameter β, {t j } J j parameters of the elimination and phases A 1 ← {x 1 , . . . , x K }. for j = 1 to J do V tj ← γΛ L + λI for t = t j to min(t j+1 -1, T ) do Play x t ∈ A j with the largest width to observe r t :

x t ← arg max x∈Aj x V -1 t V t+1 ← V t + x t x T t end for
Eliminate the arms that are not promising:

αt ← V -1 t [x tj , . . . , x t ][r tj , . . . , r t ] T p ← max x∈Aj αt , x -x V -1 t β A j+1 ← x ∈ A j , αt , x + x V -1 t β ≥ p end for
We provide the proof of Theorem 1 in Section 5 and examine the performance of SPECTRALUCB experimentally in Section 6. The d √ T result of Theorem 1 is to be compared with the classical linear bandits, where LinUCB is the algorithm often used in practice [START_REF] Li | A Contextual-Bandit Approach to Personalized News Article Recommendation[END_REF] achieving D √ T cumulative regret. As mentioned above and demonstrated in Figure 2, in the T < N regime we can expect d ≪ D = N and obtain an improved performance.

SPECTRALELIMINATOR

It is known that the available upper bound for LinUCB or OFUL is not optimal for the linear bandit setting with finite number of arms in terms of dimension D. On the other hand, the algorithms SupLinRel or SupLinUCB achieve the optimal √ DT regret. In the following, we likewise provide an algorithm that also scales better with d and achieves √ dT regret. The algorithm is called SPECTRALELIMINA-TOR (Algorithm 2) and works in phases, eliminating the arms that are not promising. The phases are defined by the time indexes t 1 = 1 ≤ t 2 ≤ . . . and depend on some parameter β. The algorithm is in a spirit similar to the Improved UCB by [START_REF] Auer | UCB Revisited: Improved Regret Bounds for the Stochastic Multi-Armed Bandit Problem[END_REF]. The main idea of SPECTRALELIMINATOR is to divide the time steps in to sets in order to introduce independence and allow the Azuma-Hoeffding inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF] to be applied. In the following theorem we characterize the performance of SPECTRALELIMINATOR and show that the upper bound on regret has √ d improvement over SPECTRALUCB.

Theorem 2. Choose the phases starts as t j = 2 j-1 . Assume all rewards are in [0, 1] and α * Λ ≤ C. For any δ > 0, with probability at least 1 -δ, the cumulative regret of SPECTRALELIMINATOR algorithm run with parameter β = 2R 14 log(2Klog 2 T /δ) + C is bounded as:

R T ≤ 4 log 2 2R 14 log 2K log 2 T δ +C dT log 1+ T λ

Scalability and computational complexity

There are three main computational issues to address in order to make SPECTRALUCB scalable: the computation of N UCBs, matrix inversion, and obtaining the eigenbasis which serves as an input to the algorithm. First, to speed up the computation of N UCBs in each time step, we use lazy updates technique [START_REF] Desautels | Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization[END_REF] which maintains a sorted queue of UCBs and in practice leads to substantial speed gains. Second, to speed up matrix inversion we do iterative matrix inversion [START_REF] Zhang | The Schur complement and its applications[END_REF].

Finally, while the eigendecomposition of a general matrix is computationally difficult, Laplacians are symmetric diagonally dominant (SDD). This enables us to use fast SDD solvers as CMG by [START_REF] Koutis | Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing[END_REF]. Furthermore, using CMG we can find good approximations to the first J eigenvectors in O(Jm log m) time, where m is the number of edges in the graph (e.g. m = 10N in the Flixter experiment). CMG can easily work with N in millions. In general, we have J = N but from our experience, a smooth reward function can be often approximated by dozens of eigenvectors. In fact, J can be considered as an upper bound on the number of eigenvectors we actually need. Furthermore, by choosing small J we not only reduce the complexity of eigendecomposition but also the complexity of the least-square problem being solved in each iteration.

Choosing a small J can significantly reduce the computation but it is important to choose J large enough so that still less than J eigenvectors are enough. This way, the problem that we solve is still relevant and our analysis applies.

In short, the problem cannot be solved trivially by choosing first k relevant eigenvectors because k is unknown. Therefore, in practice we choose the largest J such that our method is able to run. In Section 6.4, we demonstrate that we can obtain good results with relatively small J.

Analysis

The analysis of SPECTRALUCB (Section 5.3) has two main ingredients. The first one is the derivation of the confidence ellipsoid for α, which is a straightforward update of the analysis of OFUL (Abbasi-Yadkori et al., 2011) using self-normalized martingale inequality (Section 5.1). The second part is crucial to prove that the final regret bound scales only with the effective dimension d and not with the ambient dimension D. We achieve this by considering the geometrical properties of the determinant which hold in our setting (Section 5.2). We also used this result to upperbound the regret of SPECTRALELIMINATOR (Section 5.4).

The proofs of the lemmas are in the appendix.

Confidence ellipsoid

The first two lemmas are by Abbasi-Yadkori et al. ( 2011) and we restate them for the convenience. Lemma 1. Let V t = X t-1 X T t-1 + Λ and define ξ t = t s=1 ε s x s . With probability at least 1 -δ, ∀t ≥ 1:

ξ t 2 V -1 t ≤2R 2 log |V t | 1/2 δ|Λ| 1/2
Lemma 2. We have:

t s=1 min 1, x s 2 V -1 s-1 ≤ 2 log |V t | |Λ|
The next lemma is a generalization of Theorem 2 by Abbasi-Yadkori et al. ( 2011) to the regularization with Λ. The result of this lemma is also used for the confidence coefficient c t in Algorithm 1, which we upperbound in Section 5.2 to avoid the computation of determinants. Lemma 3. Let V t = X t-1 X T t-1 + Λ and α * Λ ≤ C. For any x and t ≥ 1, with probability at least 1 -δ:

|x T ( αt -α * )| ≤ x V -1 t R 2 log |V t | 1/2 δ|Λ| 1/2 + C

Effective dimension

In Section 5.1 we show that several quantities scale with log(|V T |/|Λ|), which can be of the order of D. Therefore, in this part we present the key ingredient of our analysis based on the geometrical properties of determinants (Lemmas 4 and 5) to upperbound log(|V T |/|Λ|) by a term that scales with d (Lemma 6). Not only this will allow us to show that the regret scales with d, but it also helps us to avoid the computation of the determinants in Algorithm 1. Lemma 4. Let Λ = diag(λ 1 , . . . , λ N ) be any diagonal matrix with strictly positive entries and for any vectors

(x t ) 1≤t≤T such that x t 2 ≤ 1 for all 1 ≤ t ≤ T , we have that the determinant |V T | of V T = Λ + T t=1 x t x T t
is maximized when all x t are aligned with the axes. Lemma 5. For any T , let V T = T t=1 x t x T t + Λ. Then:

log |V T | |Λ| ≤ max N i=1 log 1 + t i λ i ,
where the maximum is taken over all possible positive real numbers {t 1 , . . . , t N }, such that N i=1 t i = T . Lemma 6. Let d be the effective dimension. Then:

log |V T | |Λ| ≤ 2d log 1 + T λ

Cumulative regret of SPECTRALUCB

Proof of Theorem 1. Let x * = arg max xv x T v α * and let rt denote the instantaneous regret at time t. With probability at least 1 -δ, for all t:

rt = x T * α * -x T t α * ≤ x T t αt + c t x t V -1 t -x T t α * (2) ≤ x T t αt + c t x t V -1 t -x T t αt + c t x t V -1 t (3) = 2c t x t V -1 t .
The inequality (2) is by the algorithm design and reflects the optimistic principle of SPECTRALUCB. Specifically,

x T * α * + c t x * V -1 t ≤ x T t αt + c t x t V -1 t
, from which:

x T * α * ≤ x T t αt + c t x t V -1 t -c t x * V -1 t ≤ x T t αt + c t x t V -1 t
In (3) we applied Lemma 3:

x T t αt ≤ x T t α * + c t x t V -1 t .
Finally, by Lemmas 2 and 6 and the assumption rt ≤ 2:

R T = T t=1 rt ≤ T T t=1 r2 t ≤ 2 max(1, c T ) T T t=1 min 1, x t 2 V -1 t ≤ 2(c T + 1) 2T log(|V T |/|Λ|) ≤ 4(c T + 1) dT log(1 + T /λ)
Above, we used that c t ≤ c T because c t is nondecreasing. By plugging c T , we get that with probability at least 1 -δ:

R T ≤ 4 R 2 log(|V T |/|Λ|) + 2 log(1/δ) + C + 1 × dT log(1 + T /λ) ≤ 8R d log(1 + T /λ) + 2 log(1/δ) + 4C + 4 × dT log(1 + T /λ) Remark 2. Notice that if we set Λ = I in

Cumulative regret of SPECTRALELIMINATOR

The probability space induced by the rewards r 1 , r 2 , . . . can be decomposed as a product of independent probability spaces induces by rewards in each phase [t j , t j+1 -1].

Denote by F j the σ-algebra generated by the rewards r 1 , . . . , r tj+1-1 , i.e., received before and during the phase j. We have the following three lemmas for any phase j. Let us write V j for V tj and αj for αtj . Lemma 7. For any fixed x ∈ R N and any δ > 0, we have that if β(α * , δ) = 2R 14 log(2/δ) + α * Λ , then at time t j (beginning of phase j):

P |x T ( αj -α * )| ≤ x V -1 j β(α * , δ) ≥ 1 -δ
Lemma 8. For all x ∈ A j , we have:

x 2 V -1 j ≤ 1 t j -t j-1 tj s=tj-1+1 x s 2 V -1 s-1
Lemma 9. For each phase j, we have:

tj s=tj-1+1 min 1, x s 2 V -1 s-1 ≤ log |V j | |Λ|
Combining all the lemmas above together we obtain: Lemma 10. For each j, x, and δ, with probability at least 1 -δ:

min 1,|x T ( αj -α * )| ≤ β(α * , δ) 1 t j -t j-1 2d log 1 + t j -t j-1 λ
Now we are ready to upperbound the cumulative regret of SPECTRALELIMINATOR.

Proof of Theorem 2. Let J = ⌊log 2 T ⌋. We have:

R T = n t=1 x * -x t , α * = J j=0 tj+1-1 t=tj x * -x t , α * = ≤ J j=0 (t j+1 -t j ) x * -x t , αj + ( x * V -1 j + x t V -1 j )β ,
in an event Ω of probability 1 -KJδ, where we used Lemma 7 in the last inequality. By definition of the action subset A j at phase j, under Ω, we have:

x * -x t , αj ≤ ( x * V -1 j + x t V -1 j )β,
since x * ∈ A j for all j ≤ J. By previous lemma: [START_REF] Auer | Using confidence bounds for exploitationexploration trade-offs[END_REF] and as a corollary to Theorem 2 also enjoys Õ( √ DT ) upper bound on the cumulative regret. On the other hand, compared to SupLin-Rel, LINEARELIMINATOR and its analysis are significantly much simpler and elegant.

R T ≤ 2 J j=0 (t j+1 -t j )β(α * , δ) 1 t j -t j-1 × 2d log 1 + t j -t j-1 λ ≤ 4 log 2 β dT log 1 + T λ

Experiments

We evaluated our algorithms and compared them to Lin-UCB. In all experiments we set δ to 0.001 and R to 0.01. For SPECTRALUCB and SPECTRALELIMINATOR we set Λ to Λ L + λI with λ = 0.01. For LinUCB we regularized with λI with λ = 1. Our results are robust to small perturbations of all learning parameters. We also performed experiments with SupLinRel, SupLinUCB, Sup-SpectralUCB 2 , but due to the known reasons [START_REF] Chu | Contextual Bandits with Linear Payoff Functions[END_REF] these algorithms are not efficient 3 and they were always outperformed by SPECTRALUCB and LinUCB.

Random graph models

To simulate realistic graph structures, we generated graphs of N nodes using three models that are commonly used in the social networks modeling. First, we considered the widely known Erdős-Rényi (ER) model. We sampled the edges in the ER model independently with probability 3%. Second, we considered the Barabási-Albert (BA) model ( 1999), with the degree parameter 3. BA models are commonly used for modeling real networks due to their preferential attachment property. Finally, we considered graphs where the edge structure forms a regular lattice.

For all the graph models we assigned uniformly random weights to their edges. Then, we randomly generated ksparse vector α * of N weights, k ≪ N and defined the true graph function as f = Qα * , where Q is the matrix of eigenvectors from the eigendecomposition of the graph Laplacian. We ran the algorithms in the desired T < N regime, with N = 500 (N = 54 for the lattice), T = 250, 2 an equivalent of SupLinUCB with spectral regularization 3 at least for the sizes of N and T that we deal with and k = 5. Figure 3 shows that the regret of LinUCB for all three models has within first T steps still a linear trend unlike SPECTRALUCB that performs much better.

Unfortunately, even though the regret bound Spectral Eliminator is asymptotically better, it was outperformed by SPECTRALUCB. This is similar to the linear case when LinUCB outperforms 4 SupLinUCB in practice [START_REF] Chu | Contextual Bandits with Linear Payoff Functions[END_REF] while it is open problem whether LinUCB can be shown to have a better regret.

MovieLens experiments

In this experiment we took user preferences and the similarity graph over movies from the MovieLens dataset [START_REF] Lam | MovieLens 1M Dataset[END_REF], a dataset of 6k users who rated one million movies. We divide the dataset into two equally-sized parts. The first dataset is used to build our model of users, the rating that user i assigns to movie j. We factor the user-item matrix using low-rank matrix factorization [START_REF] Keshavan | Matrix Completion from a Few Entries[END_REF] as M ≈ UV ′ , a standard approach to collaborative filtering. The rating that the user i assigns to movie j is estimated as ri,j = u i , v j , where u i is the i-th row of U and v j is the j-th row of V. The rating ri,j is the payoff of pulling arm j when recommending to user i. The second dataset is used to build our similarity graph over movies. We factor the dataset in the same way as the first dataset. The graph contains an edge between movies i and i ′ if the movie i ′ is among 10 nearest neighbors of the movie i in the latent space of items V. The weight on all edges is one. Notice that if two items are close in the item space, then their expected rating is expected to be similar. However, the opposite is not true. If two items have a similar expected rating, they do not have to be close in the item space. In other words, we take advantage of ratings but do not hardwire the two similarly rated items to be similar.

In Figure 4, we sampled 50 users and evaluated the regret of both algorithms for T = 100. Here SPECTRALUCB suffers only about one fourth of regret over LinUCB, specifically 43.4611 vs. 133.0996 on average.

Flixter Experiments

We also performed experiments on users preferences from the movie recommendation website Flixter. The social network of the users was crawled by [START_REF] Jamali | A matrix factorization technique with trust propagation for recommendation in social networks[END_REF] and then clustered by [START_REF] Graclus | [END_REF] to obtain a strongly connected subgraph. We extracted a subset of users and movies, where each movie has at least 30 ratings and each user rated at least 30 movies. This resulted in a dataset of 4546 movies and 5202 users. As with MovieLens dataset we completed the missing ratings by a low-rank matrix factorization and used it construct a 10-NN similarity graph.

Again in Figure 4, we sampled 50 users and evaluated the regret of both algorithms for T = 100. On average, SPEC-TRALUCB suffers only about one third of regret over Lin-UCB, specifically 37.6499 vs. 99.8730 on average.

Reduced basis

As discussed in Section 4.4, one can decrease the computational complexity and thus increase the scalability by only extracting first J ≪ N eigenvectors of the graph Laplacian. First, the computational complexity of such operation is O(Jm log m), where m is the number of edges. Second, the least-squares problem that we have to do in each time step of the algorithm is only J dimensional.

In Figure 5 we plot the cumulative regret and the total computational time in seconds (log scale) for a single user from the MovieLens dataset. We varied J as 20, 200, and 2000 which corresponds to about 1%, 10% and 100% of basis functions (N = 2019). The total computational time also includes the computational savings from lazy updates and iterative matrix inversion. We see that with 10% of the eigenvectors we can achieve similar performance as for the full set for the fraction of the computational time.

Conclusion

We presented spectral bandit setting inspired mostly by the applications in the recommender systems and targeted advertisement in social networks. In this setting, we are asked to repeatedly maximize an unknown graph function, assumed to be smooth on a given similarity graph. Traditional linear bandit algorithm can be applied but their regret scales with the ambient dimension D, either linearly or as a square root, which can be very large.

Therefore, we introduced two algorithms, SPECTRALUCB and SPECTRALELIMINATOR, for which the regret only scales with effective dimension d which is typically much smaller than D for real-world graphs. We demonstrated that SPECTRALUCB delivers desired benefit for the graphs generated by Barabási-Albert, Erdős-Rényi, and regular lattice models; and for the movie rating data from the MovieLens and Flixster social networks. In future, we plan to extend this work to a sparse setting when the smooth function is assumed to be a linear combination of only finite number of eigenvectors.

Acknowledgements

We would like to thank Yiannis Koutis for his great help with the efficient computation of eigenvectors. We thank Andreas Krause for suggesting the lazy updates of UCBs. We would also like to thank Giovanni Zappella, Claudio Gentile, and especially Alessandro Lazaric for helpful discussions.

Supplementary Material

Confidence ellipsoid Lemma 3. Let V t = X t-1 X T t-1 + Λ and α * Λ ≤ C. For any x and t ≥ 1, with probability at least 1 -δ:

|x T ( αt -α * )| ≤ x V -1 t R 2 log |V t | 1/2 δ|Λ| 1/2 + C
Proof of Lemma 3. We have:

|x T ( αt -α * )| = |x T (-V -1 t Λα * + V -1 t ξ t )| ≤ |x T V -1 t Λα * | + |x T V -1 t ξ t | ≤ x T , Λα * V -1 t + x, ξ t V -1 t ≤ x V -1 t ξ t V -1 t + Λα * V -1 t ,
where we used Cauchy-Schwarz inequality in the last step. Now we bound ξ t V -1 t by Lemma 1 and notice that:

Λα * V -1 t = (α * ) T ΛV -1 t Λα * ≤ (α * ) T Λα * = α * Λ ≤ C
Effective dimension Lemma 11. For any real positive-definite matrix A with only simple eigenvalue multiplicities and any vector x such that x 2 ≤ 1 we have that the determinant |A + xx T | is maximized by a vector x which is aligned with an eigenvector of A.

Proof of Lemma 11. Using Sylvester's determinant theorem, we have:

|A + xx T | = |A||I + A -1 xx T | = |A|(1 + x T A -1 x)
From the spectral theorem, there exists an orthonormal matrix U, the columns of which are the eigenvectors of A; such that A = UDU T with D being a diagonal matrix with the positive eigenvalues of A on the diagonal. Thus:

max x 2≤1 x T A -1 x = max x 2≤1 x T UD -1 U T x = max y 2≤1 y T D -1 y, since U is a bijection from {x, x 2 ≤ 1} to itself.
Since there are no multiplicities, it is easy to see that the quadratic mapping y → y T D -1 y is maximized (under the constraint y 2 ≤ 1) by a canonical vector e I corresponding to the lowest diagonal entry I of D. Thus the maximum of x → x T A -1 x is reached for Ue I , which is the eigenvector of A corresponding to its lowest eigenvalue. For any 1 ≤ t ≤ T , let us define:

V -t = Λ + T s=1 s =t x s x T s
We have that V T = V -t + x t x T t . Consider the case with only simple eigenvalue multiplicities. In this case, Lemma 11 implies that x t → d(x 1 , . . . , x t , . . . , x T ) is maximized when x t is aligned with an eigenvector of V -t . Thus all x t , for 1 ≤ t ≤ T , are aligned with an eigenvector of V -t and therefore also with an eigenvector of V T . Consequently, the eigenvectors of

T t=1 x t x T t are also aligned with V T . Since Λ = V T - T t=1 x t x T
t and Λ is diagonal, we conclude that V T is diagonal and all x t are aligned with the canonical axes. Now in the case of eigenvalue multiplicities, the maximum of |V T | may be reached by several sets of vectors {(x m t ) 1≤t≤T } m but for some m * , the set (x m * t ) 1≤t≤T will be aligned with the axes. In order to see that, consider a perturbed matrix V ε -t by a random perturbation of amplitude at most ε, i.e. such that V ε -t → V -t when ε → 0. Since the perturbation is random, then the probability that Λ ε , as well as all other V ε -t possess an eigenvalue of multiplicity bigger than 1 is zero. Since the mapping ε → V ε -t is continuous, we deduce that any adherent point xt of the sequence (x ε t ) ε (there exists at least one since the sequence is bounded in ℓ 2 -norm) is aligned with the limit V -t and we can apply the previous reasoning.

P |x T ( αj -α * )| ≤ x V -1 j β(α * , δ) ≥ 1 -δ
Proof of Lemma 7. Defining ξ j = tj s=tj-1+1 x s ε s , we have:

|x T ( αj -α * )| = |x T (-V -1 j Λα * + V -1 j ξ j )| ≤ |x T V -1 j Λα * | + |x T V -1 j ξ j | (4)
The first term in the right hand side of ( 4) is bounded as:

|x T V -1 j Λα * | ≤ x T V -1 j Λ 1/2 Λ 1/2 α * = α * Λ x T V -1 j ΛV -1 j x ≤ α * Λ x T V -1 j x = α * Λ x V -1 j
Now consider the second term in the r.h.s. of (4). We have:

x T V -1 t ξ j = tj s=tj-1+1 (x T V -1 j x s )ε s
Let us notice that the points (x s ) selected by the algorithm during phase j -1 only depend on their width x V -1 s which does not depend on the rewards received during the phase j -1. Thus, given F j-2 , the sequence (x s ) tj-1+1≤s<tj is deterministic. Consequently, one may use a variant of Azuma's inequality [START_REF] Shamir | A Variant of Azuma's Inequality for Martingales with Subgaussian Tails[END_REF]:

P |x T V -1 j ξ j | 2 ≤ 28R 2 2 log(2/δ)× × x T V -1 j tj s=tj-1+1
x s x T s V -1 j x F j-2 ≥ 1 -δ, from which we deduce:

P |x T V -1 j ξ j | 2 ≤ 56R 2 x T V -1 j x log(2/δ) F j-2 ≥ 1-δ,
since tj s=tj-1+1 x s x T s ≺ V j . Thus:

P |x T V -1 j ξ j | ≤ 2R x V -1 j 14 log(2/δ) ≥ 1 -δ
Lemma 8. For all x ∈ A j , we have:

x 2 V -1 j ≤ 1 t j -t j-1 tj s=tj-1+1 x s 2 V -1 s-1
Proof of Lemma 8. We have:

(t j -t j-1 ) x 2 V -1 j ≤ max x∈Aj tj s=tj-1+1 x 2 V -1 s-1 ≤ tj s=tj-1+1 max x∈Aj x 2 V -1 s-1 ≤ tj s=tj-1+1 max x∈Aj-1 x 2 V -1 s-1 = tj s=tj-1+1 x s 2 V -1 s-1
, since the algorithm selects (during phase j -1) the arms with largest width. Lemma 9. For each phase j, we have:

tj s=tj-1+1 min 1, x s 2 V -1 s-1 ≤ log |V j | |Λ| .
Proof of Lemma 9. This lemma is proved by instantiating Lemma 2 for each phase.

  Proceedings of the31 st International Conference on Machine Learning, Beijing, China, 2014. JMLR: W&CP volume 32. Copyright 2014 by the authors.

Figure 1 .

 1 Figure 1. Eigenvectors from the Flixster data corresponding to the smallest few eigenvalues of the graph Laplacian projected onto the first principal component of data. Colors indicate the values.

Figure 2 .

 2 Figure 2. Effective dimension d in the regime T < N . The effective dimension for this data is much smaller than the ambient dimension D = N , which is 500 and 4546 respectively.

  Algorithm 1, we recover LinUCB. Since log(|V T |/|Λ|) can be upperbounded by D log T (Abbasi-Yadkori et al., 2011), we obtain Õ(D √ T ) upper bound of regret of LinUCB as a corollary of Theorem 1.

Figure 3 .

 3 Figure 3. Cumulative regret for random graphs models Remark 3. If we set Λ = I in Algorithm 2 as in Remark 2, we get a new algorithm, LINEARELIMINATOR, which is a competitor to SupLinRel[START_REF] Auer | Using confidence bounds for exploitationexploration trade-offs[END_REF] and as a corollary to Theorem 2 also enjoys Õ( √ DT ) upper bound on the cumulative regret. On the other hand, compared to SupLin-Rel, LINEARELIMINATOR and its analysis are significantly much simpler and elegant.

Figure 4 .Figure 5 .

 45 Figure 4. MovieLens and Flixter: Cumulative regret for 50 randomly chosen users. Horizontal axis shows the user number.

  The research presented in this paper was supported by French Ministry of Higher Education and Research, by European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n o 270327 (project CompLACS), and by Intel Corporation.

  Lemma 4. Let Λ = diag(λ 1 , . . . , λ N ) be any diagonal matrix with strictly positive entries. Then for any vectors (x t ) 1≤t≤T , such that x t 2 ≤ 1 for all 1 ≤ t ≤ T , we have that the determinant |V T | of V T = Λ + Proof of Lemma 4. Let us write d(x 1 , . . . , x T ) = |V T | the determinant of V T . We want to characterize:

		T t=1 x t x T
	max x1,...,xn: xt 2≤1,∀1≤t≤T	d(x 1 , . . . , x T )

t is maximized when all x t are aligned with the axes.

  Lemma 5. For any T , let V T = where the maximum is taken over all possible positive real numbers {t 1 , . . . , t N }, such thatN i=1 t i = T .Proof of Lemma 5. We want to bound the determinant |V T | under the coordinate constraints x t 2 ≤ 1. Let:M (x 1 , . . . , x T ) = Λ +From Lemma 4 we deduce that the maximum of M is reached when all x t are aligned with the axes: Lemma 6. Let d be the effective dimension. Then: For any fixed x ∈ R N and any δ > 0, we have that if β(α * , δ) = 2R 14 log(2/δ) + α * Λ , then at time t j (beginning of phase j):

											T
											x t x T
											t=1
											T
	M =	max x1,...,x T ;xt∈{e1,...,e N }	Λ +	t=1	x t x T t
		=	max t1,...,t N positive integers, N i=1	ti=T	diag(λ i + t i )
											N
		≤	max t1,...,t N positive reals, N i=1	ti=T	i=1	λ i + t i ,
	from which we obtain the result.
				log	|V T | |Λ|	≤ 2d log 1 +	T λ
	Proof of Lemma 6. Using Lemma 5 and Definition 1:
	log	|V T | |Λ|	≤	d i=1	log 1 +	T λ	+	N i=d+1	log 1 +	t i λ d
				≤ d log 1 +	T λ	+	N i=1	t i λ d+1
				≤ d log 1 +	T λ	+	T λ d+1
				≤ 2d log 1 +	T λ
	SPECTRALELIMINATOR
	Lemma 7.
											T t=1 x t x T t + Λ. Then:
											log	|V T | |Λ|	≤ max	N i=1	log 1 +	t i λ i	,

t

We set Λ to ΛL + λI with λ = 0.01, where ΛL is the graph Laplacian of the respective graph.

For example, these algorithms do not to use all the rewards obtained for the estimation of α.