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

Rémi Munos
email: munos@google.com

Branislav Kveton
email: bkveton@google.com

Shipra Agrawal

Michal Valko
email: valkom@deepmind.com

Peter Auer

Spectral bandits

Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this work, 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 content-based recommendation. In this problem, each item we can recommend is a node of an undirected graph and its expected rating is similar to the one of 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 three algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of node 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][START_REF] Valko | Online semi-supervised learning on quantized graphs[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 (see Figure 1 for an example). Therefore, the problem of learning such function can be cast as a regression problem on these eigenvectors. The present work brings this concept to bandits [START_REF] Valko | Bandits on graphs and structures[END_REF]. 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] Miller 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. We remove all the users that rated a small number of movies as well as the movies rated by only a few users. This leaves us with a u × m matrix M where u is the number of users and m is the number of movies and entry M i, j of matrix M is the rating of movie j by user i, provided it exists. Note that matrix M might be missing some of the entries.

(2) Filling in the missing entries: For this step, we use low-rank matrix factorization [START_REF] Keshavan | Matrix completion from a few entries[END_REF] to obtain u × r matrix U and m × r matrix V, for some given rank r, such that M ≈ UV T .

(3) Constructing a similarity graph: We construct the graph by creating an edge between movies i and j if the movie j is among 5 nearest neighbors of the movie i in the latent space of movies V. (4) Visualization: Using the computed matrix V, the matrix capturing the latent space of movies, we can find the direction of the highest variance of the data using PCA on V. This gives us a way to visualize eigenvectors by projecting them on the first principal component. The above visualization shows that the eigenvectors corresponding to smaller eigenvalues tend to be smoother-the values corresponding to actions with their projections close to each other are similar. On the other hand, the eigenvectors corresponding to larger eigenvalues are more chaotic as values for nearby items can vary a lot. This gives a small insight into why a function created as a linear combination of the first few eigenvectors is a smooth reward function. We are more precise about the definition of smoothness and the connection of smooth functions and eigenvectors later in Section 4.

Another application of our work are recommender systems [START_REF] Jannach | Recommender systems: An introduction[END_REF]. In content-based recommendation [START_REF] Horng | 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 is 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.

We consider the following learning setting. The graph is known in advance and its edges represent the similarity of the nodes. At round 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 has clicked on it. 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 round t + 1. In both applications described above, the learner (advertiser) has rarely the budget (time horizon T ) to try all the options even once. Furthermore, imagine that the learner is a movie recommender system and would ask the user to rate all the movies before it starts producing relevant recommendations. Such a recommender system would be of little value. Yet, many bandit algorithms start with pulling each arm once. This is something that we cannot afford and therefore, contrary to standard bandits, we consider the case T N , where the number of nodes N is huge. While we are mostly interested in the regime when t < N , our results are beneficial also for t > N . This regime is especially challenging since traditional multi-arm bandit algorithms need to try every arm.

If the smooth graph function is 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 exploitation-exploration trade-offs[END_REF][START_REF] Varsha | Stochastic linear optimization under bandit feedback[END_REF][START_REF] Li | A contextual-bandit approach to personalized news article recommendation[END_REF]Agrawal and Goyal, 2013b;[START_REF] Abeille | Linear Thompson sampling revisited[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 this makes the problem we study non-trivial.

Early short versions of our work appeared at International Conference on Machine Learning [START_REF] Valko | Spectral bandits for smooth graph functions[END_REF] and AAAI Conference on Artificial Intelligence (Kocák et al., 2014b). Compared to those, we give a new and improved definition of the effective dimension that is smaller than the old one, provide a matching lower bound, improved the regret bounds for two of our algorithm, and report a comprehensive empirical evaluation on artificial datasets as well as on the Movielens and Flixster datasets.

Setting

In this section, we formally define the spectral bandit setting. Let G be the given graph with the set of nodes V and denote N |V| the number of nodes. Let W be the symmetric N × N matrix of similarities w ij (edge weights) and D be the N × N diagonal matrix with entries d ii j w ij (node degrees). 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 an eigendecomposition of L, where Q is an N × N orthogonal matrix with eigenvectors in columns.
The eigenvectors of the graph Laplacian form a basis. Therefore, we can represent the reward function as 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 T 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]. For more details, see Section 4.1. Figure 1 displays the first few eigenvectors of the Laplacian constructed from the data that 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 bandit algorithms 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.

We now define the learning setting. In each round t ≤ T , the recommender chooses a node a t and obtains a noisy reward such that

r t x T at α + ε t ,
where the noise ε t is assumed to be zero mean and conditionally independent R-sub-Gaussian random variable for any t, that is, E [exp(sε t )] ≤ exp(R 2 s 2 /2), for all s ∈ R and E [ε t ] = 0. 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 a t be the node picked (referred to as pulling an arm) by an algorithm at round t. The cumulative (pseudo-) regret of an algorithm is defined as

R T T max v f α (v) - T t=1 f α (a 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 (the eigenvectors are of dimension N ). However, a regret that scales with N or D that can be obtained using those approaches 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 are valid for any finite K.

Related work

The most related settings to our work are that of the linear and contextual linear bandits. For these settings, [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF] proposed SupLinRel and showed that it obtains √ DT regret which matches the lower bound by [START_REF] Varsha | Stochastic linear optimization under bandit feedback[END_REF]. However, the 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] analyzed SupLinUCB, which is a LinUCB equivalent of SupLinRel, to show that it also obtains √ DT regret. [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] proposed OFUL for linear bandits which obtains D √ T regret. Using their analysis, it is possible to show that LinUCB obtains D √ T regret as well (Remark 25). Whether LinUCB matches the √ DT lower bound for this setting is still an open problem.

Apart from the above optimistic approaches, an older approach to the problem is Thompson sampling (TS, Thompson, 1933). It solves the exploration-exploitation dilemma by a simple and intuitive rule: when choosing the next action to play, choose it according to the probability that it is the best one; that is the one that maximizes the expected payoff. [START_REF] Chapelle | An empirical evaluation of Thompson sampling[END_REF] showed its practical relevance to the computational advertising. This motivated the researchers to explain the success of TS [START_REF] Agrawal | Analysis of Thompson sampling for the multi-armed bandit problem[END_REF][START_REF] Kaufmann | Thompson sampling: An asymptotically optimal finite-time analysis[END_REF][START_REF] May | Optimistic Bayesian sampling in contextual-bandit problems[END_REF]Agrawal and Goyal, 2013a;[START_REF] Abeille | Linear Thompson sampling revisited[END_REF]. The most relevant results for our work are by Agrawal and Goyal (2013b), who bring a new martingale technique, enabling us to analyze cases where the payoffs of the actions are linear in some basis. [START_REF] Jacob D Abernethy | Competing in the dark: An efficient algorithm for bandit linear optimization[END_REF] and [START_REF] Bubeck | Towards minimax policies for online linear optimization with bandit feedback[END_REF] studied a more difficult adversarial setting of linear bandits where the reward function is time-dependent. It is an open problem if this approaches would work in our setting and have an upper bound on the regret that scales better than with D. [START_REF] Kleinberg | Multi-armed bandit problems in metric spaces[END_REF], [START_REF] Slivkins | Contextual bandits with similarity information[END_REF], and [START_REF] Bubeck | X -armed 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 | Finitetime 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 data-independent bounds exist 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. These weight vectors are assumed to be smooth on the graph. [START_REF] Gentile | Online clustering of bandits[END_REF] take a different approach to similarities in social networks by assuming that the actions are clustered into several unknown clusters and the actions within one cluster have the same expected reward. This approach can be applied also to the setting presented in our paper. The biggest advantage of the CLUB algorithm by [START_REF] Gentile | Online clustering of bandits[END_REF] is that it constructs graph iteratively, starting with complete graph and removing edges which are not likely to be presented in the underlying clustering. Therefore, the algorithm does not need to know the similarity graph unlike in our setting. However, theoretical improvement of CLUB compared to the basic bandit algorithm comes from the small number of clusters. Therefore, if the number of clusters is close to the number of actions the algorithm does not bring any improvement while the algorithms in our setting still can leverage the similarity structure. [START_REF] Li | Collaborative filtering bandits[END_REF] and [START_REF] Gentile | On context-dependent clustering of bandits[END_REF] later extended the approach to double-clustering where both the users and the items are assumed to appear in clusters (with the underlying clustering unknown to the learner) and [START_REF] Korda | Distributed clustering of linear bandits in peer to peer networks[END_REF] considers a distributed extension. Yet another assump-tion of a special graph reward structure is exploited by unimodal bandits (Yu and Mannor, 2011;[START_REF] Combes | Unimodal bandits: Regret lower bounds and optimal algorithms[END_REF]. One of the settings considered by Yu and Mannor (2011) is a graph bandit setting where every path in the graph has unimodal rewards and therefore also imposes a specific kind of smoothness with respect to the graph topology. In networked bandits [START_REF] Fang | Networked bandits with disjoint linear payoffs[END_REF], the learner picks a node, but besides receiving the reward from that node, its reward is the sum of the rewards of the picked node and its neighborhood. The algorithm of [START_REF] Fang | Networked bandits with disjoint linear payoffs[END_REF], NetBandits, can also deal with changing topology, however, this has to be always revealed to the learner before it makes its decision.

Furthermore, bandits with side observations treat a different graph bandit setting where the learner obtains not only the reward from the selected action but also the rewards from the neighbors of the selected action. This setting was studied in both the stochastic case [START_REF] Caron | Leveraging side observations in stochastic bandits[END_REF][START_REF] Buccapatnam | Stochastic bandits with side observations on networks[END_REF] and the adversarial one [START_REF] Mannor | From bandits to experts: On the value of side-observations[END_REF][START_REF] Noga Alon | From bandits to experts: A tale of domination and independence[END_REF]Kocák et al., 2014a;[START_REF] Noga Alon | Nonstochastic multi-armed bandits with graph-structured feedback[END_REF][START_REF] Noga Alon | Online learning with feedback graphs: Beyond bandits[END_REF]Kocák et al., 2016a,b). For a comprehensive discussion, we refer to survey on graph bandits [START_REF] Valko | Bandits on graphs and structures[END_REF].

Spectral bandits with different objectives In the follow-up work on spectral bandits, there have been algorithms optimizing other objective function than the cumulative regret. First, in some sensor networks, sensing a node (pulling an arm) has an associated cost [START_REF] Sunil | Signal processing techniques for interpolation in graph structured data[END_REF]. In a particular, cheap bandit setting [START_REF] Hanawal | Cheap bandits[END_REF], it is cheaper to get an average of rewards of a set of nodes than a specific reward of a single one. More precisely, the learner pays the cost for the action which depends on the spectral properties of the graph while relying on the property that getting the average reward of many nodes is less costly than getting a reward of a single node. For this setting, [START_REF] Hanawal | Cheap bandits[END_REF] proposed CheapUCB that reduces the cost of sampling by 1/4 as compared to SpectralUCB, while maintaining O(d √ T ) cumulative regret. Next, Gu and Han (2014) study the online classification setting on graphs with bandit feedback, very similar to spectral bandits; after predicting the class the oracle returns a single bit indicating whether the prediction is correct or not. The analysis of their algorithm delivers essentially the same bound on the regret, however, they need to know the number of relevant eigenvectors d. Moreover, [START_REF] Ma | Active search and bandits on graphs using sigma-optimality[END_REF] consider several variants of Σ-optimality that favors specific exploration when selecting the nodes, for example, the learner is not allowed to play one arm multiple times. The authors were able to show a regret bound which scales with the effective dimension that we defined in our prior work [START_REF] Valko | Spectral bandits for smooth graph functions[END_REF].

Spectral bandits

In this section, we show how to leverage the smoothness of the rewards on a given graph. In our setting, the features of the arms (contexts) form a basis and therefore 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 an additional information across the arms through the estimation of the parameter α.

Smooth graph functions

There are several possible ways to define the smoothness of the function f with respect to the undirected graph G. We are using the one which is standard in the spectral clustering [START_REF] Von | A tutorial on spectral clustering[END_REF] and semi-supervised learning [START_REF] Belkin | Manifold regularization: A geometric framework for learning from labeled and unlabeled examples[END_REF], defined as

S G (f ) 1 2 i, j∈[N ] w i,j (f (i) -f (j)) 2 .
Therefore, whenever the function values of the nodes connected by an edge with large weight are close, the smoothness of the function with respect to the graph is small and the function is smoother with respect to the graph. This definition has several useful properties. We are mainly interested in the following one,

S G (f ) = f T Lf = f T QΛQ T f = α T Λα = α 2 Λ = N i=1 λ i α 2 i ,
where f = (f (1), . . . , f (N )) T is the vector of the function values, QΛQ T is an eigendecomposition of the graph laplacian L, and α = Q T f is the representation of the vector f in the eigenbasis. The assumption on the smoothness of the reward function with respect to the underlying graph is reflected by the small value of S G (f ) and therefore, the components of α corresponding to the large eigenvalues should be small as well.

As a result, we can think of our setting as an N -arm bandit problem where N is possibly larger than the time horizon T and the mean reward f (k) for each arm k satisfies the property that under a change of coordinates, the vector f of mean rewards has small components, i.e., there exists a known orthogonal matrix U such that α = Uf has a low norm. As a consequence, we can estimate α using penalization corresponding to the large eigenvalues and to recover f . Given a vector of weights α, we define its Λ-norm as

α Λ N i=1 λ i α 2 i = √ α T Λα. ( 1
)
This norm is closely related to the smoothness of the function and we use it later in our algorithms by regularization which enforces small Λ-norm of α.

Effective dimension

In order to present and analyze our algorithms, we use a notion of effective dimension denoted by (lower case) d. While we introduced a slightly different version of the effective dimension for spectral bandits previously [START_REF] Valko | Spectral bandits for smooth graph functions[END_REF], we now present an improved definition. This new definition of effective dimension enables us to prove tighter regret bounds for our algorithms. In the rest of the paper, we refer to the old definition of the effective dimension, introduced by [START_REF] Valko | Spectral bandits for smooth graph functions[END_REF], as d old . We keep using capital D to denote the ambient dimension (the number of features). Intuitively, the effective dimension is a proxy for the number of relevant dimensions. We first provide a formal definition and then discuss its properties, including d < d old D.

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

< λ = λ 1 ≤ λ 2 ≤ • • • ≤ λ N and a set of N vectors x 1 , . . . , x N ∈ R N such that x i 2 ≤ 1 for all i.
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 = λ > 0.
Definition 1 The effective dimension d is defined as

d     max log N i=1 1 + t i λ i log 1 + T Kλ    
, where the maximum is taken over all possible non-negative real numbers {t 1 , . . . , t N }, such that N i=1 t i = T and K is the number of zero eigenvalues of Λ L . K is also the number of components of G.

Remark 2 Note that if we first upper bound every 1/λ i in the numerator by 1/λ then the maximum is acquired for t i equal to T /N . Therefore, the right-hand side of the definition is bounded from above by D = N . This means that d is upper bounded by D. Later we show that in many practical situations, d is much smaller than D.

For the comparison, we show the previous definition of the effective dimension [START_REF] Valko | Spectral bandits for smooth graph functions[END_REF] and from now we call it old effective dimension denoted by d old .

Definition 3 (old effective dimension, [START_REF] Valko | Spectral bandits for smooth graph functions[END_REF] Let the old effective dimension d old be the largest

d old ∈ [N ] such that (d old -1)λ d old ≤ T log(1 + T /λ) •
Remark 4 Note that from Lemma 5 and Lemma 6 by [START_REF] Valko | Spectral bandits for smooth graph functions[END_REF], we see that the relation between the old and new definition of the effective dimension is: d ≤ 2d old . As we show later, the bounds using the effective dimension scale either with d or with 2d old . Moreover, we show that d is usually much smaller than 2d old and therefore using the new definition of the effective dimension brings an improvement to the bound.

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 is much larger than T , such as in graphs from social networks with a very large number of nodes N . In contrast, when the coefficients λ i are all small (if the graph is sparse, all eigenvalues of Laplacian are small) then d may be of the order of T . That would make the regret bounds useless.

The actual form of Definition 1 comes from Lemma 24 and becomes apparent in Section 6. 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. This ellipsoid is wide in the directions corresponding to the small eigenvalues and narrow in the directions corresponding to the large ones. After playing an action, the confidence ellipsoid shrinks in the directions of the action. Therefore, exploring in a direction where the ellipsoid is wide can reduce the volume of the ellipsoid much more than exploring in a direction where the ellipsoid is narrow. In fact, for a small T , the axes of the ellipsoid corresponding to the large eigenvalues of L are negligible. Consequently, d is related to the metric dimension of this ellipsoid. Therefore, when T tends to infinity, then 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.

The computation of the effective dimension

All of the algorithms that we propose need to know the value of the effective dimension in order to leverage the structure of the problem. Therefore, it is necessary to compute it beforehand. when computing the effective dimension, we proceed in two steps:

1. Finding an N -tuple (t 1 , . . . , t N ) which maximizes the expression from the definition of the effective dimension.

2. Plugging the N -tuple to the definition of the effective dimension.

We now focus on the first step. The following lemma gives us an efficient way to determine the N -tuple

Lemma 5 Let ω ∈ [N ] be the largest integer such that ω i=1 λ i ω + T ω -λ ω > 0,
then t 1 , . . . , t N that maximize the expression in the definition of the effective dimension are in the following form,

t i = ω i=1 λ i ω + T ω -λ i for i = 1, . . . , ω, t i = 0 for i = ω + 1, . . . , N.
Proof First of all, we use the fact that logarithm is an increasing function and that the N -tuple which maximizes the expression is invariant to a multiplication of the expression by a constant, arg max log

N i=1 1 + t i λ i = arg max N i=1 1 + t i λ i = arg max N i=1 (λ i + t i ) .
The last expression is easy to maximize since we know that for any ∆ ≥ δ ≥ 0 and for any real number a we have

0 ≤ ∆ 2 -δ 2 a 2 -∆ 2 ≤ a 2 -δ 2 (a -∆)(a + ∆) ≤ (a -δ)(a + δ).
Therefore, if we take any two terms (λ i + t i ) and (λ j + t j ) from the expression which we are maximizing, we can potentially increase their product simply by balancing them,

t new i λ i + λ j + t i + t j 2 -λ i t new j λ i + λ j + t i + t j 2 -λ j .
However, we still have to take into consideration that every t i has to be positive. Therefore, if, for example, t new j is negative, we can simply set

t new i t i + t j t new j 0.
We apply this argument to the expression we are trying to maximize to obtain the statement of the lemma.

The second part is straightforward. To avoid computational difficulties of multiplying N numbers, we use properties of logarithm to get

d =     max log N i=1 1 + t i λ i log 1 + T Kλ     =     max N i=1 log 1 + t i λ i log 1 + T Kλ    
• Knowing an N -tuple which maximizes the expression, we simply plug it in and obtain the value of the effective dimension.

The old vs. new definition of the effective dimension

As we mentioned in Remark 4, our new effective dimension is always upperbounded by 2d old .

In this section, we show that the gap between d and 2d old can be significant. We demonstrate on the graphs constructed for several real-world datasets and also on several random graphs. in Section 7. The figures clearly demonstrate the gap between d and 2d old while both of the quantities are much smaller then D. In fact, effective dimension d is much smaller than D even for T > N (Figures 2 and3). Therefore, spectral bandits can be used even for T > N while maintaining the advantage of better regret bounds compared to the linear bandit algorithms.

Lower bound

In this section, we show a lower bound for the spectral setting. More precisely, for each possible value of effective dimension d and time horizon T , we show the existence of a "hard" problem with a lower bound of Ω( √ dT ). We prove the theorem by reducing a carefully selected problem to a multi-arm bandit problem with d arms and using the following lower bound for it.

Theorem 6 [START_REF] Auer | The nonstochastic multi-armed bandit problem[END_REF] For any number of actions K ≥ 2 and for any time horizon T , there exists a distribution over the assignment of Bernoulli rewards such that the expected regret of any algorithm (where the expectation is taken with respect to both the randomization over rewards and the algorithms internal randomization) is at least

R T ≥ 1 20 min √ KT , T .
Theorem 6 can also be proved without the randomization device. The constant 1/20 in the lower bound above can be improved into 1/8 (Cesa-Bianchi and Lugosi, 2006, Theorem 6.11). We now state a lower bound for spectral bandits, featuring the effective dimension d.

Theorem 7 For any T and d, there exists a problem with effective dimension d and time horizon T such that the expected regret of any algorithm is of Ω( √ dT ).

Proof We define a problem with the set of actions consisting of K = d blocks. Each block is a complete graph K M T on M T vertices. Moreover, all weights of the edges inside a component are equal to one. We define M T as a T -dependent constant such that the effective dimension of the problem d is exactly K. We specify the precise value of M T later.

On top of the structure described above, we choose a reward function with smoothness 0, i.e., a constant on each of the components of the graph. In fact, even knowing that the reward function is constant on individual components, this problem is as difficult as the multi-arm bandit problem with K arms. Therefore, the lower bound of Ω( √ KT ) of the K-arm bandit problem applies to our setting too. Consequently, we have the lower bound of Ω( √ dT ), since d = K. The last part of the proof is to show that d = K and therefore, we have to specify value of M T . The graph consists of K blocks consisting M T vertices each. Therefore, the graph Laplacian is the following matrix

L = 0 0 (M T -1) -1 . . . -1 -1 . . . . . . -1 -1 . . . -1 (M T -1) . . . (M T -1) -1 . . . -1 -1 . . . . . . -1 -1 . . . -1 (M T -1)                                                                           . Now we compute eigenvalues of L to obtain L eigenvalues -------→ K 0, . . . , 0, (M T -1)K M T , . . . , M T .
We plug the above eigenvalues to the definition of the effective dimension and to set the value of M T to obtain

d =     max log K i=1 1 + t i λ KM T i=K+1 1 + t i λ+M T log 1 + T Kλ    
• By setting M T ≥ T /K, we have that the maximum in the definition is obtained for

t 1 = • • • = t K = T /K and t K+1 = • • • = t KM T = 0. Therefore, d = log K i=1 1 + T Kλ log 1 + T Kλ = K i=1 log 1 + T Kλ log 1 + T Kλ = K.
This means that our problem is at least as difficult as the multi-arm bandit problem with K = d arms and therefore, the lower bound for K-arm bandits (Theorem 6) applies.

Algorithms

In this section, we introduce the algorithms for spectral bandits: SpectralUCB, SpectralTS, and SpectralEliminator. For each algorithm, we state the regret bound and later we R, C: upper bounds on the noise and α Λ 7: Initialization:

8: V 1 ← Λ ← Λ L + λI 9: α 1 ← 0 N 10: d ← (max log N i=1 (1 + t i /λ i ))/ log(1 + T /(Kλ)) (Definition 1) 11: c ← R 2d log(1 + T /(Kλ)) + 8 log(1/δ) + C 12: Run: 13: for t = 1 to T do 14:
Choose the node a t (a t -th row of Q):

a t ← arg max a x T a α t + c x a V -1 t 15:
Observe a noisy reward r t ← x T at α + ε t 16:

Update the basis coefficients α:

17:

V t+1 ← V t + x at x T at 18: α t+1 ← V -1 t+1 t s=1
x as r s 19: end for discuss the computational advantages and compare the theoretical regret bounds of the algorithms with the lower bound provided in the previous section. Full proofs are given in Section 6.

SpectralUCB

We first present SpectralUCB (Algorithm 1) which is based on LinUCB [START_REF] Li | A contextual-bandit approach to personalized news article recommendation[END_REF] and uses the spectral penalty (1) in its least-square estimate. Here, we consider a regularized least-squares estimate α t of the form

α t arg min w∈R N t s=1 x T as w -r as 2 + w 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 and consequently the upper confidence bounds (UCBs). We take advantage of our analysis (Section 6.3) to define c t based on the effective dimension d which is tailored to our setting. This way we also avoid the computation of the determinant (see Section 6). The following theorem characterizes the performance of SpectralUCB and bounds the regret as a function of effective dimension d.

Theorem 8 Let d be the effective dimension and λ be the minimum eigenvalue of Λ. If α Λ ≤ C and for all x a , x T a α ∈ [-1, 1], then the cumulative regret of SpectralUCB is with probability at least 1 -δ bounded as

R T ≤ 2R 2d log 1 + T Kλ + 8 log 1 δ + 2C + 2 2dT log 1 + T Kλ ≤ O d √ T .
Remark 9 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, in particular when C t ≥ α Λ .

We provide the proof of Theorem 8 in Section 6 and examine the performance of our SpectralUCB experimentally in Section 7. The d

√

T result of Theorem 8 is to be compared with the standard 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 Figures 2 and3, in the T < N regime we can expect d D = N and obtain an improved performance.

SpectralTS

The second algorithm presented in this paper is SpectralTS which is based on LinearTS, analyzed by Agrawal and Goyal (2013b), and uses Thompson sampling to decide which arm to play. Specifically, we represent our current knowledge about α as a normal distribution

N ( α t , v 2 V -1 t )
, where α t is our actual approximation of the unknown vector α and v 2 V -1 t reflects our uncertainty about it. As mentioned before, we assume that the reward function is a linear combination of eigenvectors of graph Laplacian L with large coefficients corresponding to the eigenvectors with small eigenvalues. We encode this assumption into our initial confidence ellipsoid by setting V 1 Λ Λ L + λI, where λ is again a regularization parameter.

In every round t, we generate a sample α t from the distribution N ( α t , v 2 V -1 t ), choose an arm a t which maximizes x T i α t , and receive a reward. Afterwards, we update our estimate of α and the confidence of it, i.e., we compute α t+1 and V t+1 ,

V t+1 = V t + x at x T at and α t+1 = V -1 t+1 t s=1
x as r s .

Remark 10 Since TS is a Bayesian approach, it requires a prior to run and we choose it here to be a Gaussian. However, this does not pose any assumption whatsoever about the actual data both for the algorithm and the analysis. The only assumptions we make about the data are: (a) that the mean payoff is linear in the features, (b) that the noise is sub-Gaussian, and (c) that we know a bound on the Laplacian norm of the mean reward function. We provide a frequentist bound on the regret (and not an average over the prior) which is a much stronger worst-case result.

Algorithm 2 SpectralTS 1: Input:

2:

N : number of actions 3:

T : number of rounds 4:

{Λ L , Q}: spectral basis of a graph Laplacian L 5:

λ, δ: regularization and confidence parameters 6:

R, C: upper bounds on the noise and α Λ 7: Initialization:

8: V 1 ← Λ ← Λ L + λI N 9: α 1 ← 0 N 10: d ← (max log N i=1 (1 + t i /λ i ))/ log(1 + T /(Kλ)) (Definition 1)
11:

v ← R 3d log(1/δ + T /(δλK)) + C 12: Run: 13: for t = 1 to T do 14:

Sample α t ∼ N ( α t , v 2 V -1 t ) 15:
Choose the node a t (a t -th row of Q): a t ← arg max a x T a α 16:

Observe a noisy reward r t ← x T at α + ε t

17:

Update the basis coefficients α:

18:

V t+1 ← V t + x at x T at 19: α t+1 ← V -1 t+1 t s=1
x as r s 20: end for

The following theorem upperbounds the cumulative regret of SpectralTS in terms of the effective dimension.

Theorem 11 Let d be the effective dimension and λ be the minimum eigenvalue of Λ. If α Λ ≤ C and for all x a , x T a α ∈ [-1, 1], then the cumulative regret of SpectralTS is with probability at least 1 -δ bounded as

R T ≤ 11g p 2 + 2λ λ dT log 1 + T Kλ + 1 T + g p 11 √ λ + 2 2T log 2 δ
, where p = 1/(4e √ π) and

g = 4 log(T N ) R 3d log 1 δ + T δλK + C + R d log T 2 δ + T 3 δλK + C.
Remark 12 Substituting g and p, we see that the regret bound scales as d √ T log N . Note that N = D could be exponential in d and therefore we need to consider factor √ log N in our bound. On the other hand, if N is indeed exponential in d, then our algorithm scales with log D √ T log D = log(D) 3/2 √ T which is even better. β, {t j } J j : parameters of the elimination and phases where J = log 2 T + 1 7:

SpectralEliminator

A 1 ← {x 1 , . . . , x K } 8: for j = 1 to J do 9:

V t j ← Λ L + λI 10: for t = t j to min(t j+1 -1, T ) do 11:
Play available arm a t (x at ∈ A j ) with the largest width and observe r t :

12: Eliminate the arms that are not promising:

a t ← arg max a|xa∈A j x a V -1 t 13: V t+1 ← V t + x at x T
16: α j+1 ← V -1 t+1 [x t j , . . . , x t ][r t j , . . . , r t ] T 17: A j+1 ← x ∈ A j , α j+1 , x + x V -1 t+1 β ≥ max x∈A j α j+1 , x -x V -1 t+1 β 18: end for
It is known that the available upper bound for LinUCB, LinearTS, or OFUL is not tight for linear bandits with a 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 similarly provide an algorithm that also scales better with d and achieves a √ dT regret. The algorithm is called SpectralEliminator (Algorithm 3) 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 ImprovedUCB by [START_REF] Auer | UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem[END_REF]. As a special case and as a side result of independent interest, we give also the LinearEliminator algorithm. LinearEliminator achieves the optimal √ DT regret and uses adaptive confidence intervals, unlike SupLinRel or SupLinUCB, that use data-agnostic confidence intervals of the form 2 -u for u ∈ N 0 .

In the following theorem, we characterize the performance of SpectralEliminator and show that the upper bound on its regret has a √ d improvement over SpectralUCB and SpectralTS.

Theorem 13 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 run with parameter β R log(2K(1 + log 2 T )/δ)+ C is bounded as

R T ≤ 2 + 8 R 2 log 2K(1 + log 2 T ) δ + C + 1 2 2dT log 2 (T ) log 1 + T λK •

Scalability and computational complexity

There are three main computational issues to address in order to make proposed algorithms scalable: the computation of N UCBs (applies to SpectralUCB), the matrix inversion, and obtaining the eigenbasis which serves as an input to any of the algorithms. First, to speed up the computation of N UCBs (that in general takes N 3 time) in each round, we use lazy updates [START_REF] Desautels | Parallelizing explorationexploitation tradeoffs in Gaussian process bandit optimization[END_REF] which maintains a sorted queue of UCBs and using the fact that the UCB for every arm can only decrease after the update. Therefore, the algorithm does not need to update all UCBs in each round. In practice, lazy updates lead to light-speed gains. This issue does not apply to SpectralTS since we only need to sample α which can be done in N 2 time and find a maximum of x T i α which can be also done in N 2 time. In general, the computational complexity of sampling in SpectralTS is better than the complexity of computing the N UCBs in SpectralUCB. However, using lazy updates can significantly speed up SpectralUCB up to the point that SpectralUCB is comparable to SpectralTS.

Second, all of the proposed algorithms need to compute inverse if N × N matrix in each round which is costly. However, we can use Sherman-Morrison formula to invert the matrix iteratively and thus speed up the inversion since the matrix changes only by adding a rank-one matrix from one round to the next one.

Finally, while an 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 L eigenvectors in O(Lm log m) time, where m is the number of edges in the graph (e.g., m = 10N for Flixter data, Section 7.5). CMG can easily work with N in millions. In general, we have L = N but from our experience, a smooth reward function can be often approximated by dozens of eigenvectors. In fact, L can be considered as an upper bound on the number of eigenvectors we actually need. Furthermore, by choosing small L we not only reduce the complexity of an eigendecomposition but also the complexity of the least-square problem that is solved in each round.

Choosing a small L can significantly reduce the computation but it is important to choose L large enough so that still less than L eigenvectors are enough. This way, the problem that we solve remains 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 L such that our method is able to run. In Section 7.3, we demonstrate that we can obtain good results with relatively small L.

Analysis

We are now ready to prove regret bounds for all algorithms. First, we show some general preliminary results (Section 6.1). Then, we present several auxiliary lemmas concerning confidence ellipsoid of the estimate (Section 6.2) and effective dimension (Section 6.3). Using these results we upperbound the regrets of SpectralUCB (Section 6.4), SpectralTS (Section 6.5), and SpectralEliminator (Section 6.6).

Preliminaries

The first lemma is a standard anti-concentration inequality for a Gaussian random variable.

Lemma 14 For a Gaussian distributed random variable Z with mean m and variance σ 2 , for any z ≥ 1,

1 2 √ πz e -z 2 2 ≤ P (|Z -m| > σz) ≤ 1 √ πz e -z 2 2 .
Multiple applications of Sylvester's determinant theorem gives our second preliminary lemma.

Lemma 15

Let V t = Λ + t-1 s=1 x s x T s , then log |V t | |Λ| = t-1 s=1 log 1 + x s 2 V -1 s .
Third lemma says that adding a rank-one matrix to a symmetric positive semi-definite matrix implies the following Löwner ordering for their inverses.

Lemma 16 For any symmetric, positive semi-definite matrix X, and any vectors u and y, y T (X + uu T ) -1 y ≤ y T X -1 y.

Proof Using Sherman-Morrison formula and the fact that inverse of a symmetric matrix is again symmetric, we have

- u T X -1 y T u T X -1 y 1 + u T X -1 u ≤ 0 y T X -1 - X -1 uu T X -1 1 + u T X -1 u y ≤ y T X -1 y y T (X + uu T ) -1 y ≤ y T X -1 y.
Corollary 17 Let V t Λ + t-1 s=1 x s x T s . Then for any vector x and for any positive integers t 1 and t 2 satisfying

t 1 ≤ t 2 , ||x|| V -1 t 1 ≥ ||x|| V -1 t 2 .

Confidence ellipsoid

We restate the two lemmas by [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] for convenience.

Lemma 18 (Abbasi-Yadkori et al., 2011, Lemma 9) -Yadkori et al., 2011, Lemma 11) For any round t, let us define

Let V t Λ + t-1 s=1 x s x T s and define ξ t t-1 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 19 (Abbasi
V t Λ + t-1 s=1 x s x T s . Then, t s=1 min 1, x s 2 V -1 s ≤ 2 log |V t+1 | |Λ| •
The next lemma is a generalization of Theorem 2 by Abbasi-Yadkori et al. ( 2011) to the regularization with Λ.

Lemma 20 Let V t Λ + t-1 s=1 x s x T s and α Λ ≤ C. With probability at least 1 -δ, for any x and t ≥ 1,

|x T α t -x T α| ≤ x V -1 t R 2 log |V t | 1/2 δ|Λ| 1/2 + C . Proof We have that |x T α t -x 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 2 t V -1 2 t Λα| + |x T V -1 2 t V -1 2 t ξ t | ≤ x V -1 t ξ t V -1 t + Λα V -1 t ,
where we use Cauchy-Schwarz inequality in the last step. Now, we bound ξ t V -1 t by Lemma 18 and using Corollary 17 we bound ||Λα|| V -1

t as Λα V -1 t ≤ Λα V -1 1 = Λα Λ -1 = α Λ ≤ C.

Effective dimension

In Section 6.2, 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 22 and 23), to upperbound log(|V t |/|Λ|) by a term that scales with d (Lemma 24). Not only this allows us to show that the regret bound scales with d, but it also helps us to avoid the computation of the determinants in Algorithm 1.

Lemma 21 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 Using Sylvester's determinant theorem, we have that

|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.
As 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.

Lemma 22 Let Λ diag(λ 1 , . . . , λ N ) be any diagonal matrix with strictly positive entries. For any vectors (x s ) 1≤s<t such that x s 2 ≤ 1 for all 1 ≤ s < t, we have that the determinant

|V t | of V t Λ + t-1 s=1 x s x T
s is maximized when all x s are aligned with the axes.

Proof Let us write d(x 1 , . . . , x t-1 ) |V t | the determinant of V t . We want to characterize max

x 1 ,...,x t-1 : xs 2 ≤1,∀1≤s<t d (x 1 , . . . , x t-1 ).
For any 1 ≤ i < t, let us define

V -i Λ + t-1 s=1 s =i
x s x T s .

We have that V t = V -i +x i x T i . Consider the case with only simple eigenvalue multiplicities. In this case, Lemma 21 implies that x i → d(x 1 , . . . , x i , . . . , x t-1 ) is maximized when x i is aligned with an eigenvector of V -i . Thus all x s , for 1 ≤ s < t, are aligned with an eigenvector of V -i and therefore also with an eigenvector of V t . Consequently, the eigenvectors of t-1 s=1 x s x T s are also aligned with V t . Since Λ = V t -t-1 s=1 x s x T s and Λ is diagonal, we conclude that V t is diagonal and all x s 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 s ) 1≤s<t } m but for some m , the set (x m s ) 1≤s<t will be aligned with the axes. In order to see that, consider a perturbed matrix V ε -i by a random perturbation of amplitude at most ε, i.e. such that V ε -i → V -i when ε → 0. Since the perturbation is random, then the probability that Λ ε , as well as all other V ε -i possess an eigenvalue of multiplicity bigger than 1 is zero. Since the mapping ε → V ε -i is continuous, we deduce that any adherent point x i of the sequence (x ε i ) ε (there exists at least one since the sequence is bounded in 2 -norm) is aligned with the limit V -i and we apply the previous reasoning.

Lemma 23 For any t, let V t t-1 s=1 x s x T s + Λ. 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 -1.
Proof We want to bound the determinant |V t | under the coordinate constraints

x s 2 ≤ 1. Let M (x 1 , . . . , x t-1 ) Λ + t-1 s=1
x s x T s .

From Lemma 22, we deduce that the maximum of M is reached when all x t are aligned with the axes,

M = max x 1 ,...,x t-1 ;xs∈{e 1 ,...,e N } Λ + t-1 s=1 x s x T s = max t 1 ,...,t N positive integers, N i=1 t i =t-1 |diag (λ i + t i )| ≤ max t 1 ,...,t N positive reals, N i=1 t i =t-1 N i=1 (λ i + t i ),
from which we obtain the result.

Lemma 24 Let d be the effective dimension and t ≤ T + 1. Then,

log |V t | |Λ| ≤ d log 1 + T Kλ •
Proof Using Lemma 23 and Definition 1 we have

log |V t | |Λ| ≤ max N i=1 log 1 + t i λ i = max N i=1 log 1 + t i λ i log(1 + T /(Kλ)) log 1 + T Kλ ≤     max N i=1 log 1 + t i λ i log(1 + T /(Kλ))     log 1 + T Kλ = d log 1 + T Kλ •

Regret bound of SpectralUCB

The analysis of SpectralUCB 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 the self-normalized martingale inequality from Section 6.2. The second part is crucial for showing 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 that hold in our setting (Section 6.3).

Proof [Theorem 8] Let x arg max xv x T v α and let R T (t) denote the instantaneous regret at round t. With probability at least 1 -δ, for all t:

R T (t) = x T α -x T at α ≤ x T at α t + c x at V -1 t -x T at α (2) ≤ x T at α t + c x at V -1 t -x T at α t + c x at V -1 t (3) = 2c x at V -1 t ,
where ( 2) is by algorithm design and reflects the optimistic principle of SpectralUCB. Specifically,

x T α t + c x V -1 t ≤ x T at α t + c x at V -1 t , from which x T α ≤ x T α t + c x V -1 t ≤ x T at α t + c x at V -1 t .
In (3), we apply Lemma 20,

x T at α t ≤ x T at α + c x at V -1 t
. Now, by Lemmas 19 and 24,

R T = T t=1 R T (t) ≤ T t=1 min 2, 2c x at V -1 t ≤ (2 + 2c) T t=1 min 1, x at V -1 t ≤ (2 + 2c) T T t=1 min 1, x at 2 V -1 t ≤ (2 + 2c) 2T log |V T +1 | |Λ| ≤ (2 + 2c) 2dT log 1 + T Kλ •
By plugging c, we get that the theorem holds with probability at least 1 -δ. [START_REF] Chu | Contextual bandits with linear payoff functions[END_REF] applies to a related but different SupLinUCB, which is not efficient.

Regret bound of SpectralTS

The regret bound of SpectralTS is based on the proof technique of Agrawal and Goyal (2013b). Before applying the technique, we first give an intuitive explanation. Each round an arm is played, our algorithm improves the confidence about our actual estimate of α via an update of V t and thus the update of the confidence ellipsoid. However, when we play a suboptimal arm, the regret we obtain can be much higher than the improvement of our knowledge. To overcome this difficulty, the arms are divided into two groups of saturated and unsaturated arms, based on whether the standard deviation for an arm is smaller than the standard deviation of the optimal arm (Definition 27) or not. Consequently, the optimal arm is in the group of unsaturated arms. The idea is to bound the regret of playing an unsaturated arm in terms of standard deviation and to show that the probability that the saturated arm is played is small enough. This way, we overcome the difficulty of high regret and small knowledge obtained by playing an arm.

Definition 26

We define E α (t) as the event when for all i,

|x T i α t -x T i α| ≤ x i V -1 t ,
where

R d log T 2 δ + T 3 δλK + C,
and E α (t) as the event when for all i,

|x T i α t -x T i α t | ≤ v x i V -1 t 4 ln(T N ), where v R 3d log 1 δ + T δλK + C.
Definition 27 Let ∆ i x T a αx T i α. We say that an arm i is saturated at round t if ∆ i > g x i V -1 t and unsaturated otherwise, including the optimal arm a . Let C(t) denote the set of saturated arms at round t.

Definition 28 We define the filtration F t-1 as the union of the history until round t -1 and features,

F t-1 {H t-1 } ∪ {x i , i = 1, . . . , N }. By definition, F 1 ⊆ F 2 ⊆ • • • ⊆ F T -1 .
Lemma 29 For all t, 0 < δ < 1, P(E α (t)) ≥ 1 -δ/T 2 , and for all possible filtrations F t-1 ,

P E α (t) | F t-1 ≥ 1 - 1 T 2 •
Proof Bounding the probability of event E α (t): Using Lemma 20, where C is such that α Λ ≤ C, for all i with probability at least 1 -δ we have that

|x T i ( α t -α)| ≤ x i V -1 t R 2 log |V t | 1/2 δ |Λ| 1/2 + C = x i V -1 t R log |V t | |Λ| + 2 log 1 δ + C .
Therefore, using Lemma 24 and substituting δ = δ/T 2 , we get that with probability at least 1 -δ/T 2 , for all i,

|x T i ( α t -α)| ≤ x i V -1 t R d log 1 + T Kλ + d log T 2 δ + C = x i V -1 t R d log T 2 δ + T 3 δλK + C = x i V -1 t .
Bounding the probability of event E α (t): The probability of each individual term |x T i ( α t -α t )| < 4 log(T N ) can be bounded using Lemma 14 to get

P |x T i ( α t -α t )| ≥ v x i V -1 t 4 log(T N ) ≤ e -2 log T N π4 log(T N ) ≤ 1 T 2 N •
We complete the proof by taking a union bound over all N vectors x i . Notice that we took a different approach than Agrawal and Goyal (2013b) to avoid the dependence on the ambient dimension D.

Lemma 30 For any filtration F t-1 such that E α (t) is true,

P x T a α t > x T a α | F t-1 ≥ 1 4e √ π •
Proof Since x T a α t is a Gaussian random variable with the mean x T a α t and the standard deviation v x a V -1 t , we can use the anti-concentration inequality from Lemma 14,

P x T a α t ≥ x T a α | F t-1 = P x T a α t -x T a α t v x a V -1 t ≥ x T a α -x T a α t v x a V -1 t | F t-1 ≥ 1 4 √ πZ t e -Z 2 t ,
where

|Z t | x T a α -x T a α t v x a V -1 t .
Since we consider filtration F t-1 such that E α (t) is true, we can upperbound the numerator to get

|Z t | ≤ x a V -1 t v x a V -1 t = v ≤ 1.
Finally,

P x T a α t > x T a α | F t-1 ≥ 1 4e √ π • Lemma 31 For any filtration F t-1 such that E α (t) is true, P (a t ∈ C(t) | F t-1 ) ≥ 1 4e √ π - 1 T 2 •
Proof The algorithm chooses the arm with the highest value of x T i α t to be played at round t. Therefore, if x T a α t is greater than x T j α t for all saturated arms, i.e., x T a α t > x T j α t , ∀j ∈ C(t), then one of the unsaturated arms (that include the optimal arm and other suboptimal unsaturated arms) must be played. Therefore,

P (a t ∈ C(t) | F t-1 ) ≥ P x T a α t > x T j α t , ∀j ∈ C(t) | F t-1 .
By definition, for all saturated arms j ∈ C(t), ∆ j > g x j V -1 t

. Now if both of the events E α(t) and E α(t) are true, then, by definition of these events, for all j ∈ C(t),

x T j α t ≤ x T j α t + g x j V -1 t . Therefore, given filtration F t-1 , such that E α (t) is true, either E α (t) is false, otherwise for all j ∈ C(t), x T j α t ≤ x T j α + g x j V -1 t ≤ x T a α.
Hence, for any F t-1 such that E α (t) is true,

P x T a α t > x T j α t , ∀j ∈ C(t) | F t-1 ≥ P x T a α t > x T a α | F t-1 -P E α (t) | F t-1 ≥ 1 4e √ π - 1 T 2
, where in the last inequality we used Lemma 29 and Lemma 30.

Lemma 32 For any filtration F t-1 such that E α (t) is true,

E [∆ at | F t-1 ] ≤ 11g p E x at V -1 t | F t-1 + 1 T 2 •
Proof Let a t denote the unsaturated arm with the smallest norm

x i V -1 t , a t arg min i ∈C(t) x i V -1 t .
Notice that since C(t) and x i V -1 t for all i are fixed on fixing F t-1 , so is a t . Now, using Lemma 31, for any F t-1 such that E α (t) is true,

E x at V -1 t | F t-1 ≥ E x at V -1 t | F t-1 , a t ∈ C(t) P (a t ∈ C(t) | F t-1 ) ≥ x at V -1 t 1 4e √ π - 1 T 2 •
Now, if events E α (t) and E α (t) are true, then for all i, by definition,

x T i α t ≤ x T i α+g x i V -1 t .
Using this observation along with x T at α t ≥ x T i α t for all i,

∆ at = ∆ at + (x T at α -x T at α) ≤ ∆ at + (x T at α t -x T at α t ) + g x at V -1 t + g x at V -1 t ≤ ∆ at + g x at V -1 t + g x at V -1 t ≤ g x at V -1 t + g x at V -1 t + g x at V -1 t .
Therefore, for any

F t-1 such that E α (t) is true, either ∆ at ≤ 2g x at V -1 t + g x at V -1 t , or E α (t) is false. We can deduce that E [∆ at | F t-1 ] ≤ E 2g x at V -1 t + g x at V -1 t | F t-1 + P E α (t) ≤ 2g p -1 T 2 E x at V -1 t | F t-1 + gE x at V -1 t | F t-1 + 1 T 2 ≤ 11g p E x at V -1 t | F t-1 + 1 T 2
, where in the last inequality we used that 1/(p -1/T 2 ) ≤ 5/p, which holds trivially for T ≤ 4. For T ≥ 5, we know that p = 1/(4e √ π) and therefore T 2 ≥ 5e √ π, from which we get that 1/(p -1/T 2 ) ≤ 5/p as well.

Definition 33 We define R T (t) R T (t) • I E α (t) .
Definition 34 A sequence of random variables (Y t ; t ≥ 0) is called a super-martingale corresponding to a filtration F t , if for all t, Y t is F t -measurable, and for t ≥ 1,

E [Y t -Y t-1 | F t-1 ] ≤ 0.
Next, following Agrawal and Goyal (2013b), we establish a super-martingale process that forms the basis of our proof of the high-probability regret bound.

Definition 35 Let X t R T (t) - 11g p x at V -1 t - 1 T 2 and Y t t w=1 X w .
Lemma 36 (Y t ; t = 0, . . . , T ) is a super-martingale process with respect to filtration F t .

Proof We need to prove that for all t ∈ {1, . . . , T } and any possible filtration

F t-1 , E[Y t -Y t-1 | F t-1 ] ≤ 0, i.e., E R T (t) | F t-1 ≤ 11g p x at V -1 t + 1 T 2 • Note that whether E α (t) is true or not, is completely determined by F t-1 . If F t-1 is such that E α (t) is not true, then R T (t) = R T (t)
• I E α (t) = 0, and the above inequality holds trivially. Moreover, for F t-1 such that E α (t) holds, the inequality follows from Lemma 32.

Note that unlike Agrawal and Goyal (2013b) and [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF], we do not want to require λ ≥ 1. Therefore, we provide the following lemma that features the dependence of

x at 2 V -1 t on λ.
Lemma 37 For all t,

x at 2 V -1 t ≤ 2 + 2 λ log 1 + x at 2 V -1 t . Proof Note, that x at V -1 t ≤ (1/ √ λ) x at ≤ (1/ √ λ)
and for all 0 ≤ x ≤ 1, we have

x ≤ 2 log(1 + x). (4)
We now consider two cases depending on λ. If λ ≥ 1, we know that 0 ≤ x at V -1 t ≤ 1 and therefore by ( 4),

x at 2 V -1 t ≤ 2 log 1 + x at 2 V -1 t . Similarly, if λ < 1, then 0 ≤ λ x at 2 V -1
t ≤ 1 and we get

x at 2 V -1 t ≤ 2 λ log 1 + λ x at 2 V -1 t ≤ 2 λ log 1 + x at 2 V -1 t .
Combining the two, we get that for all λ ≥ 0,

x at 2 V -1 t ≤ max 2, 2 λ log 1 + x at 2 V -1 t ≤ 2 + 2 λ log 1 + x at 2 V -1 t .
Proof [Theorem 11] First, notice that X t is bounded as

|X t | ≤ 1 + 11g p √ λ + 1 T 2 ≤ g p 11 √ λ + 2 •
Thus, we can apply the Azuma-Hoeffding inequality to obtain that with probability at least

1 -δ/2, T t=1 R T (t) ≤ T t=1 11g p x at V -1 t + T t=1 1 T 2 + 2 T t=1 g 2 p 2 11 √ λ + 2 2 log 2 δ •
Since p and g are constants, then with probability 1 -δ/2,

T t=1 R T (t) ≤ 11g p T t=1 x at V -1 t + 1 T + g p 11 √ λ + 2 2T log 2 δ •
The last step is to upperbound

T t=1 x at V -1 t
. For this purpose, Agrawal and Goyal (2013b) rely on the analysis of [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF] and the assumption that λ ≥ 1. We provide an alternative approach using Cauchy-Schwartz inequality, Lemma 15, and Lemma 37 to get

T t=1 x at) V -1 t ≤ T T t=1 x at 2 V -1 t ≤ T 2 + 2 λ log |V T | |Λ| ≤ 2 + 2λ λ dT log 1 + T Kλ •
Finally, we know that E α (t) holds for all t with probability at least 1 -δ/2 and R T (t) = R T (t) for all t with probability at least 1 -δ/2. Hence, with probability 1 -δ,

R T ≤ 11g p 2 + 2λ λ dT log 1 + T Kλ + 1 T + g p 11 √ λ + 2 2T log 2 δ • 6.6 Regret bound 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 t j+1 -1 , i.e., received before and during the phase j. We have the following two lemmas for any phase j. Let V j Λ + t j -1 s=t j-1 x as x T as and let α j stand for α t j for simplicity.

Lemma 38 For any fixed x ∈ R N , any δ > 0, and β(δ) R 2 log(2/δ) + α Λ , we have for all j,

P |x T ( α j -α)| ≤ x V -1 j β(δ) ≥ 1 -δ.
Proof Defining ξ j t j -1 s=t j-1 x as ε 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 |. (5)
The first term in the right hand side of ( 5) 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 right hand side of (5). We have

x T V -1 j ξ j = t j -1 s=t j-1 (x T V -1 j x as )ε s .
Let us notice that the context vectors (x as ) 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 values x T V -1 j x as are deterministic for all rounds t j-1 ≤ s < t j . Consequently, we can use a variant of Hoeffding bound for scaled sub-Gaussians [START_REF] Wainwright | STAT 210B Advanced mathematical statistics[END_REF], in particular for x T V -1

j ξ j = t j -1 s=t j-1 x T V -1 j x as ε s , to get P    x T V -1 j ξ j ≤ R 2 log 2 δ t j -1 s=t j-1 x T V -1 j x as 2    ≥ 1 -δ,
where ε s is R-sub-Gaussian and x T V -1 j x as is deterministic given F j-2 . We further deduce

P    x T V -1 j ξ j ≤ R 2 log 2 δ t j -1 s=t j-1 x T V -1 j x as x T as V -1 j x    ≥ 1 -δ P    x T V -1 j ξ j ≤ R 2 log 2 δ x T V -1 j   t j -1 s=t j-1 x as x T as   V -1 j x    ≥ 1 -δ P x T V -1 j ξ j ≤ R 2 log 2 δ x T V -1 j x ≥ 1 -δ, since V -1
j is symmetric and

t j -1 s=t j-1 x s x T s ≺ V j (Lemma 16
). We conclude that

P x T V -1 j ξ j ≤ R x V -1 j 2 log 2 δ ≥ 1 -δ.
Lemma 39 For all x ∈ A j , j > 1, we have that

min 1, x V -1 j ≤ 1 t j -t j-1 t j -1 s=t j-1 min 1, x as V -1 s .
Proof Using Lemma 16, we have that

(t j -t j-1 ) min 1, x V -1 j ≤ max x∈A j t j -1 s=t j-1 min 1, x V -1 s ≤ max x∈A j-1 t j -1 s=t j-1 min 1, x V -1 s ≤ t j -1 s=t j-1 min 1, max x∈A j-1 x V -1 s = t j -1 s=t j-1 min 1, x as V -1 s ,
since the algorithm selects (during phase j -1) the arms with the largest width.

We now are ready to upperbound the cumulative regret of SpectralEliminator.

Proof [Theorem 13] Let J log 2 T + 1 and t j 2 j-1 . We have that

R T = T t=1 x T a α -x T at α ≤ 2 + J j=2 t j+1 -1 t=t j min(2, x T a α -x T at α) ≤ 2 + J j=2 t j+1 -1 t=t j min 2, x T a α j -x T at α j + x V -1 j + x t V -1 j β(δ ) ,
in an event ω of probability 1 -δ, where we used Lemma 38 and the union bound in the last inequality for δ δ/(KJ). By definition of the action subset A j at phase j > 1, under ω, we have that

x T a α j -x at α j ≤ x a V -1 j + x at V -1 j β(δ ),
since x a ∈ A j for all j ≤ J. By previous two lemmas and the Cauchy-Schwarz inequality,

R T ≤ 2 + J j=2 t j+1 -1 t=t j min 2, 4β(δ ) x at V -1 j ≤ 2 + (4β(δ ) + 2) J j=2 t j+1 -1 t=t j min 1, x at V -1 t ≤ 2 + (4β(δ ) + 2) J j=2 t j+1 -t j t j -t j-1 t j -1 t=t j-1 min 1, x at V -1 t ≤ 2 + (8β(δ ) + 4) J j=2 t j -1 t=t j-1 min 1, x at V -1 t ≤ 2 + (8β(δ ) + 4) T J j=2 t j -1 t=t j-1 min 1, x at 2 V -1 t ≤ 2 + (8β(δ ) + 4) T J j=2 2 log |V j | |Λ| ≤ 2 + (8β(δ ) + 4) 2dT log 2 (T ) log 1 + T Kλ •
Finally, using J = 1 + log 2 T , δ = δ/(KJ), and β(δ ) ≤ β(δ/(K(1 + log 2 T ))), we obtain the result of Theorem 13.

Remark 40 If we set Λ = I in Algorithm 3 as in Remark 25, we get a new algorithm, LinearEliminator, which is a competitor to SupLinRel [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF] and SupLinUCB [START_REF] Chu | Contextual bandits with linear payoff functions[END_REF] and as a corollary to Theorem 13 also enjoys an O( √ DT ) upper bound on the cumulative regret. Compared to SupLinRel and SupLinUCB, LinearEliminator and its analysis are significantly simpler and more elegant. Furthermore, LinearEliminator is more data-adaptive since it uses self-normalized concentration bounds rather than dataagnostic confidence intervals of the form 2 -u for u ∈ N 0 , which are used in SupLinRel and SupLinUCB. Therefore, LinearEliminator narrows the gap between the practical algorithms and the algorithms with the optimal cumulative regret of O( √ DT ).

Experiments

In this section, we evaluate the empirical regret as well the empirical computational complexity of SpectralTS, SpectralUCB, LinearTS, and LinUCB on artificial datasets with different types of underlying graph structure as well as on MovieLens and Flixster datasets. We do not include SpectralEliminator in our experiments due to its impracticality for small time horizons. 2 We study the sensitivity of the algorithms to the important parame- ters and comment on practical issues. Moreover, we study the effects of different speed-up techniques. In particular, we show the effect of the reduced basis on both the computational complexity and performance of the algorithms and the effect of Sherman-Morrison (the computation of matrix inversions) together with lazy updates (the computation of UCBs) on the running time. In all experiments, we set both the confidence parameter δ, use the uniformly distributed noise satisfying R ≤ 0.05, and average over 5 runs. We performed but do not include the results for different values of δ and R since the results of the experiments are not sensitive to the values of these parameters and follow the same trend.

Artificial datasets

To demonstrate the benefit of spectral algorithms, we perform exhaustive experiments on artificial datasets with various underlying graphs. More precisely, we focus on problems where underlying graphs form a lattice or they are sampled either from the Barabási-Albert (BA) or Erdős-Rényi (ER) graph model. For all experiments on artificial datasets, we set the number of arms N to 500 and the time horizon T to 100. We sample a random vector α such that reward function f Qα is smooth on the graph. We do it by settings only the first 20 elements of α to be nonzero. For a more useful empirical comparison, we set the regularization parameter λ and confidence ellipsoid parameters v (TS) and c (UCB) respectively to the best empirical value over a grid search. We run the algorithms with several different values and select the values which minimized average cumulative regret after a few runs of algorithms. Figure 4 shows the dependence of cumulative regret on parameters with strong indication that SpectralTS and SpectralUCB can leverage smoothness of the reward function and outperform LinearTS and LinUCB.

Erdős-Rényi graphs

For this experiment, we construct the underlying graph as an Erdős-Rényi graph on 500 nodes with parameter 0.005 (the probability of edge appearance). The values of the parameters used for the experiment are listed in Table 1, which are the values where the algorithms perform the best.

Figure 5a shows the cumulative regrets of the algorithms with selected parameters. The regret of spectral algorithms tends to be sublinear while regret of linear algorithms appears to be linear for small T . Moreover, spectral algorithms reach much smaller empirical regrets than their linear counterparts.

SpectralTS

SpectralUCB LinearTS LinUCB

λ = 0.1 v = 0.1 λ = 1 c = 1 λ = 1 v = 0.1 λ = 0.1 c = 0.1
Table 1: The best-performing empirical parameters for the Erdős-Rényi graph model.

Lattice graphs

For lattices, we arrange 500 nodes to form a lattice and connect every pair of nodes by an edge if they are neighbors in the lattice. As for the other experiments, we empirically select the best set of parameters (Table 2) and use them to plot the cumulative regret of algorithms (Figure 5b). Even in this case, spectral algorithms perform well compared to the linear ones.

SpectralTS SpectralUCB

LinearTS LinUCB

λ = 0.01 v = 0.1 λ = 0.1 c = 1 λ = 1 v = 0.1 λ = 0.1 c = 0.1 Table 2:
The best-performing empirical parameters for lattices.

Barabási-Albert graphs

We construct the BA graph for our experiments in the following way. We start with k nodes (k = 3 in our case) without any connections between them. Then, we sequentially add one node at a time. Each new node is connected to m ≤ k previously added nodes and we sampled the connections according to the degrees of existing nodes: the higher the degree, the bigger the chance of the connection. Table 3 summarizes the best empirical values of the parameters for the algorithms and Figure 5c shows the performance of algorithms for the parameters in Table 3. Here we can clearly see that the spectral algorithms outperform the linear ones after just a few rounds. Note that the empirically optimal parameters can sometimes be too aggressive and force an algorithm to exploit more than it should. This is likely the case of SpectralUCB in Figure 5c since the curve of the cumulative regret of SpectralUCB appears to be linear for the time horizon used in our experiment. Therefore, we include Figure 5d, where we plot the cumulative regret of SpectralUCB for an empirically suboptimal value of c = 1 (close to the best theoretical value of c) to demonstrate the sublinear trend of the regret.

SpectralTS

SpectralUCB LinearTS LinUCB

λ = 0.001 v = 0.1 λ = 0.001 c = 0.01 λ = 0.01 v = 0.01 λ = 0.1 c = 0.1
Table 3: The best-performing empirical parameters for the Barabási-Albert graph model.

The effect of smoothness on the regret

In this section, we study the effect of the smoothness of the reward function on the performance of spectral algorithms. We use a BA graph on 500 nodes for the experiment with time horizon 100 and the parameters of the algorithms are set according to table 3. The value of effective dimension is close to 8. We controll the smoothness by explicitly setting the number of eigenvectors used for constructing the reward function by letting 5, 25, 100, or 500 elements of α to be nonzero. Note that the value of the effective dimension is the same for every reward function we used, since the definition of the effective dimension is independent of the reward function. Table 4 shows how the smoothness changes with the number of nonzero elements of α and Figures 6a and 6b confirm that the spectral algorithms are able to leverage spectral properties of underlying graph better when the reward function is smoother. This is also supported by our analysis, since in our experiment, the smoothness of the reward function decreases with a smaller number of eigenvectors and the regret bounds of the spectral algorithms are decreasing with smoothness as well.

Computational complexity improvements

In general, the computation of N UCBs is computationally more expensive than sampling in TS. In Section 5.4, we discuss several possibilities to speed up algorithms. The impact of lazy updates for computing UCBs and effect of Sherman-Morrison formula on matrix inversion is demonstrated in Figure 7. The plot clearly shows that the lazy updates can improve the computation of UCBs to the point where the running time of SpectralUCB is comparable and in some cases even better than the running time of SpectralTS.

Another possible computational-time improvement, discussed in Section 5.4, can be made by extracting only the first L N eigenvectors of the graph Laplacian. First, the computational complexity of such operation is O(Lm log m) where m is the number of edges. Second, the least-squares problem that we have to do in each round of the algorithm is only L-dimensional. In Figure 8 (right), we plot the cumulative regret and the total running time in seconds (log scale) of SpectralUCB for a single user from the MovieLens dataset. We vary L as 20, 200, and 2000 which corresponds to about 1%, 10%, and 100% of basis functions (N = 2019). The total running time also includes the computational savings from lazy updates and iterative matrix inversion. We see that with 10% of the eigenvectors, we achieve a similar performance as for the full set in the fraction of the running time.

MovieLens experiments

In this experiment, we take user preferences and the similarity graph over movies from the MovieLens dataset (Lam and Herlocker, 2012), a dataset of 6k users who rated one million movies. First, we extract a subset of 400 users and 618 movies with at least 500 ratings. Then we divide the dataset into three parts. The first 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 r i,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 r i,j is the payoff of pulling arm j when recommending to user i. The second part of the dataset is used for parameter estimation. Similarly as for the first part, we complete ratings using low-rank factorization. The reason for using a different part of the dataset is to avoid dependencies.

The last part of the dataset is used to build our similarity graph over movies. We factor the dataset in the same way as the first two parts of the dataset. The graph contains an edge between movies i and i if the movie i is among 5 nearest neighbors of the movie i in the latent space of items V. The weights on all edges are set to 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.

Table 5 summarizes the best parameters learned on training part of the dataset. We use the parameters to run the algorithms on test part. Figure 9a shows 20 random users sampled from the testing part of the MovieLens dataset. We evaluate the regret of all four algorithms for T = 500 and compared the running time. We make few observations. First, spectral algorithms are consistently outperforming linear algorithms. Second, as we mention in Section 5.4, we use lazy updates for UCB algorithms which can improve the running time significantly. We see that in our experiment, the running time of UCB algorithms is better than the running time of TS algorithms even though in general, TS algorithms are computationally more efficient than UCB algorithms without lazy updates.

SpectralTS

Flixster experiments

We also perform experiments on users preferences from the movie recommendation website Flixster. 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. Similarly as for Movielens, we extract a subset of users and movies, where each movie has at least 500 ratings. This results in a dataset of 972 movies and 1070 users. As with MovieLens, we complete the missing ratings by a low-rank matrix factorization and used it to construct a 5-NN similarity graph. For Figure 9b, we sample 20 random users and evaluate the regret of all four algorithms for T = 50. Similarly as for MovieLens, we set parameter λ to 0.01 while setting the parameter v of SpectralTS to be ten times smaller than the theoretical value. Table 6: The best-performing empirical parameters for Flixster.

SpectralTS

Additional observations for improving the empirical performance

We give additional indications on how to improve the performance of the algorithms. This can be useful for the deployment of spectral bandits in practice.

• Adjusting the number of edges in the graph. Typically, the real-world datasets do not come with a graph structure. Therefore, we construct a nearest-neighbor graph which connects only the most similar actions. By reducing the number of neighbors, we are increasing the effective dimension (worsening the regret bound) and decreasing smoothness of the function (improving the regret bound). Finding a good trade-off While standard linear bandits 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 three algorithms, SpectralUCB, SpectralTS, and theoretically interesting SpectralEliminator. For all three algorithms, the regret bound only scales with the effective dimension d which is typically much smaller than D for real-world graphs. We also performed experiments and showed that spectral algorithms are able to leverage the structure of the problem when the reward function is smooth on the graph much better than their linear counterparts.

As two side results of independent interest, we provide the regret analysis of LinUCB with the upper bound of O(D √ T ) and define LinearEliminator for which we prove minimaxoptimal regret bound of O( √ DT ). With adaptive confidence bounds and simpler analysis, LinearEliminator becomes a state-of-the-art algorithm among the ones with O( √ DT ) regret.

Figure 1 :

 1 Figure1: Eigenvectors from the Flixster dataset corresponding to the smallest few eigenvalues projected onto the first principal component of the data; x-axis represents components of the eigenvector sorted according to the projection onto the first principal component of the data while y-axis represent the value of the corresponding component of the eigenvector. To produce the figure above, we performed the following steps. (1) Preprocessing: We remove all the users that rated a small number of movies as well as the movies rated by only a few users. This leaves us with a u × m matrix M where u is the number of users and m is the number of movies and entry M i, j of matrix M is the rating of movie j by user i, provided it exists. Note that matrix M might be missing some of the entries. (2) Filling in the missing entries: For this step, we use low-rank matrix factorization[START_REF] Keshavan | Matrix completion from a few entries[END_REF] to obtain u × r matrix U and m × r matrix V, for some given rank r, such that M ≈ UV T . (3) Constructing a similarity graph: We construct the graph by creating an edge between movies i and j if the movie j is among 5 nearest neighbors of the movie i in the latent space of movies V. (4) Visualization: Using the computed matrix V, the matrix capturing the latent space of movies, we can find the direction of the highest variance of the data using PCA on V. This gives us a way to visualize eigenvectors by projecting them on the first principal component. The above visualization shows that the eigenvectors corresponding to smaller eigenvalues tend to be smoother-the values corresponding to actions with their projections close to each other are similar. On the other hand, the eigenvectors corresponding to larger eigenvalues are more chaotic as values for nearby items can vary a lot. This gives a small insight into why a function created as a linear combination of the first few eigenvectors is a smooth reward function. We are more precise about the definition of smoothness and the connection of smooth functions and eigenvectors later in Section 4.

Flixster

Figure 2 :Figure 3 :

 23 Figure 2: Difference between d and 2d old for real world datasets. From left to right: Flixster dataset with N = 972, Movielens dataset with N = 618, and LastFM dataset with N = 804.

  L , Q}: spectral basis of a graph Laplacian L 5: λ, δ: regularization and confidence parameters 6:

Remark 25

 25 Notice that if we set Λ I in Algorithm 1, we recover the LinUCB algorithm. Since log(|V T +1 |/|Λ|)is upperbounded by D log T (Abbasi-Yadkori et al., 2011), we obtain O(D √ T ) upper bound of regret of LinUCB as a corollary of Theorem 8. The known O( √ DT ) upper bound of

Figure 4 :

 4 Figure 4: The dependence of cumulative regret on confidence and regularization parameters.

Figure 7 :

 7 Figure 7: The impact of lazy updates and Sherman-Morrison formula on running time.

Figure 8 :

 8 Figure 8: Cumulative regret and running time of SpectralUCB with reduced basis.

Figure 9 :

 9 Figure 9: Comparison of spectral and linear bandit algorithms for a subset of users.

  SpectralUCB LinearTSLinUCBλ = 0.01 v = 0.1 λ = 0.01 c = 0.11 λ = 1 v = 0.1 λ = 1 c = 1

Table 4 :

 4 The effect of smoothness on the cumulative regret for T = 100.

	Number of nonzero components	5	25	100	500
	Smoothness of the rewards (α T Λα)	1.56 11.16	58.12 216.89
	Regret of SpectralTS	7.99 32.80	94.10 123.79
	Regret of SpectralUCB	3.05 22.84 108.19 130.54

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

since the algorithm updates confidence ellipsoid only at the end of the phase

Acknowledgments

The authors wish to thank anynomous reviewers and Claudio Gentile for helpful suggestions. We are also grateful to András György for pointing out the connection between the effective dimension and the capacity formula of parallel Gaussian channels, and also for his suggestions on fixing the asymptotics of our lower bound.

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), European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Inria and Otto-von-Guericke-Universität Magdeburg associated-team North-European project Allocate, Nord-Pas-de-Calais Regional Council, CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020, French National Research Agency projects ExTra-Learn (n.ANR-14-CE24-0010-01) and BoB (n.ANR-16-CE23-0003), Intel Corporation, FMJH Program PGMO with the support to this program from CRITEO.

and adjusting the number of the edges can improve the performance of the algorithms significantly.

• Scaling the confidence ellipsoid, i.e., parameter c in SpectralUCB and parameter v in SpectralTS . Typically, the algorithms are too conservative and the bounds are too loose in order to include the worst-case case. Therefore, reducing the size of the confidence ellipsoid can sometimes improve the empirical performance of the algorithm at the price that some bounds might not hold anymore. In our experiments, we used the values for which the algorithms had good empirical performance.

• The magnitude of regularization parameter λ. By setting λ to a large value, all regularized eigenvalues become similar and therefore the algorithms take the graph structure into account less. On the other hand, if the regularization parameter λ is small, the algorithms depend on the graph structure more. Therefore, in order to leverage the graphs' structure, we have to find a good compromise while setting λ.

In our experiments, we found that setting λ well was important and we tried several values of λ to pick the value with the best empirical performance.

• Scaling the graph weights. By scaling all the weights of the graph by some constant we scale the gap between the eigenvalues and therefore change the value of the effective dimension. Moreover, by scaling the weights we are also changing the smoothness of the reward function. Therefore, by simply scaling the weights we can make the graphs more useful for spectral bandits.

Conclusion

We presented spectral bandits inspired mostly by the applications in 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.